AISTATS 2022poster74 citations
Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games
Yulai Zhao, Yuandong Tian, Jason Lee, Simon Du
Abstract
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.
BibTeX
@InProceedings{pmlr-v151-zhao22b,
title = { Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games },
author = {Zhao, Yulai and Tian, Yuandong and Lee, Jason and Du, Simon},
booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics},
pages = {2736--2761},
year = {2022},
editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel},
volume = {151},
series = {Proceedings of Machine Learning Research},
month = {28--30 Mar},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v151/zhao22b/zhao22b.pdf},
url = {https://proceedings.mlr.press/v151/zhao22b.html},
abstract = { 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. }
}