Constrained RL(一)：策略优化理论

在真实世界中，智能体的探索通常有约束的，因为有些行为会产生较大的成本。同时，对于多目标的智能体来说，待满足的目标之间属于冲突的，那么就可以把其转化为有约束的优化问题，从而更好的解决问题。然而，《Constrained Policy Optimization》之前，CRL主要适用于低维空间。那么，CPO提出了什么方法，从而解决高维控制问题呢？

有约束的马尔科夫决策过程

在MDP基础之上，CMDP增加了辅助成本函数集合$C$和限度$d_1,\ldots,d_m$。其中，成本函数集中每个函数$C_i:S\times A\times S\to\mathbb{R}$。若$J_{C_i}(\pi)$表示成本函数$C_i$的平均折扣回报$J_{C_i}(\pi)=\underset{\tau\sim\pi}{E}[\sum_{t=0}^{\infty}\gamma^tC_i(s_t,a_t,s_{t+1})]$，那么CMDP的可行静态策略集合为
$$
\begin{aligned}
\Pi_{C}=\{\pi\in\Pi:\forall i,J_{C_{i}}(\pi)\le d_i\}
\end{aligned}\tag{1}
$$
在CMDP数学模型下，RL的策略优化目标为
$$
\begin{aligned}
\pi^{*}=\underset{\pi\in\Pi_{C}}{argmax}J(\pi)
\end{aligned}\tag{2}
$$

辅助成本函数的价值函数、Q函数、以及优势函数分别表示为$V_{C_i}^{\pi},Q_{C_i}^{\pi},A_{C_i}(\pi)$

策略提升理论

在TRPO算法中，策略优化的目标为
$$
\begin{aligned}
\pi_{k+1}=\underset{\pi\in\Pi_{\theta}}{argmax}J(\pi) \\
s.t.~D(\pi,\pi_k)\le\delta
\end{aligned}\tag{3}
$$
其中，式(3)约束是为了保证策略迭代不发散。
对于有约束的策略优化，不仅要奖励提升，而且满足约束和策略迭代可行的约束。
$$
\begin{aligned}
\pi_{k+1}=\underset{\pi\in\Pi_{\theta}}{argmax}J(\pi) \\
s.t. J_{C_{i}}(\pi)\le d_i~i=1,\ldots,m\\
~D(\pi,\pi_k)\le\delta
\end{aligned}\tag{4}
$$
在TRPO的通用随机策略单调提升的理论基础上，CPO对Trust Region中两个随机策略之间回报的下界得到了tighten
由
$$
\begin{aligned}
\eta(\pi_{new})\ge L_{\pi_{old}}(\pi_{new})-\frac{2\epsilon\gamma}{(1-\gamma)^{2}}\alpha^2 \\
where~\epsilon=\underset{s}{max}\vert\mathbb{E}_{a\sim{\pi}'(a\vert s)}[A_{\pi}(s,a)]\vert
\end{aligned}\tag{5}
$$
变为
$$
\begin{aligned}
J(\pi_{k+1})-J(\pi_{k})\ge\frac{-\sqrt{2\delta}\gamma\epsilon^{\pi_{k+1}}}{(1-\gamma)^2} \\
where~\epsilon^{\pi_{k+1}}=max_{s}\vert E_{a\sim\pi_{k+1}}[A^{\pi_{k}}(s,a)]\vert
\end{aligned}\tag{6}
$$
该结果有两个优势：

• 有利于tighten理论与实践之间的连接
• CPO可继承TRPO的策略提升表现

有约束的策略优化方法

根据CPO的策略提升理论推导，对于合适的参数$\alpha_k,\beta_k^i$，策略更新
$$
\begin{aligned}
\pi_{k+1}=\underset{\pi\in\Pi_{\theta}}{argmax}\underset{\underset{a\sim\pi}{s\sim d^{\pi_{k}}}}{E}[A^{\pi_k}(s,a)-\alpha_k\sqrt{\bar{D}_{KL}(\pi\Vert\pi_k)}] \\
s.t.~J_{C_i}(\pi_k)+\underset{\underset{a\sim\pi}{s\sim d^{\pi_{k}}}}{E}[\frac{A_{C_i}^{\pi_{k}}(s,a)}{1-\gamma}]+\beta_k^{i}\sqrt{\bar{D}_{KL}(\pi\Vert\pi_k)}\le d_i
\end{aligned}\tag{7}
$$
由于该目标函数下的策略更新较小，为了增大更新步数，利用Trust Region
$$
\begin{aligned}
\pi_{k+1}=\underset{\pi\in\Pi_{\theta}}{argmax}\underset{\underset{a\sim\pi}{s\sim d^{\pi_{k}}}}{E}[A^{\pi_k}(s,a)] \\
s.t.~J_{C_i}(\pi_k)+\frac{1}{1-\gamma}\underset{\underset{a\sim\pi}{s\sim d_{\pi_k}}}{E}[A_{C_i}^{\pi_k}(s,a)]\le d_i~\forall i~\bar{D}_{KL}(\pi\Vert\pi_k)\le\delta
\end{aligned}\tag{10}
$$
对于该策略更新，最坏情况的约束违反，即$\pi_{k+1}$下$C_i$回报的上界为
$$
\begin{aligned}
J_{C_i}(\pi_{k+1})\le d_i+\frac{\sqrt{2\delta}\gamma\epsilon^{\pi_{k+1}}_{C_i}}{(1-\gamma)^2}
\end{aligned}
$$
该上界说明，最坏情况满足约束的策略属于常数量级的次优策略。

实际实现

为了解决近似、采样误差、以及潜在违反问题，通过约束辅助成本的方式进一步约束上界。
对于高维策略参数空间，直接求解式(10)是不实际的。然而，在较小的步长$\delta$下，目标函数和成本可被线形化$\pi_k$而近似，KL-Divergence可被其二阶展开而近似($\pi_k=\pi$下梯度及其本身为$0$)。若目标函数的梯度为$g$、约束$i$的梯度为$b_i$、KL-Divergence的Hessian矩阵为$H$，且定义$c_i=J_{C_i}(\pi_k)-d_i$，那么式(10)的近似为
$$
\begin{aligned}
\theta_{k+1}=\underset{\theta}{argmax}g^{T}(\theta-\theta_k) \\
s.t.~c_i+b_i^T(\theta-\theta_k)\le0~i=1,\ldots,m \\
\frac{1}{2}(\theta-\theta_k)^TH(\theta-\theta_k)\le\delta
\end{aligned}\tag{11}
$$
由于Fisher信息矩阵$H$总是半正定的，因此在特定情况下该优化问题是凸的，那么对偶问题为
$$
\begin{aligned}
\underset{\underset{v\ge0}{\lambda\ge0}}{max}\frac{-1}{2\lambda}(g^TH^{-1}g-2r^T+v^TSv)+v^Tc-\frac{\lambda\delta}{2}
\end{aligned}\tag{12}
$$
式中$B=[b_1,\ldots,b_m]$且$c=[c_1,\ldots,c_m]^T$，$r=g^TH^{-1}B,S=B^TH^{-1}B$。
若$\lambda^{*},v^{*}$为对偶的解，那么原问题的解为
$$
\begin{aligned}
\theta^{*}=\theta_k+\frac{1}{\lambda^{*}}H^{-1}(g-Bv^{*})
\end{aligned}\tag{13}
$$
由于近似误差的存在，策略的更新可能不满足约束，那么利用线搜索确保约束的满足。对于高维问题，Hessian矩阵的逆很难计算，因此采用共轭梯度近似计算。

对于非凸且约束条件个数为$1$的情况，可通过简单的减小约束值
$$
\begin{aligned}
\theta^{*}=\theta_{k}-\sqrt{\frac{2\delta}{b^{T}H^{-1}b}}H^{-1}b
\end{aligned}\tag{14}
$$
综上所述，CPO算法细节可见算法$1$。

One More Thing

由于式(3)与实际算法之间存在很多近似，因此对原约束施加上界约束，即
$$
\begin{aligned}
C_{i}^{+}(s,a,{s}')=C_i(s,a,{s}')+\Delta_i(s,a,{s}')
\end{aligned}\tag{15}
$$
式中$\Delta_i:S\times A\times S\to\mathbb{R}_{+}$，其表示在固定时间窗口内进入不安装状态的概率。