Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor

By Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick. 2010

179 citations recorded by the source corpus.

Ye [2011] showed recently that the simplex method with Dantzig’s pivoting rule, as well as Howard’s policy iteration algorithm, solve discounted Markov decision processes (MDPs), with a constant discount factor, in strongly polynomial time. More precisely, Ye showed that both algorithms terminate after at most O(mn1−γ log n1−γ) iterations, where n is the number of states, m is the total number of actions in the MDP, and 0 < γ < 1 is the discount factor. We improve Ye’s analysis in two respects. First, we improve the bound given by Ye and show that Howard’s policy iteration algorithm actually terminates after at most O(m1−γ log n1−γ) iterations. Second, and more importantly, we show that the same bound applies to the number of iterations performed by the strategy iteration (or strategy improvement) algorithm, a generalization of Howard’s policy iteration algorithm used for solving 2-player turn-based stochastic games with discounted zero-sum rewards. This provides the first strongly polynomial algorithm for solving these games, solving a long standing open problem. Combined with other recent results, this provides a complete characterization of the complexity the standard strategy iteration algorithm for 2-player turn-based stochastic games; it is strongly polynomial for a fixed discount factor, and exponential otherwise.

Subfields: Economics and Econometrics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Management Science and Operations Research

Citations in the corpus

Safe Policy Improvement by Minimizing Robust Baseline Regret (2016, background): “It is known that this class of RMDP problems can be solved in (strongly) polynomial time [4] and has also been solved efﬁciently in practice [9].”
Approximate Dynamic Programming for Two-Player Zero-Sum Markov Games (2015, background): “An optimal counter strategy against µ is any strategy ν satisfying vµ,ν = vµ.”
Action Robust Reinforcement Learning and Applications in Continuous Control (2019, methodology): “The Probabilistic Robust PI (PR-PI, Algorithm 1) is a two player PI scheme adjusted to solving a PR-MDP (e.g., Rao et al. (1973); Hansen et al. (2013)).”
RAAM: The Benefits of Robustness in Approximating Aggregated MDPs in Reinforcement Learning (2014, methodology): “RMDPs can be solved in polynomial time and the solution methods are practical (Kaufman and Schaefer, 2013; Hansen et al. , 2013).”
Primal-dual algorithms for discounted Markov decision processes (2015, background): “Collectively, the recent papers [7], [17], [8], [9], [15] have established that policy iteration runs in polynomial time if a certain input parameter (the discount factor) remains fixed across problem instances, but can run in exponential time if the discount factor is allowed to vary for problem in”
Provable Self-Play Algorithms for Competitive Reinforcement Learning (2020, background): “There is a long line of classical work since then on solving this problem (see e.g. Littman, 1994; 2001; Hu & Wellman, 2003; Hansen et al., 2013).”
Robust Markov Decision Processes (2013, unknown): “[11], Ye [29], Ye [30]).”
A Sharp Analysis of Model-based Reinforcement Learning with Self-Play (2020, background): “…are widely used to model multi-agent RL. Learning the Nash equilibria of Markov games has been studied in Littman (1994; 2001); Hu & Wellman (2003); Hansen et al. (2013); Lee et al. (2020), where the transition matrix and reward are assumed to be known, or in the asymptotic setting where the…”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “This stands in sharp contrast of turn-based games (Hansen et al., 2013; Jia et al., 2019; Sidford et al., 2019), in which each turn only involves constructing an UCB for one player.”
Near-Optimal Reinforcement Learning with Self-Play (2020, background): “Learning the Nash equilibria of Markov games has been studied in classical work [18, 19, 11, 10], where the transition matrix and reward are assumed to be known, or in the asymptotic setting where the number of data goes to infinity.”