Collaborative Multi-agent Stochastic Linear Bandits
This work addresses the challenge of distributed decision-making in networked agents, which is incremental as it extends existing bandit methods to a multi-agent setting with communication constraints.
The paper tackles the problem of collaborative multi-agent stochastic linear bandits, where agents in a network aim to minimize overall regret by selecting the best global action based on average reward parameters, and it achieves a regret bound of order O(√(T/(N log(1/|λ₂|)))·(log T)²).
We study a collaborative multi-agent stochastic linear bandit setting, where $N$ agents that form a network communicate locally to minimize their overall regret. In this setting, each agent has its own linear bandit problem (its own reward parameter) and the goal is to select the best global action w.r.t. the average of their reward parameters. At each round, each agent proposes an action, and one action is randomly selected and played as the network action. All the agents observe the corresponding rewards of the played actions and use an accelerated consensus procedure to compute an estimate of the average of the rewards obtained by all the agents. We propose a distributed upper confidence bound (UCB) algorithm and prove a high probability bound on its $T$-round regret in which we include a linear growth of regret associated with each communication round. Our regret bound is of order $\mathcal{O}\Big(\sqrt{\frac{T}{N \log(1/|λ_2|)}}\cdot (\log T)^2\Big)$, where $λ_2$ is the second largest (in absolute value) eigenvalue of the communication matrix.