- 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.
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 γ. 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 γ 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+ as the last iterate before the next Player~1 cycle is created, or as the terminal iterate if the algorithm terminates first. Since k′ is arbitrary beyond the stated bound, the exclusion holds for the same action a or cycle C at every such iterate through 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π, where Aπ is the submatrix of A formed by selecting one column per state according to π, in state order.