第二十讲：策略搜索算法¶

回忆上一讲的内容，实际上上一讲的例子就是一个部分可观测MDP的特例。

在原LQR问题中有模型$s_{t+1}=As_t+Ba_t+w_t$，我们改变了条件，假设只能观测到$y_t=Cs_t+v_t$（不能直接观测到状态，只能观测到某些关于状态的函数，并需要根据这些观测值对最优动作作出判断）。

在状态完全可观测的情形下，我们可以根据$a_t=L_ts_t$选择动作；而在部分可观测的例子中，我们会使用$s_{t\mid t}$估计$s_t$，然后使用Kalman滤波的思想$s_{t\mid y_0,\cdots,y_t}\sim\mathcal N\left(s_{t\mid t},\varSigma_{t\mid t}\right)$计算这个估计$s_{t\mid t}$。

最后，我们使用$a_t=L_ts_{t\mid t}$选择最优动作。事实上这个算法让我们能够在不完全清楚系统每一个状态的前提下选择尽可能好的策略，而在一个部分可观测MDP中求最优策略是一个NP困难问题。

10.3 部分可观测MDP（POMDP: Partial Observed MDP）¶

我们现在给出POMDP的正式描述——七元组$(S,A,Y,\{P_{sa}\},\{O_s\},T,R)$：

• $Y$是可观测到的值的集合；

• $O$是可观测到的值的分布；

  也就是在每个$s_t$下都能够观测到某个服从$y_t\sim O_{s_t}$的随机变量。上一讲中我们介绍的在线性动力学系统中的特例可以使用Kalman过滤算法，从观测值中估计状态，再通过状态计算最优策略。然而这个算法仅对上一讲那个的特例（上一讲的例子也是POMDP的特例）有效，不过这个算法对普通的POMDP问题也有一定的效果，只是对该问题这个算法不一定是最优的算法。

12. 策略搜索（Policy Search）¶

再来介绍一个不同的强化学习算法——策略搜索算法，看名字就大概可以猜出，它可以被用于完全可观测MDP（Fully Observed MDP）或部分可观测MDP的最优策略求解。下面我们先来介绍策略搜索算法在完全可观测MDP中的应用。（在后面我们会介绍如何将策略搜索应用在POMDP上，但这并不能保证算法会找到全局最优解，策略搜索通常在POMDP中找到的是局部最优策略。解决POMDP是异常困难的，而策略搜索算法在实践中被证明是最好的POMDP解决算法之一。）

• 首先定义$\varPi$为策略的集合，而我们的算法就是在$\varPi$中搜索$\pi\in\varPi$。可以类比前面在监督学习算法中的概念——从假设类$\mathcal H$中搜索最优假设$h$（参见第九讲）。

  在之前的关于MDP的算法中，我们都是通过解出最优价值函数$V^*$进而得到最优策略$\pi^*$的。而在策略搜索算法中——有时被称作直接搜索算法——我们会“直接”去寻找最优策略（不再通过中间的步骤——计算最优价值函数）。

• 接下来再定义随机策略——是一个函数$\pi:S\times A\to\mathbb R$，$\pi(s,a)$表示在状态$s$执行动作$a$的概率。从定义就可以知道，函数$\pi$实际上是事件“在状态$s$执行动作$a$的概率”的概率密度函数，满足$\displaystyle\sum_a\pi(s,a)=1,\pi(s,a)\geq0$。换句话说，对于每一个状态，函数$\pi$都确定了一个在$a$上的分布。

  举个例子，假设我们要执行随机的策略$\pi$，而在当前的MDP中有三个动作$a_t\in\{a_1,a_2,a_3\}$，那么我们执行动作$a_1$的概率就是$\pi(s,a_1)$、执行动作$a_2$的概率就是$\pi(s,a_2)$、执行动作$a_3$的概率就是$\pi(s,a_3)$。这个过程就是执行一个随机策略。

下面继续使用倒置钟摆的例子来讲解策略搜索算法，我们定义$\phi$为钟摆偏离竖直位的角度，$a_1$是向右的加速度，$a_2$是向左的加速度。再找一个奖励函数，杆不论倒向那一边都对模型做出惩罚。提出一类随机策略意味着提出一类函数，这类函数被用来估计在状态$s_t$下将要执行的行动$a_t$。而现在，我们选择逻辑函数作为我们的策略，因为它是我们经常使用的一个很方便的函数： $$ \begin{align} \pi_\theta(s,a_1)&=\frac{1}{1+e^{-\theta^Ts}}\\ \pi_\theta(s,a_2)&=1-\frac{1}{1+e^{-\theta^Ts}} \end{align} $$ 因为我们不是选择$a_1$就是选择$a_2$，所以选择它们的概率之和为$1$。举个例子解释这个选择的合理性，假设我们的状态向量为$s=\begin{bmatrix}1\\x\\\dot x\\\phi\\\dot\phi\end{bmatrix}$（这里添加了$1$作为截距项给逻辑回归一个额外的特征值），如果我们选择$\theta=\begin{bmatrix}0\\0\\0\\1\\0\end{bmatrix}$，则有$P\displaystyle\left(a=\textrm{"right"}\right)=\frac{1}{1+e^{-\theta^Ts}}=\frac{1}{1+e^{-\phi}}$，这说明“向右加速”的概率只取决于“杆的倾角$\phi$”，所以当的杆向右偏的时候小车就会尝试向右加速以接住杆。当然，这个例子里的参数选择并不是最优的，因为它忽略的别的参数。现在，我们的目标就是调整$\theta$，使得当执行$\pi_\theta$时能够让杆尽可能的保持竖直，也就是说，我们的目标是选择一个参数$\theta$使得执行$\pi_\theta$时的预期总收益最大化。再举个例子，如果有$d$个离散的动作，那么我们也可以用第四讲提到的softmax回归$\displaystyle\theta_1,\cdots,\theta_d;\ \pi_{\theta_i}(s,a_i)=\frac{e^{\theta_i^Ts}}{\sum_je^{\theta_j^Ts}}$，策略类型的选择是可以自己确定的，线性函数、使用二次特征值的线性函数、监督学习算法等等。

12.1 增强算法（Reinforce algorithm）¶

设$s_0$是一个固定的初始化状态（即从一个确定的初始状态分布中抽样得到），我们的目标是：

$$ \begin{align} \max\ &\mathrm E[R(s_0,a_0)+\cdots+R(s_T,a_T]\\ &=\sum_{(s_0,a_0),\cdots,(s_T,a_T)}P(s_0a_0\cdots s_Ta_T)[R(s_0,a_0)+\cdots+R(s_T,a_T)]\tag{1}\\ &=\sum_{(s_0,a_0),\cdots,(s_T,a_T)}P(s_0)\pi_\theta(s_0,a_0)P_{s_0a_0}(s_1)\pi_\theta(s_1,a_1)P_{s_1a_1}(s_2)\cdots P_{s_{T-1}\ a_{T-1}}\ (s_T)\pi_\theta(s_T,a_T)\cdot\underbrace{[R(s_0,a_0)+\cdots+R(s_T,a_T)]}_{\textrm{payoff}}\tag{2} \end{align} $$

在后面我们就将$R(s_0,a_0)+\cdots+R(s_T,a_T)$部分简称为收益（payoff），先写出算法步骤：

• 重复：{

  • 抽样：$s_0,a_0,s_1,a_1,\cdots,s_T,a_t$
  • 计算收益：$R(s_0,a_0)+\cdots+R(s_T,a_T)$
  • 更新参数：$\displaystyle\theta:=\theta+\alpha\left[\frac{\nabla_\theta\pi_\theta(s_0,a_0)}{\pi_\theta(s_0,a_0)}+\cdots+\frac{\nabla_\theta\pi_\theta(s_T,a_T)}{\pi_\theta(s_T,a_T)}\right]\cdot[R(s_0,a_0)+\cdots+R(s_T,a_T)]$

  }

算法的第一步就是随机抽样得到一个状态-动作序列，也就是在MDP中执行当前的随机策略——从某个$s_0$开始，根据随机策略选择一个动作$a_0$，然后看状态转换概率给出的下一个状态，继续重复执行策略。第二步就是计算收益。第三步更新参数。

由于这个算法执行的是随机策略，所以我们想知道它为什么这样更新参数。我们可以计算更新参数步骤的期望，只要更新参数后带来的收益呈增长趋势，我们就对算法是满意的。实际上这个算法类似随机梯度上升，它将在局部最优解附近“游荡”，但总趋势是向局部最优解前进。

回顾上面的$(2)$式，它表示概率与收益之积在所有状态上的和，我们现在要做的就是对$(2)$式求关于$\theta$的导数，因为我们想对这个式子做梯度上升： $$ \begin{align} \nabla_\theta\mathrm E\left[R(s_0,a_0)+\cdots+R(s_T,a_T)\right] =\sum_{(s_0,a_0),\cdots,(s_T,a_T)} &\Bigg[\ P(s_0)\underline{(\nabla_\theta\pi_\theta(s_0,a_0))}P_{s_0a_0}(s_1)\pi_\theta(s_1,a_1)P_{s_1a_1}(s_2)\cdots P_{s_{T-1}\ a_{T-1}}\ (s_T)\pi_\theta(s_T,a_T)\\ &+P(s_0)\pi_\theta(s_0,a_0)P_{s_0a_0}(s_1)\underline{(\nabla_\theta\pi_\theta(s_1,a_1))}P_{s_1a_1}(s_2)\cdots P_{s_{T-1}\ a_{T-1}}\ (s_T)\pi_\theta(s_T,a_T)\\ &+\cdots\\ &+P(s_0)\pi_\theta(s_0,a_0)P_{s_0a_0}(s_1)\pi_\theta(s_1,a_1)P_{s_1a_1}(s_2)\cdots P_{s_{T-1}\ a_{T-1}}\ (s_T)\underline{(\nabla_\theta\pi_\theta(s_T,a_T))}\ \Bigg]\\ &\times[R(s_0,a_0)+\cdots+R(s_T,a_T)]\\ =\sum_{(s_0,a_0),\cdots,(s_T,a_T)}&P(s_0)\pi_\theta(s_0,a_0)P_{s_0a_0}(s_1)\pi_\theta(s_1,a_1)P_{s_1a_1}(s_2)\cdots P_{s_{T-1}\ a_{T-1}}\ (s_T)\pi_\theta(s_T,a_T)\\ &\times\left[\frac{\nabla_\theta\pi_\theta(s_0,a_0)}{\pi_\theta(s_0,a_0)}+\frac{\nabla_\theta\pi_\theta(s_1,a_1)}{\pi_\theta(s_1,a_1)}+\cdots+\frac{\nabla_\theta\pi_\theta(s_T,a_T)}{\pi_\theta(s_T,a_T)}\right]\\ &\times[R(s_0,a_0)+\cdots+R(s_T,a_T)]\\ =\sum_{(s_0,a_0),\cdots,(s_T,a_T)}&P(s_0a_0\cdots s_Ta_T)\cdot\left[\frac{\nabla_\theta\pi_\theta(s_0,a_0)}{\pi_\theta(s_0,a_0)}+\cdots+\frac{\nabla_\theta\pi_\theta(s_T,a_T)}{\pi_\theta(s_T,a_T)}\right]\\ &\times[R(s_0,a_0)+\cdots+R(s_T,a_T)]\\ \end{align}\\ \Downarrow\\ \nabla_\theta\mathrm E\left[R(s_0,a_0)+\cdots+R(s_T,a_T)\right]=\mathrm E\left[\left(\frac{\nabla_\theta\pi_\theta(s_0,a_0)}{\pi_\theta(s_0,a_0)}+\cdots+\frac{\nabla_\theta\pi_\theta(s_T,a_T)}{\pi_\theta(s_T,a_T)}\right)\cdot\left(R(s_0,a_0)+\cdots+R(s_T,a_T)\right)\right] $$ 第一步应用了几个相乘函数的求导法则$\displaystyle\frac{\mathrm d}{\mathrm d\theta}f(\theta)g(\theta)h(\theta)=f'(\theta)g(\theta)h(\theta)+f(\theta)g'(\theta)h(\theta)+f(\theta)g(\theta)h'(\theta)$。

但是，使用加强算法的时候，我们通常认为对于待解决的问题，存在一个简单的函数（如线性函数、逻辑函数等），描述了从状态空间到动作空间的映射。对于倒置钟摆这种简单的任务，事实可能就是这样的（杆向右偏时小车就向右加速接住杆）。实际上对于很多低级别的控制任务（如开车时右边有障碍就应该向左转向以避让），人类也是条件反射式的做出“本能”动作。对于这种较为简单的、极短时间内的“本能”判断，通常能够找到一个由简单函数组成的合理的策略类。

与其相反的是复杂任务，需要很长的多步推理的任务，比如象棋、围棋等。在这种活动中做出决策需要多步严密的因果推理，这是一种高级别的控制任务，所以就不能使用“本能”了。在这种任务中我们有时会用前面提到的价值函数的线性近似。另外，在POMDP中如果使用$\hat s$近似真实状态（比如在Kalman滤波中的$\hat s=s_{t\mid t}$），则我们仍然可以使用策略搜索算法$\displaystyle\pi_\theta(\hat s,a_t)=\frac{1}{1+e^{-\theta^T\hat s}}$。

最后，关于加强算法——这个算法在做上升时本质上是没有明确方向的（虽然其总体期望上是正确的），这可能会导致加强算法需要大量的迭代才到达到最优值附近；而且，在算法中，每次迭代都需要一次抽样，如果对于一个物理实体来说成本可能会很高，比如我们在研究控制一个机器人，那么这个机器人可能就需要做很多次动作（多次迭代，每次都需要抽样），所以这个算法通常运行在模拟器中。

12.2 Pegasus算法¶

在第十七讲我们提到模拟器的应用。模拟器可以接受状态$s_t$和动作$a_t$，输出下一步的状态$s_{t+1}$，$s_{t+1}$通常是一个从随机状态转换概率中抽样的随机状态，也就是说在模拟器中$s_{t+1}$是一个关于$s_t,a_t$的随机函数。比如我们在直升机的例子中，使用线性回归、局部加权回归等监督学习算法，就可以构建一个非线性动力学模型，在这个模型中，$s_{t+1}$就是一个关于$s_t,a_t$的随机函数。我们可以使用模拟器估计任意的状态-动作序列对应的预期总收益（将每个状态的奖励函数值相加即可）。

同样是在第十七讲我们定义了策略，它接受当前状态，输出当前状态下应执行的动作，那么结合模拟器，就可以估计任意策略的预期总收益了（选定初始状态$s_0$后，输入策略$\pi$得到$a_0$，再将$s_0,a_0$输入模拟器得到$s_1$；将$s_1$带入策略$\pi$得到$a_1$，再将$s_1,a_1$带入模拟器得到$s_2$……将所有状态带入奖励函数，求和即可估计出该策略的预期总收益）。那么，我们就可以尝试找到使这个由模拟器估计出的总收益最大的策略，也就是找到该策略对应的参数即可。从概念上讲，这是一个不错的思路，但是实际上几乎不可行：由于模拟器的随机性，即使我们对同一个策略做估计时，也会得到有细微的差别两个不同的结果，所以在策略空间中对策略进行估计时，如果策略空间维数较高，那么我们很难知道空间中策略对应的收益的分布趋势。

模拟器会根据输入的状态-动作输出一个带有机性的下一步状态，通常，能够做到这一点的模拟器都会调用一个随机数生成器。那么，为了降低使用模拟器对策略空间进行搜索的难度，我们可以在MDP中每一步调用模拟器时，固定随机数生成器得到的值（也就是让每一步的生成器只生成器只运行一次，然后就固定这个值），如果我们每次估计策略都使用同一组随机数序列，则模拟器就不再是随机的了，此时对同一个策略进行多次估计，得到的也将是相同的值（取消了随机数也就意味着确定了在策略空间上的收益函数，这极大程度上降低了最优策略的求解难度）。虽然我们现在通过模拟器只能得到的策略预期总收益的估计（因为固定了随机数，模拟器不再是原来通过试验数据拟合出来的系统了），但这个估计值离实际的预期总收益相乘不大，所以现在我们就可以使用诸如梯度上升等算法在策略空间中搜索最优策略了。

关于这个随机数，可以举个例子，在直升机模型中，假设随机数是对直升机在风场中的模拟，不同的随机数对应不同的风。在对风场的模拟中，我们不是对每一种模式的风都进行建模估计，而是采样不同模式的风，对它们做平均的估计。在模拟器中，我们对控制策略做收益估计，并不是只做一次，而是做很多次，然后取所有测试的平均收益。这就相当于在不同的风场中做了多次测试，然后得出控制策略在不同风场状况下的平均预期收益。

12.3 强化学习算法小结¶

我们一共介绍了两种强化学习算法，第一种方法是通过求解最优价值函数推导出最优策略，这种方法常被用于解决需要“深思熟虑”才能解决的问题，它涉及的问题一般都会有多步推导，且后面步骤的决策也会影响前面的步骤，常见于诸如俄罗斯方块、象棋等场景；第二种方法是通过策略搜索直接找到最优策略，这种方法通常被用于解决“条件反射”式的问题，比如直升机悬停控制、汽车障碍避让等场景。强化学习算法的核心是根据状态做出的决策序列，它的适用场景为“需要依次根据状态做出决策的问题，而且决策可能具有长期影响”。列出一些RL算法已经应用的场景：医疗决策——根据病人所处的状态选择不同的治疗方案；用于减少排队等待时间——其中包括流水线上的效率提升问题等；用于博弈论中某些场景——比如怎样大量抛售股票同时又将对市场的影响降到最低；也应用于运筹学——最大化工厂的生产效率同时降低成本……。