Multi-arm Multi-player bandit for wireless Ad-Hoc Networks


Abstract:

Multi-player Multi-Armed Bandits (MAB) have been extensively studied in the literature, motivated by applications to Cognitive Radio systems. Driven by such applications as well, we motivate the introduction of several levels of feedback for multi-player MAB algorithms. Most existing work assume that sensing information is available to the algorithm. Under this assumption, we improve the state-of-the-art lower bound for the regret of any decentralized algorithms and introduce two algorithms, MCTopM-Static and MCTopM - Dynamic, that are shown to empirically outperform existing algorithms. Moreover, we provide strong theoretical guarantees for these algorithms, including a notion of asymptotic optimality in terms of the number of selections of bad arms. We then We took variant of the stochastic multi-armed bandit problem, where multiple players simultaneously choose from a set of arms and then resolved many drawbacks like collision, prior knowledge of users, quasi stationary reward distribution (change detection), etc.