Federated Multi-Armed Bandits via Distributed Tsallis Mirror Descent

We study a multi-agent multi-armed bandit problem in which the agents of a network learn personalized (agent-specific) policies. Our method is designed for networks whose agents form clusters with similar loss distributions, in particular a shared optimal arm, while the cluster assignments are unknown; each agent's regret is measured against the optimal arm of its own cluster. We propose GTV-Tsallis, which couples local instances of Tsallis-INF, a best-of-both-worlds mirror-descent bandit algorithm, through generalized total variation minimization (GTVMin) on the agents' policies. Consensus-based methods force all agents onto one shared policy. GTVMin instead penalizes disagreement between neighbors, so policies stay piecewise constant across cluster boundaries and distinct clusters converge to different arms without first estimating the clusters. A policy-similarity gate restricts the coupling to neighbors whose policies agree. We evaluate GTV-Tsallis in homogeneous and heterogeneous settings, under stochastic and adversarial losses, across four network topologies and two real-world graphs. Whenever agents have same-cluster neighbors it reduces regret relative to non-cooperative Tsallis-INF and to cooperative baselines that assume a shared optimal arm: final regret falls by more than half in the homogeneous setting and by 17–30% on the real-world graphs. When every edge crosses clusters, the policy-similarity gate matches the non-cooperative baseline.