REVIEW 3 major objections 3 minor 13 references
Learning Deterministic Policies with Policy Gradients in Constrained Markov Decision Processes
T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A primal-dual policy-gradient method, trained on noisy stochastic (hyper)policies and deployed noise-free, provably reaches the optimal feasible deterministic policy of a constrained MDP in the last iterate, under weak gradient domination.
desk verdict A serious framework for constrained policy gradients with deterministic deployment, but the main transfer theorem currently has a backwards inequality that degrades the stated constant. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine of the proof is the ridge-regularized Lagrangian $\mathcal{L}_\omega(\upsilon,\lambda) = J_0(\upsilon) + \langle\lambda, J(\upsilon) - b\rangle - \frac{\omega}{2}\|\lambda\|_2^2$, whose strong concavity in the dual variable gives the closed-form primal function $H_\omega(\upsilon) = J_0(\upsilon) + \frac{1}{2\omega}\|(J(\upsilon)-b)_+\|_2^2$, and the potential function $\mathcal{P}_k(\chi) = a_k + \chi b_k$, where $a_k$ is the expected gap of $H_\omega$ and $b_k$ the expected duality gap; driving $\mathcal{P}_k(\chi)$ to zero certifies both optimality and feasibility. The decisive inequality is the weak $\psi$-gradient domination condition, which states that the suboptimality of the Lagrangian at any parameter and multiplier is bounded by a power of the gradient norm, up to a bias; this turns the per-step descent of the alternating primal-descent/dual-ascent updates into a global last-iterate recurrence with explicit rates. The white-noise model is what licenses deterministic deployment: Theorems 4.1 through 4.3 show that gradient domination, smoothness, and the deployment gap are all inherited from the deterministic Lagrangian, with a noise-dependent bias $\beta^\dagger(\sigma,\psi)$ that vanishes at $\sigma = 0$, so the stochastic training phase and the deterministic deployment phase are governed by the same constants.
What would settle it
Estimate the quantity $\|\nabla_\theta \mathcal{L}_{D,0}(\theta,\lambda)\|_2^\psi - \alpha_D(\mathcal{L}_{D,0}(\theta,\lambda) - \min_{\theta'} \mathcal{L}_{D,0}(\theta',\lambda)) + \beta_D$ on the two-dimensional CostLQR used in the experiments, over a grid of $(\theta,\lambda)$ for a linear-Gaussian policy; if no positive $\alpha_D$ and finite $\beta_D$ make it nonnegative everywhere, Assumption 4.3 fails and the Theorem 4.6 certificate does not apply. A complementary check is to run C-PG on a small CMDP whose policy class provably violates gradient domination, and see whether the last-iterate objective gap and constraint violation stop shrinking at the predicted accuracy.
Extended reading notes
Core claim
The central claim is Theorem 4.6. Under the white-noise model, in which an action-based stochastic policy or a parameter-based stochastic hyperpolicy is obtained by adding zero-mean, bounded-variance noise to a parametric deterministic policy, C-PG run for $K = O(\omega^{-3}\sigma^{-2}\epsilon^{-4/\psi+1})$ iterations with estimated gradients guarantees that the deterministic policy obtained by zeroing the noise at the last iterate satisfies $\mathcal{P}_{D,K}(\chi) \le \epsilon + \beta^\dagger(\sigma,\psi)/\alpha_D + 4(1+\Lambda_{\max}) L_1^\dagger \sigma \sqrt{d^\dagger}$. Here $\epsilon$ is the user-chosen accuracy, $\beta^\dagger(\sigma,\psi)/\alpha_D$ is the gradient-domination bias inherited from the deterministic Lagrangian (it vanishes when the deterministic problem is strongly gradient-dominated), and the last term is the deployment cost of the noise, which vanishes as $\sigma \to 0$. Because the potential function bounds both the suboptimality of the regularized primal function and the duality gap of the current iterate, Theorem 3.1 converts such a bound into explicit control of the true objective gap $\mathbb{E}[J_0(\upsilon_k) - J_0(\upsilon_0^*)]$ and of the constraint violations $\mathbb{E}[(J_i(\upsilon_k) - b_i)_+]$, so the deployed policy is near-optimal and near-feasible. The same update scheme, with different gradient estimators, yields the action-based variant C-PGAE and the parameter-based variant C-PGPE, and the deterministic-deployment rate matches the unconstrained setting up to an extra $\sigma^{-2}$ factor.
Load-bearing premise
The load-bearing premise is Assumption 4.3, that the deterministic Lagrangian satisfies weak $\psi$-gradient domination for every parameter and Lagrange multiplier, so that the gradient size controls the suboptimality gap globally — a property known for tabular softmax and natural parameterizations but never verified for the continuous Gaussian policies used in the experiments.
Editorial extensions
If this is right
- One algorithm, C-PG, covers both action-based and parameter-based exploration in constrained continuous control with multiple constraints, and its convergence rate does not depend on the cardinality of the state or action spaces.
- Deterministic deployment is certified: switching off the noise in the last iterate yields a deterministic policy whose objective gap and constraint violations are bounded by $\epsilon$ plus a noise term that vanishes as $\sigma \to 0$ and a bias term that vanishes when the deterministic problem is strongly gradient-dominated.
- Setting $\omega = O(\epsilon)$ and $\sigma = O(\epsilon)$ gives sample complexity $O(\epsilon^{-(4+4/\psi)} \log(1/\epsilon))$ with estimated gradients, which is $O(\epsilon^{-8} \log(1/\epsilon))$ under gradient domination ($\psi=1$) and $O(\epsilon^{-6} \log(1/\epsilon))$ under the Polyak-\Lojasiewicz condition ($\psi=2$).
- Theorem 3.1's conservative-threshold remark gives a direct path to zero constraint violation: shift the thresholds to $b_i' \approx b_i - 4\epsilon - \omega\|\lambda_0^*\|_2$ and run the identical algorithm.
- The deployment bounds recover the known action-versus-parameter exploration trade-off: action noise costs grow with action dimension and horizon, while parameter noise costs grow with parameter-space dimension.
Reading between the lines
- The paper itself flags that its recommended noise level $\sigma = O(\epsilon)$ is impractical; an editorial next step, which the authors reference as solved only in the unconstrained case, is to anneal the noise during training and prove whether the last-iterate certificate survives.
- Because the deployment bias $\beta^\dagger(\sigma,\psi)$ is derived from the deterministic Lagrangian through explicit Lipschitz constants, one could audit a real deployment by verifying weak gradient domination once per policy class and then computing the certificate for any noise level, instead of re-checking per run.
- If the central claim holds, the stochastic-versus-deterministic distinction in constrained RL becomes a bookkeeping choice inside one framework, and benchmark reporting should follow the experiments here by quoting the deployed noise-free policy's performance, since that is the object with a guarantee.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proposes C-PG, a primal-dual policy gradient algorithm for constrained MDPs with a Lagrangian formulation regularized in the dual variable. The authors establish dimension-free last-iterate convergence rates under a weak psi-gradient domination assumption (Theorem 3.2), and then specialize to white-noise action-based and parameter-based exploration, showing that the weak psi-gradient domination can be inherited from the underlying deterministic policy (Theorem 4.2) and that switching off the noise at the end of training yields last-iterate convergence to a near-optimal feasible deterministic policy (Theorem 4.6). The paper includes detailed appendix proofs, a comparison with existing primal-dual methods, and experiments on constrained control tasks.
Significance. The contribution is potentially significant: it extends last-iterate primal-dual guarantees to multiple constraints, continuous spaces, and both action-based and parameter-based exploration, and it provides a sample-complexity analysis for deterministic deployment in CMDPs under a white-noise model. The appendix contains detailed proofs and the code is available, which are strengths. However, the main deterministic-deployment theorem depends on a gradient-transfer step in Theorem 4.2 that is not correct as written, and a learning-rate specification in Theorem 4.6 is inconsistent with its proof; these issues are local and fixable but currently leave the central guarantee unproven as stated.
major comments (3)
- [4.3, Theorem 4.2] In the proof of Theorem 4.2 (PB case, and the same step in the AB case), after deriving ||∇_θ L_D,0(θ,λ)||_2 ≤ ||∇_θ L_P,0(θ,λ)||_2 + C, the paper asserts that, since ψ∈[1,2], superadditivity of (·)^ψ gives ||∇_θ L_D,0||_2^ψ ≤ ||∇_θ L_P,0||_2^ψ + C^ψ. For ψ>1, x^ψ is superadditive on R_+, i.e., (a+b)^ψ ≥ a^ψ + b^ψ, so the displayed inequality is reversed; for example ψ=2, a=b=1 gives 4 ≤ 2, which is false. The correct relation is ||∇_θ L_P,0||_2^ψ ≥ 2^{1−ψ}||∇_θ L_D,0||_2^ψ − C^ψ, which, combined with Equation (8), yields the inherited weak gradient domination with constant 2^{1−ψ} α_D (or, equivalently, a β† enlarged by a 2^{ψ−1}-type factor) instead of α_D. Since Theorem 4.6 places β†(σ,ψ)/α_D in the bias and uses α_D in the rate constants, the stated guarantee is not established. This is a concrete proof error, and it is load-bearing for the paper's central claim.
- [4.4, Theorem 4.6] The theorem statement specifies ζ_λ = O(ω σ^2 ε^{2/ψ}) and ζ_θ = ω ζ_λ, which gives ζ_θ = O(ω^2 σ^2 ε^{2/ψ}); the proof sketch in the main text and the appendix proof instead use ζ_θ = O(ω^3 σ^2 ε^{2/ψ}), i.e., ζ_θ = O(ω^2 ζ_λ), matching the relation used in Theorem 3.2. With the stated ζ_θ = ω ζ_λ, the denominator of the iteration bound is no longer O(ω^3 σ^2 ε^{4/ψ−1}), so the displayed sample complexity K = O(ω^{−3} σ^{−2} ε^{−4/ψ+1}) is not justified for the learning-rate choice stated in the theorem. Please correct the statement or the proof so that the parameterization matches the analysis.
- [6, Assumption 4.3] The experiments use linear Gaussian stochastic policies and Gaussian hyperpolicies (Appendix D.1), but the paper does not verify the weak ψ-gradient domination of the deterministic Lagrangian L_D,0 for these policy classes. Remark 3.1 only cites sufficient conditions for ψ=1 (non-degenerate Fisher information and compatible approximation bias) and does not check them for the Lagrangian with arbitrary Lagrange multipliers λ used in Assumption 4.3. Consequently, Theorem 4.6 is not shown to apply to the reported empirical settings; the numerical results should be regarded as heuristic validation of the algorithm rather than confirmation of the convergence theorem.
minor comments (3)
- [4.4, Theorem 4.6 and Table 2] The displayed sample complexity K = O(ω^{−3} σ^{−2} ε^{−4/ψ+1}) omits the log(1/ε) factor that appears in the proof sketch and in Table 2; please state the rate with the logarithmic factor for consistency.
- [4.1, Definitions 4.2 and 4.3] Definitions 4.2 and 4.3 assume that μ_θ(s)+ε and θ+ε remain in the action and parameter spaces A and Θ, respectively; since A and Θ are only assumed to be subsets of R^d, the noise perturbation can leave these sets. Please state an explicit assumption (e.g., A=Θ=R^d or a projection mechanism) or justify that the analysis covers constrained spaces.
- [4.3, Lemma 4.4 proof] In the proof of Lemma 4.4, the bound on E[||∇_θ log π_θ(τ)||^2] is attributed to 'Lemma E.3 by Montenegro et al. (2024b)', while the surrounding text and reference list attribute the corresponding regularity results to Montenegro et al. (2024a); please reconcile the citation.
Circularity Check
No circular reduction: the deterministic-deployment guarantee is derived from explicit assumptions and independently stated cited lemmas, not from the conclusion itself.
full rationale
The central chain (Theorem 3.2 -> Theorems 4.2/4.3/4.5 -> Theorem 4.6) does not reduce to its inputs. Assumption 4.3 postulates weak psi-gradient domination of the deterministic Lagrangian; Theorem 4.2 transfers it to the stochastic Lagrangian using regularity assumptions and white-noise gap bounds; Theorem 4.6 concatenates Theorem 3.2's potential-function recursion with Theorem 4.5's gap bound. No fitted parameter is renamed as a prediction, and no uniqueness or ansatz is imported from the authors' prior work to force the conclusion. The reuse of Montenegro et al. 2024a/2024b (e.g., Theorems 5.1/5.2 in the proof of Theorem 4.1, Lemmas D.3/D.7/E.3/E.4) is substantial but non-circular: those are independently stated regularity and score-function bounds whose assumptions do not include the target CMDP deterministic-deployment guarantee, so they count as real evidence rather than a self-referential reduction. A separate, non-circularity concern is the proof of Theorem 4.2, which asserts 'by exploiting the superadditivity of (.)^psi' the inequality ||grad L_D,0||^psi <= ||grad L_P,0||^psi + C^psi; for convex x^psi with psi>1 this has the wrong direction, and a correct bound would degrade alpha_D or enlarge beta_dagger. That is a correctness/validity issue, not a circular reduction, so it does not raise the circularity score.
Assumptions & free parameters
free parameters (4)
- regularization parameter omega =
omega = O(epsilon) in theory; 10^-4 or 10^-2 in experiments
- stochasticity level sigma =
sigma = O(epsilon) in theory; sigma^2 in {0.01, 0.05, 0.1, 0.5, 1} in deployment study
- potential weight chi =
chi < 1/5
- learning rate constants =
zeta_lambda = O(omega sigma^2 epsilon^{2/psi}), zeta_theta = O(omega^3 sigma^2 epsilon^{2/psi})
assumptions (7)
- domain assumption Assumption 3.1: existence of a saddle point of the unregularized Lagrangian, equivalently strong duality for the parametric policy class
- domain assumption Assumption 3.2 and its deterministic version Assumption 4.3: weak psi-gradient domination of the Lagrangian
- domain assumption Assumption 3.3: smoothness and Lipschitz regularity of the Lagrangian in theta and lambda
- domain assumption Assumption 3.4: unbiased gradient estimators with bounded variance
- domain assumption Assumptions 4.1 and 4.2: Lipschitz and smoothness of deterministic costs with respect to theta and nonstationary policies
- domain assumption Assumption 4.4: deterministic policy is Lipschitz in its parameters, needed only for AB exploration
- domain assumption Assumption 4.5: bounded score moments of the white noise distribution
Cite this review
Pith. "Pith review of Learning Deterministic Policies with Policy Gradients in Constrained Markov Decision Processes." pith.science (2026). https://pith.science/paper/VZ66TI76
@misc{pith2026250605953,
author = {Pith},
title = {Pith review of: Learning Deterministic Policies with Policy Gradients in Constrained Markov Decision Processes},
year = {2026},
howpublished = {\url{https://pith.science/paper/VZ66TI76}},
note = {Machine review of arXiv:2506.05953}
}
read the original abstract
Constrained Reinforcement Learning (CRL) addresses sequential decision-making problems where agents are required to achieve goals by maximizing the expected return while meeting domain-specific constraints. In this setting, policy-based methods are widely used thanks to their advantages when dealing with continuous-control problems. These methods search in the policy space with an action-based or a parameter-based exploration strategy, depending on whether they learn the parameters of a stochastic policy or those of a stochastic hyperpolicy. We introduce an exploration-agnostic algorithm, called C-PG, which enjoys global last-iterate convergence guarantees under gradient domination assumptions. Furthermore, under specific noise models where the (hyper)policy is expressed as a stochastic perturbation of the actions or of the parameters of an underlying deterministic policy, we additionally establish global last-iterate convergence guarantees of C-PG to the optimal deterministic policy. This holds when learning a stochastic (hyper)policy and subsequently switching off the stochasticity at the end of training, thereby deploying a deterministic policy. Finally, we empirically validate both the action-based (C-PGAE) and parameter-based (C-PGPE) variants of C-PG on constrained control tasks, and compare them against state-of-the-art baselines, demonstrating their effectiveness, in particular when deploying deterministic policies after training.
Figures
Figures from the paper (5 more)
Reference graph
Works this paper leans on
-
[7]
Robotics and Autonomous Systems 131, 103568
Combining reinforcement learning with rule-based controllers for transparent and general decision-making in autonomous driving. Robotics and Autonomous Systems 131, 103568. Lillicrap,T.P.,Hunt,J.J.,Pritzel,A.,Heess,N.M.O.,Erez,T.,Tassa,Y.,Silver,D.,Wierstra,D.,2015. Continuouscontrolwithdeepreinforcement learning. CoRR abs/1509.02971. Liu, T., Zhou, R., K...
arXiv 2015
-
[9]
On the global convergence rates of softmax policy gradient methods, in: Proceedings of the International Conference on Machine Learning (ICML), PMLR. pp. 6820–6829. Metelli,A.M.,Papini,M.,Faccio,F.,Restelli,M.,2018.Policyoptimizationviaimportancesampling,in:AdvancesinNeuralInformationProcessing Systems (NeurIPS), pp. 5447–5459. Mondal,W.U.,Aggarwal,V.,202...
arXiv 2018
-
[13]
Primal-dual learning for the model-free risk-constrained linear quadratic regulator, in: Proceedings of the Conference on Learning for Dynamics and Control (CDC), PMLR. pp. 702–714. Zheng,T.,You,P.,Mallada,E.,2022. Constrainedreinforcementlearningviadissipativesaddleflowdynamics,in:AsilomarConferenceonSignals, Systems, and Computers (ACSSC), IEEE. pp. 136...
work page 2022
-
[36]
Ding,D.,Wei,X.,Yang,Z.,Wang,Z.,Jovanovic,M.R.,2021.Provablyefficientsafeexplorationviaprimal-dualpolicyoptimization,in:Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), PMLR. pp. 3304–3312. Ding, D., Zhang, K., Basar, T., Jovanovic, M.,
work page 2021
-
[2002]
Self learning control of constrained markov chains - a gradient approach, in: IEEE Conference on Decision and Control (CDC), IEEE. pp. 1940–1945. Williams, R.J.,
work page 1940
-
[2006]
Policy gradient methods for robotics, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE. pp. 2219–2225. Rozada,S.,Ding,D.,Marques,A.G.,Ribeiro,A.,2025. Deterministicpolicygradientprimal-dualmethodsforcontinuous-spaceconstrainedmdps, in: AAAI Conference on Artificial Intelligence, pp. 20200–20208. Sehnke,F.,Osendorfer,C.,Rücksti...
work page 2025
-
[2007]
Optimal control: linear quadratic methods. Courier Corporation. Azizzadenesheli,K.,Yue,Y.,Anandkumar,A.,2018. Policygradientinpartiallyobservableenvironments:Approximationandconvergence. arXiv preprint arXiv:1810.07900 . Bai, Q., Bedi, A.S., Agarwal, M., Koppel, A., Aggarwal, V.,
arXiv 2018
-
[2012]
Journal of Optimization Theory and Applications 153, 688–708
An online actor-critic algorithm with function approximation for constrained markov decision processes. Journal of Optimization Theory and Applications 153, 688–708. Brunke,L.,Greeff,M.,Hall,A.W.,Yuan,Z.,Zhou,S.,Panerati,J.,Schoellig,A.P.,2022. Safelearninginrobotics:Fromlearning-basedcontrolto safe reinforcement learning. Annual Review of Control, Roboti...
work page 2022
Show all 13 references
-
[2018]
arXiv preprint arXiv:1801.08757
Safe exploration in continuous action spaces. arXiv preprint arXiv:1801.08757 . Deisenroth, M.P., Neumann, G., Peters, J.,
-
[2020]
Advances in Neural Information Processing Systems (NeurIPS) 33, 8378–8390
Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems (NeurIPS) 33, 8378–8390. Ding,D.,Zhang,K.,Duan,J.,Başar,T.,Jovanović,M.R.,2022. Convergenceandsamplecomplexityofnaturalpolicygradientprimal-d...
2022
-
[2021]
arXiv preprint arXiv:2111.00552
Policy optimization for constrained mdps with provable fast global convergence. arXiv preprint arXiv:2111.00552 . Liu, Y., Ding, J., Liu, X.,
-
[2022]
A dual approach to constrained markov decision processes with entropy regularization, in: Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), PMLR. pp. 1887–1909. Yu, M., Yang, Z., Kolar, M., Wang, Z.,
1909
-
[2023]
11506–11533
Algorithm for constrained markov decision processwithlinearconvergence,in:ProceedingsoftheInternationalConferenceonArtificialIntelligenceandStatistics(AISTATS),PMLR.pp. 11506–11533. Gravell,B.,Esfahani,P.M.,Summers,T.,2020. Learningoptimalcontrollersforlinearsystemswithmultipl...
2020
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.