Concurrent bandits and cognitive radio networks
This addresses coordination challenges in cognitive radio networks for selfish users, but it is incremental as it builds on existing bandit methods.
The paper tackles the problem of multiple users selecting arms in a stochastic bandit without communication, motivated by cognitive radio networks, and shows that their algorithm achieves sub-linear regret with dramatic experimental improvement.
We consider the problem of multiple users targeting the arms of a single multi-armed stochastic bandit. The motivation for this problem comes from cognitive radio networks, where selfish users need to coexist without any side communication between them, implicit cooperation or common control. Even the number of users may be unknown and can vary as users join or leave the network. We propose an algorithm that combines an $ε$-greedy learning rule with a collision avoidance mechanism. We analyze its regret with respect to the system-wide optimum and show that sub-linear regret can be obtained in this setting. Experiments show dramatic improvement compared to other algorithms for this setting.