# The Simple Strategy-Iteration Method is Strongly Polynomial for the Turn-Based Deterministic Forward Game

arXiv: https://arxiv.org/abs/2606.29568 · HTML: https://mlsanity.com/paper/2606.29568/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2026.

## Built on by (most cited first, 1 of 1)

- [Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes](https://mlsanity.com/paper/2610.02131/) (2026)

## Abstract (arXiv)

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(n6m4log4 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(n3m2log2 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.