03.md

# 马尔可夫决策过程与动态规划

**马尔可夫决策过程**（ **MDP** ）提供了解决**强化学习**（ **RL** ）问题的数学框架。 几乎所有的 RL 问题都可以建模为 MDP。 MDP 被广泛用于解决各种优化问题。 在本章中，我们将了解什么是 MDP 以及如何使用它来解决 RL 问题。 我们还将学习动态编程，它是一种有效解决复杂问题的技术。

在本章中，您将学习以下主题：

*   马尔可夫链与马尔可夫过程
*   马尔可夫决策过程
*   奖励与退货
*   贝尔曼方程
*   使用动态规划求解 Bellman 方程
*   利用价值和政策迭代来解决冻湖问题

# 马尔可夫链与马尔可夫过程

在进入 MDP 之前，让我们了解马尔可夫链和马尔可夫过程，它们构成了 MDP 的基础。

马尔可夫性质指出，未来仅取决于现在而不是过去。 马尔可夫链是一个概率模型，仅依靠当前状态来预测下一个状态，而不是先前的状态，也就是说，未来有条件地独立于过去。 马尔可夫链严格遵循马尔可夫属性。

例如，如果我们知道当前状态是多云，则可以预测下一个状态可能是雨天。 我们得出的结论是，只有考虑当前状态（多云）而不考虑过去的状态（可能是晴天，大风等），下一个状态才会下雨。 但是，Markov 属性并不适用于所有进程。 例如，掷骰子（下一个状态）与前一个数字无关，无论骰子上显示的是什么（当前状态）。

从一种状态移动到另一种状态称为**过渡**，其概率称为**过渡概率**。 我们可以用表格的形式来表示转移概率，如下所示，它被称为 **Markov table** 。 在给定当前状态的情况下，它显示了移至下一个状态的概率为：

| **当前状态** | **下一个状态** | **转移概率** |
| 多云的 | 多雨的 | 0.6 |
| 多雨的 | 多雨的 | 0.2 |
| 阳光明媚 | 多云的 | 0.1 |
| 多雨的 | 阳光明媚 | 0.1 |

我们还可以以状态图的形式表示马尔可夫链，该状态图显示过渡概率：

![](img/00018.jpeg)

前面的状态图显示了从一种状态转移到另一种状态的可能性。 还是不了解马尔可夫链？ 好吧，让我们谈谈。

我：“你在做什么？”

您：“我正在阅读有关马尔可夫链的信息。”

我：“看完书后你打算做什么？”

你：“我要睡觉了。”

我：“您确定要睡觉吗？”

您：“可能。如果我不困，我会看电视的。”

我：“很酷；这也是一条马尔可夫链。”

你：“嗯？”

我们可以将对话公式化为马尔可夫链，并绘制如下状态图：

![](img/00019.jpeg)

马尔可夫链位于核心概念中，即未来仅取决于现在而不是过去。 如果遵循 Markov 属性，则随机过程称为 Markov 过程。

# 马尔可夫决策过程

MDP 是马尔可夫链的延伸。 它提供了用于建模决策情况的数学框架。 几乎所有的强化学习问题都可以建模为 MDP。

MDP 由五个重要元素表示：

*   代理实际上可以处于的一组状态![](img/00020.jpeg)。
*   代理可以执行的一组动作![](img/00021.jpeg)，用于从一种状态转移到另一种状态。
*   转移概率（![](img/00022.jpeg)），是通过执行某些操作![](img/00025.jpeg)从一种状态![](img/00023.jpeg)转移到另一种![](img/00024.jpeg)状态的概率。
*   奖励概率（![](img/00026.jpeg)），是代理商通过执行某些动作![](img/00029.jpeg)从一种状态![](img/00027.jpeg)转移到另一种状态![](img/00028.jpeg)所获得的奖励的概率。
*   折扣因子（![](img/00030.jpeg)），用于控制立即和将来奖励的重要性。 我们将在接下来的部分中详细讨论。

# 奖励与退货

如我们所知，在 RL 环境中，代理通过执行操作与环境交互，并从一种状态转移到另一种状态。 根据其执行的动作，它会获得奖励。 奖励不过是一个数字值，例如，一个好动作为+1，而一个坏动作为-1。 我们如何确定一个动作是好是坏？ 在迷宫游戏中，好动作是指特工进行移动以使其不会撞到迷宫壁的地方，而不好的动作是指特工进行移动并撞到迷宫壁的地方。

代理试图最大化从环境而不是即时奖励中获得的奖励（累积奖励）总量。 代理商从环境中获得的总奖励金额称为回报。 因此，我们可以将代理商收到的奖励（回报）总额计算如下：

![](img/00031.jpeg)

![](img/00032.jpeg)是代理在执行步骤
![](img/00034.jpeg)从一种状态转换到另一种状态时在时间步骤![](img/00033.jpeg)时收到的奖励。 ![](img/00035.jpeg)是代理在执行从一个状态到另一状态的动作时，在
步骤![](img/00036.jpeg)时收到的奖励。 类似地，![](img/00037.jpeg)是代理在执行从一个状态到另一状态的动作时，在最后时间步骤![](img/00038.jpeg)所收到的奖励。

# 间歇性和连续性任务

情景任务是具有终端状态（结束）的任务。 在 RL 中，情节被视为从初始状态到最终状态的代理人与环境的相互作用。

例如，在赛车视频游戏中，您启动游戏（初始状态）并玩游戏直到游戏结束（最终状态）。 这称为情节。 游戏结束后，您可以通过重新启动游戏来开始下一个情节，并且无论您在上一个游戏中所处的位置如何，都将从初始状态开始。 因此，每个情节彼此独立。

在连续任务中，没有终端状态。 连续的任务永远不会结束。 例如，个人协助机器人没有终端状态。

# 折现系数

我们已经看到，代理商的目标是使回报最大化。 对于一项临时任务，我们可以将返回定义为 *R <sub class="calibre24">t</sub> = r <sub class="calibre24">t + 1</sub> + r <sub class="calibre24">t + 2</sub> +...。 + r <sub class="calibre24">T</sub>* ，其中 *T* 是情节的最终状态，我们尝试最大化回报 *R <sub class="calibre24">t</sub>* 。

由于连续任务没有任何最终状态，因此我们可以将连续任务的收益定义为 *R <sub class="calibre24">t</sub> = r <sub class="calibre24">t + 1</sub> + r <sub class="calibre24">t + 2</sub> + ....* ，总和为无穷大。 但是，如果永不止息，我们如何才能最大化回报呢？

这就是为什么我们引入折扣因子的概念。 我们可以使用折扣因子![](img/00039.jpeg)重新定义收益，如下所示：

![](img/00040.jpeg) ---（1）

![](img/00041.jpeg) ---（2）

折扣系数决定了我们对未来奖励和即时奖励的重视程度。 折扣因子的值在 *0* 至 *1* 之内。 折扣因子 *0* 意味着即时奖励更为重要，而折扣因子 *1* 意味着未来奖励比即时奖励更为重要。

折扣系数 *0* 永远不会只考虑立即获得的奖励。 同样， *1* 的折扣因子将永远学习，以寻找未来的奖励，这可能导致无限。 因此，折现因子的最佳值在 0.2 到 0.8 之间。

根据使用情况，我们重视即时奖励和将来的奖励。 在某些情况下，未来的奖励比立即的奖励更可取，反之亦然。 在国际象棋游戏中，目标是击败对手的国王。 如果我们重视即时奖励，而即时奖励是通过典当击败任何对手玩家等行动获得的，那么坐席将学会执行此子目标，而不是学习达到实际目标。 因此，在这种情况下，我们重视未来的奖励，而在某些情况下，我们更喜欢即时奖励，而不是未来的奖励。 （说，如果我今天或 13 个月后给您巧克力，您会喜欢巧克力吗？）

# 政策功能

我们已经在[第 1 章](01.html#K0RQ0-3c5bb317ad314d43ac43a332c0db6f00)和*强化学习简介*中了解了策略功能，该功能将状态映射到操作。 用π表示。

策略功能可以表示为![](img/00042.jpeg)，指示从状态到动作的映射。 因此，基本上，策略功能会说明在每种状态下要执行的操作。 我们的最终目标在于找到最佳策略，该策略指定在每个状态下执行的正确操作，从而最大化回报。

# 状态值功能

状态值函数也简称为值函数。 它通过策略*π*指定代理处于特定状态的状态如何。 值函数通常由 *V（s）*表示。 它表示遵循策略的状态的值。

我们可以定义一个状态值函数，如下所示：

![](img/00043.jpeg)

这根据策略*π*指定从状态 *s* 开始的预期收益。 我们可以用（2）的值函数替换 *R <sub class="calibre24">t</sub>* 的值，如下所示：

![](img/00044.jpeg)

请注意，状态值函数取决于策略，并且取决于我们选择的策略而有所不同。

我们可以在表中查看值函数。 假设我们有两个状态，并且这两个状态都遵循策略π。 根据这两个状态的值，我们可以判断出执行策略后，我们的代理处于该状态有多好。 值越大，状态越好：

| **状态** | **值** |
| 状态 1 | 0.3 |
| 状态 2 | 0.9 |

根据上表，我们可以知道处于状态 2 很好，因为它具有很高的价值。 在接下来的部分中，我们将看到如何直观地估计这些值。

# 状态作用值功能（Q 功能）

状态作用值函数也称为 *Q* 函数。 它指定代理在具有策略*π*的状态下执行特定操作的效果如何。 *Q* 函数由 *Q（s）*表示。 它表示在遵循策略*π*的状态下执行操作的值。

我们可以定义 *Q* 函数，如下所示：

![](img/00045.jpeg)

这根据策略*π*指定从状态 *s* 开始的预期回报，其动作为 *a* 。 我们可以从（2）的 *Q* 函数中替换 *R <sub class="calibre24">t</sub>* 的值，如下所示：

![](img/00046.jpeg)

值函数和 *Q* 函数之间的区别在于，值函数指定状态的优劣，而 *Q* 函数指定状态的行为的优劣。

与状态值函数一样， *Q* 函数可以在表中查看。 也称为 *Q* 表。 让我们说我们有两个状态和两个动作。 我们的 *Q* 表如下所示：

| **状态** | **动作** | **值** |
| 状态 1 | 动作 1 | 0.03 |
| 状态 1 | 动作 2 | 0.02 |
| 状态 2 | 动作 1 | 0.5 |
| 状态 2 | 动作 2 | 0.9 |

因此， *Q* 表显示了所有可能的状态动作对的值。 因此，通过查看此表，我们可以得出结论，在状态 1 中执行动作 1 和在状态 2 中执行动作 2 是更好的选择，因为它具有很高的价值。

每当我们说值函数 *V（S）*或 *Q* 函数 *Q（S，a），*时，它实际上表示值表，而 *Q* 表，如前所示。

# Bellman 方程和最优性

以美国数学家理查德·贝尔曼（Richard Bellman）命名的贝尔曼方程式可帮助我们求解 MDP。 它在 RL 中无处不在。 当我们说解决 MDP 时，实际上意味着找到最佳的策略和价值功能。 根据不同的策略，可以有许多不同的价值函数。 与所有其他值函数相比，最优值函数![](img/00047.jpeg)是产生最大值的函数：

![](img/00048.jpeg)

类似地，最优策略是导致最优值函数的策略。

由于最优值函数![](img/00049.jpeg)是比所有其他值函数（即最大收益）更高的值的函数，因此它将是 *Q* 函数的最大值。 因此，可以通过将 *Q* 函数的最大值取如下来轻松地计算最佳值函数：

![](img/00050.jpeg)-（3）

值函数的 Bellman 方程可以表示为（在下一主题中，我们将看到如何推导该方程）：

![](img/00051.jpeg)

它指示状态值及其后继状态与所有可能性的平均值之间的递归关系。

类似地，用于 *Q* 函数的 Bellman 方程可以表示为：

![](img/00052.jpeg) ---（4）

将公式（4）代入（3），我们得到：

![](img/00053.jpeg)

前面的方程式称为 Bellman 最优方程式。 在接下来的部分中，我们将看到如何通过求解该方程式找到最佳策略。

# 推导值和 Q 函数的 Bellman 方程

现在，让我们看看如何导出值和 *Q* 函数的 Bellman 方程。

如果您对数学不感兴趣，可以跳过本节。 但是，数学将非常有趣。

首先，我们将![](img/00054.jpeg)定义为在执行动作*和*时从状态![](img/00055.jpeg)转换为![](img/00056.jpeg)的转移概率：

![](img/00057.jpeg)

我们将![](img/00058.jpeg)定义为在执行动作*和*时从状态![](img/00059.jpeg)移至![](img/00060.jpeg)所获得的奖励概率：

![](img/00061.jpeg)

![](img/00062.jpeg) from（2）---（5）

我们知道值函数可以表示为：

![](img/00063.jpeg)

![](img/00064.jpeg)来自（1）

我们可以通过获取第一笔报酬来重写价值函数：

![](img/00065.jpeg) ---（6）

如果我们处于状态 *s* ，并通过策略*π*执行动作*和*，则值函数中的期望值指定了期望收益。

因此，我们可以通过总结所有可能的动作和奖励来明确地重写我们的期望，如下所示：

![](img/00066.jpeg)

在 RHS 中，我们将等式（5）中的![](img/00067.jpeg)替换为：

![](img/00068.jpeg)

同样，在 LHS 中，我们将从等式（2）中替换 *r <sub class="calibre24">t + 1</sub>* 的值，如下所示：

![](img/00069.jpeg)

因此，我们的最终期望方程变为：

![](img/00070.jpeg) ---（7）

现在，我们将期望值（7）替换为值函数（6），如下所示：

![](img/00071.jpeg)

代替![](img/00072.jpeg)，我们可以用等式（6）代替![](img/00073.jpeg)，我们的最终值函数如下所示：

![](img/00074.jpeg)

以非常相似的方式，我们可以为 *Q* 函数导出一个 Bellman 方程； 最终方程如下：

![](img/00075.jpeg)

现在，对于值函数和 *Q* 函数都有一个 Bellman 方程，我们将看到如何找到最佳策略。

# 求解 Bellman 方程

我们可以通过求解 Bellman 最优性方程来找到最优策略。 为了解决 Bellman 最优性方程，我们使用一种称为动态规划的特殊技术。

# 动态编程

**动态编程**（ **DP** ）是一种解决复杂问题的技术。 在 DP 中，不是一次解决一个复杂的问题，而是将问题分解为简单的子问题，然后针对每个子问题，我们计算并存储解决方案。 如果出现相同的子问题，我们将不会重新计算，而是使用已经计算的解决方案。 因此，DP 有助于极大地减少计算时间。 它的应用广泛，包括计算机科学，数学，生物信息学等。

我们使用两种强大的算法来求解 Bellman 方程：

*   价值迭代
*   策略迭代

# 价值迭代

在值迭代中，我们从随机值函数开始。 显然，随机值函数可能不是最佳函数，因此我们以迭代方式寻找新的改进值函数，直到找到最佳值函数为止。 一旦找到最优值函数，就可以轻松地从中得出最优策略：

![](img/00076.gif)

值迭代涉及的步骤如下：

1.  首先，我们初始化随机值函数，即每个状态的随机值。
2.  然后，我们为 *Q（s，a）*的所有状态动作对计算 *Q* 函数。
3.  然后，我们使用 *Q（s，a）*中的最大值更新值函数。
4.  我们重复这些步骤，直到 value 函数的变化很小。

让我们通过手动逐步执行值迭代来直观地理解它。

考虑此处显示的网格。 让我们说我们处于状态 **A** ，我们的目标是在不访问状态 **B** 的情况下达到状态 **C** ，我们有两个动作，0-左/右 和 1-上/下：

![](img/00077.gif)

您能想到这里的最佳政策吗？ 此处的最佳策略是告诉我们在 **A** 状态下执行操作 1 的策略，这样我们就可以访问 **C** 而无需访问 **B** 。 我们如何找到这个最佳政策？ 现在让我们看看：

初始化随机值函数，即所有状态的随机值。 让我们将 **0** 分配给所有状态：

![](img/00078.gif)

让我们计算所有状态动作对的 *Q* 值。

Q 值告诉我们每个状态下一个动作的值。 首先，让我们计算状态 *A* 的 *Q* 值。 调用 *Q* 函数的方程式。 为了进行计算，我们需要过渡和奖励概率。 让我们考虑状态 **A** 的转移和奖励概率，如下所示：

![](img/00079.gif)

状态 **A** 的 Q 函数可以计算如下：

*Q（s，a）=转移概率*（奖励概率+伽玛* next_state 的值）*

在此，*伽马*是折扣因子； 我们将其视为 *1* 。

*状态 *A* 和操作 *0* *的 Q* 值：*

![](img/00080.jpeg)

*Q（A，0）=（0.1 *（0 + 0））+（0.4 *（-1.0 + 0））+（0.3 *（1.0 + 0））*

Q（A，0）= -0.1

现在我们将计算状态 *A* 和操作 *1：*的 *Q* 值

![](img/00081.jpeg)

*Q（A，1）=（0.3 *（0 + 0））+（0.1 *（-2.0 + 0））+（0.5 *（1.0 + 0））*

*Q（A，1）= 0.3*

现在，我们将在 *Q* 表中对此进行更新，如下所示：

![](img/00082.gif)

从 *Q（s，a）*更新值函数为最大值。

如果您查看前面的 *Q* 函数，则 *Q（A，1）*的值大于 *Q（A，0）*的值，因此我们将更新该值 状态 *A* 的形式为 *Q（A，1）*：

![](img/00083.gif)

同样，我们为所有状态动作对计算 *Q* 值，并通过获取具有最高状态动作值的 *Q* 值来更新每个状态的值函数。 我们的更新值函数如下所示。 这是第一次迭代的结果：

![](img/00084.gif)

我们重复此步骤几次迭代。 也就是说，我们将步骤 *2* 重复到步骤 *3* （在每次迭代中，在计算 *Q* 值时，我们使用更新后的值函数，而不是相同的随机初始化函数） 值函数）。

这是第二次迭代的结果：

![](img/00085.gif)

这是第三次迭代的结果：

![](img/00086.gif)

但是我们什么时候停止呢？ 当每次迭代之间的值变化较小时，我们将停止； 如果查看第二和第三次迭代，则值函数的变化不大。 在这种情况下，我们停止迭代并将其视为最佳值函数。

好了，既然我们已经找到了最优价值函数，那么我们如何得出最优政策呢？

这很简单。 我们用最终的最优值函数计算 *Q* 函数。 假设我们计算出的 *Q* 函数如下所示：

![](img/00087.gif)

从此 *Q* 函数中，我们选择每种状态下具有最大值的动作。 在状态 **A** 下，我们为操作 1 设置了最大值，这是我们的最佳策略。 因此，如果我们在状态 **A** 中执行动作 1，则无​​需访问 **B** 就可以达到 **C** 。

# 策略迭代

与值迭代不同，在策略迭代中，我们从随机策略开始，然后找到该策略的值函数。 如果价值函数不是最优的，那么我们会找到新的改进策略。 我们重复此过程，直到找到最佳策略。

策略迭代有两个步骤：

1.  **策略评估**：评估随机估算策略的价值函数。
2.  **策略改进**：在评估价值函数时，如果它不是最优的，我们会发现新的改进策略：

![](img/00088.gif)

策略迭代涉及的步骤如下：

1.  首先，我们初始化一些随机策略
2.  然后我们找到该随机策略的值函数，并进行评估以检查其是否最优，这称为策略评估
3.  如果不是最佳选择，我们会找到新的改进政策，称为政策改进
4.  我们重复这些步骤，直到找到最佳策略

让我们通过逐步手动执行策略迭代来直观地理解。

考虑我们在*值迭代*部分中看到的相同网格示例。 我们的目标是找到最佳策略：

1.  初始化随机策略功能。

让我们通过为每个状态指定随机动作来初始化随机策略函数：

说 *A-> 0*

*B-> 1*

*C-> 0*

2.  查找随机初始化策略的值函数。

现在，我们必须使用随机初始化的策略来查找值函数。 我们说一下计算后的值函数如下：

![](img/00089.gif)

现在，根据随机初始化的策略有了新的价值函数，让我们使用新的价值函数计算新的政策。 我们如何做到这一点？ 这与我们在*值迭代*中所做的非常相似。 我们为新值函数计算 *Q* 值，然后针对具有最大值的每个状态采取措施作为新策略。

我们说新政策的结果是：

*A-> 0*

*B-> 1*

*C-> 1*

我们检查旧策略，即随机初始化的策略和新策略。 如果它们相同，则我们已经达到收敛，即找到了最佳策略。 如果没有，我们将旧策略（随机策略）更新为新策略，并从步骤 *2* 开始重复。

听起来令人困惑？ 看一下伪代码：

```py
policy_iteration():
    Initialize random policy
    for i in no_of_iterations: 
        Q_value = value_function(random_policy)
        new_policy = Maximum state action pair from Q value
        if random_policy == new policy:
            break
        random_policy = new_policy 
    return policy
```

# 解决冻湖问题

如果您到目前为止还不了解我们所学的知识，请放心，我们将研究所有概念以及冻湖问题。

想象一下，有一个从家到办公室的冰冻湖泊。 您必须在结冰的湖面上行走才能到达办公室。 但是糟糕！ 冰冻的湖面上有洞，因此您在冰冻的湖面上行走时必须小心，以免被困在洞中：

![](img/00090.gif)

看上图：

*   **S** 是起始位置（原点）
*   **F** 是您可以漫步的冰冻湖
*   **H** 是孔，您必须非常小心
*   **G** 是目标（办公室）

好的，现在让我们代替您使用我们的代理来找到到达办公室的正确方法。 该代理的目标是找到从 **S** 到 **G** 的最佳路径，而不会陷入 **H** 的陷阱。 代理商如何做到这一点？ 如果代理正确地在冰冻的湖面上行走，我们给+1 分作为奖励，如果代理正确落入洞中，则给 0 分，以便代理确定正确的行动。 代理现在将尝试找到最佳策略。 最优政策意味着采取正确的道路，这将最大化代理商的报酬。 如果代理人正在使报酬最大化，则显然代理人正在学习跳过漏洞并到达目的地。

我们可以将问题建模为我们先前研究的 MDP。 MDP 包含以下内容：

*   **状态**：状态集。 在这里，我们有 16 个州（网格中的每个小方框）。
*   **动作**：所有可能动作的集合（左，右，上，下；这是我们的代理商在冰冻湖面环境中可以采取的所有四种可能动作）。
*   **转移概率**：通过执行动作*和*从一种状态（ **F** ）转换为另一种状态（ **H** ）的概率。
*   **奖励概率**：这是从一种状态（ **F** ）迁移到另一种状态（ **H** ）时获得奖励的概率。 执行*和*动作。

现在我们的目标是解决 MDP。 解决 MDP 意味着寻找最佳策略。 现在，我们介​​绍三个特殊功能：

*   **策略功能**：指定在每种状态下要执行的操作
*   **值函数**：指定状态的良好程度
*   **Q 函数**：指定动作在特定状态下的状态

当我们说有多好时，这到底意味着什么？ 这意味着最大化奖励是多么的好。

然后，我们使用称为 Bellman 最优性方程的特殊方程式表示值函数和 *Q* 函数。 如果我们解决这个方程，我们可以找到最佳策略。 在这里，求解方程式意味着找到正确的价值函数和策略。 如果我们找到正确的价值功能和政策，那将是我们获得最大回报的最佳途径。

我们将使用一种称为动态规划的特殊技术来求解 Bellman 最优性方程。 要应用 DP，必须预先知道模型动力学，这基本上意味着必须预先知道模型环境的转换概率和奖励概率。 由于我们知道模型动力学，因此可以在此处使用 DP。 我们使用两种特殊的 DP 算法来找到最佳策略：

*   价值迭代
*   策略迭代

# 价值迭代

简单来说，在值迭代中，我们首先将一些随机值初始化为 value 函数。 我们初始化的随机值很有可能不会达到最佳状态。 因此，我们遍历每个状态并找到新的值函数； 我们停止迭代，直到找到最佳值函数。 一旦找到最优值函数，就可以轻松地从中提取最优策略。

现在我们将看到如何使用值迭代来解决冻湖问题。

首先，我们导入必要的库：

```py
import gym
import numpy as np
```

然后，我们使用 OpenAI 的 Gym 创建冰冻的湖泊环境：

```py
env = gym.make('FrozenLake-v0')
```

我们将首先探索环境。

由于我们有一个 4 * 4 的网格，因此环境中的状态数为 16：

```py
print(env.observation_space.n)
```

环境中的操作数为四个，分别为上，下，左和右：

```py
print(env.observation_space.n)
```

现在我们定义一个`value_iteration()`函数，该函数返回最佳值函数（值表）。 我们将首先逐步了解该功能，然后再查看整个功能。

首先，我们为所有状态和迭代次数初始化随机值表`0`：

```py
value_table = np.zeros(env.observation_space.n)
no_of_iterations = 100000
```

然后，在每次迭代开始时，我们将`value_table`复制到`updated_value_table`：

```py
 for i in range(no_of_iterations):
     updated_value_table = np.copy(value_table) 
```

现在，我们计算 Q 表，并选择具有最高值的最大状态动作对作为值表。

我们将使用之前解决的示例来理解代码。 我们在上一个示例中计算了状态 *A* 和操作 *1* 的 *Q* 值：

*Q（A，1）=（0.3 *（0 + 0））+（0.1 *（-1.0 + 0））+（0.5 +（1.0 + 0））*

*Q（A，1）= 0.5*

我们没有为每个状态创建 *Q* 表，而是创建了一个名为`Q_value`的列表，然后为该状态中的每个动作创建了一个名为`next_states_rewards`的列表，该列表存储了`Q_value` 下一个过渡状态。 然后，我们对`next_state_rewards`求和并将其附加到我们的`Q_value`中。

请看前面的示例，其中状态为 *A* ，操作为 *1* 。 *（0.3 *（0 + 0））*是过渡状态 *A* 和*（0.1 *（-1.0 + 0））*的下一个状态奖励 过渡状态 *B* 的下一状态奖励。 *（0.5 +（1.0 + 0））*是过渡状态 *C* 的下一个状态奖励。 我们将所有这些加总为`next_state_reward`，并将其附加到`Q_value`中，该值为 0.5。

当我们为状态的所有动作计算`next_state_rewards`并将其附加到 *Q* 值时，我们选取​​最大的 *Q* 值并将其更新为我们的状态值：

```py
for state in range(env.observation_space.n):
    Q_value = []
    for action in range(env.action_space.n):
        next_states_rewards = []
        for next_sr in env.P[state][action]: 
            trans_prob, next_state, reward_prob, _ = next_sr 
            next_states_rewards.append((trans_prob * (reward_prob + gamma *                    updated_value_table[next_state]))) 

          Q_value.append(np.sum(next_states_rewards))

```

```py
          #Pick up the maximum Q value and update it as value of a state
          value_table[state] = max(Q_value) 
```

然后，我们将检查是否已经达到收敛，即，我们的价值表和更新后的价值表之间的差异非常小。 我们怎么知道它很小？ 我们定义了一个名为`threshold`的变量，然后我们看一下差异是否小于我们的`threshold`； 如果小于，则中断循环，并将值函数返回为最佳值函数：

```py
threshold = 1e-20
if (np.sum(np.fabs(updated_value_table - value_table)) <= threshold):
    print ('Value-iteration converged at iteration# %d.' %(i+1))
    break
```

查看`value_iteration()`的完整功能可以更好地理解：

```py
def value_iteration(env, gamma = 1.0):
    value_table = np.zeros(env.observation_space.n)
    no_of_iterations = 100000
    threshold = 1e-20

    for i in range(no_of_iterations):
        updated_value_table = np.copy(value_table) 

        for state in range(env.observation_space.n):
            Q_value = []

            for action in range(env.action_space.n):
                next_states_rewards = []

                for next_sr in env.P[state][action]: 
                    trans_prob, next_state, reward_prob, _ = next_sr 
                    next_states_rewards.append((trans_prob * (reward_prob + gamma * updated_value_table[next_state])))

                Q_value.append(np.sum(next_states_rewards))
            value_table[state] = max(Q_value) 
        if (np.sum(np.fabs(updated_value_table - value_table)) <= threshold):
             print ('Value-iteration converged at iteration# %d.' %(i+1))
             break

    return value_table, Q_value
```

因此，我们可以使用`value_iteration`导出`optimal_value_function`：

```py
optimal_value_function = value_iteration(env=env,gamma=1.0)
```

找到`optimal_value_function`后，如何从`optimal_value_function`中提取最佳策略？ 我们使用最佳值操作来计算 *Q* 值，并选择每个状态中具有最高 *Q* 值的操作作为最佳策略。 我们通过称为`extract_policy()`的函数来完成此操作； 我们现在将逐步介绍这一点。

首先，我们定义随机策略； 对于所有状态，我们将其定义为`0`：

```py
policy = np.zeros(env.observation_space.n)
```

然后，对于每个状态，我们都构建一个`Q_table`，并且针对该状态中的每个动作，我们计算 *Q* 值并将其添加到我们的`Q_table`中：

```py
for state in range(env.observation_space.n):
        Q_table = np.zeros(env.action_space.n)
        for action in range(env.action_space.n):
            for next_sr in env.P[state][action]: 
                trans_prob, next_state, reward_prob, _ = next_sr 
                Q_table[action] += (trans_prob * (reward_prob + gamma * value_table[next_state]))
```

然后，我们为`state`选择策略，将其作为具有 *Q* 最高值的操作：

```py
policy[state] = np.argmax(Q_table)
```

看一下完整的功能：

```py
def extract_policy(value_table, gamma = 1.0):

    policy = np.zeros(env.observation_space.n) 
    for state in range(env.observation_space.n):
        Q_table = np.zeros(env.action_space.n)
        for action in range(env.action_space.n):
            for next_sr in env.P[state][action]: 
                trans_prob, next_state, reward_prob, _ = next_sr 
                Q_table[action] += (trans_prob * (reward_prob + gamma * value_table[next_state]))
        policy[state] = np.argmax(Q_table)

    return policy
```

因此，我们可以得出`optimal_policy`如下：

```py
optimal_policy = extract_policy(optimal_value_function, gamma=1.0)
```

我们将获得如下输出，即`optimal_policy`，即在每种状态下要执行的操作：

```py
array([0., 3., 3., 3., 0., 0., 0., 0., 3., 1., 0., 0., 0., 2., 1., 0.])
```

完整的程序如下：

```py
import gym
import numpy as np
env = gym.make('FrozenLake-v0')

def value_iteration(env, gamma = 1.0):
    value_table = np.zeros(env.observation_space.n)
    no_of_iterations = 100000
    threshold = 1e-20
    for i in range(no_of_iterations):
        updated_value_table = np.copy(value_table) 

        for state in range(env.observation_space.n):
            Q_value = []
            for action in range(env.action_space.n):
                next_states_rewards = []
                for next_sr in env.P[state][action]: 
                    trans_prob, next_state, reward_prob, _ = next_sr 
                    next_states_rewards.append((trans_prob * (reward_prob + gamma * updated_value_table[next_state]))) 
                Q_value.append(np.sum(next_states_rewards))

            value_table[state] = max(Q_value) 

        if (np.sum(np.fabs(updated_value_table - value_table)) <= threshold):
             print ('Value-iteration converged at iteration# %d.' %(i+1))
             break

    return value_table

def extract_policy(value_table, gamma = 1.0):
    policy = np.zeros(env.observation_space.n) 
    for state in range(env.observation_space.n):
        Q_table = np.zeros(env.action_space.n)
        for action in range(env.action_space.n):
            for next_sr in env.P[state][action]: 
                trans_prob, next_state, reward_prob, _ = next_sr 
                Q_table[action] += (trans_prob * (reward_prob + gamma * value_table[next_state]))
        policy[state] = np.argmax(Q_table)

    return policy

optimal_value_function = value_iteration(env=env,gamma=1.0)
optimal_policy = extract_policy(optimal_value_function, gamma=1.0)

print(optimal_policy)
```

# 策略迭代

在策略迭代中，首先我们初始化一个随机策略。 然后，我们将评估初始化的随机策略：它们是否好？ 但是，我们如何评估政策呢？ 我们将通过计算它们的价值函数来评估我们随机初始化的策略。 如果它们不好，那么我们会找到新的政策。 我们重复此过程，直到找到好的政策。

现在让我们看看如何使用策略迭代来解决冻湖问题。

在查看策略迭代之前，我们将了解在给定策略的情况下如何计算价值函数。

我们用状态数将`value_table`初始化为零：

```py
value_table = np.zeros(env.nS)
```

然后，对于每个状态，我们从策略中获取操作，然后根据`action`和`state`计算值函数，如下所示：

```py
        updated_value_table = np.copy(value_table)
        for state in range(env.nS):
            action = policy[state]
            value_table[state] = sum([trans_prob * (reward_prob + gamma *  updated_value_table[next_state]) 
                        for trans_prob, next_state, reward_prob, _ in env.P[state][action]])
```

当`value_table`和`updated_value_table`之差小于我们的`threshold`时，我们将打破这一点：

```py
threshold = 1e-10
if (np.sum((np.fabs(updated_value_table - value_table))) <= threshold):
    break
```

查看以下完整功能：

```py
def compute_value_function(policy, gamma=1.0):
    value_table = np.zeros(env.nS)
    threshold = 1e-10
    while True:
        updated_value_table = np.copy(value_table)
        for state in range(env.nS):
            action = policy[state]
            value_table[state] = sum([trans_prob * (reward_prob + gamma * updated_value_table[next_state]) 
                        for trans_prob, next_state, reward_prob, _ in env.P[state][action]])
        if (np.sum((np.fabs(updated_value_table - value_table))) <= threshold):
            break
    return value_table
```

现在，我们将逐步了解如何执行策略迭代。

首先，我们将`random_policy`初始化为零个 NumPy 数组，其形状为状态数：

```py
 random_policy = np.zeros(env.observation_space.n)
```

然后，对于每次迭代，我们根据随机策略计算`new_value_function`：

```py
new_value_function = compute_value_function(random_policy, gamma)
```

我们将使用计算出的`new_value_function`提取策略。 `extract_policy`函数与我们在值迭代中使用的函数相同：

```py
 new_policy = extract_policy(new_value_function, gamma)
```

然后，我们检查是否已经达到收敛，即是否通过比较`random_policy`和新策略找到了最佳策略。 如果它们相同，我们将中断迭代。 否则，我们用`new_policy`更新`random_policy`：

```py
if (np.all(random_policy == new_policy)):
    print ('Policy-Iteration converged at step %d.' %(i+1))
    break
random_policy = new_policy
```

查看完整的`policy_iteration`函数：

```py
def policy_iteration(env,gamma = 1.0):
    random_policy = np.zeros(env.observation_space.n) 
    no_of_iterations = 200000
    gamma = 1.0
    for i in range(no_of_iterations):
        new_value_function = compute_value_function(random_policy, gamma)
        new_policy = extract_policy(new_value_function, gamma)
        if (np.all(random_policy == new_policy)):
            print ('Policy-Iteration converged at step %d.' %(i+1))
            break
        random_policy = new_policy
    return new_policy
```

因此，我们可以使用`policy_iteration`获得`optimal_policy`：

```py
optimal_policy = policy_iteration(env, gamma = 1.0)
```

我们将获得一些输出，即`optimal_policy`，这是在每种状态下要执行的操作：

```py
array([0., 3., 3., 3., 0., 0., 0., 0., 3., 1., 0., 0., 0., 2., 1., 0.])
```

完整的程序如下：

```py
import gym
import numpy as np

env = gym.make('FrozenLake-v0')

def compute_value_function(policy, gamma=1.0):
    value_table = np.zeros(env.nS)
    threshold = 1e-10
    while True:
        updated_value_table = np.copy(value_table)
        for state in range(env.nS):
            action = policy[state]
            value_table[state] = sum([trans_prob * (reward_prob + gamma * updated_value_table[next_state]) 
                        for trans_prob, next_state, reward_prob, _ in env.P[state][action]])
        if (np.sum((np.fabs(updated_value_table - value_table))) <= threshold):
            break
    return value_table

def extract_policy(value_table, gamma = 1.0):
    policy = np.zeros(env.observation_space.n) 
    for state in range(env.observation_space.n):
        Q_table = np.zeros(env.action_space.n)
        for action in range(env.action_space.n):
            for next_sr in env.P[state][action]: 
                trans_prob, next_state, reward_prob, _ = next_sr 
                Q_table[action] += (trans_prob * (reward_prob + gamma * value_table[next_state]))
        policy[state] = np.argmax(Q_table)

    return policy

def policy_iteration(env,gamma = 1.0):
    random_policy = np.zeros(env.observation_space.n) 
    no_of_iterations = 200000
    gamma = 1.0
    for i in range(no_of_iterations):
        new_value_function = compute_value_function(random_policy, gamma)
        new_policy = extract_policy(new_value_function, gamma)
        if (np.all(random_policy == new_policy)):
            print ('Policy-Iteration converged at step %d.' %(i+1))
            break
        random_policy = new_policy
    return new_policy

print (policy_iteration(env))
```

因此，我们可以得出最佳策略，该策略使用值和策略迭代来解决冻结湖问题，从而指定在每种状态下要执行的操作。

# 概要

在本章中，我们了解了什么是马尔可夫链和马尔可夫过程，以及如何使用 MDP 表示 RL 问题。 我们还研究了 Bellman 方程，并解决了 Bellman 方程，从而使用 DP 推导了最优策略。 在下一章[，第 4 章](04.html#2VBO80-3c5bb317ad314d43ac43a332c0db6f00)，*使用蒙特卡洛方法*进行游戏中，我们将研究蒙特卡洛树搜索以及如何使用它进行智能游戏的构建。

# 问题

问题列表如下：

1.  马尔可夫财产是什么？
2.  为什么我们需要马尔可夫决策过程？
3.  我们何时更喜欢即时奖励？
4.  折扣因子有什么用？
5.  为什么要使用 Bellman 函数？
6.  您将如何导出 Q 函数的 Bellman 方程？
7.  值函数和 Q 函数有何关系？
8.  价值迭代和策略迭代有什么区别？

# 进一步阅读

[**MDP 哈佛讲座材料**](http://am121.seas.harvard.edu/site/wp-content/uploads/2011/03/MarkovDecisionProcesses-HillierLieberman.pdf)