Federated Linear Contextual Bandits
This work addresses the challenge of efficient and private collaborative learning in multi-client bandit settings, representing an incremental advancement in federated learning methods.
The paper tackles the problem of federated linear contextual bandits with heterogeneous clients by proposing Fed-PE, a collaborative algorithm that achieves near-optimal regrets with logarithmic communication costs, as demonstrated in experiments on synthetic and real-world datasets.
This paper presents a novel federated linear contextual bandits model, where individual clients face different $K$-armed stochastic bandits coupled through common global parameters. By leveraging the geometric structure of the linear rewards, a collaborative algorithm called Fed-PE is proposed to cope with the heterogeneity across clients without exchanging local feature vectors or raw data. Fed-PE relies on a novel multi-client G-optimal design, and achieves near-optimal regrets for both disjoint and shared parameter cases with logarithmic communication costs. In addition, a new concept called collinearly-dependent policies is introduced, based on which a tight minimax regret lower bound for the disjoint parameter case is derived. Experiments demonstrate the effectiveness of the proposed algorithms on both synthetic and real-world datasets.