acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 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 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.

Primary area:
optimization
Keywords:
Simplex Method, Strategy-Iteration Method, Turn-Based Deterministic Game, Markov Decision Problem, Linear Programming, Dynamic Programming, Strongly Polynomial Time

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_h1X6OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper analyzes an existing strategy-iteration algorithm for two-player deterministic discounted games. The algorithm changes one action of Player 1 and then recomputes Player 2’s optimal response. The paper shows that for Forward Games, that is games where cycles only concern one of the player (and the other player does not control any node in the cycle), the bound on the number of pivot is strongly polynomial, i.e. independent on the discount Gamma<1.

Critical strengths

The bound removes dependence on 1/(1-Gamma), which is valuable when Gamma is close to 1.

Critical weaknesses

W1) The practical relevance of the Forward game is dubious. The examples provided by the authors of forward games are acyclic 2 player games (chess, go...).

W2) Further, forward games are pretty close to acyclic games, they could probably be reduced to an acyclic game.

W3) Last, one could imagine that an algorithm specifically devoted to acyclic (or forward) game would have even btter complexity. Is there any advantage into consider this particuler algorithm?

Questions for authors

Q1. Can you provide relevant TBDFG (=forward games) which are interesting and not acyclic?

Q2. In Appendix B.3, I am not sure how the argument excluding an action at a later iterate extends to all subsequent iterates before a new Player 1 cycle is created, as required in Lemmas 9–10. Could the authors clarify this step?

Q3. Page 1, line 051: In the formula for the total number of actions, the summation index is s, so the summand k_i should be k_s.

Q4. Page 5, line 257: A = I - Gamma P is dimensionally inconsistent for the full n-by-m action matrix A. The identity should refer to the policy submatrix: A_pi = I - Gamma P^pi.

1 comment

We would like to thank you for taking the time and effort to review our paper and provide insightful comments. We have revised our manuscript according to your comments. Major changes to the manuscript are highlighted in blue. Below are our responses to the weaknesses and questions you mentioned. We hope that our responses and revision successfully address your comments. For a clearer reference, we will also include your original comments. Where a reference has changed, we give the revised label or location in parentheses.

Critical Weaknesses:

W1: The practical relevance of the Forward game is dubious. The examples provided by the authors of forward games are acyclic 2 player games (chess, go...).

Response: Thank you for this comment. We have added a robust MDP for equipment maintenance in Appendix A.

W2: Further, forward games are pretty close to acyclic games, they could probably be reduced to an acyclic game.

Response: Thank you for your insightful comment. Indeed, contracting the strongly connected components (SCCs) of a TBDFG yields an acyclic graph and determines the order in which the components can be solved. Computing the values within each component still requires solving a one-player discounted game, which can be an arbitrary strongly connected deterministic MDP. Thus, even after mixed-player cycles are excluded, choosing among single-player cycles remains a substantive optimization problem. SCC contraction alone therefore does not reduce the original game to an ordinary acyclic game solvable by backward induction. The algorithmic distinction is also discussed in our response to W3 below.

W3: Last, one could imagine that an algorithm specifically devoted to acyclic (or forward) game would have even btter complexity. Is there any advantage into consider this particular algorithm?

Response: Thank you for your comment. We agree that solving the SCCs of the game in reverse topological order yields a strongly polynomial algorithm for TBDFGs with a better worst-case pivot bound.

However, our interest in simple strategy iteration (SSI) is algorithmic. The advantage of this algorithm is that it applies to general discounted TBSG and is known to be strongly polynomial for each fixed discount factor γ\gamma. It requires no knowledge of the SCC structure and applies without modification when mixed-player cycles are present. The SCC-based algorithm, by comparison, relies on each component being controlled by one player so that it can be solved as a deterministic MDP. The question we study is whether SSI itself admits a strongly polynomial pivot bound when γ\gamma is part of the input. We prove that it does for TBDFGs, even though SSI never tests for or exploits the forward structure. We have clarified this distinction in the revised manuscript.

Questions For Authors:

Q1: Can you provide relevant TBDFG (=forward games) which are interesting and not acyclic?

Response: Thank you for this comment. We have added a robust equipment-maintenance example formulated as a robust MDP to Appendix A of the revised paper to illustrate the role of single-player cycles.

Q2: In Appendix B.3, I am not sure how the argument excluding an action at a later iterate extends to all subsequent iterates before a new Player 1 cycle is created, as required in Lemmas 9–10. Could the authors clarify this step?

Response: Thank you for pointing this out. We have clarified this step in this revision (formerly Appendix B.3, now the proof of Lemma 7 in Section 2.2). Fix k+k^+ as the last iterate before the next Player~1 cycle is created, or as the terminal iterate if the algorithm terminates first. Since k′k′ is arbitrary beyond the stated bound, the exclusion holds for the same action a or cycle C at every such iterate through k+k^+ and hence extends to all subsequent iterates.

Q3: Page 1, line 051: In the formula for the total number of actions, the summation index is s, so the summand k_i should be k_s.

Response: Thank you for pointing this out. We have fixed this in the revision.

Q4: Page 5, line 257: A = I - Gamma P is dimensionally inconsistent for the full n-by-m action matrix A. The identity should refer to the policy submatrix: A_pi = I - Gamma P^pi.

Response: Thank you for pointing this out. We have corrected Proposition~1(v) to state Aπ=I−γPπA_\pi=I-\gamma P^\pi, where AπA_\pi is the submatrix of AA formed by selecting one column per state according to π\pi, in state order.

Reviewer_7qmUOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces Turn-Based Deterministic Forward Games (TBDFGs), the subclass of turn-based deterministic zero-sum discounted games in which no directed cycle of the game graph contains actions of both players. Cycles are therefore allowed, but only within the states of a single player. The authors analyze the existing simple strategy-iteration algorithm for turn-based stochastic games (Algorithm 1, identical to Algorithm 1 of Jia et al. (2020)). The main result (Theorem 1) is that on TBDFGs this algorithm terminates after O(n^6 m^4 log^4 n) simplex pivots for any uniform discount factor, i.e. it is strongly polynomial, even though the algorithm neither detects nor uses the forward property.

Minor comments (not decisive for my recommendation):

Lines 51-52: It should read sum_{s=1}^{n} k_s.

Definitions 1 to 4 are stated for TBDGs, but the text then suddenly switches to TBSGs. Please use one class consistently or explain the switch.

Line 89: the "cost-to-go value" is used without having been defined.

Literature and background (Section 1.1): author names are repeatedly given twice, once in the text and again in the citation, e.g. "Papadimitriou and Tsitsiklis analyzed the complexity of ... Papadimitriou & Tsitsiklis (1987)"

Line 341: notation inconsistency between pi^* and pi_. The optimal profile is written pi^ (e.g. lines 95 and 363), while here and in Proposition 1(vi) (line 262) the players' components are written with a subscript, pi_^1 and pi_^2. Please use one convention throughout.

Critical strengths

The paper is clearly written and the results appear correct. I checked the proofs and am convinced that they work.

The bound holds for a generic, structure-oblivious algorithm. The analysis shows that an existing strategy-iteration method is strongly polynomial on TBDFGs without being told that the input has this structure. This is the main point in the paper's favour, although (see Weaknesses) I do not find it sufficient on its own for acceptance.

Critical weaknesses

Limited contribution and novelty: The algorithm is not new: Algorithm 1 is exactly the simple strategy-iteration algorithm already proposed for general TBSGs (Jia et al., 2020), as the authors acknowledge themselves (lines 317-320: "the novelty here is not a new pivot rule"). The contribution therefore consists only of a complexity analysis for a new subclass, and I do not find the TBDFG class interesting. Excluding all cycles that involve both players removes most of what makes two-player games difficult, and the paper does not convincingly show that this restricted class is of independent interest. Overall, the substance of the contribution seems too weak for ICLR. This is the main reason for my recommendation.

Balance and presentation of the paper: Of the nine pages of main text, roughly the first six recap known material (definitions, known lemmas, the LP formulation, and the literature review); Section 2, the only new material, starts at line 279 and occupies less than three pages, and part of it (Algorithm 1 and Remark 1) is again restated from prior work. In addition, since the game is deterministic, the transition probabilities play no role, yet the paper uses the full probabilistic MDP/TBSG notation and terminology throughout. Stating the problem directly in graph terms (each action is an edge to a successor state) would make the paper considerably easier to read and would leave space for the actual contribution.

Questions for authors

Beyond acyclic games, which natural problems are TBDFGs but not acyclic? The motivating board games (Chess, Go) do not seem to need the single-player cycles that distinguish TBDFGs from acyclic games. Concrete examples where such cycles are essential would strengthen the case that the class is of interest.

Which parts of the proof are genuinely new relative to Post & Ye (2015) and Hansen et al. (2013), and which are direct adaptations? A short statement of what fails when the one-player argument is applied directly, and how this is overcome, would help to assess the technical contribution.

Suggestion: Since the transition probabilities play no role, have you considered presenting the model purely in graph terms? This would shorten the preliminaries considerably.

3 comments

We would like to thank you for taking the time and effort to review our paper and provide insightful comments. We have revised our manuscript according to your comments. Major changes to the manuscript are highlighted in blue. Below are our responses to the weaknesses and questions you mentioned. We hope that our responses and revision successfully address your comments. For a clearer reference, we will also include your original comments. Where a reference has changed, we give the revised label or location in parentheses.

Minor comments (not decisive for my recommendation):

Lines 51-52: It should read sum_{s=1}^{n} k_s.

Definitions 1 to 4 are stated for TBDGs, but the text then suddenly switches to TBSGs. Please use one class consistently or explain the switch.

Line 89: the "cost-to-go value" is used without having been defined.

Literature and background (Section 1.1): author names are repeatedly given twice, once in the text and again in the citation, e.g. "Papadimitriou and Tsitsiklis analyzed the complexity of ... Papadimitriou & Tsitsiklis (1987)"

Line 341: notation inconsistency between pi^* and pi_. The optimal profile is written pi^ (e.g. lines 95 and 363), while here and in Proposition 1(vi) (line 262) the players' components are written with a subscript, pi_^1 and pi_^2. Please use one convention throughout.

Response: Thank you for pointing these out. We corrected the action count to m=∑s=1nksm=\sum_{s=1}^{n}k_s, used TBDG consistently in the definitions and value discussion, and defined vsv_s immediately after its introduction as the total discounted cost incurred when play starts at ss and follows π\pi. We also removed the repeated author names in Section~1.1 and standardized the optimal strategy profile as π∗=(π∗1,π∗2)\pi_*=(\pi_*^1,\pi_*^2) throughout the paper.

Our response continues as follows:

Critical Weaknesses:

W1: Limited contribution and novelty: The algorithm is not new: Algorithm 1 is exactly the simple strategy-iteration algorithm already proposed for general TBSGs (Jia et al., 2020), as the authors acknowledge themselves (lines 317-320: "the novelty here is not a new pivot rule"). The contribution therefore consists only of a complexity analysis for a new subclass, and I do not find the TBDFG class interesting. Excluding all cycles that involve both players removes most of what makes two-player games difficult, and the paper does not convincingly show that this restricted class is of independent interest. Overall, the substance of the contribution seems too weak for ICLR. This is the main reason for my recommendation.

Response: Thank you for your comment. Mixed-player cycles are one source of difficulty in the longstanding open question of whether general discounted TBDGs admit a strongly polynomial algorithm. The simple strategy iterations (SSI) is a promising starting point for algorithm design because it is strongly polynomial for two-player games with fixed γ\gamma (Jia et al., 2020), and its one-player deterministic counterpart is strongly polynomial uniformly over all γ∈(0,1)\gamma\in(0,1) (Post and Ye, 2015). This motivates the question we study: does SSI retain its discount-independent guarantee when each cycle is controlled by a single player? We prove that it does. The proof requires a substantially different analysis because a single Player 1 pivot can trigger several Player 2 pivots. These results provide a foundation for the general problem by identifying precisely which progress estimates depend on a cycle surviving the opponent's response. We have also added a robust equipment-maintenance example formulated as a robust MDP in Appendix A, drawing on Bellman’s equipment-replacement model (1955) and Iyengar’s framework for robust MDPs (2005).

W2: Balance and presentation of the paper: Of the nine pages of main text, roughly the first six recap known material (definitions, known lemmas, the LP formulation, and the literature review); Section 2, the only new material, starts at line 279 and occupies less than three pages, and part of it (Algorithm 1 and Remark 1) is again restated from prior work. In addition, since the game is deterministic, the transition probabilities play no role, yet the paper uses the full probabilistic MDP/TBSG notation and terminology throughout. Stating the problem directly in graph terms (each action is an edge to a successor state) would make the paper considerably easier to read and would leave space for the actual contribution.

Response: Response: Thank you for this suggestion. We moved the background on strategies and optimality, including the unscaled LP formulation, to Appendix C and brought the proofs of the progress and action-elimination bounds into the main text. We retain Algorithm 1 and Remark 1 to specify the pivot rule and best-response step whose complexity we analyze. After considering the graph-based presentation, we chose to retain the transition-matrix notation for consistency with prior work. In a TBDG, each action is a directed edge to a unique successor, and its transition vector is simply the unit vector for that successor. This notation lets us use the value and flux identities from prior strategy-iteration analyses directly when measuring progress over a full iteration.

Questions For Authors:

Q1: Beyond acyclic games, which natural problems are TBDFGs but not acyclic? The motivating board games (Chess, Go) do not seem to need the single-player cycles that distinguish TBDFGs from acyclic games. Concrete examples where such cycles are essential would strengthen the case that the class is of interest.

Response: Thank you for your comment. We agree that Chess and Go do not illustrate the role of single-player cycles. We have added a robust equipment-maintenance example formulated as a robust MDP in Appendix~A of the revised paper to address this point.

Q2: Which parts of the proof are genuinely new relative to Post & Ye (2015) and Hansen et al. (2013), and which are direct adaptations? A short statement of what fails when the one-player argument is applied directly, and how this is overcome, would help to assess the technical contribution.

Response: Thank you for your comment. Post and Ye bound progress after a single pivot. In Algorithm 1, Player 2's subsequent best response can change the flux through the entering action, so their bound does not apply to the full iteration. In our analysis, extending the one-player argument to a full SSI iteration requires both the forward property, which lets us track newly created Player 1 cycles across multiple pivots within that iteration, and the best-response conditions, which control Playe 2's contribution to the change in value.

Q3: Suggestion: Since the transition probabilities play no role, have you considered presenting the model purely in graph terms? This would shorten the preliminaries considerably.

Response: Thank you for this suggestion. After carefully considering this suggestion, we chose to retain the transition-matrix notation for consistency with prior work. In this setting, each action's transition vector simply identifies its unique successor. This notation also lets us use the value and flux identities from prior analyses directly. Post and Ye (2015, Section~2) adopt the same convention for deterministic MDPs.

Reviewer_9rc3OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces a subclass of games on graphs called turn-based deterministic forward games (TBDFGs). They are those special turn-based discounted deterministic two-player games on graphs (TBDG) played on the vertices of a digraph whose strongly connected components are each controlled by a single player. Note that TBDGs are also known as discounted payoff games (DPGs), see e.g. Fijalkow 'Games on graphs'.

They show that the 'simple strategy-iteration' algorithm from Jia et al can solve these games in strongly polynomial time. This algorithm is the two-player equivalent of an algorithm by Post and Ye, which in turn is essentially applying the simplex method with Dantzig's rule to the standard LP formulation of a discounted Markov decision process. The algorithm by Post and Ye was previously shown to be strongly polynomial for one-player TBDGs.

While the complexity of general two-player TBDGs remains unclear, the paper shows that the algorithm runs in strongly polynomial time on TBDFGs. The argument follows the same structure as the paper by Post and Ye, extending their arguments from one-player TBDGs to TBDFGs: they show that every O(n^2mlog n) iterations a new player 1 cycle is created, and that every O(n log n) cycle creations an edge is eliminated from being either in a cycle or in a strategy altogether. Because every iteration takes strongly polynomial time (as it is solving a one-player TBDG), and there are only m edges to be eliminated, the algorithm terminates in strongly polynomial time.

Critical strengths
  • The paper shows that a two-player subclass of TBDGs / DGPs can be solved in strongly polynomial time. It mostly extends the complexity analysis of an existing (rather basic) algorithm from the one-player setting using a suitably chosen restriction of the game structure. This is partially interesting from a complexity-theoretic point of view and may also have applications for modeling interesting game classes.

  • The presentation of the arguments is technical but reasonably clear.

Critical weaknesses
  • While the authors present a strongly polynomial algorithm for solving their class of games, this may already follow more easily from the existence of such an algorithm by Post and Ye that solves one-player games in strongly polynomial time: one could solve the bottom SCC of the two-player game with Post-Ye's algorithm, then use the obtained values to solve the bottom SCC of the remaining game, and so on. This would also be much faster than using simple strategy-improvement, and the authors do not explain what the advantage of using simple strategy-improvement is. The paper does not seem to introduce any substantial new techniques compared to the paper by Post and Ye.

  • The applicability of the class of games is not sufficiently clarified. The elaboration in the main text was too vague, and I am not sure if I understood the elaboration in the appendix correctly.

Questions for authors
  • Which games of interest can be modeled as TBDFGs and hence be solved in strongly polynomial time? In which sense could then chess be solved in strongly polynomial time?

  • Suggestion: It may help the presentation to check with existing results in the above-mentioned book 'Games on graphs'; in particular Lemma 3 and 4 are rather standard.

1 comment

We would like to thank you for taking the time and effort to review our paper and provide insightful comments. We have revised our manuscript according to your comments. Major changes to the manuscript are highlighted in blue. Below are our responses to the weaknesses and questions you mentioned. We hope that our responses and revision successfully address your comments. For a clearer reference, we will also include your original comments. Where a reference has changed, we give the revised label or location in parentheses.

Critical Weaknesses:

W1: While the authors present a strongly polynomial algorithm for solving their class of games, this may already follow more easily from the existence of such an algorithm by Post and Ye that solves one-player games in strongly polynomial time: one could solve the bottom SCC of the two-player game with Post-Ye's algorithm, then use the obtained values to solve the bottom SCC of the remaining game, and so on. This would also be much faster than using simple strategy-improvement, and the authors do not explain what the advantage of using simple strategy-improvement is. The paper does not seem to introduce any substantial new techniques compared to the paper by Post and Ye.

Response: Thank you for your comment. We agree that solving the SCCs in reverse topological order yields a strongly polynomial algorithm for TBDFGs with a better worst-case pivot bound.

However, our interest in simple strategy iteration (SSI) is algorithmic. The advantage of this algorithm is that it applies to general discounted TBSG and is known to be strongly polynomial for each fixed discount factor γ\gamma. It requires no prior knowledge of the SCC structure and applies without modification when mixed-player cycles are present. The SCC-based algorithm, by comparison, relies on each component being controlled by one player so that it can be solved as a deterministic MDP. The question we study is whether SSI itself admits a strongly polynomial pivot bound when γ\gamma is part of the input. We prove that it does for TBDFGs, even though SSI never tests for or exploits the forward structure. We have clarified this distinction in the revised manuscript.

As for the new techniques introduced, we extend Post and Ye’s path-and-cycle analysis. In their deterministic MDP, each iteration consists of a single pivot. In SSI, a Player 1 pivot is followed by a full best response from Player 2, which may require several additional pivots. The challenge is to quantify how much improvement survives that response. Thus, although our proof follows Post and Ye’s overall framework, accounting for Player 2’s best response after each Player 1 pivot requires a substantially different analysis from the single-pivot argument used for deterministic MDPs.

W2: The applicability of the class of games is not sufficiently clarified. The elaboration in the main text was too vague, and I am not sure if I understood the elaboration in the appendix correctly.

Response: Thank you for this comment. We have revised the discussion and added a robust equipment-maintenance example formulated as a robust MDP in Appendix A to illustrate how TBDFGs arise in practice.

Questions For Authors:

Q1: Which games of interest can be modeled as TBDFGs and hence be solved in strongly polynomial time? In which sense could then chess be solved in strongly polynomial time?

Response: We have revised Appendix A to clarify which games can be modeled as TBDFGs and added a robust equipment-maintenance example with recurring maintenance decisions in a robust MDP. For chess, the guarantee is strongly polynomial in nn and mm, where nn is the number of nodes in the explicitly expanded game tree and mm is the total number of legal move edges in that tree.

Q2: Suggestion: It may help the presentation to check with existing results in the above-mentioned book 'Games on graphs'; in particular Lemma 3 and 4 are rather standard.

Response: Thank you for pointing this out. We agree that Lemmas 3 and 4 (now Lemmas 1 and 2) are standard. We include them for completeness and have added the reference in the revised manuscript. From Lemma 5 (now Lemma~3) onward, we build on Post and Ye’s path-and-cycle framework for TBDFG, extending the framework to two-player SSI requires a substantially different analysis because a single Player 1 pivot may trigger several Player 2 pivots. We must show that the cycle and flux estimates needed to quantify progress remain valid after Player 2’s full best response. This requirement makes our analysis substantially different from existing work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.