Minimax-Optimal Regret for Heterogeneous Federated Bandits

In heterogeneous federated bandits, agents on a communication graph face different reward distributions and seek the arm with the highest global mean, that is, the mean reward averaged across agents. We propose Adaptive Federated Elimination (AFE). It estimates global means from all agents' samples and removes clearly suboptimal arms early, so that agents incur little regret while waiting for messages. For $N$ agents, $K$ arms, and $T$ rounds on any connected graph of diameter $D$, AFE achieves expected regret $O(D+\sqrt{KT/N})$ for every agent. We establish a matching lower bound on every connected graph, showing that AFE is minimax optimal. AFE also adapts to the suboptimality gaps ${\Delta }_i$ and achieves regret $O({\sum }_{{\Delta }_i>0}\log (NT)/(N{\Delta }_i))$ plus a cost of waiting for messages that does not depend on $T$. This bound applies the same factor $\log (NT)$ to every arm. We refine it and show that each arm needs only a smaller factor, which depends on the arm's gap and on how many arms have gaps smaller than or close to that gap. When all suboptimal arms have similar gaps, a lower bound shows that AFE is optimal up to additive costs that do not depend on $T$. In a complete-graph example, AFE's refined bound is smaller than the guarantees of recent algorithms by a factor of order $\log (NT)/\log \log (NT)$.