mlsanityData to 14 Oct 2026

Reward Teaching for Federated Multi-armed Bandits

arXiv 2305.02441 ↗First posted 3 May 2023stat.ML cs.IT cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Most of the existing federated multi-armed bandits (FMAB) designs are based on the presumption that clients will implement the specified design to collaborate with the server. In reality, however, it may not be possible to modify the clients' existing protocols. To address this challenge, this work focuses on clients who always maximize their individual cumulative rewards, and introduces a novel idea of ``reward teaching'', where the server guides the clients towards global optimality through implicit local reward adjustments. Under this framework, the server faces two tightly coupled tasks of bandit learning and target teaching, whose combination is non-trivial and challenging. A phased approach, called Teaching-After-Learning (TAL), is first designed to encourage and discourage clients' explorations separately. General performance analyses of TAL are established when the clients' strategies satisfy certain mild requirements. With novel technical approaches developed to analyze the warm-start behaviors of bandit algorithms, particularized guarantees of TAL with clients running UCB or epsilon-greedy strategies are then obtained. These results demonstrate that TAL achieves logarithmic regrets while only incurring logarithmic adjustment costs, which is order-optimal w.r.t. a natural lower bound. As a further extension, the Teaching-While-Learning (TWL) algorithm is developed with the idea of successive arm elimination to break the non-adaptive phase separation in TAL. Rigorous analyses demonstrate that when facing clients with UCB1, TWL outperforms TAL in terms of the dependencies on sub-optimality gaps thanks to its adaptive design. Experimental results demonstrate the effectiveness and generality of the proposed algorithms.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 36 of its 69 references that are in the map. First posted on arXiv 3 May 2023.

Builds on

36 of 69 references.

References · 36

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2020FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Datacited by 144
  3. 2018Stochastic bandits robust to adversarial corruptionscited by 119
  4. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 92
  5. 2020Differentially-Private Federated Linear Banditscited by 83
  6. 2021Federated Multi-armed Bandits with Personalizationcited by 62
  7. 2021Federated Linear Contextual Banditscited by 61
  8. 2021Federated Multi-Armed Banditscited by 59
  9. 2018Adversarial Attacks on Stochastic Banditscited by 57
  10. 2020Federated Bandit: A Gossiping Approachcited by 55
  11. 2015Bayesian Incentive-Compatible Bandit Explorationcited by 53
  12. 2019Data Poisoning Attacks on Stochastic Banditscited by 53
24 more
  1. 2016Bayesian Exploration: Incentivizing Exploration in Bayesian Gamescited by 37
  2. 2020Adversarial Attacks on Linear Contextual Banditscited by 34
  3. 2021Asynchronous Upper Confidence Bound Algorithms for Federated Linear Banditscited by 31
  4. 2021A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithmscited by 30
  5. 2020Federated Recommendation System via Differential Privacycited by 26
  6. 2018Data Poisoning Attacks in Contextual Banditscited by 23
  7. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  8. 2019The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulationcited by 15
  9. 2018Multi-armed Bandits with Compensationcited by 13
  10. 2020Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attackcited by 13
  11. 2021Privacy-Preserving Communication-Efficient Federated Multi-Armed Banditscited by 11
  12. 2022Almost Cost-Free Communication in Federated Best Arm Identificationcited by 11
  13. 2021When Are Linear Stochastic Bandits Attackable?cited by 10
  14. 2021Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verificationcited by 9
  15. 2020Action-Manipulation Attacks Against Stochastic Bandits: Attacks and Defensecited by 8
  16. 2021Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributionscited by 8
  17. 2022Federated Best Arm Identification with Heterogeneous Clientscited by 8
  18. 2015Incentivizing Exploration with Heterogeneous Value of Moneycited by 6
  19. 2022Federated Multi-Armed Bandits Under Byzantine Attackscited by 6
  20. 2022Parallel Best Arm Identification in Heterogeneous Environmentscited by 6
  21. 2013Distributed Online Learning via Cooperative Contextual Banditscited by 5
  22. 2020On No-Sensing Adversarial Multi-player Multi-armed Bandits with Collision Communicationscited by 5
  23. 2021Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptionscited by 5
  24. 2021(Almost) Free Incentivized Exploration from Decentralized Learning Agentscited by 3

Built on by

Not cited yet.