Research map / Learning theory and algorithms / Submodular and game algorithms
Thresholds for sensitive optimality and Blackwell optimality in stochastic games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives new upper bounds on the Blackwell threshold and the d-sensitive threshold for two-player perfect-information zero-sum stochastic games, using Lagrange root-separation, Mahler-measure, and multiplicity-of-root arguments.
Problem
Bounding the discount factor above which discount-optimal strategies are guaranteed to be Blackwell optimal (Blackwell threshold) or d-sensitive optimal (d-sensitive threshold) in perfect-information zero-sum stochastic games, which controls the cost of computing such strategies via discounted-game
Approach
Reduce the question to locating roots of a polynomial numerator of differences of discounted value functions and separate those roots from 1 using Lagrange's root bound, Mahler-measure separation (Dubickas/Mignotte-Waldschmidt), and Borwein-Erdélyi-Kós multiplicity bounds, extending d-sensitive threshold bounds beyond d=-1.
Key results
- For deterministic games, alpha_d <= 1 - 1/(24 W binom(2n, min{d+4,n})), giving the first d-sensitive threshold bounds beyond d=-1.
- For stochastic games, alpha_Bw <= 1 - 2^{floor(2n/3)-2}/(nW(2M)^{2n-1} binom(2n-1, floor(2n/3))) via Lagrange bound.
- Multiplicity approach gives deterministic-game Blackwell-optimality degree d = O(sqrt(n log W)), improving on the n-2 bound in regimes where log W = o(n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Lagrange root-separation bounds for Blackwell-threshold analysis | Perfect-information stochastic games · Blackwell threshold | -log(1-α_Bw) bound: improves upon [cite] and [cite] by a factor Ω(n) | Helped |
| Use Mahler-measure root separation to bound the Blackwell threshold | Perfect-information stochastic games · Blackwell threshold | -log(1-α_Bw) bound | Mixed |
| Bound the d-sensitive threshold beyond the mean-payoff case d=-1 | Deterministic perfect-information stochastic games · d-sensitive threshold | α_d upper bound: 1-\frac{1}{24 W{2n\choose {\min \{ d+4 , n\}}}} | Helped |
| Use the multiplicity approach to show a smaller sufficient sensitivity level | Deterministic perfect-information stochastic games · Blackwell optimality | sufficient d: O\left(\sqrt{n\log(W)}\right) | Helped |
| Apply the multiplicity approach to stochastic games rather than deterministic games | Perfect-information stochastic games · Blackwell optimality | sufficient d: n-2\ll \bar{d}^{\mathrm{sto}}(n,W) | Hurt |
| Seek a d-sensitive threshold bound without the unichain assumption | Non-deterministic perfect-information stochastic games · d-sensitive threshold | α_d upper bound | No clear effect |
Surprising findings
- The multiplicity-based approach does not improve over the n-2 bound in the stochastic (non-deterministic) case.
Limitations
- Bounds on alpha_Bw are still exponentially close to 1, so no weakly- or quasi-polynomial algorithm results.
- Bounds on alpha_d for stochastic games require a unichain assumption.
- No lower bounds are provided.
Experimental setup
Baselines: Friedmann-style bounds for SGs MDP Blackwell threshold bounds
Builds on: Blackwell optimality Veinott d-sensitive optimality Lagrange bound Mahler measure separation (Dubickas)
Closest papers by meaning
- Extensive-Form Game Solving via Blackwell Approachability on Treeplexes (NeurIPS 2024 · similarity 0.88)
- Efficient $\Phi$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games (NeurIPS 2024 · similarity 0.87)
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.86)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.86)
- Robust PAC Learning of Concurrent Stochastic Games (NeurIPS 2026 · similarity 0.86)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.