蒙特卡罗方法¶

约 2413 个字预计阅读时间 8 分钟

Reference¶

http://incompleteideas.net/book/RLbook2018.pdf
https://people.cs.umass.edu/~bsilva/courses/CMPSCI_687/Fall2022/Lecture_Notes_v1.0_687_F22.pdf

1 蒙特卡罗策略评估¶

考虑使用蒙特卡罗方法估计策略 $\pi$ 的状态值函数. 具体而言，考虑估计状态 $s \in S$ 的值. 若生成从 $S_0 = s$ 开始的轨迹 $H = (S_0, A_0, R_0, S_1, A_1, R_1, \ldots)$ ，如何构造 $v^{\pi}(s)$ 的无偏估计量？

episode 指的是智能体与环境进行交互的一个完整过程 . 从初始状态开始，智能体不断根据当前策略选择动作与环境互动，获取奖励，状态也随之转移，直至满足某个终止条件，这个过程就构成了一个 episode .

通过计算从策略 $\pi$ 采样轨迹中 $s$ 首次出现时的折扣回报，可构造 $v^{\pi}(s)$ 的无偏估计量. 若从 $s$ 的最后一次访问计算回报，未必能得到无偏估计. 例如，考虑一个单状态 $s_0$ 的MDP，以0.5概率自转移，0.5概率转移到 $s_{\infty}$ ，$\gamma=1$，自转移奖励+1，转移到 $s_{\infty}$ 奖励0. 此例中 $s_0$ 的值为1，首次访问 $s_0$ 的期望回报为1，但最后一次访问的期望回报为0.

若仅考虑轨迹中 $s$ 第二次访问后的回报，根据马尔可夫性质，进入 $s$ 之前的历史不改变期望回报，因此只要丢弃 $s$ 未出现两次的episode，这仍是 $v^{\pi}(s)$ 的无偏估计量.

然而，若对 $s$ 每次出现的回报求平均，未必是无偏估计量. 仍用上述例子，每次访问估计的期望值计算如下（ $0.5^k$ 是 $S_{k+1}$ 为 $s_{\infty}$ 首次出现的概率，括号内是所有s访问的平均回报，即 $\frac{1}{k} \sum_{i=0}^{k-1} i = \frac{(k-1)}{2}$ ）：

\[ \begin{aligned} &0.5(0)+0.5^{2}\left(\frac{1}{2}\right)+0.5^{3}\left(\frac{2}{2}\right)+0.5^{4}\left(\frac{3}{2}\right)+0.5^{5}(2)+\ldots+0.5^{k}\left(\frac{k-1}{2}\right)\ldots \\ =&\sum_{k=1}^{\infty} 0.5^{k}\left(\frac{k-1}{2}\right) \\ =&0.5 \end{aligned} \]

由于 $v^{\pi}(s) = 1$ ，这意味着对每次访问的值求平均会产生有偏估计（期望值为0.5）.

综上，若使用状态 $s$ 第 $k$ 次出现的时间步 $s_t$ （丢弃 $s$ 在episode中出现次数不足 $k$ 次的情况），则折扣回报的期望是 $v^{\pi}(s_t)$ 的无偏估计量，包括 $k=1$ 的首次访问特例. 若使用倒数第 $k$ 次出现或对多次出现的回报求平均（包括每次出现的情况），则不是无偏估计量.

这暗示了估计 $v^{\pi}$ 的简单算法：生成大量episode数据，对每个状态，平均其在每个episode中首次出现后的折扣回报. 此算法称为首次访问蒙特卡罗，伪代码见算法1.

算法1：首次访问蒙特卡罗
输入：1）待近似状态值函数的策略 $\pi$ ；2）初始状态值函数估计 $v$（如初始化为0）
- 对所有 $s \in S$ ，初始化 $\text{Returns}(s)$ 为空列表.
- 循环：
- 使用 $\pi$ 生成一个episode；
- 对episode中出现的每个状态s：
- t为s在episode中首次出现的时间步；
- $G = \sum_{k=0}^{\infty} \gamma^k R_{t+k}$ ；
- 将G添加到 $\text{Returns}(s)$ ；
- $v(s) = \text{average}(\text{Returns}(s))$ ；

若每个状态被无限次访问，则（对任何有限MDP，有界奖励且 $\gamma<1$）首次访问蒙特卡罗的状态值函数估计 $v$ 几乎必然收敛到 $v^{\pi}$ . 此性质的证明基于辛钦强大数定律：

性质2（辛钦强大数定律）：设 $\{X_i\}_{i=1}^{\infty}$ 为独立同分布随机变量，则 $\left(\frac{1}{n} \sum_{i=1}^{n} X_i\right)_{n=1}^{\infty}$ 几乎必然收敛到 $E[X_1]$ ，即 $\frac{1}{n} \sum_{i=1}^{n} X_i \xrightarrow{a.s.} E[X_1]$ .
证明：见Sen和Singer（1993，定理2.3.13）. $\square$

关于几乎必然收敛的回顾，见维基百科. 另一个有用的大数定律（此处不使用）是柯尔莫哥洛夫强大数定律：

性质3（柯尔莫哥洛夫强大数定律）：设 $\{X_i\}_{i=1}^{\infty}$ 为独立（未必同分布）随机变量，若所有 $X_i$ 有相同均值和有界方差，则 $\left(\frac{1}{n} \sum_{i=1}^{n} X_i\right)_{n=1}^{\infty}$ 几乎必然收敛到 $E[X_1]$ .
证明：见Sen和Singer（1993，定理2.3.10与命题2.3.10）. $\square$

为证明首次访问蒙特卡罗几乎必然收敛到 $v^{\pi}$ ，考虑某状态s的估计序列 $v_k(s)$ ，有 $v_k(s) = \frac{1}{k} \sum_{i=1}^{k} G_i$ ，其中 $G_i$ 是 $\text{Returns}(s)$ 中的第i个回报. 注意 $E[G_i] = v^{\pi}(s)$ 且 $G_i$ 独立同分布（因来自独立episode）. 根据辛钦强大数定律， $v_k(s) \xrightarrow{a.s.} v^{\pi}(s)$ . 此外，由于状态数有限，这种收敛是一致的，不仅是逐点收敛——即每个状态的值几乎必然收敛到正确值，且整个值函数估计收敛到真实状态值函数.

此外， $\text{Var}(v_k(s)) \propto \frac{1}{k}$ ，因为（利用 $G_i$ 独立同分布）：

\[ \begin{aligned} \text{Var}\left(v_k(s)\right) &= \text{Var}\left(\frac{1}{k} \sum_{i=1}^{k} G_i\right) \\ &= \frac{1}{k^2} \text{Var}\left(\sum_{i=1}^{k} G_i\right) \\ &= \frac{1}{k^2} k \text{Var}(G_i) \\ &= \frac{1}{k} \text{Var}(G_i) \end{aligned} \]

首次访问蒙特卡罗的替代方法是每次访问蒙特卡罗，使用episode中每次访问状态s的回报. 伪代码见算法2. 注意每次访问蒙特卡罗的回报估计并非都是 $v^{\pi}(s)$ 的无偏估计量，且这些估计量不独立（同一episode中的两次回报可能相关）. 因此，辛钦强大数定律的论证不适用，也无法直接使用柯尔莫哥洛夫定律（因 $G_i$ 不独立）. 但可证明，若每个状态被无限次访问，则（对任何有限MDP，有界奖励且 $\gamma<1$）每次访问蒙特卡罗的状态值近似也几乎必然收敛到 $v^{\pi}$ .

算法2：每次访问蒙特卡罗
输入：
1）待近似状态值函数的策略 $\pi$ ；2）初始状态值函数估计v（如初始化为0）
- 对所有 $s \in S$ ，初始化 $\text{Returns}(s)$ 为空列表.
- 循环：
- 使用 $\pi$ 生成一个episode；
- 对episode中出现的每个状态$s$及每次出现时间$t$：
- $G = \sum_{k=0}^{\infty} \gamma^k R_{t+k}$ ；
- 将 $G$ 添加到 $\text{Returns}(s)$ ；
- $v(s) = \text{average}(\text{Returns}(s))$ ；

2 基于梯度的蒙特卡罗算法¶

考虑另一种蒙特卡罗估计算法，从值函数估计 $v \in \mathbb{R}^{|S|}$ 开始，在时间t执行更新：

\[ v(S_t) \leftarrow v(S_t) + \alpha(G_t - v(S_t)) \quad \]

我们将看到许多此类形式的更新，一般形式为：

\[ f(x) \leftarrow f(x) + \alpha(g(x) - f(x)) \]

此处 $g(x)$ 是 $f(x)$ 的目标，此更新使 $f(x)$ 更接近 $g(x)$ .

现证明此更新可视为对均方值误差（MSVE）损失函数的梯度下降更新：

\[ \text{MSVE}(v) := E\left[\frac{1}{2}\left(v^{\pi}(S) - v(S)\right)^2\right] \]

其中期望关于状态S的分布（此分布是执行策略 $\pi$ 时的状态观测分布，具体见Sutton和Barto第二版）.

MSVE的梯度下降算法使用更新：

\[ \begin{aligned} v &\leftarrow v - \alpha \frac{\partial \text{MSVE}(v)}{\partial v} \\ &= v - \alpha \frac{\partial}{\partial v} E\left[\frac{1}{2}\left(v^{\pi}(S) - v(S)\right)^2\right] \\ &= v + \alpha E\left[\left(v^{\pi}(S) - v(S)\right) \frac{\partial v(S)}{\partial v}\right] \end{aligned} \]

由于未知 $v^{\pi}$ 和执行 $\pi$ 的状态分布，无法计算此梯度更新. 转而使用随机梯度下降，用梯度的无偏估计量. 通过采样状态$S$并使用蒙特卡罗回报 $G_t$ 代替 $v^{\pi}(S)$ ，得到随机梯度下降更新：

\[ v \leftarrow v + \alpha\left(G_t - v(S_t)\right) \frac{\partial v(S_t)}{\partial v} \]

考虑项 $\frac{\partial v(S)}{\partial v}$ ，这是一个 $|S|$ 维向量，除第S个元素为1外其余为0. 因此，整个向量v的更新可仅对第S个元素进行，其余元素因乘以 $\frac{\partial v(S)}{\partial v}$ 而保持为0，得到式(207)的更新.

由于式(207)是随机梯度下降算法的实例，其收敛性质已被充分研究（Bertsekas和Tsitsiklis, 2000）. 在足够光滑假设下，它将收敛到局部最优解. 此外，因MSVE是v的二次函数（凸函数），局部最优即全局最小，随机梯度下降将收敛到 $v^{\pi}$ （不同光滑性和步长序列假设下有不同收敛形式）.

注：此处内容略超前，下节课会详细讨论. 提前引入是为了让后续技术推导更简洁. 注意此算法可轻松适配连续状态，设 $v_w$ 是由向量 $w \in \mathbb{R}^n$ 参数化的函数（此处 $\pi$ 与之前讨论的n无关，是任意整数），即不同w对应不同函数 $v_w: S \to \mathbb{R}$ . 在强化学习文献中， $v_w$ 称为函数近似器，常见例子是人工神经网络，其中w是网络权重.

根据式(207)作为MSVE随机梯度下降更新的推导，使用函数近似器的等价更新为：

\[ w \leftarrow w + \alpha\left(G_t - v_w(S_t)\right) \frac{\partial v_w(S_t)}{\partial w} \]

同样，作为随机梯度下降算法，在适当假设下几乎必然收敛到局部最优解. 但若 $v_w$ 不是w的线性函数，解可能不是全局最优. 此外，若真实状态值函数无法被所选函数近似器表示，全局最优可能不是 $v^{\pi}$ . 最后注意，式(207)是式(214)的特例，其中 $v_w$ 为每个状态存储一个值.

3 蒙特卡罗控制¶

现在我们准备考虑如何将蒙特卡罗估计用于控制，即逼近最优策略. 总体思路与动态规划章节中相同，也就是遵循广义策略迭代（GPI）的思想. 在广义策略迭代中，人们同时维护一个近似策略和一个近似价值函数. 价值函数会反复调整，以更接近当前策略的价值函数，并且策略会根据当前价值函数反复改进，如右图所示. 这两种变化在一定程度上相互制约，因为每种变化都会为对方创造一个移动的目标，但它们共同作用，使策略和价值函数都趋向于最优.

评估： $Q \approx q_{\pi}$
策略： $\pi \approx greedy(Q)$
改进： $\pi \rightarrow greedy(Q)$

首先，让我们考虑经典策略迭代的蒙特卡罗版本. 在这种方法中，我们从任意策略 $\pi_0$ 开始，交替进行完整的策略评估和策略改进步骤，最终得到最优策略和最优行动价值函数： $\(\pi_{0} \stackrel{E}{\to} q_{\pi_{0}} \stackrel{I}{\to} \pi_{1} \stackrel{E}{\to} q_{\pi_{1}} \stackrel{I}{\to} \pi_{2} \stackrel{E}{\to} \cdots \stackrel{I}{\to} \pi_{*} \stackrel{E}{\to} q_{*},$\) 其中， $\stackrel{E}{\to }$ 表示一次完整的策略评估，$\stackrel{I}{\to}$表示一次完整的策略改进. 策略评估的具体操作与上一节描述的完全相同. 通过经历许多片段，近似的动作价值函数会渐近地逼近真实函数. 目前，我们假设确实观察到了无穷多个片段，并且这些片段是在探索性起始的情况下生成的. 在这些假设下，蒙特卡罗方法将为任意的$\pi_{k}$精确计算每个$q_{\pi_{k}}$ .

策略改进是通过使策略相对于当前价值函数变为贪婪策略来实现的. 在这种情况下，我们有一个动作价值函数，因此构建贪婪策略时不需要模型. 对于任何动作价值函数$q$，相应的贪婪策略是对于每个$s \in S$，确定性地选择具有最大动作价值的动作： $\(\pi(s) \doteq \underset{a}{\arg\max} q(s, a). (5.1)$\)

然后，可以通过将每个$\pi_{k + 1}$构建为相对于$q_{\pi_{k}}$的贪婪策略来完成策略改进. 策略改进定理（4.2节）适用于$\pi_{k}$和$\pi_{k + 1}$，因为对于所有$s \in S$ ： $\(\begin{align*} q_{\pi_{k}}(s, \pi_{k + 1}(s)) &= q_{\pi_{k}}(s, \underset{a}{\arg\max} q_{\pi_{k}}(s, a)) \\ &= \max_{a} q_{\pi_{k}}(s, a) \\ &\geq q_{\pi_{k}}(s, \pi_{k}(s)) \\ &\geq v_{\pi_{k}}(s). \end{align*}$\)

正如我们在上一章所讨论的，该定理向我们保证，每个$\pi_{k + 1}$都比$\pi_{k}$更好，或者与$\pi_{k}$一样好（在这种情况下它们都是最优策略）. 这反过来又确保了整个过程收敛到最优策略和最优价值函数. 通过这种方式，蒙特卡罗方法仅需样本片段，无需环境动态的其他知识，就可用于找到最优策略.

为了轻松获得蒙特卡罗方法收敛的保证，我们做出了两个不太现实的假设. 一个是片段具有探索性起始，另一个是策略评估可以在无穷多个片段上进行. 为了得到一个实用的算法，我们必须去除这两个假设. 我们将对第一个假设的讨论推迟到本章后面.

目前我们关注策略评估在无穷多个片段上进行的假设. 这个假设相对容易去除. 实际上，即使在经典的动态规划方法（如迭代策略评估）中也会出现同样的问题，该方法也只是渐近地收敛到真实价值函数. 在动态规划和蒙特卡罗两种情况下，有两种方法可以解决这个问题. 一种是坚持在每次策略评估中逼近$q_{\pi_{k}}$的想法. 通过进行测量和假设来获得估计误差的大小和概率的界限，然后在每次策略评估中采取足够的步骤，以确保这些界限足够小. 从保证在一定近似水平上正确收敛的意义上讲，这种方法可能是完全令人满意的. 然而，除了最小的问题之外，在实践中它可能需要太多的片段，以至于不太实用.

避免策略评估名义上所需的无穷多个片段的第二种方法是，在返回策略改进之前，放弃尝试完成策略评估. 在每次评估步骤中，我们朝着$q_{\pi_{k}}$的方向移动价值函数，但并不期望在很多步骤之前就能真正接近它. 我们在4.6节首次引入广义策略迭代的概念时就使用了这个想法. 这个想法的一种极端形式是值迭代，在每次策略改进步骤之间仅执行一次迭代策略评估. 就地值迭代的形式更为极端，在那里我们针对单个状态在改进和评估步骤之间交替进行.

对于蒙特卡罗策略迭代，自然的做法是在逐个片段的基础上在评估和改进之间交替进行. 在每个片段之后，使用观察到的回报进行策略评估，然后在该片段中访问的所有状态上改进策略. 沿着这些思路的一个完整而简单的算法，我们称之为蒙特卡罗ES（带探索性起始的蒙特卡罗方法），其伪代码如下框所示.

蒙特卡罗ES（探索性起始），用于估计 $\pi \approx \pi_{*}$ - 初始化： - 对于所有 $s \in S$，任意初始化 $\pi(s) \in A(s)$ - 对于所有 $s \in S$，$a \in A(s)$，任意初始化 $Q(s, a) \in \mathbb{R}$ - 对于所有 $s \in S$，$a \in A(s)$，将 $Returns(s, a)$ 初始化为空列表 - 无限循环（针对每个片段）： - 从 $S_0, A_0$ 开始，遵循 $\pi$ 生成一个片段：$S_0, A_0, R_1, \ldots, S_{T - 1}, A_{T - 1}, R_T$. 随机选择 $S_0 \in S$，$A_0 \in A(S_0)$，使得所有对的概率都大于0 - $G \leftarrow 0$ - 对于片段中的每一步 $t = T - 1, T - 2, \ldots, 0$： - $G \leftarrow \gamma G + R_{t + 1}$ - 除非对 $(S_t, A_t)$ 出现在 $(S_0, A_0), (S_1, A_1), \ldots, (S_{t - 1}, A_{t - 1})$ 中： - 将 $G$ 添加到 $Returns(S_t, A_t)$ - $Q(S_t, A_t) \leftarrow average(Returns(S_t, A_t))$ - $\pi(S_t) \leftarrow \underset{a}{\arg\max} Q(S_t, a)$

在蒙特卡罗ES中，每个状态 - 动作对的所有回报都会被累积和平均，无论在观察这些回报时采用的是什么策略. 很容易看出，蒙特卡罗ES不会收敛到任何次优策略. 如果它收敛到次优策略，那么价值函数最终会收敛到该策略的价值函数，而这反过来又会导致策略改变. 只有当策略和价值函数都达到最优时，才能实现稳定. 随着时间的推移，动作价值函数的变化逐渐减小，收敛到这个最优的固定点似乎是必然的，但尚未得到正式证明. 在我们看来，这是强化学习中最基本的未解决理论问题之一（部分解决方案见Tsitsiklis，2002）.

4 无探索性起始的蒙特卡罗控制¶

我们如何避免探索性起始这个不太现实的假设呢？确保所有动作都被无限次选择的唯一通用方法，是让智能体持续选择它们. 有两种方法可以确保这一点，从而产生了我们所说的同策略（on - policy）方法和异策略（off - policy）方法. 同策略方法试图评估或改进用于决策的策略，而异策略方法评估或改进的策略与用于生成数据的策略不同. 上面开发的蒙特卡罗ES方法就是同策略方法的一个例子. 在本节中，我们将展示如何设计一种不使用探索性起始这一不现实假设的同策略蒙特卡罗控制方法. 下一节将讨论异策略方法.

在同策略控制方法中，策略通常是“软”的，这意味着对于所有 $s \in S$ 和所有 $a \in A(s)$，$\pi(a|s) > 0$，但会逐渐向确定性的最优策略靠近. 第2章中讨论的许多方法都提供了实现这一点的机制. 我们在本节中介绍的同策略方法使用$\varepsilon$-贪婪策略，这意味着大多数时候它们会选择具有最大估计动作价值的动作，但以概率$\varepsilon$会随机选择一个动作. 也就是说，所有非贪婪动作被选择的概率为最小概率 $\frac{\varepsilon}{|A(s)|}$，而剩余的大部分概率 $1 - \varepsilon + \frac{\varepsilon}{|A(s)|}$ 则分配给贪婪动作. $\varepsilon$-贪婪策略是$\varepsilon$-软策略的一个例子，$\varepsilon$-软策略被定义为对于某些 $\varepsilon > 0$，对于所有状态和动作都满足 $\pi(a|s) \geq \frac{\varepsilon}{|A(s)|}$ 的策略. 在$\varepsilon$-软策略中，$\varepsilon$-贪婪策略在某种意义上是最接近贪婪策略的.

同策略蒙特卡罗控制的总体思路仍然是广义策略迭代. 与蒙特卡罗ES一样，我们使用首次访问蒙特卡罗方法来估计当前策略的动作价值函数. 然而，由于没有探索性起始的假设，我们不能简单地通过使策略相对于当前价值函数变为贪婪策略来改进它，因为这会阻止对非贪婪动作的进一步探索. 幸运的是，广义策略迭代并不要求策略一直变为贪婪策略，只要求它朝着贪婪策略的方向移动. 在我们的同策略方法中，我们只会将其移动到一个$\varepsilon$-贪婪策略. 对于任何$\varepsilon$-软策略$\pi$，相对于$q_{\pi}$的任何$\varepsilon$-贪婪策略都保证比$\pi$更好或与$\pi$一样好. 完整的算法如下框所示.

同策略首次访问蒙特卡罗控制（针对$\varepsilon$-软策略），估计 $\pi \approx \pi_{*}$ - 算法参数：小的 $\varepsilon > 0$ - 初始化： - $\pi$ 为任意 $\varepsilon$-软策略 - 对于所有 $s \in S$，$a \in A(s)$，任意初始化 $Q(s, a) \in \mathbb{R}$ - 对于所有 $s \in S$，$a \in A(s)$，将 $Returns(s, a)$ 初始化为空列表 - 无限重复（针对每个片段）： - 遵循 $\pi$ 生成一个片段：$S_0, A_0, R_1, \ldots, S_{T - 1}, A_{T - 1}, R_T$ - $G \leftarrow 0$ - 对于片段中的每一步 $t = T - 1, T - 2, \ldots, 0$： - $G \leftarrow \gamma G + R_{t + 1}$ - 除非对 $(S_t, A_t)$ 出现在 $(S_0, A_0), (S_1, A_1), \ldots, (S_{t - 1}, A_{t - 1})$ 中： - $Q(S_t, A_t) \leftarrow average(Returns(S_t, A_t))$ - $A^* \leftarrow \underset{a}{\arg\max} Q(S_t, a)$（平局时任意打破） - 将 $G$ 添加到 $Returns(S_t, A_t)$ - 对于所有 $a \in A(S_t)$： - 如果 $a = A^*$，则 $\pi(a|S_t) = 1 - \varepsilon + \frac{\varepsilon}{|A(S_t)|}$ - 如果 $a \neq A^*$，则 $\pi(a|S_t) = \frac{\varepsilon}{|A(S_t)|}$

策略改进定理保证了相对于$q_{\pi}$的任何$\varepsilon$-贪婪策略都是对任何$\varepsilon$-软策略$\pi$的改进. 设$\pi'$为$\varepsilon$-贪婪策略. 策略改进定理的条件适用，因为对于任何 $s \in S$：

\[ \begin{align*} q_{\pi}(s, \pi'(s)) &= \sum_{a} \pi'(a|s) q_{\pi}(s, a) \\ &= \frac{\varepsilon}{|A(s)|} \sum_{a} q_{\pi}(s, a) + (1 - \varepsilon) \max_{a} q_{\pi}(s, a) \\ &\geq \frac{\varepsilon}{|A(s)|} \sum_{a} q_{\pi}(s, a) + (1 - \varepsilon) \sum_{a} \frac{\pi(a|s) - \frac{\varepsilon}{|A(s)|}}{1 - \varepsilon} q_{\pi}(s, a) \end{align*} (5.2) \]

（该和是一个非负权重且权重总和为1的加权平均，因此它必须小于或等于所平均的最大数）

\[ \begin{align*} &= \frac{\varepsilon}{|A(s)|} \sum_{a} q_{\pi}(s, a) - \frac{\varepsilon}{|A(s)|} \sum_{a} q_{\pi}(s, a) + \sum_{a} \pi(a|s) q_{\pi}(s, a) \\ &= v_{\pi}(s). \end{align*} \]

因此，根据策略改进定理，对于所有 $s \in S$，$\pi' \geq \pi$（即 $v_{\pi'}(s) \geq v_{\pi}(s)$）. 我们现在证明，只有当$\pi'$和$\pi$在$\varepsilon$-软策略中都是最优的，即它们比所有其他$\varepsilon$-软策略都更好或一样好时，等式才成立.

考虑一个新环境，它与原始环境完全相同，只是将策略必须是$\varepsilon$-软的要求“内置”到环境中. 新环境与原始环境具有相同的动作和状态集，其行为如下. 如果在状态$s$下采取行动$a$，那么以概率$1 - \varepsilon$，新环境的行为与旧环境完全相同. 以概率$\varepsilon$，它会随机重新选择行动（概率相等），然后像旧环境一样使用新的随机行动. 在这个新环境中，使用一般策略能达到的最佳效果，与在原始环境中使用$\varepsilon$-软策略能达到的最佳效果相同. 设$\tilde{v}_{*}$和$\tilde{q}$表示新环境的最优价值函数. 那么，一个策略$\pi$在$\varepsilon$-软策略中是最优的，当且仅当$v_{\pi} = \tilde{v}_{*}$. 根据$\tilde{v}_{*}$的定义，我们知道它是以下方程的唯一解： $\(\begin{align*} \tilde{v}_{*}(s) &= (1 - \varepsilon) \max_{a} \tilde{q}_{*}(s, a) + \frac{\varepsilon}{|A(s)|} \sum_{a} \tilde{q}_{*}(s, a) \\ &= (1 - \varepsilon) \max_{a} \sum_{s', r} p(s', r|s, a)[r + \gamma \tilde{v}_{*}(s')] \\ & + \frac{\varepsilon}{|A(s)|} \sum_{a} \sum_{s', r} p(s', r|s, a)[r + \gamma \tilde{v}_{*}(s')]. \end{align*}$\)

当等式成立且$\varepsilon$-软策略$\pi$不再改进时，从（5.2）式我们也知道： $$ \begin{align} v_{\pi}(s) &= (1 - \varepsilon) \max_{a} q_{\pi}(s, a) + \frac{\varepsilon}{|A(s)|} \sum_{a} q_{\pi}(s, a) \ &= (1 - \varepsilon) \max_{a} \sum_{s', r} p(s', r|s, a)[r + \gamma v_{\pi}(s')] \ & + \frac{\varepsilon}{|A(s)|} \sum_{a} \sum_{s', r} p(s', r|s, a)[r + \gamma v_{\pi}(s')]. \end{align} $$

然而，这个方程与前面的方程相同，只是用 $v_{\pi}$ 代替了 $\tilde{v}_{*}$. 由于 $\tilde{v}_{*}$ 是唯一解，所以必然有 $v_{\pi} = \tilde{v}_{*}$.

本质上，我们在过去几页中表明，策略迭代适用于$\varepsilon$-软策略. 使用$\varepsilon$-软策略的自然贪婪策略概念，人们可以确保每一步都有所改进，除非已经在$\varepsilon$-软策略中找到了最佳策略. 这个分析与在每个阶段如何确定动作价值函数无关，但它确实假设动作价值函数是精确计算的. 这使我们大致回到了上一节的情况. 现在我们只能在$\varepsilon$-软策略中获得最佳策略，但另一方面，我们消除了探索性起始的假设.