PaperlayerView exact revision on arXiv

Source-linked AI summary

A Lyapunov-based Approach to Safe Reinforcement Learning

Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman, Mohammad Ghavamzadeh

arXiv:1805.07708v1cs.LGcs.AIstat.ML

TL;DR

Safe RL must optimize performance while avoiding cumulative constraint violations during training and deployment. The paper formulates this problem as CMDPs and develops LP-based Lyapunov methods that transform DP and RL algorithms into safe counterparts. Across benchmark tasks, the proposed methods outperform common baselines in balancing performance and constraint satisfaction.

  • Problem

    Real-world RL requires optimizing returns while satisfying safety constraints during both training and deployment, whereas existing Lagrangian methods offer little per-iteration behavior-policy safety.

  • Method

    The paper constructs Lyapunov functions with an LP-based method and uses them to derive safe DP and scalable safe RL algorithms for CMDPs.

  • Results

    The proposed algorithms outperform common baselines across benchmark planning tasks in balancing performance and constraint satisfaction.

  • Takeaways & Limitations

    Lyapunov-induced local constraints provide a way to guarantee global behavior-policy safety while adapting standard DP and RL algorithms.

  • Takeaways & Limitations

    The theoretical optimality condition requires a sufficiently close feasible baseline policy, while the practical algorithms lack optimality guarantees and empirically often return near-optimal policies.

Abstract

from arXiv · show

In many real-world reinforcement learning (RL) problems, besides optimizing the main objective function, an agent must concurrently avoid violating a number of constraints. In particular, besides optimizing performance it is crucial to guarantee the safety of an agent during training as well as deployment (e.g. a robot should avoid taking actions - exploratory or not - which irrevocably harm its hardware). To incorporate safety in RL, we derive algorithms under the framework of constrained Markov decision problems (CMDPs), an extension of the standard Markov decision problems (MDPs) augmented with constraints on expected cumulative costs. Our approach hinges on a novel \emph{Lyapunov} method. We define and present a method for constructing Lyapunov functions, which provide an effective way to guarantee the global safety of a behavior policy during training via a set of local, linear constraints. Leveraging these theoretical underpinnings, we show how to use the Lyapunov approach to systematically transform dynamic programming (DP) and RL algorithms into their safe counterparts. To illustrate their effectiveness, we evaluate these algorithms in several CMDP planning and decision-making tasks on a safety benchmark domain. Our results show that our proposed method significantly outperforms existing baselines in balancing constraint satisfaction and performance.

1 Introduction

Safe RL must optimize returns while satisfying cumulative constraints during both training and deployment. The paper formulates this challenge as CMDPs and introduces Lyapunov-based safe DP and RL algorithms.

  • Motivation: Real-world RL must satisfy safety constraints during training and deployment, not merely optimize a single return.Examples include preventing irreversible hardware damage and avoiding harmful or offensive recommendations.
  • Problem formulation: CMDPs extend MDPs with expected cumulative constraint costs, supporting trajectory-level safety specifications.This formulation is suited to constraints defined over whole trajectories rather than individual state-action pairs.
  • Limitations of existing methods: Lagrangian methods can face numerical instability and provide little safety guarantee for the behavior policy at each training iteration.Their safety guarantee is asymptotic when the policy is learned with a Lagrange multiplier.
  • Related work: Prior Lyapunov approaches did not explicitly model CMDP constraints and relied on hand-crafted functions without principled performance guarantees.The paper addresses both the construction problem and the safety-performance trade-off.
  • Contributions: The paper proposes an LP-based Lyapunov construction, safe DP algorithms, and scalable safe RL algorithms evaluated on benchmark planning tasks.The proposed methods include safe policy iteration, safe value iteration, safe DQN, and safe DPI.

2 Preliminaries

The paper models sequential decision-making with MDPs and adds expected cumulative constraint costs to obtain CMDPs. Safety is expressed as an upper bound on cumulative constraint cost for a policy.

  • MDP model: An MDP consists of states, actions, immediate costs, transition probabilities, and an initial state.The formulation includes transient states and a terminal state.
  • CMDP model: A CMDP extends the MDP with an immediate constraint cost and a threshold on expected cumulative constraint cost.The threshold is denoted d0 in the supplied formulation.
  • Assumptions: The analysis assumes transient MDPs whose first hitting time of the terminal state is uniformly bounded by T.The paper motivates this using finite stopping times in sampled RL trajectories.
  • Optimization problem: The CMDP optimization problem seeks a policy minimizing expected cumulative cost subject to a cumulative constraint-cost threshold.When the feasibility set is non-empty, an optimal stationary Markov policy exists under the transient CMDP assumption.

3 A Lyapunov Approach for Solving CMDPs

The Lyapunov approach constructs local constraints whose induced policies remain globally safe and can include an optimal CMDP policy under a baseline-policy assumption. This enables safe Bellman optimization and standard DP solutions.

  • Lyapunov formulation: The method constructs Lyapunov functions relative to a feasible baseline policy, with induced policies constrained by the Lyapunov function.A baseline policy may be chosen to minimize constraint cost.
  • Safety guarantee: Any policy induced by a valid Lyapunov function is feasible because its constraint cost remains bounded by the Lyapunov function.The bound follows from the contraction property of the constraint Bellman operator.
  • Lyapunov construction: Cost shaping can transform the optimal policy’s constraint value function into a Lyapunov function induced by the baseline policy.The auxiliary constraint cost is the mechanism used for this transformation.
  • Candidate properties: The candidate Lϵ* upper-bounds constraint costs for both the baseline and optimal policies.Its construction uses an upper bound on the auxiliary cost-shaping term.
  • Optimality condition: If the baseline policy satisfies the distance assumption, the induced feasible-policy set contains an optimal CMDP policy.The assumption limits the allowable distance between the baseline and optimal policies.
  • Safe dynamic programming: The safe Bellman operator is monotonic and contractive, and its fixed point solves the CMDP optimization problem under the baseline-policy assumption.An optimal policy can be constructed by minimizing the Bellman operator over the Lyapunov-induced feasible set.
  • Practical boundary: The optimality result still requires estimating the total variation distance between the baseline and optimal policies.The paper identifies this verification as challenging and proposes approximating the auxiliary term through bootstrapping in practice.

4 Safe Reinforcement Learning Using Lyapunov Functions

The paper constructs Lyapunov functions through an LP-based auxiliary-cost procedure and uses them to enforce safe policy updates. This yields safe DP and scalable function-approximation RL algorithms with feasibility guarantees and favorable empirical behavior.

  • Lyapunov-function construction: The largest auxiliary cost satisfying the Lyapunov and safety conditions is selected to enlarge the induced feasible policy set.The construction solves for eϵ subject to Leϵ(x) ≥ TπB,d[Leϵ](x) and Leϵ(x0) ≤ d0.
  • Safe DP algorithms: Safe policy iteration recomputes the Lyapunov function from the current baseline policy before each constrained policy update.The update minimizes the objective cost value while restricting the policy to the Lyapunov-induced feasible set.
  • Safe DP algorithms: A feasible current policy implies a feasible updated policy, while cumulative cost does not increase under safe policy iteration.With strictly concave and convex regularizers, respectively, the policy sequence also asymptotically converges.
  • Safe DP algorithms: Safe value iteration updates Lyapunov estimates by bootstrapping from current value estimates and has consistent-feasibility and convergence properties.The method updates the Lyapunov function at every iteration using the current optimal value estimate.
  • Scalable safe RL: Safe DQN and safe DPI replace safe DP value and policy updates with function approximations for unknown models and large state or action spaces.Safe DQN uses off-policy fitted Q-iteration, whereas safe DPI uses approximate policy iteration and policy distillation.
  • Empirical behavior: Across grid-world planning results, safe DP methods produce feasible policies with good performance, while safe RL methods learn safely with discrete or image observations.The planning figure reports average return and cumulative constraint cost with 80% confidence intervals.

5 Experiments

Experiments use a stochastic 25 × 25 grid-world where agents seek short routes while limiting obstacle visits. Safe DP and safe RL methods balance performance and constraint satisfaction more effectively than the reported baselines.

  • Experimental domain: The benchmark is a stochastic 25 × 25 grid-world with 625 states, noisy four-neighbor movement, unit movement costs, and a reward of 1000 for reaching the destination.Obstacle visits incur constraint cost 1, and the agent must reach the destination while visiting obstacles at most d0 times.
  • CMDP planning: CMDP planning compares SPI and SVI with step-wise surrogate, super-martingale surrogate, Lagrangian, and dual LP baselines.The planning setting provides explicit reward and transition models.
  • CMDP planning: Across obstacle densities ρ from 0 to 0.5, SPI consistently returns feasible policies with good performance, while surrogate methods show little policy improvement.SVI is feasible and near-optimal at low density but degrades as ρ grows; Lagrangian solutions begin violating constraints at higher density.
  • Safe reinforcement learning: Safe RL evaluates SDPI and SDQN with one-hot or image observations and constraint thresholds d0 = 1 and d0 = 5.The algorithms are initialized with a randomized baseline policy.
  • Safe reinforcement learning: Across task variants, SDPI and SDQN achieve good returns while guaranteeing safety and keeping later updated policies safe after finding a safe policy.Lagrangian approaches more often violate constraints during training, can obtain worse rewards, and are sensitive to initialization.

6 Conclusion

The paper presents Lyapunov-based CMDP methods for safe RL, including an LP-based construction that supports safe DP and RL algorithms. Experiments and theoretical results support feasibility and robust learning, while future work targets broader algorithms and real-world evaluation.

  • Conclusion: The paper formulates safe RL as a CMDP and proposes a Lyapunov approach with an LP-based method for generating Lyapunov functions.The resulting algorithms guarantee feasibility and achieve optimality under certain conditions.
  • Conclusion: The Lyapunov framework transforms DP and RL algorithms into safe counterparts through straightforward implementation modifications.The paper reports empirical validation of safety and robust learning in RL.
  • Future work: Future algorithmic work includes applying the Lyapunov approach to policy-gradient methods and comparing it with CPO in continuous RL problems.The authors also identify evaluation on real-world testbeds as a practical direction.
  • Safety formulations: Reachability safety bounds the probability of entering hazardous regions before termination by a threshold d0.The CMDP formulation can encode this through state augmentation that tracks whether a hazardous region has been visited.
  • Safety formulations: Bounding expected visits to undesirable regions also satisfies the reachability constraint.The paper states that any policy satisfying the undesirable-region visitation constraint satisfies the reachability constraint.

B Existing Approaches for Solving CMDPs

Existing CMDP solvers use surrogate constraints, Lagrangian optimization, or occupation-measure linear programming, but each faces conservatism, scalability, or safe-training limitations.

  • The Lagrangian Based Algorithm: Lagrangian methods seek a saddle point by alternating policy optimization with multiplier optimization, relying on strong duality under a non-empty interior feasible set.Intermediate policies may violate constraints during iteration, while convergence rates, numerical stability, and multiplier initialization remain challenging.
  • The Dual LP Based Algorithm: Occupation-measure LPs recover optimal stationary policies for finite CMDPs but scale poorly and do not directly extend to unknown-model reinforcement learning.The interior-point complexity is O(|X ′|^2|A|^2(2|X ′||A|+1)).
  • Step-wise Constraint Surrogate Approach: Step-wise surrogates embed cumulative constraints into admissible actions, enabling standard dynamic programming through a contraction Bellman operator.Every resulting policy is feasible, but the surrogate constraint can be substantially more stringent than the original safety constraint.
  • Super-martingale Constraint Surrogate Approach: Super-martingale surrogates decouple feasibility-set construction from optimization, allowing fixed-point dynamic programming over refined feasible policies.They can remain overly conservative, and suboptimality guarantees are difficult to characterize.
  • Super-martingale Constraint Surrogate Approach: The paper’s surrogate value-function approximation replaces an generally unavailable constraint fixed point with a computable fixed-point solution, and a sufficient condition yields a safe policy.When DS(x0) ≤ d0, the resulting policy satisfies Dπ(x0) ≤ d0.

C.2 Proof of Theorem 1

The proof establishes that the constructed safe Bellman operator is monotone and contractive, then uses these properties to show the Lyapunov construction satisfies the required conditions.

  • Lyapunov Construction: Under the stated construction, the auxiliary-cost Lyapunov function satisfies both required Lyapunov properties.The proof derives the two inequalities using the baseline transition structure, auxiliary costs, and the assumptions used in the theorem.
  • Operator Properties: The safe Bellman operator is a contraction under a positive weighting vector and discounting factor 0 < γ < 1.The proof constructs the weighting from a stochastic shortest-path fixed point and invokes a standard contraction result.
  • Operator Properties: The safe Bellman operator is monotone: V(x) ≤ W(x) implies T[V](x) ≤ T[W](x) for every state.The proof applies the inequality to each action, averages with policy probabilities, and minimizes over the Lyapunov-induced feasible set.

C.4 Proof of Theorem 2

The proof shows that the fixed point of the safe Bellman operator equals the CMDP optimum and that its greedy policy is optimal.

  • Optimality Proof: The greedy policy induced by the fixed point is feasible for the original CMDP, yielding VOPT(x0) ≤ V*(x0).This direction uses membership in the Lyapunov-induced feasible set and contraction of the policy Bellman operator.
  • Optimality Proof: The optimal CMDP policy is feasible for the safe Bellman optimization, yielding VOPT(x0) ≥ V*(x0).The argument applies the Lyapunov Bellman inequality recursively under the optimal policy.
  • Optimality Proof: Therefore VOPT(x0) = V*(x0), and the greedy policy from the fixed-point equation is optimal for the CMDP.The equality combines both inequalities proved above.

C.5 Proof of Proposition 1

The proof establishes consistent feasibility, policy improvement, and asymptotic convergence for the Lyapunov-based policy iteration procedure.

  • A feasible initial policy induces a Lyapunov function, making the Lyapunov-function set and subsequent policy-optimization feasibility set non-empty.The current policy remains feasible for the optimization in Step 1.
  • The updated policy π1 is feasible for the constrained optimization problem.
  • Policy improvement follows because the current policy is feasible and the updated policy minimizes the Step 1 optimization objective.The proof uses the Bellman operator’s contraction property to establish the improvement claim.
  • The value-function sequence is uniformly monotonic and lower bounded, so it converges when policy improvement stops.Strict convexity and concavity after regularization make the limiting policies and Lyapunov-function updates unique.
  • The resulting policy sequence {πk} converges after the Lyapunov-function and policy updates stop.

C.7 Proof of Proposition 2

The proof extends consistent feasibility, monotonic value improvement, and asymptotic convergence to the value-iteration procedure under proper-policy and transient-MDP assumptions.

  • The initial policy π0 is feasible, so its constraint value can serve as a Lyapunov function and Step 1 has a non-empty feasibility set.
  • The updated policy π1 remains feasible for the constrained optimization problem.
  • The value-iteration trajectory separates cumulative cost into the first K stages and the remaining tail.
  • Because all policies are proper and the MDP is transient, the probability mass remaining in transient states after step K is bounded and vanishes as K grows.
  • The iterated Bellman operators converge pointwise to the limiting value function for every transient initial state.

E Practical Implementations

The practical implementations use entropy regularization, saddle-point Lagrangian optimization, and restricted quadratic function parameterizations to scale safe policy updates.

  • Entropy regularization converts the inner policy optimization into a tractable finite-dimensional formulation, especially when the action space is large.The unregularized inner problem is a linear program, while the regularized variant supports approximate policy computation.
  • Strong duality yields a saddle-point Lagrangian formulation whose solution policy equals the entropy-regularized optimum.
  • The optimal Lagrange multiplier is uniquely characterized by a KKT condition and can be obtained by solving a polynomial equation in z = exp(−λ).
  • For continuous actions, second-order Taylor parameterizations of the Q-function and Lyapunov function enable analytical policy updates but restrict the function class.
  • Under these parameterizations, the entropy-regularized policy is Gaussian, while its multiplier requires numerical integration unless the baseline policy has a tractable form.

F Experimental Setup

The experiments assess safe dynamic-programming and Lagrangian methods in obstacle-rich grid worlds, using return, cumulative constraint cost, and training progress as evaluation axes.

  • The large 60 × 60 planning example uses SciPy linprog; each policy-optimization iteration takes approximately 25.0 seconds on average.SVI takes around 200 iterations to converge, whereas SPI takes 60 iterations.
  • RL training collects 100-step episodes, performs 10 replay-buffer updates per iteration, and updates target Q networks every 10 iterations.The baseline policy is updated every 50 iterations.
  • Discrete observations use a feed-forward network with hidden-layer sizes 16, 64, and 32, while image observations use convolutional and fully connected networks.
  • Figure 3 varies obstacle density and reports average return, average cumulative constraint cost, and all experimental methods with 80% confidence intervals.The caption states that safe DP algorithms compute safe policies with good performance.
  • Figure 4 plots saddle-point Lagrangian optimization results against episode count measured in thousands.
Loading 1805.07708v1…