Trust Region Policy Optimization

Abstract

1. Introduction

2. Preliminaries

考虑一个 Infinite-Horizon 的带折扣 MDP $(\mathcal{S},\mathcal{A},P,r,{\rho }_0,\gamma )$，其中 $\mathcal{S}$ 是有限状态集，$\mathcal{A}$ 是有限动作集，$P:\mathcal{S}\times \mathcal{A}\times \mathcal{S}\to \mathbb{R}$ 是转移概率分布，$r:\mathcal{S}\to \mathbb{R}$ 是奖励函数，${\rho }_0:\mathcal{S}\to \mathbb{R}$ 是初始状态 $s_0$ 的分布，并且 $\gamma \in (0,1)$ 是折扣因子。

对于策略 $\pi :\mathcal{S}\times \mathcal{A}\to [0,1]$，其期望折扣奖励定义为

$$\eta (\pi )={\mathbb{E}}_{s_0,a_0,\dots }\left[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)\right]$$

这里 $s_0,a_0,\dots$ 为 $\pi$ 生成的一个无限长的轨迹，类似可以定义价值函数 $V_{\pi }$、动作-价值函数 $Q_{\pi }$ 和优势函数 $A_{\pi }$。可以证明，对于任意两个策略 $\pi$ 和 $\tilde{\pi }$，我们可以使用优势函数估计两个策略期望回报的差距：

$$\eta (\tilde{\pi })-\eta (\pi )={\mathbb{E}}_{\tau \sim \tilde{\pi }}\left[\sum _{t=0}^{\infty }{\gamma }^t{A}_{\pi }(s_t,a_t)\right]\text{\hspace{1em}(1)}$$

Proof

注意到 $A_{\pi }(s,a)={\mathbb{E}}_{s^{\prime }\sim P(\cdot \mid s,a)}[r(s)+\gamma V_{\pi }(s^{\prime })-V_{\pi }(s)]$。我们可以有下面估计

$$\begin{array}{rl}{\mathbb{E}}_{\tau \sim \tilde{\pi }}\left[\sum _{t=0}^{\infty }{\gamma }^t{A}_{\pi }(s_t,a_t)\right]& ={\mathbb{E}}_{\tau \sim \tilde{\pi }}\left[\sum _{t=0}^{\infty }{\gamma }^t(r(s_t)+\gamma V_{\pi }(s_{t+1})-V_{\pi }(s_t))\right]\\ & ={\mathbb{E}}_{\tau \sim \tilde{\pi }}\left[-V_{\pi }(s_0)+\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)\right]\\ & =-{\mathbb{E}}_{s_0}[V_{\pi }(s_0)]+{\mathbb{E}}_{\tau \sim \tilde{\pi }}\left[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)\right]\\ & =-\eta (\pi )+\eta (\tilde{\pi })\end{array}$$

如果定义 $\bar{A}(s)$ 为状态 $s$ 下 $\tilde{\pi }$ 相对于 $\pi$ 的预期优势：

$$\bar{A}(s)={\mathbb{E}}_{a\sim \tilde{\pi }(\cdot \mid s)}[A_{\pi }(s,a)].$$

那么，式 (1) 可以写成如下形式：

$$\eta (\tilde{\pi })=\eta (\pi )+{\mathbb{E}}_{\tau \sim \tilde{\pi }}\left[\sum _{t=0}^{\infty }{\gamma }^t\bar{A}(s_t)\right]\text{\hspace{1em}(2)}$$

如果给出一个（未归一化的）折扣状态访问频率 ${\rho }_{\pi }$，我们就可以重写期望 ${\mathbb{E}}_{\tau \sim \tilde{\pi }}[\sum {\gamma }^t{A}_{\pi }(s_t,a_t)]$：

$$\begin{array}{rl}{\rho }_{\pi }(s)& =P(s_0=s)+\gamma P(s_1=s)+{\gamma }^{2}P(s_2=s)+\dots ,\\ \eta (\tilde{\pi })& =\eta (\pi )+\sum _{t=0}^{\infty }\sum _{s}P(s_t=s\mid \tilde{\pi })\sum _a\tilde{\pi }(a\mid s){\gamma }^t{A}_{\pi }(s,a)\\ & =\eta (\pi )+\sum _s\sum _{t=0}^{\infty }{\gamma }^{t}P(s_t=s\mid \tilde{\pi })\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{array}\text{\hspace{1em}(3)}$$

如果对于一个策略更新 $\pi \to \tilde{\pi }$，$\tilde{\pi }$ 在每个状态 $s$ 处都具有非负的期望优势 ${\sum }_a\tilde{\pi }(a\mid s)A_{\pi }(s,a)\ge 0$，那么这个策略更新就一定可以保证可以提升策略性能 $\eta$，就算这个期望更新在所有状态都为零也可以保持策略性能恒定。这就可以保证经典的策略迭代成立了，如果使用确定性策略 $\tilde{\pi }(s)={\mathrm{argmax}}_a{A}_{\pi }(s,a)$，且至少存在一个状态-动作对 $(s,a)$ 使得 $A_{\pi }(s,a)>0$ 且 $P(s\mid \tilde{\pi })>0$，那么策略就一定会提升，否则算法就已经收敛到最优策略了。

但是，在近似情形/Approximate Setting 下，由于目标和更新都不是精确的，通常会出现估计误差和近似误差，要么是通过采样/时序差分得到的 $A_{\pi }$ 不精确，要么是 $\tilde{\pi }$ 不是贪心的，或者两者兼而有之，因此对某些状态 $s$ 来说，有可能出现 ${\sum }_a\tilde{\pi }(a\mid s)A_{\pi }(s,a)<0$，这是不可避免的。因此我们需要考虑使用策略梯度。

另一方面，式 (3) 中的 ${\rho }_{\tilde{\pi }}$ 对 $\tilde{\pi }$ 的依赖过于复杂，如果直接使用策略梯度，那就必须要对 ${\rho }_{\tilde{\pi }}$ 进行求导，还得对新分布采样，这就极其复杂。因此我们将 (3) 内的 ${\rho }_{\tilde{\pi }}$ 冻结为旧分布 ${\rho }_{\pi }$，忽略由于策略变化而引起的状态访问密度的变化，从而切断上述复杂依赖，得到 $\eta$ 的局部近似

$$L_{\pi }(\tilde{\pi })=\eta (\pi )+\sum _s{\rho }_{\pi }(s)\sum _a\tilde{\pi }(a\mid s)A_{\pi }(s,a).\text{\hspace{1em}(4)}$$

很容易知道，如果 ${\pi }_{\theta }$ 是一个参数的策略，${\pi }_{\theta }(a\mid s)$ 可微，其实 $L_{\pi }$ 和 $\eta$ 在旧点处是一阶等价的，也就是对于任意的参数 ${\theta }_0$，都有

$$\begin{array}{rl}{L}_{{\pi }_{{\theta }_0}}({\pi }_{{\theta }_0})& =\eta ({\pi }_{{\theta }_0}),\\ {{\nabla }_{\theta }{L}_{{\pi }_{{\theta }_0}}({\pi }_{\theta })|}_{\theta ={\theta }_0}& ={{\nabla }_{\theta }\eta ({\pi }_{\theta })|}_{\theta ={\theta }_0}.\end{array}\text{\hspace{1em}(5)}$$

Supplementary

第一个是显然的，第二个可以直接证明：

$$\begin{array}{rl}{\nabla }_{\theta }{L}_{{\pi }_{{\theta }_0}}({\pi }_{\theta })& ={\nabla }_{\theta }\left(\eta ({\pi }_{{\theta }_0})+\sum _s{\rho }_{{\pi }_{{\theta }_0}}(s)\sum _a{\pi }_{\theta }(a\mid s)A_{{\pi }_{{\theta }_0}}(s,a)\right)\\ & =\sum _s{\rho }_{{\pi }_{{\theta }_0}}(s)\sum _a{\nabla }_{\theta }{\pi }_{\theta }(a\mid s)A_{{\pi }_{{\theta }_0}}(s,a)\\ {\nabla }_{\theta }\eta ({\pi }_{\theta })& ={\nabla }_{\theta }\left(\eta ({\pi }_{{\theta }_0})+\sum _s{\rho }_{{\pi }_{\theta }}(s)\sum _a{\pi }_{\theta }(a\mid s)A_{{\pi }_{{\theta }_0}}(s,a)\right)\\ & =\sum _s\left({\nabla }_{\theta }{\rho }_{{\pi }_{\theta }}(s)\sum _a{\pi }_{\theta }(a\mid s)A_{{\pi }_{{\theta }_0}}(s,a)+{\rho }_{{\pi }_{\theta }}(s)\sum _a{\nabla }_{\theta }{\pi }_{\theta }(a\mid s)A_{{\pi }_{{\theta }_0}}(s,a)\right)\\ & =\sum _s{\rho }_{{\pi }_{\theta }}(s)\sum _a{\nabla }_{\theta }{\pi }_{\theta }(a\mid s)A_{{\pi }_{{\theta }_0}}(s,a)\end{array}$$

这就表明，可以改善 $L_{{\pi }_{{\theta }_{old}}}$ 的一个充分小的更新 ${\pi }_{{\theta }_0}\to \tilde{\pi }$

Appendix: Conservative Policy Iteration