2021

Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games

Chen, Zixiang, Zhou, Dongruo, Gu, Quanquan

Understand

We study reinforcement learning for two-player zero-sum Markov games with simultaneous moves in the finite-horizon setting, where the transition kernel of the underlying Markov games can be parameterized by a linear function over the current state, both players' actions and the next state.

In particular, we assume that we can control both players and aim to find the Nash Equilibrium by minimizing the duality gap.
We propose an algorithm Nash-UCRL based on the principle "Optimism-in-Face-of-Uncertainty".
Our algorithm only needs to find a Coarse Correlated Equilibrium (CCE), which is computationally efficient.

Built on

Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound
Original
Lin F Yang and Mengdi Wang · 1905
Earlier work this paper cites.
Stochastic games
Lloyd S Shapley · 1953
Earlier work this paper cites.
Frequentist regret bounds for randomized least-squares value iteration
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric · 1964
Earlier work this paper cites.
Weighted sums of certain dependent random variables
Kazuoki Azuma · 1967
Earlier work this paper cites.
Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon
Hervé Moulin and J-P Vial · 1978
Earlier work this paper cites.
Correlated equilibrium as an expression of bayesian rationality
Robert J Aumann · 1987
Earlier work this paper cites.
Learning from delayed rewards
Christopher John Cornish Hellaby Watkins · 1989
Earlier work this paper cites.
Markov games as a framework for multi-agent reinforcement learning
Michael L Littman · 1994
Earlier work this paper cites.
A generalized reinforcement-learning model: Convergence and applications
Michael L Littman and Csaba Szepesvári · 1996
Earlier work this paper cites.
Friend-or-foe q-learning in general-sum games
Michael L Littman · 2001
Earlier work this paper cites.
Near-optimal reinforcement learning in polynomial time
Michael Kearns and Satinder Singh · 2002
Earlier work this paper cites.
Correlated q-learning
Amy Greenwald, Keith Hall, and Roberto Serrano · 2003
Earlier work this paper cites.
Nash q-learning for general-sum stochastic games
Junling Hu and Michael P Wellman · 2003
Earlier work this paper cites.
Learning near optimal policies with low inherent Bellman error
Original
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill · 2003
Earlier work this paper cites.
Finite-time bounds for fitted value iteration
Rémi Munos and Csaba Szepesvári · 2008
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.

Similar

Improved algorithms for linear stochastic bandits
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári · 2011
Cited alongside, same era.
Value function approximation in zero-sum markov games
Original
Michail Lagoudakis and Ron Parr · 2012
Cited alongside, same era.
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick · 2013
Cited alongside, same era.
Markov decision processes: discrete stochastic dynamic programming
Martin L Puterman · 2014
Cited alongside, same era.
Approximate dynamic programming for two-player zero-sum markov games
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin · 2015
Cited alongside, same era.
Safe, multi-agent, reinforcement learning for autonomous driving
Original
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua · 2016
Cited alongside, same era.
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, Marc Lanctot, et al · 2016
Cited alongside, same era.
Minimax regret bounds for reinforcement learning
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos · 2017
Cited alongside, same era.
Learning nash equilibrium for general-sum markov games from batch data
Julien Pérolat, Florian Strub, Bilal Piot, and Olivier Pietquin · 2017
Cited alongside, same era.
Online reinforcement learning in stochastic games
Original
Chen-Yu Wei, Yi-Te Hong, and Chi-Jen Lu · 2017
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.
Near-optimal time and sample complexities for for solving discounted Markov decision process with a generative model
Original
Aaron Sidford, Mengdi Wang, Xian Wu, Lin F Yang, and Yinyu Ye · 2018
Cited alongside, same era.

Then

Optimism in reinforcement learning with generalized linear function approximation
Original
Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy · 2019
Later among the works it cites.
Model-based reinforcement learning with value-targeted regression
Original
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin F Yang · 2020
Later among the works it cites.
Provable self-play algorithms for competitive reinforcement learning
Yu Bai and Chi Jin · 2020
Later among the works it cites.
Near-optimal reinforcement learning with self-play
Yu Bai, Chi Jin, and Tiancheng Yu · 2020
Later among the works it cites.
Minimax sample complexity for turn-based stochastic game
Original
Qiwen Cui and Lin F Yang · 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.
Model-based reinforcement learning with value-targeted regression
Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang · 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.
A sharp analysis of model-based reinforcement learning with self-play
Original
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin · 2020
Later among the works it cites.
Sample complexity of reinforcement learning using linearly combined model ensembles
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh · 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.
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.
Model-free reinforcement learning: from clipped pseudo-regret to sample complexity
Original
Zihan Zhang, Yuan Zhou, and Xiangyang Ji · 2020
Later among the works it cites.
Provably efficient reinforcement learning for discounted mdps with feature mapping
Dongruo Zhou, Jiafan He, and Quanquan Gu · 2020
Later among the works it cites.
Logarithmic regret for reinforcement learning with linear function approximation
Jiafan He, Dongruo Zhou, and Quanquan Gu · 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…