Decentralized Cooperative Stochastic Multi-armed Bandits
Decentralized Cooperative Stochastic Multi-armed Bandits
复制标题
去中心化合作随机多臂老虎机
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Patrick Rebeschini
中科院分区：
文献类型：
--
作者：
David Martínez;Varun Kanade;Patrick Rebeschini
研究了$N$个智能体网络上具有$K$个手臂的分散合作随机多臂强盗问题。在我们的模型中，每个手臂的奖励分配是独立的代理。每个代理迭代地选择一只手臂来玩，然后与她的邻居通信。目标是最小化总网络遗憾。我们设计了一个完全分散的算法，使用一个运行的共识程序来计算，有一些延迟，准确估计的平均奖励获得的所有代理为每个手臂，然后使用一个置信上限算法，占延迟和误差的估计。我们分析了算法，直到一个常数，我们的遗憾界是更好的所有网络比其他算法设计来解决同样的问题。对于某些图表，我们的遗憾界限明显更好。
We study a decentralized cooperative stochastic multi-armed bandit problem with $K$ arms on a network of $N$ agents. In our model, the reward distribution of each arm is agent-independent. Each agent chooses iteratively one arm to play and then communicates to her neighbors. The aim is to minimize the total network regret. We design a fully decentralized algorithm that uses a running consensus procedure to compute, with some delay, accurate estimations of the average of rewards obtained by all the agents for each arm, and then uses an upper confidence bound algorithm that accounts for the delay and error of the estimations. We analyze the algorithm and up to a constant our regret bounds are better for all networks than other algorithms designed to solve the same problem. For some graphs, our regret bounds are significantly better.