Federated Linear Contextual Bandits
Federated Linear Contextual Bandits
复制标题
DOI：
--
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Ruiquan Huang;Weiqiang Wu;Jing Yang;Cong Shen
中科院分区：
文献类型：
--
作者：
Ruiquan Huang;Weiqiang Wu;Jing Yang;Cong Shen
本文提出了一种新的联邦线性上下文强盗模型，其中每个客户端面临不同的$K$-武装随机强盗耦合通过共同的全球参数。通过利用线性奖励的几何结构，提出了一种称为Fed-PE的协作算法，以科普客户端之间的异构性，而无需交换本地特征向量或原始数据。Fed-PE依赖于一种新的多客户端G-最优设计，并实现了接近最优的遗憾，不相交和共享参数的情况下，对数通信成本。此外，还引入了共线性相关策略的概念，并在此基础上得到了参数不相交时的极小极大后悔下界。实验证明了所提出的算法的有效性在合成和真实世界的数据集。
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.