2020

Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium

Xie, Qiaomin, Chen, Yudong, Wang, Zhaoran et al.

Understand

We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games with simultaneous moves.

To incorporate function approximation, we consider a family of Markov games where the reward function and transition kernel possess a linear structure.
Both the offline and online settings of the problems are considered.
In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap.

Built on

Q-learning with UCB exploration is sample efficient for infinite-horizon MDP
Original
Dong, K., Wang, Y., Chen, X., and Wang, L. (2019b) · 1901
Earlier work this paper cites.
Provably efficient RL with rich observations via latent state decoding
Original
Du, S. S., Krishnamurthy, A., Jiang, N., Agarwal, A., Dudík, M., and Langford, J. (2019a) · 1901
Earlier work this paper cites.
A theoretical analysis of deep Q-learning
Yang, Z., Xie, Y., and Wang, Z. (2019) · 1901
Earlier work this paper cites.
Sample-optimal parametric Q-learning with linear transition models
Original
Yang, L. F. and Wang, M. (2019b) · 1902
Earlier work this paper cites.
Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound
Original
Yang, L. F. and Wang, M. (2019a) · 1905
Earlier work this paper cites.
Model-based reinforcement learning with a generative model is minimax optimal
Original
Agarwal, A., Kakade, S., and Yang, L. F. (2019) · 1906
Earlier work this paper cites.
Feature-based Q-learning for two-player stochastic games
Original
Jia, Z., Yang, L. F., and Wang, M. (2019) · 1906
Earlier work this paper cites.
Provably efficient reinforcement learning with linear function approximation
Original
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2019) · 1907
Earlier work this paper cites.
Exploration-enhanced POLITEX
Original
Abbasi-Yadkori, Y., Lazic, N., Szepesvari, C., and Weisz, G. (2019b) · 1908
Earlier work this paper cites.
Solving discounted stochastic two-player games with near-optimal time and sample complexity
Original
Sidford, A., Wang, M., Yang, L. F., and Ye, Y. (2019) · 1908
Earlier work this paper cites.
Emergent tool use from multi-agent autocurricula
Original
Baker, B., Kanitscheider, I., Markov, T., Wu, Y., Powell, G., McGrew, B., and Mordatch, I. (2019) · 1909
Earlier work this paper cites.
n \sqrt{n} -regret for learning in markov decision processes with function approximation and low Bellman rank
Original
Dong, K., Peng, J., Wang, Y., and Zhou, Y. (2019a) · 1909
Earlier work this paper cites.
Value function estimation in markov reward processes: Instance-dependent ℓ ∞ \ell_{\infty} -bounds for policy evaluation
Original
Pananjady, A. and Wainwright, M. J. (2019) · 1909
Earlier work this paper cites.
Frequentist regret bounds for randomized least-squares value iteration
Original
Zanette, A., Brandfonbrener, D., Pirotta, M., and Lazaric, A. (2019) · 1911
Earlier work this paper cites.
Multi-agent reinforcement learning: A selective overview of theories and algorithms
Original
Zhang, K., Yang, Z., and Başar, T. (2019) · 1911
Earlier work this paper cites.
Provably efficient exploration in policy optimization
Original
Cai, Q., Yang, Z., Jin, C., and Wang, Z. (2019) · 1912
Earlier work this paper cites.
Learning adversarial mdps with bandit feedback and unknown transition
Original
Jin, T. and Luo, H. (2019) · 1912
Earlier work this paper cites.
Optimism in reinforcement learning with generalized linear function approximation
Original
Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A. (2019) · 1912
Earlier work this paper cites.
Stochastic games
Shapley, L. S. (1953) · 1953
Earlier work this paper cites.
On stochastic games
Maitra, A. and Parthasarathy, T. (1970) · 1970
Earlier work this paper cites.
On stochastic games, ii
Maitra, A. and Parthasarathy, T. (1971) · 1971
Earlier work this paper cites.
Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon
Moulin, H. and Vial, J.-P. (1978) · 1978
Earlier work this paper cites.
Correlated equilibrium as an expression of Bayesian rationality
Aumann, R. J. (1987) · 1987
Earlier work this paper cites.
Q-learning
Watkins, C. J. and Dayan, P. (1992) · 1992
Earlier work this paper cites.
Linear least-squares algorithms for temporal difference learning
Bradtke, S. J. and Barto, A. G. (1996) · 1996
Earlier work this paper cites.
A generalized reinforcement-learning model: Convergence and applications
Littman, M. L. and Szepesvari, C. (1996) · 1996
Earlier work this paper cites.
Actor-critic algorithms
Konda, V. R. and Tsitsiklis, J. N. (2000) · 2000
Earlier work this paper cites.
Correlated Q-learning
Greenwald, A., Hall, K., and Serrano, R. (2003) · 2003
Earlier work this paper cites.

Similar

Nash Q-learning for general-sum stochastic games
Hu, J. and Wellman, M. P. (2003) · 2003
Cited alongside, same era.
On the sample complexity of reinforcement learning
Kakade, S. M. (2003) · 2003
Cited alongside, same era.
PAC model-free reinforcement learning
Strehl, A. L., Li, L., Wiewiora, E., Langford, J., and Littman, M. L. (2006) · 2006
Cited alongside, same era.
Regret minimization and the price of total anarchy
Blum, A., Hajiaghayi, M., Ligett, K., and Roth, A. (2008) · 2008
Cited alongside, same era.
A comprehensive survey of multiagent reinforcement learning
Busoniu, L., Babuska, R., and Schutter, B. D. (2008) · 2008
Cited alongside, same era.
Finite-time bounds for fitted value iteration
Munos, R. and Szepesvári, C. (2008) · 2008
Cited alongside, same era.
Computing correlated equilibria in multi-player games
Papadimitriou, C. H. and Roughgarden, T. (2008) · 2008
Cited alongside, same era.
Settling the complexity of computing two-player Nash equilibria
Chen, X., Deng, X., and Teng, S.-H. (2009) · 2009
Cited alongside, same era.
The complexity of computing a Nash equilibrium
Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H. (2009) · 2009
Cited alongside, same era.
Near-optimal regret bounds for reinforcement learning
Jaksch, T., Ortner, R., and Auer, P. (2010) · 2010
Cited alongside, same era.
Improved algorithms for linear stochastic bandits
Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011) · 2011
Cited alongside, same era.
Value function approximation in zero-sum Markov games
Original
Lagoudakis, M. and Parr, R. (2012) · 2012
Cited alongside, same era.

Then

Emergent complexity via multi-agent competition
Original
Bansal, T., Pachocki, J., Sidor, S., Sutskever, I., and Mordatch, I. (2017) · 2017
Later among the works it cites.
Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning
Dann, C., Lattimore, T., and Brunskill, E. (2017) · 2017
Later among the works it cites.
Contextual decision processes with low bellman rank are PAC-learnable
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2017) · 2017
Later among the works it cites.
Multi-agent actor-critic for mixed cooperative-competitive environments
Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, O. P., and Mordatch, I. (2017) · 2017
Later among the works it cites.
Deepstack: Expert-level artificial intelligence in heads-up no-limit poker
Moravčík, M., Schmid, M., Burch, N., Lisỳ, V., Morrill, D., Bard, N., Davis, T., Waugh, K., Johanson, M., and Bowling, M. (2017) · 2017
Later among the works it cites.
Proximal policy optimization algorithms
Original
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017) · 2017
Later among the works it cites.
Mastering the game of Go without human knowledge
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., and Bolton, A. (2017) · 2017
Later among the works it cites.
Online reinforcement learning in stochastic games
Wei, C.-Y., Hong, Y.-T., and Lu, C.-J. (2017) · 2017
Later among the works it cites.
Efficient reinforcement learning in deterministic systems with value function generalization
Wen, Z. and Van Roy, B. (2017) · 2017
Later among the works it cites.
Superhuman AI for heads-up no-limit poker: Libratus beats top professionals
Brown, N. and Sandholm, T. (2018) · 2018
Later among the works it cites.
On oracle-efficient PAC rl with rich observations
Dann, C., Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2018) · 2018
Later among the works it cites.
Balancing two-player stochastic games with soft q-learning
Original
Grau-Moya, J., Leibfried, F., and Bou-Ammar, H. (2018) · 2018
Later among the works it cites.
Social influence as intrinsic motivation for multi-agent deep reinforcement learning
Original
Jaques, N., Lazaridou, A., Hughes, E., Gulcehre, C., Ortega, P. A., Strouse, D., Leibo, J. Z., and De Freitas, N. (2018) · 2018
Later among the works it cites.
Is Q-learning provably efficient?
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018) · 2018
Later among the works it cites.
Bandit algorithms
Lattimore, T. and Szepesvári, C. (2018) · 2018
Later among the works it cites.
OpenAI Five
OpenAI (2018) · 2018
Later among the works it cites.
Actor-critic fictitious play in simultaneous move multistage games
Perolat, J., Piot, B., and Pietquin, O. (2018) · 2018
Later among the works it cites.
Actor-critic policy optimization in partially observable multiagent environments
Srinivasan, S., Lanctot, M., Zambaldi, V., Pérolat, J., Tuyls, K., Munos, R., and Bowling, M. (2018) · 2018
Later among the works it cites.
Reinforcement learning: An introduction
Sutton, R. S. and Barto, A. G. (2018) · 2018
Later among the works it cites.
Superhuman AI for multiplayer poker
Brown, N. and Sandholm, T. (2019) · 2019
Later among the works it cites.
Online stochastic shortest path with bandit feedback and unknown transition function
Rosenberg, A. and Mansour, Y. (2019) · 2019
Later among the works it cites.
Worst-case regret bounds for exploration via randomized value functions
Russo, D. (2019) · 2019
Later among the works it cites.
Non-asymptotic gap-dependent regret bounds for tabular MDPs
Simchowitz, M. and Jamieson, K. G. (2019) · 2019
Later among the works it cites.
Grandmaster level in StarCraft II using multi-agent reinforcement learning
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., Oh, J., Horgan, D., Kroiss, M., Danihelka, I., Huang, A., Sifre, L., Cai, T., Agapiou, J. P., Jaderberg, M., Vezhnevets, A. S., Leblond, R., Pohlen, T., Dalibard, V., Budden, D., Sulsky, Y., Molloy, J., Paine, T. L., Gulcehre, C., Wang, Z., Pfaff, T., Wu, Y., Ring, R., Yogatama, D., Wünsch, D., McKinney, K., Smith, O., Schaul, T., Lillicrap, T., Kavukcuoglu, K., Hassabis, D., Apps, C., and Silver, D. (2019) · 2019
Later among the works it cites.
Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds
Zanette, A. and Brunskill, E. (2019) · 2019
Later among the works it cites.
The leave-one-out approach for matrix completion: Primal and dual analysis
Original
Ding, L. and Chen, Y. (2020) · 2020
Closest in time.
Is a good representation sufficient for sample efficient reinforcement learning?
Du, S. S., Kakade, S. M., Wang, R., and Yang, L. F. (2020) · 2020
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…