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

DOI10.1145/2432622.2432623zbMath1281.91019arXiv1008.0530OpenAlexW2141076336MaRDI QIDQ5395701

Peter Bro Miltersen, Thomas Dueholm Hansen, Uri Zwick

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1008.0530

zbMATH Keywords

Markov decision processes policy iteration strongly polynomial algorithms strategy iteration turn-based stochastic games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Stochastic games, stochastic differential games (91A15) Markov and semi-Markov decision processes (90C40)

Related Items (17)

A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations ⋮ The greedy strategy for optimizing the Perron eigenvalue ⋮ Improved and Generalized Upper Bounds on the Complexity of Policy Iteration ⋮ The stochastic shortest path problem: a polyhedral combinatorics perspective ⋮ Continuous Positional Payoffs ⋮ Towards solving 2-TBSG efficiently ⋮ Unnamed Item ⋮ Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming ⋮ Improved bound on the worst case complexity of policy iteration ⋮ On satisficing in quantitative games ⋮ Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes ⋮ Efficient computation of a canonical form for a matrix with the generalized P-property ⋮ A non-iterative algorithm for generalized pig games ⋮ The operator approach to entropy games ⋮ On the reduction of total‐cost and average‐cost MDPs to discounted MDPs ⋮ Multi-agent reinforcement learning: a selective overview of theories and algorithms ⋮ Multiply Accelerated Value Iteration for NonSymmetric Affine Fixed Point Problems and Application to Markov Decision Processes

This page was built for publication: Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor