Reward Teaching for Federated Multi-armed Bandits

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.