Towards General Function Approximation in Zero-Sum Markov Games
arXiv:2107.14702
Abstract
This paper considers two-player zero-sum finite-horizon Markov games with simultaneous moves. The study focuses on the challenging settings where the value function or the model is parameterized by general function classes. Provably efficient algorithms for both decoupled and {coordinated} settings are developed. In the {decoupled} setting where the agent controls a single player and plays against an arbitrary opponent, we propose a new model-free algorithm. The sample complexity is governed by the Minimax Eluder dimension -- a new dimension of the function class in Markov games. As a special case, this method improves the state-of-the-art algorithm by a factor in the regret when the reward function and transition kernel are parameterized with -dimensional linear features. In the {coordinated} setting where both players are controlled by the agent, we propose a model-based algorithm and a model-free algorithm. In the model-based algorithm, we prove that sample complexity can be bounded by a generalization of Witness rank to Markov games. The model-free algorithm enjoys a -regret upper bound where is the number of episodes.
References in corpus (25)
- Playing Atari with Deep Reinforcement Learning
- Dota 2 with Large Scale Deep Reinforcement Learning
- 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
- On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
- Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
- Actor-Critic Policy Optimization in Partially Observable Multiagent Environments
- 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
- Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
- Provably efficient RL with Rich Observations via Latent State Decoding
- Provable Self-Play Algorithms for Competitive Reinforcement Learning
- Contextual Bandit Learning with Predictable Rewards
- Model-based Reinforcement Learning and the Eluder Dimension
- Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
- 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
- Bilinear Classes: A Structural Framework for Provable Generalization in RL
- Exploration-Enhanced POLITEX
- On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
- Near-Optimal Reinforcement Learning with Self-Play
- Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
- The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces