First Order Constrained Optimization in Policy Space

1 Introduction

• Reward-focused exploration does not account for harmful behavior, such as robot maneuvers that may damage the robot or harm nearby people.The paper frames RL safety as important for real-world applications.Source: §1 · p. 1
• Taylor approximations in prior constrained policy updates can produce infeasible updates that require recovery or backtracking, wasting samples.The introduction notes that backtracking can occur as part of those recovery steps.Source: §1 · p. 2
• FOCOPS finds a constrained optimal update in nonparameterized policy space, then projects it into the parameterized policy space using samples from the current policy.The method has an approximate upper bound on worst-case constraint violation throughout training.Source: §1 · p. 2
• FOCOPS empirically outperforms state-of-the-art approaches, including second-order CPO, while maintaining approximate constraint satisfaction on high-dimensional continuous-control tasks.The paper describes the approach as simple to implement because it uses only first-order approximations.Source: §1 · p. 2

2.1 Constrained Markov Decision Process

• A CMDP adds cost constraints to an MDP, and its objective is to maximize expected discounted return over policies whose cost returns stay within their bounds.The setup restricts the discussion to one cost function, while noting that the method can be extended to multiple constraints.Source: §2.1 · p. 2

2.2 Solving CMDPs via Local Policy Search

• Local policy search limits policy changes to a region around the current policy; CPO uses a surrogate cost constraint based on current-policy samples and Taylor approximations.For high-dimensional policy parameters, the resulting optimization is difficult to solve directly and CPO uses first- and second-order approximations.Source: §2.2 · pp. 2–3
• CPO’s sampling, Taylor, and Fisher-matrix approximation errors can necessitate recovery steps, while FOCOPS is presented as eliminating the latter two error sources.Earlier high-dimensional primal-dual and penalized-reward approaches have convergence results, but the cited methods do not guarantee constraint satisfaction during training.Source: §2.2 · p. 3, §2.3 · p. 3

2.3 Related Work

• PCPO also uses a two-step projection approach but relies on second-order approximations in both steps, whereas FOCOPS is first-order.The text says PCPO’s empirical results do not consistently outperform CPO.Source: §2.3 · pp. 3–4
• FOCOPS applies a primal-dual optimization view to a cost-constrained trust-region problem, then projects the solution into the parameterized policy space.The paper describes this as the first application of these ideas to cost-constrained RL, to the authors’ knowledge.Source: §2.3 · p. 4

3.1 Finding the Optimal Update Policy

• For any feasible current policy, the optimal update has a near-closed-form solution and an approximate bound on worst-case cost-constraint violation.The policy assigns probability mass to high-return state-action pairs, offset by a penalty proportional to their cost advantage.Source: §3.1 · p. 4

3.2 Approximating the Optimal Update Policy

• FOCOPS projects the nonparameterized optimal update into the parameterized policy class by minimizing a loss with a first-order gradient.The gradient can be estimated from trajectories generated by the current policy, enabling stochastic-gradient training.Source: §3.2 · p. 5

3.3 Practical Implementation

• The dual problem can be computationally impractical in large state/action spaces because it requires calculating a partition function that may involve a high-dimensional integral or sum.The dual variables λ and ν also need to be adapted at every iteration.Source: §3.3 · p. 5
• λ controls the update policy’s exploration: it approaches greedy behavior as λ tends to zero and becomes more exploratory as λ increases.The implementation uses a fixed λ selected through hyperparameter sweeps, while ν is continuously adapted to help ensure cost-constraint satisfaction.Source: §3.3 · p. 5
• The ν update increases the cost penalty when the current policy violates the constraint and decreases it otherwise; a per-state KL acceptance indicator rejects samples outside the trust region.The paper emphasizes that FOCOPS uses first-order methods and requires only gradient descent.Source: §3.3 · p. 6

4.1 Robots with Speed Limit

• FOCOPS outperforms baselines in reward on most speed-limit tasks while enforcing cost constraints, though TRPO-L violates the constraint by nearly 9% on HalfCheetah-v3.The comparison also notes that PPO-L deteriorates on the more challenging Ant-v3, HalfCheetah-v3, and Humanoid-v3 tasks.Source: §4.1 · p. 7, Figure 1 · p. 7, Table 1 · p. 8

4.2 Circle Tasks

• On both Circle tasks, all four approaches approximately satisfy the cost constraint set at 50, while FOCOPS achieves higher performance than the other algorithms.The reported 95% confidence intervals for FOCOPS lie above those of the other algorithms on both tasks.Source: §4.2 · p. 8, Figure 2 · p. 8, Table 2 · p. 9

4.3 Generalization Analysis

• On unseen random seeds, FOCOPS outperforms every other constrained algorithm on all speed-limit environments except Hopper-v3.The trained agent was tested on ten unseen random seeds after training on one fixed seed.Source: §4.3 · p. 9

4.4 Sensitivity Analysis

• Setting νmax = +∞ yields an average 0.3% performance degradation versus optimal νmax = 2, while other λ values perform on average 7.4% worse than optimal λ = 1.5.The paper reports that performance is largely insensitive to these hyperparameters.Source: §4.4 · p. 9

5 Discussion

• FOCOPS is presented as a simple, first-order approach that empirically outperforms more complex second-order methods and is easy to implement.The authors connect simplicity with making RL more accessible to researchers in other fields.Source: §5 · p. 9
• Future work includes off-policy data and constraints such as sample-path requirements, human preferences, and natural language.These are described as promising avenues rather than capabilities established in this work.Source: §5 · p. 9

6 Broader Impact

• Constraints offer a way to quantify safety requirements, whereas reward-only balancing risks either insufficient exploration or hazardous behavior.The authors advocate considering constraints in safety-critical RL systems.Source: §6 · p. 9

A Proof of Theorem 1

• The policy-space problem is convex: its objective and cost constraint are linear in the update policy, while its KL constraint is convex.A feasible current policy is an interior point for the KL constraint, so Slater’s condition yields strong duality.Source: A Proof of Theorem 1 · p. 13
• Strong duality lets the proof solve the problem through its dual, whose inner maximization decomposes into separate optimization problems for each state.The resulting statewise problem is treated as a convex optimization problem.Source: A Proof of Theorem 1 · p. 13
• A Lagrangian argument derives the optimal policy form; its partition function ensures a valid probability distribution, with λ and ν chosen by optimization.The proof introduces ζ as the multiplier for the action-probability normalization constraint.Source: A Proof of Theorem 1 · pp. 13–14

B Proof of Corollary 1

• The Corollary 1 proof derives the gradient by rewriting cross-entropy minus entropy as KL divergence and using importance sampling.Source: B Proof of Corollary 1 · pp. 14–15

C Proof of Corollary 2

• The Corollary 2 proof differentiates the expected term of L(π*, λ, ν) through π*’s dependence on ν, then combines it with the affine-term derivative.Source: C Proof of Corollary 2 · pp. 15–16

D.1 PPO-Lagrangian

• PPO-Lagrangian alternates maximizing and minimizing an augmented objective, but its performance degrades in harder environments and worst-case guarantees remain open.Source: §D.1 · p. 16

D.2 TRPO-Lagrangian

• TRPO-Lagrangian alternates TRPO maximization with ν minimization; it is second-order and performs poorly on constraint satisfaction.Source: §D.2 · p. 17

E FOCOPS for Different Cost Thresholds

• FOCOPS learns constraint-satisfying policies across thresholds set at 25%, 50%, and 75% of unconstrained PPO’s cost after 1 million samples.Figure 3 plots reward and cost returns against samples, with cost-threshold lines and bootstrap confidence intervals.Source: E FOCOPS for Different Cost Thresholds · p. 17, Figure 3 · p. 17

F Pseudocode

• The pseudocode initializes policy and value networks and parameters, then collects episodes from the current policy to estimate cost returns.Source: F Pseudocode · p. 18

G Implementation Details for Experiments

• Experiments used PyTorch 1.3.1 and Python 3.7.4 on Intel Xeon Gold 6230 processors; CPO used the authors’ own PyTorch implementation, while PPO, PPO Lagrangian, and TRPO Lagrangian used optimized PPO/TRPO implementations.Source: G Implementation Details for Experiments · pp. 18–19

G.1.1 Environment Details

• For straight-line speed-limit tasks, cost is the absolute x-direction velocity, C(s, a) = |vx|.Source: §G.1.1 · p. 19

G.1.2 Algorithmic Hyperparameters

• Speed-limit experiments used two-layer tanh policy and value networks with Gaussian policies, normalized states and advantages, and mostly annealed learning rates.The ν learning rate was fixed; νmax was tuned across six values, and the algorithms were reported as not especially sensitive to it.Source: §G.1.2 · p. 19

G.2.1 Environment Details

• Circle tasks require movement along a circle while staying inside a smaller safety region; the illustrated constrained path follows segments AD and BC.The Ant and Humanoid circle radius was 10, with xlim set to 3 and 2.5, respectively.Source: §G.2.1 · pp. 19–20, Figure 4 · p. 19

G.2.2 Algorithmic Hyperparameters

• Circle-task experiments used batch size 50000, minibatch size 1000 for PPO, PPO-Lagrangian, and FOCOPS, discount rate 0.995, and FOCOPS λ = 1.0 and δ = 0.04.Source: §G.2.2 · p. 20

• For each algorithm, the authors selected a seed with the highest maximum return that still met the cost constraint at training end, then tested on 10 unseen seeds.Source: H Generalization Analysis · pp. 20–21
• FOCOPS outperformed the other three algorithms on five of six speed-limit and circle tasks when tested on unseen seeds.Table 4 reports average returns over 10 episodes on 10 unseen random seeds, with bootstrap means and normal 95% confidence intervals.Source: H Generalization Analysis · p. 21, Table 4 · p. 21

• FOCOPS was largely insensitive to hyperparameter choices, especially νmax, though more challenging environments such as Humanoid were more sensitive.The study tested 10 λ values and five νmax values over 1 million samples per speed-limit environment.Source: I Sensitivity Analysis · p. 21