Decentralized Learning for Multiplayer Multiarmed Bandits

DOI10.1109/TIT.2014.2302471zbMATH Open1360.91038arXiv1206.3582OpenAlexW2061641373MaRDI QIDQ2986457FDOQ2986457

Authors: Dileep Kalathil, Naumaan Nayyar, Rahul Jain 

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We consider the problem of distributed online learning with multiple players in multi-armed bandits (MAB) models. Each player can pick among multiple arms. When a player picks an arm, it gets a reward. We consider both i.i.d. reward model and Markovian reward model. In the i.i.d. model each arm is modelled as an i.i.d. process with an unknown distribution with an unknown mean. In the Markovian model, each arm is modelled as a finite, irreducible, aperiodic and reversible Markov chain with an unknown probability transition matrix and stationary distribution. The arms give different rewards to different players. If two players pick the same arm, there is a "collision", and neither of them get any reward. There is no dedicated control channel for coordination or communication among the players. Any other communication between the users is costly and will add to the regret. We propose an online index-based distributed learning policy called $tdUC{B}_4$ algorithm that trades off extit{exploration v. exploitation} in the right way, and achieves expected regret that grows at most as near-$O(lo{g}^{2}T)$. The motivation comes from opportunistic spectrum access by multiple secondary users in cognitive radio networks wherein they must pick among various wireless channels that look different to different users. This is the first distributed learning algorithm for multi-player MABs to the best of our knowledge.

Full work available at URL: https://arxiv.org/abs/1206.3582

Recommendations

• On Regret-Optimal Learning in Decentralized Multiplayer Multiarmed Bandits
• Distributed Learning in Multi-Armed Bandit With Multiple Players
• Distributed Multiarmed Bandits
• Decentralized Heterogeneous Multi-Player Multi-Armed Bandits With Non-Zero Rewards on Collisions
• Distributed cooperative decision making in multi-agent multi-armed bandits
• Distributed Online Learning via Cooperative Contextual Bandits
• Partially decentralized reinforcement learning in finite, multi-agent Markov decision processes
• Game of thrones: fully distributed learning for multiplayer bandits
• Asymptotic optimality for decentralised bandits

Mathematics Subject Classification ID

Rationality and learning in game theory (91A26) Probabilistic games; gambling (91A60)

Cited In (9)

• Decentralized Learning in Finite Markov Chains: Revisited
• Integrated online learning and adaptive control in queueing systems with uncertain payoffs
• Distributed learning in congested environments with partial information
• Game of thrones: fully distributed learning for multiplayer bandits
• Distributed cooperative decision making in multi-agent multi-armed bandits
• Multiplayer Bandits Without Observing Collision Information
• Title not available (Why is that?)
• Decentralized Q-Learning for Stochastic Teams and Games
• Bounded Regret for Finitely Parameterized Multi-Armed Bandits

This page was built for publication: Decentralized Learning for Multiplayer Multiarmed Bandits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986457)