We thank you for taking the time to review the paper. We address your questions below.

Response to questions.

Q1: multiplicity-based approach. The multiplicity approach relies on bounding the multiplicity $\bar{d}$ of $1$ as a root of the polynomial $\Delta(\alpha)$ representing the difference of value functions (since this multiplicity leads to a bound on the minimal value of $d$ satisfying that any $d$-sensitive optimal strategy is also Blackwell optimal). A known result shows that given a polynomial $P = \sum_{k=0}^{d} c_k X^k$ of degree $d$ such that $\max_{k} |c_k| \leq 1$, then this multiplicity is bounded by $O\left(\sqrt{d(1+\log(c_0))}\right)$ (this is in lines 567 - 569 of our paper).

For deterministic games, we can ensure that $|c_0|$ remains small (using Lemma 3.1 in our submission), allowing us to obtain the meaningful bound $\bar{d} = O(\sqrt{n})$ by this technique. However, for general stochastic instances, the magnitude of $c_0$ can grow as $O(n 4^n M^n)$ (with $M$ = denominator in the transitions probabilities and $n$ = number of states). This leads to a vacuous bound ($\bar{d} = \Omega(n)$) that is no better than existing ones (it is known that any $n-2$-sensitive optimal strategy is also Blackwell optimal). This is why the multiplicity approach breaks down for general games.

Q2. On our three different approaches. We found that our three proof techniques (Lagrange, Mahler, Multiplicity) each leverage different aspects of the problem, with different strengths and weaknesses:

• The Lagrange bound can use the fact that some coefficients are zero (which is useful for the analysis of d-sensitive thresholds as in Theorem 3.3) and always holds.
• The Mahler bound is stronger than Lagrange in some regimes (ex: $W = O(1)$) but not in others ($W = \exp(\Theta(n))$).
• The multiplicity analysis provides new results for MDPs and deterministic games (a better bound on $d$ such that d-sensitive strategies are also Blackwell optimal), independent of the problem of bounding the Blackwell thresholds

As evident from the previous items, there are several ingredients entering into the problems that we address in this paper. In particular, our bounds depend on:

• the number of states and the “granularity” of the games (integers $W$ and $M$ in our paper)
• the deterministic or stochastic character of the Markov chains induced by strategies
• the multiplicity of $1$ as a root of some polynomials $\Delta(\alpha)$ associated with the games

Additionally, we focus on several different objective functions (Blackwell optimality, d-sensitive optimality for $d=-1,...,n-2$). While a unifying theory is desirable, we found no single method that yields uniformly tight bounds across all these variables. Instead, our results map out which tool performs best in each regime (as highlighted for instance in lines 120 - 126 or in Table 3).

Q3. From unichain to multichain. The unichain assumption allows us to neatly relate conditions on the value function differences $v^{\sigma*,\tau*}(\alpha) - v^{\sigma*,\tau}(\alpha)$ with some conditions on the polynomial $\Delta(\alpha)$ with a manageable structure (lines 636 - 639 on page 17, in Appendix C). More specifically, under the unichain assumption, we can write $\Delta(\alpha) = R(\alpha) \cdot (v^{\sigma*,\tau*}(\alpha) - v^{\sigma*,\tau}(\alpha))$ with $R(\alpha) = (1-\alpha)^{2} * D(\alpha)$ and $D(1) \neq 0$. From this, we can reformulate the definition of the d-sensitive optimality (Equation (2) in Definition 2.2 on page 5): $\lim_{\alpha \rightarrow 1} (1-\alpha)^{d} (v^{\sigma*,\tau*}(\alpha) - v^{\sigma*,\tau}(\alpha) )= 0$ as some conditions on the polynomial $\Delta(\alpha)$: $\lim_{\alpha \rightarrow 1} (1-\alpha)^{d-2} \Delta(\alpha)= 0.$ Controlling this polynomial $R(\alpha)$ in all generality (for multichain models) is the main difficulty in removing the unichain assumption. Generalizing to the multichain settings would require a finer characterization of the spectral properties of the induced Markov chains under arbitrary strategies, which is a challenging open problem. We will clarify this further and make it more explicit in our revised manuscript.

Q4. On hard game instances. This is a fundamental question, which we list as a next step in our open questions subsection (page 9), where we discuss the importance of finding a lower bound on $\alpha_{\sf bw}$ (and therefore a matching instance). Our analysis suggests that the hardest instances should be stochastic and multichain and should involve intricate transition structures. More fundamentally, our techniques allow us to relate questions about stochastic games/MDPs (how close to $1$ can $\alpha_{\sf bw}$ be, for a stochastic game with $n$ states, integer rewards bounded by $W$, and transitions probabilities with common denominator $M$?) with questions from polynomials and algebraic number theory (how close to $1$ can a real root of a polynomial $P$ be, if $P$ has degree $n$ and its coefficients are bounded by $H$?). Thus, our approach provides a stronger connection between games and the rich literature on polynomials, which we plan to further exploit for demonstrating lower bounds.

On limitations. We acknowledge the methodological nature of our work. However, we believe our work marks a substantial step forward in the analysis of long-term decision-making: we significantly improve the best-known bound for the Blackwell threshold by reducing the exponent by a full order of magnitude, and we provide the first explicit bounds for the d-sensitive thresholds. To achieve this, we introduce new analytical tools—most notably, the use of Mahler measure bounds, which had not been previously applied in this setting, and a multiplicity-based approach that sharpens our understanding of when d-sensitive strategies become Blackwell optimal. These techniques go beyond prior methods and offer tighter, more general bounds across a variety of regimes.

More broadly, our results contribute to a fundamental and long-standing question in reinforcement learning and game theory: how farsighted must an agent be to act optimally in the long run? This question underpins many real-world applications, from planning under uncertainty to multi-agent systems, and sharp answers have been elusive. Our paper makes concrete progress in this direction. We view this as an essential step toward more principled long-horizon decision-making in learning systems. It is also worth emphasizing that methodological contributions to game theory (broadly defined) have been a substantial contingent of the papers accepted at ML conferences in recent years, even attracting awards, e.g., best-paper award at AAAI 2023 for mean-payoff robust MDPs [0] and ICML 2023 [1], or spotlights at NeurIPS 2022 [2,3]. These kinds of methodological advances form the backbone of many prominent successes that made the headlines in the newspaper recently, such as Deepmind solving Go [4] and CMU solving Poker [5], and even reinforcement learning-based fine-tuning of LLMs [6].

Conclusion

We hope that we addressed your main comments. We will refine the paper based on your inputs and our response to your questions. We are looking forward to your new feedback and evaluation/score, and we remain at your disposal through the rebuttal process in case you have further questions.

References

[0] Wang, Y., Velasquez, A., Atia, G., Prater-Bennette, A., & Zou, S.. Robust average-reward markov decision processes. AAAI 2023.

[1] Fiegel, C., Ménard, P., Kozuno, T., Munos, R., Perchet, V., & Valko, M.. Adapting to game trees in zero-sum imperfect information games. ICML 2023.

[2] Cai, Y., Oikonomou, A., & Zheng, W.. Finite-time last-iterate convergence for learning in multi-player games. NeurIPS 2022.

[3] Anagnostides, I., Farina, G., Kroer, C., Lee, C. W., Luo, H., & Sandholm, T. Uncoupled learning dynamics with $o (\log t)$ swap regret in multiplayer games. NeurIPS 2022.

[4] Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., ... & Hassabis, D.. Mastering the game of Go with deep neural networks and tree search. Nature 2016. [5] Brown, N., & Sandholm, T.. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science 2018.

[6] Munos, R., Valko, M., Calandriello, D., Azar, M. G., Rowland, M., Guo, Z. D., ... & Piot, B. (2023). Nash learning from human feedback. arXiv preprint arXiv:2312.00886, 18.

We thank you for your time reviewing our paper and for your positive evaluation.

Response to your questions. Both of your questions pertain to the tightness of the bounds that we obtain. Our conjecture is that the bounds based on Mahler measures are tight, at least for deterministic games. More precisely, we believe that there exist some game instances where the Blackwell threshold $\alpha_{\sf bw}$ is exponentially close to $1$, with a gap close to the bound of Theorem 1.3, but we do not have a proof of this fact yet.

This conjecture is based on the known tightness of the Mahler bound for polynomials. It is shown in Dubickas~[0] that there exist real polynomials that have complex roots exponentially close to $1$. However, whether this is true for real roots remains an open question. Indeed, in the work of Dubickas and others, the existence of complex roots close to one is obtained by a coarse control of the ``Newton polygons’’, depending on the log of moduli of the coefficients of candidate polynomials. Showing the existence of real roots close to $1$ requires a finer control (of the log of moduli of the coefficients, and also on the sign), which we do not have yet because some of the candidate polynomials are obtained in a non-explicit way (as an application of a lemma of Siegel on the existence of small integer solutions of underdetermined linear systems). Whether the bounds remain tight in the case of multichain stochastic games is also an open question. We highlight this as an important future direction of research in our open questions subsection on page 9.

We do agree that exploring explicit game instances where the thresholds are near to $1$ would be valuable and give more insight on d-sensitive and Blackwell optimality. Constructing such examples—whether worst-case, drawn from real-world scenarios, or sampled at random—is an exciting avenue we plan to investigate further.

[0] Dubickas, A. (1998). On algebraic numbers close to 1. Bulletin of the Australian Mathematical Society, 58(3), 423-434.

Conclusion: We hope that we addressed your main comments, and we thank you again for your positive score. We will refine the paper's presentation based on your input. We remain at your disposal throughout the rebuttal process in case you have further questions.

Thank you for the response. My attitude remains positive for the paper.

We would like to thank you for taking the time to review our paper and for your constructive comments. We will revise our manuscript to fix any typos/writing issues (e.g. the brackets issues that you mentioned) and use the extra space to add a table with notations/assumptions.

Response to your questions:

1. Fit for NeurIPS.

We believe that the topic of our work makes our paper a good fit for NeurIPS; more generally, the problem of designing methods for long-term decision-making with strategic agents has broad relevance to the machine learning community.

Indeed, repeated games, MDPs, and their generalizations (like stochastic games) form the backbone of many AI systems, including prominent successes that made the headlines in the newspaper recently such as Deepmind solving Go [4] and CMU solving Poker [5], and even reinforcement learning-based fine-tuning of LLMs [6]. The specific concepts we study (Blackwell optimality and d-sensitive optimality) are directly connected with how long-term reward is modeled and optimized, a question at the heart of reinforcement learning.

From an academic standpoint, this is exemplified by the number of recent papers at NeurIPS/ICML//AAAI around the following topics: Markov games, robust MDPs, repeated games in extensive-forms, and even simpler setups such as two-player zero-sum games have all attracted a lot of attention in the last years. In fact, papers focusing on these topics even received some prizes at these conferences:

• a recent paper on average-reward robust MDPs (a setup equivalent to stochastic games) won a best paper award at AAAI 2023 [0];
• two papers on multiplayer games were oral presentations at NeurIPS 2022 [1,2];
• a paper on adaptively solving repeated games won an outstanding paper award at ICML 2023 [3].

We will take care to more explicitly connect our contributions with these lines of work in the revised version.

2. On the practical takeaways.

We will do our best to revise our paper to better highlight the main takeaways for practitioners. Our contributions in this sense are twofold:

• Better modeling of long-term reward: The different objectives considered in this paper (Blackwell optimality and d-sensitive optimality) are refinements of the usual discounted return. Our objectives allow decision-makers to better take into account future rewards and to choose strategies that are very far-sighted (taking into account the rewards obtained after a very large number of steps).

• Quantitative takeaway: at a high level, our main takeaway is that optimizing these long-run objectives is quite difficult but can be safely reduced to discounted problems with discount factors close to 1; our bounds on the Blackwell threshold $\alpha_{\sf bw}$ and the d-sensitive threshold $\alpha_{\sf d}$ precisely quantify how close to 1 should these discount factors be.

Let us finally mention some practical domains where long-term reward matters: This is important in applications with a very long-run horizon (e.g. games played over many rounds, such as Poker [5], Atari Games [7], Diplomacy [8], etc.) or applications requiring sustainable growth objectives, e.g. applications of sequential decision-making in sustainable exploitation and harvesting [9,10]. We will use the additional space to highlight these connections.

Conclusion:

We hope that we addressed your main comments. We will improve the paper based on your inputs. We are looking forward to your new feedback and evaluation/score, and we remain at your disposal through the rebuttal process in case you have any other questions.

References

[0] Wang, Y., Velasquez, A., Atia, G., Prater-Bennette, A., & Zou, S.. Robust average-reward markov decision processes. AAAI 2023.

[1] Cai, Y., Oikonomou, A., & Zheng, W.. Finite-time last-iterate convergence for learning in multi-player games. NeurIPS 2022.

[2] Anagnostides, I., Farina, G., Kroer, C., Lee, C. W., Luo, H., & Sandholm, T. Uncoupled learning dynamics with $o (\log t)$ swap regret in multiplayer games. NeurIPS 2022.

[3] Fiegel, C., Ménard, P., Kozuno, T., Munos, R., Perchet, V., & Valko, M.. Adapting to game trees in zero-sum imperfect information games. ICML 2023.

[4] Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., ... & Hassabis, D.. Mastering the game of Go with deep neural networks and tree search. Nature 2016.

[5] Brown, N., & Sandholm, T.. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science 2018.

[6] Munos, R., Valko, M., Calandriello, D., Azar, M. G., Rowland, M., Guo, Z. D., ... & Piot, B. (2023). Nash learning from human feedback. arXiv preprint arXiv:2312.00886, 18.

[7] Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., ... & Hassabis, D.. Human-level control through deep reinforcement learning. Nature 2015.

[8] Meta Fundamental AI Research Diplomacy Team (FAIR)†, Bakhtin, A., Brown, N., Dinan, E., Farina, G., Flaherty, C., ... & Zijlstra, M.. Human-level play in the game of Diplomacy by combining language models with strategic reasoning. Science 2022.

[9] Possingham, H, & Tuck, G. Application of stochastic dynamic programming to optimal fire management of a spatially structured threatened species. In Proceedings International Congress on Modelling and Simulation, MODSIM, pages 813–817, 1997.

[10] Ekeland, I, Karp, L, & Sumaila, R. Equilibrium resource management with altruistic overlapping generations, Journal of Environmental Economics and Management, Volume 70, 2015, Pages 1-16

We appreciate your time in reviewing our paper and we thank you for your positive score. We answer your questions below.

Question 1: clarification

• Thanks for pointing out these presentation issues. In our revised manuscript, we will use the extra space to enhance the exposition of past results and more clearly separate and highlight the differences in the results obtained for MDPs (one player) and stochastic games (two players).

• We have introduced stochastic games where the rewards $r_{i}^{ab}$ depend on the current state $i$ and the players’ actions $a,b$, but not on the next state $j$. This assumption is standard and without loss of generality - any game with rewards of the form $r_{ij}^{ab}$ can be converted to a game with rewards dependent only on current-state-action triples $(i,a,b)$ by expanding the state space to include intermediary states of the form (i,j,a,b). It is worth emphasizing that many standard textbooks and papers on stochastic games focus on the setting with $r_{i}^{ab}$ instead of $r_{ij}^{ab}$, e.g. the competitive MDP textbook [0] (e.g. chapter 3 there on discounted stochastic games) and the main collection of articles on stochastic games collected by Neyman and Sorin [1] (e.g. Chapter 1 by Lloyd Shapley in this book).

[0] Filar, J., & Vrieze, K. (2012). Competitive Markov decision processes.

[1] Neyman, A., & Sorin, S. (Eds.). (2003). Stochastic games and applications.

Question 2: smoothness

You are correct in noting that we do not require any smoothness assumptions in our paper. Since the sets of states and actions are finite, all functions (rewards and transitions) are discrete. Therefore, continuity or differentiability assumptions are not needed. It is worth noting that the Blackwell threshold may not exist in models with continuous state sets, and this is even the case for countable state sets, as shown in Maitra’1965 “Dynamic programming for countable state systems”. We will make this point more explicit in the paper to avoid any confusion.

Conclusion:

We hope that we addressed your main comments, and we thank you again for your positive score. We will refine the paper's presentation based on your input. We remain at your disposal throughout the rebuttal process in case you have further questions.