PaperlayerView exact revision on arXiv

Source-linked AI summary

Sharper bounds on the thresholds for sensitive and Blackwell optimality

Xavier Allamigeon, Stéphane Gaubert, Julien Grand-Clément, Ricardo Katz

arXiv:2610.10295v1cs.GT

TL;DR

In perfect-information stochastic games, the paper addresses how to bound the discount thresholds above which discount-optimal policies are Blackwell or d-sensitive optimal. It uses reduced comparison-polynomial families and root separation to derive improved Blackwell bounds and the first multichain stochastic d-sensitive bounds.

  • Problem

    The paper seeks bounds on Blackwell and d-sensitive thresholds in terms of game parameters, where knowing a threshold enables computing more farsighted optimal policies through discount-optimal policies.

    Source: §1 · p. 1

  • Method

    It builds reduced polynomial comparison families from adjacent policies and applies root-separation bounds, with Matrix Forest Theorem analysis controlling polynomial degree and height.

    Source: §1 · p. 2, §3.1 · p. 6, §3.4.1 · p. 8

  • Results

    The approach improves Blackwell-threshold bounds and provides the first d-sensitive threshold bounds for multichain stochastic games.

    Source: §1 · p. 2, §7 · p. 23

  • Takeaways & Limitations

    The reduced-family degree and height bounds for the minimal polynomial of ρBw are tight, while the threshold results are refined for deterministic instances.

    Source: §1 · p. 2, §7 · p. 23

    For fixed W, deterministic Blackwell bounds still leave a gap between O(n) and Ω((n log(n))^(1/3)).

    Source: §4.3.2 · p. 14

Abstract

from arXiv · show

In perfect-information two-player stochastic games, the notions of Blackwell and sensitive optimality provide generalizations of the classical mean-payoff optimality and discount optimality criteria to account for more farsighted preferences. We provide bounds on the Blackwell threshold $\alpha_{\sf bw}$ and the $d$-sensitive thresholds $\alpha_{\sf d}$, defined as the smallest discount factors above which discount optimal policies coincide with Blackwell optimal policies and $d$-sensitive optimal policies respectively. Our refined bounds improve upon prior work by focusing on ``reduced'' families of polynomials and, crucially, our bounds are tight in terms of controlling the degrees and heights of the minimal polynomials of the Blackwell thresholds. We apply classical root separation based on Mahler's and Cauchy's bounds to our reduced families to derive the strongest upper and lower bounds on $\alpha_{\sf bw}$ in the literature, and we are the first to obtain bounds on $\alpha_{\sf d}$ in the multichain stochastic setting.

1 Introduction.

The paper bounds Blackwell and d-sensitive thresholds for perfect-information stochastic games, where knowing a threshold lets discount-optimal policies be used to obtain more farsighted optimal policies. It develops reduced comparison-polynomial families to improve threshold bounds and control polynomial degree and height.

1 Introduction.

  • Knowing αBw or αd allows discount-optimal policies at a sufficiently high discount factor to recover Blackwell or d-sensitive optimal policies, with computation complexity controlled by (1 − α)−1.The paper seeks bounds in terms of the number of states n, reward bound W, and transition-probability denominator M.Source: §1 · pp. 1–2
  • Prior work established threshold bounds, but their tightness in polynomial degree, height, and resulting thresholds was unclear.Earlier Blackwell upper bounds can be as large as exp(c√n log(n)), while lower-bound results include deterministic instances with order exp(c n^(1/5)√log(n)).Source: §1 · p. 2
  • The paper introduces reduced comparison families based on Veinott vectors for adjacent policies, with tight bounds on the degree and height of the minimal polynomial of ρBw.The Matrix Forest Theorem supports improved polynomial degree and height bounds.Source: §1 · p. 2
  • The reduced-family root-separation bounds improve prior upper and lower bounds on the Blackwell threshold, with the stochastic hard-instance bound tight in M and a remaining gap for deterministic instances.These are bounds on ρBw, which yield the corresponding opposite-direction bounds on αBw.Source: §1 · p. 2
  • The paper gives the first bounds on d-sensitive thresholds in the multichain stochastic setting, using analysis of adjacent policies’ recurrent classes.For deterministic instances, its bounds on ρd also improve upon prior work.Source: §1 · p. 2

2 Preliminaries.

The preliminaries define the game and its optimality criteria, state the finite-integral-data assumptions used for threshold bounds, and explain how stochastic games reduce to induced MDPs. This reduction transfers threshold bounds from those MDPs to the game.

2.1 Perfect-information stochastic games.

  • A perfect-information stochastic game assigns states to Min or Max; stationary deterministic policies can be considered without loss of generality.The setting has finite states and actions, integer rewards, and rational transition probabilities.Source: §2.1 · pp. 3–4
  • Blackwell optimality means remaining discount optimal for all discount factors sufficiently close to 1; d-sensitive optimality forms a hierarchy, with Blackwell optimality corresponding to all d.Mean-payoff optimality is the d = −1 case, and d-sensitive optimality for d implies it for d′ ≤ d.Source: §2.1 · p. 3
  • The thresholds mark when discount-optimal policies become Blackwell or d-sensitive optimal, and their bounds matter because discount-optimal computation scales with (1 − α)−1.For any d, αd ≤ αBw.Source: §2.1 · pp. 3–4
  • Threshold bounds are expressed using n states, an integer-reward magnitude bound W, and the common transition-probability denominator M.Rational rewards can be scaled to integral rewards without changing the optimal-policy sets.Source: §2.1 · p. 4
  • The interest rate ρ = (1 − α)/α approaches 0 as α approaches 1, so upper bounds on α correspond to lower bounds on ρ.The paper states its main results in terms of lower bounds on the interest-rate thresholds.Source: §2.1 · p. 4

2.2 From stochastic games to Markov decision processes.

  • Fixing one player’s policy induces an MDP; Proposition 2.6 transfers lower bounds on the induced MDP thresholds to the game’s Blackwell and d-sensitive thresholds.MDPs induced by a game satisfying Assumption 2.5 also satisfy that assumption.Source: §2.2 · pp. 4–5

3 Complete and reduced families of comparison polynomials.

This section develops reduced comparison-polynomial families for locating the Blackwell threshold and bounds their degrees and heights using adjacent-policy comparisons and forest-weight estimates. It also gives constructions illustrating the bounds’ tightness, including an MDP whose threshold is the unique positive root of an irreducible degree-n−1 polynomial.

3.3 Proof of Theorem 3.6

  • The Blackwell threshold is a positive root of a polynomial in any reduced comparison family, so its smallest positive root gives a lower bound.The proof uses policies that are discount optimal near the threshold but not Blackwell optimal, then identifies an adjacent-policy comparison polynomial that vanishes at the threshold.Source: §3.1 · p. 5, §3.3 · pp. 7–8

3.1 Main results

  • Theorem 3.7 gives a reduced family with degree at most n−1 and a height bound depending on the MDP’s integral data.The paper frames smaller degree and height as the way to strengthen root-separation bounds.Source: §3.1 · p. 6, §3.4.2 · p. 9
  • The degree and height bounds are essentially tight: for specified n, M, and W, an MDP can have a Blackwell-threshold minimal polynomial of degree n−1 and the stated height.The construction applies when 2W−1 is prime and M is not divisible by 2W−1.Source: §3.1 · p. 6

3.2 Veinott’s comparison vectors

  • Veinott’s comparison vectors characterize discount optimality by checking signs against adjacent policies rather than all policies.For adjacent policies, the comparison-vector condition is equivalent to the relevant value-function ordering.Source: §3.2 · pp. 6–7

3.4.1 Constructing a reduced family

  • The reduced family clears comparison-vector denominators with a positive integer-coefficient polynomial, preserving the signs and zeros needed for policy comparisons.The construction uses the characteristic polynomial Dσ(ρ), whose positivity for ρ > 0 makes the resulting polynomials’ signs and zeros track the comparison vectors.Source: §3.4.1 · p. 8

3.4.2 Bounding the degree and height of the reduced family

  • The degree and height analysis uses variations of the matrix-tree theorem to express characteristic-polynomial coefficients through weighted directed forests.The coefficients are integer-bounded using the MDP’s integral data.Source: §3.4.2 · p. 9

3.4.2 Bounding the degree and height of the reduced family.

  • Forest-weight sums are bounded by M^k using stochasticity, and the reduced polynomial Δ(ρ) has degree at most n−1.Source: §3.4.2 · p. 10

3.5 Proof of Theorem 3.8.

  • An n-state MDP construction makes the Blackwell threshold the unique positive root of a degree n−1 polynomial.The polynomial is p(ρ) = (2W−1)M^(n−1)ρ(1+ρ)^(n−2)−1.Source: §3.5 · p. 11
  • The threshold polynomial is irreducible by Eisenstein’s criterion, so it is the minimal polynomial of the Blackwell threshold.The construction assumes 2W−1 is prime and does not divide M.Source: §3.5 · p. 11
  • Subtracting W−1 from every reward preserves the Blackwell thresholds and puts the integer rewards between −W and W.Source: §3.5 · p. 11

4 Bounds on the Blackwell thresholds.

The section applies root-separation methods to reduced comparison polynomials to bound the Blackwell threshold, then constructs stochastic and deterministic instances with thresholds close to 1. The stochastic construction yields an explicit bound, while the deterministic bounds leave a gap for fixed rewards.

4.1 Root separation methods

  • Cauchy’s and Mahler-measure root-separation methods yield lower bounds on ρBw from reduced comparison polynomials, with the Cauchy-based bound stronger in the general stochastic setting.The Mahler-based approach can be useful for deterministic instances where the measure is better controlled.Source: §4.2 · pp. 12–13

4.3.1 Stochastic instances

  • For stochastic instances, some MDP has ρBw ≤ 1/((2W −1)M^(n−1)), matching the general lower bound’s M^(n−1) term and improving prior bounds in the M exponent and W factor.The construction’s bound relies on a chain of transition probabilities 1/M and is nearly vacuous when M = 1.Source: §4.3.1 · pp. 13–14, §4.3.2 · p. 14

4.3.2 Deterministic instances

  • For deterministic instances, the paper constructs discount thresholds from integer polynomials with roots near 1, yielding an upper bound on ρBw while leaving a gap between O(n) and Ω((n log(n))^(1/3)) for fixed W.The authors say closing the gap likely requires resolving the multiplicity of real-polynomial roots at 1, which appears difficult.Source: §4.3.2 · p. 14

5 Bounds for the d-sensitive thresholds.

This section develops bounds on d-sensitive thresholds for games satisfying Assumption 2.5, reducing the problem to MDPs and using Laurent-series criteria and polynomial root bounds. It also sharpens bounds for deterministic instances.

5.1 A sufficient criterion for d-sensitive optimality

  • A policy is d-sensitive optimal exactly when its value-function Laurent coefficients from order −1 through d are lexicographically minimal.The criterion is stated for comparisons with every other policy.Source: §5.1 · p. 15
  • Nonnegative lexicographic comparison coefficients through order d+1 against every adjacent policy suffice for d-sensitive optimality.This improves [Vei69, Theorem 4] by requiring consideration of adjacent policies only.Source: §5.1 · pp. 16–17

5.2 Polynomials admitting ρ_d as a root

  • When finite, the d-sensitive threshold ρ_d is a positive root of a polynomial in the reduced family P_d, with additional structure on its first nonzero coefficients.The theorem’s polynomial has degree at most n−1.Source: §5.2 · p. 18
  • The zero initial coefficients of threshold polynomials enable stronger positive-root separation using a variant of Cauchy’s bound.The supplied passage describes the separation result but does not provide its numerical bound.Source: §5.2 · p. 18

5.2 Polynomials admitting ρd as a root.

  • Theorem 5.12 bounds the d-sensitive threshold by reducing it to positive roots of comparison polynomials, which satisfy an explicit lower bound.The argument applies to games satisfying Assumption 2.5 by considering the MDPs they induce.Source: §5.2 · p. 19

5.3 The case of deterministic instances.

  • For deterministic instances with M = 1, Corollary 5.14 gives a sharper bound on the d-sensitive threshold under Assumption 2.5.The improvement follows from tighter control of the comparison quantities for deterministic MDPs.Source: §5.3 · p. 19
  • If every nonzero adjacent-policy comparison vector has order at 0 at most d̄, then any d̄-sensitive optimal policy is Blackwell optimal.This criterion does not itself require a deterministic MDP.Source: §5.3 · p. 20
  • For deterministic MDPs, trajectory structure and coefficient bounds yield an upper bound on comparison-vector order, enabling a lower-order sensitivity criterion for Blackwell optimality.The value-function differences are represented using coefficients bounded in absolute value by 8W; applying the order bound gives Corollary 5.20’s Blackwell-threshold bound.Source: §5.3 · pp. 20–21
  • The multiplicity approach gives uninformative order bounds for stochastic instances, while a Mahler-based root-separation argument establishes a Blackwell-threshold bound for instances with M = 1.For stochastic instances, the cited approach yields an order bound of Θ(n), already known to be no better than n.Source: §5.3 · p. 21

6 Discussion.

The discussion compares root-separation approaches and emphasizes that the paper’s reduced comparison family has the best degree and height bounds, which are tight. Bound quality depends on the game setting and parameter regime; closing the deterministic threshold gap remains open.

6 Discussion.

  • Prior work differs in whether it separates roots from 1 or from 0, so its comparison families require care when comparing degree and height.The paper distinguishes approaches in [ACSSU24] [GGCK26] from those in and its own work.Source: §6 · p. 21
  • The reduced family has the smallest degree and better coefficient bounds than prior comparison families, and these degree and height bounds are tight.The paper attributes this to adjacent-policy comparison vectors and the Matrix Forest theorem; its upper bound on ρBw also improves asymptotically in n over [ACSSU24].Source: §6 · p. 22
  • The paper gives bounds for multichain stochastic d-sensitive thresholds, where [GGCK26] required a unichain assumption.Its bound on d̄ also improves the bound establishing that d̄-sensitive optimality implies Blackwell optimality.Source: §6 · p. 22
  • For stochastic instances, the Cauchy bound is better than the Mahler bound, while deterministic instances have no uniformly best separation method across log(W) regimes.For deterministic instances, Mahler, Cauchy, and multiplicity approaches can each be optimal in some regimes; multiplicity is at least as strong as Cauchy.Source: §6 · p. 22
  • Closing the upper–lower bound gap for deterministic Blackwell thresholds remains open, and improving comparison-family bounds requires stronger root separation or a different approach.The discussion notes that the polynomial degree and height bounds are already tight for stochastic and deterministic instances.Source: §6 · pp. 22–23

7 Conclusion.

The paper develops a unified approach to bounding Blackwell and d-sensitive thresholds in perfect-information stochastic games. Reduced comparison families and matrix-forest analysis yield sharper, essentially tight polynomial degree and height estimates, improved Blackwell bounds, and the first general multichain stochastic d-sensitive bounds.

7 Conclusion.

  • Reduced comparison families based on adjacent policies and matrix-forest analysis yield sharper, essentially tight degree and height estimates for the polynomials.The paper refines the bounds for deterministic instances and leaves open closing the Blackwell threshold gap, especially for deterministic games.Source: §7 · p. 23
  • The approach yields improved Blackwell threshold bounds and the first general d-sensitive threshold bounds for multichain stochastic games.The main open questions include identifying subclasses where both thresholds are polynomially close to 1.Source: §7 · p. 23

A Proof of Theorem 2.6.

The supplied proof passages reduce a stochastic-game claim to properties of induced MDPs and give polynomial constructions and root arguments used in threshold bounds. They also state a multiplicity bound and an MDP example for Blackwell thresholds.

A Proof of Theorem 2.6.

  • Part (a) follows from the definition of the MDPs induced by a stochastic game.Source: A Proof of Theorem 2.6 · p. 25
  • An MDP with n + 7 states, rewards in {0, 1}, and transitions in {0, 1, 1/2, 1/2−ϵ, ϵ} provides a Blackwell-threshold example.Source: A Proof of Theorem 2.6 · p. 25
  • Theorem 4.10 adapts the polynomial construction of from coefficients in {0, 1, −1} to coefficients bounded by H.The constructed polynomial has a real root greater than 1 and close to 1; a sign change of its factor ϕ establishes the root.Source: A Proof of Theorem 2.6 · p. 26
  • The constructed polynomial yields a root α in (0, 1) by taking the reciprocal of a root γ greater than 1.The passages establish that γ−1 is small and that 1−α is smaller than γ−1.Source: A Proof of Theorem 2.6 · p. 28
  • The multiplicity of F at 0 is bounded by A(N−j)(1 + log(H/|Q(0)|)), with |Q(0)| ≥ 1.Source: A Proof of Theorem 2.6 · p. 28

D.1 Proof of Theorem 5.18.

The proof represents deterministic-policy values through paths leading into cycles, then derives polynomial comparison bounds from that structure. A seven-state construction shows the coefficient-height bound 8W is tight.

D.1 Proof of Theorem 5.18.

  • A deterministic policy’s trajectory has a path-then-cycle form, giving its value as a discounted path sum plus a discounted cycle sum divided by 1−α^q.Here p and q are the path and cycle lengths.Source: §D.1 · pp. 28–29
  • The policy graph decomposes into disjoint circuits and their upstream state sets, each of which forms a river network leading to one circuit.For a state in a set of size n_h, the path and circuit lengths satisfy p_h ≤ n_h−1 and p_h+q_h ≤ n_h.Source: §D.1 · p. 29
  • The comparison polynomials are rewritten in ρ, with G having order at most two at 0; the deterministic coefficient bounds include height at most 8W.The value-function polynomial has integer coefficients bounded by 2W, and the derived polynomial ˜F has height at most 8W.Source: §D.1 · pp. 29–30
  • A seven-state deterministic MDP construction shows that the bound 8W from Proposition 5.18 is tight.Source: §D.1 · p. 30
Loading 2610.10295v1…