---

  下图介绍了强化学习里面智能体与环境之间的交互，智能体得到环境的状态后，它会采取动作，并把这个采取的动作返还给环境。环境得到智能体的动作后，它会进入下一个状态，把下一个状态传给智能体。在强化学习中，智能体与环境就是这样进行交互的，这个交互过程可以通过马尔可夫决策过程来表示，所以马尔可夫决策过程是强化学习的基本框架。

  本章将介绍马尔可夫决策过程。在介绍马尔可夫决策过程之前，我们先介绍它的简化版本：马尔可夫过程（Markov process，MP）以及马尔可夫奖励过程（Markov reward process，MRP）。通过与这两种过程的比较，我们可以更容易理解马尔可夫决策过程。其次，我们会介绍马尔可夫决策过程中的策略评估（policy evaluation），就是当给定决策后，我们怎么去计算它的价值函数。最后，我们会介绍马尔可夫决策过程的控制，具体有策略迭代（policy iteration）和价值迭代（value iteration）两种算法。在马尔可夫决策过程中，它的环境是全部可观测的。但是很多时候环境里面有些量是不可观测的，但是这个部分观测的问题也可以转换成马尔可夫决策过程的问题。

---

一、马尔可夫过程

1.1 马尔可夫性质

  在随机过程中, 马尔可夫性质（Markov property）是指一个随机过程在给定现在状态及所有过去状态情况下, 其末来状态的条件概率分布仅依赖于当前状态。以离散随机过程为例, 假设随机变量 $X_0,X_1,\cdots ,X_T$ 构成一个随机过程。这些随机变量的所有可能取值的集合被称为状态空间 (state space)。 如果 $X_{t+1}$ 对于过去状态的条件概率分布仅是 $X_t$ 的一个函数, 则：

  其中, $X_{0:t}$ 表示变量集合 $X_0,X_1,\cdots ,X_t,x_{0:t}$ 为在状态空间中的状态序列 $x_0,x_1,\cdots ,x_t$ 。
  马尔可夫性质也可以描述为给定当前状态时，将来的状态与过去状态是条件独立的。如果某一个过程满足马尔可夫性质，那么未来的转移与过去的是独立的，它只取决于现在。马尔可夫性质是所有马尔可夫过程的基础。

1.2 马尔可夫链

  马尔可夫过程是一组具有马尔可夫性质的随机变量序列 $s_1,\cdots ,s_t$, 其中下一个时刻的状态 $s_{t+1}$ 只取 决于当前状态 $s_t$ 。我们设状态的历史为 h t = { s 1 , s 2 , s 3 , … , s t } h_t=\left\{s_1, s_2, s_3, \ldots, s_t\right\} ht​={s1​,s2​,s3​,…,st​} ( $h_t$ 包含了之前的所有状态), 则马尔可夫 过程满足条件：

  从当前 $s_t$ 转移到 $s_{t+1}$, 它是直接就等于它之前所有的状态转移到 $s_{t+1}$ 。
  离散时间的马尔可夫过程也称为马尔可夫链 (Markov chain)。马尔可夫链是最简单的马尔可夫过 程, 其状态是有限的。例如, 下图里面有 4 个状态, 这 4 个状态在 $s_1,s_2,s_3,s_4$ 之间互相转移。比如从 $s_1$ 开始, $s_1$ 有 $0.1$ 的概率继续存留在 $s_1$ 状态, 有 $0.2$ 的概率转移到 $s_2$, 有 $0.7$ 的概率转移到 $s_4$ 。如果 $s_4$ 是我们的当前状态, 它有 $0.3$ 的概率转移到 $s_2$, 有 $0.2$ 的概率转移到 $s_3$, 有 $0.5$ 的概率留在当前状态。

  我们可以用状态转移矩阵 (state transition matrix) $\mathbf{P}$ 来描述状态转移 $p\left(s_{t+1}=s^{\prime }\mid s_t=s\right)$ :

  状态转移矩阵类似于条件概率 ( conditional probability), 它表示当我们知道当前我们在状态 $s_t$ 时, 到达 下面所有状态的概率。所以它的每一行描述的是从一个节点到达所有其他节点的概率。

1.3 马尔可夫过程的例子

  如下图所示为一个马尔可夫过程的例子, 这里有七个状态。比如从 $s_1$ 开始, 它有 $0.4$ 的概率到 $s_2$, 有 $0.6$ 的概率留在当前的状态。 $s_2$ 有 $0.4$ 的概率到 $s_1$, 有 $0.4$ 的概率到 $s_3$, 另外有 $0.2$ 的概率留在当前状 态。所以给定状态转移的马尔可夫链后, 我们可以对这个链进行采样, 这样就会得到一串轨迹。例如, 假 设我们从状态 $s_3$ 开始, 可以得到 3 个轨迹：

• $s_3,s_4,s_5,s_6,s_6$
• $s_3,s_2,s_3,s_2,s_1$
• $s_3,s_4,s_4,s_5,s_5$

  通过对状态的采样, 我们可以生成很多这样的轨迹。

---

二、马尔可夫奖励过程

  马尔可夫奖励过程（Markov reward process, MRP）是马尔可夫链加上奖励函数。在马尔可夫奖励过程中，状态转移矩阵和状态都与马尔可夫链一样，只是多了奖励函数（reward function）。奖励函数R 是一个期望，表示当我们到达某一个状态的时候，可以获得多大的奖励。这里另外定义了折扣因子γ。如果状态数是有限的，那么R 可以是一个向量。

2.1 回报与价值函数

  这里我们进一步定义一些概念。范围 (horizon) 是指一个回合的长度（每个回合最大的时间步数), 它是由有限个步数决定的。回报（return）可以定义为奖励的逐步叠加, 假设时刻 $t$ 后的奖励序列为 $r_{t+1},r_{t+2},r_{t+3},\cdots$, 则回报为：
  其中, $T$ 是最终时刻, $\gamma$ 是折扣因子, 越往后得到的奖励, 折扣越多。这说明我们更希望得到现有的奖励, 对 末来的奖励要打折扣。当我们有了回报之后, 就可以定义状态的价值了, 就是状态价值函数 (state-value function)。对于马尔可夫奖励过程, 状态价值函数被定义成回报的期望, 即：

  其中, $G_t$ 是之前定义的折扣回报 (discounted return)。我们对 $G_t$ 取了一个期望, 期望就是从这个状 态开始, 我们可能获得多大的价值。所以期望也可以看成末来可能获得奖励的当前价值的表现, 就是当我 们进人某一个状态后, 我们现在有多大的价值。
  我们使用折扣因子的原因如下。第一, 有些马尔可夫过程是带环的, 它并不会终结, 我们想避免无穷 的奖励。第二, 我们并不能建立完美的模拟环境的模型，我们对末来的评估不一定是准确的，我们不一定 完全信任模型, 因为这种不确定性, 所以我们对末来的评估增加一个折扣。我们想把这个不确定性表示出 来, 希望尽可能快地得到奖励, 而不是在末来某一个点得到奖励。第三, 如果奖励是有实际价值的, 我们 可能更希望立刻就得到奖励, 而不是后面再得到奖励（现在的钱比以后的钱更有价值）。最后, 我们也更 想得到即时奖励。有些时候可以把折扣因子设为 $0(\gamma =0)$, 我们就只关注当前的奖励。我们也可以把折 扣因子设为 $1(\gamma =1)$, 对末来的奖励并没有打折扣, 末来获得的奖励与当前获得的奖励是一样的。折扣 因子可以作为强化学习智能体的一个超参数 (hyperparameter) 来进行调整, 通过调整折扣因子, 我们可 以得到不同动作的智能体。
  在马尔可夫奖励过程里面, 我们如何计算价值呢? 马尔可夫奖励过程依旧是状态转移, 其奖励函数可以定义为：智能体进人第一个状态 $s_1$ 的时候会得到 5 的奖励, 进人第七个状态 $s_7$ 的时候会 得到 10 的奖励, 进人其他状态都没有奖励。我们可以用向量来表示奖励函数, 即：

  我们对 4 步的回合 $(\gamma =0.5)$ 来采样回报 $G$ 。
  (1) $s_4,s_5,s_6,s_7$ 的回报 : $0+0.5\times 0+0.25\times 0+0.125\times 10=1.25$
  (2) $s_4,s_3,s_2,s_1$ 的回报 : $0+0.5\times 0+0.25\times 0+0.125\times 5=0.625$
  (3) $s_4,s_5,s_6,s_6$ 的回报: $:0+0.5\times 0+0.25\times 0+0.125\times 0=0$
  我们现在可以计算每一个轨迹得到的奖励, 比如我们对轨迹 $s_4,s_5,s_6,s_7$ 的奖励进行计算, 这里折扣 因子是 $0.5$ 。在 $s_4$ 的时候, 奖励为 0 。下一个状态 $s_5$ 的时候, 因为我们已经到了下一步, 所以要把 $s_5$ 进 行折扣, $s_5$ 的奖励也是 0 。然后是 $s_6$, 奖励也是 0 , 折扣因子应该是 $0.25$ 。到达 $s_7$ 后, 我们获得了一个 奖励, 但是因为状态 $s_7$ 的奖励是末来才获得的奖励, 所以我们要对之进行 3 次折扣。最终这个轨迹的回 报就是 $1.25$ 。类似地, 我们可以得到其他轨迹的回报。

  这里就引出了一个问题, 当我们有了一些轨迹的实际回报时, 怎么计算它的价值函数呢? 比如我们想 知道 $s_4$ 的价值, 即当我们进人 $s_4$ 后, 它的价值到底如何? 一个可行的做法就是我们可以生成很多轨迹, 然 后把轨迹都叠加起来。比如我们可以从 $s_4$ 开始, 采样生成很多轨迹, 把这些轨迹的回报都计算出来, 然后 将其取平均值作为我们进人 $s_4$ 的价值。这其实是一种计算价值函数的办法, 也就是通过蒙特卡洛 (Monte Carlo, MC) 采样的方法计算 $s_4$ 的价值。

2.2 贝尔曼方程

  其中, $s^{\prime }$ 可以看成末来的所有状态, $p\left(s^{\prime }\mid s\right)$ 是指从当前状态转移到未来状态的概率。 $V\left(s^{\prime }\right)$ 代表的是未来 某一个状态的价值。我们从当前状态开始, 有一定的概率去侄末来的所有状态, 所以我们要把 $p\left(s^{\prime }\mid s\right)$ 写 上去。我们得到了未来状态后, 乘一个 $\gamma$, 这样就可以把末来的奖励打折扣。 $\gamma {\sum }_{s^{\prime }\in S}p\left(s^{\prime }\mid s\right)V\left(s^{\prime }\right)$ 可以 看成未来来奖励的折扣总和 (discounted sum of future reward)。
贝尔曼方程定义了当前状态与未来状态之间的关系。未来奖励的折扣总和加上即时奖励, 就组成了贝 尔曼方程。

矩阵形式的贝尔曼方程

$$\left(\begin{array}{c}V\left(s_1\right)\\ V\left(s_2\right)\\ ⋮\\ V\left(s_N\right)\end{array}\right)=\left(\begin{array}{c}R\left(s_1\right)\\ R\left(s_2\right)\\ ⋮\\ R\left(s_N\right)\end{array}\right)+\gamma \left(\begin{array}{cccc}p\left(s_1\mid s_1\right)& p\left(s_2\mid s_1\right)& \dots & p\left(s_N\mid s_1\right)\\ p\left(s_1\mid s_2\right)& p\left(s_2\mid s_2\right)& \dots & p\left(s_N\mid s_2\right)\\ ⋮& ⋮& \ddots & ⋮\\ p\left(s_1\mid s_N\right)& p\left(s_2\mid s_N\right)& \dots & p\left(s_N\mid s_N\right)\end{array}\right)\left(\begin{array}{c}V\left(s_1\right)\\ V\left(s_2\right)\\ ⋮\\ V\left(s_N\right)\end{array}\right)$$

直接求解

$$\begin{array}{rl}\mathbf{V}& =\mathbf{R}+\gamma \mathbf{P}\mathbf{V}\\ \mathbf{I}\mathbf{V}& =\mathbf{R}+\gamma \mathbf{P}\mathbf{V}\\ (\mathbf{I}-\gamma \mathbf{P})\mathbf{V}& =\mathbf{R}\\ \mathbf{V}& =(\mathbf{I}-\gamma \mathbf{P}{)}^{-1}\mathbf{R}\end{array}$$

直接求解存在的问题：
状态很多时，意味着我们需要对大矩阵进行求解，而求逆的复杂度是$O(N^3)$，所以大矩阵求逆是非常困难的，这种通过解析解去求解的方法只适用于很小量的马尔可夫奖励过程

2.3 计算马尔可夫奖励过程价值的迭代算法

为了求出状态非常多的MRP的价值，通常有以下三个迭代算法：

• 动态规划
• 蒙特卡洛
• 时序差分

2.3.1 动态规划方法

通过自举（bootstrapping）的方法不停地迭代贝尔曼方程，当最后更新的状态与我们上一个状态的区别并不大的时候，更新就可以停止

2.3.2 蒙特卡洛方法

• 从某个状态开始，依状态转移概率进行”随波逐流“
• ”随波逐流“会产生一个轨迹，一个轨迹就会有一个奖励
• 将折扣的奖励g算出来
• 累加到总奖励$G_t$中
• 当有了足够数量的轨迹时，以$\frac{G_t}{N}$作为某个状态的价值（N为轨迹数量）

2.3.3 马尔可夫奖励过程的例子

我们通过一个形象的例子来理解马尔可夫奖励过程。我们把一艘纸船放到河流之中，它就会随着水流而流动，它自身是没有动力的。所以我们可以把马尔可夫奖励过程看成一个随波逐流的例子，当我们从某一个点开始的时候，纸船就会随着事先定义好的状态转移进行流动，它到达每个状态后，我们都有可能获得一些奖励。

---

三、马尔可夫决策过程

相对于马尔可夫奖励过程，马尔可夫决策过程多了决策（决策是指动作），其他的定义与马尔可夫奖励过程的是类似的。此外，状态转移也多了一个条件，变成了$p\left(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a\right)$。未来的状态不仅依赖于当前的状态，也依赖于在当前状态智能体采取的动作。马尔可夫决策过程满足条件：$$p\left(s_{t+1}\mid s_t,a_t\right)=p\left(s_{t+1}\mid h_t,a_t\right)$$
对于奖励函数，它也多了一个当前的动作，变成了 $R\left(s_t=s,a_t=a\right)=\mathbb{E}\left[r_t\mid s_t=s,a_t=a\right]$ 。当前的状态以及采取的动作会决定智能体在当前可能得到的奖励多少。

3.1 马尔可夫决策过程中的策略

策略定义了在某一个状态应该采取什么样的动作。知道当前状态后，我们可以把当前状态代入策略函数来得到一个概率

$$\pi (a\mid s)=p\left(a_t=a\mid s_t=s\right)$$

概率代表在所有可能的动作里面怎样采取行动，比如可能有 0.7 的概率往左走，有 0.3 的概率往右走，这是一个概率的表示。另外策略也可能是确定的，它有可能直接输出一个值，或者直接告诉我们当前应该采取什么样的动作，而不是一个动作的概率。假设概率函数是平稳的（stationary），不同时间点，我们采取的动作其实都是在对策略函数进行采样。

当策略$\pi$已知时，我们就可以得到状态转移概率

$$P_{\pi }\left(s^{\prime }\mid s\right)=\sum _{a\in A}\pi (a\mid s)p\left(s^{\prime }\mid s,a\right)$$

对于奖励函数，我们也可以把动作去掉，这样就会得到类似于马尔可夫奖励过程的奖励函数，即

$$r_{\pi }(s)=\sum _{a\in A}\pi (a\mid s)R(s,a)$$

3.2 马尔可夫决策过程和马尔可夫过程/马尔可夫奖励过程的区别

在MRP中，状态的转移是直接通过状态转移概率矩阵得到的。

而在MDP中，状态的转移是先确定动作，然后再确定状态的改变

3.3 马尔可夫决策过程中的价值函数

马尔可夫决策过程中的价值函数可定义为
$$V_{\pi }(s)={\mathbb{E}}_{\pi }\left[G_t\mid s_t=s\right]$$
其中，期望基于我们采取的策略。当策略决定后，我们通过对策略进行采样来得到一个期望，计算出它的价值函数。
这里另外引入了一个 $\mathrm{Q}$ 函数 (Q-function)。 $\mathrm{Q}$ 函数也被称为动作价值函数 (action-value function)。 $\mathrm{Q}$ 函数定义的是在某一个状态采取某一个动作，它有可能得到的回报的一个期望，即
$$Q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[G_t\mid s_t=s,a_t=a\right]$$
这里的期望其实也是基于策略函数的。所以我们需要对策略函数进行一个加和，然后得到它的价值。对 $Q$ 函数中的动作进行加和，就可以得到价值函数:
$$V_{\pi }(s)=\sum _{a\in A}\pi (a\mid s)Q_{\pi }(s,a)$$

对 $Q$ 函数的贝尔曼方程进行推导:

$$\begin{array}{rl}Q(s,a)& =\mathbb{E}\left[G_t\mid s_t=s,a_t=a\right]\\ & =\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\dots \mid s_t=s,a_t=a\right]\\ & =\mathbb{E}\left[r_{t+1}\mid s_t=s,a_t=a\right]+\gamma \mathbb{E}\left[r_{t+2}+\gamma r_{t+3}+{\gamma }^2{r}_{t+4}+\dots \mid s_t=s,a_t=a\right]\\ & =R(s,a)+\gamma \mathbb{E}\left[G_{t+1}\mid s_t=s,a_t=a\right]\\ & =R(s,a)+\gamma \mathbb{E}\left[V\left(s_{t+1}\right)\mid s_t=s,a_t=a\right]\\ & =R(s,a)+\gamma \sum _{s^{\prime }\in S}p\left(s^{\prime }\mid s,a\right)V\left(s^{\prime }\right)\end{array}$$

3.4 贝尔曼期望方程

我们可以把状态价值函数和 Q 函数拆解成两个部分：即时奖励和后续状态的折扣价值（discounted value of successor state）。 通过对状态价值函数进行分解，我们就可以得到一个类似于之前马尔可夫奖励过程的贝尔曼方程————贝尔曼期望方程（Bellman expectation equation）：

$$V_{\pi }(s)={\mathbb{E}}_{\pi }\left[r_{t+1}+\gamma V_{\pi }\left(s_{t+1}\right)\mid s_t=s\right]$$
对于 $\mathrm{Q}$ 函数，我们也可以做类似的分解，得到 $\mathrm{Q}$ 函数的贝尔曼期望方程:
$$Q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[r_{t+1}+\gamma Q_{\pi }\left(s_{t+1},a_{t+1}\right)\mid s_t=s,a_t=a\right]$$
贝尔曼期望方程定义了当前状态与未来状态之间的关联。
我们进一步进行简单的分解
$$\begin{gathered} V_{\pi }(s)=\sum _{a\in A}\pi (a\mid s)Q_{\pi }(s,a) \\ {Q}_{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}p\left(s^{\prime }\mid s,a\right)V_{\pi }\left(s^{\prime }\right) \end{gathered}$$

上式代表状态价值函数与 Q 函数之间的关联。
$$V_{\pi }(s)=\sum _{a\in A}\pi (a\mid s)\left(R(s,a)+\gamma \sum _{s^{\prime }\in S}p\left(s^{\prime }\mid s,a\right)V_{\pi }\left(s^{\prime }\right)\right)$$
上式代表当前状态的价值与末来状态价值之间的关联。

$$Q_{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}p\left(s^{\prime }\mid s,a\right)\sum _{a^{\prime }\in A}\pi \left(a^{\prime }\mid s^{\prime }\right)Q_{\pi }\left(s^{\prime },a^{\prime }\right)$$
上式代表当前时刻的 $Q$ 函数与末来时刻的 $Q$ 函数之间的关联。

3.5 备份图

备份类似于自举之间的迭代关系，对于某一个状态，它的当前价值是与它的未来价值线性相关的。 与下图类似的图称为备份图（backup diagram）或回溯图，因为它们所示的关系构成了更新或备份操作的基础，而这些操作是强化学习方法的核心。这些操作将价值信息从一个状态（或状态-动作对）的后继状态（或状态-动作对）转移回它。 每一个空心圆圈代表一个状态，每一个实心圆圈代表一个状态-动作对。

3.6 策略评估

已知马尔可夫决策过程以及要采取的策略 $\pi$ ，计算价值函数 $V_{\pi }(s)$ 的过程就是策略评估。

策略评估在有些地方也被称为价值预测，也就是预测我们当前采取的策略最终会产生多少价值。

3.7 预测与控制

3.7.1 预测

输入：马尔可夫决策过程$<S,A,P,R,\gamma >$和策略 $\pi$
输出：价值函数$V_{\pi }$
解释：计算每个状态的价值

3.7.2 控制

输入：马尔可夫决策过程$<S,A,P,R,\gamma >$
输出：最佳价值函数$V^{\ast }$和最佳策略${\pi }^{\ast }$
解释：寻找一个最佳策略以及它的最佳价值函数

3.8 动态规划

动态规划（dynamic programming，DP）适合解决满足最优子结构（optimal substructure）和重叠子问题（overlapping subproblem）两个性质的问题。最优子结构意味着，问题可以拆分成一个个的小问题，通过解决这些小问题，我们能够组合小问题的答案，得到原问题的答案，即最优的解。重叠子问题意味着，子问题出现多次，并且子问题的解决方案能够被重复使用，我们可以保存子问题的首次计算结果，在再次需要时直接使用。

马尔可夫决策过程是满足动态规划的要求的，在贝尔曼方程里面，我们可以把它分解成递归的结构。当我们把它分解成递归的结构的时候，如果子问题的子状态能得到一个值，那么它的未来状态因为与子状态是直接相关的，我们也可以将之推算出来。价值函数可以存储并重用子问题的最佳的解。动态规划应用于马尔可夫决策过程的规划问题而不是学习问题，我们必须对环境是完全已知的，才能做动态规划，也就是要知道状态转移概率和对应的奖励。使用动态规划完成预测问题和控制问题的求解，是解决马尔可夫决策过程预测问题和控制问题的非常有效的方式。

3.9 马尔可夫决策过程中的策略评估

策略评估就是给定马尔可夫决策过程和策略，评估我们可以获得多少价值，即对于当前策略，我们可以得到多大的价值。

我们来看一个动态的例子

斯坦福大学的一个网页

• 每个格子都代表一个状态。每个格子里面有一个初始值0。
• 每个格子里还有一个箭头，这个箭头是指智能体在当前状态应该采取什么策略。
• 我们这里采取随机的策略，不管智能体在哪一个状态，它往上、下、左、右的概率都是相同的。比如在某个状态，智能体都有上、下、左、右各 0.25 的概率采取某一个动作，所以它的动作是完全随机的。
• 我们也定义了奖励函数，我们可以看到有些格子里面有一个R的值，比如有些值是负的。我们可以看到有几个格子里面是 −1 的奖励，只有一个 +1 奖励的格子。
• 在网格世界的中间位置，我们可以看到有一个R的值是 1。所以每个状态对应一个值，有一些状态没有任何值，它的奖励就为0。

初始化时，所有的$V(s)$都是0

迭代一次之后，有些状态的值已经产生了变化

再迭代一次，之前有值的状态的周围状态也开始有值。因为周围状态与之前有值的状态是临近的，所以这就相当于把周围的状态转移过来

当我们迭代了很多次之后，有些很远的状态的价值函数已经有值了，而且整个过程是一个呈逐渐扩散的过程，这其实也是策略评估的可视化。当我们每一步进行迭代的时候，远的状态就会得到一些值，值从已经有奖励的状态逐渐扩散。

当我们执行很多次迭代之后，各个状态的值会逐渐稳定下来，最后值就会确定不变。收敛之后，每个状态的值就是它的状态价值。
80次迭代时，基本已经收敛

3.10 马尔可夫决策过程控制

寻找最佳策略的过程就是马尔可夫决策过程的控制过程。马尔可夫决策过程控制就是去寻找一个最佳策略使我们得到一个最大的价值函数值，即

$${\pi }^{\ast }(s)=\underset{\pi }{\mathrm{argmax}}{V}_{\pi }(s)$$

当Q函数收敛后，因为 Q 函数是关于状态与动作的函数，所以如果在某个状态采取某个动作，可以使得 Q 函数最大化，那么这个动作就是最佳的动作。如果我们能优化出一个 Q 函数 $Q^{\ast }(s,a)$，就可以直接在 Q 函数中取一个让 Q 函数值最大化的动作的值，就可以提取出最佳策略。

对于一个事先定好的马尔可夫决策过程，当智能体采取最佳策略的时候，最佳策略一般都是确定的，而且是稳定的（它不会随着时间的变化而变化）。但最佳策略不一定是唯一的，多种动作可能会取得相同的价值。

Q: 怎样进行策略搜索？
A:最简单的策略搜索方法就是穷举。假设状态和动作都是有限的，那么每个状态我们可以采取A种动作的策略，总共就是$A^S$个可能的策略。我们可以把策略穷举一遍，算出每种策略的价值函数，对比一下就可以得到最佳策略。
但是穷举非常没有效率，所以我们要采取其他方法。搜索最佳策略有两种常用的方法：策略迭代和价值迭代。

3.10.1 策略迭代

策略迭代由两个步骤组成：策略评估和策略改进

第一个步骤是策略评估，当前我们在优化策略 $\pi$，在优化过程中得到一个最新的策略。我们先保证这个策略不变，然后估计它的价值，即给定当前的策略函数来估计状态价值函数。

第二个步骤是策略改进，得到 状态价值函数后，我们可以进一步推算出它的 Q 函数。得到 Q 函数后，我们直接对 Q 函数进行最大化，通过在 Q 函数做一个贪心的搜索来进一步改进策略。对于每个状态，策略改进会得到它的新一轮的策略，对于每个状态，我们取使它得到最大值的动作，即

$${\pi }_{i+1}(s)=\underset{a}{\mathrm{argmax}}{Q}_{{\pi }_i}(s,a)$$

这两个步骤一直在迭代进行

贝尔曼最优方程

当我们一直采取 arg max 操作的时候，我们会得到一个单调的递增。通过采取这种贪心操作（arg max 操作），我们就会得到更好的或者不变的策略，而不会使价值函数变差。所以当改进停止后，我们就会得到一个最佳策略。当改进停止后，我们取让 Q 函数值最大化的动作，Q 函数就会直接变成价值函数，即:
$$Q_{\pi }\left(s,{\pi }^{\prime }(s)\right)=\underset{a\in A}{\max }{Q}_{\pi }(s,a)=Q_{\pi }(s,\pi (s))=V_{\pi }(s)$$

我们也就可以得到贝尔曼最优方程（Bellman optimality equation）
$$V_{\pi }(s)=\underset{a\in A}{\max }{Q}_{\pi }(s,a)$$

贝尔曼最优方程表明：最佳策略下的一个状态的价值必须等于在这个状态下采取最好动作得到的回报的期望。 当马尔可夫决策过程满足贝尔曼最优方程的时候，整个马尔可夫决策过程已经达到最佳的状态。

3.10.2 价值迭代

最优性原理定理（principle of optimality theorem）： 一个策略$\pi (a|s)$在状态$s$达到了最优价值，也就是$V_{\pi }(s)=V^{\ast }(s)$成立，当且仅当对于任何能够从$s$到达的$s^{\prime }$都已经达到了最优价值。也就是对于所有的$s^{\prime }$，$V_{\pi }(s^{\prime })=V^{\ast }(s^{\prime })$恒成立。

如果我们知道子问题 $V^{\ast }\left(s^{\prime }\right)$ 的最优解，就可以通过价值迭代来得到最优的 $V^{\ast }(s)$ 的解。价值迭代就是把贝尔曼最优方程当成一个更新规则来进行，即

$$V(s)\leftarrow \underset{a\in A}{\max }\left(R(s,a)+\gamma \sum _{s^{\prime }\in S}p\left(s^{\prime }\mid s,a\right)V\left(s^{\prime }\right)\right)$$

只有当整个马尔可夫决策过程已经达到最佳的状态时，上式才满足

我们不停地迭代贝尔曼最优方程，价值函数就能逐渐趋向于最佳的价值函数，这是价值迭代算法的精髓。

为了得到最佳的$V^{\ast }$，对于每个状态的$V$，我们直接通过贝尔曼最优方程进行迭代，迭代多次之后，价值函数就会收敛。这种价值迭代算法也被称为确认性价值迭代（deterministic value iteration）。

价值迭代算法的过程如下:

(1) 初始化：令$k=1$，对于所有状态$s$，$V_0(s)=0$

(2) 对于$k=1:H$($H$是让$V(s)$收敛所需的迭代次数)，对所有状态$s$执行下面操作，最后 $k=k+1$，直到$k=H$ ，迭代停止

$$\begin{array}{c}{Q}_{k+1}(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}p\left(s^{\prime }\mid s,a\right)V_k\left(s^{\prime }\right)\\ V_{k+1}(s)=\underset{a}{\max }{Q}_{k+1}(s,a)\end{array}$$

在迭代后提取最优策略

$$\pi (s)=\underset{a}{\mathrm{argmax}}\left[R(s,a)+\gamma \sum _{s^{\prime }\in S}p\left(s^{\prime }\mid s,a\right)V_{H+1}\left(s^{\prime }\right)\right]$$

3.10.3 策略迭代与价值迭代的区别

策略迭代特点：估计$V(s)$，计算$Q_{{\pi }_i}(s,a)$，然后根据$max{Q}_{{\pi }_i}(s,a)$更新策略为${\pi }_{i+1}$，如此循环直到收敛
不断更新的是策略$\pi$

价值迭代特点：初始化价值函数$V(s)=0$，然后不断通过贝尔曼最优方程去更新价值函数
不断更新的是价值函数$V(s)$

3.11 马尔可夫决策过程中的预测和控制总结

总结如表所示，我们使用动态规划算法来解马尔可夫决策过程里面的预测和控制，并且采取不同的贝尔曼方程。

• 对于预测问题，即策略评估的问题，我们不停地执行贝尔曼期望方程，这样就可以估计出给定的策略，然后得到价值函数。
• 对于控制问题，如果我们采取的算法是策略迭代，使用的就是贝尔曼期望方程；如果我们采取的算法是价值迭代，使用的就是贝尔曼最优方程。

问题	贝尔曼方程	算法
预测	贝尔曼方程	迭代策略评估
控制	贝尔曼期望方程	策略迭代
控制	贝尔曼最优方程	价值迭代

---

四、关键词总结

• 马尔可夫性质（Markov property，MP）: 如果某一个过程未来的状态与过去的状态无关，只由现在的状态决定，那么其具有马尔可夫性质。换句话说，一个状态的下一个状态只取决于它的当前状态，而与它当前状态之前的状态都没有关系。
• 马尔可夫链（Markov chain）: 概率论和数理统计中具有马尔可夫性质且存在于离散的指数集（index set）和状态空间（state space）内的随机过程（stochastic process）。
• 状态转移矩阵（state transition matrix）: 状态转移矩阵类似于条件概率（conditional probability），其表示当智能体到达某状态后，到达其他所有状态的概率。矩阵的每一行描述的是从某节点到达所有其他节点的概率。
• 马尔可夫奖励过程（Markov reward process，MRP）：本质是马尔可夫链加上一个奖励函数。在马尔可夫奖励过程中，状态转移矩阵和它的状态都与马尔可夫链的一样，只多了一个奖励函数。奖励函数是一个期望，即在某一个状态可以获得多大的奖励。
• 范围（horizon）: 定义了同一个回合（episode）或者一个完整轨迹的长度，它是由有限个步数决定的。
• 回报（return）: 把奖励进行折扣（discounted），然后获得的对应的奖励。
• 贝尔曼方程（Bellman equation）: 其定义了当前状态与未来状态的迭代关系，表示当前状态的价值函数可以通过下个状态的价值函数来计算。贝尔曼方程因其提出者、动态规划创始人理查德· 贝尔曼（Richard Bellman）而得名，同时也被叫作“动态规划方程”。贝尔曼方程即$V(s)=R(s)+\gamma {\sum }_{s^{\prime }\in S}P\left(s^{\prime }\mid s\right)V\left(s^{\prime }\right)$。特别地，其矩阵形式为$\mathrm{V}=\mathrm{R}+\gamma \mathrm{PV}$
• 蒙特卡洛算法（Monte Carlo algorithm，MC algorithm）：可用来计算价值函数的值。使用本节中小船的例子，当得到一个马尔可夫奖励过程后，我们可以从某一个状态开始，把小船放到水中，让它随波流动，这样就会产生一个轨迹，从而得到一个折扣后的奖励g 。当积累该奖励到一定数量后，用它直接除以轨迹数量，就会得到其价值函数的值。
• 动态规划算法（dynamic programming，DP）：其可用来计算价值函数的值。通过一直迭代对应的贝尔曼方程，最后使其收敛。当最后更新的状态与上一个状态差距不大的时候，动态规划算法的更新就可以停止。
• Q 函数（Q-function）：其定义的是某一个状态和某一个动作所对应的有可能得到的回报的期望。
• 马尔可夫决策过程中的预测问题：即策略评估问题，给定一个马尔可夫决策过程以及一个策略$\pi$ ，计算它的策略函数，即每个状态的价值函数值是多少。其可以通过动态规划算法解决。
• 马尔可夫决策过程中的控制问题：即寻找一个最佳策略，其输入是马尔可夫决策过程，输出是最佳价值函数（optimal value function）以及最佳策略（optimal policy）。其可以通过动态规划算法解决。
• 最佳价值函数：搜索一种策略π ，使每个状态的价值最大，$V^{\ast }$就是到达每一个状态的极大值。在极大值中，我们得到的策略是最佳策略。最佳策略使得每个状态的价值函数都取得最大值。所以当我们说某一个马尔可夫决策过程的环境可解时，其实就是我们可以得到一个最佳价值函数。

---

五、习题

2-1 为什么在马尔可夫奖励过程中需要有折扣因子?
2-2 为什么矩阵形式的贝尔曼方程的解析解比较难求得?
2-3 计算贝尔曼方程的常见方法有哪些, 它们有什么区别?
2-4 马尔可夫奖励过程与马尔可夫决策过程的区别是什么?
2-5 马尔可夫决策过程中的状态转移与马尔可夫奖励过程中的状态转移的结构或者计算方面的差异有
哪些?
2-6 我们如何寻找最佳策略, 寻找最佳策略方法有哪些?

---

六、面试题

2-1 友善的面试官: 请问马尔可夫过程是什么? 马尔可夫决策过程又是什么? 其中马尔可夫最重要的 性质是什么呢?
2-2 友善的面试官: 请问我们一般怎么求解马尔可夫决策过程?
2-3 友善的面试官: 请问如果数据流不具备马尔可夫性质怎么办? 应该如何处理?
2-4 友善的面试官: 请分别写出基于状态价值函数的贝尔曼方程以及基于动作价值函数的贝尔曼方程。
2-5 友善的面试官: 请问最佳价值函数 $V^{\ast }$ 和最佳策略 ${\pi }^{\ast }$ 为什么等价呢?
2-6 友善的面试官：能不能手写一下第 $n$ 步的价值函数更新公式呀? 另外, 当 $n$ 越来越大时, 价值函 数的期望和方差是分别变大还是变小呢?