Reward Teaching for Federated Multi-armed Bandits
Reward Teaching for Federated Multi-armed Bandits
复制标题
DOI：
10.1109/isit54713.2023.10206444
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Chengshuai Shi;Wei Xiong;Cong Shen;Jing Yang
中科院分区：
文献类型：
--
作者：
Chengshuai Shi;Wei Xiong;Cong Shen;Jing Yang
大多数现有的联邦多武装匪徒（FMAB）的设计是基于这样的假设，即客户端将实现新的设计与服务器合作。然而，实际上，可能无法修改客户端协议。出于这种限制，这项工作的重点是客户端谁总是最大化他们的个人累积奖励，并介绍了一种新的想法的奖励教学，服务器引导客户端走向全局最优通过隐式的本地奖励调整。在此框架下，服务器端面临着两个紧密耦合的任务：强盗学习和目标教学，这两个任务的结合是非常重要和具有挑战性的。提出了一种新的算法，称为教学后学习（TAL），它鼓励和不鼓励客户端的探索分开。在顾客策略满足一定要求的情况下，建立了TAL在后悔和成本方面的一般绩效分析。为了具体化结果，然后考虑具有UCB或ε-贪婪策略的客户端，其中开发了新的技术方法来分析其热启动行为。得到的保证具体表明，当面对这些客户端的策略，TAL实现对数遗憾，而只产生对数调整成本，这是订单最优的w.r.t.一个自然的下限。
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.