Reward Teaching for Federated Multiarmed Bandits
Reward Teaching for Federated Multiarmed Bandits
复制标题
DOI：
10.1109/tsp.2023.3333658
复制
发表时间：
2023
影响因子：
5.4
通讯作者：
Chengshuai Shi;Wei Xiong;Cong Shen;Jing Yang
中科院分区：
文献类型：
--
作者：
Chengshuai Shi;Wei Xiong;Cong Shen;Jing Yang
大多数现有的联邦多武装匪徒（FMAB）的设计是基于这样的假设，即客户端将实现指定的设计与服务器合作。然而，在现实中，修改客户端的现有协议可能是不可能的。为了解决这一挑战，这项工作的重点是客户端谁总是最大化他们的个人累积奖励，并介绍了一个新的想法“奖励教学”，其中服务器引导客户端走向全局最优通过隐式的本地奖励调整。在此框架下，服务器端面临着两个紧密耦合的任务：强盗学习和目标教学，这两个任务的结合是非常重要和具有挑战性的。一个分阶段的方法，称为教学后学习（TAL），首先是为了鼓励和劝阻客户的探索分开。当客户的策略满足一定的温和要求时，建立了TAL的一般性能分析。通过分析Bandit算法的热启动行为，得到了客户端运行UCB或$\boldsymbol{\varepad}$-greedy策略时TAL的具体保证.这些结果表明，TAL实现对数遗憾，而只产生对数调整成本，这是订单最优的w.r.t.一个自然的下限。作为进一步的扩展，边教边学（TWL）算法的思想，逐步消除臂打破非自适应相位分离TAL。严格的分析表明，当面对使用UCB 1的客户时，由于其自适应设计，TWL在次优差距的依赖性方面优于TAL。实验结果证明了该算法的有效性和通用性。
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 $\boldsymbol{\varepsilon}$-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.