PaperlayerView exact revision on arXiv

Source-linked AI summary

Projection-Based Constrained Policy Optimization

Tsung-Yen Yang, Justinian Rosca, Karthik Narasimhan, Peter J. Ramadge

arXiv:2010.03152v1cs.LGcs.AIcs.RO

TL;DR

The paper addresses learning reward-optimizing control policies under safety, fairness, and cost constraints. It proposes PCPO, which first improves reward within a trust region and then projects the policy onto the constraint set, with theoretical update bounds and convergence analysis. Across control tasks, PCPO achieves fewer cumulative constraint violations and higher reward than prior approaches.

  • Problem

    Real-world control policies must optimize reward while satisfying safety, fairness, or other cost constraints, but direct optimization can violate constraints and existing alternatives can become infeasible or require extensive tuning.

  • Method

    PCPO performs a trust-region reward improvement update followed by projection of the intermediate policy onto the constraint set.

  • Results

    3.5 times fewer constraint violations and around 15% more reward were achieved across four control tasks than state-of-the-art methods.

  • Takeaways & Limitations

    PCPO maintains feasibility across updates while achieving comparable or superior reward and constraint satisfaction across the evaluated tasks.

  • Takeaways & Limitations

    Theoretical guarantees for feasible current policies do not cover constraint-violating policies, which can arise from approximation errors or random initialization.

Abstract

from arXiv · show

We consider the problem of learning control policies that optimize a reward function while satisfying constraints due to considerations of safety, fairness, or other costs. We propose a new algorithm, Projection-Based Constrained Policy Optimization (PCPO). This is an iterative method for optimizing policies in a two-step process: the first step performs a local reward improvement update, while the second step reconciles any constraint violation by projecting the policy back onto the constraint set. We theoretically analyze PCPO and provide a lower bound on reward improvement, and an upper bound on constraint violation, for each policy update. We further characterize the convergence of PCPO based on two different metrics: $\normltwo$ norm and Kullback-Leibler divergence. Our empirical results over several control tasks demonstrate that PCPO achieves superior performance, averaging more than 3.5 times less constraint violation and around 15\% higher reward compared to state-of-the-art methods.

1 INTRODUCTION

Constrained policy learning is needed when safety, fairness, or other costs restrict exploration, because direct reward optimization can violate constraints. PCPO addresses limitations of constrained optimization and penalty-based approaches with projected updates, achieving stronger empirical reward and constraint satisfaction.

  • Safety, fairness, and other costs restrict exploration in real-world control applications such as autonomous cars and unmanned aerial vehicles.
  • Direct reward optimization commonly violates constraints, while constrained optimization can become infeasible and penalty methods require extensive hyperparameter tuning.
  • PCPO performs reward improvement in a trust region, then projects any intermediate policy back onto the constraint set.
  • Projection enables constraint satisfaction without line search or penalty-weight adjustment and supports recovery from constraint-violating states.
  • PCPO derives per-update lower bounds on reward improvement and upper bounds on constraint violations, while analyzing convergence under two distance measures.
  • 3.5 times fewer constraint violations and around 15% more reward were achieved across four control tasks than state-of-the-art methods.

2 PRELIMINARIES

The paper formulates policy learning as a constrained Markov Decision Process in which policies maximize discounted reward while keeping discounted cost below a threshold. The formulation specifies states, actions, transitions, rewards, costs, and trajectory generation under a policy.

  • A constrained Markov Decision Process represents policy learning as maximizing reward while minimizing cost.
  • The CMDP is defined by states, actions, transition probabilities, reward functions, and cost functions.
  • The policy selects actions conditional on the current state, after which the environment transitions and produces reward and cost.
  • The objective is to maximize cumulative discounted reward while keeping cumulative discounted cost below a desired threshold.
  • Trajectory distributions depend on the policy through the initial-state distribution, action selection, and transition dynamics.
  • Policy performance is expressed using an advantage-function identity and discounted future state distributions.

3 PROJECTION-BASED CONSTRAINED POLICY OPTIMIZATION

PCPO combines trust-region reward improvement with projection onto the constraint set, using L2 or KL distance measures. Its KL-projection analysis provides per-update performance bounds and addresses both feasible and constraint-violating current policies.

  • PCPO update procedure: PCPO updates policies through a reward improvement step followed by a projection step onto the constraint set.
  • Reward improvement step: The reward step maximizes a reward-advantage objective subject to a KL-divergence trust-region constraint.
  • Projection step: The projection step chooses a constraint-satisfying policy close to the intermediate policy under a selected distance measure.
  • Projection step: PCPO considers L2 norm and KL divergence projections, with KL projection supporting provable guarantees in probability-distribution space.
  • Performance bounds: For feasible current policies, KL projection yields a lower bound on reward improvement and an upper bound on constraint violation for each update.
  • Performance bounds: When the reward-step size δ is small, the worst-case performance degradation is tolerable.
  • Performance bounds: Constraint-violating current policies can arise from approximation errors or random initialization, motivating separate worst-case degradation analysis.
  • Performance bounds: Theorem 3.2 shows that greater constraint violation increases worst-case performance degradation, while non-expansive projection supports the KL bound.

4 PCPO UPDATES

PCPO approximates its reward-improvement and projection updates for large policies, then analyzes how projection choice affects convergence and objective improvement.

  • Update approximation: Small-step PCPO uses first-order expansions for reward and constraints and second-order expansions for KL-based update and projection terms.These approximations make the updates computationally tractable for large neural-network policies.
  • Algorithm: Each iteration collects trajectories, computes g, a, H, and b, obtains the next policy parameters, and clears the trajectory data.Algorithm 1 describes this repeated update procedure.
  • Projection choices: PCPO supports L2 norm projection in parameter space and KL divergence projection in probability space.The projection choice changes the cost update direction and can produce different reward behavior.
  • Convergence: Both projection variants converge to stationary points inside the constraint set or on its boundary, with boundary conditions differing between KL and L2 projections.KL uses g = −αa, whereas L2 uses H^-1g = −αa.
  • Convergence: The Fisher information matrix’s singular values affect objective improvement and convergence rates, motivating adaptive projection selection.The analysis relates behavior to the smallest and largest singular values of H and its condition number.

5 RELATED WORK

PCPO builds on constrained policy learning and projection methods while addressing infeasibility that can arise in CPO’s simultaneous trust-region and constraint update.

  • Policy Learning with Constraints: Safe reinforcement learning commonly learns constraint-satisfying policies through environment exploration or expert demonstrations.PCPO uses trial-and-error exploration and projects onto the constraint set during learning.
  • Comparison to CPO: CPO simultaneously considers a trust region and constraint set, becoming infeasible when the current policy violates the constraint.Its update uses line search, while PCPO separates reward optimization from constraint projection.
  • Task context: The evaluated tasks include safety-constrained control environments and fairness-constrained traffic-management problems.The task set spans Gather, Circle, Grid, and Bottleneck.
  • Comparison to CPO: PCPO first optimizes reward and then projects to satisfy constraints, maintaining a feasible update solution.This contrasts with CPO’s simultaneous formulation and is intended to avoid slow progress from infeasible updates.

6 EXPERIMENTS

Experiments compare PCPO with CPO, PDO, FPO, and unconstrained TRPO across four safety and fairness control tasks, using reward and constraint-violation measures.

  • Tasks and baselines: The experiments cover four tasks: Gather and Circle with safety constraints, and Grid and Bottleneck with fairness constraints.The baselines are CPO, PDO, FPO, and unconstrained TRPO.
  • Evaluation: Figure 4 plots discounted reward and undiscounted constraint value over policy updates, with means and standard deviations over five runs.The constraint plots also show threshold h; TRPO curves represent ignoring constraints.
  • Overall Performance: PCPO improves reward while achieving the fastest constraint satisfaction across all tested tasks and is the only method learning satisfying policies in every task.CPO has more violations, PDO is conservative, and FPO requires substantial tuning of λ.
  • Constraint satisfaction: 85.15% and 5.42 times less constraint violation than CPO are achieved in Grid and Bottleneck, respectively.These tasks exhibit slightly more violation because of behavioral complexity and non-convex constraints.
  • Reward–constraint trade-off: 66 times and 15 times less constraint violation than CPO occur under the same reward improvement in point Circle and point Gather, respectively.Figure 5 compares discounted reward against cumulative constraint value.
  • Projection comparison: L2 projection is more constraint-satisfying, whereas KL projection tends to provide more stable reward improvement.L2 reward fluctuations appear in point Circle, ant Circle, and ant Gather.

7 CONCLUSION

The paper concludes that PCPO combines reward optimization with projections to maintain feasible updates, while projection choice affects convergence and future work targets adaptive selection.

  • Conclusion: PCPO optimizes reward while using projections to ensure constraint satisfaction and maintain feasibility at each update.The conclusion reports comparable or superior reward improvement and constraint satisfaction in all tested cases.
  • Conclusion: The convergence analysis indicates that different tasks may prefer KL divergence or L2 norm projection.Future work proposes using the Fisher information matrix to prescribe projection choice iteratively.
  • Future work: Future work also considers expert demonstrations or other domain knowledge to reduce sample complexity.This extends the proposed exploration-based approach with additional sources of guidance.

S.1 PROOF OF THEOREM 3.1: PERFORMANCE BOUND ON UPDATING THE CONSTRAINT-SATISFYING POLICY

For a constraint-satisfying current policy, the analysis bounds reward degradation and constraint violation after each KL-projection update. These bounds depend on the update step size and use a KL-divergence projection argument.

  • Proof strategy: The proof first establishes the KL divergence between πk and πk+1 for the KL-divergence projection.This projection result is then used to derive the policy-performance bound.
  • Performance bounds: Theorem 3.1 gives a lower bound on reward improvement and an upper bound on constraint violation for each policy update.The bounds apply when the current policy πk satisfies the constraint.
  • Performance bounds: The reward degradation bound for one update is 2δγϵπk+1 R /(1 −γ)^2.The expression depends on the step size δ, discount factor γ, and reward-advantage error term ϵπk+1 R.
  • Performance bounds: The constraint violation bound for one update is 2δγϵπk+1 C /(1 −γ)^2.The corresponding error term is the constraint-advantage error ϵπk+1 C.

S.2 PROOF OF THEOREM 3.2: PERFORMANCE BOUND ON UPDATING THE CONSTRAINT-VIOLATING POLICY

For a constraint-violating current policy, the proof analyzes KL projection onto a sublevel set and derives per-update reward and constraint bounds. It identifies new infeasible-case bounds and relates projection behavior to local policy geometry.

  • Proof strategy: The infeasible-policy analysis proves a KL-divergence relation between πk and πk+1 before deriving the worst-case performance degradation.The proof uses a separate lemma for policies that violate the constraint.
  • Projection step: The projection is onto the sublevel set of the cost constraint function defined for the current infeasible policy πk.The construction places the current policy and the projected policy in the relevant local set.
  • Assumptions: When the current constraint violation b+ is small, the analysis treats the infeasible policy as locally close to feasibility.Here b+ is defined as max(0, JC(πk) − h).
  • Novelty: The infeasible-case bounds are described as new results to the authors’ knowledge.The claim concerns the bounds obtained for constraint-violating current policies.

S.3 PROOF OF ANALYTICAL SOLUTION TO PCPO

The analytical solution treats PCPO as two constrained optimization problems: reward optimization followed by projection onto the constraint set. KKT conditions yield closed-form solutions under stated convexity and invertibility assumptions.

  • PCPO update: PCPO first optimizes the reward and then projects the resulting policy onto the constraint set.The two stages correspond to the reward improvement step and the constraint-reconciliation step.
  • Optimization problems: The first optimization uses a quadratic constraint with H, while the projection uses L, where L = H for KL divergence and L = I for the L2 norm.The variables satisfy g, a, θ ∈ Rn, b, δ ∈ R, and δ > 0.
  • Assumptions: The general projection analysis assumes a closed, convex constraint set and an L-smooth, twice continuously differentiable negative-reward objective.A unique solution additionally assumes H is invertible.
  • Optimality conditions: Because H is the Fisher Information matrix and positive semi-definite, the first problem is a convex program with quadratic inequality constraints.With a feasible point, Slater’s condition and strong duality apply, and KKT conditions characterize optimality.
  • Closed-form solutions: The KKT conditions express the first-step solution as θ∗ = θk + λ∗H^-1g.This expression assumes the relevant inverse exists.
  • Closed-form solutions: For the projection problem, the KKT derivation gives θ∗ = θk+1/2 − max(0, aT(θk+1/2 − θk) + b)/(aT L^-1a) L^-1a.The solution moves the intermediate policy toward the constraint set along the L^-1a direction.

S.4 PROOF OF THEOREM 4.1: STATIONARY POINTS OF PCPO WITH THE KL DIVERGENCE AND L2 NORM PROJECTIONS

The analysis characterizes stationary points for PCPO under KL-divergence and L2-norm projections, then relates projection choice to Fisher-matrix properties and empirical constraint–reward behavior.

  • Assumptions: The analysis assumes the negative reward objective is L-smooth and twice continuously differentiable over a closed, convex constraint set.The objective is minimized by convention in the theoretical analysis.
  • Stationary points: KL-divergence projection converges to stationary points satisfying g ∈ −a, where g is the objective gradient and a is the cost-advantage gradient.For KL projection, the metric matrix is H, the Fisher information matrix.
  • Stationary points: L2-norm projection converges to stationary points satisfying H−1g ∈ −a, with the stated objective-change result requiring σmax(H) ≤ 1.Here H is the Fisher information matrix and the L2 projection uses the identity metric.
  • Proof strategy: The proof works in a Hilbert space and uses the projection’s non-expansive property to establish stationary points and objective-value changes.The projection cannot increase the distance between unprojected policies.
  • Empirical findings: The Fisher information matrix can be ill-conditioned, making approximate H−1a inaccurate and causing KL-projection PCPO to incur more constraint violation than TRPO in the Grid task.More conjugate-gradient iterations reduce the approximation error and improve constraint satisfaction.
Loading 2010.03152v1…