Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games
Policy-based methods with function approximation are widely used for solving two-player zero-sum games with large state and/or action spaces. However, it remains elusive how to obtain optimization and statistical guarantees for such algorithms. We present a new policy optimization algorithm with function approximation and prove that under standard regularity conditions on the Markov game and the function approximation class, our algorithm finds a near-optimal policy within a polynomial number of samples and iterations. To our knowledge, this is the first provably efficient policy optimization algorithm with function approximation that solves two-player zero-sum Markov games.
Code (0)
등록된 구현이 없습니다.
Tasks
Policy Gradient MethodsVocal Bursts Valence PredictionSimilar Papers 제목 키워드 기반
Policy Optimization in Zero-Sum Markov Games: Fictitious Self-Play Provably Attains Nash Equilibria
Fictitious Self-Play (FSP) has achieved significant empirical success in solving extensive-form games. However, from a theoretical perspective, it remains unknown whether FSP is guaranteed to converge to Nash equilibria…
Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions
While single-agent policy optimization in a fixed environment has attracted a lot of research attention recently in the reinforcement learning community, much less is known theoretically when there are multiple agents pl…
Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning
We examine online safe multi-agent reinforcement learning using constrained Markov games in which agents compete by maximizing their expected total rewards under a constraint on expected total utilities. Our focus is con…
Multi-agent Reinforcement Learningreinforcement-learningReinforcement LearningSafe Reinforcement LearningA Sharp Analysis of Model-based Reinforcement Learning with Self-Play
Model-based algorithms -- algorithms that explore the environment through building and utilizing an estimated model -- are widely used in reinforcement learning practice and theoretically shown to achieve optimal sample …
Model-based Reinforcement LearningMulti-agent Reinforcement Learningreinforcement-learningReinforcement Learning+1Sample Efficient Stochastic Policy Extragradient Algorithm for Zero-Sum Markov Game
Two-player zero-sum Markov game is a fundamental problem in reinforcement learning and game theory. Although many algorithms have been proposed for solving zero-sum Markov games in the existing literature, they generally…