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

Abstract

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 ${\max }_{i\in [m]}{A}_i$, where $A_i$ is the number of actions for the $i^{\mathrm{th}}$ player. This is in sharp contrast to the size of the joint action space which is ${\prod }_{i=1}^m{A}_i$. 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.

arXiv commentThis is the journal version of arXiv:2006.12007, with new results on (1) finding CE and CCE in the multiplayer general-sum setting, (2) monotonic techniques that allow V-learning to output Markov policies in a subset of settings, and (3) decoupling V-learning with the adversarial bandit subroutine

References in corpus (18)

• Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments
• Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver
• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Generalization and Exploration via Randomized Value Functions
• On Lower Bounds for Regret in Reinforcement Learning
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
• Decentralized Q-Learning in Zero-sum Markov Games
• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces

Cited by in corpus (2)

• On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games
• Independent Learning in Stochastic Games