# Reward Teaching for Federated Multi-armed Bandits

arXiv: https://arxiv.org/abs/2305.02441 · HTML: https://mlsanity.com/paper/2305.02441/

## 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 (most cited first, 30 of 36)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data](https://mlsanity.com/paper/2005.11418/) (2020)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [Data Poisoning Attacks on Stochastic Bandits](https://mlsanity.com/paper/1905.06494/) (2019)
- [Bayesian Exploration: Incentivizing Exploration in Bayesian Games](https://mlsanity.com/paper/1602.07570/) (2016)
- [Adversarial Attacks on Linear Contextual Bandits](https://mlsanity.com/paper/2002.03839/) (2020)
- [Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits](https://mlsanity.com/paper/2110.01463/) (2021)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [Federated Recommendation System via Differential Privacy](https://mlsanity.com/paper/2005.06670/) (2020)
- [Data Poisoning Attacks in Contextual Bandits](https://mlsanity.com/paper/1808.05760/) (2018)
- [Exploiting Heterogeneity in Robust Federated Best-Arm Identification](https://mlsanity.com/paper/2109.05700/) (2021)
- [The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation](https://mlsanity.com/paper/1906.01528/) (2019)
- [Multi-armed Bandits with Compensation](https://mlsanity.com/paper/1811.01715/) (2018)
- [Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack](https://mlsanity.com/paper/2002.07214/) (2020)
- [Privacy-Preserving Communication-Efficient Federated Multi-Armed Bandits](https://mlsanity.com/paper/2111.01570/) (2021)
- [Almost Cost-Free Communication in Federated Best Arm Identification](https://mlsanity.com/paper/2208.09215/) (2022)
- [When Are Linear Stochastic Bandits Attackable?](https://mlsanity.com/paper/2110.09008/) (2021)
- [Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification](https://mlsanity.com/paper/2102.07711/) (2021)
- [Action-Manipulation Attacks Against Stochastic Bandits: Attacks and Defense](https://mlsanity.com/paper/2002.08000/) (2020)
- [Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions](https://mlsanity.com/paper/2106.13669/) (2021)
- [Federated Best Arm Identification with Heterogeneous Clients](https://mlsanity.com/paper/2210.07780/) (2022)
- [Incentivizing Exploration with Heterogeneous Value of Money](https://mlsanity.com/paper/1512.08427/) (2015)

## 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.