Multi-Agent Bandits

Follow this topic Ask about this topic

Latest papers

13 papers2 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits
Oct 13, 2026Sacha Arroues-Paykin, Etienne Boursier, Vianney PerchetMulti-Armed Bandits Multi-Agent Bandits
Ecole Polytechnique · INRIA, LMO, Université Paris-Saclay · CREST, ENSAE
The Deceptive Bandit Problem: Exploratory Coupling and the Fragility of Multi-Agent Learning
Oct 6, 2026Michael Tang, Mahmoud Abdelgalil, Jorge I. PovedaMulti-Agent Bandits Bandit Learning
Electrical and Computer Engineering Department at the University of California, San Diego, La Jolla, CA, USA · Mechanical and Aerospace Engineering Department at the University at Buffalo, State University of New York, Buffalo, NY, USA
DCM Bandits: Multiplayer Information Asymmetric Cascading Bandits for Multiple Clicks
Aug 12, 2026Andy Wang, Charlton Shih, William ChangMulti-Armed Bandits Multi-Agent Bandits
Department of Mathematics University of California, Los Angeles Los Angeles, USA
Improved Multiplayer Bandit Algorithm for Bernoulli Rewards
Aug 11, 2026Khang Nguyen, Ricardo Parada, William ChangMulti-Agent Bandits Multi-Armed Bandits
Dept. of Computer Science University of California, Los Angeles Los Angeles, CA, USA · Dept. of Electrical and Computer Engineering University of California, Los Angeles Los Angeles, CA, USA
Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry
Aug 11, 2026Daphne Feng, Ricardo Parada, Lily Jiang +2Multi-Armed Bandits Robust Multi-Armed Bandits
Department of Mathematics, University of California, Los Angeles, Los Angeles, CA, USA · Department of Mathematics, University of California, Riverside, Riverside, CA, USA
Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits
Aug 11, 2026Ricardo Parada, Chenzhang Zhao, William ChangLipschitz Bandits Multi-Armed Bandits
University of California, Riverside Riverside, CA, USA · University of California, Los Angeles Los Angeles, CA, USA
Collaborating in Multi-Armed Bandits with Strategic Agents
May 13, 2026Idan Barnea, Ofir Schlisselberg, Yishay MansourMulti-Armed Bandits Mechanism Design
Tel Aviv University · Google Research
Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization
May 7, 2026John Wang, Mengfan XuMulti-Armed Bandits Multi-Agent System Optimization
University of Massachusetts Amherst
Bandit Learning in General Open Multi-agent Systems
May 7, 2026Mengfan XuMulti-Armed Bandits Multi-Agent Bandits
Mechanical and Industrial Engineering, University of Massachusetts Amherst
Creator Incentives in Recommender Systems: A Cooperative Game-Theoretic Approach for Stable and Fair Collaboration in Multi-Agent Bandits
Apr 9, 2026Ramakrishnan Krishnamurthy, Arpit Agarwal, Lakshminarayanan Subramanian +1Multi-Agent Bandits Recommender Systems
Courant Institute, New York University · Indian Institute of Technology Bombay · FAIR, Meta AI
SMaRT: Online Reusable Resource Assignment and an Application to Mediation in the Kenyan Judiciary
Feb 20, 2026Shafkat Farabi, Didac Marti Pinto, Wei Lu +4Multi-Agent Bandits Sequential Decision Making
Virginia Tech · University College London · The World Bank
Multi-Agent Lipschitz Bandits
Feb 18, 2026Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1Lipschitz Bandits Multi-Agent Bandits
University of Colorado Boulder · INRIA Paris
Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback
Feb 18, 2026Subham Pokhriyal, Shweta Jain, Vaneet AggarwalMulti-Agent Bandits Submodular Optimization
Indian Institute of Technology Ropar, Rupnagar, India · Purdue University, West Lafayette, USA

Oct 13, 2026J/K move · Enter open · S save

Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits

Sacha Arroues-Paykin, Etienne Boursier, Vianney Perchet

Ecole Polytechnique · INRIA, LMO, Université Paris-Saclay · CREST, ENSAE

Multi-Armed Bandits Multi-Agent Bandits Approximation Algorithms Combinatorial Optimization

Open paper AskPDF arXiv

Motivated by applications to cognitive radio networks, multi-player multi-armed bandits (MMAB) have attracted considerable attention in recent years. The asynchronous variant, in which players are active only at a fraction of timesteps, better reflects real-world decentralized networks, where devices are not permanently active. Despite its practical relevance, this setting remains relatively understudied. Existing work on asynchronous MMAB has focused on homogeneous players, who share the same activation probability, a setting in which the optimal centralized allocation can be easily characterized. In contrast, efficiently computing the optimal allocation in the heterogeneous setting, where players have different activation probabilities, has remained an open problem. In this work, we investigate this problem and first establish its NP-hardness. We then turn to the greedy algorithm, which runs in polynomial time, and prove that it achieves a

\frac{1}{e}

-approximation of the optimal allocation. Furthermore, when players are processed in decreasing order of their activation probabilities, the approximation guarantee improves to

\frac{1}{\sqrt{e}}

. Overall, our results establish the greedy algorithm as an efficient approximation to the optimal allocation, providing a practical oracle baseline for the design of online algorithms for heterogeneous asynchronous multi-player bandits.