Kernel Methods for Cooperative Multi-Agent Contextual Bandits
arXiv:2008.06220
Abstract
Cooperative multi-agent decision making involves a group of agents cooperatively solving learning problems while communicating over a network with delays. In this paper, we consider the kernelised contextual bandit problem, where the reward obtained by an agent is an arbitrary linear function of the contexts' images in the related reproducing kernel Hilbert space (RKHS), and a group of agents must cooperate to collectively solve their unique decision problems. For this problem, we propose \textsc{Coop-KernelUCB}, an algorithm that provides near-optimal bounds on the per-agent regret, and is both computationally and communicatively efficient. For special cases of the cooperative problem, we also provide variants of \textsc{Coop-KernelUCB} that provides optimal per-agent regret. In addition, our algorithm generalizes several existing results in the multi-agent bandit setting. Finally, on a series of both synthetic and real-world multi-agent network benchmarks, we demonstrate that our algorithm significantly outperforms existing benchmarks.
19 pages including supplement, camera-ready at ICML 2020
References in corpus (12)
- A Contextual-Bandit Approach to Personalized News Article Recommendation
- Analysis of Thompson Sampling for the multi-armed bandit problem
- Distributed Learning in Multi-Armed Bandit with Multiple Players
- Distributed Clustering of Linear Bandits in Peer to Peer Networks
- Online Clustering of Bandits
- Delay and Cooperation in Nonstochastic Bandits
- Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
- Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits
- Bandit optimisation of functions in the Matérn kernel RKHS
- Online Clustering of Contextual Cascading Bandits
- Cooperative Online Learning: Keeping your Neighbors Updated
- Improved Algorithm on Online Clustering of Bandits