SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits
Motivated by cognitive radio networks, we consider the stochastic multiplayer multi-armed bandit problem, where several players pull arms simultaneously and collisions occur if one of them is pulled by several players at the same stage. We present a decentralized algorithm that achieves the same performance as a centralized one, contradicting the existing lower bounds for that problem. This is possible by "hacking" the standard model by constructing a communication protocol between players that deliberately enforces collisions, allowing them to share their information at a negligible cost. This motivates the introduction of a more appropriate dynamic setting without sensing, where similar communication protocols are no longer possible. However, we show that the logarithmic growth of the regret is still achievable for this model with a new algorithm.
Code (2)
Tasks
Multi-Armed BanditsSimilar Papers 제목 키워드 기반
An Optimal Algorithm for Multiplayer Multi-Armed Bandits
The paper addresses the Multiplayer Multi-Armed Bandit (MMAB) problem, where $M$ decision makers or players collaborate to maximize their cumulative reward. When several players select the same arm, a collision occurs an…
Multi-Armed BanditsA Chirp Spread Spectrum Modulation Scheme for Robust Power Line Communication
This paper proposes the use of a LoRa like chirp spread spectrum physical layer as the basis for a new Power Line Communication modulation scheme suited for low-bandwidth communication. It is shown that robust communicat…
Distributed Algorithms for Multi-Agent Multi-Armed Bandits with Collision
We study the stochastic Multiplayer Multi-Armed Bandit (MMAB) problem, where multiple players select arms to maximize their cumulative rewards. Collisions occur when two or more players select the same arm, resulting in …
Multi-Armed BanditsMulti-view data capture for dynamic object reconstruction using handheld augmented reality mobiles
We propose a system to capture nearly-synchronous frame streams from multiple and moving handheld mobiles that is suitable for dynamic object 3D reconstruction. Each mobile executes Simultaneous Localisation and Mapping …
3D ReconstructionObject ReconstructionQuadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
There has been significant recent progress in algorithms for approximation of Nash equilibrium in large two-player zero-sum imperfect-information games and exact computation of Nash equilibrium in multiplayer strategic-f…