Introduction
Safe reinforcement learning seeks high reward while respecting cost constraints [1 ] , [2 ] . Lagrangian methods introduce a multiplier λ \lambda λ that controls the cost penalty during policy improvement [3 ] , [4 ] , [5 ] . For a fixed policy with mean cost c c c , the multiplier objective is λ ( d − c ) \lambda(d-c) λ ( d − c ) . Its exact minimizer on [ 0 , λ max ] [0,\lambda_{\max}] [ 0 , λ m a x ] switches from zero to λ max \lambda_{\max} λ m a x as c c c crosses the budget d d d . This fixed-policy bang-bang response arises even with exact cost estimates.
Quadratic regularization makes the fixed-policy response continuous. Its penalty stays zero for c ≤ d c \le d c ≤ d and activates after a mean-cost violation. This violation-triggered dual activation can lag policy changes when cost estimates are delayed. We seek smooth feedback that can activate within the feasible region based on current trajectories. Incremental gradient updates can oscillate through policy coupling. PID uses tuned gains to combine damping and cost-trend feedback [6 ] , [7 ] . Entropy regularization can smooth the dual function when the policy is reoptimized for each multiplier [8 ] , [9 ] . With the policy held fixed, the multiplier objective remains linear, so its exact minimizer exhibits bang-bang switching. Table 1 compares these methods.
Table 1. Single-constraint multiplier responses with policy and return statistics fixed. Inner solve counts scalar optimization steps to multiplier accuracy ε λ \varepsilon_\lambda ε λ . Linear objectives admit an exact closed-form solution (4); SDLA uses ternary search. Bang-bang refers to the exact response. For PID, “No closed form” denotes feedback updates without a closed-form optimal response; — denotes not applicable. Entropy-Regularized refers to policy entropy.
We propose Structural DuaL Adaptation (SDLA) to replace fixed-policy bang-bang switching with structured smooth feedback. Its trajectory-dependent surrogate combines log-sum-exp weighting of penalized returns with current-cost centering. Quadratic regularization and trajectory-weighted cost variance control response sensitivity, yielding a unique continuous multiplier response. Ternary search computes this response without a dual gradient stepsize.
Our main contributions are:
Structured multiplier response. We construct a strongly convex surrogate whose unique multiplier response replaces fixed-policy bang-bang switching with a continuous transition. Current-cost centering and trajectory weighting determine its activation and saturation regimes. A scalar inner solve computes the response without a dual gradient stepsize.
Sensitivity characterization. We bound response sensitivity, including clipped endpoints, and identify the interior gain through regularization and trajectory-weighted cost variance. For entropy-regularized tabular policies, we bound fixed-parameter equilibrium feasibility and reward gaps and establish convergence of delayed updates with actor and dual errors under mild assumptions.
Practical actor–critic evaluation. On HASARD, PPO-SDLA achieves higher reported mean reward than the human baseline in 6 of 18 task–difficulty settings, including four
with lower mean cost. All six settings meet their respective mean-cost budgets. To the best of our knowledge, this is the first report of simultaneously higher mean reward and lower mean cost than the human baseline across multiple HASARD settings. Ablations examine the surrogate components, while training-time diagnostics quantify multiplier changes and constraint tracking.
Preliminary
Constrained Markov Decision Process
We consider a single-constraint discounted CMDP ( S , A , P , r , c , γ , d ) (\mathcal{S},\mathcal{A},P,r,c,\gamma,d) ( S , A , P , r , c , γ , d ) [10 ] , with 0 ≤ r ≤ R max 0 \le r \le R_{\max} 0 ≤ r ≤ R m a x , 0 ≤ c ≤ C max 0 \le c \le C_{\max} 0 ≤ c ≤ C m a x , γ ∈ [ 0 , 1 ) \gamma\in[0,1) γ ∈ [ 0 , 1 ) , and a fixed initial distribution. Let R = ∑ t ≥ 0 γ t r ( s t , a t ) R = \sum_{t\geq0}\gamma^t r(s_t,a_t) R = ∑ t ≥ 0 γ t r ( s t , a t ) and C = ∑ t ≥ 0 γ t c ( s t , a t ) C = \sum_{t\geq0}\gamma^t c(s_t,a_t) C = ∑ t ≥ 0 γ t c ( s t , a t ) denote trajectory returns, and write J r ( π ) = E π R J^r(\pi)=\mathbb{E}_{\pi}R J r ( π ) = E π R , J c ( π ) = E π C J^c(\pi)=\mathbb{E}_{\pi}C J c ( π ) = E π C . The objective is
max π J r ( π ) s.t. J c ( π ) ≤ d . (1) \max_{\pi} J^r(\pi) \qquad\text{s.t.}\qquad J^c(\pi)\leq d. \tag*{(1)} π max J r ( π ) s.t. J c ( π ) ≤ d . (1)
Returns satisfy R ≤ R max / ( 1 − γ ) R \leq R_{\max}/(1-\gamma) R ≤ R m a x / ( 1 − γ ) and C ≤ C ˉ : = C max / ( 1 − γ ) C \leq\bar{C}:=C_{\max}/(1-\gamma) C ≤ C ˉ := C m a x / ( 1 − γ ) . Discounted policy entropy is H ( π ) = E π ∑ t ≥ 0 γ t [ − log π ( a t ∣ s t ) ] H(\pi)=\mathbb{E}_{\pi}\sum_{t\geq0}\gamma^t[-\log\pi(a_t\mid s_t)] H ( π ) = E π ∑ t ≥ 0 γ t [ − log π ( a t ∣ s t )] .
Related Methods
Gradient primal–dual updates accumulate cost errors, and coupling with policy optimization can cause oscillation and stepsize sensitivity [6 ] , [11 ] . PID control adds proportional damping and derivative feedback based on cost trends [6 ] . Augmented penalties [12 ] , critic calibration [13 ] , and regularized primal–dual methods [14 ] , [15 ] provide other stabilization mechanisms. SDLA derives its response by optimizing a scalar surrogate on a frozen trajectory batch, with explicit activation and sensitivity bounds.
Penalty methods require selecting a penalty strength [16 ] . Constrained or projected methods introduce additional actor optimization steps [17 ] , [18 ] , [19 ] , [20 ] , while state augmentation requires budget-conditioned policy inputs [21 ] , [22 ] . For constrained multi-objective RL, Gu et al. [23 ] combine gradient manipulation across reward objectives with cost-reducing policy updates when constraints are violated. Appendix E details these tradeoffs. SDLA changes the multiplier response within an actor–critic implementation.
Policy Dual Smoothness and Fixed-Policy Responses
Entropy regularization improves the optimization landscape of CMDPs by smoothing policy optimization. With entropy coefficient α > 0 \alpha>0 α > 0 , the entropy-regularized problem is
max π { J r ( π ) + α H ( π ) } s.t. J c ( π ) ≤ d . (2) \max_{\pi}\{J^r(\pi)+\alpha H(\pi)\}\qquad\text{s.t.}\qquad J^c(\pi)\leq d. \tag*{(2)} π max { J r ( π ) + α H ( π )} s.t. J c ( π ) ≤ d . (2)
Lagrangian dual. The corresponding policy dual is [8 ]
g s t d ( λ ) : = sup π { J r ( π ) + α H ( π ) − λ ( J c ( π ) − d ) } . (3) g_{\mathrm{std}}(\lambda):=\sup_{\pi}\{J^r(\pi)+\alpha H(\pi)-\lambda(J^c(\pi)-d)\}. \tag*{(3)} g std ( λ ) := π sup { J r ( π ) + α H ( π ) − λ ( J c ( π ) − d )} . (3)
In entropy-regularized tabular formulations, policy-dual smoothness enables accelerated optimization [8 ] , [9 ] . These guarantees involve solving, or approximating, the underlying policy optimization problem.
Fixed-policy dual response. For a frozen policy π c u r \pi_{\mathrm{cur}} π cur , both J r ( π c u r ) J^r(\pi_{\mathrm{cur}}) J r ( π cur ) and α H ( π c u r ) \alpha H(\pi_{\mathrm{cur}}) α H ( π cur ) are constant with respect to λ \lambda λ . Writing c = J c ( π c u r ) c=J^c(\pi_{\mathrm{cur}}) c = J c ( π cur ) , the exact multiplier response is
arg min 0 ≤ λ ≤ λ max λ ( d − c ) = { { 0 } , c < d , [ 0 , λ max ] , c = d , { λ max } , c > d . (4) \underset{0\leq\lambda\leq\lambda_{\max}}{\arg\min}\ \lambda(d-c)=
\begin{cases}
\{0\}, & c<d,\\
[0,\lambda_{\max}], & c=d,\\
\{\lambda_{\max}\}, & c>d.
\end{cases} \tag*{(4)} 0 ≤ λ ≤ λ m a x arg min λ ( d − c ) = ⎩ ⎨ ⎧ { 0 } , [ 0 , λ m a x ] , { λ m a x } , c < d , c = d , c > d . (4)
This bang-bang response concerns the fixed-policy subproblem. The policy dual in (3) reoptimizes the policy as λ \lambda λ changes. Quadratic regularization smooths the fixed-policy response and retains the activation boundary c = d c=d c = d : the multiplier remains zero for c ≤ d c\leq d c ≤ d and activates after a mean-cost violation. SDLA builds on this curvature to construct structured smooth feedback from current mean and trajectory-weighted costs. Its response has controlled sensitivity and can also activate within the feasible region.
Structural Dual Adaptation
Surrogate Dual Formulation
We first define SDLA through expectations under a fixed policy π \pi π . Write c π = J c ( π ) c_{\pi}=J^c(\pi) c π = J c ( π ) and fix τ , β , λ max > 0 \tau,\beta,\lambda_{\max}>0 τ , β , λ m a x > 0 . Returns satisfy the bounds in § 2 .
Definition 3.1 (Population Surrogate Dual). The population surrogate dual is
g π ( λ ) = τ log E π e ( R − λ C ) / τ + λ ( d − c π ) + λ 2 2 β , (5) g_{\pi}(\lambda)=\tau\log\mathbb{E}_{\pi}e^{(R-\lambda C)/\tau}+\lambda(d-c_{\pi})+\frac{\lambda^2}{2\beta}, \tag*{(5)} g π ( λ ) = τ log E π e ( R − λ C ) / τ + λ ( d − c π ) + 2 β λ 2 , (5)
for λ ∈ [ 0 , λ max ] \lambda\in[0,\lambda_{\max}] λ ∈ [ 0 , λ m a x ] . Its multiplier response is
Λ ( π ) = arg min 0 ≤ λ ≤ λ max g π ( λ ) . (6) \Lambda(\pi)=\underset{0\leq\lambda\leq\lambda_{\max}}{\arg\min}\ g_{\pi}(\lambda). \tag*{(6)} Λ ( π ) = 0 ≤ λ ≤ λ m a x arg min g π ( λ ) . (6)
Write F π ( λ ) = τ log E π e ( R − λ C ) / τ F_{\pi}(\lambda)=\tau\log\mathbb{E}_{\pi}e^{(R-\lambda C)/\tau} F π ( λ ) = τ log E π e ( R − λ C ) / τ . Its derivative supplies the trajectory-weighted cost
m π ( λ ) : = − F π ′ ( λ ) = E π [ C e ( R − λ C ) / τ ] E π e ( R − λ C ) / τ . (7) m_{\pi}(\lambda):=-F'_{\pi}(\lambda)=\frac{\mathbb{E}_{\pi}[C e^{(R-\lambda C)/\tau}]}{\mathbb{E}_{\pi}e^{(R-\lambda C)/\tau}}. \tag*{(7)} m π ( λ ) := − F π ′ ( λ ) = E π e ( R − λ C ) / τ E π [ C e ( R − λ C ) / τ ] . (7)
Trajectories with higher penalized returns R − λ C R-\lambda C R − λ C receive greater weight. Centering by λ ( d − c π ) \lambda(d-c_{\pi}) λ ( d − c π ) combines mean and trajectory-weighted costs into the signal c π + m π ( λ ) − d c_{\pi}+m_{\pi}(\lambda)-d c π + m π ( λ ) − d . Quadratic regularization and trajectory-weighted cost variance control the response curvature.
Structural Properties and Activation
Lemma 3.2 (Curvature and continuous activation). For any fixed policy with 0 ≤ C ≤ C ˉ 0\leq C\leq\bar{C} 0 ≤ C ≤ C ˉ , the population surrogate satisfies
g π ′ ( λ ) = d − c π − m π ( λ ) + λ / β , (8) g'_{\pi}(\lambda)=d-c_{\pi}-m_{\pi}(\lambda)+\lambda/\beta, \tag*{(8)} g π ′ ( λ ) = d − c π − m π ( λ ) + λ / β , (8)
g π ′ ′ ( λ ) = Var q π , λ ( C ) τ + 1 β . (9) g''_{\pi}(\lambda)=\frac{\operatorname{Var}_{q_{\pi,\lambda}}(C)}{\tau}+\frac{1}{\beta}. \tag*{(9)} g π ′′ ( λ ) = τ Var q π , λ ( C ) + β 1 . (9)
Here q π , λ q_{\pi,\lambda} q π , λ is the trajectory law reweighted by e ( R − λ C ) / τ e^{(R-\lambda C)/\tau} e ( R − λ C ) / τ . Hence g π g_{\pi} g π is 1 / β 1/\beta 1/ β -strongly convex and ( 1 / β + C ˉ 2 / ( 4 τ ) ) (1/\beta+\bar{C}^{2}/(4\tau)) ( 1/ β + C ˉ 2 / ( 4 τ )) -smooth. Its response Λ ( π ) \Lambda(\pi) Λ ( π ) is unique and satisfies
Λ ( π ) > 0 ⟺ c π + m π ( 0 ) > d . (10) \Lambda(\pi)>0 \quad\Longleftrightarrow\quad c_{\pi}+m_{\pi}(0)>d. \tag*{(10)} Λ ( π ) > 0 ⟺ c π + m π ( 0 ) > d . (10)
Moreover, 0 ≤ Λ ( π ) ≤ min { λ max , β [ c π + m π ( 0 ) − d ] + } 0\leq\Lambda(\pi)\leq\min\{\lambda_{\max},\beta[c_{\pi}+m_{\pi}(0)-d]_{+}\} 0 ≤ Λ ( π ) ≤ min { λ m a x , β [ c π + m π ( 0 ) − d ] + } .
Feasible-region activation. Condition (10) permits penalties before the current policy’s mean cost exceeds the budget.
Proposition 4.2 quantifies equilibrium constraint violations and regularized reward gaps for fixed parameters. The endpoint derivatives distinguish three response regimes:
Inactive: g π ′ ( 0 ) ≥ 0 g_{\pi}'(0) \ge0 g π ′ ( 0 ) ≥ 0 gives Λ ( π ) = 0 \Lambda(\pi) = 0 Λ ( π ) = 0 .
Transitional: g π ′ ( 0 ) < 0 < g π ′ ( λ max ) g_{\pi}'(0) < 0 < g_{\pi}'(\lambda_{\max}) g π ′ ( 0 ) < 0 < g π ′ ( λ m a x ) gives 0 < Λ ( π ) < λ max 0 < \Lambda(\pi) < \lambda_{\max} 0 < Λ ( π ) < λ m a x and c π + m π ( Λ ( π ) ) = d + Λ ( π ) / β c_{\pi} + m_{\pi}(\Lambda(\pi)) = d + \Lambda(\pi)/\beta c π + m π ( Λ ( π )) = d + Λ ( π ) / β .
Saturated: g π ′ ( λ max ) ≤ 0 g_{\pi}'(\lambda_{\max}) \le0 g π ′ ( λ m a x ) ≤ 0 gives Λ ( π ) = λ max \Lambda(\pi) = \lambda_{\max} Λ ( π ) = λ m a x .
The lemma implies Λ ( π ) → 0 \Lambda(\pi) \to0 Λ ( π ) → 0 as [ c π + m π ( 0 ) − d ] + → 0 [c_{\pi} + m_{\pi}(0) - d]_{+} \to0 [ c π + m π ( 0 ) − d ] + → 0 . Section 3.3 quantifies sensitivity across these regimes; Appendix B gives the proofs. Section 6.4 compares empirical variants with fixed and adaptive centering.
Closed-Loop Multiplier Feedback
For consecutive policies π t = π θ t \pi_t = \pi_{\theta_t} π t = π θ t , write g t = g π t g_t = g_{\pi_t} g t = g π t , m t = m π t m_t = m_{\pi_t} m t = m π t , c t = J c ( π t ) c_t = J^{c}(\pi_t) c t = J c ( π t ) , and ℓ t = Λ ( π t ) \ell_t = \Lambda(\pi_t) ℓ t = Λ ( π t ) . For the actor interpretation, set r ( θ ) = J c ( π θ ) r(\theta) = J^{c}(\pi_{\theta}) r ( θ ) = J c ( π θ ) and c ( θ ) = J c ( π θ ) c(\theta) = J^{c}(\pi_{\theta}) c ( θ ) = J c ( π θ ) . Keeping τ \tau τ , β \beta β , λ max \lambda_{\max} λ m a x fixed isolates the response to policy changes.
The following result quantifies how the multiplier increases or decreases as the mean and weighted costs change. Define
D t : = ( c t + 1 − c t ) + m t + 1 ( ℓ t ) − m t ( ℓ t ) , δ t : = ℓ t + 1 − ℓ t . (11) D_t := (c_{t+1} - c_t) + m_{t+1}(\ell_t) - m_t(\ell_t), \qquad\delta_t := \ell_{t+1} - \ell_t. \tag*{(11)} D t := ( c t + 1 − c t ) + m t + 1 ( ℓ t ) − m t ( ℓ t ) , δ t := ℓ t + 1 − ℓ t . (11)
Theorem 3.3 (Closed-loop multiplier feedback). For any two consecutive policies, including responses at either endpoint,
δ t 2 β ≤ δ t D t , ∣ δ t ∣ ≤ β ∣ D t ∣ . (12) \frac{\delta_t^2}{\beta} \le\delta_t D_t, \qquad|\delta_t| \le\beta|D_t|. \tag*{(12)} β δ t 2 ≤ δ t D t , ∣ δ t ∣ ≤ β ∣ D t ∣. (12)
Thus D t < 0 D_t < 0 D t < 0 gives ℓ t + 1 ≤ ℓ t \ell_{t+1} \le\ell_t ℓ t + 1 ≤ ℓ t , and D t > 0 D_t > 0 D t > 0 gives ℓ t + 1 ≥ ℓ t \ell_{t+1} \ge\ell_t ℓ t + 1 ≥ ℓ t . Both implications are strict when ℓ t ∈ ( 0 , λ max ) \ell_t \in(0, \lambda_{\max}) ℓ t ∈ ( 0 , λ m a x ) . If both responses are interior, then
ℓ t + 1 − ℓ t = D t β − 1 + V ‾ t + 1 , (13) \ell_{t+1} - \ell_t = \frac{D_t}{\beta^{-1} + \overline{V}_{t+1}}, \tag*{(13)} ℓ t + 1 − ℓ t = β − 1 + V t + 1 D t , (13)
where V ‾ t + 1 ≥ 0 \overline{V}_{t+1} \ge0 V t + 1 ≥ 0 is the average trajectory-weighted cost variance divided by τ \tau τ along the segment from ℓ t \ell_t ℓ t to ℓ t + 1 \ell_{t+1} ℓ t + 1 .
Proof sketch. Combining the constrained first-order conditions with strong convexity gives (12), including clipped endpoints. For interior responses, integrating the curvature between the two stationary points gives (13). Appendix B.2 provides the full proof.
Both weighted costs in D t D_t D t are evaluated at the old multiplier ℓ t \ell_t ℓ t , so their difference measures the change in trajectory information under a common penalty. A larger multiplier places greater weight on cost reduction in the actor update. The resulting policy supplies the next trajectory batch and dual signal, completing the feedback loop.
(12) bounds the multiplier change in proportion to the combined cost-signal change. In the interior, the response gain is β / ( 1 + β V ‾ t + 1 ) \beta/(1 + \beta\overline{V}_{t+1}) β / ( 1 + β V t + 1 ) . Increasing the multiplier downweights higher-cost trajectories, adding the trajectory-weighted cost variance term to the curvature of the quadratic regularizer. For a given feedback signal, this reduces the multiplier change. Clipping can keep the multiplier fixed under a nonzero signal, as captured by (12).
Theoretical Guarantees
Convergence
We consider a finite discounted CMDP with tabular policies and 0 < γ < 1 0 < \gamma< 1 0 < γ < 1 . Let Π = ∏ s ∈ S Δ ( A ) \Pi= \prod_{s \in\mathcal{S}} \Delta(\mathcal{A}) Π = ∏ s ∈ S Δ ( A ) be the tabular policy space, with Frobenius norm ∥ ⋅ ∥ F \lVert\cdot\rVert_F ∥ ⋅ ∥ F , and assume the initial distribution satisfies ρ ( s ) > 0 \rho(s) > 0 ρ ( s ) > 0 for every state. Fix a policy-entropy coefficient α > 0 \alpha> 0 α > 0 and write
J α ( π ) = J r ( π ) + α H ( π ) , J_{\alpha}(\pi) = J^{r}(\pi) + \alpha H(\pi), J α ( π ) = J r ( π ) + α H ( π ) ,
L α ( π , λ ) = J α ( π ) − λ [ J c ( π ) − d ] , \mathcal{L}_{\alpha}(\pi,\lambda) = J_{\alpha}(\pi) - \lambda[J^{c}(\pi) - d], L α ( π , λ ) = J α ( π ) − λ [ J c ( π ) − d ] ,
B ( λ ) = arg max π ∈ Π L α ( π , λ ) . (14) B(\lambda) = \underset{\pi\in\Pi}{\operatorname{arg\,max}}\ \mathcal{L}_{\alpha}(\pi,\lambda). \tag*{(14)} B ( λ ) = π ∈ Π arg max L α ( π , λ ) . (14)
The policy-entropy coefficient α \alpha α is distinct from the trajectory temperature τ \tau τ . Write Λ β , τ ( π ) \Lambda_{\beta,\tau}(\pi) Λ β , τ ( π ) and m π , τ ( λ ) m_{\pi,\tau}(\lambda) m π , τ ( λ ) for the response and trajectory-weighted cost in Section 3.1, making parameter dependence explicit. Let K c K_c K c and K m ( τ ) K_m(\tau) K m ( τ ) be Lipschitz constants for J c ( π ) J^c(\pi) J c ( π ) and m π , τ ( λ ) m_{\pi,\tau}(\lambda) m π , τ ( λ ) in Frobenius norm, with the latter uniform over λ ∈ [ 0 , λ max ] \lambda\in[0,\lambda_{\max}] λ ∈ [ 0 , λ m a x ] . Set κ = min s ρ ( s ) > 0 \kappa= \min_s \rho(s) > 0 κ = min s ρ ( s ) > 0 and L Λ = β [ K c + K m ( τ ) ] L_{\Lambda} = \beta[K_c + K_m(\tau)] L Λ = β [ K c + K m ( τ )] . Appendix B.2.4 derives these constants and the actor response bound from the soft-policy optimality identity [8 ] .
Take a full-support initial policy and λ 0 ∈ [ 0 , λ max ] \lambda_0 \in[0,\lambda_{\max}] λ 0 ∈ [ 0 , λ m a x ] . At outer step t t t , hold λ t \lambda_t λ t fixed and run K t ≥ 1 K_t \ge1 K t ≥ 1 actor updates from π t 0 = π t \pi_t^0 = \pi_t π t 0 = π t :
π t k + 1 ( a ∣ s ) ∝ [ π t k ( a ∣ s ) ] 1 − ω exp ( Q ^ t k ( s , a ) / α ) . \pi_t^{k+1}(a \mid s) \propto[\pi_t^k(a \mid s)]^{1-\omega} \exp(\widehat{Q}_t^k(s,a)/\alpha). π t k + 1 ( a ∣ s ) ∝ [ π t k ( a ∣ s ) ] 1 − ω exp ( Q t k ( s , a ) / α ) .
For 0 < ω ≤ 1 0 < \omega\le1 0 < ω ≤ 1 , assume ∥ Q ^ t k − Q π t k ∥ ∞ ≤ ξ t ≤ ξ ‾ < ∞ \lVert\widehat{Q}_t^k - Q_{\pi_t^k}\rVert_{\infty} \le\xi_t \le\overline{\xi} < \infty ∥ Q t k − Q π t k ∥ ∞ ≤ ξ t ≤ ξ < ∞ and set π t + 1 = π t K t \pi_{t+1} = \pi_t^{K_t} π t + 1 = π t K t . The cases ω = 1 \omega= 1 ω = 1 and 0 < ω < 1 0 < \omega< 1 0 < ω < 1 correspond to tabular soft policy improvement and an entropy-regularized KL-PPO update, respectively [24 , 25 ] . The analysis establishes tabular convergence under mild assumptions specified below. Section 6 evaluates neural PPO-Clip and SAC empirically.
Write b = K c / κ b = K_c/\kappa b = K c / κ , L Λ = L Λ ( β , τ ) L_{\Lambda} = L_{\Lambda}(\beta,\tau) L Λ = L Λ ( β , τ ) , and χ = 1 − ( 1 − γ ) ω \chi= 1 - (1 - \gamma)\omega χ = 1 − ( 1 − γ ) ω . Appendix B.3 specifies the updates and derives uniform constants A 0 , A 1 A_0,A_1 A 0 , A 1 from Cen et al. [26 ] , with actor error at most A 0 χ K t − 1 + A 1 ξ t A_0\chi^{K_t-1} + A_1\xi_t A 0 χ K t − 1 + A 1 ξ t . At each outer iteration, let λ t + 1 ∈ [ 0 , λ max ] \lambda_{t+1} \in[0,\lambda_{\max}] λ t + 1 ∈ [ 0 , λ m a x ] satisfy
∣ λ t + 1 − Λ β , τ ( π t ) ∣ ≤ ζ t , ζ t ≥ 0. (15) |\lambda_{t+1} - \Lambda_{\beta,\tau}(\pi_t)| \le\zeta_t, \qquad\zeta_t \ge0. \tag*{(15)} ∣ λ t + 1 − Λ β , τ ( π t ) ∣ ≤ ζ t , ζ t ≥ 0. (15)
Theorem 4.1 (Convergence of tabular SDLA updates). Under the assumptions and updates above, suppose q = b L Λ < 1 q = bL_{\Lambda} < 1 q = b L Λ < 1 . Then the equilibrium satisfying π ˉ = B ( λ ˉ ) \bar{\pi} = B(\bar{\lambda}) π ˉ = B ( λ ˉ ) and λ ˉ = Λ β , τ ( π ˉ ) \bar{\lambda} = \Lambda_{\beta,\tau}(\bar{\pi}) λ ˉ = Λ β , τ ( π ˉ ) is unique. Write e t = ∥ π t − π ˉ ∥ F e_t = \lVert\pi_t - \bar{\pi}\rVert_F e t = ∥ π t − π ˉ ∥ F . If K t → ∞ K_t \to\infty K t → ∞ , ξ t → 0 \xi_t \to0 ξ t → 0 , and ζ t → 0 \zeta_t \to0 ζ t → 0 , then ( π t , λ t ) → ( π ˉ , λ ˉ ) (\pi_t,\lambda_t) \to(\bar{\pi},\bar{\lambda}) ( π t , λ t ) → ( π ˉ , λ ˉ ) from every full-support initial policy. If K t ≥ K K_t \ge K K t ≥ K , ξ t ≤ ξ ‾ \xi_t \le\overline{\xi} ξ t ≤ ξ , and ζ t ≤ ζ ‾ \zeta_t \le\overline{\zeta} ζ t ≤ ζ , then
lim sup t → ∞ e t ≤ κ E , ξ , ζ : = A 0 χ K − 1 + A 1 ξ ‾ + b ζ ‾ 1 − q , (16) \limsup_{t \to\infty} e_t \le\kappa_{E,\xi,\zeta} := \frac{A_0\chi^{K-1} + A_1\overline{\xi} + b\overline{\zeta}}{1-q}, \tag*{(16)} t → ∞ lim sup e t ≤ κ E , ξ , ζ := 1 − q A 0 χ K − 1 + A 1 ξ + b ζ , (16)
lim sup t → ∞ ∣ λ t − λ ˉ ∣ ≤ ζ ‾ + L Λ κ E , ξ , ζ . \limsup_{t \to\infty} |\lambda_t - \bar{\lambda}| \le\overline{\zeta} + L_{\Lambda}\kappa_{E,\xi,\zeta}. t → ∞ lim sup ∣ λ t − λ ˉ ∣ ≤ ζ + L Λ κ E , ξ , ζ .
If χ K t − 1 + ξ t + ζ t = O ( r t ) \chi^{K_t-1} + \xi_t + \zeta_t = O(r^t) χ K t − 1 + ξ t + ζ t = O ( r t ) for r ∈ ( 0 , 1 ) r \in(0,1) r ∈ ( 0 , 1 ) , then
∥ π t − π ˉ ∥ F + ∣ λ t − λ ˉ ∣ = O ( ν t ) , max { q , r } < ν < 1. (17) \lVert\pi_t - \bar{\pi}\rVert_F + |\lambda_t - \bar{\lambda}| = O(\nu^t), \qquad\max\{\sqrt{q},r\} < \nu< 1. \tag*{(17)} ∥ π t − π ˉ ∥ F + ∣ λ t − λ ˉ ∣ = O ( ν t ) , max { q , r } < ν < 1. (17)
The proof uses a two-step error recursion (Supplementary (62) ), yielding an outer-iteration contraction factor of q \sqrt{q} q . Appendix B.3 combines the actor bound of Cen et al. [26 ] with the actor and dual sensitivities from Appendix B.2.4. The condition q = b L Λ < 1 q=bL_{\Lambda}<1 q = b L Λ < 1 bounds the coupled response gains, following small-gain principles used in mean-field learning [27 , 28 ] , performative RL [29 ] , and actor–critic analysis [30 ] . Since L Λ = β ( K c + K m ) L_{\Lambda}=\beta(K_c+K_m) L Λ = β ( K c + K m ) , stronger quadratic regularization reduces this gain; Appendix B.2.4 gives a nonempty sufficient parameter range.
Feasibility and Reward Bounds
Proposition 4.2 (Fixed-parameter feasibility and reward bounds). In the tabular setting above, suppose J c ( π s ) ≤ d − σ J^c(\pi_s)\le d-\sigma J c ( π s ) ≤ d − σ for some σ > 0 \sigma>0 σ > 0 . Let U ≥ sup π J α ( π ) U\ge\sup_{\pi}J_{\alpha}(\pi) U ≥ sup π J α ( π ) , Δ = U − J α ( π s ) \Delta=U-J_{\alpha}(\pi_s) Δ = U − J α ( π s ) , and J α ⋆ ( d ) = max J c ( π ) ≤ d J α ( π ) J_{\alpha}^{\star}(d)=\max_{J^c(\pi)\le d}J_{\alpha}(\pi) J α ⋆ ( d ) = max J c ( π ) ≤ d J α ( π ) . Fix β , τ , L = λ max > 0 \beta,\tau,L=\lambda_{\max}>0 β , τ , L = λ m a x > 0 . Any exact equilibrium π ˉ = B ( λ ˉ ) \bar{\pi}=B(\bar{\lambda}) π ˉ = B ( λ ˉ ) , λ ˉ = Λ β , τ ( π ˉ ) \bar{\lambda}=\Lambda_{\beta,\tau}(\bar{\pi}) λ ˉ = Λ β , τ ( π ˉ ) satisfies
[ J c ( π ˉ ) − d ] + ≤ V β , L , (18) [J^c(\bar{\pi})-d]_+ \le V_{\beta,L}, \tag*{(18)} [ J c ( π ˉ ) − d ] + ≤ V β , L , (18) V β , L : = max { σ 2 + 4 Δ / β − σ 2 , [ Δ L − σ ] + } , V_{\beta,L}:=\max\left\{\frac{\sqrt{\sigma^2+4\Delta/\beta}-\sigma}{2},\left[\frac{\Delta}{L}-\sigma\right]_+\right\}, V β , L := max { 2 σ 2 + 4Δ/ β − σ , [ L Δ − σ ] + } , [ J α ⋆ ( d ) − J α ( π ˉ ) ] + ≤ β C ˉ 2 4 . (19) [J_{\alpha}^{\star}(d)-J_{\alpha}(\bar{\pi})]_+ \le\frac{\beta\bar{C}^2}{4}. \tag*{(19)} [ J α ⋆ ( d ) − J α ( π ˉ ) ] + ≤ 4 β C ˉ 2 . (19) If L ≥ Δ / σ L\ge\Delta/\sigma L ≥ Δ/ σ , then V β , L ≤ Δ / ( β σ ) V_{\beta,L}\le\Delta/(\beta\sigma) V β , L ≤ Δ/ ( β σ ) .
Actor optimality gives λ ˉ [ J c ( π ˉ ) − d + σ ] ≤ Δ \bar{\lambda}[J^c(\bar{\pi})-d+\sigma]\le\Delta λ ˉ [ J c ( π ˉ ) − d + σ ] ≤ Δ ; combining this with the surrogate endpoint conditions proves the bounds. Appendix B.3.4 gives the proof and, under Theorem 4.1, the iterative feasibility bound V β , L + K c E K , ξ , ζ V_{\beta,L}+K_c\mathcal{E}_{K,\xi,\zeta} V β , L + K c E K , ξ , ζ . The equilibrium bounds hold independently of the convergence condition q < 1 q<1 q < 1 .
Optimality
Corollary 4.3 (CMDP optimality under parameter matching). Under Theorem 4.1, suppose L α \mathcal{L}_{\alpha} L α has a saddle point ( π α ⋆ , λ α ⋆ ) (\pi_{\alpha}^{\star},\lambda_{\alpha}^{\star}) ( π α ⋆ , λ α ⋆ ) with J c ( π α ⋆ ) = d > 0 J^c(\pi_{\alpha}^{\star})=d>0 J c ( π α ⋆ ) = d > 0 and 0 < λ α ⋆ < λ max 0<\lambda_{\alpha}^{\star}<\lambda_{\max} 0 < λ α ⋆ < λ m a x . Choose β = β ⋆ ( τ ) \beta=\beta^{\star}(\tau) β = β ⋆ ( τ ) , where
β ⋆ ( τ ) = λ α ⋆ m π α ⋆ , τ ( λ α ⋆ ) > 0. (20) \beta^{\star}(\tau)=\frac{\lambda_{\alpha}^{\star}}{m_{\pi_{\alpha}^{\star},\tau}(\lambda_{\alpha}^{\star})}>0. \tag*{(20)} β ⋆ ( τ ) = m π α ⋆ , τ ( λ α ⋆ ) λ α ⋆ > 0. (20) Require q < 1 q<1 q < 1 at this parameter choice. Then ( π ˉ , λ ˉ ) = ( π α ⋆ , λ α ⋆ ) (\bar{\pi},\bar{\lambda})=(\pi_{\alpha}^{\star},\lambda_{\alpha}^{\star}) ( π ˉ , λ ˉ ) = ( π α ⋆ , λ α ⋆ ) and [ J c ( π t ) − d ] + ≤ K c ϵ t [J^c(\pi_t)-d]_+\le K_c\epsilon_t [ J c ( π t ) − d ] + ≤ K c ϵ t . As K t → ∞ K_t\to\infty K t → ∞ and ξ t , ζ t → 0 \xi_t,\zeta_t\to0 ξ t , ζ t → 0 , J α ( π t ) → J α ( π α ⋆ ) J_{\alpha}(\pi_t)\to J_{\alpha}(\pi_{\alpha}^{\star}) J α ( π t ) → J α ( π α ⋆ ) and constraint violations vanish. Uniform errors give lim sup t [ J c ( π t ) − d ] + ≤ K c E K , ξ , ζ \limsup_t[J^c(\pi_t)-d]_+\le K_c\mathcal{E}_{K,\xi,\zeta} lim sup t [ J c ( π t ) − d ] + ≤ K c E K , ξ , ζ .
Corollary 4.3 establishes exact optimality through parameter matching. Parameter conditions expressed through optimal multipliers also occur in constrained optimization, including exact penalty theory [31, Exercise 5.16] [32 ] . Here β ⋆ ( τ ) \beta^{\star}(\tau) β ⋆ ( τ ) provides the theoretical characterization, and ablations evaluate practical parameter choices.
Practical Implementation
Empirical Surrogate Dual
Following standard sample-based practice in safe RL [17 ] , we collect M M M trajectories under π c u r \pi_{\mathrm{cur}} π cur and compute discounted returns { ( R i , C i ) } i = 1 M \{(R_i,C_i)\}_{i=1}^{M} {( R i , C i ) } i = 1 M . Replacing population expectations with sample averages gives
F ^ M ( λ ) = τ log [ 1 M ∑ i = 1 M e ( R i − λ C i ) / τ ] , \widehat{F}_M(\lambda)=\tau\log\left[\frac{1}{M}\sum_{i=1}^{M}e^{(R_i-\lambda C_i)/\tau}\right], F M ( λ ) = τ log [ M 1 i = 1 ∑ M e ( R i − λ C i ) / τ ] ,
c ^ M = 1 M ∑ i = 1 M C i , (21) \widehat{c}_M=\frac{1}{M}\sum_{i=1}^{M}C_i, \tag*{(21)} c M = M 1 i = 1 ∑ M C i , (21)
and the empirical surrogate
g ^ M ( λ ) = F ^ M ( λ ) + λ ( d − c ^ M ) + λ 2 2 β . (22) \widehat{g}_M(\lambda)=\widehat{F}_M(\lambda)+\lambda(d-\widehat{c}_M)+\frac{\lambda^2}{2\beta}. \tag*{(22)} g M ( λ ) = F M ( λ ) + λ ( d − c M ) + 2 β λ 2 . (22)
Its trajectory-weighted cost is
m ^ ( λ ) = − F ^ M ′ ( λ ) = ∑ i C i e ( R i − λ C i ) / τ ∑ i e ( R i − λ C i ) / τ . (23) \widehat{m}(\lambda)=-\widehat{F}'_M(\lambda)=\frac{\sum_i C_i e^{(R_i-\lambda C_i)/\tau}}{\sum_i e^{(R_i-\lambda C_i)/\tau}}. \tag*{(23)} m ( λ ) = − F M ′ ( λ ) = ∑ i e ( R i − λ C i ) / τ ∑ i C i e ( R i − λ C i ) / τ . (23)
The batch stays fixed during the solve. The empirical surrogate is 1 / β 1/\beta 1/ β -strongly convex, with a unique minimizer λ ^ ∗ \widehat{\lambda}^{\ast} λ ∗ on [ 0 , λ max ] [0,\lambda_{\max}] [ 0 , λ m a x ] . Its activation condition is λ ^ ∗ > 0 \widehat{\lambda}^{\ast}>0 λ ∗ > 0 exactly when c ^ M + m ^ ( 0 ) > d \widehat{c}_M+\widehat{m}(0)>d c M + m ( 0 ) > d .
Scalar Solver and PPO/SAC Integration
Ternary search computes λ ^ ∗ \widehat{\lambda}^{\ast} λ ∗ to accuracy ε λ \varepsilon_{\lambda} ε λ without a dual learning rate, using O ( M log ( λ max / ε λ ) ) O(M\log(\lambda_{\max}/\varepsilon_{\lambda})) O ( M log ( λ m a x / ε λ )) arithmetic operations. We use 15 iterations and stabilized log-sum-exp evaluations; Appendix C.1 gives the interval bound. Trajectory-estimation and scalar-solver errors contribute to ζ t \zeta_t ζ t in (15) (Supplementary Eq. (52) ).
SDLA combines a scalar dual solve with SAC [24 ] or PPO [33 ] . Reward and cost critics estimate Q ϕ r r Q_{\phi_r}^{r} Q ϕ r r and Q ϕ c c Q_{\phi_c}^{c} Q ϕ c c ; the actor uses Q r − λ Q c Q^r-\lambda Q^c Q r − λ Q c . Each dual solve holds the trajectory batch fixed.
Related safe RL methods also combine structural analyses with neural implementations [4 , 34 , 35 ] ; Appendix C compares their theoretical settings.
PPO-SDLA combines rollout advantages as A ^ r − λ A ^ c \widehat{A}^{r}-\lambda\widehat{A}^{c} A r − λ A c and uses the same batch for the dual solve. SAC-SDLA updates actors and critics from replay transitions; recent rollout or evaluation episodes supply trajectory returns and mean cost for the surrogate. Both hold λ \lambda λ fixed during actor updates and use the subsequent dual solution in the next iteration.
Supplementary Algorithms S1–S3 give the general framework and its PPO/SAC implementations.
Experiments
We evaluate neural PPO-SDLA and SAC-SDLA on reward–cost performance, training-time constraint tracking, computational overhead, and component and parameter ablations.
Experimental Setup
HASARD. HASARD [36 ] uses egocentric RGB observations. Following its protocol, the cost threshold is 5 for Remedy Rush, Collateral Damage, and Detonator’s Dilemma, and 50 for all other environments.
OmniSafe’s MuJoCo Velocity Benchmark. We evaluate Ant, HalfCheetah, Hopper, Walker2d, and Swimmer with a cost limit of 25, following OmniSafe [37 ] . These velocity-constrained continuous-control tasks complement HASARD’s visual observations.
Baselines. We use baselines available in each benchmark’s official implementation. For HASARD, following [36 ] , we compare against: PPOlag [3 ] , PPOPID [6 ] , PPOCost [36 ] , P3O [16 ] , and PPOSaute [21 ] . For OmniSafe, we compare against: PPOlag, SAC lag [3 ] , P3O [16 ] , FOCOPS [19 ] , PPOsaute [21 ] , and PPOEarlyTermin [37 ] .
Implementation Details. We implement SDLA on top of PPO and SAC. The default surrogate-dual parameters are
τ = 1 \tau= 1 τ = 1 and β = 0.1 \beta= 0.1 β = 0.1 for both HASARD and OmniSafe Safety-Gymnasium. Ternary search runs for K = 15 K = 15 K = 15 iterations per dual update. Our experiments use 5 random seeds and λ max = 10 \lambda_{\max} = 10 λ m a x = 10 ; HASARD baselines use archived runs (Appendix D).
Evaluation Metrics. We report episode reward and cost, comparing mean cost against the task budget. HASARD tables report means and standard deviations across per-run summaries of terminal training performance.
Human Comparison. On HASARD, PPO-SDLA achieves higher reported mean reward than the human baseline in 6 of 18 task–difficulty settings, including four with lower mean cost (Table 3 ). All six settings meet their respective mean-cost budgets. Human results from Tomlin et al. [36 ] are averaged over 10 episodes, while PPO-SDLA results use terminal training summaries.
Table 3. Human player rewards and costs averaged over 10 episodes compared to PPO-SDLA terminal training summaries. Bold: PPO-SDLA achieves higher reported mean reward than human.
Figure 1 and Figure 2 compare reward and cost trajectories on four HASARD tasks at Levels 1 and 2. Learning curves for all 18 settings appear in Appendix D.
Figure 1. HASARD Level 1: reward (top) and cost (bottom). Lines show means and shading one standard deviation over five SDLA runs and three runs per baseline. Dashed lines mark budgets of 50 for Armament Burden and 5 for the other tasks. PPOCost shows task reward with its logged penalty added back.
Figure 2. HASARD Level 2: reward (top) and cost (bottom) for the same four tasks, with methods, budgets, and statistical conventions as in Figure 1 .
Results for HASARD
Baseline Comparison. PPO-SDLA is the only compared method whose reported mean cost meets the budget in all 18 HASARD settings, and it has the highest mean reward among budget-meeting methods in each setting (Table 2 ). For example, Armament Burden L1 reward increases from PPOPID’s 8.99 to 19.46, while mean cost is 12.80 against a budget of 50. Table S5 reports standard deviations.
Table 2. Rewards and costs over five SDLA runs and available archived baseline runs. The cost threshold is 5 for Remedy Rush, Collateral Damage, and Detonator’s Dilemma, and 50 for all other environments. Green: mean cost meets the budget. Bold Green: highest mean reward among methods meeting the mean cost budget.
Table S5. Rewards and costs over five SDLA runs and available archived baseline runs. The cost threshold is 5 for Remedy Rush, Collateral Damage, and Detonator’s Dilemma, and 50 for all other environments. Green: mean cost meets the budget. Bold Green: highest mean reward among methods meeting the mean cost budget.
Performance on MuJoCo Velocity Benchmark
PPO-based methods. Among the compared PPO-based methods meeting the mean-cost budget, PPO-SDLA achieves the highest mean reward on four of five tasks (Table 4 ). On Ant, its reward is close to PPOLag’s (3200.44 versus 3205.96), with lower mean cost (19.73 versus 22.46). Figure S2 and Figure S4 report the learning curves.
Table 4. Performance on OmniSafe’s MuJoCo Velocity Benchmark. Mean ± \pm ± std over 5 random seeds. Green: mean cost ≤ 25 \le25 ≤ 25 . Bold Green: highest mean reward within the same algorithm family (PPO-based or SAC-based) among methods meeting this budget.
Figure S2. PPO-SDLA on Safety-Gym velocity tasks. Rows show episode reward, episode cost, and the dual variable λ \lambda λ , respectively.
Figure S4. SAC-SDLA on Safety-Gym velocity tasks. Rows show episode reward, episode cost, and the dual variable λ \lambda λ , respectively.
SAC-based methods. SAC-SDLA improves mean reward over SACLag on all five tasks with mean costs below budget; the Ant reward gain is 23.9%. On HalfCheetah, SACLag exceeds the cost budget (43.65), while SAC-SDLA stays below it (15.06). PPO-SDLA adds approximately 1.5% GPU time over PPOLag on Ant (Appendix D.4.2).
Ablations
Adaptive feedback versus fixed early penalization. We compare SDLA with PPO-QR-d / 2 d/2 d /2 to evaluate adaptive centering against the fixed center d / 2 d/2 d /2 . For the fixed trajectory batch in (21), the ablation objectives are
g ^ E ( λ ) = F ^ M ( λ ) + λ d , (24) \widehat{g}_{\mathrm{E}}(\lambda) = \widehat{F}_{M}(\lambda) + \lambda d, \tag*{(24)} g E ( λ ) = F M ( λ ) + λ d , (24)
g ^ Q R ( λ ) = F ^ M ( λ ) + λ d + λ 2 2 β , (25) \widehat{g}_{\mathrm{QR}}(\lambda) = \widehat{F}_{M}(\lambda) + \lambda d + \frac{\lambda^2}{2\beta}, \tag*{(25)} g QR ( λ ) = F M ( λ ) + λ d + 2 β λ 2 , (25)
g ^ Q R − d / 2 ( λ ) = F ^ M ( λ ) + λ d 2 + λ 2 2 β . (26) \widehat{g}_{\mathrm{QR-d/2}}(\lambda) = \widehat{F}_{M}(\lambda) + \frac{\lambda d}{2} + \frac{\lambda^2}{2\beta}. \tag*{(26)} g QR − d/2 ( λ ) = F M ( λ ) + 2 λ d + 2 β λ 2 . (26)
PPOEntropy, PPO-QR, and PPO-QR-d / 2 d/2 d /2 minimize these respective objectives over [ 0 , λ max ] [0,\lambda_{\max}] [ 0 , λ m a x ] , using ternary search. All retain trajectory weighting; PPOEntropy omits quadratic regularization, while PPO-QR and PPO-QR-d / 2 d/2 d /2 use fixed centers d d d and $d/2. SDLA uses d − c ^ M d - \widehat{c}_{M} d − c M in (22). Here “Entropy” refers to trajectory log-sum-exp smoothing. The PPO backbone and budget d = 25 d = 25 d = 25 are shared. PPO-QR-d / 2 d/2 d /2 uses β = 0.2 \beta= 0.2 β = 0.2 versus SDLA’s 0.1, matching their constant-cost activation threshold and slope (Appendix D.§ 1 ).
Table 6 compares reward, cost, and violation rates across the surrogate variants. On Ant, relative to the fixed-margin PPO-QR-d / 2 d/2 d /2 baseline, SDLA reduces the violation rate from 24.8% to 6.7% and mean cost from 25.47 to 19.73, with reported mean reward of 3200.4 versus 3169.3. On Swimmer, the corresponding violation rate decreases from 74.1% to 27.1%, with mean cost of 20.39 versus 23.67 and reported mean reward of 115.8 versus 92.6. On Ant, mean ∣ Δ λ ∣ |\Delta\lambda| ∣Δ λ ∣ is similar for SDLA and PPO-QR-d / 2 d/2 d /2 (0.0865 versus 0.0849), while its 95th percentile falls from 0.4219 to 0.3576 (Appendix D.§ 1 ).
Across β ∈ { 0.1 , 0.5 , 1 , 2 , 5 , ∞ } \beta\in\{0.1, 0.5, 1, 2, 5, \infty\} β ∈ { 0.1 , 0.5 , 1 , 2 , 5 , ∞ } , all final mean costs remain below 25, with rewards between 3086.35 and 3200.44 (Table S2 ). Mean ∣ Δ λ ∣ |\Delta\lambda| ∣Δ λ ∣ increases monotonically from 0.0865 to 0.8037 as β \beta β increases.
Table S2. Regularization ablation on SafetyAntVelocity-v1 with d = 25 d = 25 d = 25 . The β \beta β sweep uses a 10M-step horizon and τ = 1 \tau= 1 τ = 1 ; β = ∞ \beta= \infty β = ∞ removes quadratic regularization. Mean ∣ Δ λ ∣ |\Delta\lambda| ∣Δ λ ∣ measures the average change between consecutive logged multipliers.
Appendix D.§ 2 compares τ ∈ { 1 , 1.5 , 2 } \tau\in\{1, 1.5, 2\} τ ∈ { 1 , 1.5 , 2 } at the default β = 0.1 \beta= 0.1 β = 0.1 .
Constraint Tracking during Training
Table 5 compares full-training constraint tracking on Ant and Walker2d, with PPOLag rerun for multiplier logging. PPO-SDLA reduces violation rates from 38.7% to 6.7% on Ant and from 41.7% to 13.0% on Walker2d. Average overshoot decreases by 94.4% and 71.3%, respectively, and boundary crossings are less frequent on both tasks. PPO-SDLA has larger mean multiplier updates alongside fewer and smaller violations. Appendix D.§ 4 gives metric definitions, plots, and multiplier-cap usage.
Conclusion
SDLA replaces fixed-policy bang-bang switching with structured smooth feedback of bounded sensitivity. Tabular analysis establishes convergence under mild assumptions; PPO/SAC experiments demonstrate competitive rewards and improved constraint tracking.
References
Appendix A: Notations Table
Table S1. Notation Table
Appendix B: Proofs
Properties of the Surrogate Dual
Proof of Lemma 3.2
Proof. Bounded returns and τ > 0 \tau> 0 τ > 0 justify differentiation under the expectation in (7). Using F π ′ = − m π F_{\pi}^{\prime}=-m_{\pi} F π ′ = − m π and m π ′ = − Var q π , λ ( C ) / τ m_{\pi}^{\prime}=-\operatorname{Var}_{q_{\pi,\lambda}}(C)/\tau m π ′ = − Var q π , λ ( C ) / τ gives (8)–(9). For C ∈ [ 0 , C ˉ ] C \in[0,\bar{C}] C ∈ [ 0 , C ˉ ] , the variance lies in [ 0 , C ˉ 2 / 4 ] [0,\bar{C}^{2}/4] [ 0 , C ˉ 2 /4 ] , giving the strong-convexity and smoothness constants. Strong convexity and compactness give a unique response. The constrained first-order conditions give Λ ( π ) = 0 \Lambda(\pi)=0 Λ ( π ) = 0 exactly when g π ′ ( 0 ) ≥ 0 g_{\pi}^{\prime}(0) \ge0 g π ′ ( 0 ) ≥ 0 , and Λ ( π ) = λ max \Lambda(\pi)=\lambda_{\max} Λ ( π ) = λ m a x exactly when g π ′ ( λ max ) ≤ 0 g_{\pi}^{\prime}(\lambda_{\max}) \le0 g π ′ ( λ m a x ) ≤ 0 . Otherwise, g π ′ ( Λ ( π ) ) = 0 g_{\pi}^{\prime}(\Lambda(\pi))=0 g π ′ ( Λ ( π )) = 0 gives the interior cost-signal identity. These conditions establish (10) and the three response regimes. Strong convexity implies g π ′ ( λ ) ≥ d − c π − m π ( 0 ) + λ / β g_{\pi}^{\prime}(\lambda) \ge d-c_{\pi}-m_{\pi}(0)+\lambda/\beta g π ′ ( λ ) ≥ d − c π − m π ( 0 ) + λ / β . If c π + m π ( 0 ) ≤ d c_{\pi}+m_{\pi}(0) \le d c π + m π ( 0 ) ≤ d , the response is zero. Otherwise, the interior equation or the upper endpoint inequality gives Λ ( π ) ≤ β ( c π + m π ( 0 ) − d ) \Lambda(\pi) \le\beta(c_{\pi}+m_{\pi}(0)-d) Λ ( π ) ≤ β ( c π + m π ( 0 ) − d ) .
Trajectory Weighting and the Cost Signal
At λ = 0 \lambda=0 λ = 0 , the population trajectory-weighted cost and mean cost satisfy
m π ( 0 ) − c π = Cov π ( C , e R / τ ) E π [ e R / τ ] . (27) m_{\pi}(0)-c_{\pi}=\frac{\operatorname{Cov}_{\pi}(C,e^{R/\tau})}{\mathbb{E}_{\pi}[e^{R/\tau}]}. \tag*{(27)} m π ( 0 ) − c π = E π [ e R / τ ] Cov π ( C , e R / τ ) . (27)
Expanding the covariance gives the identity. Its sign determines whether trajectory weighting raises or lowers the cost signal relative to the policy mean.
Multiplier Feedback and Feasible Policy Updates
We use the population definitions of § 3.1 , the structural properties of § 3.2 , and the notation of § 3.3 . The local actor assumptions and delayed updates are specified in Appendix B.§ 2.2 . The convergence and optimality proofs use the entropy-regularized actor best responses of § 4.1 and delayed dual update (15) . For a policy π θ \pi_\theta π θ , write g θ g_\theta g θ and m θ m_\theta m θ for g π θ g_{\pi_\theta} g π θ and m π θ m_{\pi_\theta} m π θ in (5) and (7). Let q θ , λ q_{\theta,\lambda} q θ , λ be the reweighted trajectory law with density proportional to e ( R − λ C ) / τ e^{(R-\lambda C)/\tau} e ( R − λ C ) / τ relative to the original trajectory law. Bounded returns justify differentiation and give
g θ ′ ( λ ) = d − c ( θ ) − m θ ( λ ) + λ / β , m θ ′ ( λ ) = − Var q θ , λ ( C ) τ . (28) g'_\theta(\lambda)=d-c(\theta)-m_\theta(\lambda)+\lambda/\beta,\qquad m'_\theta(\lambda)=-\frac{\operatorname{Var}_{q_{\theta,\lambda}}(C)}{\tau}. \tag*{(28)} g θ ′ ( λ ) = d − c ( θ ) − m θ ( λ ) + λ / β , m θ ′ ( λ ) = − τ Var q θ , λ ( C ) . (28)
Hence g θ ′ ′ ( λ ) = β − 1 + Var q θ , λ ( C ) / τ ≥ β − 1 g''_\theta(\lambda)=\beta^{-1}+\operatorname{Var}_{q_{\theta,\lambda}}(C)/\tau\ge\beta^{-1} g θ ′′ ( λ ) = β − 1 + Var q θ , λ ( C ) / τ ≥ β − 1 on the common interval [ 0 , λ max ] [0,\lambda_{\max}] [ 0 , λ m a x ] . We use g t = g θ t g_t=g_{\theta_t} g t = g θ t and m t = m θ t m_t=m_{\theta_t} m t = m θ t .
Proof of Theorem 3.3
Proof. The constrained optimality conditions give
g t ′ ( ℓ t ) ( ℓ t + 1 − ℓ t ) ≥ 0 , g t + 1 ′ ( ℓ t + 1 ) ( ℓ t − ℓ t + 1 ) ≥ 0. g'_t(\ell_t)(\ell_{t+1}-\ell_t)\ge0,\qquad g'_{t+1}(\ell_{t+1})(\ell_t-\ell_{t+1})\ge0. g t ′ ( ℓ t ) ( ℓ t + 1 − ℓ t ) ≥ 0 , g t + 1 ′ ( ℓ t + 1 ) ( ℓ t − ℓ t + 1 ) ≥ 0.
Since g t + 1 ′ ( ℓ t ) − g t ′ ( ℓ t ) = − D t g'_{t+1}(\ell_t)-g'_t(\ell_t)=-D_t g t + 1 ′ ( ℓ t ) − g t ′ ( ℓ t ) = − D t , combining these inequalities yields
δ t [ g t + 1 ′ ( ℓ t + 1 ) − g t + 1 ′ ( ℓ t ) ] ≤ δ t D t . \delta_t\left[g'_{t+1}(\ell_{t+1})-g'_{t+1}(\ell_t)\right]\le\delta_tD_t. δ t [ g t + 1 ′ ( ℓ t + 1 ) − g t + 1 ′ ( ℓ t ) ] ≤ δ t D t .
Strong monotonicity of g t + 1 ′ g'_{t+1} g t + 1 ′ bounds the left-hand side below by δ t 2 / β \delta_t^2/\beta δ t 2 / β . This proves (12), including the absolute-value bound when δ t ≠ 0 \delta_t\ne0 δ t = 0 ; it also holds when δ t = 0 \delta_t=0 δ t = 0 . A nonzero response change must have the same sign as D t D_t D t . If ℓ t \ell_t ℓ t is interior and D t ≠ 0 D_t\ne0 D t = 0 , then g t ′ ( ℓ t ) = 0 g'_t(\ell_t)=0 g t ′ ( ℓ t ) = 0 and g t + 1 ′ ( ℓ t ) = − D t ≠ 0 g'_{t+1}(\ell_t)=-D_t\ne0 g t + 1 ′ ( ℓ t ) = − D t = 0 . The unique new minimizer therefore moves strictly in the indicated direction.
If both responses are interior, g t ′ ( ℓ t ) = g t + 1 ′ ( ℓ t + 1 ) = 0 g'_t(\ell_t)=g'_{t+1}(\ell_{t+1})=0 g t ′ ( ℓ t ) = g t + 1 ′ ( ℓ t + 1 ) = 0 . With
V ‾ t + 1 : = 1 τ ∫ 0 1 Var q θ t + 1 , ℓ t + z δ t ( C ) d z ≥ 0 , (29) \overline{V}_{t+1}:=\frac{1}{\tau}\int_0^1\operatorname{Var}_{q_{\theta_{t+1},\ell_t+z\delta_t}}(C)\,dz\ge0, \tag*{(29)} V t + 1 := τ 1 ∫ 0 1 Var q θ t + 1 , ℓ t + z δ t ( C ) d z ≥ 0 , (29)
the fundamental theorem of calculus gives
D t = g t + 1 ′ ( ℓ t + 1 ) − g t + 1 ′ ( ℓ t ) = ( β − 1 + V ‾ t + 1 ) δ t . D_t=g'_{t+1}(\ell_{t+1})-g'_{t+1}(\ell_t)=(\beta^{-1}+\overline{V}_{t+1})\delta_t. D t = g t + 1 ′ ( ℓ t + 1 ) − g t + 1 ′ ( ℓ t ) = ( β − 1 + V t + 1 ) δ t .
This proves (13).
Feasible actor regimes under delayed dual feedback
Actor regularity and updates. For the actor analysis, assume r , c r,c r , c have locally Lipschitz gradients near the iterate under consideration and v t : = ∇ c ( θ t ) ≠ 0 v_t:=\nabla c(\theta_t)\ne0 v t := ∇ c ( θ t ) = 0 . Write u t = ∇ r ( θ t ) u_t=\nabla r(\theta_t) u t = ∇ r ( θ t ) and κ t = u t T v t / ∥ v t ∥ 2 \kappa_t=u_t^\mathsf{T}v_t/\lVert v_t\rVert^2 κ t = u t T v t / ∥ v t ∥ 2 . Local smoothness controls the second-order error of a finite actor step, while κ t \kappa_t κ t is the penalty at which its first-order cost change vanishes. Following the ordering in Algorithm S1, initialize λ 0 ∈ [ 0 , λ max ] \lambda_0\in[0,\lambda_{\max}] λ 0 ∈ [ 0 , λ m a x ] and consider
θ t + 1 = θ t + η t p t , p t = u t − λ t v t , λ t + 1 = ℓ t . (30) \theta_{t+1}=\theta_t+\eta_tp_t,\qquad p_t=u_t-\lambda_tv_t,\qquad\lambda_{t+1}=\ell_t. \tag*{(30)} θ t + 1 = θ t + η t p t , p t = u t − λ t v t , λ t + 1 = ℓ t . (30)
The actor uses the previous dual response, and the new multiplier is computed from the policy that collected the batch. The feedback law relates population dual responses; actor regularity connects these responses to finite policy steps.
For t ≥ 1 t\ge1 t ≥ 1 , the delayed update gives λ t = ℓ t − 1 \lambda_t=\ell_{t-1} λ t = ℓ t − 1 . Applying Theorem 3.3 to consecutive policies yields
∣ λ t − ℓ t ∣ ≤ ε t l a g , ε t l a g : = β ∣ c t − c t − 1 + m t ( λ t ) − m t − 1 ( λ t ) ∣ . (31) |\lambda_t-\ell_t|\le\varepsilon_t^{\mathrm{lag}},\qquad\varepsilon_t^{\mathrm{lag}}:=\beta\left|c_t-c_{t-1}+m_t(\lambda_t)-m_{t-1}(\lambda_t)\right|. \tag*{(31)} ∣ λ t − ℓ t ∣ ≤ ε t lag , ε t lag := β ∣ c t − c t − 1 + m t ( λ t ) − m t − 1 ( λ t ) ∣ . (31)
The bound measures the difference between the multiplier used by the actor and the current dual response. The following result compares that response with κ t \kappa_t κ t , allowing for this difference, to determine the direction of the actor’s cost change. A positive safety margin also leaves room for cost to increase during a reward-improving step.
Theorem B.1 (Feasible actor regimes under delayed dual feedback). Under the assumptions and actor updates above, let ε t l a g ≥ 0 \varepsilon_t^{\mathrm{lag}}\ge0 ε t lag ≥ 0 satisfy ∣ λ t − ℓ t ∣ ≤ ε t l a g |\lambda_t-\ell_t|\le\varepsilon_t^{\mathrm{lag}} ∣ λ t − ℓ t ∣ ≤ ε t lag .
(i) Feasible reward recovery. If c t < d c_t<d c t < d and ℓ t + ε t l a g < κ t \ell_t+\varepsilon_t^{\mathrm{lag}}<\kappa_t ℓ t + ε t lag < κ t , then λ t < κ t \lambda_t<\kappa_t λ t < κ t . For all sufficiently small positive η t \eta_t η t , the actor step in (S4) satisfies
r ( θ t + 1 ) > r ( θ t ) , c t < c ( θ t + 1 ) < d . (32) r(\theta_{t+1})>r(\theta_t),\qquad c_t<c(\theta_{t+1})<d. \tag*{(32)} r ( θ t + 1 ) > r ( θ t ) , c t < c ( θ t + 1 ) < d . (32) (ii) Feasible-region constraint suppression. If c t ≤ d c_t\le d c t ≤ d and ℓ t − ε t l a g > κ t \ell_t-\varepsilon_t^{\mathrm{lag}}>\kappa_t ℓ t − ε t lag > κ t , then λ t > κ t \lambda_t>\kappa_t λ t > κ t . For all sufficiently small positive η t \eta_t η t , the same actor step satisfies
c ( θ t + 1 ) < c t ≤ d . (33) c(\theta_{t+1})<c_t\le d. \tag*{(33)} c ( θ t + 1 ) < c t ≤ d . (33)
In part (i), the actor increases reward and cost within the available safety margin. In part (ii), the cost-decreasing update expands the margin. The multiplier comparisons apply throughout the clipped interval. Recomputing the multiplier before the actor step gives ε t l a g = 0 \varepsilon_t^{\mathrm{lag}}=0 ε t lag = 0 .
Safety-margin criteria. The surrogate derivative converts these multiplier comparisons into conditions on the available margin. When the comparison point κ t − : = κ t − ε t lag \kappa_t^- := \kappa_t - \varepsilon_t^{\operatorname{lag}} κ t − := κ t − ε t lag lies in ( 0 , λ max ) (0,\lambda_{\max}) ( 0 , λ m a x ) , the condition
d − c t > m t ( κ t − ) − κ t − / β (34) d-c_t > m_t(\kappa_t^-) - \kappa_t^-/\beta \tag*{(34)} d − c t > m t ( κ t − ) − κ t − / β (34)
gives g t ′ ( κ t − ) > 0 g_t'(\kappa_t^-) > 0 g t ′ ( κ t − ) > 0 , hence ℓ t < κ t − \ell_t < \kappa_t^- ℓ t < κ t − and the recovery comparison in part (i). When κ t + : = κ t + ε t lag \kappa_t^+ := \kappa_t + \varepsilon_t^{\operatorname{lag}} κ t + := κ t + ε t lag lies in ( 0 , λ max ) (0,\lambda_{\max}) ( 0 , λ m a x ) , the condition
d − c t < m t ( κ t + ) − κ t + / β (35) d-c_t < m_t(\kappa_t^+) - \kappa_t^+/\beta \tag*{(35)} d − c t < m t ( κ t + ) − κ t + / β (35)
gives g t ′ ( κ t + ) < 0 g_t'(\kappa_t^+) < 0 g t ′ ( κ t + ) < 0 , hence ℓ t > κ t + \ell_t > \kappa_t^+ ℓ t > κ t + and the suppression comparison in part (ii). These thresholds relate the available margin to trajectory feedback and actor gradients. From a strictly feasible policy, condition (S8) supports reward recovery within the budget. From a feasible policy, condition (S9) gives a cost-decreasing direction that expands the margin. Both conclusions use the actor assumptions and sufficiently small steps of Theorem B.1.
Proof of Theorem B.1
Proof. For the updates in (S4), apply (12) to θ t − 1 , θ t \theta_{t-1},\theta_t θ t − 1 , θ t . Since ℓ t − 1 = λ t \ell_{t-1}=\lambda_t ℓ t − 1 = λ t , it gives
∣ λ t − ℓ t ∣ ≤ β ∣ c t − c t − 1 + m t ( λ t ) − m t − 1 ( λ t ) ∣ = ε t lag . (36) |\lambda_t-\ell_t| \le\beta\left|c_t-c_{t-1}+m_t(\lambda_t)-m_{t-1}(\lambda_t)\right|=\varepsilon_t^{\operatorname{lag}}. \tag*{(36)} ∣ λ t − ℓ t ∣ ≤ β ∣ c t − c t − 1 + m t ( λ t ) − m t − 1 ( λ t ) ∣ = ε t lag . (36)
(i) Recovery. From ℓ t + ε t lag < κ t \ell_t+\varepsilon_t^{\operatorname{lag}}<\kappa_t ℓ t + ε t lag < κ t and the multiplier-error bound,
0 ≤ λ t ≤ ℓ t + ε t lag < κ t . (37) 0\le\lambda_t\le\ell_t+\varepsilon_t^{\operatorname{lag}}<\kappa_t. \tag*{(37)} 0 ≤ λ t ≤ ℓ t + ε t lag < κ t . (37)
Since ( u t − κ t v t ) T v t = 0 (u_t-\kappa_tv_t)^{\mathsf{T}}v_t=0 ( u t − κ t v t ) T v t = 0 , the direction p t = u t − λ t v t p_t=u_t-\lambda_tv_t p t = u t − λ t v t satisfies
v t T p t = ( κ t − λ t ) ∥ v t ∥ 2 > 0 , (38) v_t^{\mathsf{T}}p_t=(\kappa_t-\lambda_t)\lVert v_t\rVert^2>0, \tag*{(38)} v t T p t = ( κ t − λ t ) ∥ v t ∥ 2 > 0 , (38)
u t T p t = ∥ u t − κ t v t ∥ 2 + κ t ( κ t − λ t ) ∥ v t ∥ 2 > 0. (39) u_t^{\mathsf{T}}p_t=\lVert u_t-\kappa_tv_t\rVert^2+\kappa_t(\kappa_t-\lambda_t)\lVert v_t\rVert^2>0. \tag*{(39)} u t T p t = ∥ u t − κ t v t ∥ 2 + κ t ( κ t − λ t ) ∥ v t ∥ 2 > 0. (39)
Here κ t > 0 \kappa_t>0 κ t > 0 follows from 0 ≤ λ t < κ t 0\le\lambda_t<\kappa_t 0 ≤ λ t < κ t .
Let L ∇ r , L ∇ c L_{\nabla r},L_{\nabla c} L ∇ r , L ∇ c be local gradient Lipschitz constants and take η t \eta_t η t small enough to keep the step within their neighborhood. Smoothness gives
r ( θ t + η t p t ) − r ( θ t ) ≥ η t u t T p t − L ∇ r η t 2 2 ∥ p t ∥ 2 , r(\theta_t+\eta_tp_t)-r(\theta_t)\ge\eta_tu_t^{\mathsf{T}}p_t-\frac{L_{\nabla r}\eta_t^2}{2}\lVert p_t\rVert^2, r ( θ t + η t p t ) − r ( θ t ) ≥ η t u t T p t − 2 L ∇ r η t 2 ∥ p t ∥ 2 ,
∣ c ( θ t + η t p t ) − c t − η t v t T p t ∣ ≤ L ∇ c η t 2 2 ∥ p t ∥ 2 . \left|c(\theta_t+\eta_tp_t)-c_t-\eta_tv_t^{\mathsf{T}}p_t\right|\le\frac{L_{\nabla c}\eta_t^2}{2}\lVert p_t\rVert^2. c ( θ t + η t p t ) − c t − η t v t T p t ≤ 2 L ∇ c η t 2 ∥ p t ∥ 2 .
Both directional derivatives are positive, so all sufficiently small positive steps satisfy
η t v t T p t + 1 2 L ∇ c η t 2 ∥ p t ∥ 2 < d − c t , 1 2 L ∇ c η t ∥ p t ∥ 2 < v t T p t , 1 2 L ∇ r η t ∥ p t ∥ 2 < u t T p t . \eta_tv_t^{\mathsf{T}}p_t+\frac{1}{2}L_{\nabla c}\eta_t^2\lVert p_t\rVert^2<d-c_t,\qquad
\frac{1}{2}L_{\nabla c}\eta_t\lVert p_t\rVert^2<v_t^{\mathsf{T}}p_t,\qquad
\frac{1}{2}L_{\nabla r}\eta_t\lVert p_t\rVert^2<u_t^{\mathsf{T}}p_t. η t v t T p t + 2 1 L ∇ c η t 2 ∥ p t ∥ 2 < d − c t , 2 1 L ∇ c η t ∥ p t ∥ 2 < v t T p t , 2 1 L ∇ r η t ∥ p t ∥ 2 < u t T p t .
The first inequality keeps the cost increase within the available margin; the other two give strict cost and reward increases. This proves (S6).
(ii) Feasible-region constraint suppression. The other regime condition gives
λ t ≥ ℓ t − ε t lag > κ t . \lambda_t\ge\ell_t-\varepsilon_t^{\operatorname{lag}}>\kappa_t. λ t ≥ ℓ t − ε t lag > κ t .
Thus the actor direction locally reduces cost:
v t T p t = ( κ t − λ t ) ∥ v t ∥ 2 < 0. v_t^{\mathsf{T}}p_t=(\kappa_t-\lambda_t)\lVert v_t\rVert^2<0. v t T p t = ( κ t − λ t ) ∥ v t ∥ 2 < 0.
For a local gradient Lipschitz constant L ∇ c L_{\nabla c} L ∇ c , smoothness along the step gives
c ( θ t + η t p t ) − c t ≤ η t v t T p t + L ∇ c η t 2 2 ∥ p t ∥ 2 . c(\theta_t+\eta_tp_t)-c_t\le\eta_tv_t^{\mathsf{T}}p_t+\frac{L_{\nabla c}\eta_t^2}{2}\lVert p_t\rVert^2. c ( θ t + η t p t ) − c t ≤ η t v t T p t + 2 L ∇ c η t 2 ∥ p t ∥ 2 .
For all sufficiently small positive η t \eta_t η t , this bound gives c ( θ t + 1 ) < c t ≤ d c(\theta_{t+1})<c_t\le d c ( θ t + 1 ) < c t ≤ d , proving (S7).
Finally, the safety-margin criteria follow from the same surrogate derivative. If κ t − ∈ ( 0 , λ max ) \kappa_t^-\in(0,\lambda_{\max}) κ t − ∈ ( 0 , λ m a x ) , condition (S8) gives
g t ′ ( κ t − ) = d − c t − m t ( κ t − ) + κ t − / β > 0. g_t'(\kappa_t^-)=d-c_t-m_t(\kappa_t^-)+\kappa_t^-/\beta>0. g t ′ ( κ t − ) = d − c t − m t ( κ t − ) + κ t − / β > 0.
Strict convexity places the constrained minimizer below this comparison point, so ℓ t < κ t − \ell_t<\kappa_t^- ℓ t < κ t − and ℓ t + ε t lag < κ t \ell_t+\varepsilon_t^{\operatorname{lag}}<\kappa_t ℓ t + ε t lag < κ t . Similarly, if κ t + ∈ ( 0 , λ max ) \kappa_t^+\in(0,\lambda_{\max}) κ t + ∈ ( 0 , λ m a x ) , condition (S9) gives
g t ′ ( κ t + ) = d − c t − m t ( κ t + ) + κ t + / β < 0 , g_t'(\kappa_t^+)=d-c_t-m_t(\kappa_t^+)+\kappa_t^+/\beta<0, g t ′ ( κ t + ) = d − c t − m t ( κ t + ) + κ t + / β < 0 ,
which implies ℓ t > κ t + \ell_t>\kappa_t^+ ℓ t > κ t + and ℓ t − ε t lag > κ t \ell_t-\varepsilon_t^{\operatorname{lag}}>\kappa_t ℓ t − ε t lag > κ t . Each criterion therefore implies the corresponding regime comparison. □
Convergence with Approximate Actor Best Responses
We use Π \Pi Π , L α \mathcal{L}_{\alpha} L α , B B B , κ \kappa κ , and L Λ L_{\Lambda} L Λ from § 4.1 . We establish convergence of delayed tabular updates with approximate actor best responses under mild assumptions specified below. Theorem 4.1 specializes the analysis to concrete actor updates.
The soft-policy optimality identity underlying Proposition 3.5 of [8 ] gives, with natural logarithms, the quadratic-growth bound
L α ( B ( λ ) , λ ) − L α ( π , λ ) ≥ κ 2 ∥ π − B ( λ ) ∥ F 2 , (40) \mathcal{L}_{\alpha}(B(\lambda),\lambda)-\mathcal{L}_{\alpha}(\pi,\lambda)\geq\frac{\kappa}{2}\lVert\pi-B(\lambda)\rVert_{F}^{2}, \tag*{(40)} L α ( B ( λ ) , λ ) − L α ( π , λ ) ≥ 2 κ ∥ π − B ( λ ) ∥ F 2 , (40)
κ = α ρ min , ρ min = min s ρ ( s ) > 0. \kappa=\alpha\rho_{\min},\qquad\rho_{\min}=\min_{s}\rho(s)>0. κ = α ρ m i n , ρ m i n = s min ρ ( s ) > 0.
Theorem B.2 (Convergence of SDLA). Under the finite-CMDP and entropy assumptions of § 4.1 , fix β \beta β , τ \tau τ , λ max > 0 \lambda_{\max}>0 λ m a x > 0 such that
q : = K c L Λ ( β , τ ) κ < 1. (41) q:=\frac{K_{c}L_{\Lambda}(\beta,\tau)}{\kappa}<1. \tag*{(41)} q := κ K c L Λ ( β , τ ) < 1. (41) Starting from any π 0 ∈ Π \pi_{0}\in\Pi π 0 ∈ Π and λ 0 ∈ [ 0 , λ max ] \lambda_{0}\in[0,\lambda_{\max}] λ 0 ∈ [ 0 , λ m a x ] , let π t ∈ Π \pi_{t}\in\Pi π t ∈ Π and λ t ∈ [ 0 , λ max ] \lambda_{t}\in[0,\lambda_{\max}] λ t ∈ [ 0 , λ m a x ] satisfy, for t ≥ 0 t\geq0 t ≥ 0 ,
L α ( B ( λ t ) , λ t ) − L α ( π t + 1 , λ t ) ≤ ε t , (42) \mathcal{L}_{\alpha}(B(\lambda_{t}),\lambda_{t})-\mathcal{L}_{\alpha}(\pi_{t+1},\lambda_{t})\leq\varepsilon_{t}, \tag*{(42)} L α ( B ( λ t ) , λ t ) − L α ( π t + 1 , λ t ) ≤ ε t , (42) and the delayed dual bound (15) , where ε t , ζ t ≥ 0 \varepsilon_{t},\zeta_{t}\geq0 ε t , ζ t ≥ 0 . Then there is a unique equilibrium ( π ˉ , λ ˉ ) (\bar{\pi},\bar{\lambda}) ( π ˉ , λ ˉ ) with π ˉ = B ( λ ˉ ) \bar{\pi}=B(\bar{\lambda}) π ˉ = B ( λ ˉ ) and λ ˉ = Λ β , τ ( π ˉ ) \bar{\lambda}=\Lambda_{\beta,\tau}(\bar{\pi}) λ ˉ = Λ β , τ ( π ˉ ) .
Writing e t = ∥ π t − π ˉ ∥ F e_{t}=\lVert\pi_{t}-\bar{\pi}\rVert_{F} e t = ∥ π t − π ˉ ∥ F , for t ≥ 1 t\geq1 t ≥ 1 ,
e t + 1 ≤ q e t − 1 + 2 ε t κ + K c κ ζ t − 1 . (43) e_{t+1}\leq qe_{t-1}+\sqrt{\frac{2\varepsilon_{t}}{\kappa}+\frac{K_{c}}{\kappa}\zeta_{t-1}}. \tag*{(43)} e t + 1 ≤ q e t − 1 + κ 2 ε t + κ K c ζ t − 1 . (43) For exact updates, with E 0 = max { e 0 , e 1 } E_{0}=\max\{e_{0},e_{1}\} E 0 = max { e 0 , e 1 } ,
e t ≤ q ⌊ t / 2 ⌋ E 0 , ∣ λ t + 1 − λ ˉ ∣ ≤ L Λ ( β , τ ) q ⌊ t / 2 ⌋ E 0 . (44) e_{t}\leq q^{\lfloor t/2\rfloor}E_{0},\qquad|\lambda_{t+1}-\bar{\lambda}|\leq L_{\Lambda}(\beta,\tau)q^{\lfloor t/2\rfloor}E_{0}. \tag*{(44)} e t ≤ q ⌊ t /2 ⌋ E 0 , ∣ λ t + 1 − λ ˉ ∣ ≤ L Λ ( β , τ ) q ⌊ t /2 ⌋ E 0 . (44) If ε t ≤ ε \varepsilon_{t}\leq\varepsilon ε t ≤ ε and ζ t ≤ ζ \zeta_{t}\leq\zeta ζ t ≤ ζ , then
lim sup t → ∞ e t ≤ 2 ε / κ + ( K c / κ ) ζ 1 − q . (45) \limsup_{t\to\infty}e_{t}\leq\frac{\sqrt{2\varepsilon/\kappa+(K_{c}/\kappa)\zeta}}{1-q}. \tag*{(45)} t → ∞ lim sup e t ≤ 1 − q 2 ε / κ + ( K c / κ ) ζ . (45) If both errors vanish, ( π t , λ t ) → ( π ˉ , λ ˉ ) (\pi_{t},\lambda_{t})\to(\bar{\pi},\bar{\lambda}) ( π t , λ t ) → ( π ˉ , λ ˉ ) .
Proof. Fix α \alpha α , β \beta β , τ \tau τ , λ max > 0 \lambda_{\max}>0 λ m a x > 0 and abbreviate L Λ = L Λ ( β , τ ) L_{\Lambda}=L_{\Lambda}(\beta,\tau) L Λ = L Λ ( β , τ ) . We first derive the regularity constants, then establish contraction of the response maps and convergence of the delayed updates.
Trajectory-weighted cost regularity. For π , π ′ ∈ Π \pi,\pi'\in\Pi π , π ′ ∈ Π , couple their trajectories using the same initial state and the same transition randomness while their state-action pairs agree. At a common state, use a maximal coupling of the action distributions. Let
Δ π = max s TV ( π ( ⋅ ∣ s ) , π ′ ( ⋅ ∣ s ) ) ≤ ∣ A ∣ 2 ∥ π − π ′ ∥ F . \Delta_{\pi}=\max_{s}\operatorname{TV}(\pi(\cdot\mid s),\pi'(\cdot\mid s))\leq\frac{\sqrt{|\mathcal{A}|}}{2}\lVert\pi-\pi'\rVert_{F}. Δ π = s max TV ( π ( ⋅ ∣ s ) , π ′ ( ⋅ ∣ s )) ≤ 2 ∣ A ∣ ∥ π − π ′ ∥ F .
The probability of a first action disagreement by time j j j is at most ( j + 1 ) Δ π (j+1)\Delta_{\pi} ( j + 1 ) Δ π . With R , C R,C R , C and R ′ , C ′ R',C' R ′ , C ′ denoting the coupled discounted returns, bounded one-step rewards and costs imply
E ∣ C − C ′ ∣ ≤ C max ∑ j ≥ 0 γ j ( j + 1 ) Δ π ≤ K c ∥ π − π ′ ∥ F , \mathbb{E}|C-C'|\leq C_{\max}\sum_{j\geq0}\gamma^{j}(j+1)\Delta_{\pi}\leq K_{c}\lVert\pi-\pi'\rVert_{F}, E ∣ C − C ′ ∣ ≤ C m a x j ≥ 0 ∑ γ j ( j + 1 ) Δ π ≤ K c ∥ π − π ′ ∥ F ,
E ∣ R − R ′ ∣ ≤ K r ∥ π − π ′ ∥ F , K c = C max ∣ A ∣ 2 ( 1 − γ ) 2 , K r = R max ∣ A ∣ 2 ( 1 − γ ) 2 . (46) \mathbb{E}|R-R'|\leq K_{r}\lVert\pi-\pi'\rVert_{F},\qquad K_{c}=\frac{C_{\max}\sqrt{|\mathcal{A}|}}{2(1-\gamma)^{2}},\qquad K_{r}=\frac{R_{\max}\sqrt{|\mathcal{A}|}}{2(1-\gamma)^{2}}. \tag*{(46)} E ∣ R − R ′ ∣ ≤ K r ∥ π − π ′ ∥ F , K c = 2 ( 1 − γ ) 2 C m a x ∣ A ∣ , K r = 2 ( 1 − γ ) 2 R m a x ∣ A ∣ . (46)
In particular, ∣ J c ( π ) − J c ( π ′ ) ∣ ≤ K c ∥ π − π ′ ∥ F |J^{c}(\pi)-J^{c}(\pi')|\leq K_{c}\lVert\pi-\pi'\rVert_{F} ∣ J c ( π ) − J c ( π ′ ) ∣ ≤ K c ∥ π − π ′ ∥ F . Write R ˉ = R max / ( 1 − γ ) \bar{R}=R_{\max}/(1-\gamma) R ˉ = R m a x / ( 1 − γ ) and
Z π ( λ ) = E π e ( R − λ C ) / τ , N π ( λ ) = E π [ C e ( R − λ C ) / τ ] . Z_{\pi}(\lambda)=\mathbb{E}_{\pi}e^{(R-\lambda C)/\tau},\qquad N_{\pi}(\lambda)=\mathbb{E}_{\pi}[Ce^{(R-\lambda C)/\tau}]. Z π ( λ ) = E π e ( R − λ C ) / τ , N π ( λ ) = E π [ C e ( R − λ C ) / τ ] .
For all λ ∈ [ 0 , λ max ] \lambda\in[0,\lambda_{\max}] λ ∈ [ 0 , λ m a x ] , the exponential weights lie between e − λ max C ˉ / τ e^{-\lambda_{\max}\bar{C}/\tau} e − λ m a x C ˉ / τ and e R ˉ / τ e^{\bar{R}/\tau} e R ˉ / τ . The mean-value inequality and (S20) give
∣ Z π ( λ ) − Z π ′ ( λ ) ∣ ≤ e R ˉ / τ τ ( K r + λ max K c ) ∥ π − π ′ ∥ F , |Z_{\pi}(\lambda)-Z_{\pi'}(\lambda)|\leq\frac{e^{\bar{R}/\tau}}{\tau}(K_{r}+\lambda_{\max}K_{c})\lVert\pi-\pi'\rVert_{F}, ∣ Z π ( λ ) − Z π ′ ( λ ) ∣ ≤ τ e R ˉ / τ ( K r + λ m a x K c ) ∥ π − π ′ ∥ F ,
∣ N π ( λ ) − N π ′ ( λ ) ∣ ≤ e R ˉ / τ [ K c + C ˉ τ ( K r + λ max K c ) ] ∥ π − π ′ ∥ F . |N_{\pi}(\lambda)-N_{\pi'}(\lambda)|\leq e^{\bar{R}/\tau}\left[K_{c}+\frac{\bar{C}}{\tau}(K_{r}+\lambda_{\max}K_{c})\right]\lVert\pi-\pi'\rVert_{F}. ∣ N π ( λ ) − N π ′ ( λ ) ∣ ≤ e R ˉ / τ [ K c + τ C ˉ ( K r + λ m a x K c ) ] ∥ π − π ′ ∥ F .
Since m π , τ = N π / Z π m_{\pi,\tau}=N_{\pi}/Z_{\pi} m π , τ = N π / Z π and 0 ≤ m π , τ ≤ C ˉ 0\leq m_{\pi,\tau}\leq\bar{C} 0 ≤ m π , τ ≤ C ˉ ,
∣ m π , τ ( λ ) − m π ′ , τ ( λ ) ∣ ≤ ∣ N π − N π ′ ∣ + C ˉ ∣ Z π − Z π ′ ∣ Z π . |m_{\pi,\tau}(\lambda)-m_{\pi',\tau}(\lambda)|\leq\frac{|N_{\pi}-N_{\pi'}|+\bar{C}|Z_{\pi}-Z_{\pi'}|}{Z_{\pi}}. ∣ m π , τ ( λ ) − m π ′ , τ ( λ ) ∣ ≤ Z π ∣ N π − N π ′ ∣ + C ˉ ∣ Z π − Z π ′ ∣ .
Consequently,
∣ m π , τ ( λ ) − m π ′ , τ ( λ ) ∣ ≤ K m ( τ ) ∥ π − π ′ ∥ F , |m_{\pi,\tau}(\lambda)-m_{\pi',\tau}(\lambda)|\leq K_{m}(\tau)\lVert\pi-\pi'\rVert_{F}, ∣ m π , τ ( λ ) − m π ′ , τ ( λ ) ∣ ≤ K m ( τ ) ∥ π − π ′ ∥ F ,
K m ( τ ) = e ( R ˉ + λ max C ˉ ) / τ [ K c + 2 C ˉ τ ( K r + λ max K c ) ] . (47) K_{m}(\tau)=e^{(\bar{R}+\lambda_{\max}\bar{C})/\tau}\left[K_{c}+\frac{2\bar{C}}{\tau}(K_{r}+\lambda_{\max}K_{c})\right]. \tag*{(47)} K m ( τ ) = e ( R ˉ + λ m a x C ˉ ) / τ [ K c + τ 2 C ˉ ( K r + λ m a x K c ) ] . (47)
This bound is uniform over the clipped multiplier interval.
Dual-response sensitivity. Apply Theorem 3.3 to π \pi π and π ′ \pi' π ′ , evaluating the weighted-cost change at ℓ = Λ β , τ ( π ) \ell= \Lambda_{\beta,\tau}(\pi) ℓ = Λ β , τ ( π ) . The combined signal is bounded by
∣ J c ( π ′ ) − J c ( π ) ∣ + ∣ m π ′ , τ ( ℓ ) − m π , τ ( ℓ ) ∣ ≤ [ K c + K m ( τ ) ] ∥ π − π ′ ∥ F . \left|J^{c}(\pi') - J^{c}(\pi)\right| + \left|m_{\pi',\tau}(\ell) - m_{\pi,\tau}(\ell)\right| \le\left[K_{c} + K_{m}(\tau)\right]\lVert\pi- \pi'\rVert_{F}. ∣ J c ( π ′ ) − J c ( π ) ∣ + ∣ m π ′ , τ ( ℓ ) − m π , τ ( ℓ ) ∣ ≤ [ K c + K m ( τ ) ] ∥ π − π ′ ∥ F .
Thus, including responses at the endpoints,
∣ Λ β , τ ( π ) − Λ β , τ ( π ′ ) ∣ ≤ L Λ ∥ π − π ′ ∥ F . (48) \left|\Lambda_{\beta,\tau}(\pi) - \Lambda_{\beta,\tau}(\pi')\right| \le L_{\Lambda}\lVert\pi- \pi'\rVert_{F}. \tag*{(48)} ∣ Λ β , τ ( π ) − Λ β , τ ( π ′ ) ∣ ≤ L Λ ∥ π − π ′ ∥ F . (48)
Actor best-response sensitivity. The policy space is compact and L α \mathcal{L}_{\alpha} L α is continuous, so an actor maximizer exists. The normalized discounted visitation distribution satisfies
d ρ π ( s ) = ( 1 − γ ) ∑ j ≥ 0 γ j Pr π ( s j = s ) ≥ ( 1 − γ ) ρ ( s ) ≥ ( 1 − γ ) ρ min . d_{\rho}^{\pi}(s) = (1-\gamma)\sum_{j\geq0}\gamma^{j}\Pr_{\pi}(s_{j}=s) \geq(1-\gamma)\rho(s) \geq(1-\gamma)\rho_{\min}. d ρ π ( s ) = ( 1 − γ ) j ≥ 0 ∑ γ j π Pr ( s j = s ) ≥ ( 1 − γ ) ρ ( s ) ≥ ( 1 − γ ) ρ m i n .
The soft Bellman optimum obeys B ( λ ) ( a ∣ s ) ∝ exp ( Q λ ⋆ ( s , a ) / α ) B(\lambda)(a\mid s) \propto\exp(Q_{\lambda}^{\star}(s,a)/\alpha) B ( λ ) ( a ∣ s ) ∝ exp ( Q λ ⋆ ( s , a ) / α ) . Subtracting the Bellman expectation equation for V π π V_{\pi}^{\pi} V π π from the soft optimality equation and iterating the residual gives the identity underlying Proposition 3.5 of [8 ] :
L α ( B ( λ ) , λ ) − L α ( π , λ ) = α 1 − γ ∑ s d ρ π ( s ) KL ( π ( ⋅ ∣ s ) ∥ B ( λ ) ( ⋅ ∣ s ) ) . (49) \mathcal{L}_{\alpha}(B(\lambda),\lambda) - \mathcal{L}_{\alpha}(\pi,\lambda) = \frac{\alpha}{1-\gamma}\sum_{s}d_{\rho}^{\pi}(s)\operatorname{KL}\left(\pi(\cdot\mid s)\mathbin{\|}B(\lambda)(\cdot\mid s)\right). \tag*{(49)} L α ( B ( λ ) , λ ) − L α ( π , λ ) = 1 − γ α s ∑ d ρ π ( s ) KL ( π ( ⋅ ∣ s ) ∥ B ( λ ) ( ⋅ ∣ s ) ) . (49)
Pinsker’s inequality for natural logarithms gives KL ( p ∥ p ′ ) ≥ 1 2 ∥ p − p ′ ∥ 1 2 ≥ 1 2 ∥ p − p ′ ∥ 2 2 \operatorname{KL}(p\mathbin{\|}p') \geq\frac{1}{2}\lVert p-p'\rVert_{1}^{2} \geq\frac{1}{2}\lVert p-p'\rVert_{2}^{2} KL ( p ∥ p ′ ) ≥ 2 1 ∥ p − p ′ ∥ 1 2 ≥ 2 1 ∥ p − p ′ ∥ 2 2 . Together with d ρ π ( s ) ≥ ( 1 − γ ) ρ min d_{\rho}^{\pi}(s) \geq(1-\gamma)\rho_{\min} d ρ π ( s ) ≥ ( 1 − γ ) ρ m i n , this proves (S14) with κ = α ρ min \kappa= \alpha\rho_{\min} κ = α ρ m i n and makes the maximizer unique. The actor reward is r − λ c r-\lambda c r − λ c , up to the constant λ d \lambda d λ d . For π i = B ( λ i ) \pi_i = B(\lambda_i) π i = B ( λ i ) , apply the quadratic-growth bound at each multiplier and add the two inequalities. The reward and entropy terms cancel, giving
κ ∥ π 1 − π 2 ∥ F 2 ≤ ( λ 2 − λ 1 ) [ J c ( π 1 ) − J c ( π 2 ) ] ≤ K c ∣ λ 1 − λ 2 ∣ ∥ π 1 − π 2 ∥ F . \kappa\lVert\pi_{1}-\pi_{2}\rVert_{F}^{2} \leq(\lambda_{2}-\lambda_{1})\left[J^{c}(\pi_{1})-J^{c}(\pi_{2})\right] \leq K_{c}|\lambda_{1}-\lambda_{2}|\lVert\pi_{1}-\pi_{2}\rVert_{F}. κ ∥ π 1 − π 2 ∥ F 2 ≤ ( λ 2 − λ 1 ) [ J c ( π 1 ) − J c ( π 2 ) ] ≤ K c ∣ λ 1 − λ 2 ∣ ∥ π 1 − π 2 ∥ F .
Thus
∥ B ( λ ) − B ( λ ′ ) ∥ F ≤ ( K c / κ ) ∣ λ − λ ′ ∣ . (50) \lVert B(\lambda)-B(\lambda')\rVert_{F} \leq(K_{c}/\kappa)|\lambda-\lambda'|. \tag*{(50)} ∥ B ( λ ) − B ( λ ′ ) ∥ F ≤ ( K c / κ ) ∣ λ − λ ′ ∣. (50)
Existence and uniqueness. Define F β , τ ( λ ) = Λ β , τ ( B ( λ ) ) F_{\beta,\tau}(\lambda)=\Lambda_{\beta,\tau}(B(\lambda)) F β , τ ( λ ) = Λ β , τ ( B ( λ )) . Equations (S22) and (S24) imply
∣ F β , τ ( λ ) − F β , τ ( λ ′ ) ∣ ≤ q ∣ λ − λ ′ ∣ . (51) |F_{\beta,\tau}(\lambda)-F_{\beta,\tau}(\lambda')| \leq q|\lambda-\lambda'|. \tag*{(51)} ∣ F β , τ ( λ ) − F β , τ ( λ ′ ) ∣ ≤ q ∣ λ − λ ′ ∣. (51)
Since q < 1 q<1 q < 1 , this self-map of the closed interval [ 0 , λ max ] [0,\lambda_{\max}] [ 0 , λ m a x ] has a unique fixed point λ ˉ \bar{\lambda} λ ˉ . Setting π ˉ = B ( λ ˉ ) \bar{\pi}=B(\bar{\lambda}) π ˉ = B ( λ ˉ ) gives the unique equilibrium.
Delayed and inexact updates. The actor objective gap and (S14) give
∥ π t + 1 − B ( λ t ) ∥ F ≤ 2 ϵ t / κ . \lVert\pi_{t+1}-B(\lambda_t)\rVert_{F} \leq\sqrt{2\epsilon_t/\kappa}. ∥ π t + 1 − B ( λ t ) ∥ F ≤ 2 ϵ t / κ .
For t ≥ 1 t\geq1 t ≥ 1 , the delayed dual update implies
∣ λ t − λ ˉ ∣ ≤ ζ t − 1 + L Λ e t − 1 . |\lambda_t-\bar{\lambda}| \leq\zeta_{t-1}+L_{\Lambda}e_{t-1}. ∣ λ t − λ ˉ ∣ ≤ ζ t − 1 + L Λ e t − 1 .
The triangle inequality and (S24) now yield
e t + 1 ≤ 2 ϵ t / κ + ( K c / κ ) ∣ λ t − λ ˉ ∣ ≤ q e t − 1 + 2 ϵ t / κ + ( K c / κ ) ζ t − 1 . e_{t+1} \leq\sqrt{2\epsilon_t/\kappa}+(K_{c}/\kappa)|\lambda_t-\bar{\lambda}| \leq qe_{t-1}+\sqrt{2\epsilon_t/\kappa}+(K_{c}/\kappa)\zeta_{t-1}. e t + 1 ≤ 2 ϵ t / κ + ( K c / κ ) ∣ λ t − λ ˉ ∣ ≤ q e t − 1 + 2 ϵ t / κ + ( K c / κ ) ζ t − 1 .
This proves (S17). Exact updates contract each of the even and odd policy subsequences by q q q , giving (S18). For bounded errors, let a = 2 ϵ / κ + ( K c / κ ) ζ a=\sqrt{2\epsilon/\kappa}+(K_{c}/\kappa)\zeta a = 2 ϵ / κ + ( K c / κ ) ζ . Each subsequence satisfies a recurrence of the form x j + 1 ≤ q x j + a x_{j+1}\leq qx_j+a x j + 1 ≤ q x j + a ; summing the geometric series gives (S19). If both errors vanish, applying the same argument to every tail gives lim sup e t = 0 \limsup e_t=0 lim sup e t = 0 . The bound ∣ λ t + 1 − λ ˉ ∣ ≤ ζ t + L Λ e t |\lambda_{t+1}-\bar{\lambda}|\leq\zeta_t+L_{\Lambda}e_t ∣ λ t + 1 − λ ˉ ∣ ≤ ζ t + L Λ e t then proves multiplier convergence.
Interpretation of the contraction condition. The bound q = b L Λ < 1 q=bL_{\Lambda}<1 q = b L Λ < 1 controls the product of the actor and multiplier response gains. Similar conditions are used to establish stability of coupled learning systems. Guo et al. [27 Theorem 1] and Xie et al. [28 Lemma 1 and Theorem 1] use d 1 + d 2 + d 3 < 1 d_{1}+d_{2}+d_{3}<1 d 1 + d 2 + d 3 < 1 for a composite policy–population response. In SDLA, F β , τ ( λ ) = Λ β , τ ( B ( λ ) ) F_{\beta,\tau}(\lambda)=\Lambda_{\beta,\tau}(B(\lambda)) F β , τ ( λ ) = Λ β , τ ( B ( λ )) depends on λ \lambda λ through B B B , yielding the product bound q = b L Λ q=bL_{\Lambda} q = b L Λ . Mandal et al. [29 Theorem 1] obtain a contraction factor μ < 1 \mu<1 μ < 1 by choosing regularization sufficiently strong relative to environment sensitivity. Olshevsky and Gharesifard [30 ] use a small-gain argument to control coupled actor and critic errors.
For fixed problem parameters, α \alpha α , τ \tau τ , and λ max \lambda_{\max} λ m a x , the constants K c K_c K c , K m ( τ ) K_m(\tau) K m ( τ ) , and κ > 0 \kappa>0 κ > 0 are independent of β \beta β . For K c > 0 K_c>0 K c > 0 , the explicit choice
0 < β < κ K c [ K c + K m ( τ ) ] 0<\beta<\frac{\kappa}{K_c[K_c+K_m(\tau)]} 0 < β < K c [ K c + K m ( τ )] κ
therefore ensures q < 1 q<1 q < 1 , giving a nonempty sufficient range for stability of the response loop. If K c = 0 K_c=0 K c = 0 , then q = 0 q=0 q = 0 . Corollary 4.3 combines the convergence condition with parameter matching to identify the equilibrium with the CMDP optimum.
Sampling and scalar-solver errors. Let λ ^ t \hat{\lambda}_t λ ^ t minimize the empirical surrogate on the batch collected under π t \pi_t π t , and suppose the numerical solve satisfies ∣ λ t + 1 − λ ^ t ∣ ≤ υ t |\lambda_{t+1}-\hat{\lambda}_t|\leq\upsilon_t ∣ λ t + 1 − λ ^ t ∣ ≤ υ t . The derivative discrepancy between empirical and population surrogates is bounded by
∣ c ^ t − J c ( π t ) ∣ + sup λ ∈ [ 0 , λ max ] ∣ m ^ t ( λ ) − m π t , τ ( λ ) ∣ . \left|\hat{c}_t-J^c(\pi_t)\right|+\sup_{\lambda\in[0,\lambda_{\max}]}\left|\hat{m}_t(\lambda)-m_{\pi_t,\tau}(\lambda)\right|. ∣ c ^ t − J c ( π t ) ∣ + λ ∈ [ 0 , λ m a x ] sup ∣ m ^ t ( λ ) − m π t , τ ( λ ) ∣ .
Applying the constrained strong-monotonicity argument above and the triangle inequality gives the pathwise bound
∣ λ t + 1 − Λ β , τ ( π t ) ∣ ≤ β ( ∣ c ^ t − J c ( π t ) ∣ + sup λ ∈ [ 0 , λ max ] ∣ m ^ t ( λ ) − m π t , τ ( λ ) ∣ ) + υ t . (52) |\lambda_{t+1}-\Lambda_{\beta,\tau}(\pi_t)|\leq\beta\left(\left|\hat{c}_t-J^c(\pi_t)\right|+\sup_{\lambda\in[0,\lambda_{\max}]}\left|\hat{m}_t(\lambda)-m_{\pi_t,\tau}(\lambda)\right|\right)+\upsilon_t. \tag*{(52)} ∣ λ t + 1 − Λ β , τ ( π t ) ∣ ≤ β ( ∣ c ^ t − J c ( π t ) ∣ + λ ∈ [ 0 , λ m a x ] sup ∣ m ^ t ( λ ) − m π t , τ ( λ ) ∣ ) + υ t . (52)
The right-hand side can therefore be used as ζ t \zeta_t ζ t in Theorem B.2. It separates trajectory-estimation error from numerical optimization error.
Convergence with Concrete Actor Updates
We prove the convergence result under mild assumptions stated in Theorem 4.1, using the same delayed updates and actor and dual error bounds as in § 4.1 .
Uniform constants for actor optimization
For the updates in § 4.1 , let n = ∣ S ∣ ∣ A ∣ n=|\mathcal{S}||\mathcal{A}| n = ∣ S ∣∣ A ∣ . The constants in (S34) can be chosen as
D Q = R max + λ max C max + α log ∣ A ∣ 1 − γ , (53) D_Q=\frac{R_{\max}+\lambda_{\max}C_{\max}+\alpha\log|\mathcal{A}|}{1-\gamma}, \tag*{(53)} D Q = 1 − γ R m a x + λ m a x C m a x + α log ∣ A ∣ , (53)
p ∗ = min { min s , a π 0 ( a ∣ s ) , e − ( D Q + 2 ξ ˉ ) / α ∣ A ∣ } , (54) p_*=\min\left\{\min_{s,a}\pi_0(a\mid s),\frac{e^{-(D_Q+2\bar{\xi})/\alpha}}{|\mathcal{A}|}\right\}, \tag*{(54)} p ∗ = min { s , a min π 0 ( a ∣ s ) , ∣ A ∣ e − ( D Q + 2 ξ ˉ ) / α } , (54)
A 0 = 2 n α [ D Q + 2 α ( 1 − ω ) log ( 1 / p ∗ ) ] , (55) A_0=\frac{2\sqrt{n}}{\alpha}\left[D_Q+2\alpha(1-\omega)\log(1/p_*)\right], \tag*{(55)} A 0 = α 2 n [ D Q + 2 α ( 1 − ω ) log ( 1/ p ∗ ) ] , (55)
A 1 = 4 n α ( 1 − γ ) ( 1 + γ ( 1 − γ ) ω ) . (56) A_1=\frac{4\sqrt{n}}{\alpha(1-\gamma)}\left(1+\frac{\gamma}{(1-\gamma)\omega}\right). \tag*{(56)} A 1 = α ( 1 − γ ) 4 n ( 1 + ( 1 − γ ) ω γ ) . (56)
These constants depend on the fixed problem parameters, initialization, and uniform critic-error bound ξ ˉ \bar{\xi} ξ ˉ , and are independent of the outer iteration. We use K c K_c K c , K ~ m ( τ ) \tilde{K}_m(\tau) K ~ m ( τ ) , L Λ L_\Lambda L Λ from Appendix B.2.4, κ = α ρ min \kappa=\alpha\rho_{\min} κ = α ρ m i n , b = K c / κ b=K_c/\kappa b = K c / κ , and q = b L Λ q=bL_\Lambda q = b L Λ .
Tabular Actor Updates and Approximation Bounds
We now derive the actor approximation error from explicit policy updates. Work in the finite tabular setting of § 4.1 , with 0 < γ < 1 0<\gamma<1 0 < γ < 1 , fixed α > 0 \alpha>0 α > 0 , and an initial policy satisfying min s , a π 0 ( a ∣ s ) > 0 \min_{s,a}\pi_0(a\mid s)>0 min s , a π 0 ( a ∣ s ) > 0 . At outer iteration t t t , hold λ t \lambda_t λ t fixed and initialize π t 0 = π t \pi_t^0=\pi_t π t 0 = π t . The soft critic for the penalized reward satisfies
Q λ π ( s , a ) = r ( s , a ) − λ c ( s , a ) + γ E s ′ ∣ s , a V λ π ( s ′ ) , Q_{\lambda}^{\pi}(s,a)=r(s,a)-\lambda c(s,a)+\gamma\mathbb{E}_{s'\mid s,a}V_{\lambda}^{\pi}(s'), Q λ π ( s , a ) = r ( s , a ) − λ c ( s , a ) + γ E s ′ ∣ s , a V λ π ( s ′ ) ,
V λ π ( s ) = ∑ a π ( a ∣ s ) Q λ π ( s , a ) + α H ( π ( ⋅ ∣ s ) ) , (57) V_{\lambda}^{\pi}(s)=\sum_a\pi(a\mid s)Q_{\lambda}^{\pi}(s,a)+\alpha\mathcal{H}(\pi(\cdot\mid s)), \tag*{(57)} V λ π ( s ) = a ∑ π ( a ∣ s ) Q λ π ( s , a ) + α H ( π ( ⋅ ∣ s )) , (57)
where H \mathcal{H} H is single-state Shannon entropy. For k = 0 , … , K t − 1 k=0,\ldots,K_t-1 k = 0 , … , K t − 1 , suppose ∥ Q ^ t k − Q λ t π t k ∥ ∞ ≤ ξ t \lVert\hat{Q}_t^k-Q_{\lambda_t}^{\pi_t^k}\rVert_\infty\leq\xi_t ∥ Q ^ t k − Q λ t π t k ∥ ∞ ≤ ξ t , with 0 ≤ ξ t ≤ ξ ˉ < ∞ 0\leq\xi_t\leq\bar{\xi}<\infty 0 ≤ ξ t ≤ ξ ˉ < ∞ , and update
π t k + 1 ( a ∣ s ) = [ π t k ( a ∣ s ) ] 1 − ω exp ( ω Q ^ t k ( s , a ) / α ) ∑ b [ π t k ( b ∣ s ) ] 1 − ω exp ( ω Q ^ t k ( s , b ) / α ) , 0 < ω ≤ 1. (58) \pi_t^{k+1}(a\mid s)=\frac{[\pi_t^k(a\mid s)]^{1-\omega}\exp(\omega\hat{Q}_t^k(s,a)/\alpha)}{\sum_b[\pi_t^k(b\mid s)]^{1-\omega}\exp(\omega\hat{Q}_t^k(s,b)/\alpha)},\qquad0<\omega\leq1. \tag*{(58)} π t k + 1 ( a ∣ s ) = ∑ b [ π t k ( b ∣ s ) ] 1 − ω exp ( ω Q ^ t k ( s , b ) / α ) [ π t k ( a ∣ s ) ] 1 − ω exp ( ω Q ^ t k ( s , a ) / α ) , 0 < ω ≤ 1. (58)
Set π t + 1 = π t K t \pi_{t+1}=\pi_t^{K_t} π t + 1 = π t K t , where K t ≥ 1 K_t\geq1 K t ≥ 1 , and retain the delayed dual update (15), with error ζ t \zeta_t ζ t . For ω = 1 \omega=1 ω = 1 , this is soft policy improvement over the tabular simplex, which underlies SAC [24 ] . For 0 < ω < 1 0<\omega<1 0 < ω < 1 , it solves the statewise entropy-regularized KL-penalty problem
max p ∈ Δ ( A ) { ⟨ p , Q ^ t k ( s , ⋅ ) ⟩ + α H ( p ) − α ( 1 − ω ) ω KL ( p ∥ π t k ( ⋅ ∣ s ) ) } . (59) \max_{p\in\Delta(\mathcal{A})}\left\{\langle p,\hat{Q}_t^k(s,\cdot)\rangle+\alpha\mathcal{H}(p)-\frac{\alpha(1-\omega)}{\omega}\operatorname{KL}\left(p\middle\|\pi_t^k(\cdot\mid s)\right)\right\}. \tag*{(59)} p ∈ Δ ( A ) max { ⟨ p , Q ^ t k ( s , ⋅ )⟩ + α H ( p ) − ω α ( 1 − ω ) KL ( p π t k ( ⋅ ∣ s ) ) } . (59)
This KL-PPO variant uses the new-to-old KL direction studied by Liu et al. [25 ] . Its exact tabular update coincides with entropy-regularized natural policy gradient at learning rate η = ( 1 − γ ) α / ω \eta=(1-\gamma)\alpha/\omega η = ( 1 − γ ) α / ω [26 ] . This equivalence supplies the actor convergence rate below. The analyzed updates use a fixed entropy coefficient and the full tabular simplex; the PPO-Clip and neural SAC implementations in the experiments use function approximation.
Write b = K c / κ b=K_c/\kappa b = K c / κ , L Λ = L Λ ( β , τ ) L_\Lambda=L_\Lambda(\beta,\tau) L Λ = L Λ ( β , τ ) , and χ = 1 − ( 1 − γ ) ω ∈ ( 0 , 1 ) \chi=1-(1-\gamma)\omega\in(0,1) χ = 1 − ( 1 − γ ) ω ∈ ( 0 , 1 ) . The constants A 0 , A 1 A_0,A_1 A 0 , A 1 in (S29)–(S30) are uniform over outer iterations and satisfy
∥ π t + 1 − B ( λ t ) ∥ F ≤ A 0 χ K t − 1 + A 1 ξ t . (60) \lVert\pi_{t+1}-B(\lambda_t)\rVert_F\leq A_0\chi^{K_t-1}+A_1\xi_t. \tag*{(60)} ∥ π t + 1 − B ( λ t ) ∥ F ≤ A 0 χ K t − 1 + A 1 ξ t . (60)
The two terms quantify finite actor optimization and critic estimation error.
Proof of Theorem 4.1
Proof. Identification of the actor update. For 0 < ω < 1 0 < \omega< 1 0 < ω < 1 , the statewise objective in (S33) is strictly concave. Its first-order conditions, including the probability-normalization multiplier, give
log p ( a ) = ( 1 − ω ) log π t k ( a ∣ s ) + ω α Q ^ t k ( s , a ) + constant . \log p(a) = (1-\omega)\log\pi_t^k(a \mid s) + \frac{\omega}{\alpha}\widehat{Q}_t^k(s,a) + \text{constant}. log p ( a ) = ( 1 − ω ) log π t k ( a ∣ s ) + α ω Q t k ( s , a ) + constant .
Normalizing gives (S32). At ω = 1 \omega= 1 ω = 1 , the same formula gives the Gibbs soft-policy improvement. The entropy-regularized natural policy gradient update of Cen et al. [26 ] has old-policy exponent 1 − η α / ( 1 − γ ) 1-\eta\alpha/(1-\gamma) 1 − η α / ( 1 − γ ) and critic exponent η / ( 1 − γ ) \eta/(1-\gamma) η / ( 1 − γ ) . Setting η = ( 1 − γ ) ω / α \eta=(1-\gamma)\omega/\alpha η = ( 1 − γ ) ω / α therefore gives exactly the specified actor update.
Uniform support across warm starts. For every policy and λ ∈ [ 0 , λ max ] \lambda\in[0,\lambda_{\max}] λ ∈ [ 0 , λ m a x ] , the soft critic lies in the common interval
[ − λ max C max 1 − γ , R max + α log ∣ A ∣ 1 − γ ] . \left[-\frac{\lambda_{\max}C_{\max}}{1-\gamma},\frac{R_{\max}+\alpha\log|\mathcal{A}|}{1-\gamma}\right]. [ − 1 − γ λ m a x C m a x , 1 − γ R m a x + α log ∣ A ∣ ] .
Its width is D Q D_Q D Q . Since ∥ Q ^ t k − Q λ t π t k ∥ ∞ ≤ ξ ˉ \lVert\widehat{Q}_t^k-Q_{\lambda_t}^{\pi_t^k}\rVert_\infty\le\bar{\xi} ∥ Q t k − Q λ t π t k ∥ ∞ ≤ ξ ˉ , the Gibbs distribution u ( a ) ∝ exp ( Q ^ t k ( s , a ) / α ) u(a)\propto\exp(\widehat{Q}_t^k(s,a)/\alpha) u ( a ) ∝ exp ( Q t k ( s , a ) / α ) has every coordinate at least e − ( D Q + 2 ξ ˉ ) / α / ∣ A ∣ e^{-(D_Q+2\bar{\xi})/\alpha}/|\mathcal{A}| e − ( D Q + 2 ξ ˉ ) / α /∣ A ∣ . The actor update is the normalized geometric mixture p ( a ) 1 − ω u ( a ) ω p(a)^{1-\omega}u(a)^\omega p ( a ) 1 − ω u ( a ) ω , where p = π t k ( ⋅ ∣ s ) p=\pi_t^k(\cdot\mid s) p = π t k ( ⋅ ∣ s ) . Hölder’s inequality gives
∑ a p ( a ) 1 − ω u ( a ) ω ≤ ( ∑ a p ( a ) ) 1 − ω ( ∑ a u ( a ) ) ω = 1. \sum_a p(a)^{1-\omega}u(a)^\omega\le\left(\sum_a p(a)\right)^{1-\omega}\left(\sum_a u(a)\right)^\omega=1. a ∑ p ( a ) 1 − ω u ( a ) ω ≤ ( a ∑ p ( a ) ) 1 − ω ( a ∑ u ( a ) ) ω = 1.
Thus p ( a ) , u ( a ) ≥ p ∗ p(a),u(a)\ge p_* p ( a ) , u ( a ) ≥ p ∗ imply π t k + 1 ( a ∣ s ) ≥ p ∗ \pi_{t}^{k+1}(a\mid s)\ge p_* π t k + 1 ( a ∣ s ) ≥ p ∗ . Induction over inner and outer iterations, with π 0 t = π t \pi_0^t=\pi_t π 0 t = π t , proves a uniform lower bound p ∗ p_* p ∗ for every iterate. The Gibbs optimal policy B ( λ ) B(\lambda) B ( λ ) satisfies the same bound.
Actor error from finite inner iterations. Theorems 1–2 of Cen et al. [26 ] , specifically the log-policy error bound with approximate policy evaluation, give
∥ log π t + 1 − log B ( λ t ) ∥ ∞ ≤ 2 α [ C 1 , t χ K t − 1 + 2 ξ t 1 − γ ( 1 + γ ( 1 − γ ) ω ) ] (61) \lVert\log\pi_{t+1}-\log B(\lambda_t)\rVert_\infty\le\frac{2}{\alpha}\left[C_{1,t}\chi^{K_t-1}+\frac{2\xi_t}{1-\gamma}\left(1+\frac{\gamma}{(1-\gamma)\omega}\right)\right] \tag*{(61)} ∥ log π t + 1 − log B ( λ t ) ∥ ∞ ≤ α 2 [ C 1 , t χ K t − 1 + 1 − γ 2 ξ t ( 1 + ( 1 − γ ) ω γ ) ] (61)
where
C 1 , t = ∥ Q λ t ∗ − Q λ t π t ∥ ∞ + 2 α ( 1 − ω ) ∥ log B ( λ t ) − log π t ∥ ∞ . C_{1,t}=\lVert Q_{\lambda_t}^*-Q_{\lambda_t}^{\pi_t}\rVert_\infty+2\alpha(1-\omega)\lVert\log B(\lambda_t)-\log\pi_t\rVert_\infty. C 1 , t = ∥ Q λ t ∗ − Q λ t π t ∥ ∞ + 2 α ( 1 − ω ) ∥ log B ( λ t ) − log π t ∥ ∞ .
To apply the reward normalization in that result, choose S = max { 1 , R max + λ max C max } S=\max\{1,R_{\max}+\lambda_{\max}C_{\max}\} S = max { 1 , R m a x + λ m a x C m a x } and transform the reward to ( r − λ c + λ max C max ) / S (r-\lambda c+\lambda_{\max}C_{\max})/S ( r − λ c + λ m a x C m a x ) / S , the entropy coefficient to α / S \alpha/S α / S , and critic errors to ξ t / S \xi_t/S ξ t / S . The transformed reward lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] . The shift adds the same constant to all action values, and scaling the critic and entropy coefficient by 1 / S 1/S 1/ S preserves the policy update. Rescaling the bound gives (S35).
The common critic interval and uniform support bound imply
C 1 , t ≤ D Q + 2 α ( 1 − ω ) log ( 1 / p ∗ ) . C_{1,t}\le D_Q+2\alpha(1-\omega)\log(1/p_*). C 1 , t ≤ D Q + 2 α ( 1 − ω ) log ( 1/ p ∗ ) .
For x , y ∈ ( 0 , 1 ] x,y\in(0,1] x , y ∈ ( 0 , 1 ] , ∣ x − y ∣ ≤ ∣ log x − log y ∣ |x-y|\le|\log x-\log y| ∣ x − y ∣ ≤ ∣ log x − log y ∣ . Hence the Frobenius policy error is at most n \sqrt{n} n times the log-policy error in the supremum norm. Substituting the preceding bound into (S35) proves (S34) with the constants in (S29)–(S30).
Coupled convergence. Appendix B.2.4 establishes
∥ B ( λ ) − B ( λ ′ ) ∥ F ≤ b ∣ λ − λ ′ ∣ , ∣ Λ β , τ ( π ) − Λ β , τ ( π ′ ) ∣ ≤ L Λ ∥ π − π ′ ∥ F . \lVert B(\lambda)-B(\lambda')\rVert_F\le b|\lambda-\lambda'|,\qquad|\Lambda_{\beta,\tau}(\pi)-\Lambda_{\beta,\tau}(\pi')|\le L_\Lambda\lVert\pi-\pi'\rVert_F. ∥ B ( λ ) − B ( λ ′ ) ∥ F ≤ b ∣ λ − λ ′ ∣ , ∣ Λ β , τ ( π ) − Λ β , τ ( π ′ ) ∣ ≤ L Λ ∥ π − π ′ ∥ F .
Thus Λ β , τ ∘ B \Lambda_{\beta,\tau}\circ B Λ β , τ ∘ B is a contraction on [ 0 , λ max ] [0,\lambda_{\max}] [ 0 , λ m a x ] with factor q < 1 q<1 q < 1 and has a unique fixed point λ ˉ \bar{\lambda} λ ˉ . Set π ˉ = B ( λ ˉ ) \bar{\pi}=B(\bar{\lambda}) π ˉ = B ( λ ˉ ) . Combining the actor error bound with the delayed dual update gives, for t ≥ 1 t\ge1 t ≥ 1 ,
e t + 1 ≤ A 0 χ K t − 1 + A 1 ξ t + b ∣ λ t − λ ˉ ∣ ≤ q e t − 1 + A 0 χ K t − 1 + A 1 ξ t + b ζ t − 1 . (62) \begin{aligned}
e_{t+1}&\le A_0\chi^{K_t-1}+A_1\xi_t+b|\lambda_t-\bar{\lambda}|\\
&\le qe_{t-1}+A_0\chi^{K_t-1}+A_1\xi_t+b\zeta_{t-1}. \tag*{(62)}
\end{aligned} e t + 1 ≤ A 0 χ K t − 1 + A 1 ξ t + b ∣ λ t − λ ˉ ∣ ≤ q e t − 1 + A 0 χ K t − 1 + A 1 ξ t + b ζ t − 1 . (62)
Write h t = A 0 χ K t − 1 + A 1 ξ t + b ζ t − 1 h_t=A_0\chi^{K_t-1}+A_1\xi_t+b\zeta_{t-1} h t = A 0 χ K t − 1 + A 1 ξ t + b ζ t − 1 . Applying the recursion separately to even and odd subsequences yields
e 2 j ≤ q j e 0 + ∑ i = 1 j q j − i h 2 i − 1 , e 2 j + 1 ≤ q j e 1 + ∑ i = 1 j q j − i h 2 i . e_{2j}\le q^je_0+\sum_{i=1}^{j}q^{j-i}h_{2i-1},\qquad e_{2j+1}\le q^je_1+\sum_{i=1}^{j}q^{j-i}h_{2i}. e 2 j ≤ q j e 0 + i = 1 ∑ j q j − i h 2 i − 1 , e 2 j + 1 ≤ q j e 1 + i = 1 ∑ j q j − i h 2 i .
If K t → ∞ K_t\to\infty K t → ∞ and both estimation errors vanish, then h t → 0 h_t\to0 h t → 0 . Splitting each sum into a finite prefix and a uniformly small tail shows that e t → 0 e_t\to0 e t → 0 . If h t ≤ A 0 χ K − 1 + A 1 ξ + b ζ h_t\le A_0\chi^{K-1}+A_1\xi+b\zeta h t ≤ A 0 χ K − 1 + A 1 ξ + b ζ , summing the geometric series gives the policy bound in (16). Under the geometric-error assumption, the shifted error satisfies ζ t − 1 = O ( r t ) \zeta_{t-1}=O(r^t) ζ t − 1 = O ( r t ) because r > 0 r>0 r > 0 is fixed, so h t = O ( r t ) h_t=O(r^t) h t = O ( r t ) . The two parity sums are bounded by constant multiples of
∑ i = 1 j q j − i r 2 i = { r 2 ( q j − r 2 j ) q − r 2 , q ≠ r 2 , j r 2 j , q = r 2 . \sum_{i=1}^{j}q^{j-i}r^{2i}=
\begin{cases}
\dfrac{r^2(q^j-r^{2j})}{q-r^2},&q\ne r^2,\\
jr^{2j},&q=r^2.
\end{cases} i = 1 ∑ j q j − i r 2 i = ⎩ ⎨ ⎧ q − r 2 r 2 ( q j − r 2 j ) , j r 2 j , q = r 2 , q = r 2 .
Together with the initial-error terms, this gives e t = O ( ( max { q , r } ) t ) e_t=O((\max\{\sqrt{q},r\})^t) e t = O (( max { q , r } ) t ) when r ≠ q r\ne\sqrt{q} r = q , and e t = O ( ( t + 1 ) ( q ) t ) e_t=O((t+1)(\sqrt{q})^t) e t = O (( t + 1 ) ( q ) t ) when r = q r=\sqrt{q} r = q . Both bounds imply e t = O ( ν t ) e_t=O(\nu^t) e t = O ( ν t ) for every max { q , r } < ν < 1 \max\{\sqrt{q},r\}<\nu<1 max { q , r } < ν < 1 . Finally,
∣ λ t − λ ˉ ∣ ≤ ζ t − 1 + L Λ e t − 1 |\lambda_t-\bar{\lambda}|\le\zeta_{t-1}+L_{\Lambda}e_{t-1} ∣ λ t − λ ˉ ∣ ≤ ζ t − 1 + L Λ e t − 1
gives multiplier convergence, its asymptotic error bound, and (17) .
Fixed-Parameter Feasibility and Reward Bounds
We prove Proposition 4.2 for any fixed β , τ , L > 0 \beta,\tau,L>0 β , τ , L > 0 and any equilibrium satisfying exact actor and population-surrogate optimality. The proof uses bounded nonnegative costs, a strictly feasible reference policy, and actor best responses, and holds independently of the contraction condition. In the finite discounted setting, a valid objective bound is
U = R max + α log ∣ A ∣ 1 − γ . U=\frac{R_{\max}+\alpha\log|\mathcal{A}|}{1-\gamma}. U = 1 − γ R m a x + α log ∣ A ∣ .
A feasible reference policy and the problem bounds determine the value of this bound.
Proof. Write c = J c ( π ˉ ) c=J^{c}(\bar{\pi}) c = J c ( π ˉ ) , v = c − d v=c-d v = c − d , m = m π , τ ( λ ˉ ) m=m_{\pi,\tau}(\bar{\lambda}) m = m π , τ ( λ ˉ ) , and J = J α ( π ˉ ) J=J_{\alpha}(\bar{\pi}) J = J α ( π ˉ ) . Nonnegative bounded costs give 0 ≤ m ≤ C ˉ 0\le m\le\bar{C} 0 ≤ m ≤ C ˉ . Actor optimality against the strictly feasible policy yields
J − λ ˉ ( c − d ) ≥ J α ( π s ) − λ ˉ [ J c ( π s ) − d ] ≥ J α ( π s ) + λ ˉ σ . J-\bar{\lambda}(c-d)\ge J_{\alpha}(\pi_s)-\bar{\lambda}[J^{c}(\pi_s)-d]\ge J_{\alpha}(\pi_s)+\bar{\lambda}\sigma. J − λ ˉ ( c − d ) ≥ J α ( π s ) − λ ˉ [ J c ( π s ) − d ] ≥ J α ( π s ) + λ ˉ σ .
Since J ≤ U J\le U J ≤ U , it follows that
λ ˉ ( v + σ ) ≤ J − J α ( π s ) ≤ Δ . (63) \bar{\lambda}(v+\sigma)\le J-J_{\alpha}(\pi_s)\le\Delta. \tag*{(63)} λ ˉ ( v + σ ) ≤ J − J α ( π s ) ≤ Δ. (63)
The population surrogate derivative at the equilibrium is g ′ ( λ ˉ ) = − v − m + λ ˉ / β g'(\bar{\lambda})=-v-m+\bar{\lambda}/\beta g ′ ( λ ˉ ) = − v − m + λ ˉ / β . Its constrained optimality conditions are
{ − v − m ≥ 0 , λ ˉ = 0 , − v − m + λ ˉ / β = 0 , 0 < λ ˉ < L , − v − m + L / β ≤ 0 , λ ˉ = L . (64) \begin{cases}
-v-m\ge0, & \bar{\lambda}=0,\\
-v-m+\bar{\lambda}/\beta=0, & 0<\bar{\lambda}<L,\\
-v-m+L/\beta\le0, & \bar{\lambda}=L. \tag*{(64)}
\end{cases} ⎩ ⎨ ⎧ − v − m ≥ 0 , − v − m + λ ˉ / β = 0 , − v − m + L / β ≤ 0 , λ ˉ = 0 , 0 < λ ˉ < L , λ ˉ = L . (64)
Feasibility. If λ ˉ = 0 \bar{\lambda}=0 λ ˉ = 0 , then v ≤ − m ≤ 0 v\le-m\le0 v ≤ − m ≤ 0 . If 0 < λ ˉ < L 0<\bar{\lambda}<L 0 < λ ˉ < L and v > 0 v>0 v > 0 , the interior condition gives
v = λ ˉ / β − m ≤ λ ˉ / β . v=\bar{\lambda}/\beta-m\le\bar{\lambda}/\beta. v = λ ˉ / β − m ≤ λ ˉ / β .
Combining this inequality with (S37) yields
β v ( v + σ ) ≤ λ ˉ ( v + σ ) ≤ Δ , v ≤ σ 2 + 4 Δ / β − σ 2 . \beta v(v+\sigma)\le\bar{\lambda}(v+\sigma)\le\Delta,\qquad v\le\frac{\sqrt{\sigma^2+4\Delta/\beta}-\sigma}{2}. β v ( v + σ ) ≤ λ ˉ ( v + σ ) ≤ Δ , v ≤ 2 σ 2 + 4Δ/ β − σ .
If λ ˉ = L \bar{\lambda}=L λ ˉ = L , equation (S37) gives v ≤ Δ / L − σ v\le\Delta/L-\sigma v ≤ Δ/ L − σ . Taking positive parts and combining the three cases proves (18). When L ≥ Δ / σ L\ge\Delta/\sigma L ≥ Δ/ σ , the saturated-case violation bound is zero. The nonnegative root x x x of x ( x + σ ) = Δ / β x(x+\sigma)=\Delta/\beta x ( x + σ ) = Δ/ β satisfies x σ ≤ Δ / β x\sigma\le\Delta/\beta x σ ≤ Δ/ β , giving V β , L ≤ Δ / ( β σ ) V_{\beta,L}\le\Delta/(\beta\sigma) V β , L ≤ Δ/ ( β σ ) .
Regularized reward. Let π ⋆ \pi^\star π ⋆ maximize J α J_\alpha J α over feasible policies; this maximum exists by compactness and continuity. Actor optimality and J c ( π ⋆ ) ≤ d J^c(\pi^\star)\le d J c ( π ⋆ ) ≤ d imply
J − λ ˉ ( c − d ) ≥ J α ⋆ ( d ) − λ ˉ [ J c ( π ⋆ ) − d ] ≥ J α ⋆ ( d ) . J-\bar{\lambda}(c-d)\ge J_\alpha^\star(d)-\bar{\lambda}[J^c(\pi^\star)-d]\ge J_\alpha^\star(d). J − λ ˉ ( c − d ) ≥ J α ⋆ ( d ) − λ ˉ [ J c ( π ⋆ ) − d ] ≥ J α ⋆ ( d ) .
Hence J α ⋆ ( d ) − J ≤ λ ˉ ( d − c ) J_\alpha^\star(d)-J\le\bar{\lambda}(d-c) J α ⋆ ( d ) − J ≤ λ ˉ ( d − c ) . When λ ˉ = 0 \bar{\lambda}=0 λ ˉ = 0 , this gap is nonpositive. For an interior multiplier, d − c = m − λ ˉ / β d-c=m-\bar{\lambda}/\beta d − c = m − λ ˉ / β ; at the upper endpoint, g ′ ( L ) ≤ 0 g'(L)\le0 g ′ ( L ) ≤ 0 gives d − c ≤ m − L / β d-c\le m-L/\beta d − c ≤ m − L / β . In both cases,
J α ⋆ ( d ) − J ≤ λ ˉ m − λ ˉ 2 / β ≤ λ ˉ C ˉ − λ ˉ 2 / β = β C ˉ 2 4 − 1 β ( λ ˉ − β C ˉ 2 ) 2 ≤ β C ˉ 2 4 . \begin{aligned}
J_\alpha^\star(d)-J\le\bar{\lambda}m-\bar{\lambda}^2/\beta\\
&\le\bar{\lambda}\bar{C}-\bar{\lambda}^2/\beta\\
&=\frac{\beta\bar{C}^2}{4}-\frac{1}{\beta}\left(\bar{\lambda}-\frac{\beta\bar{C}}{2}\right)^2\le\frac{\beta\bar{C}^2}{4}.
\end{aligned} J α ⋆ ( d ) − J ≤ λ ˉ m − λ ˉ 2 / β ≤ λ ˉ C ˉ − λ ˉ 2 / β = 4 β C ˉ 2 − β 1 ( λ ˉ − 2 β C ˉ ) 2 ≤ 4 β C ˉ 2 .
The right-hand side is nonnegative, so taking the positive part proves (19). The violation bound uses strict feasibility; the reward bound follows from feasibility of the comparison optimum and the two best-response conditions.
Iteration errors. Under Theorem 4.1 and the strict-feasibility assumption of Proposition 4.2, the unique equilibrium obeys these bounds. Since the positive-part map is 1-Lipschitz,
[ J c ( π t ) − d ] + ≤ [ J c ( π ˉ ) − d ] + + K c ∥ π t − π ˉ ∥ F ≤ V β , L + K c ϵ t . (65) [J^c(\pi_t)-d]_+\le[J^c(\bar{\pi})-d]_++K_c\|\pi_t-\bar{\pi}\|_F\le V_{\beta,L}+K_c\epsilon_t. \tag*{(65)} [ J c ( π t ) − d ] + ≤ [ J c ( π ˉ ) − d ] + + K c ∥ π t − π ˉ ∥ F ≤ V β , L + K c ϵ t . (65)
Consequently, the uniform error conditions of that theorem imply
lim sup t → ∞ [ J c ( π t ) − d ] + ≤ V β , L + K c ε K , ξ , ζ . (66) \limsup_{t\to\infty}[J^c(\pi_t)-d]_+\le V_{\beta,L}+K_c\varepsilon_{K,\xi,\zeta}. \tag*{(66)} t → ∞ lim sup [ J c ( π t ) − d ] + ≤ V β , L + K c ε K , ξ , ζ . (66)
The bound combines the equilibrium term V β , L V_{\beta,L} V β , L with actor, critic, and dual approximation errors. If these errors vanish as specified in Theorem 4.1, the asymptotic feasibility bound reduces to V β , L V_{\beta,L} V β , L , and continuity of J α J_\alpha J α gives
lim sup t → ∞ [ J α c ( d ˉ ) − J α ( π t ) ] + ≤ β C ˉ 2 4 . \limsup_{t\to\infty}\left[J^c_\alpha(\bar d)-J_\alpha(\pi_t)\right]_+ \le\frac{\beta\bar C^2}{4}. t → ∞ lim sup [ J α c ( d ˉ ) − J α ( π t ) ] + ≤ 4 β C ˉ 2 .
Parameter interpretation. An interior equilibrium satisfies J c ( π ˉ ) − d = λ ˉ / β − m J^c(\bar\pi)-d=\bar\lambda/\beta-m J c ( π ˉ ) − d = λ ˉ / β − m . Increasing β \beta β tightens the interior violation bound and increases the reward bound and response gain q = b β ( K c + K m ) q=b\beta(K_c+K_m) q = b β ( K c + K m ) . Proposition 4.2 applies to any exact equilibrium with positive fixed parameters; the iterative bounds additionally use q < 1 q<1 q < 1 and the approximation assumptions of Theorem 4.1.
Numerical evaluation uses the strict-feasibility margin σ \sigma σ , objective bound U U U , and tabular response constants. The neural experiments evaluate β = 0.1 \beta=0.1 β = 0.1 , τ = 1 \tau=1 τ = 1 , and L = 10 L=10 L = 10 empirically. Corollary 4.3 identifies the parameter matching that recovers an entropy-regularized CMDP saddle point.
Proof of Corollary 4.3
Proof. Since costs are nonnegative and J c ( π α ∗ ) = d > 0 J^c(\pi^*_\alpha)=d>0 J c ( π α ∗ ) = d > 0 , the weighted cost m π α ∗ , τ ( λ α ∗ ) m_{\pi^*_\alpha,\tau}(\lambda^*_\alpha) m π α ∗ , τ ( λ α ∗ ) is positive. Parameter matching (20) gives
g π α ∗ , β , τ ′ ( λ α ∗ ) = − m π α ∗ , τ ( λ α ∗ ) + λ α ∗ / β = 0. g'_{\pi^*_\alpha,\beta,\tau}(\lambda^*_\alpha)=-m_{\pi^*_\alpha,\tau}(\lambda^*_\alpha)+\lambda^*_\alpha/\beta=0. g π α ∗ , β , τ ′ ( λ α ∗ ) = − m π α ∗ , τ ( λ α ∗ ) + λ α ∗ / β = 0.
Strong convexity and the interior multiplier yield Λ β , τ ( π α ∗ ) = λ α ∗ \Lambda_{\beta,\tau}(\pi^*_\alpha)=\lambda^*_\alpha Λ β , τ ( π α ∗ ) = λ α ∗ . The saddle-point condition gives B ( λ α ∗ ) = π α ∗ B(\lambda^*_\alpha)=\pi^*_\alpha B ( λ α ∗ ) = π α ∗ . Uniqueness in Theorem 4.1 identifies the equilibrium with this saddle point. The cost Lipschitz bound then gives
[ J c ( π t ) − d ] + ≤ ∣ J c ( π t ) − J c ( π α ∗ ) ∣ ≤ K c e t . \left[J^c(\pi_t)-d\right]_+ \le\left|J^c(\pi_t)-J^c(\pi^*_\alpha)\right| \le K_c e_t. [ J c ( π t ) − d ] + ≤ ∣ J c ( π t ) − J c ( π α ∗ ) ∣ ≤ K c e t .
The convergence and error-floor conclusions follow from Theorem 4.1. Continuity of J α J_\alpha J α gives convergence of the entropy-regularized objective when e t → 0 e_t\to0 e t → 0 .
PPO and SAC Implementations
Related safe RL methods also pair analyses under explicit structural assumptions with neural implementations. Chen et al. [4 ] assume Lipschitz gradients and strong convexity of the Lagrangian in actor parameters, and evaluate PPO-Lagrangian and DDPG-Lagrangian variants on Bullet-Safety-Gym. CVPO [34 ] establishes optimality of its nonparametric variational E-step and fits a neural policy in the M-step. CRPO [35 ] analyzes both tabular policies and, under additional assumptions, two-layer neural-network approximation.
Algorithm S1 gives the general framework; Algorithms S2 and S3 give its PPO-SDLA and SAC-SDLA implementations.
Algorithm S1 SDLA (General Framework)
Input: Base RL algorithm, hyperparameters τ \tau τ , β \beta β , d d d , λ max \lambda_{\max} λ m a x
Initialize: π θ \pi_\theta π θ , critics Q ϕ r r Q_{\phi_r}^{r} Q ϕ r r , Q ϕ c c Q_{\phi_c}^{c} Q ϕ c c , λ = 0 \lambda= 0 λ = 0
for each iteration do
Run π θ \pi_\theta π θ , collect T \mathcal{T} T , compute { R i , C i } i = 1 M \{R_i,C_i\}_{i=1}^{M} { R i , C i } i = 1 M and c ^ M \hat{c}_M c ^ M
Q ϕ r r , Q ϕ c c ← UpdateCritics ( T ) Q_{\phi_r}^{r}, Q_{\phi_c}^{c} \leftarrow\operatorname{UpdateCritics}(\mathcal{T}) Q ϕ r r , Q ϕ c c ← UpdateCritics ( T )
π θ ← UpdateActor ( Q ϕ r r − λ Q ϕ c c ) \pi_\theta\leftarrow\operatorname{UpdateActor}(Q_{\phi_r}^{r}-\lambda Q_{\phi_c}^{c}) π θ ← UpdateActor ( Q ϕ r r − λ Q ϕ c c )
// Dual update with the fixed trajectory batch
Define F ^ M \widehat{F}_M F M by (21)
Define g ^ M \widehat{g}_M g M by (22)
λ ← TernarySearch 15 ( g ^ M , [ 0 , λ max ] ) \lambda\leftarrow\operatorname{TernarySearch}_{15}(\widehat{g}_M,[0,\lambda_{\max}]) λ ← TernarySearch 15 ( g M , [ 0 , λ m a x ])
end for
Algorithm S2 PPO-SDLA
Initialize policy π θ \pi_\theta π θ , reward value V ϕ r r V_{\phi_r}^{r} V ϕ r r , cost value V ϕ c c V_{\phi_c}^{c} V ϕ c c , and dual variable λ = 0 \lambda= 0 λ = 0 .
Hyperparameters: cost limit d d d , dual temperature τ \tau τ , regularization β \beta β , dual cap λ max \lambda_{\max} λ m a x .
for each iteration do
Run the current policy π θ \pi_\theta π θ for M M M trajectories and collect
T = { ξ i } i = 1 M . \mathcal{T} = \{\xi_i\}_{i=1}^{M}. T = { ξ i } i = 1 M .
Compute trajectory-wise discounted reward and cost returns:
R i = ∑ t ≥ 0 γ t r ( s t i , a t i ) , C i = ∑ t ≥ 0 γ t c ( s t i , a t i ) . R_i = \sum_{t\ge0}\gamma^t r(s_t^i,a_t^i), \qquad C_i = \sum_{t\ge0}\gamma^t c(s_t^i,a_t^i). R i = t ≥ 0 ∑ γ t r ( s t i , a t i ) , C i = t ≥ 0 ∑ γ t c ( s t i , a t i ) .
Estimate current policy cost:
c ^ M = 1 M ∑ i = 1 M C i . \hat{c}_M = \frac{1}{M}\sum_{i=1}^{M} C_i. c ^ M = M 1 i = 1 ∑ M C i .
Compute reward and cost advantages A ^ t r , A ^ t c \hat{A}_t^r,\hat{A}_t^c A ^ t r , A ^ t c using GAE.
Update V ϕ r r , V ϕ c c V_{\phi_r}^{r},V_{\phi_c}^{c} V ϕ r r , V ϕ c c by value regression.
Update actor by PPO using the Lagrangian advantage
A ^ t λ = A ^ t r − λ A ^ t c . \hat{A}_t^\lambda= \hat{A}_t^r-\lambda\hat{A}_t^c. A ^ t λ = A ^ t r − λ A ^ t c .
Dual update. For any candidate λ ′ ∈ [ 0 , λ max ] \lambda' \in[0,\lambda_{\max}] λ ′ ∈ [ 0 , λ m a x ] , compute
F ^ M ( λ ′ ) = τ log ( 1 M ∑ i = 1 M exp ( R i − λ ′ C i τ ) ) . \widehat{F}_M(\lambda') = \tau\log\left(\frac{1}{M}\sum_{i=1}^{M}\exp\left(\frac{R_i-\lambda'C_i}{\tau}\right)\right). F M ( λ ′ ) = τ log ( M 1 i = 1 ∑ M exp ( τ R i − λ ′ C i ) ) .
Define the trajectory-wise empirical surrogate dual
g ^ M ( λ ′ ) = F ^ M ( λ ′ ) + λ ′ ( d − c ^ M ) + ( λ ′ ) 2 2 β . \widehat{g}_M(\lambda') = \widehat{F}_M(\lambda')+\lambda'(d-\hat{c}_M)+\frac{(\lambda')^2}{2\beta}. g M ( λ ′ ) = F M ( λ ′ ) + λ ′ ( d − c ^ M ) + 2 β ( λ ′ ) 2 .
Update dual variable by K = 15 K=15 K = 15 ternary-search iterations:
λ ← TernarySearch 15 ( g ^ M , [ 0 , λ max ] ) . \lambda\leftarrow\operatorname{TernarySearch}_{15}(\widehat{g}_M,[0,\lambda_{\max}]). λ ← TernarySearch 15 ( g M , [ 0 , λ m a x ]) .
end for
Output π θ \pi_\theta π θ .
Algorithm S3 SAC-SDLA
Initialize: Policy π θ \pi_\theta π θ , Q-functions Q ϕ r , 1 r , Q ϕ r , 2 r , Q ϕ c , 1 c , Q ϕ c , 2 c Q^r_{\phi_{r,1}}, Q^r_{\phi_{r,2}}, Q^c_{\phi_{c,1}}, Q^c_{\phi_{c,2}} Q ϕ r , 1 r , Q ϕ r , 2 r , Q ϕ c , 1 c , Q ϕ c , 2 c , target networks Q ˉ ϕ ˉ r , 1 r , Q ˉ ϕ ˉ r , 2 r , Q ˉ ϕ ˉ c , 1 c , Q ˉ ϕ ˉ c , 2 c \bar{Q}^r_{\bar{\phi}_{r,1}}, \bar{Q}^r_{\bar{\phi}_{r,2}}, \bar{Q}^c_{\bar{\phi}_{c,1}}, \bar{Q}^c_{\bar{\phi}_{c,2}} Q ˉ ϕ ˉ r , 1 r , Q ˉ ϕ ˉ r , 2 r , Q ˉ ϕ ˉ c , 1 c , Q ˉ ϕ ˉ c , 2 c , replay buffer B \mathcal{B} B , λ = 0 \lambda= 0 λ = 0 .
Hyperparameters: dual temperature τ \tau τ , regularization β \beta β , cost limit d d d , dual cap λ max \lambda_{\max} λ m a x , SAC temperature α \alpha α , target update rate τ P o l y a k \tau_{\mathrm{Polyak}} τ Polyak .
for each iteration do
Run π θ \pi_\theta π θ in the environment, add transitions ( s , a , r , c , s ′ ) (s,a,r,c,s') ( s , a , r , c , s ′ ) to B \mathcal{B} B .
From recent rollout/evaluation episodes, compute trajectory-wise discounted returns
R i = ∑ t ≥ 0 γ t r i t , C i = ∑ t ≥ 0 γ t c i t , i = 1 , … , M . R_i = \sum_{t \ge0} \gamma^t r^t_i,\qquad C_i = \sum_{t \ge0} \gamma^t c^t_i,\qquad i = 1,\ldots,M. R i = t ≥ 0 ∑ γ t r i t , C i = t ≥ 0 ∑ γ t c i t , i = 1 , … , M .
Estimate current policy cost:
c ^ M = 1 M ∑ i = 1 M C i . \hat{c}_M = \frac{1}{M}\sum_{i=1}^{M} C_i. c ^ M = M 1 i = 1 ∑ M C i .
// SAC critic and actor updates
for gradient step g = 1 , … , N g r a d g = 1,\ldots,N_{\mathrm{grad}} g = 1 , … , N grad do
Sample mini-batch { ( s i , a i , r i , c i , s i ′ ) } i = 1 B \{(s_i,a_i,r_i,c_i,s'_i)\}_{i=1}^{B} {( s i , a i , r i , c i , s i ′ ) } i = 1 B from B \mathcal{B} B .
Sample next actions a i ′ ∼ π θ ( ⋅ ∣ s i ′ ) a'_i \sim\pi_\theta(\cdot|s'_i) a i ′ ∼ π θ ( ⋅ ∣ s i ′ ) .
11.
y i r ← r i + γ [ min j = 1 , 2 Q ˉ ϕ ˉ r , j r ( s i ′ , a i ′ ) − α log π θ ( a i ′ ∣ s i ′ ) ] . y^r_i \leftarrow r_i + \gamma\left[\min_{j=1,2}\bar{Q}^r_{\bar{\phi}_{r,j}}(s'_i,a'_i)-\alpha\log\pi_\theta(a'_i|s'_i)\right]. y i r ← r i + γ [ j = 1 , 2 min Q ˉ ϕ ˉ r , j r ( s i ′ , a i ′ ) − α log π θ ( a i ′ ∣ s i ′ ) ] .
12.
y i c ← c i + γ min j = 1 , 2 Q ˉ ϕ ˉ c , j c ( s i ′ , a i ′ ) . y^c_i \leftarrow c_i + \gamma\min_{j=1,2}\bar{Q}^c_{\bar{\phi}_{c,j}}(s'_i,a'_i). y i c ← c i + γ j = 1 , 2 min Q ˉ ϕ ˉ c , j c ( s i ′ , a i ′ ) .
Update Q ϕ r , 1 r , Q ϕ r , 2 r , Q ϕ c , 1 c , Q ϕ c , 2 c Q^r_{\phi_{r,1}}, Q^r_{\phi_{r,2}}, Q^c_{\phi_{c,1}}, Q^c_{\phi_{c,2}} Q ϕ r , 1 r , Q ϕ r , 2 r , Q ϕ c , 1 c , Q ϕ c , 2 c by minimizing TD losses.
Sample actions a ~ i ∼ π θ ( ⋅ ∣ s i ) \tilde{a}_i \sim\pi_\theta(\cdot|s_i) a ~ i ∼ π θ ( ⋅ ∣ s i ) .
Define
Q ^ r ( s i , a ~ i ) = min j = 1 , 2 Q ϕ r , j r ( s i , a ~ i ) , Q ^ c ( s i , a ~ i ) = min j = 1 , 2 Q ϕ c , j c ( s i , a ~ i ) . \hat{Q}^r(s_i,\tilde{a}_i)=\min_{j=1,2}Q^r_{\phi_{r,j}}(s_i,\tilde{a}_i),\qquad
\hat{Q}^c(s_i,\tilde{a}_i)=\min_{j=1,2}Q^c_{\phi_{c,j}}(s_i,\tilde{a}_i). Q ^ r ( s i , a ~ i ) = j = 1 , 2 min Q ϕ r , j r ( s i , a ~ i ) , Q ^ c ( s i , a ~ i ) = j = 1 , 2 min Q ϕ c , j c ( s i , a ~ i ) .
Update actor by minimizing
L π = 1 B ∑ i = 1 B [ α log π θ ( a ~ i ∣ s i ) − Q ^ r ( s i , a ~ i ) + λ Q ^ c ( s i , a ~ i ) ] . L_\pi= \frac{1}{B}\sum_{i=1}^{B}\left[\alpha\log\pi_\theta(\tilde{a}_i|s_i)-\hat{Q}^r(s_i,\tilde{a}_i)+\lambda\hat{Q}^c(s_i,\tilde{a}_i)\right]. L π = B 1 i = 1 ∑ B [ α log π θ ( a ~ i ∣ s i ) − Q ^ r ( s i , a ~ i ) + λ Q ^ c ( s i , a ~ i ) ] .
Update target networks by Polyak averaging.
end for
// Dual update via trajectory-wise empirical surrogate
For any candidate λ ′ ∈ [ 0 , λ max ] \lambda' \in[0,\lambda_{\max}] λ ′ ∈ [ 0 , λ m a x ] , compute
F ^ M ( λ ′ ) = τ log ( 1 M ∑ i = 1 M exp ( R i − λ ′ C i τ ) ) . \hat{F}_M(\lambda')=\tau\log\left(\frac{1}{M}\sum_{i=1}^{M}\exp\left(\frac{R_i-\lambda'C_i}{\tau}\right)\right). F ^ M ( λ ′ ) = τ log ( M 1 i = 1 ∑ M exp ( τ R i − λ ′ C i ) ) .
Define the trajectory-wise empirical surrogate dual
g ^ M ( λ ′ ) = F ^ M ( λ ′ ) + λ ′ ( d − c ^ M ) + ( λ ′ ) 2 2 β . \hat{g}_M(\lambda')=\hat{F}_M(\lambda')+\lambda'(d-\hat{c}_M)+\frac{(\lambda')^2}{2\beta}. g ^ M ( λ ′ ) = F ^ M ( λ ′ ) + λ ′ ( d − c ^ M ) + 2 β ( λ ′ ) 2 .
Update dual variable by K = 15 K=15 K = 15 ternary-search iterations:
λ ← TernarySearch 15 ( g ^ M , [ 0 , λ max ] ) . \lambda\leftarrow\operatorname{TernarySearch}_{15}(\hat{g}_M,[0,\lambda_{\max}]). λ ← TernarySearch 15 ( g ^ M , [ 0 , λ m a x ]) .
end for
Output: Policy π θ \pi_\theta π θ .
Scalar Solver Complexity
The empirical surrogate g ^ M \widehat{g}_M g M is strictly convex on [ 0 , λ max ] [0,\lambda_{\max}] [ 0 , λ m a x ] , admitting a unique minimum. For single-constraint CMDPs, ternary search computes the multiplier without a dual learning rate. Each ternary-search iteration retains an interval containing the minimizer and reduces its length by a factor 2 / 3 2/3 2/3 . Starting from [ 0 , λ max ] [0,\lambda_{\max}] [ 0 , λ m a x ] , after K K K iterations its width is λ max ( 2 / 3 ) K \lambda_{\max}(2/3)^K λ m a x ( 2/3 ) K . Thus K = ⌈ log ( λ max / ε λ ) log ( 3 / 2 ) ⌉ K = \left\lceil\frac{\log(\lambda_{\max}/\varepsilon_\lambda)}{\log(3/2)} \right\rceil K = ⌈ l o g ( 3/2 ) l o g ( λ m a x / ε λ ) ⌉ iterations suffice for multiplier error at most ε λ \varepsilon_\lambda ε λ , for 0 < ε λ < λ max 0 < \varepsilon_\lambda< \lambda_{\max} 0 < ε λ < λ m a x , using two objective evaluations per iteration. We use K = 15 K = 15 K = 15 in practice, giving a final interval width of λ max ( 2 / 3 ) 15 \lambda_{\max}(2/3)^{15} λ m a x ( 2/3 ) 15 . Each empirical objective evaluation costs O ( M ) O(M) O ( M ) for a fixed batch of M M M trajectories, giving O ( M log ( λ max / ε λ ) ) O(M \log(\lambda_{\max}/\varepsilon_\lambda)) O ( M log ( λ m a x / ε λ )) arithmetic operations. In practice, log-sum-exp is evaluated after subtracting the largest trajectory score to avoid numerical overflow.
HASARD results use five SDLA runs per setting and three archived runs per baseline, except PPOCost on Volcanic Venture L1, for which the archive contains one run. The HASARD learning curves below show one standard deviation across the available runs for each method.
Regularization Ablation
Component objectives. Equations (24) –(26) define the three PPO ablations using the same empirical trajectory objective F ^ M \widehat{F}_M F M as SDLA. Their derivatives are
g ^ E = d − m ^ ( λ ) , g ^ Q R = d − m ^ ( λ ) + λ / β , g ^ Q R − d / 2 = d / 2 − m ^ ( λ ) + λ / β . \widehat{g}_{\mathrm{E}} = d-\widehat{m}(\lambda), \qquad\widehat{g}_{\mathrm{QR}} = d-\widehat{m}(\lambda)+\lambda/\beta, \qquad\widehat{g}_{\mathrm{QR}-d/2} = d/2-\widehat{m}(\lambda)+\lambda/\beta. g E = d − m ( λ ) , g QR = d − m ( λ ) + λ / β , g QR − d /2 = d /2 − m ( λ ) + λ / β .
SDLA has derivative d − c ^ M − m ^ ( λ ) + λ / β d-\widehat{c}_M-\widehat{m}(\lambda)+\lambda/\beta d − c M − m ( λ ) + λ / β . Thus PPO-QR here retains trajectory log-sum-exp weighting; the quadratic-regularized linear multiplier objective discussed in § 2 uses the mean cost alone.
The fixed-center and adaptive-center configurations also differ in multiplier updates. Define ∣ Δ λ t ∣ = ∣ λ t + 1 − λ t ∣ |\Delta\lambda_t|=|\lambda_{t+1}-\lambda_t| ∣Δ λ t ∣ = ∣ λ t + 1 − λ t ∣ between consecutive logged values. Relative to PPO-QR-d / 2 d/2 d /2 , PPO-SDLA changes the mean update from 0.0849 to 0.0865, an increase of 1.9%, while reducing its 95th percentile from 0.4219 to 0.3576, a reduction of 15.2%.
Figure S1 shows reward, cost, and multiplier trajectories on Ant and Swimmer. The Ant runs reproduce main Table 6 ; the Swimmer SDLA runs reproduce its reward and cost in main Table 4 .
Table 6. Adaptive feedback versus fixed early penalization on Ant and Swimmer (d = 25 d = 25 d = 25 ; five runs per method). Entries report mean ± \pm ± standard deviation. PPO-QR-d / 2 d/2 d /2 uses β = 0.2 \beta= 0.2 β = 0.2 versus SDLA’s β = 0.1 \beta= 0.1 β = 0.1 , matching their constant-acceleration threshold and response slope. Violation % is the fraction of logged updates exceeding the cost limit.
Figure S1. Reward, cost, and logged multiplier trajectories on Ant (top) and Swimmer (bottom). Lines show means over five distinct seeds per method and environment; shading shows one standard deviation, clipped at zero for cost and λ \lambda λ . Curves use all 500 logged points without temporal smoothing. Dashed cost lines mark d = 25 d=25 d = 25 . Swimmer uses τ = 1 \tau=1 τ = 1 , with β = 10 \beta=10 β = 10 for PPO-QR, β = 0.1 \beta=0.1 β = 0.1 for SDLA, and β = 0.2 \beta=0.2 β = 0.2 for PPO-QR-d / 2 d/2 d /2 .
Regularization sweep. Table S2 reports the full regularization sweep. The default β = 0.1 \beta=0.1 β = 0.1 gives the smallest mean multiplier change, while all tested settings have final mean costs below the budget.
Temperature Ablation
Table S3 compares the default τ = 1 \tau=1 τ = 1 with τ = 1.5 \tau=1.5 τ = 1.5 and τ = 2 \tau=2 τ = 2 on SafetyAntVelocity-v1. All three settings have mean costs below the budget of 25. The default gives the highest reported mean reward, with τ = 1.5 \tau=1.5 τ = 1.5 close in mean reward. Mean ∣ Δ λ ∣ |\Delta\lambda| ∣Δ λ ∣ is 0.0865, 0.08649, and 0.08890, respectively.
Table S3. Temperature ablation on SafetyAntVelocity-v1 with d = 25 d = 25 d = 25 and the default β = 0.1 \beta= 0.1 β = 0.1 . Entries report mean ± \pm ± standard deviation. Mean ∣ Δ λ ∣ |\Delta\lambda| ∣Δ λ ∣ reports the average absolute change between consecutive logged multipliers. Bold marks the highest mean reward.
Learning Curves on Safety-Gym Velocity Tasks
Figure S2 reports PPO-SDLA learning curves; Figure S4 reports the SAC-SDLA counterpart.
We integrate SDLA with SAC and evaluate it on Safety-Gym velocity tasks. Figure S4 presents the reward, cost, and Lagrange multiplier trajectories, respectively.
Additional Comparisons and Training Diagnostics
Constraint Tracking during Training
We compare PPO-SDLA with PPOLag on the Ant and Walker2d velocity tasks using complete training logs. PPOLag was rerun with multiplier logging for this comparison. Let c t l o g c_t^{\mathrm{log}} c t log denote the logged episode cost and let T T T be the number of logged updates. We report the violation rate, average overshoot, and constraint-boundary crossing rate:
Violation ( % ) = 100 T ∑ t = 1 T 1 { c t l o g > d } , Overshoot = 1 T ∑ t = 1 T [ c t l o g − d ] + , \operatorname{Violation}(\%) = \frac{100}{T}\sum_{t=1}^{T} \mathbf{1}\{c_t^{\mathrm{log}} > d\}, \qquad\operatorname{Overshoot} = \frac{1}{T}\sum_{t=1}^{T}[c_t^{\mathrm{log}} - d]_+, Violation ( % ) = T 100 t = 1 ∑ T 1 { c t log > d } , Overshoot = T 1 t = 1 ∑ T [ c t log − d ] + ,
CrossRate ( % ) = 100 T − 1 ∑ t = 1 T − 1 1 { ( c t l o g − d ) ( c t + 1 l o g − d ) < 0 } . \operatorname{CrossRate}(\%) = \frac{100}{T-1}\sum_{t=1}^{T-1}\mathbf{1}\{(c_t^{\mathrm{log}} - d)(c_{t+1}^{\mathrm{log}} - d) < 0\}. CrossRate ( % ) = T − 1 100 t = 1 ∑ T − 1 1 {( c t log − d ) ( c t + 1 log − d ) < 0 } .
Table 5 in the main paper reports these summaries over the full logged training horizon; Figure S3 presents the same values graphically.
Table 5. Training-time constraint tracking with d = 25 d = 25 d = 25 . All statistics use the complete training logs. Violation and CrossRate are percentages; overshoot is averaged over all logged updates, including those below the budget.
Figure S3. Full-training constraint tracking on Ant and Walker2d, using the values in main Table 5 . Points show means and error bars show one standard deviation. Panels report mean absolute multiplier change, violation rate, average overshoot, and constraint-boundary crossing rate. The cost budget is d = 25 d = 25 d = 25 ; overshoot includes all logged updates.
Wall-Clock Time
On SafetyAntVelocity with a single NVIDIA RTX 4090 (24 GB), stable-training epochs take 23.58 seconds for PPO-SDLA versus 23.22 for PPOLag. Runs take approximately 3.28 versus 3.23 GPU-hours, a 1.5% increase.
Multiplier Cap
The same λ max = 10 \lambda_{\max} = 10 λ m a x = 10 is used across tasks. We measure near-cap frequency by
NearCapRate ( % ) = 100 T ∑ t = 1 T 1 { λ t ≥ 0.95 λ max } . \operatorname{NearCapRate}(\%) = \frac{100}{T}\sum_{t=1}^{T}\mathbf{1}\{\lambda_t \ge0.95\lambda_{\max}\}. NearCapRate ( % ) = T 100 t = 1 ∑ T 1 { λ t ≥ 0.95 λ m a x } .
Table S4 shows that the logged multiplier stays below this region on four tasks and enters it for 2.4% of updates on Swimmer.
Table S4. Fraction of logged PPO-SDLA updates with λ t ≥ 0.95 λ max \lambda_t \ge0.95\lambda_{\max} λ t ≥ 0.95 λ m a x , using λ max = 10 \lambda_{\max} = 10 λ m a x = 10 .
Evaluation on HASARD Benchmark
We evaluate PPO-SDLA on the HASARD benchmark across three difficulty levels (L1–L3) and six scenarios: Armament Burden, Volcanic Venture, Remedy Rush, Collateral Damage, Precipice Plunge, and Detonator’s Dilemma. Learning curves are presented in Figure S5 –Figure S10 . Lines show mean training episode aggregates and shaded regions show one standard deviation across runs. For PPOCost, the logged cost penalty is added back to the logged reward to recover task reward, as in the tables. The plots compare PPO-SDLA, PPOLag, PPOCost, PPOPID, and PPOSaute; the tables additionally report PPO and P3O.
Figure S5. Learning curves on HASARD Level 1 (Part 1): Armament Burden, Volcanic Venture, Remedy Rush.
Figure S10. Learning curves on HASARD Level 3 (Part 2): Collateral Damage, Precipice Plunge, Detonator’s Dilemma.
Table 3 compares terminal PPO-SDLA summaries with human averages over 10 episodes.
Figure S6. Learning curves on HASARD Level 1 (Part 2): Collateral Damage, Precipice Plunge, Detonator’s Dilemma.
Figure S7. Learning curves on HASARD Level 2 (Part 1): Armament Burden, Volcanic Venture, Remedy Rush.
Figure S8. Learning curves on HASARD Level 2 (Part 2): Collateral Damage, Precipice Plunge, Detonator’s Dilemma.
Figure S9. Learning curves on HASARD Level 3 (Part 1): Armament Burden, Volcanic Venture, Remedy Rush.
Extended Discussion of Related Methods
Primal-Dual Approach
The standard primal-dual approach forms the Lagrangian L ( π , λ ) = J r ( π ) − λ ( J c ( π ) − d ) \mathcal{L}(\pi,\lambda) = J^{r}(\pi) - \lambda(J^{c}(\pi) - d) L ( π , λ ) = J r ( π ) − λ ( J c ( π ) − d ) and solves min λ ≥ 0 max π L ( π , λ ) \min_{\lambda\ge0}\max_{\pi}\mathcal{L}(\pi,\lambda) min λ ≥ 0 max π L ( π , λ ) via gradient descent-ascent (GDA) [3 ] , [4 ] , [5 ] :
π ← π + η π ∇ π L ( π , λ ) , λ ← [ λ + η λ ( J c ( π ) − d ) ] + . \pi\leftarrow\pi+ \eta_{\pi}\nabla_{\pi}\mathcal{L}(\pi,\lambda), \qquad\lambda\leftarrow[\lambda+ \eta_{\lambda}(J^{c}(\pi)-d)]_{+}. π ← π + η π ∇ π L ( π , λ ) , λ ← [ λ + η λ ( J c ( π ) − d ) ] + .
GDA on minimax problems can exhibit slow progress and sensitivity to the relative primal and dual stepsizes [11 ] . Oscillation is also commonly observed near the constraint boundary [6 ] .
Stabilizing Multiplier Updates
Several methods stabilize λ \lambda λ updates within the primal–dual structure. Stooke et al. [6 ] interpret gradient multiplier updates as integral control and introduce proportional and derivative feedback. Their continuous-time analysis explains how the proportional term adds damping, while the derivative term uses cost trends to anticipate constraint violations. Tuned controller gains set the strength of each feedback term. Gradient and PID methods specify how the multiplier evolves from cost errors and their history. SDLA derives a response from a regularized scalar objective on the current trajectory batch, with explicit activation conditions and response-gain bounds.
Dai et al. [12 ] add a quadratic penalty term σ 2 ( J c − d ) + 2 \frac{\sigma}{2}(J^{c}-d)_{+}^{2} 2 σ ( J c − d ) + 2 to the Lagrangian. CAL [13 ] calibrates the cost critic in off-policy learning.
Recent works have also explored regularization-based approaches for stable primal-dual updates in CMDPs. [14 ] propose RPG-PD, which combines entropy regularization on the policy with quadratic regularization on the dual variable, achieving sublinear last-iterate convergence via single-time-scale GDA. [15 ] propose C-PG, a general framework with dual-variable regularization that achieves global last-iterate convergence under weak gradient domination assumptions. SDLA constructs its regularized dual objective from a frozen trajectory batch and current policy cost information, then computes the response with a scalar inner solve. This dual update retains the PPO and SAC actor update rules.
Penalty, State-Augmentation, and Projection Methods
Penalty-based alternatives include PPOCost [36 ] , which uses r ~ = r − β ′ c \tilde{r}=r-\beta^{\prime}c r ~ = r − β ′ c with a fixed coefficient, and P3O [16 ] . The penalty strength controls the reward–cost tradeoff. P3O establishes exactness for a sufficiently large finite coefficient and uses a sample approximation in its practical surrogate [16 ] .
State augmentation methods transform the CMDP into an unconstrained problem. SAUTE RL [21 ] augments the state with a safety budget z t z_t z t , and SIMMER [22 ] extends this with budget scheduling. The resulting policy takes budget-conditioned inputs and optimizes a reshaped objective; SIMMER also schedules the budget.
Constrained and projected policy methods modify the actor update directly. CPO [17 ] and PCPO [18 ] use local constraint and KL approximations, with second-order computations in their practical updates. FOCOPS [19 ] and CUP [20 ] implement policy projection with first-order updates.
Acknowledgments
OpenAI ChatGPT/Codex assisted with draft polishing. The authors take responsibility for the final manuscript.