介绍

本文主要介绍Trust Region Policy Optimization这篇文章，这篇文章主要回答了如下2个问题：

1. 两个不同策略的value function，他们的差异是多少？
2. 有什么办法可以保证，一个策略相比于另外一个策略一定能够提升呢？

针对这两个问题，我们先定义一些基本的概念，

基本定义

下图是一个较为一般的强化学习MDP框架下的概率图模型

注意，这个图并不一定通用，特别是reward（比如$s_{t+1}$可以不指向$r_{t+1}$），可能是需要考虑具体场景，但这是一个较为一般化结构。基于此，我们有：

马尔科夫性质

$$P\left(S_{t+1}=s^{\prime },R_{t+1}=r^{\prime }\mid s_t,a_t,r_t,\dots ,r_1,s_0,a_0\right)=P\left(S_{t+1}=s^{\prime },R_{t+1}=r^{\prime }\mid s_t,a_t\right)$$

状态转移矩阵：

$${\mathcal{P}}_{s{s}^{\prime }}^a=\sum _{r^{\prime }}P\left(S_{t+1}=s^{\prime },R_{t+1}=r^{\prime }\mid S_t=s,A_t=a\right)$$

下一时刻的reward：

$${\mathcal{R}}_{s{s}^{\prime }}^a=E[R_{t+1}\mid S_t=s,A_t=a,S_{t+1}=s^{\prime }]=\frac{1}{{\mathcal{P}}_{s{s}^{\prime }}^a}\sum _{r^{\prime }}{r}^{\prime }P\left(S_{t+1}=s^{\prime },R_{t+1}=r^{\prime }\mid S_t=s,A_t=a\right)$$

轨迹序列联合概率：

$$p(\tau \mid \pi )=p(s_0)\prod _{t=0}^{T-1}p(s_{t+1},r_{t+1}\mid s_t,a_t)\pi (a_t\mid s_t)$$

State Value Function:

$$\begin{array}{rl}& V_{\pi }(s)\\ =& {\mathbb{E}}_{\tau \sim \pi }\left[\sum _{l=0}^{\infty }{\gamma }^l{r}_{t+l+1}|S_t=s\right]\\ =& \sum _{a_t,r_{t+1},s_{t+1}....}p(s_t)\prod _t^{\infty }p(s_{t+1}|s_t,a_t)p(r_{t+1}\mid s_t,a_t,s_{t+1})\pi (a_t\mid s_t)\sum _{l=0}^{\infty }{\gamma }^l{r}_{t+l+1}\\ =& \sum _{a_t,r_{t+1},s_{t+1}....}p(s_t)\prod _t^{\infty }p(s_{t+1}|s_t,a_t)p(r_{t+1}\mid s_t,a_t,s_{t+1})\pi (a_t\mid s_t)\left(r_{t+1}+\sum _{l=1}^{\infty }{\gamma }^l{r}_{t+l+1}\right)\\ =& \sum _{a_t,r_{t+1},s_{t+1}}p(s_t)p(s_{t+1}|s_t,a_t)p(r_{t+1}\mid s_t,a_t,s_{t+1})\pi (a_t\mid s_t)r_{t+1}+\\ & \sum _{a_t,r_{t+1},s_{t+1}}p(s_t)p(s_{t+1}|s_t,a_t)p(r_{t+1}\mid s_t,a_t,s_{t+1})\pi (a_t\mid s_t)\sum _{l=1}^{\infty }{\gamma }^l{r}_{t+l+1}\\ =& \sum _{a_t,r_{t+1},s_{t+1}}p(s_t)p(s_{t+1}|s_t,a_t)p(r_{t+1}\mid s_t,a_t,s_{t+1})\pi (a_t\mid s_t)r_{t+1}+\\ & \sum _{a_t,r_{t+1},s_{t+1}}p(s_t)p(s_{t+1}|s_t,a_t)p(r_{t+1}\mid s_t,a_t,s_{t+1})\pi (a_t\mid s_t)\sum _{a_{t+1},r_{t+2},s_{t+2}....}p(s_{t+1})\prod _t^{\infty }p(s_{t+2}\mid s_{t+1},a_{t+1})p(r_{t+2}\mid s_{t+1},a_{t+1},s_{t+2})\pi (a_{t+1}\mid s_{t+1})\sum _{l=1}^{\infty }{\gamma }^l{r}_{t+l+1}\\ =& \sum _{a_t,r_{t+1},s_{t+1}}p(s_t)p(s_{t+1}|s_t,a_t)p(r_{t+1}\mid s_t,a_t,s_{t+1})\pi (a_t\mid s_t)r_{t+1}+\\ & \sum _{a_t,r_{t+1},s_{t+1}}p(s_t)p(s_{t+1}|s_t,a_t)p(r_{t+1}\mid s_t,a_t,s_{t+1})\pi (a_t\mid s_t)\gamma V(s_{t+1})\\ =& \sum _{a_t,r_{t+1},s_{t+1}}p(s_t)p(s_{t+1}|s_t,a_t)p(r_{t+1}\mid s_t,a_t,s_{t+1})\pi (a_t\mid s_t)(r_{t+1}+\gamma V(s_{t+1}))\\ =& E_{r_{t+1}}\left[\sum _{a_t,s_{t+1}}p(s_t)p(s_{t+1}|s_t,a_t)\pi (a_t\mid s_t)(r_{t+1}+\gamma V(s_{t+1}))\right]\\ =& {\mathbb{E}}_{\tau \sim \pi }[r_{t+1}+\gamma V(s_{t+1})|S_t=s]\end{array}$$

其中$s_t=s$，一个细节，$s_t$是没有被求和的，因为他是给定的。另外一个细节是，这里没有考虑$R_t$时刻的reward的，reward是从$t+1$开始算起的，原因是reward往往需要上一时刻的$s_t$来计算，而初始时，并没有上一时刻的值所以不会计算。此外，reward的取值有时候是确定的，并没有随机性，那么可以简单用一个函数代替，如$r_{t+1}=r(s_t)$，在这种时候，对于$V_{\pi }(s_t)$，可以简写为

$$V_{\pi }(s_t)={\mathbb{E}}_{\pi }\left[\sum _{l=0}^{\infty }{\gamma }^{l}r(s_{t+l})\right]$$

Trust Region Policy Optimization

接下来，我们介绍TRPO这篇文章。这篇论文主要研究了一种如何让你的policy在累计reward上一定能够得到提升的方法，要研究这个东西我们首先需要搞清楚一个问题，那就是，两个不同的polocy他们的效果的区别在哪里？只有找到两者的联系，我们才能设计一种更好的更新策略。

首先，这里我们研究的是expected discounted reward：
$$\begin{array}{rl}& \eta (\pi )={\mathbb{E}}_{s_0,a_0,\dots }\left[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)\right],\text{ where}\\ & 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).\end{array}$$

注意，这里$\eta (\pi )$与value function$V^{\pi }(s)$有点不同，其不同之处在于，$\eta$需要进一步对初始状态$s$求期望，即需要考虑初始状态下每个状态的概率，我们用${\rho }_0(s):=P(s_0=s)$表示初始状态为s的概率，于是，$\eta$与$V$的联系为：

$$E_{s_0}\left[V^{\pi }(s_0)\right]=\sum _{s_0\in S}{\rho }_0(s_0)V^{\pi }(s_0)=\eta (\pi )$$

那么，这篇文章第一个结论就是，两个不同polocy，expected discounted reward有如下关系：

$$\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]$$

其中

$$\begin{array}{rl}& Q_{\pi }(s_t,a_t)={\mathbb{E}}_{s_{t+1},a_{t+1},\dots }\left[\sum _{l=0}^{\infty }{\gamma }^{l}r(s_{t+l})\right]\\ & V_{\pi }(s_t)={\mathbb{E}}_{a_t,s_{t+1},\dots }\left[\sum _{l=0}^{\infty }{\gamma }^{l}r(s_{t+l})\right]\\ & A_{\pi }(s,a)=Q_{\pi }(s,a)-V_{\pi }(s),\text{ where }\\ & a_t\sim \pi (a_t\mid s_t),s_{t+1}\sim P(s_{t+1}\mid s_t,a_t)\text{ for }t\ge 0\end{array}$$

注意一些细节，在Q的定义中，期望是从$a_{t+1}$开始取的，而V中的期望是从$a_t$就开始取的，所以

$$Q_{\pi }(s_t,a_t)-V_{\pi }(s_t)=r(s_t)+\sum _{s_{t+1}}p(s_{t+1}|s_t,a_t)V(s_{t+1})-V_{\pi }(s_t)=r(s_t)+E_{s_{t+1}\sim p(s_{t+1}|s_t,a_t)}[V(s_{t+1})]-V_{\pi }(s_t)$$

直觉上，$Q_{\pi }(s,a)-V_{\pi }(s)$衡量了只在当前step选择a所得到的额外好处，接下来利用这个A我们就可以推导出，两种不同polocy之间的差异，正是由A决定的：

$$\begin{array}{rl}& {\mathbb{E}}_{\tau \mid \tilde{\pi }}\left[\sum _{t=0}^{\infty }{\gamma }^t{A}_{\pi }(s_t,a_t)\right]\\ & ={\mathbb{E}}_{\tau \mid \tilde{\pi }}\left[\sum _{t=0}^{\infty }{\gamma }^t{E}_{s_{t+1}\sim p(s_{t+1}|s_t,a_t)}[r(s_t)+\gamma V_{\pi }(s_{t+1})-V_{\pi }(s_t)]\right]\\ & ={\mathbb{E}}_{\tau \mid \tilde{\pi }}\left[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)+E_{s_1,s_2,...,}\left[\gamma V_{\pi }(s_1)-V_{\pi }(s_0)+{\gamma }^2{V}_{\pi }(s_2)-\gamma V_{\pi }(s_1)+{\gamma }^3{V}_{\pi }(s_3)-{\gamma }^2{V}_{\pi }(s_2)+...\right]\right]\\ & ={\mathbb{E}}_{\tau \mid \tilde{\pi }}\left[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)-V_{\pi }(s_0)\right]\\ & =-{\mathbb{E}}_{s_0}[V_{\pi }(s_0)]+{\mathbb{E}}_{\tau \mid \tilde{\pi }}\left[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)\right]\\ & =-\eta (\pi )+\eta (\tilde{\pi })\end{array}$$

此外，在$\eta (\pi )$的原始定义，我们需要对每个序列的时间步求积分，但如果S里面的取值是有限的，那么$s$将会相互重复，注意到，这里的r是由$s_{t+l}$决定的，因此，对于相同状态的reward是可以被合并的。举个例子：

不妨设$t=0,1,2$，于是

$$\begin{array}{rl}\eta (\pi )& ={\mathbb{E}}_{s_0,s_1,s_2}\left[\sum _{t=0}^2{\gamma }^{t}r(s_t)\right]\\ & =\sum _{s_0}p(s_0){\gamma }^{0}r(s_0)\\ & +\sum _{a_0,s_0,s_1}p(s_0)\pi (a_0\mid s_0)p(s_1|s_0,a_0)\gamma r(s_1)\\ & +\sum _{a_0,s_0,a_1{s}_1,s_2}p(s_0)\pi (a_0\mid s_0)p(s_1|s_0,a_0)p(s_2|s_1,a_1)\pi (a_1\mid s_1){\gamma }^{2}r(s_2)\\ & =P(s_0=1){\gamma }^{0}r(1)+\sum _{s_0,a_0}p(s_1=1|s_0,a_0)p(s_0)\pi (a_0|s_0){\gamma }^{1}r(1)+\sum _{s_0,a_0,s_1,a_1}p(s_2=1|s_1,a_1)p(s_1|s_0,a_0)p(s_0)\pi (a_1|s_1){\gamma }^{2}r(1)\\ & +P(s_0=2){\gamma }^{0}r(2)+\sum _{s_0,a_0}p(s_1=2|s_0,a_0)p(s_0)\pi (a_0|s_0){\gamma }^{1}r(2)+\sum _{s_0,a_0,s_1,a_1}p(s_2=2|s_1,a_1)p(s_1|s_0,a_0)p(s_0)\pi (a_1|s_1){\gamma }^{2}r(2)\\ & +P(s_0=3){\gamma }^{0}r(3)+\sum _{s_0,a_0}p(s_1=3|s_0,a_0)p(s_0)\pi (a_0|s_0){\gamma }^{1}r(3)+\sum _{s_0,a_0,s_1,a_1}p(s_2=3|s_1,a_1)p(s_1|s_0,a_0)p(s_0)\pi (a_1|s_1){\gamma }^{2}r(3)\\ & =\sum _s\rho (s)r(s)\end{array}$$

类似的，我们利用有限的state的性质来重写value function：

$$\begin{array}{rl}\eta (\tilde{\pi })& ={\eta (\pi )+\mathbb{E}}_{\tau \mid \tilde{\pi }}\left[\sum _{t=0}^{\infty }{\gamma }^t{A}_{\pi }(s_t,a_t)\right]\\ & =\eta (\pi )+\sum _{t=0}^{\infty }{\gamma }^t\sum _{s}P\left(s_t=s\mid \tilde{\pi }\right)\sum _a\tilde{\pi }(a\mid s)A_{\pi }(s,a)\\ & =\eta (\pi )+\sum _{t=0}^{\infty }{\gamma }^t\sum _{s}P\left(s_t=s\mid \tilde{\pi }\right)\sum _a\tilde{\pi }(a\mid s)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{array}$$

其中

$${\rho }_{\pi }(s)=P(s_0=s)+\gamma P(s_1=s)+{\gamma }^{2}P(s_2=s)+\dots$$

根据这个等式，我们发现，只要能够保证$\sum _a\tilde{\pi }(a\mid s)A_{\pi }(s,a)⩾0$，那么$\pi \to \tilde{\pi }$就一定有提升，这意味着一种传统的贪婪方法：

$$\tilde{\pi }=arg\underset{a}{\max }{A}_{\pi }(s,a)$$

只要A中有有某个状态与动作是正数，那么$\tilde{\pi }$就一定能提升（因为取最大值总能找到这个数）。但问题在于，我们并不知道更新了policy后,${\rho }_{\tilde{\pi }}(s)$会变成什么样，这个东西只能采样估计，那么有没有一些近似的方法呢从直觉上讲，只要两个分布$\pi ,\tilde{\pi }$的距离不太远，${\rho }_{\tilde{\pi }}(s)$和${\rho }_{\pi }(s)$应该相差不远才对，也就是说，如果我们能够限制两个$\pi$的距离，那么${\rho }_{\pi }(s)$之间的距离也应该会被限制住，所以，我们是不是可以用一种近似的方法来学习出$\eta (\tilde{\pi })$:

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

这里，我们将${\rho }_{\tilde{\pi }}(s)$换成了${\rho }_{\pi }(s)$。

但问题在于，它与真实的$\eta (\tilde{\pi })$的差距有多大呢？我们将证明当$\pi$与$\tilde{\pi }$的距离有限时，$L(\tilde{\pi })$与真实$\eta (\tilde{\pi })$的差距将会被bound住：
定理1 令$\alpha =\underset{s}{\max }{D}_{TV}\left(\pi (\cdot |s)\Vert \tilde{\pi }(\cdot |s)\right)$，则下面的不等式成立

$$\begin{array}{c}\eta ({\pi }_{\text{ new }})\ge L_{{\pi }_{\text{ old }}}({\pi }_{\text{ new }})-\frac{4ϵ\gamma }{(1-\gamma {)}^2}{\alpha }^2\\ \text{ where }ϵ={\max }_{s,a}|A_{\pi }(s,a)|,\end{array}$$

这里$D_{TV}$是Total variation distance of probability measures。为了证明这个东西，我们先看下Total variation distance的相关知识。

Total variation distance of probability measures

Total variation distance定义如下：

$$D_{TC}(\mu ,\nu )=\underset{A\in \mathcal{F}}{\sup }|\mu (A)-\nu (A)|.$$

其中$\mathcal{F}$是sigma-algebra。他衡量了两个概率分布的最大差异，即存在某个事件A使得他们概率相差最大。如果sigma-algebra是可数的（如离散，自然数等），那么TC可以写成l1范数

$$\Vert \mu -\nu {\Vert }_{TV}=\frac{1}{2}\sum _{x\in \Omega }|\mu (x)-\nu (x)|$$

直觉上，两个分布的最大差异一定是发生在区域 B = { x ∣ μ ( x ) > ν ( x ) } \displaystyle B=\{x|\mu ( x) >\nu ( x)\} B={x∣μ(x)>ν(x)}中，或在区域中 B ‾ = { x ∣ μ ( x ) < ν ( x ) } \displaystyle \overline{B} =\{x|\mu ( x) < \nu ( x)\} B={x∣μ(x)<ν(x)}。换句话说，当发生的事件恰好为$B$时，这就是差异最大的时候，于是，直觉上

$$\Vert \mu -\nu {\Vert }_{TV}=\mu (B)-\nu (B)或\nu (\overline{B})-\mu (\overline{B})$$

实际上，你会发现，

$$\mu (B)-\nu (B)=\nu (\overline{B})-\mu (\overline{B})$$

这是因为，

$$\mu (B)+\mu (\overline{B})=\nu (\overline{B})+\nu (B)=1$$

所以

$$\begin{array}{rl}\Vert \mu -\nu {\Vert }_{TV}& =\frac{1}{2}(\mu (B)-\nu (B)+\nu (\overline{B})-\mu (\overline{B}))\\ & =\frac{1}{2}\sum _{x\in \Omega }|\mu (x)-\nu (x)|\\ & =\frac{1}{2}\Vert \mu -\nu {\Vert }_1\end{array}$$

以上就证明了，在离散或者可数集下，TV距离可以使用l1范数代替。

Pertubation Theory Proof of Policy Improvement Bound

接下来我们开始证明，论文里面提供两种证明方法，我们这里主要介绍第二种基于Pertubation Theory的证明方法。
定理1 令$\alpha =\underset{s}{\max }{D}_{TV}\left(\pi (\cdot |s)\Vert \tilde{\pi }(\cdot |s)\right)$，则下面的不等式成立

$$\begin{array}{c}\eta ({\pi }_{\text{ new }})\ge L_{{\pi }_{\text{ old }}}({\pi }_{\text{ new }})-\frac{4ϵ\gamma }{(1-\gamma {)}^2}{\alpha }^2\\ \text{ where }ϵ={\max }_{s,a}|A_{\pi }(s,a)|,\end{array}$$

证明：令$P_{\pi }(s^{\prime }|s)={\sum }_{a\in A}M(s^{\prime }|s,a)\pi (a|s)$，这里我们用$M$表示的这个MDP model的概率转移分布，$P_{\pi }(s^{\prime }|s)$表示在给定某个策略下而形成的state之间的转移概率。且$P_{\pi }$是一个$|S|\times |S|$的矩阵。首先回忆一下

$$\begin{array}{rl}\eta (\pi )& ={\mathbb{E}}_{s_0,s_1,s_2...}\left[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)\right]\\ & =\sum _{s_0}P(s_0){\gamma }^{0}r(s_0)+\sum _{s_0}p(s_0)\sum _{s_1}\sum _{a_0}P(s_1|s_0,a_0)\pi (a_0|s_0){\gamma }^{1}r(s_1)+\sum _{s_0}p(s_0)\sum _{s_1}\sum _{a_0}P(s_1|s_0,a_0)\pi (a_0|s_0)\sum _{s_2}\sum _{a_1}p(s_2|s_1,a_1)\pi (a_1|s_1){\gamma }^{2}r(s_2)+...\\ & =\sum _{s\in S}P(s_0=s){\gamma }^{0}r(s)+\sum _{s\in S}p(s_0=s)\sum _{s^{\prime }\in S}\sum _{a\in A}\underset{P_{\pi }(s^{\prime }|s)}{\underbrace{P(s^{\prime }|s,a)\pi (a|s)}}{\gamma }^{1}r(s^{\prime })+\sum _{s\in S}p(s_0=s)\sum _{s^{\prime }\in S}\sum _{a\in A}\underset{P_{\pi }(s^{\prime }|s)}{\underbrace{P(s^{\prime }|s,a)\pi (a|s)}}\sum _{s^{\prime \prime }\in S}\sum _{a^{\prime }\in A}\underset{P_{\pi }(s^{\prime \prime }|s^{\prime })}{\underbrace{p(s^{\prime \prime }|s^{\prime },a^{\prime })\pi (a^{\prime }|s^{\prime })}}{\gamma }^{2}r(s^{\prime \prime })+...\\ & =\left(\begin{array}{cccc}r(1)& r(2)& \cdots & r(n)\end{array}\right)\left(I+\gamma \left(\begin{array}{cccc}{P}_{\pi }(1|1)& P_{\pi }(1|2)& \cdots & P_{\pi }(1|n)\\ P_{\pi }(2|1)& P_{\pi }(2|2)& \cdots & P_{\pi }(2|n)\\ ⋮& ⋮& & ⋮\\ P_{\pi }(n|1)& P_{\pi }(n|2)& \cdots & P_{\pi }(n|n)\end{array}\right)+{\gamma }^2{\left(\begin{array}{cccc}{P}_{\pi }(1|1)& P_{\pi }(1|2)& \cdots & P_{\pi }(1|n)\\ P_{\pi }(2|1)& P_{\pi }(2|2)& \cdots & P_{\pi }(2|n)\\ ⋮& ⋮& & ⋮\\ P_{\pi }(n|1)& P_{\pi }(n|2)& \cdots & P_{\pi }(n|n)\end{array}\right)}^2+...\right)\left(\begin{array}{c}P(s_0=1)\\ P(s_0=2)\\ ⋮\\ P(s_0=n)\end{array}\right)\\ & =r(I-\gamma P_{\pi }{)}^{-1}{\rho }_0\end{array}$$

从求和到矩阵的转换可能有点烧脑，我们讲解一下。首先第一个等号是正常的展开，我们对每个时间求期望。第二个等式则是利用了状态数量有限（可数）的性质，对于相同的state，虽然发生的时间不同，但因为分布P和$\pi$其实跟时间无关，所以我们写成编列所有state。假设state一种有n种，于是我们就可以得到了矩阵的表达式，我们拿一项出来验证一下对不对：

$$\begin{array}{rl}& \left(\begin{array}{cccc}r(1)& r(2)& \cdots & r(n)\end{array}\right)\gamma \left(\begin{array}{cccc}{P}_{\pi }(1|1)& P_{\pi }(1|2)& \cdots & P_{\pi }(1|n)\\ P_{\pi }(2|1)& P_{\pi }(2|2)& \cdots & P_{\pi }(2|n)\\ ⋮& ⋮& & ⋮\\ P_{\pi }(n|1)& P_{\pi }(n|2)& \cdots & P_{\pi }(n|n)\end{array}\right)\left(\begin{array}{c}P(s_0=1)\\ P(s_0=2)\\ ⋮\\ P(s_0=n)\end{array}\right)\\ =& \gamma \left(\begin{array}{cccc}{\sum }_{s^{\prime }}{P}_{\pi }(s^{\prime }|1)r(s^{\prime })& {\sum }_{s^{\prime }}{P}_{\pi }(s^{\prime }|2)r(s^{\prime })& \cdots & {\sum }_{s^{\prime }}{P}_{\pi }(s^{\prime }|n)r(s^{\prime })\end{array}\right)\left(\begin{array}{c}P(s_0=1)\\ P(s_0=2)\\ ⋮\\ P(s_0=n)\end{array}\right)\\ =& \sum _{s}P(s_0=s)\sum _{s^{\prime }}{P}_{\pi }(s^{\prime }|s)\gamma r(s^{\prime })\end{array}\text{\hspace{1em}(1)}$$
你会发现这个东西跟公式的第二项对应上了。我们看看第三项，

$$\begin{array}{rl}& \left(\begin{array}{cccc}r(1)& r(2)& \cdots & r(n)\end{array}\right){\gamma }^2{\left(\begin{array}{cccc}{P}_{\pi }(1|1)& P_{\pi }(1|2)& \cdots & P_{\pi }(1|n)\\ P_{\pi }(2|1)& P_{\pi }(2|2)& \cdots & P_{\pi }(2|n)\\ ⋮& ⋮& & ⋮\\ P_{\pi }(n|1)& P_{\pi }(n|2)& \cdots & P_{\pi }(n|n)\end{array}\right)}^2\left(\begin{array}{c}P(s_0=1)\\ P(s_0=2)\\ ⋮\\ P(s_0=n)\end{array}\right)\\ =& {\gamma }^2\left(\begin{array}{cccc}{\sum }_{s^{\prime \prime }}{P}_{\pi }(s^{\prime \prime }|1)r(s^{\prime \prime })& {\sum }_{s^{\prime \prime }}{P}_{\pi }(s^{\prime \prime }|2)r(s^{\prime \prime })& \cdots & {\sum }_{s^{\prime \prime }}{P}_{\pi }(s^{\prime \prime }|n)r(s^{\prime \prime })\end{array}\right)\left(\begin{array}{cccc}{P}_{\pi }(1|1)& P_{\pi }(1|2)& \cdots & P_{\pi }(1|n)\\ P_{\pi }(2|1)& P_{\pi }(2|2)& \cdots & P_{\pi }(2|n)\\ ⋮& ⋮& & ⋮\\ P_{\pi }(n|1)& P_{\pi }(n|2)& \cdots & P_{\pi }(n|n)\end{array}\right)\left(\begin{array}{c}P(s_0=1)\\ P(s_0=2)\\ ⋮\\ P(s_0=n)\end{array}\right)\\ =& {\gamma }^2\left(\begin{array}{cccc}{\sum }_{s^{\prime }}{P}_{\pi }(s^{\prime }|1){\sum }_{s^{\prime \prime }}{P}_{\pi }(s^{\prime \prime }|s^{\prime })r(s^{\prime \prime })& {\sum }_{s^{\prime }}{P}_{\pi }(s^{\prime }|2){\sum }_{s^{\prime \prime }}{P}_{\pi }(s^{\prime \prime }|s^{\prime })r(s^{\prime \prime })& \cdots & {\sum }_{s^{\prime }}{P}_{\pi }(s^{\prime }|n){\sum }_{s^{\prime \prime }}{P}_{\pi }(s^{\prime \prime }|s^{\prime })r(s^{\prime \prime })\end{array}\right)\left(\begin{array}{c}P(s_0=1)\\ P(s_0=2)\\ ⋮\\ P(s_0=n)\end{array}\right)\\ =& \sum _{s}P(s_0=s)\sum _{s^{\prime }}{P}_{\pi }(s^{\prime }|s)\sum _{s^{\prime \prime }}{P}_{\pi }(s^{\prime \prime }|s^{\prime }){\gamma }^{2}r(s^{\prime \prime })\end{array}\text{\hspace{1em}(2)}$$

令$G=\left(1+\gamma P_{\pi }+(\gamma P_{\pi }{)}^2+\dots \right)=(1-\gamma P_{\pi }{)}^{-1}$，$\tilde{G}=\left(1+\gamma P_{\tilde{\pi }}+(\gamma P_{\tilde{\pi }}{)}^2+\dots \right)=(1-\gamma P_{\tilde{\pi }}{)}^{-1}$，根据上面的分析，我们有，$\eta (\pi )=r(I-\gamma P_{\pi }{)}^{-1}{\rho }_0$,$\eta (\tilde{\pi })=r(I-\gamma P_{\tilde{\pi }}{)}^{-1}{\rho }_0$，

为了方便我们设

$$G^{-1}-{\tilde{G}}^{-1}=(1-\gamma P_{\pi })-(1-\gamma P_{\tilde{\pi }})=\gamma (P_{\tilde{\pi }}-P_{\pi })=\gamma \Delta$$

于是对其左乘$G$,又乘$\tilde{G}$:

$$\begin{gathered} \tilde{G}-G=\gamma G\Delta \tilde{G} \\ \tilde{G}=G+\gamma G\Delta \tilde{G} \end{gathered}$$

将$\tilde{G}$代进去

$$\begin{gathered} \tilde{G}-G=\gamma G\Delta \left(G+\gamma G\Delta \tilde{G}\right) \\ \tilde{G}=G+\gamma G\Delta G+{\gamma }^{2}G\Delta G\Delta \tilde{G} \end{gathered}$$

于是

$$\eta (\tilde{\pi })-\eta (\pi )=r\left(\tilde{G}-G\right){\rho }_0=\gamma rG\Delta G{\rho }_0+{\gamma }^{2}rG\Delta G\Delta \tilde{G}{\rho }_0$$

对于第一项，$rG=v$是state value vector，见公式(1)(2)，显然其每个元素对应着不同state的value function，另外$G{\rho }_0={\rho }_{\pi }$. 所以$\gamma rG\Delta G{\rho }_0=\gamma v\Delta {\rho }_{\pi }$，接下来我们将证明$L_{\pi }(\tilde{\pi })-L_{\pi }(\pi )$两者的差距正是$\gamma v\Delta {\rho }_{\pi }$:

$$\begin{array}{rl}{L}_{\pi }(\tilde{\pi })-L_{\pi }(\pi )& =\sum _s{\rho }_{\pi }(s)\sum _a(\tilde{\pi }(a\mid s)-\pi (a\mid s))A_{\pi }(s,a)\\ & =\sum _s{\rho }_{\pi }(s)\sum _a(\tilde{\pi }(a\mid s)-\pi (a\mid s))\left(Q^{\pi }(s,a)-V^{\pi }(s)\right)\\ & =\sum _s{\rho }_{\pi }(s)\sum _a(\tilde{\pi }(a\mid s)-\pi (a\mid s))(E_{s^{\prime }\sim p(s^{\prime }|s,a)}[r(s)+\gamma v_{\pi }(s^{\prime })-v_{\pi }(s)])\\ & =\sum _s{\rho }_{\pi }(s)\sum _a\left(\tilde{\pi }(a\mid s)-\pi (a\mid s)\right)\left[r(s)+\sum _{s^{\prime }}p\left(s^{\prime }\mid s,a\right)\gamma v_{\pi }\left(s^{\prime }\right)-v_{\pi }(s)\right]\\ & =\sum _s{\rho }_{\pi }(s)\underset{={\sum }_a\tilde{\pi }(a\mid s)-{\sum }_a\pi (a\mid s)=1-1=0}{\underbrace{\sum _a\left(\tilde{\pi }(a\mid s)-\pi (a\mid s)\right)}}r(s)\\ & +\sum _s{\rho }_{\pi }(s)\sum _{s^{\prime }}\sum _a\left(\tilde{\pi }(a\mid s)-\pi (a\mid s)\right)p\left(s^{\prime }\mid s,a\right)\gamma v_{\pi }\left(s^{\prime }\right)\\ & -\sum _s{\rho }_{\pi }(s)\underset{={\sum }_a\tilde{\pi }(a\mid s)-{\sum }_a\pi (a\mid s)=1-1=0}{\underbrace{\sum _a\left(\tilde{\pi }(a\mid s)-\pi (a\mid s)\right)}}{v}_{\pi }\left(s^{\prime }\right)\\ & =\sum _s{\rho }_{\pi }(s)\sum _{s^{\prime }}\sum _a(\pi (a\mid s)-\tilde{\pi }(a\mid s))p\left(s^{\prime }\mid s,a\right)\gamma v_{\pi }\left(s^{\prime }\right)\\ & =\sum _s{\rho }_{\pi }(s)\sum _{s^{\prime }}\left(p_{\pi }\left(s^{\prime }\mid s\right)-p_{\tilde{\pi }}\left(s^{\prime }\mid s\right)\right)\gamma v_{\pi }\left(s^{\prime }\right)\\ & =\gamma v\Delta {\rho }_{\pi }\end{array}$$

于是我们就有了表达式:

$$\eta (\tilde{\pi })-\eta (\pi )=L_{\pi }(\tilde{\pi })-L_{\pi }(\pi )+{\gamma }^{2}rG\Delta G\Delta \tilde{G}{\rho }_0$$

又因为$L_{\pi }(\pi )=\eta (\pi )$，于是我们有

$$\begin{array}{rl}\eta (\tilde{\pi })& =L_{\pi }(\tilde{\pi })+{\gamma }^{2}rG\Delta G\Delta \tilde{G}{\rho }_0\end{array}$$

因此，我们只要能够确定最后一项的范围，我们就能找到$\eta (\tilde{\pi })$和$L_{\pi }(\tilde{\pi })$之间的关系，即

$$\begin{array}{rl}|\eta (\tilde{\pi })-L_{\pi }(\tilde{\pi })|& =|{\gamma }^{2}rG\Delta G\Delta \tilde{G}{\rho }_0|\\ & ⩽?\end{array}$$

接下来我们研究下最后一项范围：

$$\begin{array}{rl}{\gamma }^2|rG\Delta G\Delta \tilde{G}\rho |& \le \gamma \Vert \gamma rG\Delta {\Vert }_{\infty }\Vert G\Delta \tilde{G}{\rho }_0{\Vert }_1\\ & \le \gamma \Vert v\Delta {\Vert }_{\infty }\Vert G\Delta \tilde{G}{\rho }_0{\Vert }_1\end{array}$$

对于第一项$\Vert v\Delta {\Vert }_{\infty }$，我们只需要知道其中的最大值即可，那么其中的某个s元素为：

$$\begin{array}{rl}|(\gamma v\Delta {)}_s|& =\left|\sum _{s^{\prime }}\left(p_{\pi }\left(s^{\prime }\mid s\right)-p_{\tilde{\pi }}\left(s^{\prime }\mid s\right)\right)\gamma v_{\pi }\left(s^{\prime }\right)\right|\\ & =\left|\sum _{s^{\prime }}\left(\sum _a\pi (s,a)p\left(s^{\prime }\mid s,a\right)-\sum _a\tilde{\pi }(s,a)p\left(s^{\prime }\mid s,a\right)\right)\gamma v_{\pi }\left(s^{\prime }\right)\right|\\ & =\left|\sum _a\pi (s,a)\sum _{s^{\prime }}p\left(s^{\prime }\mid s,a\right)\gamma v_{\pi }\left(s^{\prime }\right)-\sum _a\tilde{\pi }(s,a)\sum _{s^{\prime }}p\left(s^{\prime }\mid s,a\right)\gamma v_{\pi }\left(s^{\prime }\right)\right|\\ & =\left|\sum _a\pi (s,a)(Q(s,a)-r(s))-\sum _a\tilde{\pi }(s,a)(Q(s,a)-r(s))\right|\\ & =\left|\sum _a\left(\pi (s,a)-\tilde{\pi }(s,a)\right)Q(s,a)-\underset{={\sum }_a\pi (s,a)-{\sum }_a\tilde{\pi }(s,a)=0}{\underbrace{\sum _a\left(\pi (s,a)-\tilde{\pi }(s,a)\right)}}r(s)\right|\\ & =\left|\sum _a(\tilde{\pi }(s,a)-\pi (s,a))Q_{\pi }(s,a)\right|\\ & =\left|\sum _a(\tilde{\pi }(s,a)-\pi (s,a))Q_{\pi }(s,a)-\sum _a(\tilde{\pi }(s,a)-\pi (s,a))V^{\pi }(s)\right|\\ & =\left|\sum _a(\tilde{\pi }(s,a)-\pi (s,a))A_{\pi }(s,a)\right|\\ & \le \sum _a|\tilde{\pi }(s,a)-\pi (s,a)|\cdot \underset{a}{\max }|A_{\pi }(s,a)|\\ & \le 2\alpha ϵ\end{array}$$

这里$\alpha =\underset{s}{\max }{D}_{TV}\left(\pi (\cdot |s)\Vert \tilde{\pi }(\cdot |s)\right),ϵ=\underset{a,s}{\max }|A_{\pi }(s,a)|$. 显然$2\alpha ϵ$就是所有元素中的最大值。接下来分析第二项

$$\begin{array}{rl}\Vert G\Delta \tilde{G}\rho {\Vert }_1& \le \Vert G{\Vert }_1\Vert \Delta {\Vert }_1\Vert \tilde{G}{\Vert }_1\Vert \rho {\Vert }_1\end{array}$$

首先，矩阵的l1 norm的定义为

$$\Vert A{\Vert }_1=\underset{\rho }{\sup }\left\{\frac{\Vert A\rho {\Vert }_1}{\Vert \rho {\Vert }_1}\right\}$$

直觉上，就是找一个最优向量使得$\Vert A\rho {\Vert }_1$最大，又因为l1往往会得到稀疏解，所有其解出来的$\rho$往往是一种one-hot向量，所以，其有着性质，就是选择绝对值求和最大的一列，即

$$\Vert A{\Vert }_1=\underset{1\le j\le n}{\max }\sum _{i=1}^m|a_{ij}|,$$

接下来，我们看看$\Vert G{\Vert }_1$的取值是多少

$$\begin{gathered} G=\left(1+\gamma P_{\pi }+(\gamma P_{\pi }{)}^2+\dots \right) \\ =\left(\begin{array}{ccc}1+\gamma P_{11}+{\gamma }^2{\sum }_j{P}_{1j}{P}_{j1}+{\gamma }^3{\sum }_{j_2}{P}_{j_{2}1}{\sum }_{j_1}{P}_{1j_1}{P}_{j_1{j}_2}+...& ...& 1+\gamma P_{1n}+{\gamma }^2{\sum }_j{P}_{1j}{P}_{jn}+{\gamma }^3{\sum }_{j_2}{P}_{j_{2}n}{\sum }_{j_1}{P}_{1j_1}{P}_{j_1{j}_2}+...\\ \gamma P_{21}+{\gamma }^2{\sum }_j{P}_{2j}{P}_{j1}+{\gamma }^3{\sum }_{j_2}{P}_{j_{2}1}{\sum }_{j_1}{P}_{2j_1}{P}_{j_1{j}_2}+...& ...& 1+\gamma P_{2n}+{\gamma }^2{\sum }_j{P}_{2j}{P}_{jn}+{\gamma }^3{\sum }_{j_2}{P}_{j_{2}n}{\sum }_{j_1}{P}_{2j_1}{P}_{j_1{j}_2}+...\\ ⋮& & ⋮\\ \gamma P_{n1}+{\gamma }^2{\sum }_j{P}_{nj}{P}_{j1}+{\gamma }^3{\sum }_{j_2}{P}_{j_{2}1}{\sum }_{j_1}{P}_{n{j}_1}{P}_{j_1{j}_2}+...& ...& 1+\gamma P_{nn}+{\gamma }^2{\sum }_j{P}_{nj}{P}_{jn}+{\gamma }^3{\sum }_{j_2}{P}_{j_{2}n}{\sum }_{j_1}{P}_{n{j}_1}{P}_{j_1{j}_2}+...\end{array}\right) \end{gathered}$$

对于第一列的求和：

$$\begin{array}{rl}& =1+\gamma \sum _{i=1}^n{P}_{i1}+{\gamma }^2\sum _j\sum _{i=1}^n{P}_{ij}{P}_{j1}+{\gamma }^3\sum _{j_2}{P}_{j_{2}1}\sum _{j_1}\sum _{i=1}^n{P}_{i{j}_1}{P}_{j_1{j}_2}+...\\ & =1+\gamma +{\gamma }^2\sum _j{P}_{j1}+{\gamma }^3\sum _{j_2}{P}_{j_{2}1}\sum _{j_1}{P}_{j_1{j}_2}+...\\ & =1+\gamma +{\gamma }^2+{\gamma }^3\sum _{j_2}{P}_{j_{2}1}+...\\ & =1+\gamma +{\gamma }^2+{\gamma }^3+...\\ & =\frac{1}{1-\gamma }\end{array}$$

显然每一列的求和均为$\frac{1}{1-\gamma }$，于是$\Vert G{\Vert }_1=\Vert \tilde{G}{\Vert }_1=\frac{1}{1-\gamma }$，对于

$$\begin{array}{rl}\Vert \Delta {\Vert }_1& =\Vert P_{\tilde{\pi }}-P_{\pi }{\Vert }_1\\ & \\ P_{\tilde{\pi }}-P_{\pi }& =\left(\begin{array}{cccc}{P}_{\pi }(1|1)& P_{\pi }(1|2)& \cdots & P_{\pi }(1|n)\\ P_{\pi }(2|1)& P_{\pi }(2|2)& \cdots & P_{\pi }(2|n)\\ ⋮& ⋮& & ⋮\\ P_{\pi }(n|1)& P_{\pi }(n|2)& \cdots & P_{\pi }(n|n)\end{array}\right)-\left(\begin{array}{cccc}{P}_{\tilde{\pi }}(1|1)& P_{\tilde{\pi }}(1|2)& \cdots & P_{\tilde{\pi }}(1|n)\\ P_{\tilde{\pi }}(2|1)& P_{\tilde{\pi }}(2|2)& \cdots & P_{\tilde{\pi }}(2|n)\\ ⋮& ⋮& & ⋮\\ P_{\tilde{\pi }}(n|1)& P_{\tilde{\pi }}(n|2)& \cdots & P_{\tilde{\pi }}(n|n)\end{array}\right)\\ & =\left(\begin{array}{ccc}{P}_{\pi }(1|1)-P_{\tilde{\pi }}(1|1)& \cdots & P_{\pi }(1|n)-P_{\tilde{\pi }}(1|n)\\ P_{\pi }(2|1)-P_{\tilde{\pi }}(2|1)& \cdots & P_{\pi }(2|n)-P_{\tilde{\pi }}(2|n)\\ ⋮& & ⋮\\ P_{\pi }(n|1)-P_{\tilde{\pi }}(n|1)& \cdots & P_{\pi }(n|n)-P_{\tilde{\pi }}(n|n)\end{array}\right)\end{array}$$

对于$P_{\tilde{\pi }}-P_{\pi }$的某一列进行求和，我们有

$$\begin{array}{rl}& \sum _{s^{\prime }}(P_{\pi }(s^{\prime }|s)-P_{\tilde{\pi }}(s^{\prime }|s))\\ =& \sum _{s^{\prime }}\left(P(s^{\prime }|s,a)\pi (a|s)-P(s^{\prime }|s,a)\tilde{\pi }(a|s)\right)\\ =& \pi (a|s)-\tilde{\pi }(a|s)\end{array}$$

所以$\Vert P_{\tilde{\pi }}-P_{\pi }{\Vert }_1$的取值应该是最大的那一列，使得$\underset{j}{\max }|\pi (a|j)-\tilde{\pi }(a|j)|=\underset{j}{\max }2\ast D_{TV}\left(\pi (\cdot |j)\Vert \tilde{\pi }(\cdot |j)\right)=2\alpha$。最后，最后一项$\Vert {\rho }_0{\Vert }_1=\sum _s|P(s_0=s)|=1$，因此，

$$\begin{array}{rl}\Vert G\Delta \tilde{G}\rho {\Vert }_1& \le \Vert G{\Vert }_1\Vert \Delta {\Vert }_1\Vert \tilde{G}{\Vert }_1\Vert \rho {\Vert }_1\\ & =\frac{1}{1-\gamma }\cdot 2\alpha \cdot \frac{1}{1-\gamma }\cdot 1\\ & =\frac{2\alpha }{(1-\gamma {)}^2}\end{array}$$

最后，我们有

$$\begin{array}{rl}{\gamma }^2|rG\Delta G\Delta \tilde{G}{\rho }_0|& \le \gamma \Vert \gamma rG\Delta {\Vert }_{\infty }\Vert G\Delta \tilde{G}{\rho }_0{\Vert }_1\\ & \le \gamma \Vert v\Delta {\Vert }_{\infty }\Vert G\Delta \tilde{G}{\rho }_0{\Vert }_1\\ & \le \gamma \Vert v\Delta {\Vert }_{\infty }\\ & \le \gamma \cdot 2\alpha ϵ\cdot \frac{2\alpha }{(1-\gamma {)}^2}\\ & =\frac{4\gamma ϵ}{(1-\gamma {)}^2}{\alpha }^2\end{array}$$

这就是最终结果了.

参考资料

Trust Region Policy Optimization

Theoretical Foundations of Reinforcement Learning

Approximately Optimal Approximate Reinforcement Learning

Notes on Reinforcement Learning - Paulo Rauber