Federated Bandit: A Gossiping Approach

Zhaowei Zhu, Jingxuan Zhu, Ji Liu, Yang Liu

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:

  1. 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.
The Gossip Protocol allows agents to exchange private data summaries to collaboratively estimate global rewards without a central server.
  1. 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.
The Local Consistency Check mechanism ensures that agents wait for consensus before committing to specific actions, mitigating the impact of local biases.

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

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.
BibTeX
@inproceedings{zhu2021federated,
  author = {Zhaowei Zhu and Jingxuan Zhu and Ji Liu and Yang Liu},
  title = {{Federated Bandit: A Gossiping Approach}},
  booktitle = {Proc. ACM Meas. Anal. Comput. Syst},
  year = {2021},
  url = {https://openreview.net/forum?id=HFIVoDVEDkr},
}
Figure