Pith. sign in

REVIEW 4 major objections 5 minor 49 references

Efficient Computation of Blackwell Optimal Policies using Rational Functions

T0 review · 4 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read By ordering rational functions near γ=1 symbolically, this paper obtains the first strongly polynomial algorithm for Blackwell-optimal policies in deterministic MDPs and the first subexponential bound for general MDPs.

desk verdict Promising symbolic-ordering approach to Blackwell-optimal policies, but the main transfer theorem is underproved and Algorithm 1 has an apparent typo; deserves a rigorous referee. read the letter →

arxiv 2508.18252 v1 pith:A6EQL2V3 submitted 2025-08-25 cs.AI

Dibyangshu Mukherjee , Shivaram Kalyanakrishnan This is my paper · ORCID
classification cs.AI
keywords BlackwelloptimalityMarkovdecisionprocessrationalfunctionsdiscountfactorpolicyiterationstronglypolynomialtimesubexponentialalgorithmdeterministicMDP
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

Blackwell-optimal policies are the ones that remain optimal for every discount factor sufficiently close to 1. They combine the stability of average-reward optimality with the flexibility of discounted optimality, but existing algorithms are expensive or numerically unstable near γ=1. This paper argues that the sign of any policy-improvement comparison can be decided symbolically, by ordering rational functions in the left-neighborhood of 1, so an algorithm can be run as if at γ=1 without numerical ill-conditioning. From that transfer it derives the first strongly polynomial algorithm for deterministic MDPs and the first subexponential expected-time algorithm for general MDPs, both with bounds independent of reward bit-size. A reader should care because these are the tightest complexity bounds known for computing Blackwell-optimal policies, and the method is a direct replacement for the comparison step in existing planning algorithms.

What carries the argument

The central object is the µ-ordering: a total order on rational functions obtained by factoring out powers of (1−x) and reading the sign of the residual at x=1. It agrees with ordinary numeric order on an interval (σ,1), so every comparison has a constant sign throughout the tail. Replacing max/min operations and sign tests in value-based MDP algorithms with µ-ordering produces a symbolic variant whose policy trajectory is identical to the base algorithm for all sufficiently high discount factors; this trajectory transfer carries the complexity bounds over to Blackwell optimality.

What would settle it

Run DetMDP2-Blackwell on a deterministic MDP while tracking the symbolic sign of every intermediate comparison; if any quantity d_i(s) or y_i(s) changes sign on some interval (τ,1), or an argmax tie resolves differently from the limiting order at 1, then the trajectory transfer in Theorem 4 fails. A concrete search could evaluate these intermediate functions numerically at γ = 1 − 10^−m for increasing m and compare the maximizing choices against the ones given by the first nonzero coefficient of the Laurent expansion at γ=1.

Watch

Extended reading notes

Core claim

The paper's central claim is that Blackwell optimality can be computed by lifting standard discounted-MDP algorithms into a symbolic domain where the discount factor stays a formal variable. Near γ=1 every value and action-value function is a rational function of γ; the paper defines the µ-ordering, a total order on such functions that agrees with the usual numerical order on some interval (σ,1). Replacing numeric max/min and sign checks by these symbolic comparisons simulates the trajectory of the base algorithm for all sufficiently large discount factors, so a Blackwell-optimal policy is recovered rather than a policy for one particular γ. On deterministic MDPs the adapted Karp-style algor

Load-bearing premise

The proofs assume that, past one fixed discount factor, every comparison the underlying algorithm makes—including the intermediate path-value maxima and the tie-breaking in the new algorithms—keeps the same sign; the paper explicitly verifies this only for stationary policy value functions.

Editorial extensions

If this is right

  • For deterministic MDPs, Blackwell-optimal policies can now be computed in strongly polynomial time O(n^4 k), independent of reward bit-size.
  • For general stochastic MDPs, a Blackwell-optimal policy can be found in expected poly(n,k)·exp(O(sqrt(n log n))) iterations, the first subexponential bound independent of input bit-size.
  • Three policy-iteration switching rules known for discounted MDPs—batch-switching, Howard's, and randomised simple policy iteration—transfer to Blackwell optimality with only polynomial overhead in their iteration bounds.
  • Because the symbolic comparison works at γ=1, the approach avoids the numerical instability that makes value iteration, policy iteration, and linear programming fail when the Blackwell threshold is exponentially close to 1.
  • Such exponentially high thresholds provably occur, so no fixed large discount factor can safely replace a direct Blackwell computation.

Reading between the lines

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

  • The trajectory-transfer idea would apply to any discounted-MDP algorithm whose intermediate comparisons could be frozen past a single threshold; extending Theorem 4 to cover finite-horizon substeps and tie-breaking would make the complexity transfer rigorous for a much broader class of algorithms.
  • The same sign-near-1 machinery could be adapted to N-discount optimality by comparing higher-order Laurent coefficients rather than just the first nonzero term, producing a hierarchy of algorithms for sensitive optimality criteria beyond Blackwell.
  • Because the symbolic order only needs the sign of a rational function's tail, approximate arithmetic with error controlled by the location of the nearest root below 1 might yield a practical numerical counterpart with rigorous guarantees, though the paper does not develop this.
  • The exponential lower bound on the Blackwell threshold suggests that any method that solves one discounted MDP at a single fixed γ cannot be general-purpose; this likely extends to learning algorithms that identify policies from finite samples, unless additional structural assumptions are imposed.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper proposes a symbolic computation framework for Blackwell-optimal (BO) policies in finite MDPs. It treats the discount factor as a symbolic variable, represents value and action-value functions as rational functions, and uses a total order (the mu-ordering) on such functions in a left-neighborhood of 1 to simulate the trajectory of existing discounted-MDP algorithms for all discount factors sufficiently close to 1. On this basis it claims: an O(n^4 k) algorithm for deterministic MDPs (DetMDP2-Blackwell), an O(n^7 k^3 log^2 n) max-gain variant, a poly(n,k) * exp(O(sqrt(n log n))) expected-iteration algorithm for general MDPs via Random-Facet, and polynomial-factor-preserving generalizations of three policy-iteration switching rules. The paper also constructs an MDP family whose Blackwell threshold is exponentially close to 1 and reports a proof-of-concept implementation.

Significance. If the central transfer theorem were fully established, the results would be a major advance: the first strongly polynomial algorithms for Blackwell-optimal policies in deterministic MDPs and the first subexponential expected bound for general MDPs independent of bit-size. The rational-function ordering lemma is simple and correct, and Appendix B's Laurent-series equivalence for the Q-V policy improvement is a useful and apparently correct contribution. The paper also ships reproducible code and experiments, which is commendable. However, the main correctness gap identified below -- Theorem 4 does not cover the quantities actually compared by the proposed algorithms -- makes the headline complexity claims currently unsupported. The paper reads as an extended abstract: several theorems are proof sketches and one pseudocode line contains an evident type error.

major comments (4)
  1. [Section 4.3, Theorem 4] The proof of Theorem 4 bounds only the roots of f_s^{i,j}(gamma)=V^{pi_j}_gamma(s)-V^{pi_i}_gamma(s), i.e., differences of stationary discounted policy values. But Algorithm 1 (lines 6, 9, 13-14) compares finite-horizon values d_i(s) and y_i(s), which are obtained by alternating max/min operations over paths and are not stationary policy values; a max of rational functions is only piecewise rational. Similarly, the policy improvement rules in Sections 5.2-5.4 and Algorithm 2 require the sign of Q^pi_gamma(s,a)-V^pi_gamma(s), which is a difference between an action-value under a one-step deviation and a stationary value, not a difference of two stationary value functions. The proof's concluding jump from 'value ordering' to 'policy preferences remains invariant' is therefore not justified. Tie-breaking is also not analyzed: the mu-ordering is a total order that may break ties differently
  2. [Section 5.1, Algorithm 1 and Theorem 5] Algorithm 1, line 10, has a type error: it sets y0(s) <- alpha_n(s), where alpha_n(s) is an action index, not a rational value. This overwrites the value computed on line 9 with an action label, making the algorithm's behavior undefined. In addition, the proof of Theorem 5 only counts the number of comparisons; it does not prove that the sequence of argmax decisions produces a Blackwell-optimal policy. The definition of gamma_1 quantifies over Phi in {D_i, Y_j}, but the proof never uses gamma_1 to establish trajectory invariance or correctness. The line must be corrected (presumably the minimizing index i for y0 should be stored in a separate variable) and a correctness argument must be supplied.
  3. [Section 5.3, Theorem 7] The proof of Theorem 7 is a sketch. The Random-Facet subexponential bound is for linear programs and abstract LP-type problems; the paper does not verify that the MDP policy graph with improving pairs (s,a) satisfying f^pi(s,a)>0 forms an LP orientation or an abstract objective function on which the Random-Facet recurrence applies. The line 'additional n^2 operations per recursive call' also does not account for the fact that the rational functions being compared may have degrees that grow with the recursion, nor does it bound the number of recursive calls in the MDP setting. Correctness is again entirely dependent on the missing extension of Theorem 4 to Q^pi-V^pi signs. The expected-iteration bound therefore needs a complete proof, not just a reference to the LP result.
  4. [Section 5.4] The generalization of policy iteration variants A1, A2, A3 is asserted in a single paragraph without a theorem, an algorithm, or a proof. The switching rules differ substantially (batch switching, Howard's simultaneous switching, and randomized single switching), and each involves tie-breaking choices and sets of improving pairs J^pi. The claim that each bound Bi is preserved up to a poly(n,k) factor under the Blackwell criterion requires a formal reduction showing that the same trajectory is followed for all gamma in (tau,1), including ties. This is especially important because B2 and B3 depend delicately on the switching rule. Please state the exact symbolic variants and prove the claimed bounds.
minor comments (5)
  1. [Section 2.1, gamma_Q definition] The displayed definition of gamma_Q is confusing: it uses Q^pi_gamma in the antecedent of the implication while quantifying over gamma. The intended meaning appears to be invariance of the sign of Q^pi_tau(s,a)-Q^pi_tau(s,a') for all tau in (gamma,1); please restate with clear quantifier order.
  2. [Section 5.1, Algorithm 1 lines 6 and 13] The max is over both the action a and the successor s', but the notation writes only 'dmax_{s' in S}' and leaves a free. The argmax expressions also lack bounds on both variables and have unmatched brackets. Please rewrite the pseudocode with explicit quantifiers and tie-breaking rules.
  3. [Section 4.2] The complexity statement says 'evaluating the polynomial at 1 up to its d-th derivative' and claims O(d^2); this is correct under Horner's method but should say 'up to the degree d' and specify the arithmetic model. Also, the complexity of comparing two rational functions is stated for polynomials of degree O(d); the paper should state explicitly why the rational functions appearing in the algorithms have degree O(n).
  4. [Appendix A] The derivation of the lower bound is compressed: the expressions for V^{pi_0}(u) and Q^{pi_0}(u,a_1) skip intermediate algebra and rely on unlabelled quantities such as V(alpha_{n/3+1}). Please expand the calculation and clearly specify the reward and transition structure of all chains, including the terminal states.
  5. [Throughout] Several equations have typographical issues: the abstract and body refer to 'M_{1-epsilon}' and 'epsilon -> 0' without formalizing the symbolic limit; Section 5.1 uses 'DetMDP2' without defining it; and some displayed inequalities (e.g., in Section 4.1) omit closing parentheses. A careful copy-edit is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: μ-ordering is an independent construction, γQ is a supporting lemma rather than a fitted input, and the trajectory-invariance gap is a correctness issue, not a circular reduction.

full rationale

The paper's central mechanism is the μ-ordering of rational functions near 1 (Section 4.1). This ordering is defined by the sign of the leading term at x=1, and Lemma 3 proves that it agrees with the actual ordering of the two functions throughout a left-neighborhood of 1. That is a genuine mathematical bridge, not a definitional restatement of Blackwell optimality. No parameter is fitted to data: the thresholds γ1 and γQ are defined from roots of rational functions, and the algorithms are not tuned to reproduce a desired output. The claims that DetMDP2-Blackwell, Max-Gain-Blackwell, and Random-Facet-Blackwell compute BO policies are transferred from the convergence of the corresponding discounted algorithms via Theorem 4. There is a real proof gap here: Theorem 4's proof only bounds roots of differences between stationary policy value functions V^{π_i}_γ(s) - V^{π_j}_γ(s), while Algorithms 1 and 2 also compare Q^π(s,a) - V^π(s) and finite-horizon quantities d_i, y_i. Those are rational functions with finitely many roots as well, so the intended argument can likely be repaired, but the written proof does not explicitly cover them. That is an incompleteness or correctness risk, not a circular reduction: the paper never defines the conclusion in terms of the premise, and no equation is shown to be its own input. The self-citation to Mukherjee and Kalyanakrishnan [37] is used for the existence of γQ and the inequality γbw ≤ γQ. This is a supporting lemma from the authors' prior work, but it is not a fitted value and not the basis of the paper's main derivations; the same finite-roots argument the paper itself uses would supply such a threshold. The paper also explicitly credits Hordijk et al. [18] for the symbolic-ordering idea and proves in Appendix B that its policy-improvement rule matches the Laurent-series rule of Miller and Veinott, so there is no ansatz smuggled in by citation and no renaming of a known result presented as new. Overall, the derivation chain is not circular; the principal concern is the unproved trajectory-invariance step, which is a correctness gap rather than a circularity.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

No fitted parameters in the main algorithms; the only hand-chosen constant is epsilon in the lower-bound construction. The paper relies on external algorithmic bounds and on an unproven extension of the trajectory invariance to non-stationary intermediate values.

free parameters (1)
  • epsilon = 0 < epsilon < 1/2, e.g., 1/4
    Free constant in the lower-bound MDP construction (Appendix A, Theorem 2). Any fixed epsilon in (0,1/2) yields threshold 1 - O(2^{-n/3}); not fitted to data and not used in the main algorithms.
assumptions (4)
  • standard math Value functions and Q-values of stationary policies are rational functions of gamma (Cramer's rule, Eq. 5-6).
    Used throughout Section 4.1-4.3 to justify mu-ordering; standard linear algebra.
  • standard math I - gamma P^pi is invertible for gamma in [0,1) for any stationary policy pi.
    Needed for Eq. 5 and for the absence of poles on [0,1); standard MDP theory.
  • domain assumption The cited algorithms (Madani et al. O(n^2 k) for discounted DMDPs; Post-Ye O(n^5 k^2 log^2 n) for max-gain; Random-Facet exp(O(sqrt(n log n))); PI bounds B1,B2,B3) have the stated correctness and complexity guarantees.
    All main theorems transfer these external bounds; if any cited bound is wrong or misquoted, the paper's bounds change. Locations: Sections 5.1-5.4.
  • ad hoc to paper Trajectory invariance extends to all quantities compared by the base algorithms, including finite-horizon d_i,y_i functions and tie-breaking choices, with a single global threshold tau (Section 4.3, Theorem 4).
    The proof in the paper only covers stationary policy value pairs; the extension to intermediate non-stationary functions and ties is asserted but not proven. This is the load-bearing assumption flagged in weakest_assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Computation of Blackwell Optimal Policies using Rational Functions." pith.science (2026). https://pith.science/paper/A6EQL2V3

@misc{pith2026250818252,
  author       = {Pith},
  title        = {Pith review of: Efficient Computation of Blackwell Optimal Policies using Rational Functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A6EQL2V3}},
  note         = {Machine review of arXiv:2508.18252}
}
abstract

Markov Decision Problems (MDPs) provide a foundational framework for modelling sequential decision-making across diverse domains, guided by optimality criteria such as discounted and average rewards. However, these criteria have inherent limitations: discounted optimality may overly prioritise short-term rewards, while average optimality relies on strong structural assumptions. Blackwell optimality addresses these challenges, offering a robust and comprehensive criterion that ensures optimality under both discounted and average reward frameworks. Despite its theoretical appeal, existing algorithms for computing Blackwell Optimal (BO) policies are computationally expensive or hard to implement. In this paper we describe procedures for computing BO policies using an ordering of rational functions in the vicinity of $1$. We adapt state-of-the-art algorithms for deterministic and general MDPs, replacing numerical evaluations with symbolic operations on rational functions to derive bounds independent of bit complexity. For deterministic MDPs, we give the first strongly polynomial-time algorithms for computing BO policies, and for general MDPs we obtain the first subexponential-time algorithm. We further generalise several policy iteration algorithms, extending the best known upper bounds from the discounted to the Blackwell criterion.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 48 canonical work pages

  1. [1]

    Simulation-Driven Reinforcement Learning in Queuing Network Routing Optimization

    F. Al-Ani, M. Wang, J. Charles, A. Ong, J. Forday, and V . Modi. Simulation-Driven Reinforcement Learning in Queuing Network Rout- ing Optimization. arXiv preprint arXiv:2507.18795, 2025

    work page Pith review arXiv 2025

  2. [2]

    Antonio, N

    C. Antonio, N. Muddasar, D. P. Giuseppe, and P. Giovanni. Reinforce- ment learning for intelligent healthcare applications: A survey.Artificial Intelligence In Medicine, 109:101964, 2020

    work page 2020

  3. [3]

    M. E. Aydin and E. Öztemel. Dynamic job-shop scheduling using re- inforcement learning agents. Robotics Auton. Syst. , 33(2-3):169–178, 2000

    work page 2000

  4. [4]

    C. C. Bennett and K. K. Hauser. Artificial intelligence framework for simulating clinical decision-making: A markov decision process ap- proach. Artif. Intell. Medicine, 57(1):9–19, 2013

    work page 2013

  5. [5]

    Blackwell

    D. Blackwell. Discrete Dynamic Programming. The Annals of Mathe- matical Statistics, pages 719–726, 1962

    work page 1962

  6. [6]

    Boone and B

    V . Boone and B. Gaujal. Identification of Blackwell Optimal Policies for Deterministic MDPs. In International Conference on Artificial In- telligence and Statistics, pages 7392–7424. PMLR, 2023

    work page 2023

  7. [7]

    K. L. Clarkson. Las Vegas Algorithms for Linear and Integer Program- ming When the Dimension is Small. J. ACM, 42(2):488–499, 1995

    work page 1995

  8. [8]

    Claudine, R

    B. Claudine, R. Guidolini, R. V . Carneiro, P. Azevedo, V . B. Cardoso, A. Forechi, L. Jesus, R. Berriel, T. M. Paixao, F. Mutz, et al. Self- Driving Cars: A Survey.Expert Systems with Applications, 165:113816, 2021

    work page 2021

Show all 49 references
  1. [9]

    Cordwell, Y

    S. Cordwell, Y . Gonzalez, and T. Tulabandhula. Markov Decision Process (MDP) Toolbox for Python. Website. URL: https://github. com/sawcordwell/pymdptoolbox (accessed on May 6, 2019), 2015

    2019

  2. [10]

    T. K. Das, A. Gosavi, S. Mahadevan, and N. Marchalleck. Solving Semi-Markov Decision Problems Using Average Reward Reinforce- ment Learning. Management Science, 45(4):560–574, 1999

    1999

  3. [11]

    E. V . Denardo. On Linear Programming in a Markov Decision Problem. Management Science, 16(5):281–288, 1970

    1970

  4. [12]

    E. V . Denardo. Computing a Bias-Optimal Policy in a Discrete-Time Markov Decision Problem. Operations Research, 18(2):279–289, 1970

    1970

  5. [13]

    C. Derman. On Sequential Decisions and Markov Chains. Management Science, 9(1):16–24, 1962

    1962

  6. [14]

    Dewanto and M

    V . Dewanto and M. Gallagher. A nearly Blackwell-optimal policy gra- dient method. arXiv preprint arXiv:2105.13609, 2021

    2021 arXiv

  7. [15]

    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

  8. [16]

    Grand-Clément and M

    J. Grand-Clément and M. Petrik. Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor. In Proc. NeurIPS 2023, pages 52628–52647. Curran Associates, Inc., 2023

    2023

  9. [17]

    Grand-Clément, M

    J. Grand-Clément, M. Petrik, and N. Vieille. Beyond discounted re- turns: Robust Markov decision processes with average and Blackwell optimality. arXiv preprint arXiv:2312.03618, 2023

    2023 arXiv

  10. [18]

    Hordijk, R

    A. Hordijk, R. Dekker, and L. C. M. Kallenberg. Sensitivity-Analysis in Discounted Markovian Decision Problems. Operations-Research- Spektrum, 7(3):143–151, 1985

    1985

  11. [19]

    R. A. Howard. Dynamic Programming and Markov Processes. MIT Press, 1960

    1960

  12. [20]

    Jeroslow

    R. Jeroslow. An Algorithm for Discrete Dynamic Programming with In- terest Rates Near Zero. Management Sciences Research Group, Grad- uate School of Industrial Administration, Carnegie-Mellon University, 1972., 1972

    1972

  13. [21]

    G. Kalai. A Subexponential Randomized Simplex Algorithm (Extended Abstract). In Proceedings of the 24th Annual ACM Symposium on The- ory of Computing, pages 475–482. ACM, 1992

    1992

  14. [22]

    Kalyanakrishnan, U

    S. Kalyanakrishnan, U. Mall, and R. Goyal. Batch-Switching Policy Iteration. In Proc. IJCAI 2016, pages 3147–3153. IJCAI/AAAI Press, 2016

    2016

  15. [23]

    Kalyanakrishnan, N

    S. Kalyanakrishnan, N. Misra, and A. Gopalan. Randomised Procedures for Initialising and Switching Actions in Policy Iteration. InProc. AAAI

  16. [24]

    R. M. Karp. A Characterization of the Minimum Cycle Mean in a Di- graph. Discrete mathematics, 23(3):309–311, 1978

    1978

  17. [25]

    Kober, J

    J. Kober, J. A. Bagnell, and J. Peters. Reinforcement Learning in Robotics: A Survey. The International Journal of Robotics Research , 32(11):1238–1274, 2013

    2013

  18. [26]

    Leahy, B

    J. Leahy, B. Kerimkulov, D. Siska, and L. Szpruch. Convergence of Policy Gradient for Entropy Regularized MDPs with Neural Network Approximation in the Mean-Field Regime. In In Proc. ICML 2022 , volume 162, pages 12222–12252. PMLR, 2022

    2022

  19. [27]

    Madani, M

    O. Madani, M. Thorup, and U. Zwick. Discounted Deterministic Markov Decision Processes and Discounted All-Pairs Shortest Paths. ACM Trans. on Alg., 6(2):1–25, 2010

    2010

  20. [28]

    Mahadevan

    S. Mahadevan. Average Reward Reinforcement Learning: Foundations, Algorithms, and Empirical Results. Mach. Learn., 22(1-3):159–195, 1996

    1996

  21. [29]

    Mahadevan

    S. Mahadevan. Sensitive Discount Optimality: Unifying Discounted and Average Reward Reinforcement Learning. In ICML, pages 328–

  22. [30]

    Mahadevan and J

    S. Mahadevan and J. Connell. Automatic Programming of Behavior- Based Robots Using Reinforcement Learning. InProceedings of the 9th National Conference on Artificial Intelligence , pages 768–773. AAAI Press / The MIT Press, 1991

    1991

  23. [31]

    Mahadevan and G

    S. Mahadevan and G. Theocharous. Optimizing Production Manufac- turing Using Reinforcement Learning. In D. J. Cook, editor, Proceed- ings of the Eleventh International Florida Artificial Intelligence Re- search Society Conference, pages 372–377. AAAI Press, 1998

    1998

  24. [32]

    A. S. Manne. Linear Programming and Sequential Decisions. Manage- ment Science, 6(3):259–267, 1960

    1960

  25. [33]

    Mansour and S

    Y . Mansour and S. Singh. On the Complexity of Policy Iteration. In Proc. UAI 1999, pages 401–408. Morgan Kaufmann, 1999

    1999

  26. [34]

    Matoušek, M

    J. Matoušek, M. Sharir, and E. Welzl. A Subexponential Bound for Linear Programming. Algorithmica, 16(4/5):498–516, 1996

    1996

  27. [35]

    B. L. Miller and A. F. Veinott. Discrete Dynamic Programming with a Small Interest Rate. The Annals of Mathematical Statistics , 40(2): 366–370, 1969

    1969

  28. [36]

    Efficient Computa- tion of Blackwell Optimal Policies using Rational Functions

    D. Mukherjee and S. Kalyanakrishnan. Code for "Efficient Computa- tion of Blackwell Optimal Policies using Rational Functions". https: //github.com/dib007/blackwell-pi, 2025. GitHub repository, last ac- cessed 24 August 2025

    2025

  29. [37]

    Mukherjee and S

    D. Mukherjee and S. Kalyanakrishnan. Howard’s Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Re- wards of Fixed Bit-size and Arbitrary Discount Factor. arXiv preprint arXiv:2505.00795, 2025

    2025 arXiv

  30. [38]

    O’Sullivan and A

    M. O’Sullivan and A. F. Veinott Jr. Polynomial-Time Computation of Strong and n-Present-Value Optimal Policies in Markov Decision Chains. Mathematics of Operations Research, 42(3):577–598, 2017

    2017

  31. [39]

    Post and Y

    I. Post and Y . Ye. The Simplex Method is Strongly Polynomial forDe- terministic Markov Decision Processes. In Proc. SODA 2013 , pages 1465–1473. SIAM, 2013

    2013

  32. [40]

    M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dy- namic Programming. John Wiley & Sons, 2014

    2014

  33. [41]

    Schneckenreither

    M. Schneckenreither. Average Reward Adjusted Discounted Reinforce- ment Learning Near-Blackwell-Optimal Policies for Real-World Appli- cations. arXiv preprint arXiv:2004.00857, 2020

    2004 arXiv

  34. [42]

    Silver, A

    D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V . Panneershelvam, M. Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484–489, 2016

    2016

  35. [43]

    R. D. Smallwood. Optimum Policy Regions for Markov Processes with Discounting. Operations Research, 14(4):658–669, 1966

    1966

  36. [44]

    S. Sood, K. Papasotiriou, M. Vaiciulis, and T. Balch. Deep Reinforce- ment Learning for Optimal Portfolio Allocation: A Comparative Study with Mean-Variance Optimization. FinPlan, 2023(2023):21, 2023

    2023

  37. [45]

    R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998

    1998

  38. [46]

    Tadepalli and D

    P. Tadepalli and D. Ok. H-learning: A Reinforcement Learning Method to Optimize Undiscounted Average Reward. Technical report, Com- puter Science Department, Oregon State University, 1994

    1994

  39. [47]

    J. N. Tsitsiklis. NP-Hardness of checking the unichain condition in average cost MDPs. Oper. Res. Lett., 35(3):319–323, 2007

    2007

  40. [48]

    A. F. Veinott. On Finding Optimal Policies in Discrete Dynamic Pro- gramming with No Discounting. The Annals of Mathematical Statistics, 37(5):1284–1294, 1966

    1966

  41. [49]

    A. F. Veinott. Discrete Dynamic Programming with Sensitive Discount Optimality Criteria. The Annals of Mathematical Statistics, 40(5):1635– 1660, 1969. A γbw : A Lower Bound In this section, we construct an MDP with a threshold discount factor γbw that is exponentially close t...

    1969

Pith tools

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