{"id":"7aa7e7fc-f19d-48d7-8ca4-c1849d24ea7f","arxiv_id":"2508.18252","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Using symbolic comparisons of rational value functions near gamma=1, the authors obtain the first strongly polynomial algorithms for Blackwell-optimal policies in deterministic MDPs and a subexponential expected algorithm for general MDPs.","lead":"This paper gives faster algorithms for computing Blackwell-optimal policies in Markov decision processes by comparing policies as symbolic rational functions near the discount factor 1. It provides the first strongly polynomial time guarantees for deterministic MDPs and a subexponential guarantee for general MDPs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4 proves trajectory invariance only for stationary V^π comparisons, but Algorithms 1–2 also compare Q^π and finite-horizon d_i,y_i functions; without bounding those roots, the main complexity-transfer claims are unsupported.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap: Theorem 4's proof bounds only stationary policy value differences, while the algorithms' decisions rest on non-stationary action values and finite-horizon max/min values. This is not a minor exposition issue—it is the bridge that lets the paper claim strongly polynomial and subexponential bounds for Blackwell optimality. The proof as written does not establish a single threshold that stabilizes all relevant comparisons, including argmax/argmin tie-breaking. Nevertheless, the underlying μ-ordering framework is plausible, and the gap may be fillable by extending the root bound to the larger set of rational functions. Hence the reader's CONDITIONAL verdict is appropriate; no change is needed. I do not see a more fundamental objection that would warrant rejection, and I agree with the reader's assessment that the proofs are sketches needing expansion.","tokens_in":1002,"tokens_out":1042,"duration_ms":108232,"concrete_test":"Independently re-derive Theorem 4 for Algorithm 1 by listing every rational function that the algorithm actually compares: all d_i(s), y_i(s), and all Q^π(s,a)−V^π(s) for policies encountered. Then compute, over all deterministic MDPs with n≤4 states, k≤3 actions, and integer rewards in [−5,5], the largest real root in [0,1) of each pairwise difference among these intermediate quantities, and compare it to the maximum root over stationary V^π differences used in the current proof. If any intermediate-quantity root exceeds the stationary-policy root, the proof of Theorem 4 is incomplete even if the algorithm happens to succeed on the enumerated instances; if no such example exists, the proof gap remains but may be patchable. This check separates an actual counterexample from a merely incomplete argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central mechanism is Theorem 4 (Section 4.3), which asserts the existence of a single threshold τ such that each base algorithm L_i follows the same trajectory for all γ ∈ [τ,1). The proof, however, only bounds the roots of differences between stationary policy value functions: f_s^(i,j)(γ) = V^{π_j}_γ(s) − V^{π_i}_γ(s). This does not cover the quantities the algorithms actually compare. Algorithm 1 (Section 5.1) makes decisions based on d_i(s) and y_i(s), which are finite-horizon optimal path values obtained by alternating max/min operations; these are not stationary policy values, and a max of rational functions is only piecewise rational, so the 'finite roots' argument does not directly apply. Similarly, the policy improvement rules in Sections 5.2 and 5.3 require the sign of Q^π(s,a) − V^π(s), which is the difference between a non-stationary action-value and a stationary value, not a difference of two stationary policy values. The proof's final leap—'value ordering—and hence policy preferences—remains invariant'—is therefore unsupported. Moreover, the μ-ordering is a total order that may break ties differently from the base algorithm's argmax, and the proof does not address tie behavior. Unless a separate argument bounds the roots of all intermediate d_i/y_i differences and Q^π−V^π differences, both the correctness and the transferred complexity bounds (Theorems 5–7) do not follow from the stated proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":2004,"tokens_out":2576,"duration_ms":131099,"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":[{"comment":"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","section":"Section 4.3, Theorem 4"},{"comment":"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.","section":"Section 5.1, Algorithm 1 and Theorem 5"},{"comment":"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.","section":"Section 5.3, Theorem 7"},{"comment":"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.","section":"Section 5.4"}],"minor_comments":[{"comment":"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.","section":"Section 2.1, gamma_Q definition"},{"comment":"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.","section":"Section 5.1, Algorithm 1 lines 6 and 13"},{"comment":"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).","section":"Section 4.2"},{"comment":"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.","section":"Appendix A"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper has substantial potential but is not yet in a publishable form. The main issue is the unsupported transfer theorem for non-stationary comparisons and ties; this is a genuine technical gap, not a matter of presentation. The Appendix B equivalence of the Laurent-series and rational-function improvement tests is a strong point and should be kept. The self-citation [37] is used for the definition of gamma_Q and is contextual, not circular. I would ask the authors to either close the Theorem 4 gap or explicitly restrict the claims to algorithms whose comparisons are governed by stationary value ordering."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nYou should know this paper makes real claims but doesn't yet back them up. It adapts rational-function ordering near 1 (from Hordijk et al.) to a handful of modern MDP algorithms, and if the transfer argument worked, it would give the first strongly polynomial algorithms for Blackwell-optimal policies in deterministic MDPs and a subexponential expected bound for general MDPs. That is a meaningful step in a subfield where most results are exponential or weakly polynomial.\n\nThe good news: the mu-ordering idea is clean, Lemma 3 is correct, and the paper is transparent about where it borrows from. The Q^π−V^π comparisons in Sections 5.2 and 5.3 are rational functions, so the eventual-sign argument should work there. The complexity bounds in Theorems 5 and 7 are plausible.\n\nThe bad news: Theorem 4, the load-bearing transfer theorem, proves invariance only for differences of stationary policy values, but Algorithm 1 compares finite-horizon path values d_i and y_i, which are piecewise rational, not rational. The proof doesn't cover those, nor does it address argmax tie-breaking. That's a real hole: the O(n^4 k) bound for deterministic MDPs and the correctness of the symbolic dmax/dmin operations don't follow from what's written. Also, line 10 of Algorithm 1 has a type error (y0(s) <- alpha_n(s)), Section 5.4 asserts bounds for three PI variants with no proof, and the Appendix A lower-bound derivation has garbled formulas that don't produce the stated threshold.\n\nNone of this is fatal. The gaps look repairable: for deterministic MDPs, finite-horizon values are polynomials of bounded degree, so a piecewise rational treatment would work; for Q−V, the rational-function argument applies directly if the theorem is stated for those functions. But the paper as submitted does not supply those arguments. The authors should be pushed to rewrite the proof of Theorem 4 and make Appendix A readable.\n\nWho should read this: anyone working on sensitive discount optimality or the complexity of MDP planning. It deserves a serious referee: the claims are important enough to spend time on even though the current manuscript is not close to acceptable.\n\nRecommendation: send to peer review, and ask the referees to focus on the transfer theorem and the correctness of Algorithm 1.","headline":"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.","tokens_in":17813,"tokens_out":5699,"would_cite":false,"duration_ms":62742,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Blackwell optimality","Markov decision process","rational functions","discount factor","policy iteration","strongly polynomial time","subexponential algorithm","deterministic MDP"],"falsifier":"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.","tokens_in":16882,"feed_emoji":"⚙️","tokens_out":6173,"duration_ms":74384,"temperature":0.7,"pith_summary":"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.","feed_headline":"Symbolic ordering makes Blackwell-optimal policies fast to compute","feed_subtitle":"The same trick gives the first strongly polynomial bound for deterministic MDPs and a subexponential bound for general ones.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes that every finite MDP has a Blackwell-optimal policy, the object the paper computes.","marker":"[5]"},{"why":"Defines the Blackwell discount factor and supplies a conservative threshold upper bound that motivates the need for direct symbolic computation.","marker":"[16]"},{"why":"Introduces the symbolic ordering of rational functions near a boundary in a simplex framework, the conceptual basis for the paper's µ-ordering.","marker":"[18]"},{"why":"Gives the O(n^2 k) Karp-style algorithm for discounted deterministic MDPs that DetMDP2-Blackwell adapts to Blackwell optimality.","marker":"[27]"},{"why":"Supplies the strongly polynomial max-gain simplex bound for deterministic MDPs that the Blackwell variant preserves.","marker":"[39]"},{"why":"Provides the Random-Facet subexponential linear-programming bound used in the expected runtime of Random-Facet-Blackwell.","marker":"[34]"},{"why":"Gives the Laurent-series policy improvement procedure whose equivalence to the rational-function approach is established in Appendix B.","marker":"[35]"},{"why":"Links Blackwell optimality to sensitive and N-discount optimality, providing the optimality hierarchy the paper builds on.","marker":"[49]"}],"fun_headline_variants":["First strongly polynomial-time algorithm for Blackwell-optimal policies","Subexponential algorithm for Blackwell-optimal policies in general MDPs","Symbolic comparison of rational functions yields faster Blackwell optimality","Lifting discount factor to formal variable speeds Blackwell-optimal policy computation","Fast Blackwell optimality via symbolic rational functions"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["First strongly polynomial-time algorithm for Blackwell-optimal policies","Subexponential algorithm for Blackwell-optimal policies in general MDPs","Symbolic comparison of rational functions yields faster Blackwell optimality","Lifting discount factor to formal variable speeds Blackwell-optimal policy computation","Fast Blackwell optimality via symbolic rational functions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000326,"raw_usage":{"total_tokens":1647,"prompt_tokens":715,"completion_tokens":932,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":459,"completion_tokens_details":{"reasoning_tokens":850}},"tokens_in":459,"tokens_out":932,"duration_ms":10197,"temperature":1.0,"reasoning_tokens":850,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T16:29:25.833530+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Blackwell","cited_arxiv_id":null,"evidence_quote":"Establishes that every finite MDP has a Blackwell-optimal policy, the object the paper computes."},{"cited_title":"Grand-Clément and M","cited_arxiv_id":null,"evidence_quote":"Defines the Blackwell discount factor and supplies a conservative threshold upper bound that motivates the need for direct symbolic computation."},{"cited_title":"Hordijk, R","cited_arxiv_id":null,"evidence_quote":"Introduces the symbolic ordering of rational functions near a boundary in a simplex framework, the conceptual basis for the paper's µ-ordering."},{"cited_title":"Madani, M","cited_arxiv_id":null,"evidence_quote":"Gives the O(n^2 k) Karp-style algorithm for discounted deterministic MDPs that DetMDP2-Blackwell adapts to Blackwell optimality."},{"cited_title":"Post and Y","cited_arxiv_id":null,"evidence_quote":"Supplies the strongly polynomial max-gain simplex bound for deterministic MDPs that the Blackwell variant preserves."},{"cited_title":"Matoušek, M","cited_arxiv_id":null,"evidence_quote":"Provides the Random-Facet subexponential linear-programming bound used in the expected runtime of Random-Facet-Blackwell."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Laurent-series policy improvement procedure whose equivalence to the rational-function approach is established in Appendix B."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Links Blackwell optimality to sensitive and N-discount optimality, providing the optimality hierarchy the paper builds on."}],"review_version":1}