mlsanityData to 7 Oct 2026

Federated Linear Bandits with Finite Adversarial Actions

arXiv 2311.00973 ↗First posted 2 Nov 2023cs.LG cs.IT math.ITcited by 3

Not on the map. Why?

Abstract (arXiv)

We study a federated linear bandits model, where M clients communicate with a central server to solve a linear contextual bandits problem with finite adversarial action sets that may be different across clients. To address the unique challenges of adversarial finite action sets, we propose the FedSupLinUCB algorithm, which extends the principles of SupLinUCB and OFUL algorithms in linear contextual bandits. We prove that FedSupLinUCB achieves a total regret of tildeO(√d T), where T is the total number of arm pulls from all clients, and d is the ambient dimension of the linear model. This matches the minimax lower bound and thus is order-optimal (up to polylog terms). We study both asynchronous and synchronous cases and show that the communication cost can be controlled as O(d M2 log(d)log(T)) and O(√d3 M3 log(d)), respectively. The FedSupLinUCB design is further extended to two scenarios: (1) variance-adaptive, where a total regret of tildeO (√d sum nolimitst=1T σt2) can be achieved with σt2 being the noise variance of round t; and (2) adversarial corruption, where a total regret of tildeO(√dT + d Cp) can be achieved with Cp being the total corruption budget. Experiment results corroborate the theoretical analysis and demonstrate the effectiveness of FedSupLinUCB on both synthetic and real-world datasets.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 16 of its 24 references that are in the map. First posted on arXiv 2 Nov 2023.

Builds on

16 of 24 references.

References · 16

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  3. 2020Differentially-Private Federated Linear Banditscited by 83
  4. 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
  5. 2021Federated Multi-armed Bandits with Personalizationcited by 62
  6. 2021Federated Linear Contextual Banditscited by 61
  7. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
  8. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  9. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  10. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  11. 2013A Gang of Banditscited by 49
  12. 2021Asynchronous Upper Confidence Bound Algorithms for Federated Linear Banditscited by 31
4 more
  1. 2022A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Banditscited by 28
  2. 2020Federated Recommendation System via Differential Privacycited by 26
  3. 2022Communication Efficient Federated Learning for Generalized Linear Banditscited by 13
  4. 2022Distributed Linear Bandits under Communication Constraintscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 0; 2025: 1; 2026: 1.

3 papers.

  1. 2025Federated Linear Dueling Banditscited by 2
  2. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1
  3. 2026Batched Stochastic Linear Bandits with 1-Bit Communication Constraintscited by 1