Pith. sign in

REVIEW 2 major objections 3 minor 54 references

Thresholds for sensitive optimality and Blackwell optimality in stochastic games

T0 review · 2 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read First explicit bounds on the discount thresholds for Blackwell and d-sensitive optimality in stochastic games.

desk verdict 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. read the letter →

arxiv 2506.18545 v1 pith:5FZEIKVX submitted 2025-06-23 cs.GT

Stéphane Gaubert , Julien Grand-Clément , Ricardo D. Katz This is my paper · ORCID
classification cs.GT MSC 91A1591A2568Q25
keywords Blackwelloptimalityd-sensitivestochasticgamesdiscountfactorthresholdalgebraicnumberseparationMahlermeasureLagrangeboundmean-payoff
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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}$.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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).

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

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.

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 (2)
  1. [Section 3, Appendix B.1 (proof of Theorem 3.3); also Section 4, Appendix C.2 (proof of Corollary 4.3)] 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.
  2. [Appendix B.2, proof of Theorem 3.5] 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.
minor comments (3)
  1. [Section 1, Theorems 1.2–1.5] The statements of Theorems 1.2–1.5 say that the game satisfies 'Theorem 1.1'; the reference should be to Assumption 1.1.
  2. [Appendix C.2, proof of Proposition C.3] 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.
  3. [Appendix B.1, proof of Lemma B.1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: thresholds are defined independently and the bounds follow from external algebraic separation results.

full rationale

The quantities being bounded, alpha_Bw and alpha_d, are defined in Sections 1 and 2 directly from discount-optimality and d-sensitive-optimality thresholds, with no reference to the bounds later derived. The upper bounds in Theorems 3.3, 3.8, 4.2 and 4.4 are obtained from explicit coefficient and degree bounds on the polynomial Delta (Lemma 3.1 and Proposition 4.1) combined with external algebraic separation results: the Lagrange bound, Dubickas' Mahler-measure bound, and the Borwein-Erdelyi-Kos multiplicity bound. No parameter is fitted to the quantity being bounded; the only inputs are the game parameters n, W and M. The single self-citation to [GCP23] appears in comparisons and in the remark that Assumption 1.1 is necessary for meaningful bounds; it is not a load-bearing premise of any theorem and does not make the derived bounds depend on the paper's own conclusions. A possible concern, noted by a skeptical reader, is that the proof of Theorem 3.3 applies Lemma 3.1 to pairs involving the possibly history-dependent violating strategy tau, while Lemma 3.1 is stated for stationary deterministic strategies; the missing reduction to stationary deviations would be a correctness or completeness gap, not a circularity, because the resulting bound is not an input to itself. Similarly, the unichain assumption in Corollary 4.3 is an explicit hypothesis, not a hidden restatement of the conclusion. Therefore no circular step is identified.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No free parameters are fitted: the bounds depend only on n, W, M and on absolute constants from cited theorems. The axioms are either standard results in algebraic number theory or explicitly stated domain assumptions (Assumption 1.1, perfect-information and zero-sum setting, unichain structure where used). No new entities (particles, forces, dimensions) are introduced.

assumptions (7)
  • domain assumption Integer rewards bounded by W and transition probabilities with common denominator M (Assumption 1.1)
    Needed so that the coefficients of Δ are integers of bounded size; the paper notes [GCP23, Prop 4.3] shows such an assumption is necessary for meaningful bounds.
  • domain assumption Perfect information and zero-sum setting: optimal strategies can be chosen stationary and deterministic
    Restricts to perfect-information SGs, following [Sha53, Gil57]; the polynomial Δ approach requires the finite set of deterministic strategy pairs.
  • domain assumption Unichain assumption in Corollary 4.3
    Needed to relate the coefficients of Δ to the Laurent series of the value difference in the non-deterministic case; without it only α_Bw is bounded.
  • standard math Lagrange separation bound (Theorem 3.2)
    Classical bound on the distance from a root to 0, used to separate roots of Δ from 1 via the change of variable ε=1-α.
  • standard math Dubickas's lower bound on |z-1| in terms of Mahler measure (Theorem 3.7)
    External theorem, used to obtain the Mahler-measure bounds in Theorems 3.8 and 4.4.
  • standard math Borwein-Erdélyi-Kós multiplicity bound (Theorem 2.1 of [BEK99])
    Used to bound the multiplicity of 1 as a root of Δ and to prove Theorem 3.5.
  • standard math Landau's bound M(P) ≤ sqrt(Σ|c_k|^2)
    Used to estimate the Mahler measure of Δ via its coefficients.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Thresholds for sensitive optimality and Blackwell optimality in stochastic games." pith.science (2026). https://pith.science/paper/5FZEIKVX

@misc{pith2026250618545,
  author       = {Pith},
  title        = {Pith review of: Thresholds for sensitive optimality and Blackwell optimality in stochastic games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5FZEIKVX}},
  note         = {Machine review of arXiv:2506.18545}
}
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.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 48 canonical work pages

  1. [1]

    Policy iteration algorithm for zero-sum multichain stochastic games with mean payoff and perfect information

    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 arXiv:1208.0446 , 2012

    work page Pith review arXiv 2012

  2. [2]

    Policy iteration for perfect information stochastic mean payoff games with bounded first return times is strongly polynomial

    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:1310.4953 , 2013

    work page Pith review arXiv 2013

  3. [3]

    Andersson and P

    D. Andersson and P. B. Miltersen. The complexity of solving stochastic games on graphs. In International Symposium on Algorithms and Computation , pages 112--121. Springer, 2009

    work page 2009

  4. [4]

    Boros, K

    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

    work page 2010

  5. [5]

    Borwein, T

    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

    work page 1999

  6. [6]

    Blackwell

    D. Blackwell. Discrete dynamic programming. The Annals of Mathematical Statistics , pages 719--726, 1962

    work page 1962

  7. [7]

    V. Boone. When do discounted-optimal policies also optimize the gain? arXiv preprint arXiv:2304.08048 , 2023

    work page Pith review arXiv 2023

  8. [8]

    R. A. Cuninghame-Green and P. Butkovic. The equation ax= by over (max,+). Theoretical Computer Science , 293(1):3--12, 2003

    work page 2003

Show all 54 references
  1. [9]

    Chatterjee, E

    K. Chatterjee, E. K. Goharshady, M. Karrabi, P. Novotn \`y , and . Z ikeli \'c . Solving long-run average reward robust mdps via stochastic games. arXiv preprint arXiv:2312.13912 , 2023

    2023 arXiv

  2. [10]

    E. M. Clarke, T. A. Henzinger, H. Veith, R. Bloem, et al. Handbook of model checking , volume 10. Springer, 2018

    2018

  3. [11]

    Cerlienco, M

    L. Cerlienco, M. Mignotte, and F. Piras. Computing the measure of a polynomial. Journal of Symbolic Computation , 4(1):21--33, 1987

    1987

  4. [12]

    Dewanto, G

    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

    2010 arXiv

  5. [13]

    Dewanto and M

    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

    2022

  6. [14]

    Dubickas

    A. Dubickas. On algebraic numbers of small measure. Lithuanian Mathematical Journal , 35:333--342, 1995

    1995

  7. [15]

    Friedmann

    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

    2009

  8. [16]

    E. A. Feinberg and A. Shwartz. Handbook of Markov decision processes: methods and applications , volume 40. Springer Science & Business Media, 2012

    2012

  9. [17]

    Frank and E

    A. Frank and E. Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Comb. , 7(1):49--65, 1987

    1987

  10. [18]

    Fujiwara

    M. Fujiwara. \"U ber die obere schranke des absoluten betrages der wurzeln einer algebraischen gleichung. Tohoku Mathematical Journal, First Series , 10:167--171, 1916

    1916

  11. [19]

    Grand-Cl \'e ment and M

    J. Grand-Cl \'e ment and M. Petrik. Reducing B lackwell and average optimality to discounted MDPs via the B lackwell discount factor. Advances in Neural Information Processing Systems , 36:52628--52647, 2023

    2023

  12. [20]

    Grand-Clement, M

    J. Grand-Clement, M. Petrik, and N. Vieille. Beyond discounted returns: Robust markov decision processes with average and blackwell optimality. arXiv preprint arXiv:2312.03618 , 2023

    2023 arXiv

  13. [21]

    Gillette

    D. Gillette. Stochastic games with zero stop probabilities. Contributions to the Theory of Games , 3(39):179--187, 1957

    1957

  14. [22]

    Gurvich, A

    V. Gurvich, A. Karzanov, and L. Khachiyan. Cyclic games and finding minimax mean cycles in digraphs. Zh. Vychisl. Mat. i Mat. Fiz , 28(9):1407--1417, 1988

    1988

  15. [23]

    Gaubert and S

    S. Gaubert and S. Sergeev. Cyclic projectors and separation theorems in idempotent convex geometry. Journal of Mathematical Sciences , 155:815--829, 2008

    2008

  16. [24]

    Hadamard

    J. Hadamard. \'E tude sur les propri\'et\'es des fonctions enti\`eres et en particulier d'une fonction consid\'er\'e par R iemann. Journal de Math\'ematiques Pures et Appliqu\'ees , 58:171--215, 1893

  17. [25]

    Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor

    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,...

    2010

  18. [26]

    Hansen, P

    T. Hansen, P. 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

    2013

  19. [27]

    Jin and A

    Y. Jin and A. Sidford. Towards tight bounds on the sample complexity of average-reward mdps. In International Conference on Machine Learning , pages 5055--5064. PMLR, 2021

    2021

  20. [28]

    J. L. Lagrange. Sur la résolution des équations numériques. Mémoires de l'Académie royale des Sciences et Belles-Lettres de Berlin , XXIII, 1769

  21. [29]

    E. Landau. Sur quelques théorèmes de M . P etrovitch relatifs aux zéros des fonctions analytiques. Bulletin de la Société Mathématique de France , 33:251--261, 1905

    1905

  22. [30]

    D. H. Lehmer. Factorization of certain cyclotomic functions. Annals of mathematics , 34(3):461--479, 1933

    1933

  23. [31]

    M. L. Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994 , pages 157--163. Elsevier, 1994

    1994

  24. [32]

    T. M. Liggett and S. A. Lippman. Stochastic games with perfect information and time average payoff. SIAM Rev. , 11:604--607, 1969

    1969

  25. [33]

    A. J. Lazarus, D. E. Loeb, J. G. Propp, W. R. Stromquist, and D. H. Ullman. Combinatorial games under auction play. Games and Economic Behavior , 27(2):229--264, 1999

    1999

  26. [34]

    Loff and M

    B. Loff and M. Skomra. Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games . In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , volume 297 of Leibniz ...

    2024

  27. [35]

    K. Mahler. On some inequalities for polynomials in several variables. J. London Math. Soc , 37(1):341--344, 1962

    1962

  28. [36]

    Mukherjee and S

    D. Mukherjee and S. Kalyanakrishnan. Howard's policy iteration is subexponential for deterministic M arkov D ecision P roblems with rewards of fixed bit-size and arbitrary discount factor. In International Conference on Automated Planning and Scheduling , 2025

    2025

  29. [37]

    Mignotte and M

    M. Mignotte and M. Waldschmidt. On algebraic numbers of small height: linear forms in one logarithm. Journal of Number Theory , 47(1):43--62, 1994

    1994

  30. [38]

    Narahari

    Y. Narahari. Game theory and mechanism design , volume 4. World Scientific, 2014

    2014

  31. [39]

    Oliu-Barton

    M. Oliu-Barton. New algorithms for solving zero-sum stochastic games. Mathematics of Operations Research , 46(1):255--267, 2021

    2021

  32. [40]

    A. Puri. Theory of hybrid systems and discrete event systems . University of California, Berkeley, 1995

    1995

  33. [41]

    M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming . John Wiley & Sons, 2014

    2014

  34. [42]

    S. M. Rump. Polynomial minimum root separation. Mathematics of Computation , 33(145):327--336, 1979

    1979

  35. [43]

    L. S. Shapley. Stochastic games. Proceedings of the national academy of sciences , 39(10):1095--1100, 1953

    1953

  36. [44]

    C. Smyth. Mahler measure of one-variable polynomials: a survey. In Number Theory and Polynomials , pages 322--349. Cambridge University Press, 2008

    2008

  37. [45]

    Sidford, M

    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 on Artificial Intelligence and Statistics , pages 2992--3002. PMLR, 2020

    2020

  38. [46]

    Y. Tang, M. Rowland, R. Munos, and M. Valko. Taylor expansion of discount factors. In International Conference on Machine Learning , pages 10130--10140. PMLR, 2021

    2021

  39. [47]

    A. F. Veinott(Jr.). Discrete Dynamic Programming with Sensitive Discount Optimality Criteria . The Annals of Mathematical Statistics , 40(5):1635--1660, 1969

    1969

  40. [48]

    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

    2024

  41. [49]

    J. Wang, M. Wang, and L. F. Yang. Near sample-optimal reduction-based policy learning for average reward MDP . arXiv preprint arXiv:2212.00603 , 2022

    2022 arXiv

  42. [50]

    C. K. Yap. Fundamental problems of algorithmic algebra , volume 49. Oxford University Press Oxford, 2000

    2000

  43. [51]

    The simplex and policy-iteration methods are strongly polynomial for the markov decision problem with a fixed discount rate

    Yinyu Ye. The simplex and policy-iteration methods are strongly polynomial for the markov decision problem with a fixed discount rate. Mathematics of Operations Research , 36(4):593--603, 2011

    2011

  44. [52]

    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

    2016

  45. [53]

    Zhang, S

    K. Zhang, S. M. Kakade, T. Basar, and L. F. Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. Journal of Machine Learning Research , 24(175):1--53, 2023

    2023

  46. [54]

    Zwick and M

    U. Zwick and M. Paterson. The complexity of mean payoff games on graphs. Theoret. Comput. Sci. , 158(1-2):343--359, 1996

    1996

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.