Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost
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 order as that incurred
by an optimal single-agent algorithm for $NT$ rounds. Remarkably, we derive an
information-theoretic lower bound on the communication cost of the distributed
contextual linear bandit problem with stochastic contexts, and prove that our
proposed algorithm is nearly minimax optimal in terms of \emph{both regret and
communication cost}. Finally, we propose DecBE-LUCB, a fully decentralized
version of DisBE-LUCB, which operates without a central server, where agents
share information with their \emph{immediate neighbors} through a carefully
designed consensus procedure.