Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins

• URL: http://arxiv.org/abs/2602.10917v1
• Date: Wed, 11 Feb 2026 14:54:26 GMT
• Title: Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins
• Authors: Qian Zuo, Zhiyong Wang, Fengxiang He,
• Abstract summary: We study safe online reinforcement learning in Constrained Markov Decision Processes (CMDPs) under strong regret and violation metrics.<n>Existing primal-dual methods that achieve sublinear strong reward regret incur growing strong constraint violation or are restricted to average-iterate convergence due to inherent oscillations.<n>We propose the Flexible safety Domain Optimization via Margin-regularized Exploration (FlexDOME) algorithm, the first to provably achieve near-constant $tildeO(1)$ strong constraint violation alongside sublinear strong regret and non-asymptotic last-iterate convergence.
• Score: 31.581870065866568
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study safe online reinforcement learning in Constrained Markov Decision Processes (CMDPs) under strong regret and violation metrics, which forbid error cancellation over time. Existing primal-dual methods that achieve sublinear strong reward regret inevitably incur growing strong constraint violation or are restricted to average-iterate convergence due to inherent oscillations. To address these limitations, we propose the Flexible safety Domain Optimization via Margin-regularized Exploration (FlexDOME) algorithm, the first to provably achieve near-constant $\tilde{O}(1)$ strong constraint violation alongside sublinear strong regret and non-asymptotic last-iterate convergence. FlexDOME incorporates time-varying safety margins and regularization terms into the primal-dual framework. Our theoretical analysis relies on a novel term-wise asymptotic dominance strategy, where the safety margin is rigorously scheduled to asymptotically majorize the functional decay rates of the optimization and statistical errors, thereby clamping cumulative violations to a near-constant level. Furthermore, we establish non-asymptotic last-iterate convergence guarantees via a policy-dual Lyapunov argument. Experiments corroborate our theoretical findings.

Related papers

• Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds [12.025550076793396]
  We study trade-offs between convergence rate and gradient to robustness errors in the context of first-order methods.<n>Under potentially biased sub-Gaussian gradient errors, we derive non-asymptotic bounds on a finite-time analogue of the risk-sensitive index (RSI)<n>In the case of smooth strongly convex functions, we also observe an analogous trade-off between RSI and convergence-rate bounds.
  arXiv  Detail & Related papers  (2025-09-17T01:56:31Z)
• Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality [53.525547349715595]
  We propose a novel primal-only algorithm called Rectified Robust Policy Optimization (RRPO)<n>RRPO operates directly on the primal problem without relying on dual formulations.<n>We show convergence to an approximately optimal feasible policy with complexity matching the best-known lower bound.
  arXiv  Detail & Related papers  (2025-08-24T16:59:38Z)
• Viability of Future Actions: Robust Safety in Reinforcement Learning via Entropy Regularization [47.30677525394649]
  We analyze the interplay between two well-established techniques in model-free reinforcement learning: entropy regularization and constraints penalization.<n>We show that entropy regularization in constrained RL inherently biases learning toward maximizing the number of future viable actions, thereby promoting constraints satisfaction robust to action noise.<n>We conclude that the connection between entropy regularization and robustness is a promising avenue for further empirical and theoretical investigation.
  arXiv  Detail & Related papers  (2025-06-12T16:34:19Z)
• Tilted Quantile Gradient Updates for Quantile-Constrained Reinforcement Learning [12.721239079824622]
  We propose a safe reinforcement learning (RL) paradigm that enables a higher level of safety without any expectation-form approximations.<n>A tilted update strategy for quantile gradients is implemented to compensate the asymmetric distributional density.<n>Experiments demonstrate that the proposed model fully meets safety requirements (quantile constraints) while outperforming the state-of-the-art benchmarks with higher return.
  arXiv  Detail & Related papers  (2024-12-17T18:58:00Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  We consider the problem of quantifying uncertainty over expected cumulative rewards in model-based reinforcement learning. We propose a new uncertainty Bellman equation (UBE) whose solution converges to the true posterior variance over values. We introduce a general-purpose policy optimization algorithm, Q-Uncertainty Soft Actor-Critic (QU-SAC) that can be applied for either risk-seeking or risk-averse policy optimization.
  arXiv  Detail & Related papers  (2023-12-07T15:55:58Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• Penalized Proximal Policy Optimization for Safe Reinforcement Learning [68.86485583981866]
  We propose Penalized Proximal Policy Optimization (P3O), which solves the cumbersome constrained policy iteration via a single minimization of an equivalent unconstrained problem. P3O utilizes a simple-yet-effective penalty function to eliminate cost constraints and removes the trust-region constraint by the clipped surrogate objective. We show that P3O outperforms state-of-the-art algorithms with respect to both reward improvement and constraint satisfaction on a set of constrained locomotive tasks.
  arXiv  Detail & Related papers  (2022-05-24T06:15:51Z)
• Policy-based Primal-Dual Methods for Concave CMDP with Variance Reduction [18.95829896746939]
  We study Concave CMDPs where both the objective and constraints are defined as concave functions of the state-action occupancy measure. We propose the Variance-Reduced Primal-Dual Policy Gradient, which updates the primal variable via policy gradient ascent and the dual variable via projected sub-gradient descent.
  arXiv  Detail & Related papers  (2022-05-22T02:50:16Z)
• Fast Global Convergence of Policy Optimization for Constrained MDPs [17.825031573375725]
  We show that gradient-based methods can achieve an $mathcalO(log(T)/T)$ global convergence rate both for the optimality gap and the constraint violation. When Slater's condition is satisfied and known a priori, zero constraint violation can be further guaranteed for a sufficiently large $T$.
  arXiv  Detail & Related papers  (2021-10-31T17:46:26Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  We introduce a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting. To our best knowledge, this gives the firstever-known stability and generalization for SGD with even non-differentiable loss functions.
  arXiv  Detail & Related papers  (2020-06-15T06:30:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.