Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost

05/26/2022

∙

by   Sanae Amani, et al.

∙

0

∙

share

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 𝒪̃(dN) and its regret is at most 𝒪̃(√(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 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.