Thresholds for sensitive optimality and Blackwell optimality in stochastic games
Authors: Stephane Gaubert
Julien Grand-Clément
Ricardo D. Katz
Venue: NeurIPS 2025 poster ()
Keywords: Stochastic games
Blackwell optimality
mean-payoff optimality
Primary area: theory

Abstract: We investigate refinements of the mean-payoff criterion in two-player zero-sum perfect-information stochastic games. A strategy is *Blackwell optimal* if it is optimal in the discounted game for all discount factors sufficiently close to $1$. The notion of *$d$-sensitive optimality* interpolates between mean-payoff optimality (corresponding to the case $d=-1$) and Blackwell optimality ($d=\infty$). The *Blackwell threshold* $\alpha_{\sf bw} \in [0,1[$ is the discount factor above which all optimal strategies in the discounted game are guaranteed to be Blackwell optimal. The *$d$-sensitive threshold* $\alpha_{\sf d} \in [0,1[$ is defined analogously. Bounding $\alpha_{\sf bw}$ and $\alpha_{\sf d}$ are fundamental problems in algorithmic game theory, since these thresholds control the complexity for computing Blackwell and $d$-sensitive optimal strategies, by reduction to discounted games which can be solved in $O\left((1-\alpha)^{-1}\right)$ iterations. We provide the first bounds on the $d$-sensitive threshold $\alpha_{\sf d}$ beyond the case $d=-1$, and we establish improved bounds for the Blackwell threshold $\alpha_{\sf bw}$. This is achieved by leveraging separation bounds on algebraic numbers, relying on Lagrange bounds and more advanced techniques based on Mahler measures and multiplicity theorems.

Thresholds for sensitive optimality and Blackwell optimality in stochastic games
Stéphane Gaubert
Julien Grand-Clément
INRIA and Ecole Polytechnique stephane. paapaaaaa.gaabeeriiiii....
HEC Paris
grand-clementhhec.rr
Ricardo D. Katz
CIFASIS-CONICET
ctw.:/ifaaai--cccct.e....o arv.
Abstract
We investigate refinements of the mean-payoff criterion in two-player zero-sum perfect-information stochastic games. A strategy is Blackwell optimal if is optimal in the discounted game for all discount factors sufficiently close 1. The notion of d-sensitive optimality interpolates between mean-payoff optimality (corresponding to the case d -1) and Blackwell optimality (d oo). The Blackwell threshold aBw E [o, 1[ is the discount factor above which all optimal strategies in the discounted game are guaranteed be Blackwell optimal. The d-sensitive threshold aa E [0, 1 is defined analogously. Bounding OBww and ad are fundamental problems in algorithmic game theory, since these thresholds control the complexity for computing Blackwell and d-sensitive optimal strategies, by reduction discounted games which can be solved in O ((1 a)) a)- iterations. beyond the case d = -1, and we establish improved bounds for the Blackwell threshold OBw- This is achieved by leveraging separation bounds on algebraic numbers, relying on Lagrange bounds and more advanced techniques based on Mahler measures and multiplicity theorems.
We provide the first bounds on the d-sensitive threshold
Introduction
Two-player perfect-informatioon zero-sum stochastic games (SGs) are an important class of Shapley's stochastic games [Sha53] where every state is controlled by unique player. SGs are corner- stone of game theory, with important applications in auctions [LLP+99] mechanism design [Nar14], multi-agent reinforcement learning [Li194], robust optimization GCPV23 CGK+ and p-calculus model-checking [CHV* 18). Shapley originally considered the sum of discounted instantaneous re-
wards as the objective; the mean-payoff objective was studied in (G177) Stationary and deterministic
optimal strategies exist for these objectives in the perfect-informatin case [Sha53 [..69.
The mean-payoff objective coincides with the limit of the discounted objective the discount factor goes to This suggests to study the variation of the set of optimal strategies in the discounted game, as function of the discount factor. Blackwell showed (in the one-player case) that, for finite state and action models, there exist strategies that remain discount optimal for all values of the discount factor that sufficiently close [Bla62]. These now called Blackwell optimal strategies. As the discount factor approaches 1, the "weight" given to the rewards received in the distant future increases. Therefore, Blackwell optimal strategies can be considered the most farsighted (or least greedy) strategies for models in long horizon. This is why better understanding Blackwell optimality
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

is referred to as "one of the pressing questions in reinforcement learning" in (DDE 20]. Veinott introduced (still in the one-player case) the notion of d-sensitive optimality, interpolating between mean-payoff optimality (obtained for d = - 1) and Blackwell optimality (obtained for d = xo). The value associated with a given stationary strategy has Laurent series expansion in the powers of 1 - a, where o is the discount factor, with a pole of order at most 1 at a = 1. Veinott's d-sensitive objective involves the sequence of coefficients of this expansion, up to order d. which is maximized or minimized with respect to the lexicographic order (see Theorem 10.1.6 in [Ptt14]. In particular, any d-sensitive optimal strategy d' d'-ensiiivve optimal for all d' < d. Moreover, for models with n states, every (n 2) -ssesiiie optimal strategy is Blackwell optimal. The notion for d 0 is also known as bias optimality.
It is worth emphasizing that the notions of Blackwell optimality and mean-payoff optimality have received increased attention recently the reinforcement learning community, see DDE+ 20 DG22 TRMV21 YGA 16). More generally, computing mean-payoff optimal strategies is an important open question in algorithmic game theory and has been extensively studied. Pseudo-polynomias algorithms exist for mean-payoff deterministic instances, based on pumping [GKK88] and value iteration [GB03 GS08). In more generality, computing mean-payoff or bias optimal strategies is difficult, since the Bellman operator is no longer contraction when a 1, and the mean-payoff and bias objectives may be discontinuous in the entries of stationary strategies (e.g.. Chapter of [FS12). In fact, strategy iteration may cycle for the mean-payoff objective in multichain instances (see Section 6 of (ACTDGI2), ), and other algorithms have an exponential dependence on the number of states with stochastic mnon-dtterministic) transitions undetermined complexities [ACTDGI2] BEGMIO.. Besides the method based on the Blackwell threshold discussed below, the only algorithm aware of to compute Blackwell optimal strategies consists in performing policy iteration, considering the discount factor as a formal parameter, and encoding the discounted value function associated with pair of strategies by its Laurent series expansion truncated at order n - 2, leading to a nested lexicographic policy iteration method, see [Put14] Chapter 10.3] for presentation in the one player case. A counter example of Friedmann implies that for deterministic games, this algorithm can take an exponential time [Fri09].
CGB03
The existence of the Blackwell threshold, defined the smallest number aBw [0, 1[ such that strategies that are optimal for any discount factor a 2 Crww are Blackwell optimal, is well-known, e.g. [AM09]. We define the d-sensitive threshold the smallest number oa E [0, 1[ such that strategies that are discount optimal for any discount factor a 2 Og are d-sensitive optimal. The existence of OBww and og suggests simple method for computing Blackwell and d-sensitive optimal strategies: compute discount optimal strategies for a discount factor close to 1. This approach has the advantage that any advances in solving discounted SGs transfer to algorithms for Blackwell and mean-payoff optimal strategies. Note that the term (1 a)- controls the complexity of computing discount optimal strategies: for known game parameters (rewards and transitions), strategy iteration and value iteration scale as Õ(( a)- [HMZ13) (hiding the dependence on the number of states/ states/actions. and lower order terms in 1 - a). For unknown game parameters, model-based methods (ZKBY23 or model-free methods based on Q-learning [SWYY2)] scale as Ö((1 ([(1-a)-) "))
Thus, for computational purposes, it is crucial to upper bound aew and ad, or equivalently to lower bound aBw and 1 - ag- For such bounds to be useful, they should only rely on a few game parameters that are available by design. In this paper, we consider SGs that satisfy the following assumption.
Assumption 1.1. I is a integer rewards, and rational transition probabilities. The parameters of the game I are n, W and M, and are defined as follow:
stochastic game with finitely many states and actions,
* n E P4 is the number of states,
W E N is an upper bound on the absolute values of the integer rewards,
.M E N is the common denominator of the transition probabilities.
Main results. We provide upper bounds for the Blackwell threshold (Bww and for the d-sensitive threshold og for perfect-information SGs. We also derive stronger results the case of deterministic games (transition probabilities in {0, 1)) or for stochastic games with unichain structure.

---

At the core of our results are separation bounds for algebraic numbers, a classical topic in algebraic number theory. More precisely, we use three separation methods. The first method relies on result of Lagrange [Lag69], also obtained by Hadamard [Had93] and Fujiwara [Fuj16], providing lower bound on the modulus |a| of any non-zero root z of polynomial P, see Lecture IV in (Yap00). The second method relies on Mahler measures to lower bound 1 - when * is root of polynomial P. especially on a theorem of Dubickas [Dbb95] building on a series of earlier works based on the seminal paper by Mignotte and Waldshmidt [MW94). The third method uses bound of Borwein, Edérlyi, and Kós on the multiplicity of I as a root a polynomial with integer coefficients [BEK99], which controls the value of d such that ad drww- We shall see that each of these approaches yields a useful bound- - not dominated by the other bounds in some regimes of the game parameters n, W and M. We present of readability, we simplify some of our results with O(.) notations here, and we defer the detailed statements to the next sections. We start with the results based on Lagrange.
main results below, according the different techniques. For the sake
Theorem 1.2 (Based on Lagrange bound). If the game I' satisfies Assumption 1.1 then:
Deterministic case (M 1). The d-sensitive threshold da and the Blackwell threshold OBw satisfy
1
Old S
2n and aBw S 24W (2:)
(1)
24W 24W (min(d+
2 21
Stochastic case (M > 1). The Blackwell threshold aBw satisfies aBw
(WMM )22M22.00 2
(2n-1)
13
2 2
2n-1 IfT is unichain, the d-sensitive threshold oa satisfies oa S 1 n (2 min 5n
Our next set of results are bounds aBww based on Mahler measures. Since these bounds are more difficult to read than the ones in the previous theorem, we only give the resulting O(.) expressions here, and we provide the exact values in Sections and We provide bounds on -log(1 aBww,, i... the value of L > 0 such that agw S 1 11-e
Theorem 1.3 (Based on Mahler measures). If the game I satisfies Assumption
then:
Deterministic case. The Blackwell threshold arew satisfies
log (1 (xBw) S SO mnax { lox( log (wT))) log(),,W))))
Stochastic case. The Blackwell threshold aBw satisfies
log (1 - aBw) S o max
vn log(n) (log(W) + r21 log( (M) log(M)))) ()))
We now present our last set of results. [ei69] shows that, for Markov decision processes (MDPs, i.e., the one-player case), (n 2) 2)-sensitive optimal strategies are also Blackwell optimal. Our next theorem shows that a much smaller value of d may suffice.
Theorem 1.4. Assume the game T satisfies Assumption T.I and is deterministic. Then every
jdet (n, W) W) sensitive optimal strategy is Blackwell optimal, where dilet (n, W) = (VVnlog(W))
When log(W) = (((), dott (n, W) may be much smaller than n - 2. Combining Theorem 1.4 with the bounds on Old of Theorem 1.2 we arrive at the following bound on OrBw-
Theorem 1.5 (Based on multiplicity). Assume that I satisfies Assumption I.I and is deterministic.
Then the Blackwell threshold OBBw satisfies Orww S
24W (inuf VoloogW)) m)
2n
In the case of general (non-deterministic) perfect-information SGs, the multiplicity method of Theorem 1.5 does not lead to useful bound. We further elaborate this in the last part of Section 4 To simplify the comparison between our bounds, and with existing work, we summarize all our results in Tables and 2 In these tables, we reformulate our bounds on aBw as bounds on log(1 -Bw),
i.c., the value of L > 0 such that aew < 1 -t. and similarly for ag.
3

---

Note that Assumption 1.1 is necessary to obtain a meaningful bound on Bw and Ord (Proposition 4.3 in
[GCP23]). ) We emphasize that the bounds derived Theorems 1.2] L.3 and L.5 are complementary.
i.e., there are different regimes of log(W), log(M and where one bound is better than the
others. As an example, consider deterministic games (M 1). When W = O(1), Theorem 1.2
yields - log(1 - OtBw) S O(n), while Theorems 1.3 and 1.5 both lead to the stronger bound
- -Log(1 (rBw) S O (Iog( In contrast, in the regime where W = (n))) Theorems 1.2
and 1.5 lead to the bound - logg1- (BBw) I O(n), which is stronger than Theorem 1.3 yielding
log(1 - OKBw) - 0 (0nnlog(()) ). We provide more discussion on this in Sections and 4
Compared to previous work, we note that our bound on - log(1 - (Bw) from Theorem 1.2 improves
upon [AM09] and [GCP23 by factor 12(1), while our bound from Theorem 1.5 recovers for SGs
the results obtained in [M225] for MDPs. Theorem 1.3 provides a new approach to bounding OB based on Mahler measures. We are also the first provide bounds for od, beyond the case for deterministic games analyzed in [ZP96]. However, we note that our results on (Bww do not lead to time algorithms for computing Blackwell optimal strategies: our bounds on Cigw are still very close to 1, and the algorithms with the best dependence on for solving discounted SGs require (((1 - ") arithmetic operations [HMZI3]. We refer to the next section for a detailed discussion and comparison with the existing bounds on drew and odd.
weakly- or even quasi-polynood
Table 1:
Bounds for deterministic SGs satisfying Assumption 1.1 For the sake of readability, in all these bounds we omit constant terms and the O(-) notation.
Bound log(11 (rBw)
Bound on -log(1 oa)
Remarks
ZP96
log( ()) + 3 3logg(n)
For d -1
AM09
log (n) + n²² log (W)
x
GCP23
n + n log( ())
x
For MDPs
MK25
n. log W log
log(W)
For MDPs
[og(W)
Th. 1.2
n + log(
W
log(W) + (d + 4) 1 1 log
2n d+1
Lagrange
vn
Th.
1.3
max V log(())) (1) log( / /nW) log( log(vnW))
X
Mahler
Th.
1.5
Vnlog(W) log log(W)) + log(W)
X
Multiplicity
Table 2: Bounds for SGs satisfying Assumption [.1 hide the constant term and the (-)) notation.
For the sake of readability, in all these bounds This bound holds only in the unichain case.
:
Bound on log(1 aew)
Bound on - logg1 as)
Remarks
AM09
n log (n) + n² log (max ( M))
x
GCP23
n² + (og(())) + n lo)
For MDPs
Th. 1.2
m11 log( MM) log(W)
12 2n-1) (d 4) log
2n
Lagrange
d+4
Th.
1.3
max ( Fo,
Mahler
F : log(M)) log(W)
Related work. To the best of our knowledge, only small number of papers have obtained bounds on the d-sensitive threshold ag (only for d = 1) or on the Blackwell threshold a:ww
d-sensitive threshold. The existence of a is proved in the seminal paper [L669] and in Theo- rem 5.4.4 of (Pur95]. It is used, for instance, in [A009 to show that these games polynomially reduce to solving discounted SGs. [ZP9) shows the tight bound a 2 1 awna for deterministic perfect-information mean -ayooff SGs. Theorem 1.2 recovers this bound for -= -1, but no general bound was known for ad (before our work). [AG13] shows that if there is renewal state, i.e., state for which the time of first return from any other state is bounded by N E N. then we can take a-1 1/N. A characterization of a for the one-player case (i.e., for MDPs) is given in [Bo233 but the obtained bound relies on the minimum gain difference between two strategies, instead of only the game parameters n, M and W as in results. Finally, note that line of work studies

---

related but different question for MDPs and reinforcement learning, namely, how close to 1 should be for a discount optimal strategy to be e-optimal for the mean-payoft criterion, e.g. [WWY22 showing that 2 e-e/H H suffices for veakly-communicht
instances with diameter H E N, or [S21]] using assumptions on the mixing times of the Markov chains induced by deterministic strategies. In contrast to these works, we focus on optimality (instead of e-optimality) and most of our results do not require an assumption on the chain structure (except for og in the stochastic case).
Blackwell threshold. The existence of (rew comes from an argument developed initially by Black- well [Bl62]]. The works closest to ours are [AM09] GCP23
MK25]. [AM09] shows a bound on Q-1 for SGs but their argument extends directly to aBw. [CCP3 gives bound on (Bww for MDPs.
[MK25] shows an analog of Theorem [14] for deterministic MDPs using Lagrange's bound. We
summarize these bounds in Tables [I] and [2] We also note that the Blackwell threshold has found
WVA +4 and in the smoothed analysis recent applications in the study of robust MDPs [GCPV33
of the complexity of strategy iteration LS24..
Main improvements compared to previous works. Our work appears to be the first to provide a bound on the d-sensitive threshold da beyond the case d -1 (corresponding to mean-payoff optimality) in the deterministic setting. Regarding Orew. MK255 only focuses on deterministic MDPs using the multiplicity approach, i.e., on the one-player deterministic case, whereas we focus on two-player SGs, This line of analysis based on multiplicity (Theorem 1.4 does not extend to the non-deteriiiistic case (see the end of Section 4, where the corresponding bound on the value of d such that ag = QBww much larger than n 2. the bound proved in the seminal paper [Ve66]] Compared to [GCP23) and [AM09], our bounds from Theorems 1.2 and 1.3 compare favorably: for instance, the bounds on - [o <Bw) in [GCP23 and [AM09] are worse by factor of (2)) compared to our bounds based on Lagrange. This improvement comes from two main innovations in the analysis: better bounds on the magnitudes of the coefficients of the considered polynomials, and the use of much stronger root separation results- [AM09] uses a bound attributed to Cauchy (e.g. Equation (5) in Lecture IV of (Yap00) which is weaker than the one we use due to Lagrange, while [GCP23 uses a bound from [Rum79]. which applies to the distance between any two roots of polynomial, whereas we only need to separate a root from 1 (and not from any other conjugates).
Outline. This paper is organized as follows. We introduce porfect-information SGs in Section 2 We derive bounds for the deterministic case in Section 3 and bounds for the stochastic case in Section The implications of our results are discussed in Section 5
All the proofs can be found in the appendix.
2 Preliminaries on perfect-information stochastic games
Lloyd Shapley introduced SGs in the seminal paper [Sha53]. We focus on the case of two-player zero-sum SGs with finitely many states and actions, and discrete time. We denote the state space by [n] := (I....,n) n) for some N. At every stage & e N. the game both players, called Min and Max. An instantaneous reward of r determined when Min chooses action a and Max chooses action b in state i, and then the game transitions to the next state j E [n] with probability poch E [0. 1]. Thus, we consider SGs where the rewards r:th depend on the current state and the players' actions a, b, but not on the next state j. It is worth noting that this assumption is standard and can be made without loss of generality (any game with rewards depending on the next state j, i.e., of the form ri can be converted state space to include intermediary states). We focus on the case of perfect-informatiinn SGs, where we can partition the state space [n] into the states controlled by Min and those controlled by Max.
a state ig E [n]] observable by
game with rewards of the form r:d expanding the
strategy of a player is a function that assigns to a history of the game (i.c., the sequence of previous states and actions) a decision (choice of an action) of this player. A pair of strategies (o, 7) of players Min and Max induces a probability measure on the set of sequences of states. We define the discounted value function a + o -T
(a) from J0, 1[ to R, associated with the pair of strategies
&roeee 1 = where Th r .... is the (a, T) and the initial state i, as E. (.T((a) (a) := E Σ a aar
random sequence of instantaneous rewards induced by (T,
5

---

Definition 2.1. A pair of strategies (a",-") of players Min and Max is discount optimal for the discount factor if for any state and for any strategies a and T of players Min and Max, we have
1/4
(a) 2 (a) 2 of (a))
pair of strategies (a", is Blackwell optimal if there exists ā < 1 such that (o", -*) is discount optimal for all discount factors larger than a.
Shapley (Sh553] shows the existence of stationary discount optimal strategies. If, in addition, the game is a perfect-information SG, then these stationary optimal strategies may be chosen deterministic. The existence of stationary deterministic Blackwell optimal strategies for cerfect-informationn SGs is
a consequence of the analysis in the seminal paper [LL69] (see the proof of Theorem in [LL69]
Definition 2.2. A pair of strategies (a" ,7*) of players Min and Max is d-sensitive optimal if
lim (1 (1-a)-a ( (a) U/ (a) 2 lim (1-a) (o,
( "T (a) - of ({((a)) 2 (2)
a-1-
a=+1
for any state and any strategies a and T of players Min and Max respectively.
Our definition of d-sensitive optimality for two-player SGs recovers the definition of d-sensitive optimality for the one-player case [Vei69], Note that Blackwell optimal strategies are d-sensitive optimal for d = -1, 0, In fact, the same analysis as for MDPs (using the Laurent series expansion, e.g. Theorem 10.1.6 of 4Put14] shows that n 2-sensitive optimal strategies are Blackwell optimal, and mean mean-payoff payoff optimality corresponds to d = -.
Before diving into our main results, we give an overview of our main proof techniques.
Bounds on aBww Our bounds are based on studying the zeros of the functions a + (a)
(a)
for any pairs (a, r) and (o', 7') of stationary strategies and any state i. This approach has been used for MDPs, e.g., see Theorem 2.16 of [FS12]. Differences of discounted value functions are rational functions in EJ0, 1[ i.e., they can be written as the ratio of two polynomials in a. As such, each of them can only have finitely many zeros Jo, 1[. Additionally, for ieferctiinooraaiion SGs, discount optimal strategies may be chosen stationary and deterministic [G177], hence we can consider only finitely many pairs of strategies. Therefore, there exists a discount factor ā < 1 such that none of
the functions a + v (a) u. (a) has zero in j 1[. and so all these functions have constant sign in Jā, 1[ This guarantees that OBw I c, since strategies that are discount optimal for some a satisfying ā < a < 1 remain discount optimal for all larger discount factors (otherwise some function + of (a) - vi ,T' (a) would change sign in Jā, 1D. Thus, a way to bound arww is to determine
how close to can a zero of the functions + vz (a) v.. .T' (ax) be. Given Assumption 1.1 we
can bound the degree of the numerator of a ++ 0- (a) 2. (a) and the size of its coefficients. We then use root separation results to separate the root of polynomial from a given scalar. Compared to previous work, our first improvement lies in a better analysis of the coefficients of the considered polynomials. As our second and main improvement, we use stronger separation bounds than in previous work, a bound due to Lagrange (Theorem 3.2) and a bound based on Mahler measures (Theorem 3.7). [AM09] uses weaker bound due to Cauchy, and [OB2I] also uses the Cauchy bound for a different purpose (bounding the variations in value functions when a + 1).
Deterministic vs. non-deterministic games. For deterministic SGs, each transition probability belongs to {0, 1}. In this case, the discounted value function associated with a pair of stationary strategies and state can be represented by the concatenation of path and an elementary circuit in the graph of the game, see Section 3 This can be used to analyze the degree and the magnitude of the coefficients of the numerator of + u. (a)-
- uf w'' (a). When the game is not deterministic, we rely on the closed-fome expression of the discounted value functions using cofactor matrices, see Section
Bounds on the d-sensitive threshold ag. Our bounds on Og rely on the same proof techniques as for orBw; except that the d-sensitive optimality allows us to deduce more information on the coefficients of the considered polynomials (more precisely, that some of them are zero). Again, the deterministic case is easier because we can exploit the graph representation of the discounted value functions mentioned above, whereas for the case of non-deterministic SGs we require unichain assumption.

---

3 Results for perfect-information deterministic stochastic games
We start by analyzing the structure of the discounted value functions deterministic perfect infor- mation SGs. A deterministic game can be represented by weighted digraph: its set of nodes is the set of states, there is an edge from state i to state j if some actions a and the players realize this transition, in which case this edge has weight Given an initial state i, pair of stationary strategies (a, determines a run of the game of the form "Ty", in which π is a path and y is a circuit. Given a (for simplicity, we denote
path - (fo, ..................... .k),, we set T)) == Tigh +0Ti16 +.... a -rir instantancous rewards by Tij instead of r.th). With this notation, E (a) = (r, T)a + T- (r, 7) where p is the length of π (i.e., the number of edges it contains) and @ is the length of y.. To study the zeros of ++ Ui o7 (a) U/ 2'r (a), we analyze the roots of the polynomial
o²
aa) = (1 a1) a (c. (a) of (a))
(here q' is the length of the circuit associated with (o', T.). The next lemma bounds the degree and coefficients of A.
Lemma 3.1. We can write A(a) = Ek= aga", where la S 12W and K S 2n - 1.
As described in the previous section, our bounds on oBw and ag rely on separating the roots of the polynomial A from 1. We proceed to do so in the next section.
3.1 Separation based on the Lagrange bound
In this section, we rely on the Lagrange bound (e.g. Lemma in Lecture IV of (Yap00))
Theorem 3.2 (Lagrange bound). Let P Σk=j ctax with ej & 0. Then, any non-zero root 2 of P
satisfies |a| N 1/ min (1+t... (lcs//le.))
The Lagrange bound separates the non zero roots a polynomial P from 0. To separate the roots of A from 1, we apply this bound to the polynomial e + A(1 - e). Using this approach, prove the first part of Theorem 1.2 namely, the bound on Odd for deterministic perfect-information SGs.
Theorem 3.3. Assume the game T satisfies Assumption
1.1 and is deterministic (M = 1). Then, the
d-sensitive threshold aa satisfies aa S
24W
2n Amin(d+1m)
The binomial coefficient in our bound on ag appears because of the change of variable e = in the polynomial A, necessary to apply the Lagrange bound to the polynomial e + A(1 e). Together with the result of [HMZ11, our bound of aa implies that for a fixed value d, we can compute d sensiiiie optimal strategies of a deterministic game in pseudo-polynone polynomial time, extending a theorem (ZP96) (for the d 1 case, then the bound is optimal).
Corollary 3.4. If the game T satisfies Assumption T.I and is deterministic (M 1), have 1
1 and aBw S Q-1 0-131- O(Wn3)
24W (2
Multiplicity approach. In this approach, we combine our bound on ag from Theorem 3.3 with a new result on the smallest integer d such that d-sensitive optimal strategies are also Blackwell optimal. Our next theorem parametrizes the value of such d by n and W.
Theorem 3.5. Assume the game satisfies Assumption T.I and is deterministic. Then, there exists constant a > 0 such that ddet (n, W)ssensitive optimal strategies are Blackwell optimal, where Filet (n, W) a ((n 1)(1 log (1g()) 2.
Note that delt (n. W) o ( (Vn(1 + log(WW). which may be much smaller than (proved by Vei69 for MDPs) in some regimes where log(W) = onn). To show that d Jolet (n, W) suffices for Blackwell optimality, we show that if pair of strategies is gilet W>-sensitive optimal, it is also d-sensitive optimal for all d' > (ne W), so that it is d-sensitive optimal for d = -1, -1,0,
7

---

therefore it is Blackwell optimal. A key ingredient in our proof is a bound on the multiplicity of 1 as a root of polynomial as a function of its degree and the size its coefficients [BEK99], used to bound the multiplicity of 1 as root of A (a:). Theorem 1.5 follows directly from the bound on da of dd obtained this section, which improve by (nn) (for log(1 (kww) compared previous works.
Theorem 3.3 by choosing d = ddet (n, W). We refer to Table I for comparisons between the bounds
3.2 Separation based on Mahler measures
We now present a bound on aBw based on the Mahler measure of algebraic numbers [Leh33 Mah62]. Definition 3.6. The Mahler measure M(P) E I of polynomial P is given by M(P) I max 1, | if P factorizes over the complex numbers P I [ -z); The Mahler measure (z) E IR of an algebraic number 2 is the Mahler measure of its minimal polynomial.
Mahler measures have applications in areas like polynomial factorization, Diophantine approximation, and knot theory, see [Smy08). Mignotte and Waldschmidt [MW94] and Dubickas [Dub95] use them to separate algebraic numbers and 1. The following is Theorem I of (Dub95).
Theorem 3.7. Let e > O. There exists a constant D. E N such that any algebraic number z of degree d > D. which is not root of unity satisfies:
|= 1 > e (x/4+c) / dolo M(s)
(4)
To apply Theorem 3.7
we need an estimate of M=), where 2 a root of A. Since A(=) = 0, the minimal polynomial of divides A, and so (z) S M(A). A classical result of Landau [Lan05
states that for any complex polynomial p= E Cg we have M(P) S / Ed k= |cx12. Applying this to the polynomial A (whose coefficients and degree are bounded in Lemma 3.1 following upper bound for a:Bw.
we arrive at the
Theorem 3.8. If the game satisfies Assumption 1.7 and is deterministic, for each e > there exists constant ae O such that the Blackwell threshold aBw satisfies CBww S MMa where
- -log( 10g(1-uma der) = max {
( (2n 1) lollolnnn--2 log 2log///
The maximum in Theorem 3.8 is necessary because for a fixed c > 0, the bound in Theorem 3.7 only applies to algebraic numbers with a degree greater than D.. Thus, if root of A has degree greater than De, we can apply Theorem 3.7 otherwise we apply the Lagrange bound.
Remark 3.9. When W is "small" (W = n (())), we obtain from the definition of det that log(1 det)
(Ma) = Oogna.... When W is "large" (W = exp(S2(n log? n))). we have - log(1 - Ma) Ollog W + log )) the (logn)/2 term being of lower order. There is an intermediate regime in which n 2(1) W S exp(O(n log" n)) and for which log(1 ( O log log W).
det
=
Note that the bound on aBww from Theorem incomparable to the one of Corollary 3.4; depending on the value of W. none of the bounds dominates the other. Taking the best (smallest) of the two bounds, we arrive at Table in which we bound the Blackwell threshold depending on the different regimes for log(W))
function of the number of states (up terms of lower order).
Remark 3.10 3. Using the preprocessing algorithm of Frank and Tardos FT877 for any deterministic mean- poyaff game with states of Min and states of Max, and arbitrary rational weights, can construct mean-payoff game with integer weights such that W 20(am)) and which has the same optimal strategies. For n m, this estimate of W is larger than the separation order W = exp(Oir log" n)) between the "intermediate" and "high W regimes in Table 3 So, all the regimes in Remark 3.9 and Table are relevant.
4 Results for perfect-information stochastic games
We now focus on the general case of pprfect-information SGs. We start by studying the structure of the discounted value function oi" (a) associated with pair of stationary strategies (a, r) and state
8

---

Table 3: Bound for the Blackwell threshold aBww of deterministic perfect-information SGs in different regimes of (W) with respect the number of states n.
log W
(log n)
@ ((n) @(n log
@(n log" ni) log W
lox
log(1 aaw): v log n
Vollo n log W
n log
log W log n log W
i. It is well-known that this function is rational, i.e., it is the ratio of two polynomials (e.g., Lemma
10.1.3 [Put14). ). We define (ax) as the numerator appearing in u (a) 0/ (ax) (we refer to
Appendix for the precise definition of A). Thus, to study the zeros of a + uf (a) ug (a) can focus on studying the roots of A. We first analyze the degree and the size of the coefficients A.
Proposition 4.1. Under Assumption 1.1 the polynomial A can be written as A(a) = Ek=o ao
where c - 2nW 2 2n
(?nx)) for all k E {0,.... 2n 10-1 1}.
Proposition 4.1 improves upon the corresponding results of [GCP23 for MDPs, which show that |cx| I 2nW 2 across all & E t0,...,,1 2n - 1}.
Results based the Lagrange bound. Applying the Lagrange bound to the polynomial + A( - <). we prove the second part of Theorem 1.2 We start with the bound on aBw-
213nJ-2
Corollary 4.2. Under Assumption I.I. we have d'ww S
nW (2M)2
We now state the bound on oa for non-deterministic SGs. Note that in the next result, we assume that the SG is unichain, i.e., that the Markov chain induced by any pair of stationary strategies unichain. This assumption is necessary to precisely connect the coefficients of A(a) with the coefficients of the Laurent series expansion of of (a) - -0,² (a:).
Corollary 4.3. If satisfies Assumption 1.7 and is unichain, the d-sensitive threshold ag satisfies
2min(d42.13n -n
Pa S 1 n (2M) ( 2n-1
Remark 4.4 (On the unichain assumption). In order prove Corollary 4.3 the unichain assump- tion allows us to relate the function a + =. of (a) with the polynomial A(a) using a manageable structure. More precisely, thanks to the unichain assumption, can write
Aaa) (1 (aa)) (a) (a) 1, "/' (a))
where Q(a)) is a polynomial that satisfies Q(1) # follows that, for any d' we have
lim (1 - a) -d (v. (a) of (a)) = 0 - lim (1 - ax) (d'+2) A(o) = =0 a-11
a-1
a property that is useful to analyze the d-sensitive optimality (see Appendix
C for more details).
Controlling this polynomial ((a) in all generality (for multichain models) is the main difficulty in removing the unichain assumption. Generalizing to the multichain setting would require a finer characterization of the spectral properties of the induced Markov chains under arbitrary strategies, which is challenging open problem.
Results based on the Mahler bound. Next, we present the results for aBw based on the Mahler bound. The proof follows the same lines in the deterministic case (Theorem (.8).
Theorem 4.5. If the game I' satisfies Assumption 1.1 for each > 0 there exists constant a, such
that the Blackwell threshold aeu satisfies aBw S aMa. where log(1 aMa) = max [8, 32), 81
( + (2n log (2n 1) log (L), B3g : a. + log (L), and L 2n (22nn-1)))
(22m-11)
We end this section with a discussion on the multiplicity approach highlighted in Theorems L.5 and 3.5 applied to the of general SGs.
worth emphasizing that the multiplicity approach fails for general SGs. Indeed, this approach relies on bounding the multiplicity of root of the polynomial A(a) representing the numerator

---

of the functions u - - (a) (since this multiplicity leads to bound on the minimal value of satisfying that any d-sensitive optimal strategy is also Blackwell optimal).
(a)
Theorem 2.1 of [EK99] shows that given a polynomial P = Ei=o Cga** of degree such that max; |x| S 1, the multiplicity d of as a root of P is bounded by [vd(1+ + log lcol) For de-
terministic games, we can ensure that lcal remains small, allowing to obtain the meaningful bound d d= OVyn) by this technique (see Lemma 3.1 and Theorem 3.5). However, for general stochastic instances, the magnitude of [col can grow as M(n4"M") In particular, under Assumption 1.1 using
arguments similar to the ones used to prove Theorem 3.5 we get that every (nt, W) -enssiive optimal strategy is Blackwell optimal, where
2n
(n,, W) = a -1) (1+ log 2nW 2
for some a >> O. This leads to a vacuous bound (d= (2())) that is not better than the existing one. Indeed, is known that d = n- enough [Vei69], and 22-2 is much smaller than O (n, W). This shows that while the multiplicity approach may be useful in the deterministic case (in the sense that there are some regimes of and W where ddet W) over existing bounds in the stochastic case, highlighting the strength of our new results based on the Lagrange and Mahler bounds.
2), does not yield any improvement
5 Discussion
We obtain bounds on the Blackwell threshold oraw and on the d-sensitive threshold oa. We improve the existing bounds on - log((1 orBw) by a factor Q(n) (compared to [AM09] for SGs and [GCP23 for MDPs), and we provide the first bound on og beyond the case d = -1 in deterministic games. Blackwell and mean-payoff optimal strategies have received some attention reinforcement learning and SGs in recent years, and our bounds control the complexity of the main method to compute Blackwell and d-sensitive optimal strategies for SGs, by choosing a > aBww (or a > aa) in algorithms for solving discounted SGs. A crucial advantage of this approach is that our bounds can be combined with any progress in solving discounted SGs. However, to the best of our knowledge, all algorithms whose complexity depends on the discount factor a scale as Õ((1 - aa) for some negative & (e.g. k- = -1 for strategy iteration [Yell] HMZI3 AG13) or k -3 for sampling-bisg based methods ISWYY200 Our bounds on (1 (rBw.) involve some terms that grow superpolynomially in (see Tables and Obtaining stronger bounds for aBw is important future research direction.
Open questions. would be interesting to obtain bounds for ag for general (non (nttmeeterministtc) perfect-information SGs, without the unichain assumption. Additionally, our work provides several different upper bounds for dBww, all of which may be exponentially close to 1. It is essential to understand if this is a limitation of our line of analysis for instance, does there exist stronger separation results between a root of polynomial P and 1 for the specific polynomials appearing in our proof? or if this is an inherent difficulty of the problem. Obtaining lower bounds for arew and ag in all generality is an important next step.
Acknowledgements
We thank the anonymous reviewers for their constructive comments improving the paper. Julien Brand-Clémen was supported by Hi! Paris and Agence Nationale de la Recherche (Grant 11-LABX- 0047).
References
[ACTDG12) M. Akian, J. Cochet-Terrasson S. Detournay, and S. Gaubert. Policy iteration algorithm for zero-sum multichain stochastic games with mean payoff and perfect information. arXiv preprint 2012.
10

---

[AG13] M. Akian and S. Gaubert. Policy iteration for perfect information stochastic mean payoff games with bounded first return times is strongly polynomial. arXiv preprint arXiv: 100,4453, 2013.
[AM09] D. Andersson and B. Miltersen. The complexity of solving stochastic games on graphs. In International Symposium on Algorithms and Compulation, pages 112-121. Springer, 2009.
[BEGM10] E. Boros, K. Elbassioni, V. Gurvich, and K. Makino. A pumping algorithm for ergodic stochastic mean payoff games with perfect information. In Integer Programming and Combinatorial Optimization: 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010. Proceedings 14, pages 341-354. Springer, 2010.
[BEK99] P. Borwein, T. Erdélyi, and G. Kós. Littlewood-type problems on [0,1]. Proceedings of the London Mathematical Society, 79(1):22-46, 1999.
[Bla62] D. Blackwell. Discrete dynamic programming. The Annals of Mathematical Statistics, pages 719-726, 1962.
[Boo23] V. Boone. When do discounted--optimal policies also optimize the gain? arXiv preprint arXiv:2304.08045 2023.
[CGB03] R. A. Cuninghame- Green and P. Butkovic. The equation A B @ y over (max,+). Theoretical Computer Science, 293(1):3-12, 2003.
[CGK+ K. Chatterjee, E. K. Goharshady, M. Karrabi, P. Novotný, and D. Žikelić. Solving long- average reward robust mdps via stochastic games, arXiv preprint arXiv:2312.13912. 2023.
18] E. M. Clarke, T. A. Henzinger, H. Veith, R. Bloem, et al. Handbook model checking, volume 10. Springer, 2018.
[CMP87] L. Cerlienco, M. Mignotte, and F. Piras. Computing the measure of polynomial. Journal of Symbolic Computation, 4(1):21-33, 1987.
[DDE+20] V. Dewanto, G. Dunn, A. Eshragh, M. Gallagher, and F. Roosta. Average-reward model-free reinforcement learning: a systematic review and literature mapping. arXiv preprint arXiv:2010.08920. 2020.
[DG22] V. Dewanto and M. Gallagher. Examining average and discounted reward optimality criteria in reinforcement learning. In Australasian Joint Conference on Artificial Intelligence, pages 800-813. Springer, 2022.
[Dub95] A. Dubickas. On algebraic numbers of small measure. Lithuanian Matherattiaa Journal, 35:333-342, 1995.
[Fri09] O. Friedmann. An exponential lower bound for the parity game strategy improvement algorithm as we know it. In LICS, pages 145-156. IEEE, August 2009.
[FS12] E. Feinberg and Shwartz. Handbook of Markov decision processes: methods and applications, volume 40. Springer Science & Business Media, 2012.
[FT87] A. Frank and Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Comb., 7(1):49 65, 1987.
[Fuj16] M. Fujiwara. Über die obere schranke des absoluten betrages der wurzeln einer algebraischen gleichung. Tohoku Mathematical Journal, First Series, 10:167-171, 1916.
[GCP23] J. Grand-Clément and M. Petrik. Reducing Blackwell and average optimality to discounted MDPs via the Blackwell discount factor. Advances Neural Information Processing Systems, 0822222852644 2023.

---

[GCPV23] J. Grand-Clement M. Petrik, and N. Vieille. Beyond discounted returns: Robust markov decision processes with average and blackwell optimality. arXiv preprint arXiv:2312.03611, 2023.
[Gil57] D. Gillette. Stochastic games with zero stop probabilities. Contributions to the Theory of Games, 3(39):17-1877, 1957.
[GKK88] V. Gurvich, A. Karzanov, and L. Khachiyan. Cyclic games and finding minimax mean cycles in digraphs. Zh. Vychisl. Mat. i Mat. Fiz,
1988.
[GS08] S. Gaubert and S. Sergeev. Cyclic projectors and separation theorems in idempotent convex geometry. Journal of Mathematical Sciences, 155:815-829, 2008.
[Had93] J. Hadamard. Étude sur les propriétés des fonctions entières et en particulier d'une fonction considéré par Riemann. Journal de Matémmatiqees Pures et Appliquées, 58:171-215, 1893.
[HMZ11] Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick. Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. In Bernard Chazelle, editor, Innovations in Computer Science ICS 2010, Tsinghua University, Beijing, China, January 7-9, 201 I. Proceedings, pages 253-263. Tsinghua University Press, 2011.
[HMZ13] T. Hansen, Miltersen, and U. Zwick. Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. Journal of the ACM (JACM), 60(1):1-16, 2013.
[JS21] Y. Jin and A. Sidford. Towards tight bounds the sample complexity of average- reward mdps. In International Conference on Machine Learning, pages 5055-5064 PMLR, 2021.
[Lag69] J. Lagrange. Sur résolution des équations numériques. Mémoires de l'Académie royale des Sciences et Belles-Lettres de Berlin, XXIII, 1769.
[Lan05] E. Landau. Sur quelques théorèmes de M. Petrovitch relatifs aux zéros des fonctions analytiques. Bulletin de la Société Mathématique de France, 33:251-261, 1905.
[Leh33] D. H. Lehmer. Factorization of certain cyclotomic functions. Annals of mathematics, 34(3):461-475 1933.
[Lit94] M. L. Littman. Markov games framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[LL69] M. Liggett and S. A. Lippman. Stochastic games with perfect information and time average payoff. SIAM Rev., 11:604 607, 1969.
[LLPP999] A. J. Lazarus D. F. Loeb, J. G. Propp. W. R. Stromquist, and D. H. Ullman. Combi- natorial games under auction play. Games and Economic Behavior, 27(2) 1999.
[LS22] B. Loff and M. Skomra. Smoothed Analysis of Deterministic Discounted and Mean- Payoff Games. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svens- son, editors. 51st International Colloquium on Automata, Languages, and Program- ming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 147:1-147:16, Dagstuhl, Germany, 2024. Schloss D Zentrum für Informatik.
[Mah62] K. Mahler. On some inequalities for polynomials in several variables. J. London Math. Soc, 37(1):341-383 -34444, 1962.
[MK25] D. Mukherjee and Kalyanakrishnan. Howard's policy iteration is subexponential for deterministic Markov Decision Problems with rewards of fixed bit-size and arbitrary discount factor. In International Conference on Automated Planning and Scheduling, 2025.
12

---

[MW94] M. Mignotte and M. Waldschmidt. On algebraic numbers of small height: linear forms one logarithm. Journal of Number Theory. 47(1):43-6) 62, 1994.
[Nar14] Y. Narahari. Game theory and mechanism design, volume 4. World Scientific, 2014.
[OB21] M. Oliu-Barton. New algorithms for solving zero-sum stochastic games. Mathematics of Operations Research, 46(1):255-267, 2021.
[Pur95] A. Puri. Theory of hybrid systems and discrete event systems. University of California, Berkeley, 1995.
[Put14] M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[Rum79] S. M. Rump. Polynomial minimum root separation. Mathematics of Computation. 33(145):377-36, 1979.
[Sha53] L. Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):1095-1100, 1953.
[Smy08] C. Smyth. Mahler measure one-variable polynomials: a survey. In Number Theory and Polymomiass, pages 322-349. Cambridge University Press, 2008.
[SWYY20] A. Sidford, M. Wang, L.. Yang, and Y. Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference Artificial Intelligence and Statistics, pages 2992-3002. PMLR, 2020.
[TRMV21] Y. Tang, M. Rowland, R. Munos, and M. Valko. Taylor expansion of discount factors. In International Conference Machine Learning, pages 10130-10140. PMLR, 2021.
[Vei69] A. Veinou(Jr.). Discrete Dynamic Programming with Sensitive Discount Optimality Criteria. The Annals of Mathematical Statistics, 4035): 1969.
[WVA+24] Y. Wang, A. Velasquez, G. Atia, A. Prater-Bennette, and S. Zou. Robust average-reward reinforcement learning. Journal of Artificial Intelligence Research, 80:719-803, 2024.
[WWY22] J. Wang, M. Wang, and L. F. Yang. Near sample-optimal reduction based policy learning for average reward MDP. arXiv preprint arXiv:2212.0061) 2022.
[Yap00] C. K. Yap. Fundamental problems of algorithmic algebra, volume 49, Oxford Univer- sity Press Oxford, 2000.
[Ye11] Yinyu Ye. The simplex and policy-iteration methods strongly polynomial for the markov decision problem with a fixed discount rate. Mathematics of Operations Research, 36(4):593-603, 2011.
[YGA+16] S. Yang, Y. Gao, B. An, H. Wang, and X. Chen. Efficient average reward reinforcement learning using constant shifting values. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
[ZKBY23] K. Zhang, S. M. Kakade, Basar, and L. F. Yang. Model-based aulti-agent rl in zero-sum markov games with near-optimal sample complexity. Journal of Machine Learning Research, (41155):1-53, 2023.
[ZP96] U. Zwick and M. Paterson. The complexity of mean payoff games graphs. Theoret. Comput. Sci., 158(1-2):343-35) 1996.
13

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We wrote abstract and introduction by outlining the topic of our paper, our main results and their limitations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The discussion on the limitation of our results can found in the introduction (section D and the last section of our main body (discussion and conclusion, section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificatiin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification:
All the proofs statements given in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: There numerical experiments in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
There are no numerical experiments in this paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttde//gguddeeeeeSouuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: There are no numerical experiments in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
There are no numerical experiments in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: There are no numerical experiments in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and ensured that the paper comply with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is mostly theoretical.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do use create assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We did not any LLMs for this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neurije http://s//.///ooeeeeeee///////// for what should or should not be described.
20

---

A Bounds from previous work
Bounds from [ The authors in [AM09] focus on perfect-information SGs. Lemma of [M09] shows that Crww I - 2( max M, W72n". We then apply the classical bound n! O (v (*) exp ( (Tmm)) to obtain the bound presented in Tables and
Bounds from [GCP23]. The authors of [GCP23] focus MDPs. Their main bound for aBw is given in Theorem 4.4, and their bound can be simplified to - -oo((1 - <Bw) O (W) n1 (1+ + log(M)) see the calculation in Appendix E of [GCP23]
Bounds from [MK25]. The bound for log(1 aBw) is given in Section 4.4 of [MK25] with the notation for our term log(W).
B Proofs for Section 3
In this section we provide the proofs of the results of Section 3 We first prove Lemma 3.1
Proof of Lemma 3.7 Note that the polynomial A defined in satisfies
A(a) = (1
a1)(1 -1--a)(11- a² ((r, a)aa x')) + (1 - a )a² (r, Na (1 o² (ra
Thus, the absolute value of instantaneous rewards are bounded by W, the coefficients of the polynomial of Lemma 3.1 satisfy laxl s 12W for all k. In addition, we have
K max (g + max p') - -.. +
2n
because we can choose 7. n' and 7' elementary (i.e., such that in the corresponding sequences of states, no state appears twice, except the initial and last state in the case of circuits), and so p + q S n. p S p, + d' and p'
B.1 Proofs for Section 3.1
We now provide the intermediate results that we need to prove Theorem 3.3 In what follows, we de- note by (P)) the height of the polynomial P P=E ca defined as H(P) = max..c(......)) lckl-
Lemma B.1. Let P = = ca.* * be a polynomial with integer coefficients and Q(y) Ek-o chy** be the polynomial which is obtained making the change of variable x = 1 in P(z). Suppose that, for some j E {O.....d}, we have d₃ # O and de = 0 for all < j. Then, the polynomial Q(y) has no zeros in the interval j0, 2H11)
1
Proof. We first bound the magnitude of the coefficients of Q in terms of H(P). Since Q(y) P(1 - y), we have of = (-1)) Ei=> ox (+) for é E (o....,d? d}. Now we use Σi (1) = (d-1) to obtain that |4| < (P) (d+1) for all i (o.
Note that |d/l 2 since dj * and of Z. Besides, note that for m and S 1, we have
(m)
m
(5)
i i++)
for all i E (j+ 1,.... m). Indeed, the cases i = j + and = m are trivial, so may assume
j < m (because j = m implies i = m). Suppose that (TT) S (m ف for some i S m Then,
++1-j
m = m +
111
m
m
m
i +
2
+1
j ++1
because
3
m-1 J+1
m m- m
m
f+1 m
(411
21

---

We are now ready to apply the Lagrange bound (Theorem 3.2
Using
we get
1
(())
H(P)
(1-1
(+2
for any i E {j + 1,..,, d). The lemma now follows from Theorem 3.2.
Note that the polynomial e + A(1 e) can be rewritten as
A(1 - c) Σ (-1)eeb
(6)
where b; -k== an (+) Then, the next proposition is direct consequence of Lemmas B. and 3.1 Proposition B.2. Suppose that bo _... bj-1 = and by of 0.for some j 2 1 in 66 Th Then, the polynomial A(1 e) has no zeros in the interval J0, 24W()
< 1, and let (a", TT) be a pair of discount optimal strategies for the discount factor a'. To prove the theorem, it is enough to show that (o", r*) a pair of d-sensitive optimal strategies.
Proof of Theorem 3.3 Let a' be such that
24W (d=1.)))
20
On the contrary, suppose that (a", -²) ) is not pair of d-sensitive optimal strategies. Then, either there exist a strategy of player Max and a state such that
lim (1 - (v,
(a) of (a)) <0,
or there exist strategy a of player Min and state such that
lim a1- (v (a) u a,t" (a)) > 0.
(8)
a=l
In the first place, assume that holds. Let d' be the smallest value satisfying
lim (1-or at) dd' (uf . (a) oi (Taa) < 0.
(9)
By 7 it follows that d' d and that lim, (1 a:) d' (0 o" x (a) 0/f (a)) for all d"
If for N we set [gla == 1 + a -- then the polynomial A defined in satisfies
(aa) (1 11--at a1) ad ((0 (a) of (a)) = (1 - a)) (a (a) - (a)) (10)
Therefore, for all dl we have
lim a1) d" (vg (a) a' 0/ (a)
(a)
lim (1 (1- oz) (d" (dd a+1
(a) 0.
a=11
We conclude that by = =... = by = 0 and b242 F 0 if we represent the polynomial A(1 c) as
in (6. Thus, by 7 and Proposition B.2 it follows that (a) u ((aa) < for 1 24W(511)
< 1, and therefore this remains true for 24W (mii.))))..))
< because K + 1 S 2n and
d' d. Since 1 contradicting the fact that (a*, .T") a pair of discount optimal strategies for a'.
a' 1, in particular we have of (a') - of (a < 0.
24W (min
On the other hand, if ( is satisfied, using symmetric arguments we also arrive to contradiction. This completes the proof.
Proof of Corollary 3.4 The first inequality of this corollary readily follows from Theorem 3.3 The
second inequality follows from Proposition B.2 the fact that K < 2n 1 and that the function
j 21W
3n
is convex and achieves its minimum j 2.
142
22

---

We conclude this section with the proof of Theorem 3.5
Proof of Theorem 3.5 Theorem 2.1 of 9 shows that if P = Σd=o Caa is non-zero poly-
nomial such that maxke (o.....d) [cs] I 1, then the multiplicity of 1 as a root of cannot exceed
a log col). where 0 is absolute constant. Applying this result to the polynomial
A(a)
T2W we conclude that the multiplicity of 1 as root of ( is at most a (2n 1)(1 + log 12W).
Then, by (TO) we can write U, (a:) vi
2- (a) as (1 Q)))) where k I jdst (n, W) = av (2n 1)(1 + log 12W) 2 and ((a) is a continuous function satisfying Q(1) + 0. the pair of strategies T) is ddot(nn, (n. W) --sensitive optimal, we have
(1 a) --)))-d (n.W) (U. (a) us o5 (a))
lim (1 (1-a)* a)* 00 pes (n, (n, (1-a))-mm.WW)00 Q(a),
v lim
a+11
a-1
and so Q(1) > 0. It follows that
lim (1 - a)" (a) = lim (1 -
2
for any d. Using similar arguments it is possible to show also that
lim (1 - a)a (o. - o. (a) 2
for any d and any strategy o' of player Min. We conclude that (a,, r) d-sensitive optimal for any and so also Blackwell optimal.
B.2 Proof for Section 3.2
Proof of Theorem 3.8
Given 0, let D. be the constant provided by Theorem 3.7 Let be any
real root the polynomial different from 1, be its degree and p = _d =²=x C be its minimal polynomial. Since is root of A, it follows that P divides A, and so we have d < 2n 1 and M(P) < M(A) (see Section 1.3 of (CMP87). Besides, note that M ((A < 12W v 2n by Landau's
bound Lan05 If > De, then holds, and so we have
2 1| > (m/4+s) d log log M(P) (#/4+c) / (2n 1) log(2n 2n 1) log M(A)
2 e (m/4+ely Ingg 1) log( 12W (2W/22)) /2m)
Assume now that d < D.. By Lemma B.1 it follows that |z 1-1
Then, since
2H(M(14))
H(P) s MP)), we have
1
2z - 11/2
2d+1 (PH 121
D.+1 (11 20.+IM(A)
2D. +1 DD+
12W /2n (
Setting log (20++1 (D+1)
conclude that A has no zeros in the interval Ja 1
C Proof for Section 4
C.1 Proof of Proposition 4.1
We now detail the proof Proposition 4.1
We first provide the exact formula for the polynomial A(a) considered in Section Given pair of stationary strategies (a, 7), let po,7 be the transition matrix and ror be the vector of instantancous rewards induced by (a, and let us define Q == M pa. and D=.7(a) == det (MI aQ*.T).
Since it is known that (1,"" (a)) =(T - ,o ,r using Cramer's formula for the inverse
23

---

of matrix and Laplace's cofactor extension, it follows that (a) 06 (a) for any state i, where
Ma(a)
Don (a)De' (()
( = o' (a)
E cof (MT - (a)T(a) cof joff -a0i--a01s)))
(1I)
We now proceed bound the degree and the coefficients of A. In the next two propositions, we assume that Q row-stochastic matrix, with Q N
M
Proposition C.1. The polynomial det(MI aQ) is of the form Ek axa", where laxl s (*) M
Proof. We have
- aaQ) MMaa)
(12)
k=
where C& (Q) is the k-th compound matrix of Q. Since the entries of C& (Q) are minors of Q of size k x k. and ΣØ=1 Qij M for each -,...,76 , conclude that the absolute value of all the
entries (Q) are less than or equal to M The result now follows from 12 and the fact that (Q) of size (1)) (*)-
It is worth noting that the result in the previous proposition is tight when Q = MI. n), Proposition C.2. For each i.j {1,...,mk) the (i,j) cofactor of the matrix MI aQ is of the form O agal, where |ax| S ("=²)
Proof. The (i,j) cofactor of the matrix MI - aQ is given by
(-1)it) det al) (-1)tt) (-a) M- (r((a(())((()
(13)
k=
where J and R are the (i,j) sub-matrices of I and Q respectively, adja (J) is the k-th higher adjugate matrix of J, and C₁ (I) is the k-th compound matrix of R. Since adje (J) has just one non-zero entry per row, of absolute value one, in the proof of Proposition C. we conclude that the absolute value of all the entries of (adja (C& (R)) are less than or equal to * The result now follows from [13 and the fact that (adj, (G)
of size ("x*) ("*))
By Propositions C.1 and C.2 form D2n-1 bya where
both terms appearing in the polynomial A defined in 11 are of the
lbk| S nWM2
Σ
("=1)
n
sti=k,sn- 1,15
Σ
n n-
k k-1 (1)
Mick-lsn-a 1i55n
(2n (2re k
1)
<nWM2n-1
nW
2n-1 2n-11
by Vandermonde's Identity. Therefore, we can rewrite A as Σ
2n-1 k= ctat, where lckl S
2n W.W. 2n 12m-1). 1 This concludes the proof of Proposition 4.1
24

---

C.2 Other proofs for Section 4
To use the Lagrange bound, we consider the polynomial E + A(1 -)), which can be rewritten as
2n-1
A (1 - c)= Σ
(-1)'d'
(14)
1=0
where 9: = Ex=r 2n-1 k=
Ck (t)))
Then, using Proposition 4.1 and the identity Σx=y (g)) = 2 (7))
we have
19:1 S
2n-1
Σ
2nW 2
16 ( 1) ()²)
(2n 10-1
(2M2))2
121 2n -
(15)
for all i (O....,.2 2n -1.. 1}.
Proposition C.3. Let be the smallest index such that 9j + 0 in 14 23-1
Then, the polynomial
e ( 6) has no zeros in the interval J0, 22(2M))a-1
Proof. As in the proof of Lemma B.I we apply the Lagrange bound (Theorem اروا 2 1 since 9j * 0 and 93 E Z. Then, for any i ii l...., 2n 1}, have
3.2g
Note that
|g Iga
1g
2
(2M))22--211-)
nW (2M) (44)
by 15) and (5. The proposition now follows from Theorem 3.2
Proof of Corollary 4.2 Note that the function j
is convex and attains its
(2M) (11))
minimum at j
13 n 1.. Then, by Proposition
we conclude that no function a: + v, TT (a)
2
8/ (a:) has zeros in the interval ]1
1[. The corollary now follows from the
nW (2M) 20 (3n))
discussion in Section 2
Proof of Corollary 4.3 Let (o",T") be a pair of discount optimal strategies for the discount factor
2mindd22 - 111-1
a', where a' satisfies
< a' <1
>:W22))an1( (mintd 12. 181
As in the proof for the deterministic case, in the first place assume that there exist strategy r and state i such that ( is satisfied, and let d' be the smallest value satisfying (9) By (7). follows that d' < d and that lim (1 (1-a)--0 -a--d" (v,"
(a) of x" it (a:) = 0 for all d" < d'.
If the game unichain, there exist two polynomials p(a) and q(a) such that p(1) + 0, (() * and ((a) (1 a) (a) .r" (a) of : (()).. where A is the polynomial defined in [11
considering the pairs of strategies (a", and (o*,T). Then, we have
lim (1-a)
(ug (a) of (a)) 0 a=1-
lim (1 a1) a)- -dd" A(a)
a-+1
for all d'. We conclude that go
+1++1 0 and g8 +2 + 0 in 14
Thus, by 7 and
Proposition C.3 it follows that es .7" (a) v (a) < 0 for 1 m2
< < 1.
(2713)
Since the function j (2M))nn
23-1
convex and attains its minimum at n 1J. and
-=ー1 d' S d, conclude that uf (a) 1u (a) < 0 for .W(2M)) (ingd++2 3-1)
1.
Thus, particular we have of of discount optimal strategies for a'.
(a') uf (al) < 0, contradicting the fact that (a", r*)
a pair
Now, if we assume that there exist strategy and state such that g is satisfied, using similar arguments as above we arrive at a contradiction.
This shows that (a", -T)) is pair of d-sensitive discount optimal strategies.
25

---

Remark C.4. Setting M = 1 in our bounds for the stochastic case do not recover our results for the deterministic case (Section Bp. This is because, the case of deterministic transitions, we can exploit the "path then circuit structure" of the discounted value functions, as highlighted in Section
C.3 Proof of Theorem 4.5
Proof. The proof follows similar arguments to the ones in the proof of Theorem 3.8 so given > let D. be the constant provided by Theorem 3.7
Let be any real root of the polynomial A different from 1, d be its degree and P Ei= Caa" be its minimal polynomial. Since is a root of A, follows that divides A, and so we have d s 2n - and (P) & M(A). Besides, note that by Proposition 4.1 and Landau's 's bound [an05 have MA) 2nW 22W (2)
If d > De. then holds, and have
1 (z/44t) M(P) (x/44+e) / (2n log( log ((A)
2 (1//440)/
log( (ox log Maw (222m=11))
Assume now that d s De. By Lemma B.1 it follows that Iz 15-1 1 (H(P)(()))
(21)) Then, since
H(P) & M(P), we have
1
1
d+1) 2 1 2d11((())
D.+h 2D. ((A)
2D ( 22 MPn-- ((ten-))))
))
[27
Setting a, = log 22.+1 +1 ) conclude that A has zeros in the interval JaMa, 1[. This (1b)))
shows that (rew S (Ma-
26


Reviews:
[{"review_id": "MiFzMOHCHt", "reviewer": "Reviewer_jDrr", "summary": "This paper studies refinements of the mean-payoff criterion in two-player zero-sum perfect-information stochastic games, focusing on Blackwell optimality and its generalization through d-sensitive optimality. The authors introduce new bounds on the d-sensitive threshold \\alpha_d​ that interpolates between mean-payoff and Blackwell optimality. The paper employs the methods and toolkits from separation bounds on algebraic numbers and shows their results can improve bounds for the Blackwell threshold. These thresholds are critical for understanding the algorithmic complexity of computing optimal strategies, as solving discounted games typically requires O(1/(1−α)) iterations.", "questions": "- The results seem to be more technically heavy than a usual Neurips paper, would it be more suitable for a more theoretical audience to review such as COLT or ALT?\n- Perhaps I am not the right reviewer for this paper, but I wonder what could be the insights and takeaways for practitioners in their design and analysis of real-world RL algorithms?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength \n\n- The paper did a reasonably good job introducing to me the concepts of sensitive optimality and Blackwell\nOptimality. The techniques of separation bounds, algebraic roots, Mahler measures, and multiplicity theorems from algebraic number theory are completely new to me, and I am surprised at how it can be used in a learning problem. There seems to be many new ideas in the analysis of this problem (especially over another neurips paper [GCP23]), though The technical analysis is well beyond my comfort zone, so I cannot make a good judgement call.\n- The problem is well-motivated to generalize this fundamental concept of Blackwell optimality to sensitive optimality. The cited statement of “one of the pressing questions in reinforcement learning” is a good showcase. \n-  The paper clearly acknowledged the limitations of their results.\n\nWeakness\n\n- I am not sure if the problems studied by this paper fits into the theme of Neurips, or its result might be interesting to a general audience at this conference. \n- A notation table can help us quickly parse through your technical results.\n- Typos: the left/right square brackets throughout this paper are sometimes not matched", "was_revised": true, "final_justification": "Overall, I recommend an acceptance of this paper given its solid technical depth. That said, I still have concerns whether this topics is interested to a general audience of NeurIPS, but I see this as a rather minor concern.", "rebuttal": "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.\n\n## Response to your questions: \n\n**1. Fit for NeurIPS.** \n\nWe 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. \n\nIndeed, 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.\n\nFrom 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:\n\n* a recent paper on average-reward robust MDPs (a setup equivalent to stochastic games) won a best paper award at AAAI 2023 [0];\n* two papers on multiplayer games were oral presentations at NeurIPS 2022 [1,2];\n* a paper on adaptively solving repeated games won an outstanding paper award at ICML 2023 [3]. \n\nWe will take care to more explicitly connect our contributions with these lines of work in the revised version.\n\n**2. On the practical takeaways.**\n\nWe will do our best to revise our paper to better highlight the main takeaways for practitioners. Our contributions in this sense are twofold:\n\n- *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). \n\n- *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. \n\nLet 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].\nWe will use the additional space to highlight these connections.\n\n\n\n## Conclusion:\n\nWe 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.\n\n**References**\n\n[0] Wang, Y., Velasquez, A., Atia, G., Prater-Bennette, A., & Zou, S.. Robust average-reward markov decision processes. AAAI 2023.\n\n[1] Cai, Y., Oikonomou, A., & Zheng, W.. Finite-time last-iterate convergence for learning in multi-player games. NeurIPS 2022.\n\n[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.\n\n[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.\n\n[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.\n\n[5] Brown, N., & Sandholm, T.. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science 2018.\n\n[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.\n\n[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.\n\n[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.\n\n[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.\n\n[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"}, {"review_id": "2PoAlOOuKM", "reviewer": "Reviewer_zUfR", "summary": "The paper obtains bounds on the d-sensitive ($\\alpha_d$) and Blackwell thresholds ($\\alpha_{BW}$) for stochastic games. The bounds improve upon existing results. Deterministic and general stochastic games are considered.", "questions": "1. The clarification regarding MDPs mentioned in the weaknesses section can be clarified.\n2. Is there an assumption of smoothness on the rewards function in either the MDP or the stochastic games? Or is it not needed due to the finite state space?", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths :\n\n1. A thorough analysis of the different regimes of the stochastic games parameter is provided.\n2. A variety of techniques are used to show the bounds.\n\n\nWeaknesses:\n\n1. The comparison tables can be improved - the results of MDP should be presented separately from those of stochastic games. \n2. Since the MDPs may be such that the reward function depends on both the current and next states maybe a clarification for the definition of MDPs considered can be detailed, along with its affects on the results on $\\alpha_{bw}$.", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time in reviewing our paper and we thank you for your positive score. We answer your questions below.\n\n**Question 1: clarification**\n\n- 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). \n\n- 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). \n\n\n[0] Filar, J., & Vrieze, K. (2012). Competitive Markov decision processes. \n\n[1] Neyman, A., & Sorin, S. (Eds.). (2003). Stochastic games and applications.\n\n**Question 2: smoothness**\n\nYou 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.\n\n# Conclusion:\n\nWe 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."}, {"review_id": "n05Mog68fz", "reviewer": "Reviewer_Ut7d", "summary": "The authors study two‑player zero‑sum perfect‑information stochastic games and ask how close the discount factor \n$\\alpha$ needs to be to $1$ before the optimal discounted strategies are already optimal for more farsighted criteria.\nIn particular, they consider the notion of Blackwell optimality – strategies that remain optimal for every $\\alpha$ sufficiently close to $1$, and an intermediate notion called d‑sensitive optimality that interpolates between mean‑payoff (for $d=-1$) and Blackwell optimality (for $d$ approachng infinity).\nThe authors use heavily algebraic tool such as Lagrange separation bound and Mahler‑measure bounds to derive new thresholds on $\\alpha$ that yield substantial quantitative improvements compared to the bounds in the prior works.", "questions": "1. Does author have some guess on whether the fact that some bounds are exponentially close to $1$ are in inherent or limitations of the analysis.\n2. Adding game instances where thresholds are close to $1$ would help calibrate how tight the theory is.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths. \n1. The paper uses sophisticated algebraic methods such as Lagrange bounds and Mahler‑measure techniques. \n2. The explicit bounds improve previous results by up to a factor of $Ω(n)$, where $n$ is the size of the game, for the Blackwell optimality threshold, and, for the first time, bound the threshold for $d$-sensitive optimality for general values of $d$. This tightens the best-known estimates for the complexities of computing Blackwell/$d$-sensitive optimal strategies.\n3. The paper is technical in nature: even with the connection between Blackwell threshold and classic polynomial root separation results, to apply these results, non-trivial analysis is needed to control the coefficients of the polynomial showing up in differences of discounted value functions. \n\nWeaknesses.\n1. The paper does not construct explicit games that witness a gap between their upper bounds and information‑theoretic lower bounds. It will be nice if the authors can provide even some sub-optimal game construction to show how far we are from the optimal bounds for these thresholds.\n2. For stochastic game, the need for unichain structure limits applicability; relaxing this assumption is an open direction acknowledged by the authors.", "was_revised": true, "final_justification": "The reviewer has adequately addressed my questions. My attitude remains positive for the paper.", "rebuttal": "We thank you for your time reviewing our paper and for your positive evaluation. \n\n**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.\n\nThis 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. \n\nWe 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.\n\n[0] Dubickas, A. (1998). On algebraic numbers close to 1. Bulletin of the Australian Mathematical Society, 58(3), 423-434.\n\n**Conclusion:**\nWe 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."}, {"review_id": "vAtqjQ8Hej", "reviewer": "Reviewer_vJhT", "summary": "This paper studies how to find d-sensitive and Blackwell optimal strategies in two-player zero-sum perfect-information stochastic games. It provides new bounds on the d-sensitive threshold ( $\\alpha_d$ ) and the Blackwell threshold $\\left(\\alpha_{B w}\\right)$. These thresholds are important because they determine the complexity of finding these strategies by solving standard discounted games.\n\nThe paper's main contributions are the first bounds for $\\alpha_d$ when $d>-1$ and improved bounds for $\\alpha_{B w}$ . The authors use three techniques from algebraic number theory to derive their results: Lagrange bounds, Mahler measures, and root multiplicity bounds. They present results for both deterministic and stochastic games, showing which technique is best for different parameter settings.", "questions": "### Questions\n1. The multiplicity-based method fails for stochastic games (Remark 4.5). Can you provide more intuition on why the analysis doesn't carry over from the deterministic case?\n2. The paper offers three different bounds. Is this necessary due to the nature of the problem, or could a unified theory combine these techniques for a single, stronger bound?\n3. What are the main obstacles to extending the $\\alpha_d$ bound to general multi-chain games without the unichain assumption?\n4. Does your analysis offer any insight into what a \"hard\" game instance (i.e., one requiring a very high discount factor) might look like?", "limitations": "The paper correctly identifies its main limitations.\n1. The bounds do not yet lead to polynomial-time algorithms.\n2. The $\\alpha_d$ bound for stochastic games is limited to the unichain case.\n3. The analysis is entirely theoretical, lacking empirical validation.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. The paper provides the first explicit bounds for the d-sensitive threshold $\\alpha_d$ (for $d>-1$ ), which is a new contribution to the field.\n2. The use of advanced tools from algebraic number theory (Lagrange bounds, Mahler measures, multiplicity theorems) is innovative and leads to stronger results than prior work.\n3. Clear Improvements: The new bounds on the Blackwell threshold $\\alpha_{B w}$ improves over existing results, particularly in their dependence on the number of states, $n$.\n4. The paper is well-organized. It clearly presents the problem, the methods, and the results. The summary tables are helpful for comparing the different bounds.\n\n### Weaknesses\n1. The improved bounds still lead to algorithms with superpolynomial complexity. Therefore, the work does not yet yield efficient, practical algorithms for finding Blackwell optimal strategies.\n2. The bound on $\\alpha_d$ in the general stochastic case requires a unichain assumption, which limits the result's applicability.\n3. The work is entirely theoretical, with no experiments to indicate how tight the bounds are in practice.", "was_revised": true, "final_justification": "The rebuttal is satisfactory, and I am going to maintain the positive rating.", "rebuttal": "We thank you for taking the time to review the paper. We address your questions below.\n\n# Response to questions.\n\n**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).\n\nFor 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.\n\n**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: \n* 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.\n* The Mahler bound is stronger than Lagrange in some regimes (ex: $W = O(1)$) but not in others ($W = \\exp(\\Theta(n))$). \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\n\nAs 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:\n* the number of states and the “granularity” of the games (integers $W$ and $M$ in our paper)\n* the deterministic or stochastic character of the Markov chains induced by strategies\n* the multiplicity of $1$ as a root of some polynomials $\\Delta(\\alpha)$ associated with the games\n\nAdditionally, 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).\n\n**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 \n$$\\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):\n$$\\lim_{\\alpha \\rightarrow 1} (1-\\alpha)^{d} (v^{\\sigma*,\\tau*}(\\alpha) - v^{\\sigma*,\\tau}(\\alpha) )= 0$$\nas some conditions on the polynomial $\\Delta(\\alpha)$:\n$$\\lim_{\\alpha \\rightarrow 1} (1-\\alpha)^{d-2} \\Delta(\\alpha)= 0.$$\nControlling 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.\n\n**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.\nMore 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.\n\n**On limitations.**\nWe 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.\n\nMore 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].\n\n# Conclusion\nWe 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.\n\n**References**\n\n[0] Wang, Y., Velasquez, A., Atia, G., Prater-Bennette, A., & Zou, S.. Robust average-reward markov decision processes. AAAI 2023.\n\n[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.\n\n[2] Cai, Y., Oikonomou, A., & Zheng, W.. Finite-time last-iterate convergence for learning in multi-player games. NeurIPS 2022.\n\n[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.\n\n[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.\n[5] Brown, N., & Sandholm, T.. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science 2018.\n\n[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."}]

Author rebuttal:

Meta-review: This paper considers two-player perfect-information zero-sum games, whereby it provides improved bounds for the Blackwell threshold, while for the $d$-sensitive threshold, it is the first work to give results beyond the $d=-1$ case. The results are in part based on a variety of non-trivial algebraic techniques, and though a potential concern was raised by Reviewer jDrr about the fit for NeurIPS, I believe that these techniques (along with the results themselves) could certainly be of general interest to the reinforcement learning and algorithmic game theory communities, whose presence at NeurIPS is well established. As the reviewers are additionally in support of the paper, I recommend acceptance to the conference.
Decision: Accept (poster)