The Simple Strategy-Iteration Method is Strongly Polynomial for the Turn-Based Deterministic Forward Game
This work provides the first strongly polynomial guarantee for strategy iteration on a nontrivial class of games, benefiting algorithmic game theory and reinforcement learning.
The paper proves that the simple strategy-iteration method is strongly polynomial for Turn-Based Deterministic Forward Games (TBDFGs), terminating in at most O(n^6 m^4 log^4 n) pivot steps, and proposes a structure-aware algorithm that improves the bound to O(n^3 m^2 log^2 n).
We study Turn-Based Deterministic Forward Games (TBDFGs), the subclass of turn-based deterministic zero-sum games in which no directed cycle contains actions controlled by both players. This forward condition is strictly weaker than acyclicity: recurrent behavior may be arbitrarily rich within one player's states, while mixed-player feedback cycles are excluded. Our main contribution separates two algorithmic consequences of this structure. First, we analyze the simple strategy-iteration method of [11,14], a generic method for TBSGs whose execution neither tests for nor uses the TBDFG property. We prove that this structure-oblivious algorithm nevertheless has a strongly polynomial guarantee on every TBDFG. In particular, it terminates after at most $O(n^6m^4\log^4 n)$ simplex pivot steps. Thus, the forward property acts as a structural certificate for convergence even when the algorithm is not informed that the input has this property. Second, when the TBDFG structure is known in advance, a backward SCC propagation algorithm is proposed that solves a sequence of deterministic-MDP subproblems and improves the bound to $O(n^3m^2\log^2 n)$ simplex pivot steps. Together, these results show that forward structure both regularizes the convergence of a general strategy-iteration method and supports a sharper structure-aware algorithm.