Reward Teaching for Federated Multi-armed Bandits

Chengshuai Shi, Wei Xiong, Cong Shen, Jing Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Most existing federated multi-armed bandits (FMAB) designs are based on the presumption that clients will implement the new design to collaborate with the server. In reality, however, it may not be possible to modify the client protocols. Motivated by this limitation, 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 novel algorithm, called Teaching-After-Learning (TAL), is proposed, which encourages and discourages clients' explorations separately. General performance analyses of TAL on regret and cost are first established when the clients' strategies satisfy certain requirements. To particularize the results, clients with UCB or ?-greedy strategies are then considered, where novel technical approaches are developed to analyze their warm-start behaviors. The obtained guarantees concretely demonstrate that when facing these client strategies, TAL achieves logarithmic regrets while only incurring logarithmic adjustment costs, which is order-optimal w.r.t. a natural lower bound.

Original languageEnglish (US)
Title of host publication2023 IEEE International Symposium on Information Theory, ISIT 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1454-1459
Number of pages6
ISBN (Electronic)9781665475549
DOIs
StatePublished - 2023
Event2023 IEEE International Symposium on Information Theory, ISIT 2023 - Taipei, Taiwan, Province of China
Duration: Jun 25 2023Jun 30 2023

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2023-June
ISSN (Print)2157-8095

Conference

Conference2023 IEEE International Symposium on Information Theory, ISIT 2023
Country/TerritoryTaiwan, Province of China
CityTaipei
Period6/25/236/30/23

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Cite this