{"id":"d30ab6fb-8b64-4479-852a-79324212d282","arxiv_id":"2412.14002","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"OS-CMDP uses Douglas-Rachford splitting to solve convex-constrained MDPs by alternating between a quadratically regularized MDP update and a projection onto the constraint set, with convergence and infeasibility-detection guarantees.","lead":"The paper introduces a first-order splitting algorithm for finite Markov decision processes with convex constraints, alternating a regularized MDP solve with a projection. It promises last-iterate convergence and a way to detect infeasible constraint sets, with numerical speedups over general-purpose solvers on benchmark problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Implemented algorithm uses only ℓ=2 inexact QRPI steps while Proposition 2's convergence guarantee requires exact inner solves; no proof is given that the induced prox error e_k is summable, so the abstract's unconditional last-iterate and infeasibility claims are not covered for Algorithm 1 as run.","rationale":"The reader and I identify the same load-bearing concern: the formal convergence results are proven for exact inner solves, while the implementation and all reported benchmarks use a small fixed number of inexact QRPI iterations. I checked the exact-theory core for internal contradictions and found none: f and g are proper closed convex, Assumption 1 supplies the needed qualification, and the infeasible-case results are standard Douglas-Rachford facts. The paper is explicit in Section V that the inexact implementation needs summable errors, but it does not deliver the needed estimate, and Proposition 1 alone does not provide one because it concerns a fixed w_k. This is a completeness gap in the proof for the implemented algorithm, not an observed instability; hence it supports conditional acceptance with a request to either prove summability under a verifiable inner-error stopping rule or qualify the abstract and Section IV claims as applying to the exact-inner variant. Missing code and some omitted convex-CMDP baselines are secondary issues. Because the exact-version contribution appears sound, I would keep the reader's CONDITIONAL verdict, so the recommendation is UNCHANGED.","tokens_in":20492,"tokens_out":14616,"duration_ms":147137,"concrete_test":"Run the S=100 Garnet instance from Section VI with the deployed settings (ell=2, omega=1.5, sigma=2e-5). At each outer iteration k, compute the exact prox_{sigma f}(w_k) by solving the QP (8) to high accuracy, or by running QRPI far beyond ell with a tight stopping tolerance, and record e_k together with partial sums S_K = sum_{k=0}^K e_k for K up to at least 10^4. If S_K does not appear to converge or e_k fails to decay, the summability condition needed to transfer Proposition 2 to Algorithm 1 as implemented is not met, and the claims should be restricted to the exact-inner variant or to an explicit error-controlled stopping rule. An analytic companion is to attempt a bound on e_k from the QRPI contraction with constants independent of k.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The exact-inner-solve theory appears internally coherent: Proposition 2 is a standard Douglas-Rachford corollary under Assumption 1, QRPI convergence in Proposition 1 is plausible as block coordinate maximization of a strongly concave dual, and Propositions 3-4 match the known infeasible-DRA framework. The load-bearing gap is between that exact theory and the algorithm actually deployed. Algorithm 1 fixes ell=2 inner QRPI iterations, and Section V concedes that the exact guarantee survives only if e_k := ||d_k - prox_{sigma f}(w_k)|| is summable, citing [47, Th. 7], but no proof of summability is supplied. Proposition 1's R-linear rate is stated for a fixed w_k; the outer iteration changes w_k at every step, so the rate does not automatically yield a uniform-in-k contraction for the warm-started ell=2 inner loop. The only evidence is the two numerical trajectory comparisons in Appendix C. Consequently, last-iterate convergence, the infeasibility flag (21), and the shifted-problem convergence (17) are formally established only for the ell=infinity variant, while Tables I-II and Figures 3-4 report results for ell=2. The abstract's unconditional claims therefore outrun the theorems as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies finite discounted MDPs with convex constraints on the occupancy measure and known dynamics. It reformulates the convex CMDP as the sum f(d)=c^T d + I_D(d) and g(d)=I_C(d), applies Douglas-Rachford splitting, and develops a double-loop algorithm: an inner QRPI method for the regularized MDP prox_{σf}(w) and an outer projection onto C. The authors prove convergence of QRPI, then, assuming the inner problem is solved exactly, prove DRA convergence under a constraint qualification, characterize the minimal displacement vector and shifted-problem convergence when C∩D is empty, and propose termination criteria. Numerical experiments on Garnet MDPs and a grid world compare OS-CMDP with Gurobi, SCS, and a primal-dual baseline.","tokens_in":20691,"tokens_out":7111,"duration_ms":66337,"significance":"If the exact-inner-loop theory holds, the paper contributes a modular first-order method for convex CMDPs that does not require explicit regularization of the original problem and provides an infeasibility certificate. The infeasibility analysis in Propositions 3 and 4 is a valuable extension over algorithms that merely return a policy when the problem is feasible. The paper is also transparent about the practical inexact variant, but this transparency does not remove the gap between theory and implementation. The use of standard operator-splitting results and the numerical comparisons give reasonable confidence that the exact claims are correct and the method is competitive at medium accuracy.","major_comments":[{"comment":"The convergence guarantees proved in Section IV apply to the variant of Algorithm 1 in which the inner QRPI loop is solved to optimality, i.e. ℓ=+∞. The implemented algorithm in the experiments uses ℓ=2, as stated in Sections V and VI. Section V acknowledges that the inexact variant needs ∑_k e_k < ∞, where e_k := ||d_k − prox_{σf}(w_k)||, and cites [47, Th. 7], but it does not prove or even estimate this condition. Since Propositions 3 and 4 also rely on the exact DRA iteration (7), the abstract's claims of last-iterate convergence and infeasibility detection, and the termination criterion (21), are not established for the algorithm actually run.","section":"Section V and Propositions 2–4"},{"comment":"Proposition 1 gives an R-linear convergence rate for QRPI for a fixed outer point w_k. This does not imply that ℓ=2 inner steps at each outer iteration produce a prox error e_k satisfying the summability condition in Section V: the outer update changes w_k at every step, so the contraction factor may depend on k, and warm starting need not yield a uniform bound. The numerical evidence in Appendix C compares ℓ=2 against ℓ=100 on only two problem instances; it is suggestive but cannot substitute for a proof that the inexact iteration inherits the DRA convergence or infeasibility-certification properties.","section":"Section V, Proposition 1, and Appendix C"},{"comment":"The identification of QRPI with the coordinate descent analysis of [48] is too terse. In particular, the displayed quantities E := [γP−Ξ  −I] and b are not explicitly reconciled with the dual objective κ in (9), and the conditions of [48, Th. 2.1] are only asserted. Since Proposition 1 is the basis for the inner-loop convergence used to compute prox_{σf}(w_k), please expand the mapping and verify all assumptions, including strong convexity of the relevant function and the exact block-coordinate update order.","section":"Appendix B, proof of Proposition 1"}],"minor_comments":[{"comment":"The name \"Douglas-Rachord\" should be \"Douglas-Rachford\".","section":"Abstract"},{"comment":"The text contains typographical errors: \"Largrange\" should be \"Lagrange\", and \"disadvantegeous\" should be \"disadvantageous\".","section":"Section III-A"},{"comment":"The loop header \"For ℓ = 0,...,ℓ−1\" uses ℓ both as the total number of inner iterations and as the running index; rename the running index (e.g., m) to avoid confusion.","section":"Algorithm 1"},{"comment":"The notation \"ρ ∈ ∆(RS)\" is inconsistent with the earlier definition ∆(S) = {x ∈ R^{|S|}_{≥0} : 1^T x = 1}; please clarify whether ρ is a vector in R^S or a distribution in the simplex.","section":"Section II-A"},{"comment":"The phrase \"uncostrained MDP\" should be \"unconstrained MDP\".","section":"Appendix D"},{"comment":"In the S=3000, f_b=0.5 row, the SCS entry \"194.85 ( -1.55 )\" is missing the unit \"s\" used elsewhere in the table.","section":"Table II"}],"recommendation":"major_revision","confidential_remarks":"I am confident the main idea is sound, but the gap between the exact-inner-loop theory and the ℓ=2 implementation is the central issue. A revision should either prove a bound on the prox error e_k (for example by increasing the inner iterations adaptively with k and verifying summability) or carefully qualify all abstract and conclusion claims so that they refer to the exact or adaptively-inexact variant. The paper's current wording, especially in the abstract, overstates what is proven for Algorithm 1 as coded."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the Douglas-Rachford splitting for convex CMDPs is a genuinely useful idea, and the exact-inner-loop theory is coherent, but the algorithm as actually run (ℓ=2) is not covered by Propositions 2–4, and the abstract overstates what is proven. That gap is fixable, not fatal.\n\nWhat's new: the decomposition f = c^T d + I_D, g = I_C is natural but I don't think it appears this way in the CMDP literature; the QRPI inner solver for quadratically regularized MDPs is a clean derivation; and the infeasibility analysis using the minimal displacement vector of the DRA is a nice touch that gives practitioners a certificate. The exact version's convergence is standard DRA theory applied correctly, and the QRPI convergence via Luo–Tseng coordinate descent is plausible.\n\nWhere it gets soft: Section V explicitly says ℓ=2 suffices in practice, but the only evidence is two trajectory comparisons in Appendix C. The text acknowledges that summability of e_k would recover the guarantee, but no proof is given, and the R-linear rate of QRPI is for fixed w_k, so it does not automatically transfer to warm-started inner loops with changing outer iterates. So the last-iterate and infeasibility-detection claims are rigorously established only for the ℓ=∞ variant. The abstract's 'last-iterate convergence' and 'minimally violates' phrasing is too strong for Algorithm 1 as shipped. Also, the numerical study omits the closest convex-CMDP baselines (e.g., [28], [30]), reports only means without variances, and no code is released. These are all addressable in revision.\n\nBottom line: a serious referee should engage with this. The core contribution is likely correct and the infeasibility certificate is valuable. Request: add a provable inner-error stopping rule or clearly qualify the guarantees, add the missing baselines, and release code. I'd put it in this month's reading group.","headline":"Solid contribution with a real gap between the ℓ=2 implementation and the exact-inner-loop convergence theorems; worth referee time.","tokens_in":21315,"tokens_out":2718,"would_cite":false,"duration_ms":23722,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C40","90C25","65K10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Douglas-Rachford splitting decouples dynamics from constraints in convex MDPs, giving a first-order algorithm with last-iterate convergence and an infeasibility certificate.","keywords":["convex constrained Markov decision process","Douglas-Rachford splitting","operator splitting","occupancy measure","infeasibility detection","quadratic regularization","policy iteration","first-order optimization"],"falsifier":"Take a feasible linearly constrained Garnet or grid-world CMDP whose optimal occupancy lies on a constraint boundary, run OS-CMDP with $\\ell=2$ and the termination criterion $\\|d_k-z_k\\|_\\infty \\le \\varepsilon_{\\mathrm{opt}}$, and compare the returned objective with the LP optimum: if the criterion fires while $c^{\\top} d_k$ is measurably above the optimum or while $d_k$ still violates a constraint, the inexact implementation is not converging to a primal-dual solution.","tokens_in":20204,"feed_emoji":"🧮","tokens_out":8493,"duration_ms":66564,"temperature":0.7,"pith_summary":"This paper tries to establish that a first-order splitting method can solve finite, known convex-constrained Markov decision processes without giving up convergence guarantees or scalability. The proposed OS-CMDP decomposes the problem into the occupancy-measure polytope $D$, which encodes the MDP dynamics, and the convex constraint set $C$, then alternates between solving a quadratically regularized MDP and projecting onto $C$. With exact inner solves, the iterates converge to a primal-dual solution of the convex CMDP under standard feasibility conditions. When $C$ and $D$ are disjoint, the difference $w_k - w_{k+1}$ converges to the minimal displacement vector $v$, and for polyhedral $C$ the occupancy iterates converge to the optimum of the shifted feasible problem $d \\in D \\cap (C - v)$. This matters because it gives a scalable first-order route to convex CMDPs and turns infeasible specifications into a certificate plus a minimally violating policy.","feed_headline":"Splitting method solves constrained MDPs fast, detects infeasibility","feed_subtitle":"Alternating MDP solves and projections gives last-iterate convergence and a certificate when constraints cannot be met.","key_machinery":"The load-bearing object is the Douglas-Rachford splitting of the convex program into $f(d)=c^{\\top}d + I_D(d)$, the unconstrained MDP part, and $g(d)=I_C(d)$, the constraint part. Its iteration alternates evaluating the proximal operator of $f$ (a quadratically regularized MDP, solved efficiently by the quadratically regularized policy iteration inner loop) with projection onto $C$. The infeasibility analysis centers on the minimal displacement vector $v=\\arg\\min_{\\beta \\in D-C}\\|\\beta\\|$, which is the limit of $w_k - w_{k+1}$ and, when $C \\cap D=\\emptyset$, the normal vector of a strongly separating hyperplane between $D$ and $C$.","core_discovery":"On its own terms, the central claim is that Douglas-Rachford splitting with $f(d)=c^{\\top}d + I_D(d)$ and $g(d)=I_C(d)$ lets an MDP's dynamics and its convex constraints be handled separately while still converging to a primal-dual solution. Each outer iteration performs two simple operations: a proximal step for $f$, which is a quadratically regularized MDP solved by the proposed QRPI scheme, and the projection of a reflected point onto $C$. Under Assumption 1 the generated $(d_k, z_k, \\nu_k)$ converges to a primal-dual solution of (4). If $C \\cap D = \\emptyset$, the paper shows that $w_k - w_{k+1}$ tends to the minimal displacement vector $v=\\arg\\min_{\\beta \\in D-C}\\|\\beta\\|$, and for polyhedral $C$ the occupancy measures converge to an optimal solution of the translated feasible problem $d \\in D \\cap (C-v)$.","pith_inferences":["Proving that the inexact inner loop with a small fixed number of QRPI steps produces a summable error sequence $e_k=\\|d_k - \\mathrm{prox}_{\\sigma f}(w_k)\\|$ would turn Proposition 2 into a guarantee for the algorithm exactly as implemented; that error bound is the natural missing piece.","The same splitting could be adapted to model-free or estimated-dynamics settings by replacing QRPI with an approximate policy evaluator, with the minimal displacement vector then serving as a certificate that the learned safety constraints are incompatible with the estimated model.","The minimal displacement vector also suggests a practical tuning rule: shift the right-hand sides of the constraints along $v$ just enough to make the problem feasible, then re-run the algorithm to obtain the best policy under the adjusted specification.","Because the constraint step is a generic projection, one could in principle plug in learned or data-defined constraint sets and retain the algorithm's structure, although the convergence theory would no longer apply."],"forward_implications":["Convex CMDPs can be solved by alternating an MDP solve with a projection, so any constraint set with an implementable projection — norm balls, entropy constraints, robust-cost constraints — fits the same algorithm.","The algorithm returns a last-iterate primal occupancy measure, not a Cesàro average, which is useful when the policy is represented by a nonlinear function approximator.","An infeasible specification is not a failure: the algorithm returns the minimal displacement vector as a certificate and, for polyhedral constraints, the optimal policy for the minimally relaxed feasible problem.","Because the inner QRPI loop converges R-linearly to the regularized MDP solution, the per-iteration subproblem can be solved by a policy-iteration-style scheme rather than by a generic quadratic program."],"supporting_citations":[{"why":"Supplies the Douglas-Rachford convergence theorem used in Proposition 2.","marker":"[32]"},{"why":"Establishes the minimal-displacement limit of the Douglas-Rachford operator used in Proposition 3.","marker":"[41]"},{"why":"Provides the asymptotic characterization of Douglas-Rachford iterates for inconsistent problems used in Proposition 4.","marker":"[42]"},{"why":"Gives the coordinate-descent convergence result that Proposition 1 uses to prove QRPI converges R-linearly.","marker":"[48]"},{"why":"Gives the inexact Douglas-Rachford condition of summable prox errors that motivates the finite inner-loop implementation.","marker":"[47]"},{"why":"Supplies the occupancy-measure polytope D and the LP formulation of MDPs on which the whole splitting rests.","marker":"[4]"}],"fun_headline_variants":["Split MDP constraints for last-iterate convergence","Operator splitting yields stable MDP solutions and infeasibility proofs","Decouple dynamics and constraints in MDPs with splitting","Detect infeasible MDPs via Douglas-Rachford splitting","Convex constrained MDPs solved by simple projections and MDP steps"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convergence theorem assumes the inner regularized MDP is solved to optimality, whereas the implementation runs only two QRPI inner iterations; numerical evidence is given, but no proof that the resulting prox error is summable.","fun_headline_variants_meta":{"raw":{"variants":["Split MDP constraints for last-iterate convergence","Operator splitting yields stable MDP solutions and infeasibility proofs","Decouple dynamics and constraints in MDPs with splitting","Detect infeasible MDPs via Douglas-Rachford splitting","Convex constrained MDPs solved by simple projections and MDP steps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000263,"raw_usage":{"total_tokens":1591,"prompt_tokens":926,"completion_tokens":665,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":542,"completion_tokens_details":{"reasoning_tokens":579}},"tokens_in":542,"tokens_out":665,"duration_ms":5941,"temperature":1.0,"reasoning_tokens":579,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:34:39.431064+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a feasible linearly constrained Garnet or grid-world CMDP whose optimal occupancy lies on a constraint boundary, run OS-CMDP with $\\ell=2$ and the termination criterion $\\|d_k-z_k\\|_\\infty \\le \\varepsilon_{\\mathrm{opt}}$, and compare the returned objective with the LP optimum: if the criterion fires while $c^{\\top} d_k$ is measurably above the optimum or while $d_k$ still violates a constraint, the inexact implementation is not converging to a primal-dual solution.","supporting_citations":[{"cited_title":"Bauschke and P","cited_arxiv_id":null,"evidence_quote":"Supplies the Douglas-Rachford convergence theorem used in Proposition 2."},{"cited_title":"On the minimal displacement vector of the Douglas–Rachford operator,","cited_arxiv_id":null,"evidence_quote":"Establishes the minimal-displacement limit of the Douglas-Rachford operator used in Proposition 3."},{"cited_title":"On the Douglas–Rachford algorithm for solving possibly inconsistent optimization problems,","cited_arxiv_id":null,"evidence_quote":"Provides the asymptotic characterization of Douglas-Rachford iterates for inconsistent problems used in Proposition 4."},{"cited_title":"On the convergence of the coordinate descent method for convex differentiable minimization,","cited_arxiv_id":null,"evidence_quote":"Gives the coordinate-descent convergence result that Proposition 1 uses to prove QRPI converges R-linearly."},{"cited_title":"On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators,","cited_arxiv_id":null,"evidence_quote":"Gives the inexact Douglas-Rachford condition of summable prox errors that motivates the finite inner-loop implementation."}],"review_version":1}