QuACK: A Multipurpose Queuing Algorithm for Cooperative $k$-Armed Bandits
This provides a general solution for multi-agent bandit problems, enabling efficient algorithms across various settings like heavy-tailed or differentially private bandits, though it is incremental as it builds on existing single-agent methods.
The paper tackles the cooperative stochastic k-armed bandit problem by introducing a black-box reduction that extends any single-agent bandit algorithm to a multi-agent setting, proving tight regret guarantees and demonstrating competitive or superior performance against specialized algorithms in experiments.
We study the cooperative stochastic $k$-armed bandit problem, where a network of $m$ agents collaborate to find the optimal action. In contrast to most prior work on this problem, which focuses on extending a specific algorithm to the multi-agent setting, we provide a black-box reduction that allows us to extend any single-agent bandit algorithm to the multi-agent setting. Under mild assumptions on the bandit environment, we prove that our reduction transfers the regret guarantees of the single-agent algorithm to the multi-agent setting. These guarantees are tight in subgaussian environments, in that using a near minimax optimal single-player algorithm is near minimax optimal in the multi-player setting up to an additive graph-dependent quantity. Our reduction and theoretical results are also general, and apply to many different bandit settings. By plugging in appropriate single-player algorithms, we can easily develop provably efficient algorithms for many multi-player settings such as heavy-tailed bandits, duelling bandits and bandits with local differential privacy, among others. Experimentally, our approach is competitive with or outperforms specialised multi-agent algorithms.