PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Multi-Armed Bandits

Chengshuai Shi, Cong Shen

arXiv:2101.12204v2cs.LGcs.ITcs.MAmath.ITstat.ML

TL;DR

Federated multi-armed bandits extend federated learning to global bandit problems where clients have non-IID local models and communication is costly. The paper develops a general framework and studies approximate and exact models with algorithms addressing arm and client sampling. Theoretical analysis and synthetic and real-world experiments support logarithmic regret for the approximate model and order-optimal regret independent of client count for the exact model under suitable update periodicity.

  • Problem

    In federated bandits, the server must learn a global stochastic bandit from non-IID local models, but finite client samples may not represent the global model and the needed client count cannot be set in advance without the suboptimality gap.

    Source: §2 · p. 2, §3.1 · p. 4, §3.2 · p. 4

  • Method

    The paper develops an FMAB framework and proposes Fed2-UCB for the approximate model and Fed1-UCB for the exact-average model.

    Source: §1 · p. 2

  • Results

    The approximate-model Fed2-UCB achieves O(log(T)) regret considering communication cost, while exact-model Fed1-UCB achieves order-optimal regret independent of client count with suitable update periodicity.

    Source: §1 · p. 2, §7 · p. 7

  • Takeaways & Limitations

    Experiments on synthetic and real-world datasets corroborate the theoretical analysis and demonstrate the effectiveness and efficiency of the proposed algorithms.

    Source: §7 · p. 7

    The approximate model assumes IID local models drawn as random realizations of a fixed, hidden global ground truth.

    Source: §2.1 · p. 3

Abstract

from arXiv · show

Federated multi-armed bandits (FMAB) is a new bandit paradigm that parallels the federated learning (FL) framework in supervised learning. It is inspired by practical applications in cognitive radio and recommender systems, and enjoys features that are analogous to FL. This paper proposes a general framework of FMAB and then studies two specific federated bandit models. We first study the approximate model where the heterogeneous local models are random realizations of the global model from an unknown distribution. This model introduces a new uncertainty of client sampling, as the global model may not be reliably learned even if the finite local models are perfectly known. Furthermore, this uncertainty cannot be quantified a priori without knowledge of the suboptimality gap. We solve the approximate model by proposing Federated Double UCB (Fed2-UCB), which constructs a novel "double UCB" principle accounting for uncertainties from both arm and client sampling. We show that gradually admitting new clients is critical in achieving an O(log(T)) regret while explicitly considering the communication cost. The exact model, where the global bandit model is the exact average of heterogeneous local models, is then studied as a special case. We show that, somewhat surprisingly, the order-optimal regret can be achieved independent of the number of clients with a careful choice of the update periodicity. Experiments using both synthetic and real-world datasets corroborate the theoretical analysis and demonstrate the effectiveness and efficiency of the proposed algorithms.

1 Introduction

The paper extends federated learning principles from supervised learning to multi-armed bandits, motivated by cognitive-radio and recommender applications with non-IID local data. It develops a general FMAB framework and studies approximate and exact models with algorithms designed for regret and communication costs.

1 Introduction

  • Cognitive radio aggregates location-dependent channel observations because a fixed base station cannot learn coverage-wide availability alone.The global channel availability is the average over the coverage area.Source: §1 · p. 1
  • In recommender systems, privacy constraints keep user data on client devices or local servers, leaving the central server with aggregate information.Local item-popularity views may be biased and unrepresentative of the overall distribution.Source: §1 · p. 1
  • FMAB extends federated learning principles to global stochastic bandits learned from non-IID local models while accounting for communication and privacy.The motivating applications are cognitive radio and recommender systems.Source: §1 · pp. 1–2
  • The framework studies an approximate model with client-sampling uncertainty and an exact model whose global bandit is the average of local models.Fed2-UCB gradually samples clients in the approximate model; Fed1-UCB has order-optimal regret independent of client count with suitable update periodicity in the exact model.Source: §1 · p. 2

2 Problem Formulation

FMAB has clients observe their own non-IID local bandits while a server learns a global bandit that determines system rewards. The approximate model treats local models as random realizations of a hidden global model, so finite client samples may fail to represent it and the required client count cannot be set in advance without the suboptimality gap.

2 Problem Formulation

  • Each client interacts only with its own local MAB, and clients do not communicate directly.Clients share the same K local arms, but their arm means are generally non-IID.Source: §2 · p. 2
  • Clients cannot directly observe the global rewards, so the server learns the global-arm objective from client feedback.Clients play local arms, whose observations are independent within a client and whose models may differ across clients.Source: §2 · pp. 2–3
  • Each client communication incurs loss C, as the server aggregates local model updates and returns its updated global estimate.Communication costs are included in the performance measure.Source: §2 · p. 3

2.1 The Approximate Model

  • In the approximate model, local bandit models are IID random realizations of a fixed, hidden global ground truth.The model requires a relationship between local and global models so local observations help the server learn the global model.Source: §2.1 · p. 3
  • Even when local models are known perfectly, a finite set of clients may not represent the global model, creating client-sampling uncertainty.The required number of clients cannot be determined in advance without knowing the suboptimality gap.Source: §2.1 · p. 3
  • The cognitive-radio example models global channel availability across a coverage area, whereas a fixed base station can sample only finitely many users at discrete locations.Even perfect observations at those locations may not make the finite-sample estimate representative of coverage-wide availability.Source: §2.1 · p. 3
  • The regret definition uses one globally optimal arm and system-level rewards, and penalizes excessive client involvement through communication loss.It discourages admitting more clients than needed to reconstruct the global model.Source: §2.1 · p. 3

3 Fed2-UCB for Approximate FMAB

The approximate FMAB model must handle uncertainty from both arm sampling and client sampling, while local optimality can differ from global optimality. Fed2-UCB gradually admits clients and uses a double confidence bound to balance these uncertainties and communication cost.

3.1 Challenges and Main Ideas

  • Because local models are random realizations of the global model, even perfect knowledge of local arms may fail to identify the globally optimal arm.The globally optimal arm may also be suboptimal for an individual client's local model, making communication important for resolving the mismatch.Source: §3.1 · p. 4

3.2 Client Sampling

  • Client-sampling uncertainty falls as more clients are involved, but without knowing the suboptimality gap, the required client count cannot be guaranteed in advance.The paper states that M = Θ(log(T)) suffices to represent the global model while maintaining O(log(T)) regret.Source: §3.2 · p. 4

3.3 The Fed2-UCB Algorithm

  • Fed2-UCB gradually admits clients after communication rounds, using a double UCB principle to address arm- and client-sampling uncertainty while controlling communication cost.The server aggregates local estimates and eliminates arms; clients continue sampling the remaining active arms.Source: §3.3 · pp. 4–5

3.4 Regret Analysis

  • With f(p) = κ and g(p) = 2p, Fed2-UCB achieves O(log(T)) regret, with exploration approaching the single-player MAB lower bound and O(log(T)) communication loss.At least O(log(T)) clients are needed, making this communication loss inevitable under the stated setting.Source: §3.4 · p. 5

4 Special Case: Exact Model and Fed1-UCB

The exact FMAB model treats the global model as the exact average of a fixed set of heterogeneous local models, so client-sampling uncertainty is absent. Fed1-UCB uses arm-sampling confidence bounds, and its carefully chosen update periodicity yields asymptotically client-count-independent regret.

4.1 The Exact Model

  • The exact model fixes the client group, and the global arm mean is the exact average of the local arm means.The global model can therefore be reconstructed from the local models, leaving only arm-sampling uncertainty.Source: §4.1 · pp. 5–6

4.2 The Fed1-UCB Algorithm

  • Fed1-UCB removes client admission and uses a confidence bound that characterizes uncertainty from arm sampling alone.Its exploration and communication procedure otherwise follows Fed2-UCB.Source: §4.2 · p. 6

4.3 Theoretical Analysis

  • The Fed1-UCB regret bound depends on f(p), and the paper reports that regret is asymptotically independent of the number of clients.The stated logarithmic update periodicity also makes communication loss a non-dominating constant.Source: §4.3 · p. 6
  • With f(p) = ⌈κ log(T)⌉, Fed1-UCB's exploration loss approaches the single-player MAB lower bound, communication loss is a non-dominating constant, and regret is asymptotically independent of M.These properties are reported for the exact model and the stated update periodicity.Source: §4.3 · p. 6

5 Experiments

Experiments on synthetic cognitive-radio data and real-world MovieLens data assess Fed1-UCB and Fed2-UCB against a centralized baseline and across client-admission schedules. Fed2-UCB handles the approximate model with limited communication loss, and on MovieLens outperforms Fed1-UCB by admitting only the clients needed to capture the global model.

5 Experiments

  • The experiments use synthetic cognitive-radio data and MovieLens recommender data, with a hypothetical improved UCB run at the server as the baseline and communication cost C=1.The cognitive-radio simulations use synthetic data because suitable real-world datasets were unavailable.Source: §5 · p. 6

5.1 Synthetic Dataset for Cognitive Radio

  • With no communication loss, Fed1-UCB performs almost like the baseline; communicating raw data every time slot causes very large regret, while Fed1-UCB incurs only a small communication loss.Increasing clients from M=5 to M=10 leaves overall regret approximately the same while speeding convergence.Source: §5.1 · p. 6, Figure 3 · p. 7
  • Fed2-UCB finds the optimal global arm in the approximate model with limited communication loss and performs almost as well as Fed1-UCB on the more challenging model.With f(p)=50, it balances client-sampling and arm-sampling uncertainty better than f(p)=10 or f(p)=100.Source: §5.1 · pp. 6–7, Figure 4 · p. 7

5.2 Real-world Dataset for Recommender System

  • Fed2-UCB with f(p)=200 and g(p)=2p performs much better on MovieLens than Fed1-UCB, which either misses the global optimum with M=200 or incurs large regret with all clients.Fed2-UCB with f(p)=500 also outperforms Fed1-UCB.Source: §5.2 · p. 7

6 Related Works

The related work spans federated learning and multi-armed bandits, including distributed multiplayer bandits and prior federated-bandit approaches. The paper distinguishes FMAB by its non-IID local models and the role of communication in learning a global bandit.

6 Related Works

  • Federated learning research addresses communication efficiency, privacy, fairness, and system design, while multi-armed bandits have applications including cognitive radio, recommender systems, and clinical trials.The cited applications include medical treatment for federated learning.Source: §6 · p. 7
  • Unlike multiplayer MAB, FMAB clients observe only local signals that may not reveal true rewards or the optimal global arm, making communication more fundamental.The cited multiplayer work considers cooperative communication or competitive collision resolution.Source: §6 · p. 7
  • Prior federated-bandit studies address strictly IID local models, federated residual learning, gossip-based information sharing, or personalized mixed bandit games.The passage contrasts these focuses with the paper’s approach to non-IID local and global model relationships.Source: §6 · p. 7

7 Conclusion

The paper develops a general framework bridging federated learning and multi-armed bandits, studies approximate and exact FMAB models, and reports theoretical and experimental support for the proposed algorithms.

7 Conclusion

  • The approximate model introduces client-sampling uncertainty, and Fed2-UCB admits clients increasingly while balancing arm and client uncertainty with communication loss to achieve O(log(T)) regret.Source: §7 · p. 7
  • For the exact model, Fed1-UCB achieves order-optimal regret while allowing a tradeoff between convergence time and number of clients.Source: §7 · p. 7
  • Experiments on synthetic and real-world datasets corroborate the theoretical analysis and the effectiveness of the proposed algorithms.Source: §7 · p. 7

Ethics Statement

The discussion links FMAB to federated-learning principles, outlines Fed1-UCB’s client and server updates, and analyzes how client growth affects regret and communication loss. It also notes infrastructure requirements and synchronization risks.

Ethics Statement

  • FMAB may support locally collected sensitive data without central raw-data collection, but it requires reliable communication and sufficient client computation, which may be difficult in rural areas or on low-cost devices.The discussion identifies broken synchronization as a significant risk and a future research problem.Source: Ethics Statement · p. 8

A Similarities between FL and FMAB

B Fed1-UCB Algorithm Description

  • Fed1-UCB clients sample each active arm, send local sample means, and update their active-arm set; the server averages those means, eliminates arms, and sends the update to clients.Source: B Fed1-UCB Algorithm Description · p. 10

C Additional Discussions on the Regret Analysis

  • With Θ(log(T)) clients, any f(p) growing faster than O(1) precludes O(log(T)) regret, and constant communication loss is unattainable.Source: §C.1 · p. 10

C.1 Discussion for Theorem 2

  • Exponential client growth with g(p)=2^p or g(p)=⌈2^p log(T)⌉ can bring exploration loss toward the lower bound while keeping communication loss sublinear at O(log(T)).Source: §C.1 · p. 10

C.2 Discussion for Theorem 3

The discussion compares Fed2-UCB regret under choices of client-growth rate; the accompanying proof uses a union bound.

C.2 Discussion for Theorem 3

  • Exponential update periods give communication loss O(log(log(T))) for f(p) = 2^p and O(1) for f(p) = ⌈2^p log(T)⌉, with both scaling as log(1/∆).These update-period choices are discussed alongside the regret choices in Table 3.Source: §C.2 · p. 10, Table 3 · p. 11
  • With f(p) = κ, overall asymptotic regret is independent of M, while communication loss is O(log(T)).The discussion fixes f(p) = κ and considers choices of g(p).Source: §C.2 · p. 10

D.1 Proof of Theorem 1

  • The proof of Theorem 1 begins by applying a union bound.The supplied proof passages then proceed through arm-gap and concentration bounds.Source: §D.1 · p. 11

D.2 Proof of Theorem 2

The proof bounds estimation error and the pulls needed to eliminate suboptimal arms, then combines exploration and communication losses into an overall regret bound.

D.2 Proof of Theorem 2

  • The averaged local mean estimate is bounded against the exact global mean using confidence bounds that account for two types of uncertainty.The proof first establishes a probability guarantee for the estimation interval.Source: §D.2 · p. 12
  • On event B, each suboptimal arm is pulled at most p_k rounds before elimination or the horizon ends.The bound uses the smallest p_k satisfying the stated confidence-width condition.Source: §D.2 · pp. 12–13
  • The proof decomposes regret into exploration and communication losses, bounds both on event B, and combines that bound with the complementary-event bound.When B fails, the exploration and communication losses are bounded linearly in T.Source: Step 3: Overall Regret · p. 13

D.3 Proof of Theorem 3

The proof bounds estimation error, arm-elimination time, and total regret. The appendix also describes privacy-enhancing communication schemes and provides experimental and implementation details.

D.3 Proof of Theorem 3

  • On event A, each suboptimal arm is pulled for at most p_k phases by each client before elimination or the horizon ends.The proof then bounds exploration and communication losses to obtain an overall regret bound.Source: Step 2: Required Number of Pulls · pp. 14–15

E.1 Better Privacy Protection

  • Quantized sample means preserve the regret order with only a slightly larger constant factor, and can significantly reduce communication cost with massive client populations.The server adjusts the confidence bound to accommodate quantization error.Source: §E.1 · p. 15
  • Clients can add zero-mean Gaussian or Laplace noise to transmitted sample means; averaging lets arm eliminations remain successful with high probability.The noise is proposed to protect each client’s sensitive data.Source: §E.1 · p. 15

F Experiment Details and Additional Results

F.1 Code and Dataset

  • The simulation code and synthetic and preprocessed MovieLens datasets are publicly available in the stated repository.The original MovieLens dataset is also identified as publicly available from GroupLens.Source: §F.1 · p. 15

F.2 Additional Results

Additional experiments report that client sampling reduces estimation error and that Fed2-UCB’s performance depends on its client-growth schedule.

F.2 Additional Results

  • With σ_c = 0.1, P_e decreases exponentially with M for ∆ = 0.02 and ∆ = 0.01, and is smaller at ∆ = 0.02.The authors report this synthetic-data result as corroborating Theorem 1.Source: §F.2 · p. 16
  • Fed2-UCB with g(p) = 2^p achieves better regret across the tested bandit environments than with g(p) = ⌈log(T)⌉.The latter choice has stronger dependence on ∆, consistent with the theoretical analysis in Table 2.Source: §F.2 · p. 16

Related papers

Loading 2101.12204v2…