Cooperative Stochastic Bandits with Asynchronous Agents and Constrained Feedback
Cooperative Stochastic Bandits with Asynchronous Agents and Constrained Feedback
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Lin Yang;Y. Chen;Stephen Pasteris;M. Hajiesmaili;John C.S. Lui;D. Towsley
中科院分区：
文献类型：
--
作者：
Lin Yang;Y. Chen;Stephen Pasteris;M. Hajiesmaili;John C.S. Lui;D. Towsley
受分布式系统中大规模学习场景的启发，本文研究了M个智能体合作解决同一个K臂随机强盗问题的场景。代理人对本地武器子集的访问是有限的，并且在决策回合之间具有不同的间隙。我们的目标是找到全局最优的手臂，智能体能够拉动任何手臂，但是，他们只能在选定的手臂是本地时观察奖励。对于智能体来说，挑战是在拉动具有可观察反馈的本地手臂或拉动没有反馈的外部手臂并依赖于以不同速率发生的其他观察之间进行权衡。我们提出了AAE-LCB，一个两阶段的算法，优先拉动本地武器后，积极的手臂消除政策，并切换到其他武器，只有当所有的本地武器占主导地位的一些外部武器。我们分析了AAE-LCB的遗憾，并表明它匹配的遗憾下限到一个小的因素。
Motivated by the scenario of large-scale learning in distributed systems, this paper studies a scenario where M agents cooperate together to solve the same instance of a K -armed stochastic bandit problem. The agents have limited access to a local subset of arms and are asynchronous with different gaps between decision-making rounds. The goal is to find the global optimal arm and agents are able to pull any arm, however, they can only observe the reward when the selected arm is local. The challenge is a tradeoff for agents between pulling a local arm with observable feedback, or pulling external arms without feedback and relying on others’ observations that occur at different rates. We propose AAE-LCB , a two-stage algorithm that prioritizes pulling local arms following an active arm elimination policy, and switches to other arms only if all local arms are dominated by some external arms. We analyze the regret of AAE-LCB and show it matches the regret lower bound up to a small factor.