Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost. (arXiv:2205.13170v1 [cs.LG])

We study distributed contextual linear bandits with stochastic contexts,
where $N$ agents act cooperatively to solve a linear bandit-optimization
problem with $d$-dimensional features. For this problem, we propose a
distributed batch elimination version of the LinUCB algorithm, DisBE-LUCB,
where the agents share information among each other through a central server.
We prove that over $T$ rounds ($NT$ actions in total) the communication cost of
DisBE-LUCB is only $\tilde{\mathcal{O}}(dN)$ and its regret is at most
$\tilde{\mathcal{O}}(\sqrt{dNT})$, which is of the same …

arxiv communication cost distributed linear minimax