{"id":"d34a4df2-c2cc-42fc-973b-4604924d5dfd","arxiv_id":"2506.18545","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For perfect-information stochastic games, this paper derives the first explicit upper bounds on the d-sensitive discount threshold (for d≥0) and improved upper bounds on the Blackwell threshold.","lead":"For two-player perfect-information stochastic games, this paper provides the first upper bounds on the 'd-sensitive' discount threshold and sharper bounds on the Blackwell threshold. The result tells algorithm designers how close to 1 the discount factor must be to guarantee farsighted optimal play in games and reinforcement learning.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3 is proven only for stationary deterministic strategies, but the statement quantifies over all strategies; the missing reduction to stationary deviations should be supplied.","rationale":"The paper's algebraic core is convincing: Lemma 3.1's degree and coefficient bounds follow from the path-plus-circuit structure of deterministic stationary strategies, and the Lagrange, Mahler, and multiplicity bounds are applied cleanly. The reader's weakest assumption (the elementary path/circuit decomposition) is sound. However, the proof of the central deterministic threshold theorem does not connect the finite set of stationary strategy pairs to the theorem's quantification over all strategies. This is a real gap in exposition, though it is repairable by a standard MDP reduction argument. Because the gap is fillable and does not affect the algebraic bounds themselves, the conditional-accept verdict should stand, but the authors should be asked to either add the reduction step or restrict the theorem statements to stationary strategies. This differs from the reader's identified weakest assumption, hence the disagreement on which assumption is most load-bearing.","tokens_in":20359,"tokens_out":56825,"duration_ms":517655,"concrete_test":"Add a lemma: for a fixed stationary deterministic strategy of one player, the opponent's problem is a finite MDP, so any history-dependent deviation τ is dominated, in the d-sensitive order near α=1, by a stationary deterministic τ'. Then replay the proof of Theorem 3.3 with τ' replacing τ; if the contradiction at α′ survives, the theorem covers all strategies. If not, restate the thresholds for stationary strategies.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 3.3 (and Corollary 4.3) derives a contradiction from a violating strategy τ in (7) and then applies Lemma 3.1 / Proposition 4.1 to the polynomial Δ associated with the pairs (σ*,τ*) and (σ*,τ). These lemmas require both strategies to be stationary and deterministic: the deterministic run is represented as a path plus a circuit, and the stochastic cofactor formula is for stationary policies. However, Definition 2.2 and the threshold α_d are stated for arbitrary history-dependent strategies, and the proof never justifies that a violation by a history-dependent τ implies a violation by a stationary deterministic τ. The standard repair is to fix σ* and observe that Max's problem is a finite one-player MDP, in which the supremum over history-dependent policies is attained by a stationary policy (and symmetrically for Min). This reduction, which preserves the d-sensitive order near α=1, is not present in the paper. As written, the main deterministic bound on α_d — and hence the Blackwell bound Corollary 3.4 — is established only for stationary optimal strategies. If the intended statement is only for stationary strategies, the definitions and theorem statements should say so; if it is for all strategies, the reduction lemma is needed.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies two-player zero-sum perfect-information stochastic games with integer rewards bounded by W and transition probabilities with common denominator M. It defines the d-sensitive threshold α_d and the Blackwell threshold α_Bw, and gives upper bounds on these thresholds in terms of n, W, and M. In the deterministic case, Theorem 3.3 bounds α_d by 1 − 1/(24W * binom(2n, min{d+4,n})), and combining this with a multiplicity result (Theorem 3.5) yields an improved α_Bw bound (Theorem 1.5). In the stochastic case, Theorems 4.1–4.4 give bounds based on Lagrange separation and Mahler measures, with the α_d bound derived under a unichain assumption. The proofs model differences of discounted value functions as polynomials Δ, bound their degrees and coefficients, and then apply algebraic root-separation results.","tokens_in":20566,"tokens_out":25541,"duration_ms":246105,"significance":"If the results hold, they are the first upper bounds on α_d for d ≥ 0 and improve the known bounds on α_Bw by a factor of Ω(n) compared with [AM09] and [GCP23]. The use of Lagrange bounds, Mahler measures, and multiplicity theorems to derive parameter-free threshold bounds is original and of clear interest to algorithmic game theory and reinforcement learning. The coefficient bounds and the algebraic separation arguments are checkable and largely coherent. However, the manuscript currently lacks a reduction from history-dependent strategies to stationary deterministic strategies in several key proofs, so the main theorems as stated are not fully established.","major_comments":[{"comment":"The proof of Theorem 3.3 takes a violating Max strategy τ from (7) and applies Lemma 3.1 to the polynomial Δ associated with (σ*,τ*) and (σ*,τ). Lemma 3.1 is proved only for pairs of stationary deterministic strategies, using the path-plus-elementary-circuit decomposition of a run. Definition 2.2 and the thresholds α_d and α_Bw are stated for arbitrary history-dependent strategies, and the manuscript does not supply a reduction showing that a violation by a history-dependent strategy implies a violation by a stationary deterministic one. The same gap appears in the proof of Corollary 4.3, where the polynomial Δ from (11) is only defined for stationary strategies, and in the proof of Theorem 3.5. As written, the deterministic bound on α_d and its consequences in Corollary 3.4 and Theorem 1.5, as well as the stochastic unichain bound on α_d, are established only for stationary optimal strategies. The standard repair is to fix σ*, observe that Max's problem is a finite one-player MDP, and use the existence of stationary deterministic optimal policies for the d-sensitive (lexicographic) criterion; a symmetric argument handles Min. This reduction lemma should be stated and proved explicitly.","section":"Section 3, Appendix B.1 (proof of Theorem 3.3); also Section 4, Appendix C.2 (proof of Corollary 4.3)"},{"comment":"The multiplicity argument applies the quoted Theorem 2.1 of [BEK99] to the polynomial Δ(α)/12W and concludes a bound on the multiplicity of 1 as a root. As stated, the cited theorem involves the constant coefficient c_0 and the quantity log|c_0|, so it requires c_0 ≠ 0; however, Δ(0) can vanish, for instance when two deterministic runs have the same first reward. The proof does not explain how to handle this case. Since Δ has integer coefficients bounded by 12W, the gap is fixable by dividing by the zero at α=0 and noting that the first nonzero coefficient has absolute value at least 1/(12W), but this argument is absent and is needed for the claimed multiplicity bound that underlies Theorem 1.5.","section":"Appendix B.2, proof of Theorem 3.5"}],"minor_comments":[{"comment":"The statements of Theorems 1.2–1.5 say that the game satisfies 'Theorem 1.1'; the reference should be to Assumption 1.1.","section":"Section 1, Theorems 1.2–1.5"},{"comment":"In the displayed chain of inequalities, the step from the expression involving 2^{(i-1)/(i-j)} and A^{1/(i-j)} to the claimed lower bound 2^{i-1}/(nW(2M)^{2n-1} binom{2n-1}{j+1}) is not immediate and should be justified, for instance by observing that A = nW(2M)^{2n-1} ≥ 16 for n ≥ 2.","section":"Appendix C.2, proof of Proposition C.3"},{"comment":"The proof of the binomial inequality (5) is written as an induction but the base case and the role of the condition m ≥ 3 are not stated clearly; a short explicit proof would improve readability.","section":"Appendix B.1, proof of Lemma B.1"}],"recommendation":"major_revision","confidential_remarks":"The central algebraic technique is promising and the coefficient bounds appear sound, but the missing stationary-deterministic reduction is a genuine gap in the main theorems. If the authors add the reduction lemma and patch the BEK99 application, I expect the paper to be publishable. The paper is within the scope of cs.GT and should be considered after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Julien,\n\nQuick take on 2506.18545. The paper delivers the first quantitative upper bounds on the d-sensitive threshold α_d for d ≥ 0 in deterministic perfect-information stochastic games, and it improves the known bounds on the Blackwell threshold α_Bw using Lagrange, Mahler, and multiplicity separation arguments. The algebraic core is solid: the coefficient bounds on the difference polynomial (Lemma 3.1, Proposition 4.1), the root-separation lemmas, and the derivations of the threshold bounds all check out. The unichain stochastic extension (Corollary 4.3) is also new and coherent. This is a real advance in a subfield where previously only α_{-1} had bounds.\n\nThe soft spots are real but repairable. The proof of Theorem 3.3 as written only handles violations by stationary deterministic strategies. Definition 2.2 quantifies over all history-dependent strategies, and the reduction from a history-dependent deviator to a stationary one is never supplied. In a finite discounted MDP, if a history-dependent τ beats the candidate optimal pair at some α' near 1, then some stationary deterministic τ' does too, so the missing step is standard and the theorem is likely true. Still, the manuscript currently has a gap: either add that reduction or restrict the definitions to stationary strategies, which would weaken the intended result. The stress-test note about this is on point.\n\nThe second issue is an overstatement in the introduction: the claim that the new bounds improve on [AM09] by a factor Ω(n) in -log(1-α_Bw) is not true when W and M are constant—there the ratio is Θ(log n), not Ω(n). It should be stated regime-dependently.\n\nThe appendix is long but checkable; I did not find an actual error in the main inequalities. The citation pattern is fine—the GCP23 and MK25 references are used for comparison, and the self-citations are legitimate.\n\nBottom line: I would send this to a serious referee. The contribution is genuine and the gap is a missing standard argument, not a fatal flaw. I would ask the authors to supply the stationarization reduction and correct the comparison claim. Also worth bringing to a reading group if you care about separation bounds in algorithmic game theory.","headline":"First bounds on d-sensitive thresholds in perfect-information stochastic games, with solid algebraic proofs, but the main deterministic theorem needs a stationarization step to cover history-dependent strategies as claimed.","tokens_in":21156,"tokens_out":4524,"would_cite":true,"duration_ms":48412,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A15","91A25","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"First explicit bounds on the discount thresholds for Blackwell and d-sensitive optimality in stochastic games.","keywords":["Blackwell optimality","d-sensitive optimality","stochastic games","discount factor threshold","algebraic number separation","Mahler measure","Lagrange bound","mean-payoff optimality"],"falsifier":"Enumerate all pairs of stationary deterministic strategies in a small deterministic perfect-information game, compute $\\Delta(\\alpha)$ from equation (3), and check whether any coefficient exceeds $12W$ in absolute value or whether any real root of $\\Delta$ lies in the interval $(1 - \\frac{1}{24W\\binom{2n}{n}}, 1)$; a single such root would refute the Blackwell-threshold bound of Corollary 3.4, and the analogous check with $\\binom{2n}{\\min\\{d+4,n\\}}$ would settle the d-sensitive bound.","tokens_in":20151,"feed_emoji":"🎲","tokens_out":15989,"duration_ms":134573,"temperature":0.7,"pith_summary":"This paper proves explicit upper bounds on the discount-factor thresholds that guarantee discounted-optimal strategies in two-player, zero-sum, perfect-information stochastic games are also Blackwell optimal or d-sensitive optimal. For deterministic games, the d-sensitive threshold satisfies $\\alpha_d \\le 1 - \\frac{1}{24W\\binom{2n}{\\min\\{d+4,n\\}}}$, the first such bound beyond the mean-payoff case $d = -1$, and the Blackwell threshold satisfies $\\alpha_{\\mathrm{Bw}} \\le 1 - \\frac{1}{24W\\binom{2n}{n}}$. Sharper Blackwell bounds are obtained with Mahler-measure separation and with a multiplicity argument showing that $O(\\sqrt{n\\log W})$-sensitive optimality already implies Blackwell optimality, far below the classic $n-2$. In general stochastic games the Blackwell threshold is bounded via Lagrange and Mahler techniques, and the d-sensitive threshold under a unichain assumption. These thresholds matter because solving a discounted game with a discount factor above them yields the desired strategies, at a cost that scales like $(1-\\alpha)^{-1}$.","feed_headline":"First bounds on the d-sensitive discount threshold","feed_subtitle":"New thresholds tell how close to 1 the discount factor must be for Blackwell- and d-sensitive-optimal play.","key_machinery":"The load-bearing object is the numerator polynomial $\\Delta(\\alpha)$, defined for deterministic games by $\\Delta(\\alpha) = (1-\\alpha^q)(1-\\alpha^{q'})(v^{\\sigma,\\tau}_i(\\alpha) - v^{\\sigma',\\tau'}_i(\\alpha))$ (equation (3)) and for stochastic games by a cofactor formula (equation (11)). Its zeros inside $(0,1)$ are exactly the discount factors at which the relative order of two stationary strategy pairs can change. Three tools separate those zeros from $1$: the Lagrange bound, which gives any nonzero root $z$ of an integer polynomial a modulus separated from $0$, and applied to $\\Delta(1-\\varepsilon)$ produces the binomial-divisor thresholds; a Mahler-measure inequality, which controls $|z-1|$ from below in terms of the degree and Mahler measure of $z$'s minimal polynomial; and the Borwein–Erdélyi–Kós multiplicity theorem, which bounds the multiplicity of $1$ as a root of a bounded-coefficient integer polynomial and thereby fixes how large $d$ must be for $d$-sensitive optimality to imply Blackwell optimality.","core_discovery":"The central discovery is that the thresholds are controlled by the real zeros of one polynomial per pair of stationary deterministic strategies. Clearing denominators in a difference of discounted value functions gives $\\Delta(\\alpha) = (1-\\alpha^q)(1-\\alpha^{q'})(v^{\\sigma,\\tau}_i(\\alpha) - v^{\\sigma',\\tau'}_i(\\alpha))$, which has degree at most $2n-1$ and coefficients of absolute value at most $12W$ in deterministic games (Lemma 3.1). Any discount factor at which two strategy pairs swap optimality order is a zero of such a $\\Delta$ in $(0,1)$, so an interval free of zeros below $1$ is a threshold. Applying the Lagrange root bound to $\\varepsilon \\mapsto \\Delta(1-\\varepsilon)$ yields $\\alpha_d \\le 1 - \\frac{1}{24W\\binom{2n}{\\min\\{d+4,n\\}}}$ (Theorem 3.3) and $\\alpha_{\\mathrm{Bw}} \\le 1 - \\frac{1}{24W\\binom{2n}{n}}$ (Corollary 3.4); applying a Mahler-measure separation inequality gives $-\\log(1-\\alpha_{\\mathrm{Bw}}) \\le O\\!\\left(\\max\\{\\sqrt{n\\log n\\,\\log(\\sqrt{n}W)},\\log(\\sqrt{n}W)\\}\\right)$ (Theorem 3.8); and applying the Borwein–Erdélyi–Kós multiplicity bound shows that $\\bar d_{\\mathrm{det}} = O(\\sqrt{n\\log W})$-sensitive optimal strategies are already Blackwell optimal (Theorem 3.5), yielding the sharper $\\alpha_{\\mathrm{Bw}}$ bound of Theorem 1.5. In stochastic games the same plan, with $\\Delta$ built from cofactor matrices, gives $\\alpha_{\\mathrm{Bw}} \\le 1 - \\frac{2^{\\lfloor 2n/3\\rfloor - 2}}{nW(2M)^{2n-1}\\binom{2n-1}{\\lfloor 2n/3\\rfloor}}$ (Corollary 4.2), a Mahler analogue (Theorem 4.4), and, under a unichain assumption, an $\\alpha_d$ bound (Corollary 4.3).","pith_inferences":["The binomial divisors in the Lagrange bounds look like an artifact of the change of variable $\\alpha = 1 - \\varepsilon$; a polynomial-specific separation bound for the alternating-coefficient pattern of $\\Delta$ might yield wider root-free intervals and therefore smaller thresholds.","The multiplicity result suggests that deterministic policy-iteration schemes which truncate Laurent expansions at order $n-2$ could truncate at order $O(\\sqrt{n\\log W})$ instead, reducing arithmetic cost per policy improvement; the paper does not explore this computational consequence.","Because the unichain assumption enters exactly where the multiplicity approach fails for non-deterministic games, constructing a multichain game whose $\\alpha_d$ violates the unichain bound would show the assumption is essential rather than an artifact of the proof.","The Mahler-measure technique used here for thresholds could plausibly transfer to other settings with rational value functions of the same cofactor form, such as robust MDPs with average reward; this is speculative and not claimed by the authors."],"forward_implications":["For any fixed $d$, d-sensitive optimal strategies of a deterministic game can be computed in pseudo-polynomial time by solving a discounted game at $\\alpha = 1 - \\frac{1}{24W\\binom{2n}{\\min\\{d+4,n\\}}}$, extending the previous mean-payoff-only result.","The Lagrange-based Blackwell bound improves the prior stochastic-game bound by a factor $\\Omega(n)$ in $-\\log(1-\\alpha_{\\mathrm{Bw}})$, and the Mahler-based bound gives $O(\\sqrt{n\\log n\\,\\log W})$ when rewards are small, with the two bounds complementary across regimes.","In deterministic games every $\\bar d = O(\\sqrt{n\\log W})$-sensitive optimal strategy is Blackwell optimal, so the sensitive order needed can be much smaller than $n-2$ when $\\log W = o(n)$.","The threshold bounds convert any algorithm for discounted games into an algorithm for Blackwell- and d-sensitive-optimal strategies, with complexity depending on the stated $(1-\\alpha)^{-1}$ factors.","In general stochastic games the Blackwell threshold is bounded without any chain-structure assumption, while the d-sensitive bound currently requires the unichain assumption."],"supporting_citations":[{"why":"Defines the stochastic game model and establishes existence of stationary discounted-optimal strategies.","marker":"[Sha53]"},{"why":"Shows existence of stationary deterministic Blackwell-optimal strategies in perfect-information stochastic games, the object the thresholds govern.","marker":"[LL69]"},{"why":"Supplies the Lagrange root-modulus bound (Theorem 3.2) used to separate zeros of Delta(1-epsilon) from 0.","marker":"[Yap00]"},{"why":"Provides the Mahler-measure inequality separating algebraic numbers from 1, used in Theorems 3.8 and 4.4.","marker":"[Dub95]"},{"why":"Bounds the multiplicity of 1 as a root of integer-coefficient polynomials, the basis of the deterministic Blackwell-threshold improvement.","marker":"[BEK99]"},{"why":"Gives the bound M(P) <= sqrt(sum |c_k|^2) used to convert coefficient bounds into Mahler-measure estimates.","marker":"[Lan05]"},{"why":"Establishes the mean-payoff threshold bound for d = -1 that Theorem 1.2 recovers and extends to all d.","marker":"[ZP96]"},{"why":"Provides the prior Blackwell-threshold bound for stochastic games that this paper improves by a factor Omega(n).","marker":"[AM09]"},{"why":"Gives the multiplicity-based result for deterministic MDPs that Theorem 1.5 recovers for two-player games.","marker":"[MK25]"},{"why":"Formalizes d-sensitive optimality through Laurent-series coefficients and supplies the n-2 threshold that Theorem 3.5 improves.","marker":"[Put14]"}],"fun_headline_variants":["First d-sensitive threshold bounds for stochastic games","Improved Blackwell threshold bounds from algebraic numbers","Root separation gives new optimality thresholds","Polynomial bounds for sensitive and Blackwell optimality","Closer to 1: new thresholds for optimal play"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The deterministic bounds depend on the lemma that every run of a stationary deterministic strategy pair is a simple path followed by a simple cycle with at most $n$ states, which bounds $\\Delta$'s degree by $2n-1$ and its coefficients by $12W$; if optimal strategies could not be taken deterministic or runs could be arbitrarily tangled, the bounds would fail.","fun_headline_variants_meta":{"raw":{"variants":["First d-sensitive threshold bounds for stochastic games","Improved Blackwell threshold bounds from algebraic numbers","Root separation gives new optimality thresholds","Polynomial bounds for sensitive and Blackwell optimality","Closer to 1: new thresholds for optimal play"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000527,"raw_usage":{"total_tokens":2709,"prompt_tokens":1279,"completion_tokens":1430,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":895,"completion_tokens_details":{"reasoning_tokens":1362}},"tokens_in":895,"tokens_out":1430,"duration_ms":11735,"temperature":1.0,"reasoning_tokens":1362,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:49:16.923166+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all pairs of stationary deterministic strategies in a small deterministic perfect-information game, compute $\\Delta(\\alpha)$ from equation (3), and check whether any coefficient exceeds $12W$ in absolute value or whether any real root of $\\Delta$ lies in the interval $(1 - \\frac{1}{24W\\binom{2n}{n}}, 1)$; a single such root would refute the Blackwell-threshold bound of Corollary 3.4, and the analogous check with $\\binom{2n}{\\min\\{d+4,n\\}}$ would settle the d-sensitive bound.","supporting_citations":[],"review_version":2}