Federated Linear Contextual Bandits

Abstract

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.

References in corpus (17)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Distributed Learning in Multi-Armed Bandit with Multiple Players
• Further Optimal Regret Bounds for Thompson Sampling
• Batched bandit problems
• Finite-Time Analysis of Kernelised Contextual Bandits
• Distributed Clustering of Linear Bandits in Peer to Peer Networks
• Online Clustering of Bandits
• Decentralized Cooperative Stochastic Bandits
• Sequential Batch Learning in Finite-Action Linear Contextual Bandits
• Estimation Considerations in Contextual Bandits
• Federated Residual Learning
• Multi-Player Bandits Revisited
• The Externalities of Exploration and How Data Diversity Helps Exploitation
• Heuristic construction of exact experimental designs under multiple resource constraints
• Approximate D-optimal Experimental Design with Simultaneous Size and Cost Constraints