Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost
Jul 24, 2023
Speakers
Sanae Amani
Speaker · 0 followers
Tor Lattimore
Speaker · 1 follower
Andras Gyorgy
Speaker · 0 followers
Lin F. Yang
Speaker · 0 followers
About
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 Ω(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 𝒪̃(dN) and its regret is 𝒪̃(√(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.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 Ω(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 t…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Exploiting locality in high-dimensional Factorial hidden Markov models
Watch later
Actor-Critic Alignment for Offline-to-Online Reinforcement Learning
Watch later
Zishun Yu, …
Why Random Pruning Is All We Need to Start Sparse
Watch later
On the Convergence of SARSA with Linear Function Approximation
Watch later
Revisiting Data-Free Knowledge Distillation with Poisoned Teachers
Watch later
Junyuan Hong, …
