Timezone: »

 
Poster
Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost
Sanae Amani · Tor Lattimore · Andras Gyorgy · Lin Yang

Wed Jul 26 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #328
in Poster Session 4 »
We study distributed contextual linear bandits with stochastic contexts, where $N$ agents/learners act cooperatively to solve a linear bandit-optimization problem with $d$-dimensional features over the course of $T$ rounds. For this problem, we derive the first ever information-theoretic lower bound $\Omega(dN)$ on the communication cost of any algorithm that performs optimally in a regret minimization setup. We then 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 the communication cost of DisBE-LUCB, matches our lower bound up to logarithmic factors. In particular, for scenarios with known context distribution, the communication cost of DisBE-LUCB is only $\tilde{\mathcal{O}}(dN)$ and its regret is $\tilde{\mathcal{O}}(\sqrt{dNT})$, which is of the same order as that incurred by an optimal single-agent algorithm for $NT$ rounds. We also provide similar bounds for practical settings where the context distribution can only be estimated. Therefore, our proposed algorithm is nearly minimax optimal in terms of *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 *immediate neighbors* through a carefully designed consensus procedure.
[ PDF]  [ Poster] 

Author Information

Sanae Amani (University of California, Los Angeles)
Tor Lattimore (DeepMind)
Andras Gyorgy (Google DeepMind)
Lin Yang (UCLA)

More from the Same Authors