Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins
This addresses a key limitation in safe reinforcement learning for applications requiring strict safety guarantees, though it is incremental as it builds on existing primal-dual methods.
The paper tackled the problem of achieving low constraint violation and sublinear regret in safe online reinforcement learning for Constrained Markov Decision Processes, and the result was the FlexDOME algorithm that provably achieves near-constant strong constraint violation with sublinear strong regret and last-iterate convergence.
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.