Game of Thrones: Fully Distributed Learning for Multi-Player Bandits

Abstract

We consider an N-player multi-armed bandit game where each player chooses one out of M arms for T turns. Each player has different expected rewards for the arms, and the instantaneous rewards are independent and identically distributed or Markovian. When two or more players choose the same arm, they all receive zero reward. Performance is measured using the expected sum of regrets, compared with an optimal assignment of arms to players that maximizes the sum of expected rewards. We assume that each player only knows her actions and the reward she received each turn. Players cannot observe the actions of other players, and no communication between players is possible. We present a distributed algorithm and prove that it achieves an expected sum of regrets of near-O\left(\log T\right). This is the first algorithm to achieve a near order optimal regret in this fully distributed scenario. All other works have assumed that either all players have the same vector of expected rewards or that communication between players is possible.

arXiv commentPublished in Mathematics of Operations Research (submitted in September 2018). A preliminary version was published in NeurIPS 2018. This extended paper improves the regret bound to near-log(T), generalizes to unbounded and Markovian rewards, and has a much better convergence rate for the GoT Dynamics

References in corpus (7)

• Distributed Learning in Multi-Armed Bandit with Multiple Players
• Distributed Algorithms for Learning and Cognitive Medium Access with Logarithmic Regret
• Online Learning of Rested and Restless Bandits
• Distributed Clustering of Linear Bandits in Peer to Peer Networks
• Delay and Cooperation in Nonstochastic Bandits
• Fully distributed optimal channel assignment for open spectrum access
• Distributed Exploration in Multi-Armed Bandits

Cited by in corpus (7)

• A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players
• Beyond ${\log }^2(T)$ Regret for Decentralized Bandits in Matching Markets
• Medium Access Control protocol for Collaborative Spectrum Learning in Wireless Networks
• A survey on multi-player bandits
• Distributed learning in congested environments with partial information
• PPA-Game: Characterizing and Learning Competitive Dynamics Among Online Content Creators
• Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure