A Distributed Algorithm for Sequential Decision Making in Multi-Armed Bandit with Homogeneous Rewards*
A Distributed Algorithm for Sequential Decision Making in Multi-Armed Bandit with Homogeneous Rewards*
复制标题
具有同质奖励的多臂老虎机顺序决策的分布式算法*
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ji Liu
中科院分区：
文献类型：
--
作者：
Jingxuan Zhu;Romeil Sandhu;Ji Liu
研究了由N个代理组成的网络上的分布式多臂盗贼问题，每个代理只能与其邻居通信，其中邻居关系用一个连通图来描述。每个代理都会做出一系列决定，从M个候选者中选择一个手臂，但它只能获得每个动作的奖励的本地样本，这是一个随机变量。提出了一种用于多个智能体协作学习最优决策的分布式置信度上限(UCB)算法。证明了当所有代理共享每个ARM奖励的均匀分布时，当T较大时，该算法在O((1+2ρ2)2logT/N)的阶上保证了所有N个代理的对数遗憾，其中ρ2表示Metropolis矩阵的所有特征值的绝对值中的第二大值。给出了分布式算法比集中式(单代理)算法学习速度快的充分条件。仿真表明，当代理对每个ARM奖励具有不同的观测时，该算法也适用。
This paper studies a distributed multi-armed bandit problem over a network of N agents, each of which can communicate only with its neighbors, where neighbor relationships are described by a connected graph $\mathbb{G}$ . Each agent makes a sequence of decisions on selecting an arm from M candidates, yet it only has access to local samples of the reward for each action, which is a random variable. A distributed upper confidence bound (UCB) algorithm is proposed for the agents to cooperatively learn the best decision. It is shown that when all the agents share a homogeneous distribution of each arm reward, the algorithm achieves guaranteed logarithmic regret for all N agents at the order of O((1 + 2ρ2)2 logT/N) when T is large, where ρ2 denotes the second largest among the absolute values of all the eigenvalues of the Metropolis matrix of $\mathbb{G}$. A sufficient condition under which the proposed distributed algorithm learns faster than the centralized (single-agent) counterpart is provided. Simulations suggest that the algorithm also works for the case when the agents have heterogeneous observations of each arm reward.
多代理多武装强盗中的社会学习
DOI：
10.1145/3393691.3394217
发表时间：
2019
期刊：
Proceedings of the ACM on Measurement and Analysis of Computing Systems
影响因子：
--
作者：
Sankararaman, Abishek;Ganesh, Ayalvadi;Shakkottai, Sanjay
通讯作者：
Shakkottai, Sanjay