强化学习的数学原理

强化学习（Reinforcement Learning, RL）是机器学习的核心范式之一，其核心目标是通过智能体与环境的动态交互，自主习得最优决策策略，以最大化长期累积奖励。

本文系统梳理了强化学习算法的相关数学原理，希望能对强化学习的理解有所帮助。同时，本文省略了部分基础知识的介绍，把重点放在强化学习经典算法和数学理解上，对复杂的证明和推导也予以省略。

# 基础概念

智能体（Agent）：决策主体，通过观察环境状态选择动作。例如，游戏 AI 中的角色控制器。

环境（Environment）：也称为模型，是智能体交互的外部世界，提供状态信息和反馈奖励。环境可以是物理世界（如机器人导航场景）或虚拟系统（如电子游戏）。

状态（State）：环境的当前特征描述，例如棋盘上的棋子分布（游戏场景）或自动驾驶车辆的实时位置和速度。

动作（Action）：智能体在特定状态下可执行的操作，分为​​离散动作​​（如游戏中的移动方向）和​​连续动作​​（如机器人关节角度调整）。

奖励（Reward）：环境对动作的即时数值反馈，用于量化动作效果。例如，游戏得分增加（正奖励）或碰撞障碍物（负奖励）。

策略（Policy）：从状态到动作的映射规则，决定智能体的行为模式。策略可以是确定性的（如查表法）或概率性的（如神经网络输出动作概率分布）。

轨迹（Trajectory）：智能体与环境交互过程中产生的状态、动作、奖励的序列链，即一条完整的交互路径。

回报（Return）：是轨迹中所有奖励的累积值，用于量化智能体在一条轨迹上的整体表现。

• 无折扣回报：直接累加所有即时奖励。$G = r_0 + r_1 + ... + r_T$
• 折扣回报：引入折扣因子 $γ \in (0,1)$，降低远期奖励的权重。$G = r_0 + γr_1 + γ^2r_2 + ...$

价值函数（Value Function）：衡量状态或动作的长期价值，分为​​状态价值函数​​（预测未来累积奖励）和​​动作价值函数​​（如 Q 函数）。

接下来对上述概念再做一些补充：

智能体在环境中，根据当前状态，依据策略选择一个动作与环境进行交互，交互完以后智能体进入下一个状态。每次执行动作，环境都会给出对应的奖励。当智能体确定好策略后，就可以计算出与策略相关联的状态价值函数与动作价值函数，用以评估策略的好坏。

环境是一个重要的概念，智能体与环境交互的过程中，学习到的是如何在环境中尽可能多的获取奖励。因此，环境有两个重要组成部分：一个是状态转移概率，一个是奖励的设置。一般情况下，智能体在同一状态执行相同动作可能进入的下一状态是不同的，这由环境的状态转移概率决定。环境的奖励由人为设定，由智能体所处的状态和采取的动作决定，可以是确定的，也可以是概率控制的。不同的奖励会影响智能体学习到的策略。

# 马尔可夫过程

智能体与环境的交互过程可以表示成马尔可夫过程（MPs）。以下是相关数学符号定义：

• 智能体的状态集合表示为 $S$，动作表示为状态的函数 $A(s)$，奖励是状态和动作的函数 $R(s,a)$。

• 环境（模型）由状态转移概率和奖励概率共同决定。状态转移概率 $p(s'\mid s,a)$ 表示智能体在状态 $s$ 下执行动作 $a$ 转移到状态 $s'$ 的概率。奖励概率 $p(r\mid s,a)$ 表示智能体状态 $s$ 下执行动作 $a$ 获得奖励 $r$ 的概率。

• 智能体执行的策略由 $\pi$ 表示，其中 $\pi(a \mid s)$ 是智能体在状态 $s$ 下执行动作 $a$ 的概率。

• 智能体与环境执行过程满足马尔可夫性质，即：

  $$p(s_{t+1}|s_t,a_t,s_{t-1},a_{t-1},\ldots,s_0,a_0)=p(s_{t+1}|s_t,a_t)\\ p(r_{t+1}|s_t,a_t,s_{t-1},a_{t-1},\ldots,s_0,a_0)=p(r_{t+1}|s_t,a_t),$$

同样，智能体在当前状态下执行动作的策略也与之前所处的状态无关，因此可以表示为马尔可夫决策过程（MDPs）。

# 贝尔曼公式

在相同环境下，智能体可以采取多种策略，那么哪个策略更好呢？从直观的角度来说，当智能体在环境中获取的回报越多，该策略就越好。此外，智能体在环境中有多个状态，好的策略应该在任意状态下都能获取更好的回报。由于环境的状态转移概率和奖励概率可以是不确定的，因此我们使用期望回报来评估策略的优劣。

# 一个简单示例

下面先通过一个四状态的交互例子演示如何计算回报，接着再介绍期望回报的计算和用途。

该例子中，智能体在一个四网格世界中行走，绿色箭头表示智能体采取的策略，红色数字是对应的奖励。在该示例中，所有过程都是确定的，包括策略，状态转移和奖励。

我们计算从每个状态出发，智能体能获取的回报：

$$\begin{gathered} v_{1}=r_1+\gamma r_2+\gamma^2r_3+\ldots=r_1+\gamma(r_2+\gamma r_3+\ldots)=r_1+\gamma v_2,\\ v_{2}=r_2+\gamma r_3+\gamma^2r_4+\ldots=r_2+\gamma(r_3+\gamma r_4+\ldots)=r_2+\gamma v_3, \\ v_{3}=r_{3}+\gamma r_{4}+\gamma^{2}r_{1}+\ldots=r_3+\gamma(r_4+\gamma r_1+\ldots)=r_3+\gamma v_4, \\ v_{4}=r_4+\gamma r_1+\gamma^2r_2+\ldots=r_4+\gamma(r_1+\gamma r_2+\ldots)=r_4+\gamma v_1. \end{gathered}$$

$v1、v2、v3、v4$ 分别表示从四个状态出发获取的回报。上面式子改用矩阵形式可以表示成下面的形式：

$$\underbrace{ \begin{bmatrix} v_1 \\ v_2 \\ v_3 \\ v_4 \end{bmatrix}}_{v}= \begin{bmatrix} r_1 \\ r_2 \\ r_3 \\ r_4 \end{bmatrix}+ \begin{bmatrix} \gamma v_2 \\ \gamma v_3 \\ \gamma v_4 \\ \gamma v_1 \end{bmatrix}=\underbrace{ \begin{bmatrix} r_1 \\ r_2 \\ r_3 \\ r_4 \end{bmatrix}}_{r}+\underbrace{\gamma \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}}_{P}\underbrace{ \begin{bmatrix} v_1 \\ v_2 \\ v_3 \\ v_4 \end{bmatrix}}_{v},\\ v = r + \gamma v$$

$v1、v2、v3、v4$ 表示智能体在上述策略下可获取的回报。

# 状态价值与贝尔曼公式

上述例子中，所有过程都是确定的，包括状态转移，策略等，因此，给定状态的回报也是确定的。当遇上随机的情况时，需要作一些拓展。

从时间 $t$ 开始考虑，智能体与环境的交互的数学表示如下：

$$S_t\xrightarrow{A_t}S_{t+1},R_{t+1}\xrightarrow{A_{t+1}}S_{t+2},R_{t+2}\xrightarrow{A_{t+2}}S_{t+3},R_{t+3}\ldots.$$

其中 $S、A、R$ 均为随机变量，以描述随机情况下的强化学习过程。基于此，回报的表达式是：

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+3} +....$$

由于 $G_t$ 是一个随机变量，从状态 $S_t$ 出发得到的期望回报即为 $v_\pi(s)=\mathbb{E}[G_t|S_t=s]$。这里，$v_\pi(s)$ 称为状态价值，表示状态 $s$ 的价值，是反映一个策略好坏的标准。

下面要解决一个重要问题：如何计算给定策略的状态价值函数？答案是使用贝尔曼公式。

根据 $G_t$ 的数学表达，可以得到：

$$\begin{aligned} G_{t} &= R_{t+1}+\gamma R_{t+2}+\gamma^{2}R_{t+3}+\ldots \\ &= R_{t+1}+\gamma(R_{t+2}+\gamma R_{t+3}+\ldots)\\ &= R_{t+1}+\gamma G_{t+1} \end{aligned}$$

进而状态价值函数可以改写成：

$$\begin{aligned} v_{\pi}(s) &=\mathbb{E}[G_t|S_t=s] \\ &=\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s] \\ &=\mathbb{E}[R_{t+1}|S_t=s]+\gamma\mathbb{E}[G_{t+1}|S_t=s] \end{aligned}$$

更进一步地，有：

$$\begin{aligned} \mathbb{E}[R_{t+1}|S_{t}=s] & =\sum_{a\in\mathcal{A}}\pi(a|s)\mathbb{E}[R_{t+1}|S_t=s,A_t=a]\\ & =\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{r\in\mathcal{R}}p(r|s,a)r \end{aligned}\\$$

$$\begin{aligned} \mathbb{E}[G_{t+1}|S_{t}=s] & =\sum_{s^{\prime}\in\mathcal{S}}\mathbb{E}[G_{t+1}|S_t=s,S_{t+1}=s^{\prime}]p(s^{\prime}|s)\\ & =\sum_{s^{\prime}\in\mathcal{S}}\mathbb{E}[G_{t+1}|S_{t+1}=s^{\prime}]p(s^{\prime}|s)\\ & =\sum_{s^{\prime}\in\mathcal{S}}v_\pi(s^{\prime})p(s^{\prime}|s) \\ & =\sum_{s^{\prime}\in\mathcal{S}}v_\pi(s^{\prime})\sum_{a\in\mathcal{A}}p(s^{\prime}|s,a)\pi(a|s) \end{aligned}$$

由此推导得到贝尔曼公式：

$$\begin{aligned} v_{\pi}(s) & =\mathbb{E}[R_{t+1}|S_t=s]+\gamma\mathbb{E}[G_{t+1}|S_t=s], \\ &= \underbrace{\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{r\in\mathcal{R}}p(r|s,a)r}_{\text{mean of immediate rewards}}+\underbrace{\gamma\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)v_\pi(s^{\prime})}_{\text{mean of future rewards}}\\ &= \sum_{a\in\mathcal{A}}\pi(a|s)\left[\sum_{r\in\mathcal{R}}p(r|s,a)r+\gamma\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)v_{\pi}(s^{\prime})\right] \end{aligned}$$

贝尔曼公式揭示了状态价值与即时奖励和未来奖励的关系。

上面提出的贝尔曼公式是元素形式的，即公式左侧的状态价值特定于某个状态，我们令 $r_{\pi}(s) = \sum_{a\in\mathcal{A}}\pi(a|s)\sum_{r\in\mathcal{R}}p(r|s,a)r$ 表示状态 $s$ 下的及时奖励期望，$p_\pi(s^{\prime}|s) =\sum_{a\in\mathcal{A}}\pi(a|s)p(s^{\prime}|s,a)$ 表示策略 $\pi$ 下智能体从状态 $s$ 转移到 $s^{\prime}$ 的概率，那么贝尔曼公式可以写成：

$$v_{\pi}(s_i) = r_{\pi}(s_i) + \gamma \sum_{s_j \in S} p_{\pi}(s_j | s_i) v_{\pi}(s_j).$$

使用矩阵形式的表达：

$$\underset{v_{\pi}}{\underbrace{\begin{bmatrix} v_{\pi}(s_1) \\ v_{\pi}(s_2) \\ v_{\pi}(s_3) \\ v_{\pi}(s_4) \end{bmatrix}}} = \underset{r_{\pi}}{\underbrace{\begin{bmatrix} r_{\pi}(s_1) \\ r_{\pi}(s_2) \\ r_{\pi}(s_3) \\ r_{\pi}(s_4) \end{bmatrix}}} + \gamma \underset{P_{\pi}}{\underbrace{\begin{bmatrix} p_{\pi}(s_1|s_1) & p_{\pi}(s_2|s_1) & p_{\pi}(s_3|s_1) & p_{\pi}(s_4|s_1) \\ p_{\pi}(s_1|s_2) & p_{\pi}(s_2|s_2) & p_{\pi}(s_3|s_2) & p_{\pi}(s_4|s_2) \\ p_{\pi}(s_1|s_3) & p_{\pi}(s_2|s_3) & p_{\pi}(s_3|s_3) & p_{\pi}(s_4|s_3) \\ p_{\pi}(s_1|s_4) & p_{\pi}(s_2|s_4) & p_{\pi}(s_3|s_4) & p_{\pi}(s_4|s_4) \end{bmatrix}}} \underset{v_{\pi}}{\underbrace{\begin{bmatrix} v_{\pi}(s_1) \\ v_{\pi}(s_2) \\ v_{\pi}(s_3) \\ v_{\pi}(s_4) \end{bmatrix}}}$$

$v_\pi$ 表示所有状态的价值，$r_\pi$ 是对应的即时奖励期望，$P_\pi$ 是状态转移概率矩阵。基于上述矩阵形式的贝尔曼公式，可知，给定策略和环境，我们可以通过以下表达式得出状态价值函数的解析解：

$$v_{\pi} = (I - \gamma P_{\pi})^{-1} r_{\pi}$$

# 迭代法求状态价值

上述方法可以计算所有状态价值，但在实际应用中面临着计算复杂度的问题。上述的求逆操作复杂度与状态数量相关，当智能体在环境中可能存在非常多甚至无穷多状态时，使用以上数学解析法求解状态价值不现实。因此这里介绍另一种迭代法：

$$v_{k+1} = r_{\pi} + \gamma P_{\pi} v_k, \quad k = 0, 1, 2, \ldots$$

$v_i$ 表示第 $i$ 次迭代得到的状态价值函数，为矩阵形式的。$v_0$ 是任意初始结果，一般初始化为全零向量。当迭代次数足够多时，有：

$$v_k \to v_\pi = (I - \gamma P_{\pi})^{-1} r_{\pi}, \quad k \to \infty$$

具体证明过程从略。

# 动作价值

前面我们介绍了状态价值的定义以及计算方法，也知道了通过比较不同策略的的状态价值可以评估策略的优劣。当一个策略比另一个策略更好时，它的所有状态的价值应当都比另一个策略更大。这里，我们介绍一个新的概念：动作价值。

依据状态价值的含义，可以得到动作价值的定义：智能体在一个状态下，选择一个动作的期望回报：

$$q_\pi(s,a)=\mathbb{E}[G_t | S_t = s， A_t=a]$$

将状态价值的表达式进行拆解，我们可以得到动作价值与状态价值的关联公式：

$$v_\pi(s)=\mathbb{E}[G_t | S_t = s] = \sum_{a \in \mathcal{A}} \underbrace{\mathbb{E}[G_t | S_t = s, A_t = a]}_{q_{\pi}(s,a)} \pi(a|s)$$

回顾贝尔曼公式的表达式，状态价值可以写成动作选择概率乘上一个式子：

$$v_\pi(s)=\sum_{a\in\mathcal{A}}\pi(a|s)\left[\sum_{r\in\mathcal{R}}p(r|s,a)r+\gamma\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)v_{\pi}(s^{\prime})\right]$$

通过对比，我们就得到了动作价值的表达式，它由两部分组成，一部分是当前状态下采取该动作的即时奖励期望，另一部分是执行该动作后，智能体在下一状态的期望回报：

$$q_\pi(s,a)=\sum_{r\in\mathcal{R}}p(r|s,a)r+\gamma\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)v_{\pi}(s^{\prime})$$

动作价值有什么用呢？和状态价值一样，都用来衡量策略的好坏。强化学习训练的过程，本质上是在不断优化智能体策略的动作价值或者状态价值，以得到更好的策略。

那么，动作价值如何计算呢？

第一种方法就是在计算得到状态价值以后，根据上面表达式求解每一个动作价值。

第二种方法则是对表达式进行改写，类似于状态价值的的迭代法，动作价值也有自己的迭代计算方法。

$$q_{\pi}(s, a) = \sum_{r \in \mathcal{R}} p(r | s, a) r + \gamma \sum_{s' \in \mathcal{S}} p(s' | s, a) \sum_{a' \in \mathcal{A}(s')} \pi(a' | s') q_{\pi}(s', a')$$

可以观察到，式子左右两侧都有 $q_\pi$，给定任意初始值，使用上述转移公式进行多次迭代后，就可以得到动作价值的近似解。

# 贝尔曼最优公式

上一节通过贝尔曼公式，我们了解了如何计算策略的状态价值、动作价值来评估策略的好坏。这一节，我们将学习另一个问题：如何优化策略？是否有最优策略？如果有，怎么得到呢？

首先，我们需要定义什么是最优策略。最优策略 $\pi^*$ 应当满足，对于任意策略 $\pi$，任意智能体的状态 $s$，都有 $v_{\pi^*}(s) \ge v_\pi(s)$。

基于最优策略的定义以及贝尔曼公式，可以得到贝尔曼最优公式：

$$\begin{align*} v(s) &= \max_{\pi(s) \in \Pi(s)} \sum_{a \in \mathcal{A}} \pi(a|s) \left( \sum_{r \in \mathcal{R}} p(r|s,a)r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a)v(s') \right) \\ &= \max_{\pi(s) \in \Pi(s)} \sum_{a \in \mathcal{A}} \pi(a|s) q(s, a), \end{align*}$$

对应的矩阵形式：

$$v = \max_{\pi \in \Pi}(r_\pi + \gamma P_\pi v)$$

注意到：

$$\sum_{a \in \mathcal{A}} \pi(a|s) q(s, a) \leq \sum_{a \in \mathcal{A}} \pi(a|s) \max_{a \in \mathcal{A}} q(s, a) = \max_{a \in \mathcal{A}} q(s, a), \\ \pi(a|s) = \begin{cases} 1, & a = a^*, \\ 0, & a \neq a^*. \end{cases} \\$$

其中，$a^* = \arg \max_{a} q(s, a)$。

可以证明，对于任意策略，计算其动作价值后，通过上述方式选择最大价值的动作更新策略，一定可以优化策略。因此，对于最优策略而言，选择最大价值的动作更新策略后，策略保持不变。此时，贝尔曼最优公式实际上就是最优策略满足的贝尔曼公式。

基于此，我们介绍第一种求解最优策略的方法 —— 策略迭代法。首先初始化任意智能体策略，计算对应的动作价值，通过上述式子更新策略。在经过无穷次迭代后，理论上得到的策略就是最优策略。

如有兴趣，读者可自行查阅相关证明资料。

接下来，我们还要继续分析贝尔曼最优公式，榨干它的剩余价值，得到另一种求解方法 —— 价值迭代法。

首先定义 $f(v) = \max_{\pi \in \Pi}(r_\pi + \gamma P_\pi v)$ 函数表示基于 $v$ 计算 $q$，选择最大价值的动作更新策略。基于此，可以将求解贝尔曼最优公式改写成求解下列方程：

$$v = f(v)$$

求解该方程涉及到压缩映射原理，可以证明，$f(v)$ 函数满足压缩映射原理的条件。因此，求解上述方程可以转变成一个迭代过程。该过程是：任意初始化状态价值 $v_0$，计算 $v_{t+1} = f(v_t)$。当 $t \to \infty$ 后，$v_t \to v^*$，有 $v^* = f(v^*)$。此时可以证明 $v^*$ 就是最优策略的状态价值，基于该价值，选择最大价值的动作更新得到的策略就是最优策略。这就是价值迭代法求解最优策略的方法。

由于这部分原理内容相对比较复杂，所以有必要进行一些补充：

观察 $f(v)$ 表达式，在此处，$\pi$ 和 $v$ 是独立的变量，不再具有任何强化学习的约束，仅是一个数学上的表达。价值迭代和策略迭代的不同之处在于，策略迭代的任意中间过程得到的策略和价值都是一一对应的，在强化学习环境中是有语义的。但价值迭代不同，中间过程的 $\pi$ 和 $v$ 都只是一个值，没有任何实际关联。换句话说，价值迭代的过程中，$v$ 可能并不对应任意一个策略，即没有实际含义。但是根据数学推论，当迭代无穷次以后，我们得到 $\pi^*$ 和 $v^*$，满足 $v^* = f(v^*)$，即满足了贝尔曼公式，此时才具有了语义，$v^*$ 就是 $\pi^*$ 的状态价值。并且，可以证明，由此得到的策略就是最优策略。

本小节的介绍思路可以概括如下：首先，阐述了贝尔曼最优公式的定义，其右侧表达式可视为一种基于贪婪策略的优化操作。可以证明，执行这一操作后，策略的状态价值不会降低，从而引出了策略迭代法（其有效性证明在此略去）。对于最优策略而言，经过该操作后，策略的价值保持不变，即满足 $ v = f (v) $。因此，求解最优策略的问题转化为求解该方程。接着，通过压缩映射原理，推导出了价值迭代方法，进而得出 $ v^* = f (v^*) $，满足贝尔曼公式。这里还有最后一个问题，最优策略满足 $ v = f (v) $ 是否意味着所有满足该方程的策略都是最优策略。事实是，在数学上是可以证明这一点，但本节中未详细展开。

# 价值迭代和策略迭代

上一节梳理了两种策略优化的方法，分别是价值迭代和策略迭代，这一节将更详细地对这两种方法进行总结，并提出另一种方法，介于价值迭代和策略迭代之间。

# 价值迭代

价值迭代的算法流程如下：

1. 首先任意初始化一个价值函数，一般选择全 0；
2. 基于当前价值函数 $v_k$，根据 $\pi_{k+1} = \arg \max_{\pi} (r_{\pi} + \gamma P_{\pi} v_k)$ 得到下一次迭代的策略 $\pi_{k+1}$。这一步，称为策略更新。
3. 根据贝尔曼最优公式迭代得到下一价值函数 $v_{k+1} = r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_k$，这一步称为价值更新。
4. 重复第二步和第三步直至策略变化或价值变化几乎收敛为止。

具体而言，策略更新这一步，基于当前轮次的价值函数，依据下列公式求解每个状态对应的各个动作价值：

$$\pi_{k+1}(s) = \arg\max_{\pi} \sum_{a} \pi(a|s) \underbrace{\left( \sum_{r} p(r|s,a)r + \gamma \sum_{s'} p(s'|s,a)v_k(s') \right)}_{q_k(s,a)}, \quad s \in \mathcal{S}$$

根据最大价值的动作更新策略得到 $\pi_{k+1}$：

$$\pi_{k+1}(a|s) = \begin{cases} 1, & a = a^*_k(s) \\ 0, & a \neq a^*_k(s) \end{cases}$$

价值更新则根据贝尔曼最优公式计算所有状态的下一轮次的状态价值：

$$v_{k+1}(s) = \sum_{a} \pi_{k+1}(a|s) \underbrace{\left( \sum_{r} p(r|s,a)r + \gamma \sum_{s'} p(s'|s,a)v_k(s') \right)}_{q_k(s,a)} = \max_{a}{q_k(s,a)}, \quad s \in \mathcal{S}$$

总结下来，价值迭代的流程如下：

$$v_k(s) \rightarrow q_k(s, a) \rightarrow \text{贪婪策略 } \pi_{k+1}(s) \rightarrow v_{k+1}(s) = \max_a q_k(s, a)$$

# 策略迭代

策略迭代的算法流程如下：

1. 首先初始化任意的策略。

2. 根据当前策略，计算贝尔曼公式，求解策略的价值函数。根据第三节提到的算法，求解策略价值函数可以通过多轮迭代的方式：

   $$v_{\pi_k}^{(j+1)} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(j)}, \quad j = 0, 1, 2, \ldots$$

   因此，策略迭代算法的每一轮还有迭代，用于估计策略价值。这一步称为策略评估。

3. 基于当前策略的价值函数，根据 $\pi_{k+1} = \arg \max_{\pi} (r_{\pi} + \gamma P_{\pi} v_k)$ 得到下一次迭代的策略 $\pi_{k+1}$。这一步称为策略改进，与价值迭代的策略更新是一样的流程。

4. 重复第二步和第三步，直至策略变化或价值变化几乎收敛为止。

策略迭代的每一次更新策略都能使新策略的价值函数更大，并且经过无穷次迭代后，得到的策略就是最优策略。

上述结论的证明请自行查阅资料了解。

# 截断策略迭代

对比策略迭代和价值迭代的算法流程，可以发现二者之间存在一些联系。

$$\begin{aligned} \pi_0 \xrightarrow{PE} v_{\pi_0} &\xrightarrow{PI} \pi_1 \xrightarrow{PE} v_{\pi_1} \xrightarrow{PI} \pi_2 \xrightarrow{PE} v_{\pi_2} \xrightarrow{PI} \cdots \\ v_0 &\xrightarrow{PU} \pi_1' \xrightarrow{VU} v_1 \xrightarrow{PU} \pi_2' \xrightarrow{VU} v_2 \xrightarrow{PU} \cdots \end{aligned}$$

将策略更新和策略改进、价值更新和策略评估一一对齐，可以发现，除了策略迭代算法在最开始需要初始化一个随机策略意外，这两种算法的唯一区别仅在于价值函数的计算上。

对于策略迭代的策略评估，我们通过下面式子循环计算得到：

$$v_{\pi_k}^{(j+1)} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(j)}, \quad j = 0, 1, 2, \ldots$$

而对于价值迭代的价值更新，我们通过下面式子计算得到：

$$v_{k+1} = r_{\pi_k} + \gamma P_{\pi_k} v_{k}$$

对应上述流程中，二者的不同实际上是从 $v_{\pi_1}$ 和 $v_1$ 的计算开始的。不难发现，$v_1$ 的计算实际是计算 $v_{\pi_1}$ 的迭代过程中的第一轮循环。更新价值时，策略迭代是在求解贝尔曼公式，而值迭代则是直接一步带入。从这个视角来看，我们就将策略迭代和价值迭代联系起来了，它们分别对应两种极端：价值迭代算法只迭代一次，策略迭代算法迭代无穷多次。而介于二者之间的算法，就是本节要介绍的截断策略迭代算法。

三者的关系通过下面公式即可清晰表示：

$$\begin{align*} \quad & v_{\pi_1}^{(0)} = v_0 \\ \text{value iteration} \leftarrow v_1 \longleftarrow \quad & v_{\pi_1}^{(1)} = r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}^{(0)} \\ & v_{\pi_1}^{(2)} = r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}^{(1)} \\ & \vdots \\ \text{truncated policy iteration} \leftarrow \bar{v}_1 \longleftarrow \quad & v_{\pi_1}^{(j)} = r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}^{(j-1)} \\ & \vdots \\ \text{policy iteration} \leftarrow v_{\pi_1} \longleftarrow \quad & v_{\pi_1}^{(\infty)} = r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}^{(\infty)} \end{align*}$$

截断策略迭代和策略迭代的不同就在于，策略评估时进通过有限次迭代计算价值函数，然后就进行策略改进。

# 蒙特卡洛方法

到目前为止，我们似乎已经解决了强化学习的核心问题：如何让智能体在环境中学习到最优策略？但是，目前所有学习的方法都基于一个重要前提 —— 环境已知。

环境，也称模型，包含两个重要因素，分别是状态转移概率 $p(s^\prime | s, a)$ 以及奖励概率 $p(r|s,a)$。本文前面介绍的求解最优策略的方法都是有模型的（model-base），即已经知道了环境的两个组成部分。然而，在实际场景中，绝大多数情况下，我们不可能提前了解环境，我们对环境的感知来自于智能体与环境的交互经验。换句话说，我们是在经验中学习。所以，本文的剩余内容，则聚焦于另一类强化学习方法 —— 无模型（mdoel-free）的强化学习算法。

在策略迭代中，有一步策略评估需要根据贝尔曼公式计算价值函数。然而当模型不可知时，我们无法计算状态价值。由于状态价值和动作价值的定义是从当前状态开始或执行此动作的回报期望，因此可以基于概率统计的方式，让智能体与环境进行多轮交互，得到多条轨迹（回合）的回报，然后计算平均值估计回报期望，作为状态价值或动作价值。这种方法就是最简单的基于蒙特卡洛的强化学习算法。

在蒙特卡洛方法中，动作价值基于下面公式进行估计：

$$q_{\pi_k}(s, a) = \mathbb{E}[G_t | S_t = s, A_t = a] \approx \frac{1}{n} \sum_{i=1}^{n} g_{\pi_k}^{(i)}(s, a)$$

其中 $n$ 是智能体与环境交互的回合数量，$g_{\pi_k}^{(i)}(s, a)$ 是第 $i$ 回合的回报奖励。

最后，根据估计的动作价值，基于蒙特卡洛的强化学习算法选择最大价值动作改进策略。

不难发现，上述方法需要进行大量的采样来估计价值，在实际应用中效率非常低下。接下来，我们逐步介绍如何优化蒙特卡洛方法，提高它的计算效率。

首先，上述方法在每次迭代需要计算某个动作价值时，会从对应的状态和动作出发执行多次，得到多个回合的回报。然而，这种采样方法得到的每个回合数据仅被用于一次计算，效率非常低下。通过下面的计算方式，我们可以更高效地利用每一回合的数据，估计对应的动作价值。

$$\begin{align*} s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_4} s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_3} s_5 \xrightarrow{a_1} \ldots \quad &\text{[original episode]} \\ s_2 \xrightarrow{a_4} s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_3} s_5 \xrightarrow{a_1} \ldots \quad &\text{[subepisode starting from $(s_2, a_4)$]} \\ s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_3} s_5 \xrightarrow{a_1} \ldots \quad &\text{[subepisode starting from $(s_1, a_2)$]} \\ s_2 \xrightarrow{a_3} s_5 \xrightarrow{a_1} \ldots \quad &\text{[subepisode starting from $(s_2, a_3)$]} \\ s_5 \xrightarrow{a_1} \ldots \quad &\text{[subepisode starting from $(s_5, a_1)$]} \end{align*}$$

改进后的算法在数据利用上更加高效，但还是存在一个问题，因为需要保证所有状态 - 动作对均能采样得到，需要从每个状态 - 动作对出发采样数据。这是因为在某些策略下，有些状态可能根本访问不到，有些动作根本不会执行，此时必须以此为起点采样数据。

进而引出新的改进算法 $\epsilon-greedy$ 蒙特卡洛方法。该算法基于策略迭代方法，在策略改进时使用下述式子更新策略：

$$\pi(a|s) = \begin{cases} 1 - \dfrac{\epsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)| - 1), & a = a^* \\ \dfrac{\epsilon}{|\mathcal{A}(s)|}, & a \ne a^* \end{cases}$$

这保证每次更新得到的策略依然具有随机性，随机程度由 $\epsilon \in [0,1]$ 超参数设置。通过这种方式更新得到的策略，可以保证智能体在任意状态下都可能执行所有动作（探索性策略），即从任意状态 - 动作对出发，只要进行足够长的交互，就可以访问到所有状态 - 动作对，也可以计算所有动作价值。这样，在策略评估阶段，只需要进行一回合交互就可以更新策略，大大提高了蒙特卡洛算法的计算效率。

需要补充的是，策略迭代算法在实际执行时可以不等待动作价值计算完成再更新策略，可以只进行几步估计就进行更新。虽然动作价值的估计很粗糙，但从长远角度来看，这种做法依然可以逼近最优策略。

在实际应用中，$\epsilon$ 的设置对智能体学习到的策略有直接影响，一般来说 $\epsilon$ 的值不宜过大，在 0.1 左右即可，视情况而定。也可以在策略迭代开始时设置一个较大的 $\epsilon$，随后在迭代过程中逐渐减小。

# 时序差分法

本节介绍另一个免模型的强化学习方法 —— 时序差分法（temporal-difference learning）。在此之前，需要先了解一些数学背景，方便更好地理解该算法。

# Robbins-Monro 算法

RM 算法用于求解这样一个等式的根：

$$g(w) = 0$$

其中 $g$ 的表达式未知，并在一般情况下，我们认为它是一个单调递增函数（机器学习中常常把优化的目标函数视为凸函数，而凸函数的导数具有单调性）。

当给定 $w$ 时，我们得到一个带有噪声的观察结果，其中 $\eta$ 是观察的误差：$\tilde{g}(w, \eta) = g(w) + \eta$。

可视化表示成下面的形式：

![RM 算法求解示例](https://jongsh.oss-cn-beijing.aliyuncs.com/blog/content/202505/202505132152478.png?x-oss-process=image/format,webp"/>