PaperlayerView exact revision on arXiv

Source-linked AI summary

Safe Policies for Reinforcement Learning via Primal-Dual Methods

Santiago Paternain, Miguel Calvo-Fullana, Luiz F. O. Chamon, Alejandro Ribeiro

arXiv:1911.09101v2eess.SYcs.LGcs.SYmath.OC

TL;DR

Safe reinforcement learning with unknown transition probabilities lacks a straightforward way to optimize policies against probabilistic safety constraints. The paper relaxes those constraints and applies primal-dual optimization; its analysis gives a small duality gap under sufficiently rich parametrization, while the navigation example illustrates adapting to differing safety constraints.

  • Problem

    For unknown MDPs, probabilistic safety constraints cannot be directly optimized from experience, and common chance-constrained methods do not guarantee positive invariance.

    Source: A. Safe reinforcement learning · p. 1

  • Method

    The paper relaxes the safety constraints and uses primal-dual optimization, whose dual objective is convex and can be minimized with gradient methods.

    Source: §V · p. 6, §VI · p. 8

  • Results

    At safety demand 1−δi = 0.999, the paper plots sample navigation trajectories and reports that dual-variable values distinguish obstacle constraint difficulty.

    Source: §VII · p. 10

  • Takeaways & Limitations

    Dual variables provide a way to assess the difficulty of satisfying each constraint at its specified safety level.

    Source: §VII · p. 10

    For continuing tasks, the safety guarantee covers an arbitrarily long window rather than all time steps.

    Source: §IV · p. 5

Abstract

from arXiv · show

In this paper, we study the learning of safe policies in the setting of reinforcement learning problems. This is, we aim to control a Markov Decision Process (MDP) of which we do not know the transition probabilities, but we have access to sample trajectories through experience. We define safety as the agent remaining in a desired safe set with high probability during the operation time. We therefore consider a constrained MDP where the constraints are probabilistic. Since there is no straightforward way to optimize the policy with respect to the probabilistic constraint in a reinforcement learning framework, we propose an ergodic relaxation of the problem. The advantages of the proposed relaxation are threefold. (i) The safety guarantees are maintained in the case of episodic tasks and they are kept up to a given time horizon for continuing tasks. (ii) The constrained optimization problem despite its non-convexity has arbitrarily small duality gap if the parametrization of the policy is rich enough. (iii) The gradients of the Lagrangian associated with the safe-learning problem can be easily computed using standard policy gradient results and stochastic approximation tools. Leveraging these advantages, we establish that primal-dual algorithms are able to find policies that are safe and optimal. We test the proposed approach in a navigation task in a continuous domain. The numerical results show that our algorithm is capable of dynamically adapting the policy to the environment and the required safety levels.

I. INTRODUCTION

The paper addresses safe reinforcement learning when transition probabilities are unknown and probabilistic constraints cannot be directly optimized from experience. It proposes relaxing trajectory-level safety constraints to support policy updates and analyzes the resulting guarantees and optimization approach.

II. PROBLEM FORMULATION

  • The paper studies an unknown MDP in which policies are learned from samples to maximize expected cumulative reward, with safety requirements imposed on state trajectories.A discounted infinite-horizon objective can be represented as a finite-horizon objective with a random stopping time.Source: A. Safe reinforcement learning · p. 1, §II · pp. 2–3

B. Alternative approaches to safety in control

A. Safe reinforcement learning

  • The paper defines safety through a lower bound on the probability that an entire trajectory remains in a safe set, then relaxes the constraint while preserving safety guarantees.The relaxation also provides stochastic constraint gradients with respect to the policy.Source: A. Safe reinforcement learning · p. 1, §II · p. 2
  • The proposed dual approach addresses the difficult choice of risk-aware reward weights, whose values have no straightforward relation to constraint satisfaction and can undermine task completion.The paper also proposes a new geometric proof of strong duality despite the primal problem's non-convexity.Source: A. Safe reinforcement learning · p. 2, §II · p. 3

II. PROBLEM FORMULATION

  • The problem concerns learning a safe policy, not ensuring that safety constraints are met during training; the paper distinguishes this from safe exploration.The proposed relaxation also provides a systematic way to adapt safety-related reward coefficients.Source: §II · p. 3

III. LEARNING SAFE POLICIES

The paper relaxes probabilistic safety constraints into cumulative-cost constraints that can be handled with standard reinforcement-learning methods. It uses dual optimization to tune safety weights and gives safety conditions and duality-gap guarantees for the resulting approach.

III. LEARNING SAFE POLICIES

  • The relaxation makes chance constraints optimizable through cumulative costs, and the dual formulation allows standard policy-gradient or actor-critic methods in model-free settings.The dual function is convex, so gradient-like algorithms can solve the dual problem.Source: §III · pp. 3–4
  • For finite-horizon tasks, the relaxation corresponds to satisfying chance constraints on average.The paper relates this formulation to online learning.Source: §III · p. 3
  • The required safety slack values depend on the desired safety level and safety horizon, so they can be computed rather than tuned as hyperparameters.The guarantees require appropriate slack values; the relaxed constraints alone are not sufficient for the stated safety levels.Source: §III · p. 4
  • Selecting the dual parameter requires solving a convex optimization problem, which is more efficient than exhaustive grid search or bisection.The approach uses the dual problem to select safety-related reward coefficients systematically.Source: §III · p. 4
  • Despite the primal problem's non-convexity, its duality gap can be made arbitrarily small for a sufficiently rich policy parametrization.This makes solving the dual a close approximation to solving the primal problem.Source: §III · p. 4

IV. SAFETY GUARANTEES

The ergodic relaxation turns safety requirements into computable constraints with finite-horizon and discounted safety guarantees. Its guarantees depend on feasibility and, for continuing tasks, apply over a finite safety window; the relaxation may also incur an optimality gap.

IV. SAFETY GUARANTEES

  • For γ=1 and finite horizon T, a feasible solution with c_i=(T+1)(1−δ_i/(T+1)) is (1−δ_i)-safe, and a sufficiently safer policy guarantees feasibility.The sufficient feasibility condition requires a policy safe at level 1−δ_i/(T+1).Source: §IV · p. 4
  • Finite-horizon safety slacks can be computed directly from the desired safety level δ_i and horizon T, without introducing extra hyperparameters.Source: §IV · p. 5
  • For γ<1, the specified slack yields (1−δ_i)-safety only through T_i; feasibility follows if a policy safe at level 1−γ^T_i(1−γ)δ_i exists.Theorem 2's safety window is limited by the horizons assumed to exist.Source: §IV · p. 5
  • Safety is preserved when sufficiently safe policies exist, but the relaxation may create an MDP-dependent optimality gap that cannot generally be bounded without further assumptions.The authors note that bounding the difference is beyond this work's scope, which focuses on safe operation.Source: §IV · pp. 5–6

V. SAFE LEARNING HAS (ALMOST) ZERO DUALITY GAP

The paper studies the dual relaxation of the safe-learning problem, whose dual function is convex and can be optimized over multipliers. Despite the non-convex primal problem, its duality gap can be made arbitrarily small with sufficiently rich policy parametrization.

V. SAFE LEARNING HAS (ALMOST) ZERO DUALITY GAP

  • The dual function is a pointwise maximum of linear functions, so it is convex and gradient descent on multipliers finds the optimal dual variable.Source: §V · p. 6
  • For sufficiently rich policy parametrization, the duality gap can be made arbitrarily small despite the non-convexity of problem (8).At the optimal multiplier, maximizing (14) is equivalent to solving (8) under this result.Source: §V · p. 6
  • The stochastic-kernel case provides an auxiliary zero-duality-gap result before the paper treats finite parametrizations.Source: §V · p. 6

A. The case of stochastic kernels

For stochastic-kernel policies, the paper establishes strong duality under bounded rewards and strict feasibility. It gives a geometric proof and relates the dual problem to risk-aware regularization, while noting that dual evaluation can be intractable for general distributions.

A. The case of stochastic kernels

  • Setting λ_i=w_i relates the dual to the risk-aware problem, but a nonzero duality gap means the two problems need not be equivalent.If the gap is zero, the problems are equivalent.Source: A. The case of stochastic kernels · p. 6
  • The proof uses an alternative geometric argument: the sub-level set of the vector-valued value-and-constraint function is convex.Source: A. The case of stochastic kernels · p. 6
  • With bounded rewards and a strictly feasible policy, the stochastic-kernel problem has strong duality, so its primal and dual optima coincide.Source: A. The case of stochastic kernels · p. 6
  • The primal and dual problems trace the same Pareto front, while specifying constraints is often simpler than specifying risk weights.Source: A. The case of stochastic kernels · p. 7
  • The strong-duality result does not itself provide a procedure for solving the primal problem because evaluating the dual function entails an intractable maximization for general distribution classes.Source: A. The case of stochastic kernels · p. 7

B. Back to parametric policies

The paper shows that sufficiently expressive parametric policies incur a duality gap bounded in proportion to their approximation error. Increasing representational capacity can make this error arbitrarily small, while solving the dual problem mainly requires an unconstrained RL problem.

B. Back to parametric policies

  • A near-universal parameterization approximates any stochastic kernel in the stated class to a specified accuracy.The paper describes this requirement as milder than approximation in uniform norm.Source: B. Back to parametric policies · p. 7
  • The policy approximation does not make occupation-measure error accumulate without bound over an infinite horizon.The error in occupation-measure approximation is smaller when γ is smaller.Source: B. Back to parametric policies · p. 7
  • For near-universal parametric policies, the duality gap is bounded linearly by the policy approximation error.The resulting sub-optimality is of order ε and can be made arbitrarily small by increasing the parameterization's representation ability.Source: B. Back to parametric policies · pp. 7–8
  • The main burden of solving the constrained problem is computing the dual function, equivalent to an unconstrained RL problem.The paper therefore characterizes this constrained problem as not much more challenging than its unconstrained counterpart.Source: B. Back to parametric policies · p. 8

VI. PRIMAL-DUAL ALGORITHM

The algorithm uses policy optimization and dual updates to solve the safe-learning problem. Convexity of the dual supports gradient descent, and stochastic estimates enable updates from sampled trajectories.

VI. PRIMAL-DUAL ALGORITHM

  • The dual function is convex, so minimizing it provides a route to the primal solution when the duality gap is bounded.The paper notes that dual algorithms alone do not identify the primal solution.Source: §VI · p. 8
  • Dual gradient descent projects multiplier updates onto the positive orthant and converges to a neighborhood of the dual optimum.The dual gradient can be computed by evaluating the original constraints at the primal maximizer of the Lagrangian.Source: §VI · p. 8
  • Policy-gradient or actor-critic methods can approximate the primal maximizer, but gradient-based methods are not generally guaranteed to find a global maximum.The paper notes their empirical success in finding solutions with small suboptimality.Source: §VI · p. 8
  • The dual iteration bound scales linearly with the inverse desired accuracy, and sufficiently small step sizes converge from any initial multiplier.The paper describes this as a small overhead relative to solving the unconstrained RL problem.Source: §VI · p. 8
  • In the parallel primal-dual variant, policy updates run on a faster timescale than multiplier updates.This timescale separation lets the method operate theoretically as dual descent.Source: §VI · p. 9
  • Stochastic primal and dual gradients can be estimated from one trajectory, with unbiased estimates for finite horizons.For infinite horizons, a geometrically distributed random stopping time yields unbiased estimates; actor-critic is noted as a lower-variance alternative.Source: §VI · p. 9

VII. NUMERICAL RESULTS

In continuous navigation, the learned policy avoids the obstacles under a 0.999 safety requirement. Dual-variable values distinguish obstacle difficulty, and removing the green obstacle yields the largest reward improvement.

VII. NUMERICAL RESULTS

  • The evaluation uses an infinite-horizon continuous navigation task with a Gaussian policy whose mean is approximated by radial basis functions.The state is the agent's position in a 10-by-10 domain, and the goal is at (8.5, 1.5).Source: §VII · pp. 9–10
  • Under the 0.999 safety requirement, the learned policy avoids all obstacles.The green L-shaped obstacle near the goal requires considerable trajectory deviation, unlike the easier-to-circumnavigate red circular obstacle.Source: §VII · p. 10
  • Higher dual-variable values mark more restrictive constraints; the green obstacle has the highest value, while red has the lowest.The dual variables also distinguish subtler cases: cyan is slightly more restrictive than orange.Source: §VII · p. 10
  • Safety guarantees are evaluated every 40,000 iterations over 500 independent evaluations, with means, standard-deviation bands, and the 0.999 requirement shown.The figure also includes a simple policy-gradient comparison using the smallest dual variable, λ = 1.128, for all constraints.Source: Figure 4 · p. 11
  • Removing the green obstacle produced the largest average-reward improvement, while removing the red obstacle produced the smallest.The comparison retrained the task after removing each obstacle's constraint.Source: Figure 3 · p. 10, §VII · p. 11

A. Safety guarantees

The primal-dual method reaches the required safety level and ultimately converges to a policy safer than required. Fixed reward weights either fail to attain that level or reduce reward, while the algorithm’s reward-safety trajectory shows safety first and reward gains thereafter.

A. Safety guarantees

  • The primal-dual algorithm reaches the required safety level in mean after approximately 10,000 iterations, and its standard-deviation band ultimately falls within the requirement.The green obstacle takes longer than the others to reach the required level and has a wider distribution; the converged policy is safer than required.Source: A. Safety guarantees · p. 11, Figure 6 · p. 12
  • With all weights fixed at λ = 1.128, the policy does not attain the required safety level in mean, and its standard-deviation band does not tighten as before.This weight is associated with the red obstacle; the text notes that selecting reward-shaping weights is not straightforward.Source: A. Safety guarantees · p. 11
  • The fixed largest weight, λ = 2.835, produces safe policies but a lower overall reward than the primal-dual algorithm.Figure 5 compares reward normalized by time steps T; the reported means and standard-deviation bands use 500 evaluations.Source: A. Safety guarantees · pp. 11–12, Figure 5 · p. 11
  • As iterations progress, mean safety probability and reward both increase until safety is attained; afterward, reward improves while safety is maintained.Early termination can therefore yield a safe but suboptimal policy.Source: A. Safety guarantees · p. 12, Figure 6 · p. 12

B. Complex navigation scenario

The authors evaluate their method in a realistic ROS/Unity simulation of a Husky navigating around obstacles. The simulated robot reaches the goal while staying close to the ideal trajectory, and the conclusion reports that the approach dynamically adapts safety costs without manual parameter tuning.

B. Complex navigation scenario

  • The complex-navigation evaluation simulates a Clearpath Husky in ROS with Unity physics, navigating from a start point to a goal while avoiding obstacles.The environment is described as a realistic simulation, not a physical-robot deployment.Source: B. Complex navigation scenario · p. 12
  • The trained policy is deployed in the ROS simulator with high-fidelity Unity physics to evaluate its navigation performance.The controller produces linear and angular velocities; the scenario uses Algorithm 2 with parameters from the previous numerical results.Source: B. Complex navigation scenario · p. 12
  • In the ROS simulation, the agent reaches the goal while avoiding obstacles and following closely the ideal trajectory, with deviations at high-speed turns.The trained model does not account for the Husky’s differential drive, which makes high-speed turning difficult in the simulation.Source: B. Complex navigation scenario · p. 13

VIII. CONCLUSIONS

  • The conclusion reports safety guarantees and a systematic way to achieve them without manually tuning parameters.It also states that the proposed scheme dynamically adapts the cost of safety in the navigation results.Source: §VIII · p. 13

APPENDIX

The appendix proves Lemma 1 through probability bounds and establishes that the set C used in Lemma 2 is nonempty and convex. The convexity argument uses the convexity of the induced occupation-measure set.

A. Proof of Lemma 1

  • The proof of Lemma 1 bounds a probability expression by truncating a sum of nonnegative terms, using non-increasing μ_t, and applying the Boole–Fréchet–Bonferroni inequality.The supplied proof passages describe these steps but do not state the lemma’s full conclusion.Source: A. Proof of Lemma 1 · p. 13

B. Proof of Lemma 2

  • For Lemma 2, convex combinations of occupation measures correspond to policies whose value and constraint quantities preserve the required bounds.The proof relies on the convexity and compactness of the set of occupation measures.Source: B. Proof of Lemma 2 · p. 13
  • The proof establishes that C is convex and nonempty, using the feasible policy that solves problem (23) to show nonemptiness.For convexity, it considers convex combinations of points in C and policies satisfying their associated value and constraint bounds.Source: B. Proof of Lemma 2 · pp. 13–14

C. Proof of Lemma 3

The proof bounds a discounted sum by relating its first term to the same expression multiplied by the discount factor. A geometric-series calculation then yields a bound proportional to ε/(1−γ).

C. Proof of Lemma 3

  • The proof first upper-bounds the expression using the triangle inequality and reduces the task to bounding the difference between the distributions.It then uses the triangle inequality again to bound that difference.Source: C. Proof of Lemma 3 · p. 14
  • The density property of the policy distributions makes one term integrate to one, while the difference is zero at t = 0.The proof uses these facts to bound the remaining integral terms.Source: C. Proof of Lemma 3 · p. 14
  • The geometric-series term yields the bound ε/(1−γ) for the expression in the proof.The argument identifies the first term as the left-hand expression multiplied by γ, then rearranges.Source: C. Proof of Lemma 3 · p. 14

D. Proof of Theorem 4 θ

The proof compares parameterized and unrestricted duals, then uses an ε-perturbed feasible problem to control approximation effects. Bounded rewards support the value argument, while constraint functions are treated analogously.

D. Proof of Theorem 4 θ

  • For every multiplier, the parameterized Lagrangian dual is no larger than the unrestricted dual because its maximizers form a subset.This comparison is used alongside weak duality in the proof.Source: D. Proof of Theorem 4 · p. 14
  • The proof reduces the remaining bound to a perturbed problem with ξ_i=ε/(1−γ); if it is infeasible, its dual optimum is infinite and the claim is immediate.Source: D. Proof of Theorem 4 · p. 14
  • In the feasible case, the proof uses a convex nonempty set with Ui(π)≥ci+ε/(1−γ)+ξ_i and places the optimal-policy value point in that set.Source: D. Proof of Theorem 4 · pp. 14–15
  • The value argument uses corresponding occupancy measures and bounded rewards for an ε-approximating policy; the constraint argument proceeds analogously with Ui.Source: D. Proof of Theorem 4 · p. 15
Loading 1911.09101v2…