Federated Multi-Armed Bandit Via Uncoordinated Exploration
Federated Multi-Armed Bandit Via Uncoordinated Exploration
复制标题
通过不协调的探索联合多臂强盗
DOI：
10.1109/icassp43922.2022.9747833
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tajer, Ali
中科院分区：
文献类型：
--
作者：
Yan, Zirui;Xiao, Quan;Chen, Tianyi;Tajer, Ali
大量的多智能体决策问题可以抽象为联邦多臂强盗（FMAB）问题。FMAB问题的一个关键挑战是，从多臂强盗方面继承的探索-利用二分法与联邦学习中的数据异构性相结合。这使得对不同代理人的探索和利用内在地纠缠在一起。针对FMAB问题中探测困难的问题，提出了一种新的联邦置信上界（UCB）算法，该算法要求Agent进行非协调探测（UE）决策.该算法（称为FedUCB-UE）与现有FMAB算法的主要区别在于，它允许代理探索非最佳手臂并在没有协调的情况下做出个性化的手臂选择决策。虽然这种不协调的探索使遗憾分析变得不平凡，但它带来了探索多样性的理论和经验优势。在一定的假设条件下，本文证明了FedUCB-UE具有极大界.此外，在合成数据集上进行的实验表明，FedUCB-UE优于最先进的算法。
A wide range of multi-agent decision-making problems can be abstracted as a federated multi-armed bandit (FMAB) problem. A key challenge of the FMAB problem is that the exploration-exploitation dichotomy inherited from the multi-armed bandit aspect is compounded with data heterogeneity in federated learning. This renders the exploration and exploitation of different agents inherently entangled. This paper focuses on overcoming the difficulty of exploration in FMAB problems, and it proposes a novel federated upper confidence bound (UCB) algorithm that requires uncoordinated exploration (UE) decisions by the agents. The major distinction of this algorithm, referred to as FedUCB-UE, with the existing FMAB algorithms is that it allows the agents to explore the non-optimal arms and make personalized arm-selection decisions without coordination. While such uncoordinated exploration makes the regret analysis non-trivial, it comes with both the theoretical and empirical benefit of diversity in explorations. Under certain mild assumptions, this paper establishes that FedUCB-UE has aregret bound. Furthermore, experiments performed on synthetic datasets show that FedUCB-UE outperforms the state-of-the-art algorithms.