Decentralized Asynchronous Multi-player Bandits

In recent years, multi-player multi-armed bandits (MP-MAB) have been extensively studied due to their wide applications in cognitive radio networks and Internet of Things systems. Most existing works focus on synchronized settings, whereas real-world systems are often decentralized and asynchronous, with players entering and leaving arbitrarily and no shared global clock. This introduces two major challenges: avoiding collisions without time coordination, and estimating the number of active players in every step. In this paper, we propose an algorithm to address these challenges. During exploration, players uniformly explore the arms that are not currently exploited by others, which reduces the probability of collisions and solves the first challenge. Meanwhile, players occasionally pull the arms that are currently exploited by others, enabling them to detect other players’ departures and addressing the second challenge. We prove that our algorithm achieves a regret of O( √︁ 𝑇 log𝑇 + log𝑇/Δ2), where Δ is the minimum expected reward gap between any two arms. To the best of our knowledge, this isthefirstefficientalgorithmintheasynchronousanddecentralized environment.

Authors

• Jingqi Fan Northeastern University
• Canzhe Zhao Shanghai Jiao Tong University
• Shuai Li Shanghai Jiao Tong University
• Siwei Wang Microsoft Research Asia

Keywords

• Multi-armed Bandits
• Multi-agent Systems
• Asynchronous Coordination
• Decentralized Learning