Game of thrones: fully distributed learning for multiplayer bandits
From MaRDI portal
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-Oleft(log T
ight). 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.
Recommendations
Cites work
- Achieving Pareto Optimality Through Distributed Learning
- Asymptotically efficient adaptive allocation rules
- Chernoff-Hoeffding bounds for Markov chains: generalized and simplified
- Decentralized Learning for Multiplayer Multiarmed Bandits
- Distributed Learning in Multi-Armed Bandit With Multiple Players
- Fully Distributed Optimal Channel Assignment for Open Spectrum Access
- scientific article; zbMATH DE number 3947447 (Why is no real title available?)
- scientific article; zbMATH DE number 1239549 (Why is no real title available?)
- Learning efficient Nash equilibria in distributed systems
- Learning in a Changing World: Restless Multiarmed Bandit With Unknown Dynamics
- Learning to optimize via posterior sampling
- Markov decision processes with arbitrary reward processes
- MNL-bandit: a dynamic learning approach to assortment selection
- On Regret-Optimal Learning in Decentralized Multiplayer Multiarmed Bandits
- Online Learning of Rested and Restless Bandits
- Partially observed Markov decision process multiarmed bandits-structural results
- Regret in online combinatorial optimization
- Regret Minimization Under Partial Monitoring
- Risk-Sensitive and Risk-Neutral Multiarmed Bandits
- The auction algorithm: A distributed relaxation method for the assignment problem
Cited in
(14)- Distributed cooperative decision making in multi-agent multi-armed bandits
- Decentralized Learning for Multiplayer Multiarmed Bandits
- Multi-player bandits revisited
- Delay and cooperation in nonstochastic bandits
- Multi-player bandits: the adversarial case
- scientific article; zbMATH DE number 7626726 (Why is no real title available?)
- SAMBA: A Generic Framework for Secure Federated Multi-Armed Bandits
- Multiplayer Bandits Without Observing Collision Information
- DOMAIN EXTENSIONS OF THE ERLANG LOSS FUNCTION: THEIR SCALABILITY AND ITS APPLICATIONS TO COOPERATIVE GAMES
- Learning Theory
- Asymptotic optimality for decentralised bandits
- Distributed learning in congested environments with partial information
- Logit-Q dynamics for efficient learning in stochastic teams
- Decentralized cooperative reinforcement learning with hierarchical information structure
This page was built for publication: Game of thrones: fully distributed learning for multiplayer bandits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4991671)
