Lyapunov-Based Safe Policy Improvement for CMDPs

Positioning: Why the problem matters

In robotics, autonomous systems, process control, energy operation, and supply-chain control under uncertainty, a policy cannot be judged only by reward or operating cost. A controller may improve throughput while accumulating thermal exposure, unsafe transitions, resource shortage, or reliability risk beyond an acceptable budget. Recommendation systems have an analogous issue when repeated actions can accumulate undesirable long-run effects.

Ordinary reinforcement learning optimizes an expected cumulative objective. A constrained Markov decision process (CMDP) instead asks for a good policy among policies that also control expected cumulative constraint cost. In cost-minimization form, the safety condition is

D^{π} (x_{0}) \leq d_{0}

where $D^{π} (x_{0})$ is the expected cumulative constraint cost from initial state $x_{0}$ under policy $π$ , and $d_{0}$ is the permitted budget. This is a trajectory-level expectation constraint: it controls cumulative safety burden over an episode, not merely whether each individual action passes a one-step rule.

Problem setting

Let $c (x, a)$ denote an objective stage cost and $d (x, a)$ a constraint stage cost. For an episodic CMDP, the objective is to choose $π$ so that

\begin{aligned} minimize over π & C^{π} (x_{0}) = E_{π} [\sum_{t} c (x_{t}, a_{t}) | x_{0}] \\ subject to & D^{π} (x_{0}) = E_{π} [\sum_{t} d (x_{t}, a_{t}) | x_{0}] \leq d_{0} \end{aligned}

The distinction between $C^{π}$ and $D^{π}$ matters. Performance can be traded against other performance terms, but a feasibility-critical budget should not be silently spent simply because a reward improvement is large. Equally, the CMDP statement is not pathwise safety: an expected bound alone does not rule out every unsafe realized trajectory.

Prior research gap

Before the Lyapunov formulation, several approaches exposed a tension between tractability and safety during learning.

Lagrangian CMDPs penalize constraint cost with a multiplier. This is mathematically natural, but multiplier adaptation may pass through policies that violate the original budget, and primal-dual learning can be unstable.
Occupation-measure or dual LP formulations give an elegant global solution for finite CMDPs with known dynamics. They become expensive in large state-action spaces and awkward when the transition model is unknown.
Step-wise surrogate constraints can prevent immediate excess use of budget, but dividing a global allowance uniformly across time is often conservative: a harmless early expenditure may be rejected even when future behavior compensates.
Supermartingale or conservative surrogate methods can preserve a safety condition, while potentially shrinking the feasible policy set enough to harm useful improvement.
CPO/TRPO-style constrained optimization is designed for scalable policy updates, but does not provide the same direct policy-iteration interpretation for arbitrary RL algorithms.

The central question is therefore whether cumulative feasibility can be expressed as local admissibility tests that retain a feasible baseline while still allowing policy improvement.

Core idea

The method replaces the global expected cumulative constraint

D^{π} (x_{0}) \leq d_{0}

with Lyapunov-type local inequalities:

T_{π, d} [L] (x) \leq L (x), for every relevant state x .

Here, $L (x)$ can be interpreted as an upper bound on future cumulative constraint cost, or as a state-dependent remaining safety budget. The operator $T_{π, d}$ adds the immediate constraint cost and the expected continuation certificate after one transition under policy $π$ . Thus the inequality says that taking one policy step does not consume more certified safety burden than the current envelope permits.

T_{π, d} [L] (x) \leq L (x) for all x, and L (x_{0}) \leq d_{0},

then repeatedly applying the local inequality gives $D^{π} (x_{0}) \leq d_{0}$ under the exact CMDP assumptions. The construction is useful precisely because it turns a global budget into local constraints on action distributions.

Mathematical structure: Local LP interpretation

Let $π_{B}$ be a currently feasible baseline policy used to construct the Lyapunov budget. It is not simply an arbitrary initialization: its known feasibility anchors the certificate and keeps the induced policy set nonempty.

For a finite action space, a candidate improvement at state $x$ can be obtained from the local linear program

\begin{aligned} π^{'} (\cdot | x) \in & \underset{π \in Δ}{\arg \min} {π (\cdot | x)}^{T} Q (x, \cdot) \\ subject to & {(π (\cdot | x) - π_{B} (\cdot | x))}^{T} Q_{L} (x, \cdot) \leq \tilde{ε} (x) . \end{aligned}

In this expression:

$Δ$
is the probability simplex over actions.
$Q (x, \cdot)$
is the objective cost-to-go vector, so minimizing its expectation is a local performance-improvement step.
$Q_{L} (x, \cdot)$
is the Lyapunov safety-burden vector associated with taking each action and continuing.
${π (\cdot | x)}^{T} Q_{L} (x, \cdot)$
is the expected Lyapunov burden of the candidate action distribution.
${(π - π_{B})}^{T} Q_{L}$
is its increase in burden relative to the feasible baseline.
$\tilde{ε} (x)$
is the permitted local increase in certified safety burden.

The LP therefore has a precise reading: improve objective value at this state while admitting only a bounded increase in Lyapunov safety burden relative to a policy already used to certify feasibility.

Algorithmic structure: Safe DQN / Safe DPI

Exact dynamic programming is generally unavailable in large or unknown MDPs. In the approximate architecture described in the supplied material, the learner estimates three state-action quantities:

\begin{array}{ll} objective Q-function: & \hat{Q} (x, a; θ) \\ constraint-cost Q-function: & {\hat{Q}}_{D} (x, a; θ_{D}) \\ stopping-time Q-function: & {\hat{Q}}_{T} (x, a; θ_{T}) \end{array}

It then constructs a state-action Lyapunov estimate:

{\hat{Q}}_{L} (x, a) = {\hat{Q}}_{D} (x, a) + \tilde{ε} {\hat{Q}}_{T} (x, a) .

Q_{T}

must not be mistaken for another safety cost. $Q_{T} (x, a)$ estimates the expected number of remaining steps until termination after action $a$ is selected in state $x$ and the baseline policy is subsequently followed. It is the Q-function of an auxiliary episodic MDP whose per-step cost is $1$ .

Consequently, $Q_{D} (x, a)$ estimates real expected cumulative constraint cost, while $\tilde{ε} Q_{T} (x, a)$ accumulates an auxiliary per-step safety allowance over the expected remaining horizon. In short:

Q_{L} = real constraint burden + cumulative auxiliary slack burden.

The approximate policy-update pipeline is:

Replay buffer
    -> learn objective action value
    -> learn constraint-cost action value
    -> learn stopping-time action value
    -> construct the Lyapunov estimate
    -> solve local Lyapunov-safe LP
    -> distill LP policy into neural policy
    -> execute/update feasible-policy approximation

The LP acts on a local action distribution. Distillation is a separate approximation step: the neural policy executed later may differ from the LP solution that satisfied the estimated constraint.

Why it can work

There are structurally defensible reasons for this approach, without claiming that it must outperform alternatives.

Compared with Lagrangian learning, it restricts the admissible policy set through a certificate inequality rather than relying only on penalties for violation.
Compared with uniform step-wise constraints, its Lyapunov budget is state-dependent and can allow less conservative allocation of cumulative budget.
Compared with a global occupation-measure LP, an update is reduced to local LPs over action distributions when the action set is finite.
Compared with unconstrained function approximation, local LP projection and distillation provide a safety-shaped target policy rather than only an objective-improving target.

Mathematical guarantees

The theorem-level conclusions belong to an exact value/model setting and should not be automatically transferred to deep implementations.

If an exact $L$ satisfies $T_{π, d} [L] (x) \leq L (x)$ for every relevant state and $L (x_{0}) \leq d_{0}$ , then the policy satisfies the global expected cumulative constraint $D^{π} (x_{0}) \leq d_{0}$ .
If a feasible baseline policy exists and the Lyapunov set is constructed from it as stipulated, that feasible set is nonempty because it includes the baseline.
Under strong assumptions that the feasible baseline is sufficiently close to the unknown optimal constrained policy, the Lyapunov-induced feasible set can contain an optimal policy.
A safe Bellman operator can recover the CMDP optimum only when such strong inclusion or baseline-closeness assumptions hold.
Safe Policy Iteration can preserve feasibility and provide monotonic objective improvement in the exact model/value setting.

These claims establish a clean certificate mechanism. They do not prove hard real-world safety for an approximate neural policy.

Assumptions and limitations: Weaknesses and strong assumptions

A feasible baseline policy is required. In a physical process or autonomous system, obtaining that baseline can itself be a significant robust-control or operations-design problem.

The optimality result depends on baseline closeness to an unknown optimal feasible policy. This condition may be informative in analysis, but is difficult to verify before solving the constrained problem of interest.

Safety is expressed as expected cumulative constraint cost, not pathwise avoidance of unsafe outcomes. If rare but severe violations are unacceptable, an expectation-constrained CMDP requires additional risk-sensitive, robust, or chance-constrained machinery.

Function approximation weakens hard guarantees. When ${\hat{Q}}_{L} \approx Q_{L}$ , a local LP based on ${\hat{Q}}_{L}$ may certify a policy that is infeasible under the true constraint values. Distilling the LP action distribution into a neural policy introduces a further deviation. For strict inference-time safety, the LP projection would need to remain active at execution, or conservative margins would need to cover both estimation and distillation errors.

Finally, any evaluation concentrated on grid-world-style tasks establishes mechanism rather than general scalability. It should not be generalized without evidence to high-dimensional nonlinear continuous control, process dynamics, or long-horizon energy and supply-chain operation.

Critical assessment

The conceptual strength is that safety is handled as membership in an admissible policy set, not merely as a penalty term. The baseline/certificate/candidate relationship makes clear why a local improvement may remain feasible in the exact setting.

Its practical vulnerability is equally clear. Certificate quality, baseline availability, and approximation error determine whether the elegant local condition remains meaningful outside a finite exact CMDP. Neural experiments can demonstrate useful empirical constraint behavior; they cannot by themselves re-establish the exact Lyapunov guarantee.

Reference

Chow Y, Nachum O, Duenez-Guzman E, Ghavamzadeh M. A lyapunov-based approach to safe reinforcement learning. Advances in neural information processing systems. 2018;31.

포지셔닝: 왜 이 문제가 중요한가

로보틱스, 자율 시스템, 공정 제어, 에너지 운영, 불확실성 하의 공급망 제어에서 정책은 보상이나 운전 비용만으로 평가될 수 없다. 어떤 제어기는 처리량을 개선하면서도 열 노출, 위험한 상태 전이, 자원 부족, 신뢰도 위험을 허용 가능한 예산 이상으로 누적시킬 수 있다. 추천 시스템에서도 반복 행동이 장기적으로 바람직하지 않은 효과를 누적시킬 수 있다는 점에서 유사한 문제가 생긴다.

일반적인 강화학습은 기대 누적 목적함수를 최적화한다. 제약 Markov decision process(CMDP)는 여기에 더해 기대 누적 제약 비용을 통제하는 정책 중에서 좋은 정책을 찾는다. 비용 최소화 형태에서 안전 조건은 다음과 같다.

D^{π} (x_{0}) \leq d_{0}

여기서 $D^{π} (x_{0})$ 는 초기 상태 $x_{0}$ 에서 정책 $π$ 를 따를 때의 기대 누적 제약 비용이고, $d_{0}$ 는 허용 예산이다. 이것은 궤적 수준의 기대 제약이다. 각 행동이 한 단계 규칙을 통과하는지만 보는 것이 아니라, 에피소드 전체에 걸친 안전 부담의 누적을 통제한다.

문제 설정

c (x, a)

를 목적 stage cost, $d (x, a)$ 를 제약 stage cost라고 하자. 에피소드 CMDP의 목표는 다음 조건을 만족하는 정책 $π$ 를 선택하는 것이다.

\begin{aligned} minimize over π & C^{π} (x_{0}) = E_{π} [\sum_{t} c (x_{t}, a_{t}) | x_{0}] \\ subject to & D^{π} (x_{0}) = E_{π} [\sum_{t} d (x_{t}, a_{t}) | x_{0}] \leq d_{0} \end{aligned}

C^{π}

와 $D^{π}$ 의 구분은 중요하다. 성능 항들은 서로 절충될 수 있지만, 실행 가능성이 중요한 안전 예산은 보상 개선이 크다는 이유만으로 조용히 소모되어서는 안 된다. 또한 CMDP 제약은 pathwise safety가 아니다. 기대값 상한은 모든 실제 궤적의 위험을 배제하지 않는다.

기존 연구의 공백

Lyapunov 형식화 이전의 여러 접근은 학습 중 안전성과 계산 가능성 사이의 긴장을 드러냈다.

Lagrangian CMDP는 제약 비용에 승수를 붙여 벌점화한다. 수학적으로 자연스럽지만 승수 적응 과정에서 원래 예산을 위반하는 정책을 지나갈 수 있고, primal-dual 학습은 불안정할 수 있다.
Occupation-measure 또는 dual LP 형식은 유한 CMDP와 알려진 동역학에서는 우아한 전역 해법을 제공한다. 그러나 큰 상태-행동 공간에서는 비싸고, 전이 모델이 알려져 있지 않을 때 다루기 어렵다.
단계별 대리 제약은 즉각적인 예산 초과를 막을 수 있지만, 전역 허용량을 시간에 균등하게 나누면 지나치게 보수적일 수 있다.
Supermartingale 또는 보수적 대리 방법은 안전 조건을 보존할 수 있지만, 가능한 정책 집합을 너무 줄여 유용한 개선을 방해할 수 있다.
CPO/TRPO 계열 제약 최적화는 확장 가능한 정책 업데이트를 위해 설계되었지만, 임의의 RL 알고리즘에 대해 같은 직접적 정책 반복 해석을 제공하지는 않는다.

따라서 핵심 질문은 누적 실행 가능성을, 안전한 baseline을 유지하면서도 정책 개선을 허용하는 국소 admissibility test로 표현할 수 있는가이다.

핵심 아이디어

이 방법은 전역 기대 누적 제약

D^{π} (x_{0}) \leq d_{0}

을 Lyapunov 형태의 국소 부등식으로 바꾼다.

T_{π, d} [L] (x) \leq L (x), for every relevant state x .

L (x)

는 미래 누적 제약 비용의 상한, 또는 상태 의존적인 남은 안전 예산으로 해석할 수 있다. 연산자 $T_{π, d}$ 는 즉각 제약 비용과 정책 $π$ 하에서 한 번 전이한 뒤의 기대 continuation certificate를 더한다. 따라서 이 부등식은 한 정책 단계가 현재 envelope가 허용하는 인증된 안전 부담보다 더 많이 소비하지 않는다는 뜻이다.

만약 모든 관련 상태에서 이 국소 부등식이 성립하고 $L (x_{0}) \leq d_{0}$ 라면, 정확한 CMDP 가정 하에서는 국소 부등식을 반복 적용해 $D^{π} (x_{0}) \leq d_{0}$ 를 얻는다. 이 구성이 유용한 이유는 전역 예산을 행동 분포에 대한 국소 제약으로 바꾸기 때문이다.

수학적 구조: 국소 LP 해석

π_{B}

를 Lyapunov 예산을 구성하는 데 쓰는 현재 feasible baseline policy라고 하자. 이것은 임의의 초기 정책이 아니다. baseline의 알려진 실행 가능성이 certificate를 고정하고, 유도된 정책 집합이 비어 있지 않게 만든다.

유한 행동 공간에서 상태 $x$ 의 후보 개선은 다음 국소 선형계획으로 얻을 수 있다.

\begin{aligned} π^{'} (\cdot | x) \in & \underset{π \in Δ}{\arg \min} {π (\cdot | x)}^{T} Q (x, \cdot) \\ subject to & {(π (\cdot | x) - π_{B} (\cdot | x))}^{T} Q_{L} (x, \cdot) \leq \tilde{ε} (x) . \end{aligned}

이 표현에서 $Δ$ 는 행동에 대한 확률 단체(simplex), $Q (x, \cdot)$ 는 목적 cost-to-go 벡터, $Q_{L}$ 는 각 행동을 취하고 계속 진행할 때의 Lyapunov safety-burden 벡터다. 제약식은 후보 행동 분포가 feasible baseline에 비해 얼마나 더 많은 Lyapunov 부담을 만드는지 제한한다. 즉 이 LP는 이미 실행 가능성을 인증하는 데 쓰인 정책에 비해 안전 부담 증가를 제한하면서, 해당 상태에서 목적값을 개선하라는 의미를 갖는다.

알고리즘 구조: Safe DQN / Safe DPI

큰 MDP나 알려지지 않은 MDP에서는 정확한 동적계획법을 쓰기 어렵다. 제공된 자료에서 설명된 근사 구조는 세 가지 state-action quantity를 학습한다.

\begin{array}{ll} objective Q-function: & \hat{Q} (x, a; θ) \\ constraint-cost Q-function: & {\hat{Q}}_{D} (x, a; θ_{D}) \\ stopping-time Q-function: & {\hat{Q}}_{T} (x, a; θ_{T}) \end{array}

그다음 state-action Lyapunov 추정치를 다음처럼 구성한다.

{\hat{Q}}_{L} (x, a) = {\hat{Q}}_{D} (x, a) + \tilde{ε} {\hat{Q}}_{T} (x, a) .

여기서 $Q_{T}$ 는 또 다른 안전 비용이 아니다. $Q_{T} (x, a)$ 는 상태 $x$ 에서 행동 $a$ 를 고른 뒤 baseline policy를 따를 때 종료까지 남은 기대 단계 수를 추정한다. 따라서 $Q_{D}$ 는 실제 기대 누적 제약 비용이고, $\tilde{ε} Q_{T}$ 는 남은 기대 horizon에 걸쳐 쌓이는 보조 slack burden이다.

근사 정책 업데이트 파이프라인은 다음처럼 읽을 수 있다.

Replay buffer
    -> objective action value 학습
    -> constraint-cost action value 학습
    -> stopping-time action value 학습
    -> Lyapunov 추정치 구성
    -> 국소 Lyapunov-safe LP 풀이
    -> LP 정책을 신경망 정책으로 distillation
    -> feasible-policy 근사 실행/업데이트

LP는 국소 행동 분포에 작용한다. Distillation은 별도의 근사 단계다. 나중에 실행되는 신경망 정책은 추정 제약을 만족한 LP 해와 달라질 수 있다.

왜 작동할 수 있는가

이 접근이 항상 다른 방법보다 낫다고 주장하지 않아도, 구조적으로 설득력 있는 이유는 있다.

Lagrangian 학습과 달리, 위반 벌점에만 의존하지 않고 certificate inequality를 통해 허용 가능한 정책 집합을 제한한다.
균등한 단계별 제약보다 상태 의존 Lyapunov 예산을 쓰므로 누적 예산 배분이 덜 보수적일 수 있다.
전역 occupation-measure LP에 비해, 유한 행동 집합에서는 업데이트가 행동 분포에 대한 국소 LP로 줄어든다.
무제약 함수근사와 달리, 국소 LP projection과 distillation은 단순히 목적을 개선하는 target이 아니라 안전 구조가 반영된 target policy를 제공한다.

수학적 보장

정리 수준의 결론은 정확한 value/model 설정에 속하며, deep implementation으로 자동 이전되어서는 안 된다.

정확한 $L$ 이 모든 관련 상태에서 $T_{π, d} [L] (x) \leq L (x)$ 를 만족하고 $L (x_{0}) \leq d_{0}$ 이면, 정책은 전역 기대 누적 제약 $D^{π} (x_{0}) \leq d_{0}$ 를 만족한다.
feasible baseline policy가 존재하고 Lyapunov set이 명시된 방식으로 구성되면, 그 feasible set은 baseline을 포함하므로 비어 있지 않다.
feasible baseline이 미지의 optimal constrained policy에 충분히 가깝다는 강한 가정 아래에서는 Lyapunov-induced feasible set이 optimal policy를 포함할 수 있다.
safe Bellman operator가 CMDP optimum을 회복한다는 주장은 이러한 강한 포함 조건 또는 baseline closeness 조건이 성립할 때에만 가능하다.
Safe Policy Iteration은 정확한 model/value 설정에서 실행 가능성을 보존하고 목적의 단조 개선을 제공할 수 있다.

이 결과들은 명확한 certificate mechanism을 세운다. 그러나 근사 신경망 정책에 대해 실제 세계의 hard safety를 증명하는 것은 아니다.

가정과 한계

feasible baseline policy가 필요하다. 물리 공정이나 자율 시스템에서는 그 baseline을 얻는 일 자체가 중요한 robust control 또는 operations design 문제가 될 수 있다.

최적성 결과는 baseline이 미지의 최적 feasible policy에 가깝다는 가정에 의존한다. 이 조건은 분석적으로는 유익하지만, 관심 있는 제약 문제를 풀기 전에 검증하기 어렵다.

안전은 기대 누적 제약 비용으로 표현된다. unsafe outcome의 pathwise avoidance가 아니다. 드물지만 심각한 위반이 허용될 수 없다면 risk-sensitive, robust, chance-constrained 기법이 추가로 필요하다.

함수근사는 hard guarantee를 약화시킨다. ${\hat{Q}}_{L} \approx Q_{L}$ 일 때, 추정치에 기반한 국소 LP는 실제 제약 값에서는 infeasible한 정책을 인증할 수 있다. LP 행동 분포를 신경망 정책으로 distill하는 과정도 추가 오차를 만든다. 엄격한 inference-time safety가 필요하다면 LP projection이 실행 시점에도 유지되거나, 추정 및 distillation 오차를 덮는 보수적 margin이 필요하다.

마지막으로 grid-world 스타일 평가에 집중한 실험은 메커니즘을 보여 주는 것이지 일반적인 확장성을 입증하는 것은 아니다. 고차원 비선형 연속 제어, 공정 동역학, 장기 에너지 및 공급망 운영으로 일반화하려면 별도의 근거가 필요하다.

비판적 평가

개념적 강점은 안전을 단순 벌점항이 아니라 admissible policy set의 membership으로 다룬다는 점이다. baseline, certificate, candidate의 관계는 정확한 설정에서 왜 국소 개선이 실행 가능성을 유지할 수 있는지 분명히 보여 준다.

실천적 취약점도 분명하다. certificate의 품질, baseline의 존재, 근사 오차가 이 우아한 국소 조건이 유한 정확 CMDP 밖에서도 의미를 유지하는지를 결정한다. 신경망 실험은 유용한 경험적 제약 행동을 보여 줄 수 있지만, 그것만으로 정확한 Lyapunov 보장을 다시 세우지는 못한다.

참고문헌

Chow Y, Nachum O, Duenez-Guzman E, Ghavamzadeh M. A lyapunov-based approach to safe reinforcement learning. Advances in neural information processing systems. 2018;31.