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.
翻译:我们根据乐观原则研究联结背景线性土匪, 美元代理商在中央服务器的帮助下合作解决全球背景线性土匪问题。 我们考虑无序环境, 所有代理商独立工作, 一个代理商和服务器之间的通信不会触发其他代理商的通信。 我们根据乐观原则提出一个名为\ texttt{FedLinUCB} 的简单算法。 我们证明,\ textt{FedLinUCB} 的遗憾受 $\tilde{O} (d\ sqrt=1 ⁇ m=MT_m} (d\sqrt=1 ⁇ m=MT_m}) 的约束, 通信的复杂性是$\ tilde{O} (dM2), 其中美元是背景矢量的维度, $T_m美元是第代理商与环境互动的总数。 据我们所知, 这是第一种非常有效的算法有效的算法, 能够让被相联结的背景线性土匪充分进行无序的通信联系, 同时实现与单一代理人设置的同样的遗憾保证。