Abstract
In this paper, we study \emph{Federated Bandit}, a decentralized Multi-Armed Bandit problem with a set of $N$ agents, who can only communicate their local data with neighbors described by a connected graph $G$. Each agent makes a sequence of decisions on selecting an arm from $M$ candidates, yet they only have access to local and potentially biased feedback/evaluation of the true reward for each action taken. Learning only locally will lead agents to sub-optimal actions while converging to a no-regret strategy requires a collection of distributed data. Motivated by the proposal of federated learning, we aim for a solution with which agents will never share their local observations with a central entity, and will be allowed to only share a private copy of his/her own information with their neighbors. We first propose a decentralized bandit algorithm Gossip_UCB, which is a coupling of variants of both the classical gossiping algorithm and the celebrated Upper Confidence Bound (UCB) bandit algorithm. We show that Gossip_UCB successfully adapts local bandit learning into a global gossiping process for sharing information among connected agents, and achieves guaranteed regret at the order of $O(\max\{ \texttt{poly}(N,M) \log T, \texttt{poly}(N,M)\log_{\lambda_2^{-1}} N\})$ for all $N$ agents, where $\lambda_2\in(0,1)$ is the second largest eigenvalue of the expected gossip matrix, which is a function of $G$. We then propose Fed_UCB, a differentially private version of Gossip_UCB, in which the agents preserve $\epsilon$-differential privacy of their local data while achieving $O(\max \{\frac{\texttt{poly}(N,M)}{\epsilon}\log^{2.5} T, \texttt{poly}(N,M) (\log_{\lambda_2^{-1}} N + \log T) \})$ regret.
Introduction
Standard Multi-Armed Bandit (MAB) problems involve an agent balancing exploration and exploitation to maximize rewards. However, in many real-world "federated" scenarios—such as hospitals testing treatment plans—individual agents often only observe biased, local slices of the global truth. For instance, a hospital in a specific demographic might see a treatment as highly effective, while the global average is much lower. Learning solely from local data can lead to convergence on sub-optimal strategies. To achieve a globally optimal outcome, agents must collaborate without relying on a central server or compromising data privacy.
This paper addresses three core challenges: decentralization (peer-to-peer communication only), heterogeneous rewards (biased local observations), and privacy (restrictions on sharing raw data). The authors propose two algorithms, Gossip_UCB and Fed_UCB, to enable collaborative learning in these environments.
Methodology
Gossip_UCB: Decentralized Learning via Peer-to-Peer Exchange
Gossip_UCB adapts the classic UCB1 policy to a decentralized setting using two key mechanisms:
- Gossip Protocol: Instead of relying on a central empirical mean, agents maintain local estimates of global rewards. These estimates are updated by "gossiping"—averaging information with a randomly selected neighbor at each time step.
- Local Consistency: To ensure information propagates effectively, the authors introduce a local consistency check. An agent only pulls an arm if its local sample count is consistent with its neighbors' estimates, preventing premature convergence on sub-optimal actions before the network reaches a consensus.
Fed_UCB: Ensuring Differential Privacy
Fed_UCB extends the gossiping framework with $\epsilon$-differential privacy (DP). To prevent noise from growing linearly with time, the authors use a Partial Sums Mechanism based on a binary tree structure. By adding Laplacian noise to blocks of data, the total noise added to an estimate grows only logarithmically ($O(\log T)$), preserving the sub-linear regret property essential for effective learning.
Evaluation and Results
The algorithms were evaluated using synthetic datasets with intentionally biased rewards and the real-world UCI Diabetes Dataset. In the medical scenario, 23 medications were mapped to 5 arms, using patient readmission status as the reward signal to simulate a federated hospital network.
Key findings include:
- Regret Performance: Gossip_UCB achieves the theoretical standard of $O(\log T)$ regret. Fed_UCB maintains sub-linear regret at $O(\log^{2.5} T)$, demonstrating a manageable privacy-regret tradeoff.
- Network Impact: Regret is a function of the network's connectivity, specifically the second-largest eigenvalue ($\lambda_2$) of the gossip matrix. Better-connected graphs facilitate faster consensus.
- Empirical Success: Experiments confirmed that Fed_UCB successfully identified optimal treatments even under strict privacy constraints ($\epsilon=1$), with regret scaling inversely with the privacy budget as predicted.
Conclusion
By coupling bandit learning with gossip convergence, this research provides a robust framework for decentralized, privacy-preserving decision-making. The "coupling challenge"—where data is generated by the bandit process itself and influenced by stale gossiped info—is the core theoretical hurdle overcome here. While the current approach shows high polynomial dependence on the number of agents and arms, it sets the stage for future extensions into contextual bandits and continuous action spaces.
Summary updated