Trust Region Policy Optimization

考虑一个无限长度的马尔科夫决策过程（MDP） $(\mathcal{S},\mathcal{A},P,r,\rho_0,\gamma)$ , 其中， $\mathcal{S}$ 是关于状态的有限集， $\mathcal{A}$ 是关于动作的有限集， $P:\mathcal{S}\times\mathcal{A}\times\mathcal{S}$ 是条件转移概率分布， $r:\mathcal{S}\rightarrow R$ 是奖励函数， $\rho_0:\mathcal{S}\rightarrow R$ 是初始状态的分布， $\gamma\in(0,1)$ 是折扣因子。

令 $\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ 为随机策略， $\eta(\pi)$ 为期望折扣奖励： $$ \eta(\pi)=E_{s_0,a_0,\dots}\left[ \sum_{t=0}^{\infty}\gamma^{t}r(s_t) \right] $$

其中， $s_0\sim\rho_0(s_0),a_t\sim\pi(a_t|s_t),s_{t+1}\sim P(s_{t+1}|s_t,a_t)$

定义状态-动作值函数 $Q_{\pi}$ ，值函数 $V_{\pi}$ ，奖励函数 $A_{\pi}$ ：

\begin{array}{l} Q_π≤ft(s_t, a_t\right)=\mathbb{E}_{s_t+1, a_t+1, \ldots}≤ft[∑_l=0^∞ γ^l r≤ft(s_t+l\right)\right]
V_π≤ft(s_t\right)=\mathbb{E}_{a_t, s_t+1, \ldots}≤ft[∑_l=0^∞ γ^l r≤ft(s_t+l\right)\right]
A_π(s, a)=Q_π(s, a)-V_π(s), \text { where }
a_t ∼ π≤ft(a_t \mid s_t\right), s_t+1 ∼ P≤ft(s_t+1 \mid s_t, a_t\right) \text { for } t ≥ 0

\end{array}

下面这个式子表示随着步长积累的另一个策略 $\tilde{\pi}$ 与当前策略 $\pi$ 的关系：

\begin{equation} \eta(\tilde{\pi})=\eta(\pi)+E_{s_0,a_0,\dots\sim\tilde{\pi}}\left[ \sum_{t=0}^{\infty}\gamma^{t}A_{\pi}(s_t,a_t) \right] \end{equation}

上面的期望表明动作是取样自 $a_t\sim\tilde{\pi}(\cdot|s_t)$ 。

证明如下： $

\begin{split} &\mathbb{E}_{\tau \sim \tilde{\pi}}\left[\sum_{t=0}^{\infty} \gamma^{t} A_{\pi}\left(s_{t}, a_{t}\right)\right] \\ &=\mathbb{E}_{\tau \sim \tilde{\pi}}\left[\sum_{t=0}^{\infty} \gamma^{t}\left(r\left(s_{t}\right)+\gamma V_{\pi}\left(s_{t+1}\right)-V_{\pi}\left(s_{t}\right)\right)\right] \\ &=\mathbb{E}_{\tau \sim \tilde{\pi}}\left[-V_{\pi}\left(s_{0}\right)+\sum_{t=0}^{\infty} \gamma^{t} r\left(s_{t}\right)\right] \\ &=-\mathbb{E}_{s_{0}}\left[V_{\pi}\left(s_{0}\right)\right]+\mathbb{E}_{r \mid \tilde{\pi}}\left[\sum_{t=0}^{\infty} \gamma^{t} r\left(s_{t}\right)\right] \\ &=-\eta(\pi)+\eta(\tilde{\eta}) \end{split}

$

令 $\rho_{\pi}$ 表示状态的折扣访问频率： $$ \rho_{\pi}(s)=P(s_0=s)+\gamma P(s_1=s)+\gamma^2 P(s_2=s)+\dots $$

其中， $s_0\sim\rho_0$ ，动作取样自 $\pi$ 。

将等式（1）展开：

\begin{equation} \begin{aligned} \eta(\tilde{\pi}) &=\eta(\pi)+\sum_{t=0}^{\infty} \sum_{s} P\left(s_{t}=s \mid \tilde{\pi}\right) \sum_{a} \tilde{\pi}(a \mid s) \gamma^{t} A_{\pi}(s, a) \\ &=\eta(\pi)+\sum_{s} \sum_{t=0}^{\infty} \gamma^{t} P\left(s_{t}=s \mid \tilde{\pi}\right) \sum_{a} \tilde{\pi}(a \mid s) A_{\pi}(s, a) \\ &=\eta(\pi)+\sum_{s} \rho_{\tilde{\pi}}(s) \sum_{a} \tilde{\pi}(a \mid s) A_{\pi}(s, a) \end{aligned} \end{equation}

从上式可以看出，如果每次策略的更新 $\pi\rightarrow\tilde{\pi}$ 中，每个状态 $s$ 都有非负期望优势 $A$ ，即 $\sum_{a}\tilde{\pi}(a|s)A_{\pi}(s,a)\geq0$ ，那么就可以确保策略的期望回报是不断增加的。但是在训练过程中，我们很难保证 每个状态的期望优势都是非负的。由于 $\rho_{\tilde{\pi}}(s)$ 使等式二变得更复杂，因此我们做第一次近似： $$ L_{\pi}(\tilde{\pi})=\eta(\pi)+\sum_{s}\rho_{\pi}(s)\sum_{a}\tilde{\pi}(a|s)A_{\pi}(s,a) $$

$L_{\pi}$ 忽视了由于策略改变引起的状态访问频率的变化，那么我们可以保证对 $L_{\pi}$ 的优化等同于对 $\eta$ 的优化吗？

可以发现：

\begin{aligned} L_{\pi_{\theta_{0}}}\left(\pi_{\theta_{0}}\right) &=\eta\left(\pi_{\theta_{0}}\right) \\ \left.\nabla_{\theta} L_{\pi_{\theta_{0}}}\left(\pi_{\theta}\right)\right|_{\theta=\theta_{0}} &=\left.\nabla_{\theta} \eta\left(\pi_{\theta}\right)\right|_{\theta=\theta_{0}} \end{aligned}

即，在 $\pi_{\theta_0}$ 作一个很小的改变，如果提高 $L_{\pi}$ ，那么也会提高 $\eta$ 。 但这个式子并没有给出步长应该走多少。

为了解决这个问题，Kakade 和 Langford 给出了一个策略更新方法——conservative policy iteration， 提供了一个能够提高 $\eta$ 的明确的下限。 令 $\pi_{old}$ 表示当前策略， $\pi^{\prime}=\arg\max_{\pi^{\prime}}L_{\pi_{old}}(\pi^{\prime})$ ， 新的策略为： $$ \pi_{new}(a|s)=(1-\alpha)\pi_{old}(a|s)+\alpha\pi^{\prime}(a|s) $$

下限为：

\begin{equation} \begin{aligned} \eta\left(\pi_{\text {new }}\right) & \geq L_{\pi_{\text {old }}}\left(\pi_{\text {new }}\right)-\frac{2 \epsilon \gamma}{(1-\gamma)^{2}} \alpha^{2} \\ & \text { where } \epsilon=\max _{s}\left|\mathbb{E}_{a \sim \pi^{\prime}(a \mid s)}\left[A_{\pi}(s, a)\right]\right| \end{aligned} \end{equation}

等式（3）表明，对等式右边的提升可以确保左边的提升。 我们的主要理论结果是，通过用 $\pi$ 和 $\tilde{\pi}$ 之间的距离替换 $\alpha$ ，并适当更改常数 $\varepsilon$ 使 等式（3）中策略改进范围扩展到一般随机策略，而不仅仅是混合策略（ $\pi_(new)$ ）。 我们使用 total variation divergence 来衡量两个策略之间的距离。对于离散环境， $D_{TV}(p||q)=\frac{1}{2}\sum_{i}|p_i-q_i$ ， 连续环境中使用密度函数。

$$ D_{TV}^{\max}=\max_{s}D_{TV}(\pi(\cdot|s)||\tilde{\pi}(\cdot|s)) $$

可以发现 TV 散度和 KL 散度之间的关系为： $D_{TV}(p||q)^2\leq D_{KL}(p||q)$ 。 令 $D_{KL}^{\max}(\pi,\tilde{\pi})=\max_{s}D_{KL}(\pi_(\cdot|s)||\tilde{\pi}(\cdot|s))$ ， 等式（4）可以写成：

\begin{equation} \begin{aligned} \eta(\tilde{\pi}) & \geq L_{\pi}(\tilde{\pi})-C D_{\mathrm{KL}}^{\max }(\pi, \tilde{\pi}) \\ & \text { where } C=\frac{4 \epsilon \gamma}{(1-\gamma)^{2}} \end{aligned} \end{equation}

算法 1 描述了基于等式（5）的策略梯度更新算法：

使用算法 1 可以使策略回报随着时间变化而递增， $\eta(\pi_0)\leq\eta(\pi_2)\leq\dots$ ， 令 $M_{i}(\pi)=L_{\pi_i}(\pi)-CD_{KL}^{\max}(\pi_i,\pi)$ ，

\begin{equation} \begin{split} &\eta(\pi_{i+1}\geq M_{i}(\pi_{i+1}))\quad by\quad Equation\quad (5) \\ &\eta(\pi_i)=M_{i}(\pi_i),\quad therefore, \\ &\eta(\pi_{i+1})-\eta(\pi_{i})\geq M_{i}(\pi_{i+1})-M(\pi_i) \end{split} \end{equation}

通过在每一步最大化 $M_i$ ，我们可以确保目标 $\eta$ 是非递减的。

接下来介绍的 TRPO 算法是算法 1 的近似，通过对 KL 散度加约束而不是使用它作为惩罚项， 来获得最大程度的更新。