We study the problem of information sharing and cooperation in Multi-Player Multi-Armed bandits. We propose the first algorithm that achieves logarithmic regret for this problem. Our results are based on two innovations. First, we show that a simple modification to a successive elimination strategy can be used to allow the players to estimate their suboptimality gaps, up to constant factors, in the absence of collisions. Second, we leverage the first result to design a communication protocol that successfully uses the small reward of collisions to coordinate among players, while preserving meaningful instance-dependent logarithmic regret guarantees.


翻译:我们研究了多层多武装匪徒的信息共享与合作问题,我们提出了第一个实现对数遗憾的算法。我们的结果基于两个创新。首先,我们表明,对连续消除战略的简单修改可以用来让玩家在没有碰撞的情况下估计其不最优化差距,直至经常因素。第二,我们利用第一个结果设计一个通信协议,成功地利用小型碰撞奖励来协调玩家之间的协调,同时保留有意义的依赖实例的对数遗憾保证。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【MIT】反偏差对比学习,Debiased Contrastive Learning
专知会员服务
90+阅读 · 2020年7月4日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
Arxiv
5+阅读 · 2020年6月16日
Multi-task Deep Reinforcement Learning with PopArt
Arxiv
4+阅读 · 2018年9月12日
Arxiv
6+阅读 · 2018年4月24日
VIP会员
相关资讯
Top
微信扫码咨询专知VIP会员