CPO Trust Region Update

Context

Achiam2017 - Constrained Policy Optimization develops CPO for neural policy search in CMDPs. The reusable formal core is the move from a performance-difference bound to a trust-region update with surrogate cost constraints.

Formal Statement

For a CMDP with costs C_i and thresholds d_i, CPO updates from policy pi_k by approximately solving:

$${\pi }_{k+1}=\arg \underset{\pi }{\max }{E}_{s\sim d_{{\pi }_k},a\sim \pi }[A^{{\pi }_k}(s,a)]$$

subject to:

$$J_{C_i}({\pi }_k)+\frac{1}{1-\gamma }{E}_{s\sim d_{{\pi }_k},a\sim \pi }[A_{C_i}^{{\pi }_k}(s,a)]\le d_i,$$

for all costs i, and:

$${\bar{D}}_{KL}(\pi \Vert {\pi }_k)\le \delta .$$

The underpinning performance bound says that replacing the new state distribution with the old one is controlled by a divergence penalty. Pinsker’s inequality turns the average total-variation term into an average KL term. For costs, the analogous upper bound gives an approximate worst-case constraint-violation bound after a trust-region step.

Derivation / Construction

• Start from the performance-difference identity using the advantage under the old policy.
• Bound the distribution-shift error by an average divergence between the old and new action distributions.
• Use the lower bound for reward improvement and the upper bound for cost increase.
• Replace direct cost feasibility under pi with on-policy surrogate cost constraints under samples from pi_k.
• For neural policies, linearize reward and cost surrogates in parameters and quadratically approximate the KL constraint:

$$\underset{\theta }{\max }{g}^{\top }(\theta -{\theta }_k)$$

subject to:

$$c_i+b_i^{\top }(\theta -{\theta }_k)\le 0,\frac{1}{2}(\theta -{\theta }_k{)}^{\top }H(\theta -{\theta }_k)\le \delta .$$

• Use line search and, in the single-constraint case, an analytical solution/recovery step to handle approximation errors.

Implications

• CPO is safer during learning than primal-dual methods that only enforce constraints at convergence.
• The safety claim is still approximate: finite samples, local linearization, and neural parameterization can all weaken the formal bound.
• Cost shaping can tighten empirical adherence to the true cost constraint by optimizing a conservative upper-bound cost.
• The update is a useful single-agent reference point for MACPO Sequential Trust Region.

Links

• Source: Achiam2017 - Constrained Policy Optimization
• Concepts: Constrained Policy Optimization, Constrained Markov Decision Processes, Safe Reinforcement Learning