PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Bandit: A Gossiping Approach

Zhaowei Zhu, Jingxuan Zhu, Ji Liu, Yang Liu

arXiv:2010.12763v2cs.LGcs.MA

TL;DR

The paper studies how decentralized agents can learn a best arm when their local rewards are biased and sharing observations with a central entity is undesirable. It combines gossiping with UCB and proposes a differentially private variant; the paper reports regret guarantees for both algorithms and experiments on synthetic and real data.

  • Problem

    The paper asks how agents with locally biased rewards can learn the best arm through decentralized cooperation without sending local observations to a central server.

    Source: §1 · pp. 1–2

  • Method

    Gossip_UCB combines UCB with gossiping among neighboring agents, and Fed_UCB is its differentially private variant.

    Source: §1 · p. 3, §3 · p. 5

  • Results

    Both algorithms achieve weak regret bounds depending on the numbers of agents and arms, time horizon, and graph connectivity, and synthetic and real-data experiments verify the approach’s feasibility.

    Source: §6 · p. 21

  • Takeaways & Limitations

    The paper presents gossip-based federated bandits as a feasible approach to decentralized learning with heterogeneous data and a privacy guarantee for Fed_UCB.

    Source: §1 · p. 3, §6 · p. 21

    The tightness of the Gossip_UCB regret bound in the number of agents and graph structure remains an open question.

    Source: §3.6 · p. 15

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper frames federated bandits as decentralized sequential learning with heterogeneous, locally biased rewards, where agents need cooperation without sending observations to a central server. It introduces gossip-based and differentially private approaches and positions them against prior work that generally does not combine gossiping with heterogeneous rewards.

1 INTRODUCTION

  • Heterogeneous datasets can encode local observation or sampling bias, unlike homogeneous data, which the paper describes as unbiased even without cooperation.The stated aim is to smooth local biases while protecting private information.Source: §1 · p. 2
  • Agents observe locally biased rewards, so learning the best arm requires cooperation while keeping local observations decentralized.The paper models each arm’s true reward as the average of agents’ locally observed rewards in expectation.Source: §1 · p. 2
  • Gossip_UCB combines gossiping with bandit learning, and Fed_UCB extends it to preserve agents’ ε-differential privacy.The introduction also reports that Fed_UCB was tested on a real medical dataset.Source: §1 · p. 3

1.1 Related Works

  • Prior distributed MAB work mostly omits either cheap gossip-based consensus or heterogeneous rewards, while cited private bandit methods generally assume one agent or homogeneous rewards.The paper presents its work as addressing heterogeneous rewards in decentralized MAB and a privacy guarantee for that setting.Source: §1.1 · pp. 3–4

2 PROBLEM FORMULATION

The problem is a networked bandit in which agents choose among shared arms but observe locally biased rewards. Its formulation specifies how local observations relate to true rewards, the regret objective, a privacy model, and a connected communication graph.

2 PROBLEM FORMULATION

  • Each of N agents chooses among M shared arms in parallel and observes a locally biased reward rather than the arm’s exact reward.The formulation assumes i.i.d. reward processes with support in [0, 1], and immediate local feedback; it focuses on delays from gossiping.Source: §2 · p. 4
  • The mean true reward of each arm equals the average of the agents’ observed-reward means, so averaging is intended to cancel local biases.The paper notes that the global reward can be generalized to a convex combination of local rewards.Source: §2 · p. 4
  • Each agent’s objective is weak regret minimization, with the goal that R_i(T) = o(T) for every agent.Agents observe only their own rewards, and no single agent can learn the optimal decision without communication.Source: §2 · p. 5

2.1 Privacy Guarantee

  • The privacy target concerns each agent’s sequential observations, with differential privacy defined over streams differing at one time step.The online setting requires the privacy guarantee for every horizon T.Source: §2.1 · p. 5

2.2 Communication Graph

  • Communication uses a simple, undirected, connected graph whose edges link neighbors; at each time, one neighboring pair exchanges information.Source: §2.2 · p. 5

3 GOSSIP UCB

Gossip_UCB extends UCB to decentralized bandit learning by gossiping estimates as agents make new observations. Its design addresses the interaction between delayed information propagation, local decisions, and heterogeneous rewards.

3 GOSSIP UCB

  • Gossip_UCB couples gossiping with the UCB1 index policy and incorporates newly arriving local observations into the gossip process.Unlike classical gossiping over initial data, the gossiped information also affects subsequent arm choices and observations.Source: §3 · pp. 5–6

3.1 Preliminaries

  • Agents track local sample counts, estimates of global maximum pulls, sample means, reward estimates, and confidence bounds to select arms.The arm choice maximizes the local reward estimate plus its confidence bound.Source: §3.1 · p. 6

3.2 Algorithm

  • Agents share estimated pull counts to maintain local consistency and gossip reward estimates; the figure depicts one active link and local consistency checks via sample counts.The algorithm encourages each agent’s pulls of an arm to stay within N of its local estimate of the global maximum pulls.Source: §3.2 · pp. 6–7, Figure 1 · p. 7

3.3 Technical Challenges

  • Gossiping delays and local consistency requirements can make confidence indices inaccurate, while poor decisions can affect later gossiping and other agents’ decisions.The challenge is amplified when agents have heterogeneous observations and information must propagate through the network.Source: §3 · p. 6, §3.3 · p. 7

24 end

The analysis uses local sample-count consistency to support decentralized confidence estimates despite heterogeneous rewards. It then bounds both the fluctuation and bias of local estimates, which are used in the regret analysis.

3.4 Guarantees on the Consistency among Agents

  • Information about arm counts propagates through the neighbor graph, while the consistency analysis accounts for graph distances and delays.The local consistency argument is presented as a sequence: model propagation, bound achieved local consistency, then characterize agents’ knowledge.Source: §3.4 · p. 9
  • The local consistency condition keeps each agent’s arm count within 3MN of its locally propagated estimate of the maximum count.This is the actual local consistency bound used to relate neighboring agents’ selections.Source: §3.4 · pp. 8, 10
  • When an agent has at least (3M+1)N pulls of an arm, global consistency bounds how differently agents have sampled that arm.The section states that no agent pulls one arm more than twice as often as another, supporting local arm selection without global sample counts.Source: §3.4 · p. 11

3.5 Concentration Bound for Local Estimates

  • With sufficiently many pulls, the section bounds local-estimate fluctuations with high probability and separately treats bias from heterogeneous rewards.The fluctuation result applies when every agent’s count reaches max{L, (3M+1)N}; the local estimate may be biased relative to the arm’s global mean.Source: §3.5 · pp. 11–13

Wrapping up: concentration bound for local gossiping estimates.

The concentration analysis supplies a confidence bound used to derive a regret upper bound for Gossip_UCB. The bound includes a term growing logarithmically with time, while the section leaves its tightness in the number of agents and graph structure unresolved.

Wrapping up: concentration bound for local gossiping estimates.

3.6 Regret Upper Bound for Gossip_UCB

  • The Gossip_UCB regret upper bound includes an O(N log T) term and another term whose order does not depend on T.The section relates the time-independent term to L, which is determined by the gossip matrix’s second eigenvalue and N.Source: §3.6 · pp. 13, 15
  • For a fully connected graph, the regret is lower-bounded by Ω(log T), while tightness in N and G remains an open question.The lower-bound comparison uses an ideal setting with simultaneous information sharing and no delay.Source: §3.6 · p. 15

4 FED_UCB: PRIVACY PRESERVING GOSSIP_UCB

The section frames sequential differential privacy as requiring protection across repeated disclosures of observations. It introduces partial-sum and Laplacian-noise algorithms as components of the privacy-preserving approach.

4 FED_UCB: PRIVACY PRESERVING GOSSIP_UCB

  • Sequential privacy must protect an observation not only when first revealed but at every later time through T.The passage contrasts this continual setting with one-shot privacy, for which adding Laplacian noise to an observation can suffice.Source: §4 · p. 15
  • The section introduces an algorithm for creating partial sums.The supplied algorithm heading identifies partial sums as a component of the privacy approach.Source: §4 · p. 16

6 end

The privacy-preserving algorithm represents cumulative observations with a logarithmic number of partial sums and adds Laplacian noise to nonempty sums. It then uses noisy observations within Gossip_UCB’s local selection and gossiping procedure.

4.1 Algorithm

  • A cumulative observation can be represented using no more than ceil(log t) partial sums, avoiding the naive scheme’s noise growing linearly with T.The passage applies the partial-sums construction to the local observation and notes that the resulting approach also preserves privacy for gossiping and selection information by data processing.Source: §4.1 · p. 16
  • Each nonempty partial sum receives independent Laplacian noise, with the per-sum privacy level set using ceil(log T).The passage specifies epsilon′ := epsilon / ceil(log T) to achieve a total epsilon-DP guarantee.Source: §4.1 · p. 16
  • Agents initialize by pulling each arm once and maintain local consistency requirements when selecting arms.The algorithm forms an eligible-arm set using the local count and the locally estimated maximum count, then selects the arm with the highest updated belief.Source: §4.1 · p. 17
  • Agents use noisy observations and exchange their local estimates with neighbors during the gossiping step.The procedure modifies observation handling to obtain differentially private observations before updating and sharing estimates.Source: §4.1 · pp. 16–17

24 end

Fed_UCB extends the Gossip_UCB regret analysis to privacy-preserving noisy estimates. Its regret bound grows as O(log^2.5 T) in the time horizon, and Gossip_UCB is recovered when ε is infinite.

24 end

  • Gossip_UCB is the ε=infinity special case of Fed_UCB, and the cited algorithm's line 16 has O(log t) time complexity.Source: §24 · p. 17

4.2 Concentration Bound for Local Privacy-Preserving Noisy Estimates

  • For n_i,k(t) ≥ max{L, (3M + 1)N}, Lemma 6 gives a high-probability concentration bound for the noisy estimate.The variance proxy combines observation variance with Laplacian-noise variance.Source: §4.2 · p. 17

4.3 Regret Upper Bound for Fed_UCB

  • Fed_UCB's regret bound has O(log^2.5 T) dependence on T, matching the reported centralized single-agent order.The paper notes that the bound can differ with the privacy algorithm and delayed transmission of heterogeneous rewards.Source: §4.3 · pp. 18–19

5 EXPERIMENTS

Experiments evaluate Fed_UCB on synthetic and hospital data, including how privacy levels relate to regret. The synthetic results follow the predicted inverse-ε regret ratio, while the hospital experiment tests feasibility using a constructed five-arm setting.

5 EXPERIMENTS

  • Experiments average regret over 100 trials and N agents, with ε set to 1, 2, or 5; ε=infinity adds no privacy step.The setup includes synthetic and real datasets, and reports the range of realized regret across trials.Source: §5 · p. 19

5.1 Synthetic datasets

  • For synthetic data with N=3, M=5, and λ2=0.5, regret for ε∈{1, 2, 5} is approximately 1:1/2:1/5 (=1/ε1:1/ε2:1/ε3), consistent with the Fed_UCB regret bound.Source: §5.1 · p. 20, Figure 2 · p. 20

5.2 Real-world datasets

  • The hospital experiment maps 23 medication types to five arms, divides samples among three hospitals, and uses readmission-based rewards to test feasibility.No record and readmission within 30 days map to reward 0; readmission after 30 days maps to reward 1.Source: §5.2 · pp. 20–21

6 CONCLUSION

The conclusion presents Gossip_UCB and its differentially private variant Fed_UCB, with regret bounds depending on agents, arms, horizon, and graph connectivity. The appendix states the sub-Gaussian assumptions used in the analyses and defines variance proxy terminology.

6 CONCLUSION

  • Gossip_UCB and Fed_UCB are proposed for gossiping bandit learning, and experiments on synthetic and real data verify the approach's feasibility.The regret orders depend on agent count, arm count, time horizon, and graph connectivity; future work includes contextual bandits and continuous arms.Source: §6 · p. 21

Appendix; A PRELIMINARIES OF SUB-GAUSSIAN RANDOM VARIABLES

A PRELIMINARIES OF SUB-GAUSSIAN RANDOM VARIABLES

B.1 Proof for Lemma 4

The proof represents each gossiped estimate as a linear combination of observations, then bounds its concentration using gossip-update properties. The following lemma proof takes expectations of the update recurrence.

B.1 Proof for Lemma 4

  • Lemma 4 gives a concentration bound for |ϑ_i,k(t)−E(ϑ_i,k(t))| once each agent's arm count reaches max{L, (3M+1)N}.Source: §B.1 · p. 24
  • Each estimate ϑ_i,k(t) is expressed as a linear combination of observations, with coefficients derived from successive gossip-update matrices.Delayed updates can make some observation coefficients zero.Source: §B.1 · p. 25

B.2 Proof for Lemma 5

  • The Lemma 5 proof takes expectations of both sides of update (13) and uses the indicator vector 1_i, whose ith entry is 1.Source: §B.2 · p. 27

B.3 Proof for Lemma 6

Lemma 6 bounds the concentration of the gossiped estimate around the mean when every agent has enough samples. Its proof accounts for the Laplace noise added to local empirical means and carried through gossiping.

B.3 Proof for Lemma 6

  • When n_i,k(t) ≥ max{L, (3M + 1)N}, the lemma bounds the probability that the estimate deviates from μ_k by at least its confidence radius.The stated condition applies to every agent; the lemma gives the concentration bound with probability at least 1 − p1.Source: §B.3 · p. 28
  • The proof tracks cumulative noise in the empirical means through gossiping to bound its effect on the estimate.It invokes a bound for sums of Laplace noise and relates the accumulated noise to the gossiped estimate.Source: §B.3 · p. 28
  • Gossiping forms linear combinations of independently added Laplace noise, which remains independent of the agents’ observations.The proof uses this independence when analyzing the noise in the gossiped estimate.Source: §B.3 · pp. 28–29

Related papers

Loading 2010.12763v2…