CS229 Lesson 16 马尔可夫决策过程

课程视频地址：http://open.163.com/special/opencourse/machinelearning.html

课程主页：http://cs229.stanford.edu/

更具体的资料链接：https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版：https://github.com/Kivy-CN/Stanford-CS-229-CN

这一讲介绍了马尔可夫决策过程。

Part XIII 强化学习和控制

我们现在开始学习强化学习和适应性控制。

​ 在监督式学习中，我们看到算法试图使他们的输出模仿训练集中给出的标签$y$。在这种设定下，标签为每个输入$x$提供了明确的“正确答案”。相反的，对于许多序列决策问题和控制问题，很难将这种类型的显式监督提供给学习算法。例如，如果我们刚刚建造了一个四足机器人，并试图对它编程，让它能行走，那么最初我们不知道采取什么样的“正确”行动是为了让它行走，所以不知道如何提供明确监督学习算法以试图模仿。

​ 在强化学习框架中，取而代之的，我们将给算法提供一个奖励函数，该函数向算法表明它何时表现良好，何时表现不佳。在四足机器人的例子中，奖励函数会在机器人向前移动时获得正面奖励，向后移动或倒退则会获得负面奖励。然后学习算法的工作就是弄清楚如何随时间选择行动以获得较高的奖励。

​ 强化学习在各种应用中都取得了成功，如直升机自动飞行，机器人腿部移动，手机网络，营销策略选择，工厂控制和高效的网页索引。我们对强化学习的研究将从马尔可夫决策过程（MDP）的定义开始，该过程给出了RL问题的常见形式。

1.马尔可夫决策过程

一个马尔可夫决策过程是一个$5$元组$(S,A,\{P_{sa}\},\gamma, R)$，其中：

• $S$是状态的集合。（例如，在直升机自动飞行中，$S$可能是直升机的所有可能位置和方向的集合。）
• $A$是行动的集合。（例如，直升机控制杆能够被推动的所有可能方向的集合。）
• $P_{sa}$是状态转移概率。对于每个状态$s\in S$和行动$a \in A$，$P_{sa}$是状态空间的分布。我们将在后面更多的讨论这点，但是简洁的，$P_{sa}$给出了如果我们在状态$s$采取行动$a$，转移状态的概率分布。
• $\gamma \in [0,1)$被称为折扣因子。
• $R: S\times A \mapsto \mathbb R$是奖励函数。（奖励函数有时被写成状态$S$的函数，在这种情形下我们有$R: S \mapsto \mathbb R$）。

​ MDP的动态过程如下：我们从某个状态$s_0$开始，然后选择MDP中的行动$a_0 \in A$。作为我们选择的结果，MDP的状态随机转移到某个后继状态$s_1$，其中$s_1 \sim P_{s_0 a_0}$。然后，我们选择另一个行动$a_1$。作为这个行动的结果，状态再次转移到$s_2 \sim P_{s_1 a_1}$。然后我们选择$a_2$，如此继续下去…形象的，我们可以将此过程表示为下图：

$$s_0 \overset{a_0} \longrightarrow s_1 \overset{a_1} \longrightarrow s_2 \overset{a_2} \longrightarrow s_3 \overset{a_3} \longrightarrow ...$$

​ 通过访问状态序列$s_0,s_1,…$和行动$a_0,a_1,…,$我们的总收益是

$$R(s_0, a_0) + \gamma R(s_1, a_1)+ \gamma^2 R(s_2, a_2) + ...$$

或者，如果我们将奖励函数仅作为状态的函数，上式变为

$$R(s_0) + \gamma R(s_1)+ \gamma^2 R(s_2) + ...$$

在我们绝大多数的推导中，我们将使用更简单的状态奖励函数$R(s)$，尽管将其一般化为状态-动作奖励函数$R(s,a)$并没有太多困难。

​ 在强化学习中，我们的目标是选择行动使得总收益的期望最大化：

$$\mathbb E[R(s_0) + \gamma R(s_1)+ \gamma^2 R(s_2) + ...]$$

注意到$t$时刻的奖励因为因子$\gamma^t$而打折扣。因此，为了使得上述期望比较大，我们希望尽快获得正向的奖励（并尽可能推迟负面奖励）。在经济学应用中，$R(.)$是盈利金额，$\gamma$的自然解释是利率（今天的1美元比明天的1美元更有价值）。

​ 策略是任意从状态映射到行动的函数$\pi : S \mapsto A$。我们说我们在执行策略$\pi$，只要我们在状态$s$采取行动$a=\pi(s)$。我们也根据下式定义策略$\pi$的价值函数

$$V^{\pi} (s)= \mathbb E[R(s_0) + \gamma R(s_1)+ \gamma^2 R(s_2) + ...| s_0 =s,\pi]$$

$V^{\pi} (s)$是起始状态为$s$，根据策略$\pi$采取行动的折扣奖励的期望总和。

​ 给定策略$\pi$，其价值函数$V^{\pi}$满足贝尔曼方程：

$$V^{\pi} (s) = R(s) + \gamma \sum_{s'\in S} P_{s\pi(s)}(s') V^{\pi}(s')$$

这是因为

$$\begin{aligned} V^{\pi} (s) &= \mathbb E[R(s_0) + \gamma R(s_1)+ \gamma^2 R(s_2) + ...| s_0 =s,\pi]\\ &=\mathbb E[R(s_0)| s_0 =s,\pi] + \gamma\mathbb E[ R(s_1)+ \gamma R(s_2) + ...| s_0 =s,\pi]\\ &=R(s)+\gamma \sum_{s'\in S}\mathbb E[R(s')+ \gamma R(s_2) + ...| s_0 =s,\pi,s_1 =s'] P_{s\pi(s)}(s')\\ &=R(s) + \gamma \sum_{s'\in S} P_{s\pi(s)}(s') V^{\pi}(s') \end{aligned}$$

上式表示折扣奖励的期望总和$V^{\pi}(s)$由两部分构成：第一部分为从状态$s$出发的即时奖励$R(s)$，第二部分为未来的折扣奖励的期望总和。仔细看第二项，我们可以发现求和项可以被重写为$\mathbb E_{s’\sim P_{s\pi(s)}}[V^{\pi}(s’)]$。这一项为从状态$s’$出发的扣奖励的期望总和，其中$s’$的分布为$P_{s\pi(s)}$，该分布是我们在MDP中从状态$s$采取的第一个动作$\pi(s)$之后的分布。因此，上述第二项给出了在MDP第一步之后获得的折扣奖励的期望总和。

​ 贝尔曼方程可以用来高效地计算出$V^{\pi}$。特别地，在有限状态MDP$(|S|<\infty)$中，我们可以对每个状态$s$的$V^{\pi}(s)$写出方程。这样就得到了有$|S|$个变量的$|S|$个线性方程，未知量为每个状态$s$对应的$V^{\pi}(s)$，这样我们就能高效的解出$V^{\pi}(s)$。

​ 我们也根据下式定义最优价值函数

$$V'(s) =\max_{\pi} V^{\pi}(s) \tag 1$$

换句话说，这是使用任何策略可以获得的折扣奖励的最佳期望总和。关于最优价值函数，还有另一个版本的贝尔曼方程：

$$V' (s) = R(s) + \max_{a\in A}\gamma \sum_{s'\in S} P_{sa}(s') V'(s') \tag 2$$

第一项和之前一样是即时奖励。第二项是采取行动$a$后，获得的未来折扣奖励期望总和的最大值。

​ 我们还按如下方式定义了策略$\pi’: S\mapsto A$：

$$\pi'(s)=\arg \max_{a\in A} \sum_{s'\in S} P_{sa}(s') V'(s') \tag 3$$

注意到$\pi’(s)$给出了达到等式$(2)$最大值的行动$a$

​ 对于每个状态$s$和每个策略$\pi​$，我们有

$$V'(s)= V^{\pi'}(s) \ge V^{\pi}(s)$$

第一个等式的含义为对每个状态$s$，其最优价值函数$V’$等于$V^{\pi’}$。此外，上述不等式表示$\pi’$的价值至少和其他任何策略的价值一样大。换句话说，等式$(3)$定义的$\pi’$实最优策略。

​ 注意到，$\pi’ $一个有趣的特点是，它是所有状态的最优策略。具体的，对每个状态$s$，同一个策略$\pi’$达到等式$(1)$的最大值。这意味着无论MDP的初始状态是什么，我们可以使用同一个策略$\pi’$。

2.值迭代和策略迭代

我们现在开始介绍两个解决有限状态MDP的高效算法。暂时，我们只考虑状态和行动空间有限的MDP$(|S|<\infty,|A|<\infty)$。

​ 第一个算法，值迭代，如下所示：

• 对每个状态$s$，初始化$V(s):=0$

• 重复直到收敛{

  • 对每个状态，更新$V(s):=R(s) + \max_{a\in A}\gamma \sum_{s’\in S}
    P_{sa}(s’) V(s’)$

  }

这个算法可以理解为利用贝尔曼方程$(2)$重复更新价值函数。

​ 在算法的内部循环中，有两个可能的方法进行更新。在第一个方法中，我们可以对每个状态$s$计算新的$V(s)$，然后用新值覆盖全部旧值。这种方法被称为同步更新。在这种情况下，该算法可以被视为实现“Bellman备份运算符”，其获取价值函数的当前估计，并将其映射到新估计。或者，我们也可以执行异步更新。这里，我们将按照某种顺序遍历状态，每次更新一个价值。

​ 在同步或异步更新下，可以发现$V$最终会收敛到$V’ $。找到$V’$后，我们可以利用等式$(3)$找到最优策略。

​ 除了值迭代，还有第二个标准算法来找到MDP的最优策略。策略迭代算法如下所示：

• 1.随机初始化$\pi$

• 2.重复直至收敛{

  • (a)令$V:=V^{\pi}$
  • (b)对每个状态$s$，令$\pi(s)=\arg \max_{a\in A} \sum_{s’\in S}
    P_{sa}(s’) V(s’)$

  }

因此，内层循环重复计算当前策略的价值函数，然后利用当前价值函数更新策略。（步骤(b)找到的策略$\pi$被称为关于$V​$的贪心策略。）注意到步骤(a)可以通过求解贝尔曼方程来完成。

​ 在最多有限步迭代后，$V$将收敛到$V’$，$\pi$将收敛到$\pi’$。

​ 值迭代和策略迭代都是处理MDP的标准算法，目前还没有关于哪种算法更好的普遍意见。对于小的MDP，策略迭代通常非常快，并且在很少的步骤后就会收敛。但是，对于有很大状态空间的MDP，解出$V^{\pi}$将涉及到求解很大的线性方程组，这将很困难。对于这类问题，值迭代将被使用。由于这个原因，在实际中，值迭代比策略迭代使用的更频繁。

3.学习MDP模型

到目前为止，我们讨论的MDP的MDP和算法都是在假设状态转移概率和奖励是已知的情形下。在很多实际的问题中，我们没有明确给出状态转移概率和奖励，而是必须从数据中估计它们。（通常，$S,A,\gamma$已知。）

​ 例如，假设对于倒立摆问题，在MDP中有一系列实验，按如下所示：

$$s_0^{(1)} \overset{a_0^{(1)}} \longrightarrow s_1^{(1)} \overset{a_1^{(1)}} \longrightarrow s_2^{(1)} \overset{a_2^{(1)}} \longrightarrow s_3^{(1)} \overset{a_3^{(1)}} \longrightarrow ... \\ s_0^{(2)} \overset{a_0^{(2)}} \longrightarrow s_1^{(2)} \overset{a_1^{(2)}} \longrightarrow s_2^{(2)} \overset{a_2^{(2)}} \longrightarrow s_3^{(2)} \overset{a_3^{(2)}} \longrightarrow ... \\ ...$$

​ 这里，$s^{(j)}_i$为实验$j$在时刻$i$的状态，$a_i^{(j)}$为该状态采取的行动。在实际中，上述每个试验都可以运行直到MDP终止（例如，如果杆在倒立摆问题中倒下），或者它可能运行某个很大但有限的时间步长。

​ 给定MDP中一系列试验得到的“经验”，我们可以很容易地推导出状态转移概率的最大似然估计：

$$P_{sa}(s')= \frac{\sharp我们在状态s采取行动a到达s'的次数}{\sharp我们在状态s采取行动a的次数}\tag 4$$

或者，如果上述比值为”$0/0$”，对应的情形为在状态$s$没有采取过行动$a$，我们可以用$1/|S|$简单估计$P_{sa}(s’)$。（即，把$P_{sa}$估计为所有状态上的均匀分布。）

​ 注意到，如果我们在MDP中得到更多经验（观测更多实验），有一种有效的方法可以使用新的经验更新我们估计的状态转移概率。具体来说，如果我们保持$(4)$的分子和分母项的计数，那么当我们观察更多的试验时，我们可以简单地累加这些计数。计算这些计数的比例给出我们对于$P_{sa}$的估计。

​ 利用类似的过程，如果$R$未知，我们可以选择状态$s$的期望即时奖励$R(s) $的估计值为状态$s$中观察到的平均奖励。

​ 在学习了MDP模型之后，我们可以使用值迭代或策略迭代来估计转移概率和奖励函数，以此来解决MDP。例如，结合模型学习和值迭代，以下是一种可能的算法，用于在具有未知状态转移概率的MDP中进行学习：

• 1.随机初始化$\pi$

• 2.重复{

  • (a)在MDP中执行$\pi$，进行一系列实验。
  • (b)利用MDP中积累的经验，更新我们对$P_{sa} $的估计值（如果可以的话，也对$R$进行更新）。
  • (c)利用估计的状态转移概率和奖励进行值迭代来获得价值函数的新估计。
  • (d)更新$\pi$为关于$V$的贪心策略。

  }

​ 我们注意到，对于这个特别的算法，有一个简单的优化可以使它运行得更快。具体来说，在我们应用值迭代的算法的内部循环中，不使用$V=0$的初始值进行迭代，而是使用算法前一次迭代期间找到的解初始化它，这样值迭代就有更好的初始起点，使其更快收敛。