A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players
A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players
复制标题
当玩家之间的手臂意味着不同时，多人强盗的实用算法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Vianney Perchet
中科院分区：
文献类型：
--
作者：
Etienne Boursier;E. Kaufmann;Abbas Mehrabian;Vianney Perchet
我们研究了一个多人随机多臂强盗问题，其中玩家不能交流，如果两个或两个以上的玩家拉同一只手臂，发生碰撞，参与的玩家获得零奖励。我们认为具有挑战性的异构设置，其中不同的武器可能有不同的手段，为不同的球员，并提出了一个新的和有效的算法，结合了利用强制碰撞的想法，隐式通信和执行匹配消除。我们提出了我们的算法的有限时间分析，给出了这个问题的第一个次线性极大极小遗憾界，并证明了如果玩家的最优分配是唯一的，我们的算法达到了最优的$O（ln（T））$遗憾，解决了NeurIPS 2018提出的一个悬而未决的问题。
We study a multiplayer stochastic multi-armed bandit problem in which players cannot communicate, and if two or more players pull the same arm, a collision occurs and the involved players receive zero reward. We consider the challenging heterogeneous setting, in which different arms may have different means for different players, and propose a new and efficient algorithm that combines the idea of leveraging forced collisions for implicit communication and that of performing matching eliminations. We present a finite-time analysis of our algorithm, giving the first sublinear minimax regret bound for this problem, and prove that if the optimal assignment of players to arms is unique, our algorithm attains the optimal $O(ln(T))$ regret, solving an open question raised at NeurIPS 2018.
针对不协调的频谱访问提供与用户相关的奖励的多用户 MAB
DOI：
10.1109/ieeeconf44664.2019.9048964
发表时间：
2019
期刊：
and Computers
影响因子：
--
作者：
Magesh, Akshayaa;Veeravalli, Venugopal V.
通讯作者：
Veeravalli, Venugopal V.