Meet Me at the Arm: The Cooperative Multi-Armed Bandits Problem with Shareable Arms
This addresses coordination challenges in multi-agent systems like wireless networks, representing a significant generalization beyond classical models.
The paper tackles the decentralized multi-player multi-armed bandits problem with unknown arm capacities and no-sensing feedback, proposing the A-CAPELLA algorithm that achieves logarithmic regret.
We study the decentralized multi-player multi-armed bandits (MMAB) problem under a no-sensing setting, where each player receives only their own reward and obtains no information about collisions. Each arm has an unknown capacity, and if the number of players pulling an arm exceeds its capacity, all players involved receive zero reward. This setting generalizes the classical unit-capacity model and introduces new challenges in coordination and capacity discovery under severe feedback limitations. We propose A-CAPELLA (Algorithm for Capacity-Aware Parallel Elimination for Learning and Allocation), a decentralized algorithm that achieves logarithmic regret in this generalized regime. Our main contribution is a collaborative hypothesis testing protocol that enables synchronized successive elimination and capacity estimation through carefully structured collision patterns. This represents a provably efficient learning result in decentralized no-sensing MMAB with unknown arm capacities.