trust region policy optimization 阅读笔记

简介
作者介绍
背景
- 在一般随机策略中保持回报单调提升

论文题目: trust region policy optimization

简介

作者介绍

背景

考虑马尔可夫过程 $(\mathcal{S},\mathcal{A},P,c,\rho_0,\gamma)$ ，其中 $c$ 是代价函数， $c:\mathcal{S}\to \mathbb{R}$ ，类似于负回报函数，其余为常规含义。

定义 $\pi$ 为随机策略 $\pi:\mathcal{S}\times\mathcal{A}\to[0,1]$ ，定义 $\eta(\pi)$ 为期望代价：

$\eta(\pi)=\mathbb{E}_{s_0,a_0,\cdots}\Big[\sum_{t=0}^\infty\gamma^tc(s_t)\Big]$

继而定义常规的 $Q_\pi$ ， $V_\pi$ 和 $A_\pi$ 。

$\begin{aligned} Q_\pi(s_t,a_t)&=\mathbb{E}_{s_{t+1},a_{t+1},\cdots}\Big[\sum_{l=0}^\infty\gamma^lc(s_{t+l})\Big] \\ V_\pi(s_t)&=\mathbb{E}_{a_{t},s_{t+1},\cdots}\Big[\sum_{l=0}^\infty\gamma^lc(s_{t+l})\Big] \\ A_\pi(s,a)&=Q_\pi(s,a)-V_\pi(s) \\ \end{aligned}$

我们考虑一个新策略 $\tilde{\pi}$ 的期望代价 $\eta(\tilde{\pi})$ 与基准策略的期望代价 $\eta(\pi)$ 的关系：

$\begin{aligned} &\eta(\tilde{\pi})=\eta(\pi)+\mathbb{E}_{s_0,a_0,\cdots}\Big[\sum_{t=0}^\infty\gamma^tA_\pi(s_t,a_t)\Big],\mathrm{where} \\ &a_t\sim\tilde{\pi}(a_t\vert s_t) \tag{1} \end{aligned}$

证明：

$\begin{aligned} \eta(\tilde{\pi})-\eta(\pi)&=\mathbb{E}_{(s_t,a_t)\sim\tilde{\pi}}\Big[\sum_{t=0}^\infty\gamma^tc(s_{t})\Big]-\mathbb{E}_{s_0\sim\rho_0}[V_\pi(s_0)] \\ &=\mathbb{E}_{(s_t,a_t)\sim\tilde{\pi}}\Big[\sum_{t=0}^\infty\gamma^tc(s_{t})-V_\pi(s_0)\Big]\\ &=\mathbb{E}_{(s_t,a_t)\sim\tilde{\pi}}\Big[\sum_{t=0}^\infty\gamma^tc(s_{t})+\sum_{t=1}^\infty\gamma^tV_\pi(s_t)-\sum_{t=0}^\infty\gamma^tV_\pi(s_t)\Big]\\ &=\mathbb{E}_{(s_t,a_t)\sim\tilde{\pi}}\Big[\sum_{t=0}^\infty\gamma^tc(s_{t})+\gamma\sum_{t=0}^\infty\gamma^tV_\pi(s_{t+1})-\sum_{t=0}^\infty\gamma^tV_\pi(s_t)\Big]\\ &=\mathbb{E}_{(s_t,a_t)\sim\tilde{\pi}}\Big[\sum_{t=0}^\infty\gamma^t[c(s_{t})+\gamma V_\pi(s_{t+1})-V_\pi(s_t)]\Big]\\ &=\mathbb{E}_{(s_t,a_t)\sim\tilde{\pi}}\Big[\sum_{t=0}^\infty\gamma^t[Q_\pi(s_t,a_t)-V_\pi(s_t)]\Big]\\ &=\mathbb{E}_{(s_t,a_t)\sim\tilde{\pi}}\Big[\sum_{t=0}^\infty\gamma^t A_\pi(s_t,a_t)\Big]\\ \end{aligned}$

为表示方便，记

$\rho_\pi(s)=(P_\pi(s_0=s)+\gamma P_\pi(s_1=s)+\gamma^2 P_\pi(s_2=s)+\cdots)$

表示在策略 $\pi$ 下出现状态 $s$ 的折扣概率。其中

$\begin{aligned} &P_\pi(s_t=s)\\ =&\sum_{s'\in\mathcal{S}}\sum_{a'\in\mathcal{A}} P_\pi(s_{t-1}=s')\pi(a_{t-1}=a'\vert s')P(s_t=s\vert a_{t-1}=a',s_{t-1}=s') \end{aligned}$

我们对 $(1)$ 进行重排，之前 $(1)$ 时是以一条完整轨迹为求和单位，现在以任意一个状态动作元组 $(s_t,a_t)$ 为求和单元，不难得到

$\eta(\tilde{\pi})=\eta(\pi)+\sum_{s}\rho_{\tilde{\pi}}(s)\sum_{a}\tilde{\pi}(a\vert s)A_\pi(s,a)\tag{2}$

证明：

$\begin{aligned} \eta(\tilde{\pi})&=\eta(\pi)+\sum_{t=0}^\infty\sum_{s,a}P(s_t=s,a_t=a\vert {\tilde{\pi}})\gamma^tA_\pi(s_t=s,a_t=a)\\ &=\eta(\pi)+\sum_{t=0}^\infty\sum_{s,a}P(s_t=s\vert {\tilde{\pi}})\tilde{\pi}(a\vert s)\gamma^tA_\pi(s,a)\\ &=\eta(\pi)+\sum_{t=0}^\infty\sum_{s}P(s_t=s\vert {\tilde{\pi}})\sum_a\tilde{\pi}(a\vert s)\gamma^tA_\pi(s,a)\\ &=\eta(\pi)+\sum_{s}\sum_{t=0}^\infty P(s_t=s\vert {\tilde{\pi}})\gamma^t\sum_a\tilde{\pi}(a\vert s)A_\pi(s,a)\\ &=\eta(\pi)+\sum_{s}\rho_{\tilde{\pi}}(s)\sum_{a}\tilde{\pi}(a\vert s)A_\pi(s,a) \end{aligned}$

在 $(2)$ 的基础上，我们可以发现，只要对任意的 $s$ ，都有 $\sum_{a}\tilde{\pi}(a\vert s)A_\pi(s,a) \geq 0$ ，就可以保证 $\eta(\tilde{\pi})\geq\eta(\pi)$ ，也就是实现了策略更新时，回报递增。这个结论同时也说明了贪心的策略迭代方法 $\tilde{\pi}(s)=\arg\max_a A_\pi(s,a)$ ，由于

$\begin{aligned} \sum_{a}\tilde{\pi}(a\vert s)A_\pi(s,a) &=1\cdot A_\pi(s,\tilde{\pi}(s))\\ &=\max_a A(s,a) \\ &=\max_a \Big[Q(s,a)-V(s)\Big] \\ &=\max_a Q(s,a)-\mathbb{E}_aQ(s,a)\\ &\geq 0 \end{aligned}$

总是保证回报不下降的。

那么看起来似乎贪心的策略迭代方法是一个很好的方法。然而，由于估计（对 $V,Q$ 的估计）和近似（对 $\mathbb{E}$ 的计算不是严格穷举的，而是基于采样）的误差，总是存在某些状态 $s$ 使得 $\sum_{a}\tilde{\pi}(a\vert s)A_\pi(s,a) < 0$ ，因此贪心策略迭代也不能保证回报不下降。

另一方面， $(2)$ 对于 $\rho_{\tilde{\pi}}(s)$ 的依赖也导致了基于 $(2)$ 直接优化/求梯度是一件非常困难的事（因为我们没有 $\tilde{\pi}$ 的轨迹信息）。因此我们考虑第一步近似操作，把 $\rho_{\tilde{\pi}}(s)$ 替换为 $\rho_{\pi}(s)$ ：

$L_{\pi}({\tilde{\pi}})=\eta(\pi)+\sum_{s}\rho_{\pi}(s)\sum_{a}\tilde{\pi}(a\vert s)A_\pi(s,a) \tag{3}$

此时我们需要注意到，（当我们把策略 $\pi$ 看作参数化策略 $\pi_\theta$ 时） $L_{\pi_0}(\cdot)$ 和 $\eta(\cdot)$ 在 $\pi_0$ 处的一阶泰勒展开是一样的，即具有一阶近似性：

$\begin{aligned} L_{\pi_{\theta_0}}(\pi_{\theta_0})&=\eta(\pi_{\theta_0}) \\ \nabla_\theta L_{\pi_{\theta_0}}(\pi_{\theta})\vert_{\theta=\theta_0}&=\nabla_\theta \eta(\pi_{\theta})\vert_{\theta=\theta_0} \tag{4} \end{aligned}$

这一性质暗示了，当我们用足够小的步长去执行 $\pi_{\theta_0}\to\tilde{\pi}$ 时，如果 $L_{\pi_{\theta_\mathrm{old}}}(\pi_{\theta_\mathrm{old}+\epsilon_1})>L_{\pi_{\theta_\mathrm{old}}}(\pi_{\theta_\mathrm{old}+\epsilon_2})$ ，那么就有 $\eta(\pi_{\theta_\mathrm{old}+\epsilon_1})>\eta(\pi_{\theta_\mathrm{old}+\epsilon_2})$ （一般情况下每次更新了策略，都会用新策略替换掉旧策略，即上式中 $\epsilon_2$ 为零向量的情况）。

简单来说，上述结论为：在 $\theta_0$ 的一个领域内， $L_{\pi_{\theta_0}}(\cdot)$ 与 $\eta(\cdot)$ 同增同减。

但我们并不知道多小的领域才满足这个性质，或者说， $L_\pi(\cdot)$ 与 $\eta(\cdot)$ 之间的差距与步长有什么关系。这里直接给出研究结论：

$\begin{aligned} \mathrm{Note}& \ \pi^*=\arg\max_{\pi'}L_{\pi_\mathrm{old}}(\pi')\\ \mathrm{let} \ \ \ \ & \ \pi_{\mathrm{new}}(a\vert s)=(1-\alpha)\pi_{\mathrm{old}}(a\vert s)+\alpha \pi^*(a\vert s)\\ \mathrm{get}\ \ \ & \ \eta(\pi_\mathrm{new})\geq L_{\pi_\mathrm{old}}(\pi_\mathrm{new})-\frac{2\epsilon\gamma}{(1-\gamma)^2}\alpha^2 \\ &\mathrm{where} \ \epsilon=\max_s \vert \mathbb{E}_ {a\sim\pi'} [A_\pi(s,a)] \vert \tag{6} \end{aligned}$

这里 $\alpha$ 本质上是对 $\pi_{\mathrm{new}}$ 和 $\pi_{\mathrm{old}}$ 之间差距的刻画，即公式(6)是在说， $\pi_{\mathrm{new}}$ 的真实价值 $\eta(\pi_{\mathrm{new}})$ 与作者给出的近似估计值 $L_{\pi_\mathrm{old}}(\pi_\mathrm{new})$ 之间的差距，可以由 $\alpha$ 控制住。虽然这里只给出 $\eta$ 的下界，但是由于 $\eta$ 是肯定小于 $L_\pi$ 的（根据公式(3)），所以可以说差距已经被控制住了。但这个结论只适用于保守型（线性组合法）的策略更新规则，在实际中难以应用。

在一般随机策略中保持回报单调提升

先写结论：作者证明了 $(6)$ 的结论稍作修改，在一般随机策略中也成立——只要修改步长 $\alpha$ （某种意义上也是邻域大小）为 $\pi$ 和 $\tilde{\pi}$ 的距离，再修正常数 $\epsilon$ 即可。

首先，策略的距离选择上，作者采用全变分散度： $D_{TV}(p\vert \vert q)=\frac{1}{2}\sum_i \vert p_i-q_i\vert$ ，其中 $p,q$ 是离散随机变量的分布。

$\begin{aligned} D_{TV}^{\max}(\pi,\tilde{\pi})=\max_s D_{TV}(\pi(\cdot\vert s)\vert \vert \tilde{\pi}(\cdot\vert s)) \tag{7} \end{aligned}$

利用全变分散度和KL散度之间的关系： $D_{TV}(p\vert\vert q)^2\leq D_{KL}(p\vert\vert q)$ ，令 $D_{KL}^{max}(\pi,\tilde{\pi})=\max_s D_{KL}(\pi(\cdot,s)\vert\vert \tilde{\pi}(\cdot,s))$ ，可以进一步修改定理一为：

至此我们得到了一般随机策略下的 $\eta$ 与 $L_\pi$ 的关系，因此只要用公式(9)的右式代替 $\eta$ 执行策略迭代算法，即算法一：

容易证明算法一得到的策略序列 ${\pi_i}$ 满足 $\eta(\pi_i)\leq\eta(\pi_{i+1})$ ：

记$M_i(\pi)=L_{\pi_i}(\pi)-CD^{\mathrm{max}}{KL}(\pi_i,\pi) $，那么有$ \eta(\pi_i)=M_i(\pi_i), \ \eta(\pi{i+1})\geq M_{i}(\pi_{i+1}) $，因此$ \eta(\pi_{i+1})-\eta(\pi_i)\geq M_i(\pi_{i+1})-M_i(\pi_i)\geq 0$。

PS:这一结论其实从直觉上是不容易想到的，因为大部分人第一反应是:两个序列 ${a_i}$ 和 ${b_i}$ 满足 $a_i\geq b_i$ 且 $b_i\leq b_{i+1}$ ，可是却不一定有 $a_i\leq a_{i+1}$ 。其中的关键之处在于 $M_i(\cdot)$ 与 $M_{i+1}(\cdot)$ 是不一样的。实际上，当我们得到满足 $\eta(\pi_i)\geq M_{i-1}(\pi_i)$ 的 $\pi_i$ 后，就利用刚得到的 $\pi_i$ 把 $M_{i-1}$ 更换为 $M_i$ ，使得 $M_i(\pi_i)=\eta(\pi_i)$ ，即将小于 $\eta(\pi_i)$ 的 $M_{i-1}(\pi_i)$ 提升到等于 $\eta(\pi_i)$ 的 $M_{i}(\pi_i)$ 了，再在此基础上进一步更新，所以得到的新的 $M_i(\pi_{i+1})\geq M_i(\pi_i)=\eta(\pi_i)$ 就是很正常的了。

trust region policy optimization 阅读笔记

简介

作者介绍

背景

在一般随机策略中保持回报单调提升

Comments