Source-linked AI summary
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick
TL;DR
The paper addresses the complexity of policy and strategy iteration for discounted MDPs and 2TBSGs, including an open problem for strongly polynomial algorithms in the latter setting. It improves Ye’s analysis and establishes a strongly polynomial bound for strategy iteration in 2TBSGs with a fixed discount factor.
Problem
Policy and strategy iteration for discounted MDPs and 2TBSGs require complexity characterization, while polynomial-time algorithms remain open when the discount factor is part of the input or for non-discounted games.
Method
The paper improves Ye’s analysis of Howard’s algorithm and analyzes strategy iteration for 2TBSGs using profitable switches, which underlie the strategy iteration algorithm.
Results
The strategy iteration algorithm for 2TBSGs has a strongly polynomial bound for a fixed discount factor, resolving a long-standing open problem.
Takeaways & Limitations
For a fixed discount factor, policy and strategy iteration are strongly polynomial for MDPs and 2TBSGs, whereas they are exponential for non-discounted problems or when the discount factor is part of the input.
Takeaways & Limitations
Polynomial-time algorithms remain open when the discount factor is part of the input or in the non-discounted case.
Abstract
from arXiv · showhide
Ye showed recently that the simplex method with Dantzig 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(\frac{mn}{1-γ}\log(\frac{n}{1-γ}))$ 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(\frac{m}{1-γ}\log(\frac{n}{1-γ}))$ 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, resolving a long standing open problem.
1 Introduction
This paper studies discounted 2-player turn-based stochastic games and extends complexity results for policy iteration in MDPs. It improves Howard’s bound and proves a strongly polynomial bound for strategy iteration, addressing a long-standing open problem.
- MDPs model long-term sequential decisions in stochastic environments, while 2TBSGs extend this setting to two-player stochastic and adversarial environments.
- Howard’s policy iteration maintains and improves policies through profitable switches and was previously known to be strongly polynomial for fixed discount factors.Ye’s analysis used an LP formulation with duality and complementary slackness.
- The paper improves Ye’s analysis by reducing Howard’s iteration bound by a factor of n.The improvement requires only an additional well-known ingredient.
- The same O bound applies to strategy iteration, a generalization of Howard’s algorithm for solving 2TBSGs.The proof replaces Ye’s LP-based quantities with game-theoretic quantities and derives corresponding bounds directly.
- For fixed discount factors, policy and strategy iteration are strongly polynomial, whereas they are exponential for non-discounted problems or when the discount factor is part of the input.
- This result provides the first strongly polynomial algorithm for discounted 2TBSGs with a fixed discount factor and resolves a long-standing open problem.The paper develops the innovative bound in its strategy-iteration analysis.
2 2-player turn-based stochastic games
2-player turn-based stochastic games model discounted, stochastic, zero-sum interactions in which players alternate actions at state-controlled positions. Optimal positional strategy profiles exist, and the paper’s main result is a strongly polynomial algorithm for computing them when the discount factor is constant.
- Game model: 2TBSGs are discounted zero-sum games where states are controlled by one player, actions incur costs, and transitions are probabilistic.Player 1 minimizes expected total discounted cost, while player 2 maximizes it.
- Game model: A 2TBSG is specified by disjoint state sets for the two players, actions available at each state, and discount factor γ.The game uses n states and m actions, with probability and cost matrices representing transitions and action costs.
- Strategies and values: Positional strategies are deterministic and memoryless, and both players have optimal positional strategies.The value of a strategy profile is defined by the expected total discounted cost from each initial state.
- Strategies and values: Every 2TBSG has an optimal strategy profile, and all optimal profiles have the same value vector.Optimality is characterized by each player using an optimal counter-strategy against the other.
- Main result: The paper proves that an optimal strategy pair can be computed in strongly polynomial time when the discount factor is constant.This resolves the long-standing open problem of obtaining such an algorithm for 2TBSGs.
3 Basic results
The basic analysis transforms strategy profiles into value and modified-cost representations. These quantities characterize optimality and identify profitable switches that drive strategy iteration.
- Value representations: For every strategy profile π, the matrix I − γPπ is invertible and its inverse has nonnegative entries with positive diagonal entries.This matrix governs the discounted value calculations for a fixed profile.
- Value representations: The value vector vπ is the expected total discounted cost under π, while modified costs apply a potential transformation using vπ.The modified-cost vector is cπ = c − (J − γP)vπ.
- Optimality: Modified value vectors compare profiles through the identity vπ′ under modified costs equals vπ′ − vπ.This relation connects cost transformations to changes in strategy-profile values.
- Optimality: A strategy profile is optimal if and only if modified costs are nonnegative for player 1’s actions and nonpositive for player 2’s actions.The condition is (cπ)A1 ≥ 0 and (cπ)A2 ≤ 0.
- Improvement steps: A profitable switch changes a player’s action to improve the strategy, and such switches form the core of strategy iteration.They are closely related to simplex pivoting steps.
4 Value iteration
Value iteration applies a contraction operator that alternates minimization and maximization over actions. Its unique fixed point yields an optimal strategy profile through strategy extraction.
- Value iteration: T selects minimum action values at player 1 states and maximum action values at player 2 states.The strategy extraction operators choose the corresponding minimizing or maximizing actions.
- Value iteration: The value iteration operator T is a contraction with Lipschitz constant γ, so it has a unique fixed point v*.Banach’s fixed-point theorem establishes uniqueness.
- Optimality: The strategy extracted from the fixed point v* is an optimal strategy profile.The proof uses the modified-cost optimality condition.
- Algorithm: Value iteration repeatedly applies T until successive vectors differ by less than ε.The algorithm eventually terminates for every ε > 0, while the zero-tolerance sequence converges to v*.
- Convergence: For any input vector, value iteration with zero tolerance converges to the optimal value vector.The contraction property supplies the convergence guarantee.
5 Strategy iteration
Strategy iteration repeatedly computes an optimal counter-strategy and improves player 1’s strategy through profitable switches. Values decrease monotonically until an optimal profile is reached after finitely many iterations.
- Algorithm: Each strategy-iteration step computes player 2’s optimal counter-strategy and replaces player 1’s strategy with P1vπk.The replacement performs a collection of improving switches.
- Monotonicity: Strategy iteration produces a nonincreasing sequence of value vectors, with strict decrease before termination.The one-step guarantee is vπ0 ≥ vπ1.
- Termination: The algorithm terminates after finitely many iterations for every initial strategy.Before the final step, vk−1 > vk ≥ v*, and the final profile is optimal.
- Termination: At termination, consecutive value vectors equal the optimal value vector and consecutive strategy profiles are identical.The tie-breaking rule ensures πN−1 = πN.
- Relation to value iteration: Strategy iteration’s value sequence is related to value iteration, with the strategy-iteration values bounded by corresponding value-iteration values.This comparison extends known MDP relations to the two-player case.
6 Strongly polynomial bound
The paper establishes a strongly polynomial iteration bound for strategy iteration in discounted 2-player turn-based stochastic games. The proof uses value comparisons among strategy profiles to show that actions eventually disappear from later strategies, limiting the total number of iterations.
- The analysis compares strategy profiles with ordered value vectors and tracks actions selected by maximum local improvement.The supporting lemmas establish value monotonicity and constrain how selected actions can recur.
- The proof analyzes the sequence of player 1 strategies generated from an arbitrary initial strategy using L = log 1/γ.Every strategy has an action absent from all sufficiently later strategies.
- Each strategy in a suitably spaced subsequence contains an action that never appears again later.Since there are only m actions, this yields the global iteration bound.
- The strategy-iteration algorithm terminates with an optimal strategy after at most (m + 1)(1 + log 1/γ) iterations.The bound holds from any initial strategy.
7 Concluding remarks
For a fixed discount factor, strategy iteration is strongly polynomial for 2-player turn-based stochastic games. The broader polynomial-time problem remains open when the discount factor is part of the input or when the games are undiscounted.
- Strategy iteration is strongly polynomial for 2TBSGs with a fixed discount factor.
- For non-discounted 2TBSGs or games where the discount factor is part of the input, strategy iteration is exponential.This contrasts with the fixed-discount setting established in the paper.
- Polynomial-time algorithms for these variable-discount or non-discounted cases remain an open problem linked to Simple Stochastic Games, Mean Payoff Games, and Parity Games.The paper notes possible consequences for complexity theory and automatic verification.
- The authors suggest that extending polynomial-time methods to the two-player case may be informed by the analysis developed here and by related interior-point approaches.