Distributed Learning in Multi-Armed Bandit with Multiple Players

Abstract

We formulate and study a decentralized multi-armed bandit (MAB) problem. There are M distributed players competing for N independent arms. Each arm, when played, offers i.i.d. reward according to a distribution with an unknown parameter. At each time, each player chooses one arm to play without exchanging observations or any information with other players. Players choosing the same arm collide, and, depending on the collision model, either no one receives reward or the colliding players share the reward in an arbitrary way. We show that the minimum system regret of the decentralized MAB grows with time at the same logarithmic order as in the centralized counterpart where players act collectively as a single entity by exchanging observations and making decisions jointly. A decentralized policy is constructed to achieve this optimal order while ensuring fairness among players and without assuming any pre-agreement or information exchange among players. Based on a Time Division Fair Sharing (TDFS) of the M best arms, the proposed policy is constructed and its order optimality is proven under a general reward model. Furthermore, the basic structure of the TDFS policy can be used with any order-optimal single-player policy to achieve order optimality in the decentralized setting. We also establish a lower bound on the system regret growth rate for a general class of decentralized polices, to which the proposed policy belongs. This problem finds potential applications in cognitive radio networks, multi-channel communication systems, multi-agent systems, web search and advertising, and social networks.

31 pages, 8 figures, revised paper submitted to IEEE Transactions on Signal Processing, April, 2010, the pre-agreement in the decentralized TDFS policy is eliminated to achieve a complete decentralization among players

References in corpus (1)

• Distributed Algorithms for Learning and Cognitive Medium Access with Logarithmic Regret

Cited by in corpus (81)

• Multi-Armed Bandit Based Client Scheduling for Federated Learning
• Online Learning of Rested and Restless Bandits
• Channel Selection for Network-assisted D2D Communication via No-Regret Bandit Learning with Calibrated Forecasting
• Risk-Averse Multi-Armed Bandit Problems under Mean-Variance Measure
• Distributed Online Learning in Social Recommender Systems
• Potential and Pitfalls of Multi-Armed Bandits for Decentralized Spatial Reuse in WLANs
• Differentially-Private Federated Linear Bandits
• Distributed Learning for Channel Allocation Over a Shared Spectrum
• Distributed Exploration in Multi-Armed Bandits
• On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits
• Game of Thrones: Fully Distributed Learning for Multi-Player Bandits
• Federated Bandit: A Gossiping Approach
• Bandit Learning in Decentralized Matching Markets
• Action-Manipulation Attacks Against Stochastic Bandits: Attacks and Defense
• Towards Optimal Adaptive Wireless Communications in Unknown Environments
• Multi-Player Bandits: The Adversarial Case
• Decentralized Learning for Multi-player Multi-armed Bandits
• Decentralized Online Learning Algorithms for Opportunistic Spectrum Access
• Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions
• SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits
• Federated Multi-armed Bandits with Personalization
• Federated Linear Contextual Bandits
• Non-Stationary Bandits with Habituation and Recovery Dynamics
• Decoupling Exploration and Exploitation in Multi-Armed Bandits
• Deterministic Sequencing of Exploration and Exploitation for Multi-Armed Bandit Problems
• Concurrent bandits and cognitive radio networks
• Competing Bandits in Matching Markets
• Low-Complexity Methods for Estimation After Parameter Selection
• Kernel Methods for Cooperative Multi-Agent Contextual Bandits
• Multiplayer Multi-armed Bandits for Optimal Assignment in Heterogeneous Networks
• Learning in A Changing World: Restless Multi-Armed Bandit with Unknown Dynamics
• A Learning-based Distributed Algorithm for Scheduling in Multi-hop Wireless Networks
• Dynamic Spectrum Access in Time-varying Environment: Distributed Learning Beyond Expectation Optimization
• Multiplayer Bandit Learning, from Competition to Cooperation
• Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits
• Cooperative Multi-Agent Bandits with Heavy Tails
• Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information
• Let Cognitive Radios Imitate: Imitation-based Spectrum Access for Cognitive Radio Networks
• Online Learning in Decentralized Multiuser Resource Sharing Problems
• Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximation
• Collaborative Top Distribution Identifications with Limited Interaction
• Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systems
• Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions
• Decentralized Learning for Channel Allocation in IoT Networks over Unlicensed Bandwidth as a Contextual Multi-player Multi-armed Bandit Game
• Multi-Player Bandits -- a Musical Chairs Approach
• My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits
• Online Learning for Cooperative Multi-Player Multi-Armed Bandits
• A survey on multi-player bandits
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• On Effective Parallelization of Monte Carlo Tree Search
• An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit
• Accelerated learning from recommender systems using multi-armed bandit
• Decentralized Restless Bandit with Multiple Players and Unknown Dynamics
• A Sensing Contribution-based Two-layer Game for Channel Selection and Spectrum Access in Cognitive Radio Ad-hoc Networks
• Online Learning in Opportunistic Spectrum Access: A Restless Bandit Approach
• Observe Before Play: Multi-armed Bandit with Pre-observations
• A High Performance, Low Complexity Algorithm for Multi-Player Bandits Without Collision Sensing Information
• On No-Sensing Adversarial Multi-player Multi-armed Bandits with Collision Communications
• Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis
• Multitask Bandit Learning Through Heterogeneous Feedback Aggregation
• Coordination without communication: optimal regret in two players multi-armed bandits
• Online Learning for Combinatorial Network Optimization with Restless Markovian Rewards
• Optimal Adaptive Learning in Uncontrolled Restless Bandit Problems
• Value of Information Aware Opportunistic Duty Cycling in Solar Harvesting Sensor Networks
• Almost Optimal Energy-Efficient Cognitive Communications in Unknown Environments
• CubeTR: Learning to Solve The Rubiks Cube Using Transformers
• Regret vs. Communication: Distributed Stochastic Multi-Armed Bandits and Beyond
• Decentralized Upper Confidence Bound Algorithms for Homogeneous Multi-Agent Multi-Armed Bandits
• Constant or logarithmic regret in asynchronous multiplayer bandits
• Optimal Stochastic Nonconvex Optimization with Bandit Feedback
• Almost Optimal Channel Access in Multi-Hop Networks With Unknown Channel Variables
• Distributed Learning and Multiaccess of On-Off Channels
• Energy-Efficient Nonstationary Spectrum Sharing
• Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Plays
• Meeting of Mobile Nodes Based on RSS Measurements in Wireless Ad Hoc Networks
• Performance and Convergence of Multi-user Online Learning
• Distributed Flow Scheduling in an Unknown Environment
• Distributed No-Regret Learning in Multi-Agent Systems
• On Distributed Multi-player Multiarmed Bandit Problems in Abruptly Changing Environment
• Distributed Learning Algorithms for Opportunistic Spectrum Access in Infrastructure-less Networks
• Collaborative Pure Exploration in Kernel Bandit