Sample-based constrained policy optimization update

Assume the Axiom of Choice for the theoretical average-KL comparison, and let a finite discounted CMDP have cost signals $c_1,\dots ,c_m$ with thresholds $b_1,\dots ,b_m$. Let $\theta \mapsto {\pi }_{\theta }$ be a stationary policy family on an open set $U\subseteq {\mathbb{R}}^d$ with fixed common support, where $d\ge 1$ and the current parameter ${\theta }_k$ lies in $U$. Assume its policy coordinates are twice continuously differentiable on a neighborhood of ${\theta }_k$. Choose a trust radius $\delta >0$, a backtracking factor $\beta \in (0,1)$, and a finite backtracking budget $L\ge 0$. At iteration $k$, the finite data batch consists of $N\ge 1$ rows $(s_j,a_j,{\omega }_j,{\widehat{A}}_j^r,{\widehat{A}}_{1,j}^c,\dots ,{\widehat{A}}_{m,j}^c)$ from trajectories generated in the CMDP under the current policy ${\pi }_{{\theta }_k}$, where ${\omega }_j\ge 0$, ${\sum }_j{\omega }_j=1$, and ${\pi }_{{\theta }_k}(a_j\mid s_j)>0$. The advantage estimates are real numbers held fixed during the update, and the batch also includes real baseline-cost estimates ${\widehat{J}}_{i,k}$. The weights and estimates may come from any fixed rollout or critic estimator; this procedure assumes no accuracy property for them. It specifies the exact finite-data trust-region subproblem and line search; implementations that approximate the subproblem solve are discussed separately.

For every $\theta \in U$, define the finite sample surrogates

${\widehat{L}}_r(\theta ):={\sum }_{j=1}^N{\omega }_j(\frac{{\pi }_{\theta }(a_j\mid s_j)}{{\pi }_{{\theta }_k}(a_j\mid s_j)}-1){\widehat{A}}_j^r,{\widehat{L}}_i^c(\theta ):={\sum }_{j=1}^N{\omega }_j(\frac{{\pi }_{\theta }(a_j\mid s_j)}{{\pi }_{{\theta }_k}(a_j\mid s_j)}-1){\widehat{A}}_{i,j}^c\mathrm{.}$

and $\widehat{K}(\theta ):={\sum }_j{\omega }_j{D}_{\mathrm{K}\mathrm{L}}({\pi }_{\theta }(\cdot \mid s_j)\mathrm{\parallel }{\pi }_{{\theta }_k}(\cdot \mid s_j))$. Put $g=\mathrm{\nabla }{\widehat{L}}_r({\theta }_k)$, $u_i=(1-\gamma {)}^{-1}\mathrm{\nabla }{\widehat{L}}_i^c({\theta }_k)$, $H={\mathrm{\nabla }}^2\widehat{K}({\theta }_k)$, and $q_i={\widehat{J}}_{i,k}-b_i$. The update procedure is:

1. If $H$ is not symmetric, or if some nonzero $x\in {\mathbb{R}}^d$ satisfies $x^{T}Hx\le 0$, return no-step. Otherwise form the local quadratic program

   ${\max }_{x\in {\mathbb{R}}^d}{g}^{T}x\text{subject to}{q}_i+u_i^{T}x\le 0(i=1,\dots ,m),\frac{1}{2}{x}^{T}Hx\le \delta \mathrm{.}$

2. If this program is feasible, let $x^{\ast }$ be its lexicographically least global maximizer. The feasible set is a closed subset of the compact ellipsoid, so the maximizer set is nonempty and compact. Minimize the first coordinate on that set, restrict to its nonempty compact minimizers, and repeat for each coordinate; the resulting point is the lexicographically least maximizer. If the program is infeasible and $m=1$, compute $v=H^{-1}{u}_1$. If $u_1=0$, return no-step, since the linearized cost cannot be reduced. Otherwise $u_1^{T}v>0$ by positive definiteness, and use the cost-recovery proposal $x^{\ast }=-\sqrt{2\delta \mathrm{/}(u_1^{T}v)}v$. If the program is infeasible and $m>1$, return no-step.

3. For $j=0,\dots ,L$, set ${\theta }_j={\theta }_k+{\beta }^j{x}^{\ast }$. Accept the first ${\theta }_j$ in the policy family's parameter domain for which $\widehat{K}({\theta }_j)\le \delta$ and every sample cost estimate ${\widehat{J}}_{i,k}+(1-\gamma {)}^{-1}{\widehat{L}}_i^c({\theta }_j)$ is at most $b_i$. If no candidate passes this sample check, return no-step; otherwise output the accepted parameter as ${\theta }_{k+1}$.

For finite constants $D_i\ge 0$, optional nonnegative bounded transition signals ${\mathrm{\Delta }}_i:\mathcal{X}\to [0,D_i]$ may be included in the supplied cost-advantage and baseline estimates by estimating the shaped costs $c_i+{\mathrm{\Delta }}_i$. The exact theorem concerns exact policies and expectations; the line search above checks only the supplied sample estimates.

Every family of nonempty sets has a choice function; AC is required for the theorem's KL branch.

The finite CMDP model and bounded transition signals.

The expected discounted cost and its threshold.

The value and advantage quantities estimated by the supplied critic.

A differentiable stationary policy family with fixed common support and score vectors.

The Hessian matrix is the matrix of second partial derivatives of a scalar function on an open Euclidean domain.

Directional KL uses natural logarithms and is infinite when the first action law is not absolutely continuous with respect to the second.

The state distribution targeted by the discounted sample weights.

The exact policy-return bound that motivates the trust-region constraint; its KL branch assumes AC.

Achiam et al., Constrained Policy Optimization, §5.3 and §§6.1–6.3.