This paper, presented at SIGMETRICS 2021, introduces a framework for solving the Multi-Armed Bandit (MAB) problem in a decentralized, federated environment where agents have biased local data and must preserve privacy.
TL;DR
The authors propose Gossip_UCB and Fed_UCB, decentralized algorithms that allow a network of agents to collaboratively find the globally optimal "arm" (action) using only peer-to-peer communication. By combining Upper Confidence Bound (UCB) logic with a gossip protocol and differential privacy, the system enables agents to overcome local observational biases without ever sharing raw data or relying on a central server.
What Problem Does This Paper Address?
In a standard Multi-Armed Bandit problem, an agent tries to maximize rewards by balancing exploration (trying new actions) and exploitation (choosing the best-known action). However, in many real-world "federated" scenarios—like hospitals testing different treatment plans—individual agents only see a small, potentially biased slice of the truth.
For example, a hospital in a specific demographic might see a treatment as highly effective, while the global average is much lower. If the hospital learns only from its own data, it will converge on a sub-optimal strategy. To find the "true" global optimum, agents must share information.
The challenges addressed here are:
- Decentralization: There is no central server to aggregate data; agents only talk to their neighbors on a communication graph.
- Heterogeneous Rewards: Local observations are biased; the global reward is the average of all local expectations.
- Privacy: Agents cannot share raw observations due to regulatory or privacy concerns.
Methods
The authors propose two main algorithms:
1. Gossip_UCB
This algorithm adapts the classic UCB1 policy to a decentralized setting.
- Gossip Protocol: Instead of a simple empirical mean, agents maintain a local estimate of the global reward for each arm, which they update by "gossiping" (averaging) with a randomly selected neighbor at each time step.
- Local Consistency: To ensure the gossip has time to propagate, the authors introduce a "local consistency" check. An agent will only pull an arm if its local sample count for that arm isn't significantly higher than its neighbors' estimates. This prevents any single agent from "running away" with a sub-optimal decision before the network can reach a consensus.
2. Fed_UCB
This is the differentially private (DP) version of the algorithm.
- Partial Sums Mechanism: Simply adding noise to every observation would cause the total noise to grow linearly with time, ruining the learning rate. Instead, the authors use a "partial sums" (binary tree) approach. They add Laplacian noise to blocks of data, ensuring that the total noise added to an estimate only grows logarithmically ($O(\log T)$) while maintaining $\epsilon$-differential privacy.
Datasets
The authors evaluate their approach using:
- Synthetic Datasets: Controlled environments with $N$ agents and $M$ arms, where local rewards are intentionally biased to test if the gossip protocol can successfully recover the global mean.
- UCI Diabetes Dataset: A real-world medical dataset containing over 100,000 inpatient records. The authors mapped 23 types of medications to 5 "arms" and used patient readmission status as the reward signal. This simulates a federated learning scenario where multiple hospitals collaborate to find the best medication strategy for diabetes.
Key Insights and Ideas
- The Coupling Challenge: The most significant theoretical contribution is analyzing the "coupling" between bandit learning and gossip convergence. In standard gossip, the data is static. Here, the data is generated by the bandit process itself, which is in turn influenced by the (potentially stale) gossiped information.
- Heterogeneity is the Motivator: Unlike previous "distributed bandit" papers that assume every agent sees the same reward distribution, this paper explicitly handles the case where local data is "wrong." This makes it much more applicable to real-world federated learning.
- Privacy-Regret Tradeoff: The authors prove that introducing differential privacy only increases the regret by a factor of roughly $O(\log^{1.5} T)$, maintaining the desirable sub-linear regret property.
Key Results
- Regret Bounds: The authors prove that
Gossip_UCBachieves $O(\log T)$ regret, which is the theoretical gold standard for MAB problems.Fed_UCBachieves $O(\log^{2.5} T)$ regret. - Network Connectivity: The regret is shown to be a function of the second-largest eigenvalue of the gossip matrix ($\lambda_2$), which represents the "expansion" or connectivity of the network. Better-connected graphs lead to faster consensus and lower regret.
- Empirical Validation: In experiments,
Fed_UCBsuccessfully identified the optimal medication in the diabetes dataset across multiple "hospitals" even with strict privacy constraints ($\epsilon=1$). The regret was shown to scale inversely with the privacy budget ($\epsilon$), matching the theoretical predictions.
Limitations and Future Work
- Computational Complexity: The current regret bounds have a high polynomial dependence on the number of agents ($N$) and arms ($M$), which might limit scalability for massive networks or huge action spaces.
- Contextual Bandits: The paper focuses on the "classical" bandit where rewards are independent of the state. The authors suggest extending this to contextual bandits, where agents make decisions based on specific user features (e.g., a patient's specific medical history), as a vital next step.
- Continuous Actions: The current model assumes a finite set of $M$ arms. Extending this to continuous action spaces remains an open challenge for this gossiping approach.
Summary updated