A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits
A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits
复制标题
DOI：
10.48550/arxiv.2207.03106
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Jiafan He;Tianhao Wang;Yifei Min;Quanquan Gu
中科院分区：
文献类型：
--
作者：
Jiafan He;Tianhao Wang;Yifei Min;Quanquan Gu
我们研究了联邦上下文线性盗贼，其中$M$代理在中心服务器的帮助下相互协作来解决全局上下文线性盗贼问题。我们考虑了异步设置，其中所有代理独立工作，一个代理与服务器之间的通信不会触发其他代理的通信。基于乐观主义原理，我们提出了一个简单的算法--Texttt{FedLinUCB}。我们证明了Texttt{FedLinUCB}的遗憾有界于$tide{O}(d\sqrt{\sum_{m=1}^M T_m})$，通信复杂度为$tilde{O}(DM^2)$，其中$d$是上下文向量的维度，$T_m$是第$m个主体与环境交互的总次数。就我们所知，这是第一个被证明有效的算法，它允许联邦上下文线性强盗的完全异步通信，同时实现与单代理设置中相同的后悔保证。
We study federated contextual linear bandits, where $M$ agents cooperate with each other to solve a global contextual linear bandit problem with the help of a central server. We consider the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents' communication. We propose a simple algorithm named \texttt{FedLinUCB} based on the principle of optimism. We prove that the regret of \texttt{FedLinUCB} is bounded by $\tilde{O}(d\sqrt{\sum_{m=1}^M T_m})$ and the communication complexity is $\tilde{O}(dM^2)$, where $d$ is the dimension of the contextual vector and $T_m$ is the total number of interactions with the environment by $m$-th agent. To the best of our knowledge, this is the first provably efficient algorithm that allows fully asynchronous communication for federated contextual linear bandits, while achieving the same regret guarantee as in the single-agent setting.