2021

Towards General Function Approximation in Zero-Sum Markov Games

Huang, Baihe, Lee, Jason D., Wang, Zhaoran et al.

Understand

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.

Built on

Residual algorithms: Reinforcement learning with function approximation
Leemon Baird · 1995
Earlier work this paper cites.
A generalized reinforcement-learning model: Convergence and applications
Michael L. Littman and Csaba Szepesvari · 1996
Earlier work this paper cites.
Value function approximation in zero-sum markov games
Michail G. Lagoudakis and Ronald Parr · 2002
Earlier work this paper cites.
Correlated Q-learning
Amy Greenwald, Keith Hall, and Roberto Serrano · 2003
Earlier work this paper cites.
PAC model-free reinforcement learning
Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman · 2006
Earlier work this paper cites.
Near-optimal regret bounds for reinforcement learning
Thomas Jaksch, Ronald Ortner, and Peter Auer · 2010
Earlier work this paper cites.
Contextual bandit learning with predictable rewards
Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, and Robert E. Schapire · 2012
Earlier work this paper cites.
Playing atari with deep reinforcement learningep reinforcement learning
Original
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, DaanWierstra, and Martin Riedmiller · 2013
Earlier work this paper cites.
Eluder dimension and the sample complexity of optimistic exploration
Daniel Russo and Benjamin Van Roy · 2013
Earlier work this paper cites.
Model-based reinforcement learning and the eluder dimension
Original
Ian Osband and Benjamin Van Roy · 2014
Earlier work this paper cites.
Deep learning
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton · 2015
Earlier work this paper cites.
Approximate dynamic programming for two-player zero-sum markov games
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin · 2015
Earlier work this paper cites.
Approximate dynamic programming for two-player zero-sum Markov games
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin · 2015
Earlier work this paper cites.
Mastering the game of go with deep neural networks and tree search
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, and Marc Lanctot · 2015
Earlier work this paper cites.
Contextual decision processes with low bellman rank are pac-learnable
Original
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire · 2016
Earlier work this paper cites.
Safe, multi-agent, reinforcement learning for autonomous driving
Original
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua · 2016
Earlier work this paper cites.
Minimax regret bounds for reinforcement learning
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos · 2017
Earlier work this paper cites.
Contextual decision processes with low bellman rank are PAC-learnable
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire · 2017
Earlier work this paper cites.
Learning nash equilibrium for general-sum markov games from batch data
Julien Pérolat, Florian Strub, Bilal Piot, and Olivier Pietquin · 2017
Earlier work this paper cites.
Super-human ai for strategic reasoning: Beating top pros in heads-up no-limit texas hold’em
Tuomas Sandholm · 2017
Earlier work this paper cites.

Similar

Online reinforcement learning in stochastic games
Chen-Yu Wei, Yi-Te Hong, and Chi-Jen Lu · 2017
Cited alongside, same era.
Balancing two-player stochastic games with soft Q-learning
Jordi Grau-Moya, Felix Leibfried, and Haitham Bou-Ammar · 2018
Cited alongside, same era.
Is Q-learning provably efficient?
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I. Jordan · 2018
Cited alongside, same era.
Neural tangent kernel: Convergence and generalization in neural networks
Arthur Jacot, Franck Gabriel, and Clément Hongler · 2018
Cited alongside, same era.
Actor-critic fictitious play in simultaneous move multistage games
Julien Perolat, Bilal Piot, and Olivier Pietquin · 2018
Cited alongside, same era.
Actor-critic policy optimization in partially observable multiagent environments
Sriram Srinivasan, Marc Lanctot, Vinicius Zambaldi, Julien Pérolat, Karl Tuyls, Rémi Munos, and Michael Bowling · 2018
Cited alongside, same era.
Exploration-enhanced POLITEX
Original
Yasin Abbasi-Yadkori, Nevena Lazic, Csaba Szepesvari, and Gellert Weisz · 2019
Cited alongside, same era.
A convergence theory for deep learning via over-parameterization
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song · 2019
Cited alongside, same era.
Dota 2 with large scale deep reinforcement learning
Original
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, and Chris Hesse · 2019
Cited alongside, same era.
Generalization bounds of stochastic gradient descent for wide and deep neural networks
Yuan Cao and Quanquan Gu · 2019
Cited alongside, same era.
Provably efficient RL with rich observations via latent state decoding
Simon S. Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford · 2019
Cited alongside, same era.
Gradient descent finds global minima of deep neural networks
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai · 2019
Cited alongside, same era.

Then

Provable self-play algorithms for competitive reinforcement learning
Original
Yu Bai and Chi Jin · 2020
Later among the works it cites.
Near-optimal reinforcement learning with self-play
Original
Yu Bai, Chi Jin, and Tiancheng Yu · 2020
Later among the works it cites.
A theoretical analysis of deep q-learning
Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang · 2020
Later among the works it cites.
Provably efficient reinforcement learning with linear function approximation
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan · 2020
Later among the works it cites.
Solving discounted stochastic two-player games with near-optimal time and sample complexity
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye · 2020
Later among the works it cites.
Neural policy gradient methods: Global optimality and rates of convergence
Original
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang · 2020
Later among the works it cites.
Provably efficient reinforcement learning with general value function approximation
Original
Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang · 2020
Later among the works it cites.
Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium
Original
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang · 2020
Later among the works it cites.
On function approximation in reinforcement learning: Optimism in the face of large state spaces
Original
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I Jordan · 2020
Later among the works it cites.
Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound
Lin Yang and Mengdi Wang · 2020
Later among the works it cites.
Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity
Original
Kaiqing Zhang, Sham M Kakade, Tamer Başar, and Lin F Yang · 2020
Later among the works it cites.
Learning near optimal policies with low inherent bellman error
Original
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill · 2020
Later among the works it cites.
Sample-efficient learning of stackelberg equilibria in general-sum games
Original
Yu Bai, Chi Jin, Huan Wang, and Caiming Xiong · 2021
Closest in time.
Almost optimal algorithms for two-player markov games with linear function approximation
Original
Zixiang Chen, Dongruo Zhou, and Quanquan Gu · 2021
Closest in time.
Bilinear classes: A structural framework for provable generalization in rl
Original
Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang · 2021
Closest in time.
Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms
Original
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi · 2021
Closest in time.
The power of exploiter: Provable multi-agent rl in large state spaces
Original
Chi Jin, Qinghua Liu, and Tiancheng Yu · 2021
Closest in time.
Optimism in reinforcement learning with generalized linear function approximation
Yining Wang, Ruosong Wang, Simon S. Du, and Akshay Krishnamurthy · 2021
Closest in time.
Provably efficient policy gradient methods for two-player zero-sum markov games, 2021
Yulai Zhao, Yuandong Tian, Jason D. Lee, and Simon S. Du · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…