Social Learning in Multi Agent Multi Armed Bandits
Social Learning in Multi Agent Multi Armed Bandits
复制标题
多代理多武装强盗中的社会学习
DOI：
10.1145/3393691.3394217
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Shakkottai, Sanjay
中科院分区：
文献类型：
--
作者：
Sankararaman, Abishek;Ganesh, Ayalvadi;Shakkottai, Sanjay
由于大规模网络和分散系统对学习算法的新需求，我们引入了经典随机多臂强盗（MAB）问题的分布式版本。我们的设置由大量代理组成，这些代理协作并同时解决相同的K武装MAB实例，以最小化所有代理的平均累积后悔。代理之间只能通过基于对异步八卦的协议进行通信和协作，该协议交换有限数量的比特。在我们的模型中，智能体在每个点上决定(i)使用哪只手臂，（ii）是否使用，如果使用，（iii）与什么和谁通信。我们模型中的智能体是分散的，即它们的行为只依赖于它们过去观察到的历史。我们开发了一种新的算法，在这种算法中，智能体无论何时选择，都只与随机选择的另一个智能体进行臂id而不是样本的通信。我们的算法实现的每个代理的遗憾缩放是$\BigO łeft(\fracłceil\fracK n \rceil+łog(n) Δ łog(T) + \fracłog^3(n) łog łog(n) Δ^2 \right) $。此外，我们算法中的任何智能体（与统一且独立选择的智能体）在T的时间间隔内总共只通信Θ（łog(T)）$次。我们将我们的结果与两个基准进行比较-一个是智能体之间没有通信，另一个对应于完整的交互，其中智能体可以访问所有智能体的整个武器历史和获得的奖励。我们在理论上和经验上都表明，与代理不协作并且每个代理都在玩标准MAB问题（其中遗憾将在K中线性扩展）的情况相比，我们的算法在每个代理的遗憾方面都经历了显着减少，并且与需要代理进行T次通信尝试的完整交互设置相比，在通信复杂性方面。因此，我们的结果表明，即使是不同代理之间最小程度的合作，也能显著减少每个代理的后悔。
Motivated by emerging need of learning algorithms for large scale networked and decentralized systems, we introduce a distributed version of the classical stochastic Multi-Arm Bandit (MAB) problem. Our setting consists of a large number of agents n that collaboratively and simultaneously solve the same instance of K armed MAB to minimize the average cumulative regret over all agents. The agents can communicate and collaborate among each other only through a pairwise asynchronous gossip based protocol that exchange a limited number of bits. In our model, agents at each point decide on (i) which arm to play, (ii) whether to, and if so (iii) what and whom to communicate with. Agents in our model are decentralized, namely their actions only depend on their observed history in the past. We develop a novel algorithm in which agents, whenever they choose, communicate only arm-ids and not samples, with another agent chosen uniformly and independently at random. The per-agent regret scaling achieved by our algorithm is $\BigO łeft( \fracłceil\fracK n \rceil+łog(n) Δ łog(T) + \fracłog^3(n) łog łog(n) Δ^2 \right) $. Furthermore, any agent in our algorithm communicates (arm-ids to an uniformly and independently chosen agent) only a total of Θ(łog(T))$ times over a time interval of T. We compare our results to two benchmarks - one where there is no communication among agents and one corresponding to complete interaction, where an agent has access to the entire system history of arms played and rewards obtained of all agents. We show both theoretically and empirically, that our algorithm experiences a significant reduction both in per-agent regret when compared to the case when agents do not collaborate and each agent is playing the standard MAB problem (where regret would scale linearly in K), and in communication complexity when compared to the full interaction setting which requires T communication attempts by an agent over T arm pulls. Our result thus demonstrates that even a minimal level of collaboration among the different agents enables a significant reduction in per-agent regret.
登录
查看更多内容
多人强盗：抢椅子的方法
DOI：
--
发表时间：
2016
期刊：
International Conference on Machine Learning
影响因子：
--
作者：
Jonathan Rosenski;Ohad Shamir;Liran Szlak
通讯作者：
Liran Szlak
分布式多人强盗 - 权力的游戏方法
DOI：
--
发表时间：
2018
期刊：
Neural Information Processing Systems
影响因子：
--
作者：
Ilai Bistritz;Amir Leshem
通讯作者：
Amir Leshem
如何管理在线市场中的信息共享——一项探索性研究
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
E. Boon;L. Pitt;Esmail Salehi
通讯作者：
Esmail Salehi
去中心化合作随机多臂老虎机
DOI：
--
发表时间：
2018
期刊：
arXiv.org
影响因子：
--
作者：
David Martínez;Varun Kanade;Patrick Rebeschini
通讯作者：
Patrick Rebeschini
收集交互机器人与虚拟信息素的行为
DOI：
--
发表时间：
2004
期刊：
Proc. 7^<th> Int. Symp. on Distributed Autonomous Robotic Systems
影响因子：
--
作者：
栖関浩平;菅原研;水口毅;小菅一弘;K.Sugawara;K.Sugawara
通讯作者：
K.Sugawara