2019

Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity

Sidford, Aaron, Wang, Mengdi, Yang, Lin F. et al.

Understand

In this paper, we settle the sampling complexity of solving discounted two-player turn-based zero-sum stochastic games up to polylogarithmic factors.

Given a stochastic game with discount factor $\gamma\in(0,1)$ we provide an algorithm that computes an $\epsilon$-optimal strategy with high-probability given $\tilde{O}((1 - \gamma)^{-3} \epsilon^{-2})$ samples from the transition function for each state-action-pair.
Our algorithm runs in time nearly linear in the number of samples and uses space nearly linear in the number of state-action pairs.
As stochastic games generalize Markov decision processes (MDPs) our runtime and sample complexities are optimal due to Azar et al (2013).

Built on

On the optimality of sparse model-based planning for markov decision processes
Original
Agarwal, A., Kakade, S., and Yang, L. F. (2019) · 1906
Earlier work this paper cites.
Non-cooperative games
Nash, J. (1951) · 1951
Earlier work this paper cites.
Stochastic games
Shapley, L. S. (1953) · 1953
Earlier work this paper cites.
Dynamic Programming
Bellman, R. (1957) · 1957
Earlier work this paper cites.
Les problemes de decisions sequentielles
De Ghellinck, G. (1960) · 1960
Earlier work this paper cites.
Dynamic programming and Markov processes
Howard, R. A. (1960) · 1960
Earlier work this paper cites.
A probabilistic production and inventory problem
d’Epenoux, F. (1963) · 1963
Earlier work this paper cites.
Game theory
Fudenberg, D. and Tirole, J. (1991) · 1991
Earlier work this paper cites.
The complexity of stochastic games
Condon, A. (1992) · 1992
Earlier work this paper cites.
Markov games as a framework for multi-agent reinforcement learning
Littman, M. L. (1994) · 1994
Earlier work this paper cites.
An upper bound on the loss from approximate optimal-value functions
Singh, S. P. and Yee, R. C. (1994) · 1994
Earlier work this paper cites.
Algorithms for sequential decision making
Littman, M. L. (1996) · 1996
Earlier work this paper cites.

Similar

Multiagent reinforcement learning: theoretical framework and an algorithm
Hu, J., Wellman, M. P., et al. (1998) · 1998
Cited alongside, same era.
Multiagent reinforcement learning in stochastic games
Hu, J. and Wellman, M. P. (1999) · 1999
Cited alongside, same era.
Finite-sample convergence rates for q-learning and indirect algorithms
Kearns, M. J. and Singh, S. P. (1999) · 1999
Cited alongside, same era.
On the complexity of policy iteration
Mansour, Y. and Singh, S. (1999) · 1999
Cited alongside, same era.
An analysis of stochastic game theory for multiagent reinforcement learning
Bowling, M. and Veloso, M. (2000) · 2000
Cited alongside, same era.
Rational and convergent learning in stochastic games
Bowling, M. and Veloso, M. (2001) · 2001
Cited alongside, same era.
Markov perfect equilibrium. I. Observable actions
Maskin, E. and Tirole, J. (2001) · 2001
Cited alongside, same era.
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.
A new complexity result on solving the Markov decision problem
Ye, Y. (2005) · 2005
Cited alongside, same era.
Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems
Even-Dar, E., Mannor, S., and Mansour, Y. (2006) · 2006
Cited alongside, same era.
Reinforcement learning with a near optimal rate of convergence
Azar, M. G., Munos, R., Ghavamzadeh, M., and Kappen, H. (2011a)
Cited in the paper.

Then

The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
Ye, Y. (2011) · 2011
Later among the works it cites.
Competitive Markov decision processes
Filar, J. and Vrieze, K. (2012) · 2012
Later among the works it cites.
Minimax pac bounds on the sample complexity of reinforcement learning with a generative model
Azar, M. G., Munos, R., and Kappen, H. J. (2013) · 2013
Later among the works it cites.
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
Hansen, T. D., Miltersen, P. B., and Zwick, U. (2013) · 2013
Later among the works it cites.
Improved and generalized upper bounds on the complexity of policy iteration
Scherrer, B. (2013) · 2013
Later among the works it cites.
Markov decision processes: discrete stochastic dynamic programming
Puterman, M. L. (2014) · 2014
Later among the works it cites.
Approximate dynamic programming for two-player zero-sum markov games
Perolat, J., Scherrer, B., Piot, B., and Pietquin, O. (2015) · 2015
Later among the works it cites.
Approximate dynamic programming for two-player zero-sum markov games
Pérolat, J., Scherrer, B., Piot, B., and Pietquin, O. (2015) · 2015
Later among the works it cites.
Decentralized q-learning for stochastic teams and games
Arslan, G. and Yüksel, S. (2017) · 2017
Later among the works it cites.
Randomized linear programming solves the discounted Markov decision problem in nearly-linear running time
Original
Wang, M. (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.

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…