A Tutorial on Distributed Multi-Armed Bandits

This tutorial paper provides an overview of distributed multi-armed bandit problems in networks of multiple agents. Each agent repeatedly selects an action from a fixed set of choices and receives a random reward, aiming to balance exploration and exploitation. The agents are allowed to communicate only with their neighbors, where the neighbor relations are described by a possibly time-varying graph. Two main settings are considered. Two main settings are discussed. In the first setting, agents observe identical reward distributions for each action. We present two distributed algorithms based on the classical UCB and KL-UCB methods. It is shown that each agent can achieve a lower logarithmic regret compared to the standard single-agent case, as long as the agent has at least one neighbor and the communication graph is strongly connected. The improvement in regret is related to the size of the agent's local neighborhood and the structure of the network. These algorithms can be further modified to be fully resilient to adversarial agents who may inject untrustworthy information, using communication redundancy. In the second setting, agents observe different reward distributions for the same actions. The goal is to minimize cumulative expected regret with respect to the true rewards, defined as the average of all agents' mean rewards. A distributed algorithm is introduced that guarantees optimal regret performance for each agent when the network remains jointly connected over time. All proposed algorithms operate in a fully distributed manner and do not require any global knowledge of the network. This tutorial highlights the theoretical foundations, algorithmic designs, and resilience properties of distributed bandit algorithms, with an emphasis on performance guarantees under limited communication and local observations. Open problems and possible future directions are also discussed.