Data to 14 Oct 2026

V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL

arXiv 2110.14555 ↗First posted 27 Oct 2021cs.LG cs.AI cs.GTcited by 114

Not on the map. Why?

Abstract (arXiv)

A major challenge of multiagent reinforcement learning (MARL) is the curse of multiagents, where the size of the joint action space scales exponentially with the number of agents. This remains to be a bottleneck for designing efficient MARL algorithms even in a basic scenario with finitely many states and actions. This paper resolves this challenge for the model of episodic Markov games. We design a new class of fully decentralized algorithms -- V-learning, which provably learns Nash equilibria (in the two-player zero-sum setting), correlated equilibria and coarse correlated equilibria (in the multiplayer general-sum setting) in a number of samples that only scales with maxi∈[m] Ai, where Ai is the number of actions for the irm th player. This is in sharp contrast to the size of the joint action space which is prodi=1m Ai. V-learning (in its basic form) is a new class of single-agent RL algorithms that convert any adversarial bandit algorithm with suitable regret guarantees into a RL algorithm. Similar to the classical Q-learning algorithm, it performs incremental updates to the value functions. Different from Q-learning, it only maintains the estimates of V-values instead of Q-values. This key difference allows V-learning to achieve the claimed guarantees in the MARL setting by simply letting all agents run V-learning independently.

Key facts. Cited by 114 papers in the map (data through 14 Oct 2026). Builds on 34 of its 65 references that are in the map. First posted on arXiv 27 Oct 2021.

Builds on

34 of 65 references.

References · 34

2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
2018QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 708
2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
2017Minimax Regret Bounds for Reinforcement Learningcited by 503
2017Value-Decomposition Networks For Cooperative Multi-Agent Learningcited by 503
2018Is Q-learning Provably Efficient?cited by 487
2019QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learningcited by 379
2019Emergent Tool Use From Multi-Agent Autocurriculacited by 313
2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
2018Actor-Attention-Critic for Multi-Agent Reinforcement Learningcited by 261
2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223

22 more

2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 194
2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
2014Generalization and Exploration via Randomized Value Functionscited by 112
2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 92
2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
2017Online Reinforcement Learning in Stochastic Gamescited by 67
2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 58
2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 42
2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
2016On Lower Bounds for Regret in Reinforcement Learningcited by 40
2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 24
2020No-Regret Learning Dynamics for Extensive-Form Correlated Equilibriumcited by 19
2019Learning to Collaborate in Markov Decision Processescited by 14

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 31; 2023: 30; 2024: 28; 2025: 11; 2026: 10.

114 papers.

Sort:

By area:

2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 49
2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learningcited by 45
2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 30
2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 30
2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 28
2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 27
2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 27
2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 26
2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 25

38 more

2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 24
2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descentcited by 24
2021Independent Learning in Stochastic Gamescited by 22
2022Independent and Decentralized Learning in Markov Potential Gamescited by 22
2022What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?cited by 22
2023Offline Learning in Markov Games with General Function Approximationcited by 18
2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 16
2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
2022Representation Learning for General-sum Low-rank Markov Gamescited by 15
2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
2022A Survey on Large-Population Systems and Scalable Multi-Agent Reinforcement Learningcited by 14
2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 14
2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 14
2024Performative Reinforcement Learning in Gradually Shifting Environmentscited by 14
2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 13
2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 13
2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 12
2022Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Gamescited by 11
2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
2022Learning in Congestion Games with Bandit Feedbackcited by 10
2022Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium Solverscited by 10
2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 10
2023Efficient Adversarial Attacks on Online Multi-agent Reinforcement Learningcited by 10
2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 10
2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
2023Learning Multi-Agent Communication with Contrastive Learningcited by 9
2023Towards a Pretrained Model for Restless Bandits via Multi-arm Generalizationcited by 9
2024Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RLcited by 9
2024Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learningcited by 9
2023Achieving Fairness in Multi-Agent Markov Decision Processes Using Reinforcement Learningcited by 8
2024Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scalecited by 8
2022Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Gamescited by 7
2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 7
2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7

50 most cited of 114 All 114 (JSON)