The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
arXiv:2106.03352
Abstract
Modern reinforcement learning (RL) commonly engages practical problems with large state spaces, where function approximation must be deployed to approximate either the value function or the policy. While recent progresses in RL theory address a rich set of RL problems with general function approximation, such successes are mostly restricted to the single-agent setting. It remains elusive how to extend these results to multi-agent RL, especially due to the new challenges arising from its game-theoretical nature. This paper considers two-player zero-sum Markov Games (MGs). We propose a new algorithm that can provably find the Nash equilibrium policy using a polynomial number of samples, for any MG with low multi-agent Bellman-Eluder dimension -- a new complexity measure adapted from its single-agent version (Jin et al., 2021). A key component of our new algorithm is the exploiter, which facilitates the learning of the main player by deliberately exploiting her weakness. Our theoretical framework is generic, which applies to a wide range of models including but not limited to tabular MGs, MGs with linear or kernel function approximation, and MGs with rich observations.
References in corpus (25)
- Dota 2 with Large Scale Deep Reinforcement Learning
- Emergent Tool Use From Multi-Agent Autocurricula
- Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
- Provably Efficient Reinforcement Learning with Linear Function Approximation
- Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
- Learning Near Optimal Policies with Low Inherent Bellman Error
- Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
- Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
- Optimism in Reinforcement Learning with Generalized Linear Function Approximation
- Provable Self-Play Algorithms for Competitive Reinforcement Learning
- Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
- Model-based Reinforcement Learning and the Eluder Dimension
- FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
- Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
- Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
- Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
- Feature-Based Q-Learning for Two-Player Stochastic Games
- Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
- Bilinear Classes: A Structural Framework for Provable Generalization in RL
- Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
- No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium
- Near-Optimal Reinforcement Learning with Self-Play
- Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
- Multi-Agent Trust Region Policy Optimization
- Provably Efficient Algorithms for Multi-Objective Competitive RL