强化学习基础导论

经典控制与强化学习的对比

控制系统的核心思想是通过反馈机制来调节系统行为。具体来说，系统接收控制器发出的输入信号 u(t)，然后产生输出 y(t)。系统还有一个目标输出 y_{ref}(t)（参考信号或期望输出）。控制器的作用就是比较当前系统的实际输出 y(t) 和我们期望的输出 y_{ref}(t)，计算它们之间的差异，然后基于这个差异来决定下一步应该给系统什么样的控制输入。这就形成了一个闭环反馈系统。

在框图中，圆圈表示比较器，它接收 y_{ref}(t) 和 y(t)，计算误差后输出给控制器。控制器根据这个误差生成控制信号 u(t)，系统接收 u(t) 后产生新的输出 y(t)，这个输出又被反馈回比较器，形成循环。

系统中的关键变量

需要明确三个核心变量的物理意义。u(t) 既是系统的输入，也是控制器的输出，它代表我们施加给系统的控制作用。y(t) 是系统的输出，反映了系统在控制作用下的实际表现。y_{ref}(t) 是我们期望系统达到的目标输出，也称为参考轨迹或设定值。

控制器的设计准则

现在的核心问题是：如何设计控制信号 u(t)？我们需要一个明确的优化目标。这个目标通过一个代价函数来表达：

这个公式的含义是：我们要找到最优的控制策略 \hat{u}(t)，使得从当前时刻 t 开始到未来所有时刻的某个代价最小化。代价函数由两部分组成。

• 第一项 \int_t^{\infty} (y_{ref}(t') - y(t'))^2 dt' 是跟踪误差的累积，它衡量系统输出与期望输出之间的偏差。这一项越小，说明系统越接近我们想要的行为。
• 第二项 \lambda \int_t^{\infty} u^2(t') dt' 是控制能量的累积，它衡量我们需要施加多大的控制力。

为什么要有第二项？因为在实际系统中，控制输入往往是有代价的（能量、成本、执行器磨损等），如果只优化第一项，可能会得到一个需要施加极大控制力的解，这在实践中不可行。参数 \lambda 用来平衡这两个目标：较小的 \lambda 意味着我们更关注跟踪精度，愿意付出更多控制代价；较大的 \lambda 意味着我们希望节省控制能量，即使牺牲一些跟踪精度。

求解这个优化问题的关键

要求解上述优化问题，我们必须知道 u(t) 和 y(t) 之间的关系。换句话说，当我们施加某个控制输入 u(t) 时，系统会如何响应，产生什么样的输出 y(t)？这种输入-输出的映射关系就是系统的动力学特性。如果不知道系统动力学，我们无法预测某个控制策略的效果，也就无法进行优化。因此，建立系统的数学模型（描述其动力学行为）是控制设计的前提。

强化学习的核心框架

为什么需要强化学习

在很多情况下，我们能够获得系统动力学的精确模型，这时可以使用前面讨论的经典控制方法。但当系统模型不可获得、过于复杂或具有高度随机性时，经典控制方法就难以应用了。这种情况下，我们需要采用强化学习的方法。强化学习的核心思想是：不需要事先知道系统的精确数学模型，而是通过与环境的交互来学习控制策略。

强化学习的基本框架

强化学习系统由两个主体构成：智能体（Agent）和环境（Environment）。它们之间通过三个量进行交互：状态、动作和奖励。

环境代表了我们感兴趣的那部分外部世界。在每个时刻 t，环境向智能体提供两个信息。第一个是状态 S_t，它属于状态空间 \mathcal{S}，描述了当前环境所处的配置。第二个是奖励 R_t，它属于实数集合 \mathcal{R} \subset \mathbb{R}，是一个标量值。奖励的作用是告诉智能体当前环境的行为是好是坏，它是评价系统表现的即时反馈信号。

智能体在时刻 t 接收到状态 S_t 和奖励 R_t 后，需要决定采取什么动作。它选择的动作记为 A_t，这个动作必须属于允许的动作集合 \mathcal{A}(S_t)。注意这里动作空间可能依赖于当前状态，因为在不同状态下可执行的动作可能不同。

从框图可以看出这是一个循环过程：智能体在 t 时刻根据 S_t 和 R_t 选择动作 A_t，环境接收这个动作后转移到新状态 S_{t+1}，同时产生新的奖励 R_{t+1}，然后将它们反馈给智能体，智能体再基于新的信息选择下一个动作，如此循环往复。

强化学习与经典控制的本质区别

回顾经典控制，我们需要知道 u(t) 到 y(t) 的映射关系（系统动力学），然后求解优化问题来得到最优控制。而在强化学习中，我们不假设知道状态转移规律（即给定 S_t 和 A_t，S_{t+1} 如何产生），智能体通过不断尝试不同的动作，观察环境的反应（状态转移和奖励），逐渐学习出哪些动作在哪些状态下能获得更高的累积奖励。这种学习过程不依赖于环境模型的先验知识。

强化学习决策机制

智能体在时刻 t 接收到状态 S_t 和奖励 R_t 后，需要决定采取什么动作 A_t \in \mathcal{A}(S_t)。但这个决策不是随意的，而是使得某个长期目标最大化。这个长期目标就是回报（Return）。

回报的定义与时间折扣

回报 G_t 定义为从时刻 t 开始的未来所有奖励的加权和：

这里 \gamma 称为折扣因子。首先，\gamma \in [0,1] 确定了未来长期奖励相比于即时奖励的重要性。如果 \gamma 接近0，智能体会变得"短视"，只关注眼前的奖励，因为 \gamma^2, \gamma^3, \ldots 会迅速衰减为0，远期奖励几乎不被考虑。如果 \gamma 接近1，智能体会"有远见"，愿意为了未来的更大收益而牺牲当前的即时奖励。

从数学角度看，折扣因子还保证了无限时间范围内回报的有界性。如果奖励序列有界，比如 |R_t| \leq R_{max}，那么即使求和到无穷，由于几何级数的收敛性，G_t \leq \frac{R_{max}}{1-\gamma} 是有限的。

证明:

1. 定义回报（持续式任务）：

2. 先“取绝对值再求和”（三角不等式）：

3. 用已知上界 |R_{t}| \le R_{\max} 替换每一项：

4. 几何级数在 \gamma\in[0,1) 时收敛：

5. 合并得到上界：

策略的概念

智能体的决策规则用策略 \pi 来表示。策略有两种情况，第一种确定性策略（Deterministic Policy）: 每个状态都只选择一个特定的动作，比如在状态 s 下，永远选择动作 a :

第二种是随机性策略（Stochastic Policy），用条件概率分布 \pi(a|s) 表示，它给出了在状态 s 下选择动作 a 的概率，比如说:

这样策略就是随机的，在同一个状态下，智能体可能以不同的概率选择不同的动作。随机性策略一般在学习早期的时候，智能体不知道哪个动作更好，因此需要探索，但是一旦我们有了最优动作价值 Q(s,a) 之后，我们就可以一直选择最优动作，这就变成了确定性策略。

随机性策略必须满足概率的归一化条件。如果动作空间 \mathcal{A} 是离散的，那么对于任意状态 s，所有可能动作的概率之和必须为1：

如果动作空间是连续的，归一化条件变成积分形式：

这两个条件确保了 \pi(a|s) 是一个有效的概率分布。

状态价值函数

有了策略和回报的定义，我们现在可以评估一个策略的好坏。状态价值函数 V^\pi(s) 用来衡量在状态 s 下，按照策略 \pi 行动，平均可以获得多少总回报：

• S_t = s：表示当前时刻智能体处于状态 s。
• G_t：表示从当前时刻开始往后的累计折扣回报。
• 期望 \mathbb{E}_{\pi}：表示在策略 \pi 下，对所有可能发生的轨迹取平均。

也就是说，从状态 s 出发，智能体按照策略 \pi 选择动作，环境根据这些动作产生新的状态和奖励。因为策略可能是随机的，环境转移也可能是随机的，所以我们取所有可能结果的平均值，这个平均值，就是 V^{\pi}(s)。

状态价值函数可以评估策略优劣。如果对于所有状态，策略 \pi_1 的价值函数都大于等于策略 \pi_2，那么 \pi_1 就是更好的策略。

最优状态价值函数

最优状态价值函数 V^*(s) 定义为所有可能策略中能达到的最大价值：

这个定义对状态空间中的每一个状态都成立。V^*(s) 代表了在状态 s 下，如果智能体采用最聪明的策略，所能获得的最大期望回报。注意这里的最大化是对所有可能的策略进行的，包括确定性策略和随机策略。

最优策略

强化学习的终极目标是找到最优策略。最优策略 \pi^* 被定义为能够最大化每个状态的价值函数的那个策略：

这个定义说明，最优策略就是在每个状态下都能获得最大期望回报的策略。注意这里的最大化是对所有可能的策略进行的。从形式上看，给定状态 s，\pi^*(a|s) 是使得价值函数 V^\pi(s) 达到最大值的那个策略。

最优价值函数和最优策略的唯一性

关于最优解的唯一性，有两个重要结论。

首先，最优价值函数 V^* 是唯一的。无论从哪个策略出发去优化，最终得到的最大价值函数都是同一个。这是因为 V^*(s) 的定义就是所有策略能达到的价值的上确界，这个上确界是唯一确定的。

但是，达到这个最优价值的策略 \pi^* 不一定唯一。可能存在多个不同的策略，它们在所有状态下都能达到同样的最优价值 V^*(s)。如果在某个状态下，两个不同的动作都能带来相同的最优回报，那么选择这两个动作中的任意一个的策略都是最优的。

换句话说，终点是唯一的，但是路可能有多条。

多臂老虎机问题

多臂老虎机模型简介

多臂老虎机是可以用强化学习工具处理的最简单模型。它的简单性体现在环境的特殊结构上：状态空间是空集 \mathcal{S} = \emptyset，这意味着不存在状态的概念，或者说整个问题只有一个状态。动作空间是有限离散的，包含 K 个动作：\mathcal{A} = \{1, \ldots, K\}，这 K 个动作对应 K 个"臂"。奖励 R_t(a) \in \mathbb{R} 只依赖于当前选择的动作 a，而与时间 t 无关（除了随机性）。

这个模型之所以简单，是因为它消除了状态转移的复杂性。智能体每次只需要选择一个臂（动作），然后观察这个臂给出的奖励，所有的选择都是独立的，不存在因为当前选择而改变未来状态的情况。多臂老虎机问题的核心挑战是：如何在探索（尝试不同的臂以了解它们的奖励分布）和利用（选择目前看起来最好的臂）之间取得平衡。

多臂老虎机的核心性质

多臂老虎机问题有两个关键性质使其成为最简单的强化学习模型。第一个性质是奖励的独立性：时刻 t 的奖励不依赖于 t 之前选择的动作。这意味着每次选择动作都是一个独立的决策，过去的选择不会影响当前的奖励分布。第二个性质是平稳性：奖励 R_t(a) 的统计特性不随时间 t 变化。换句话说，如果我们在时刻1选择动作 a 和在时刻100选择动作 a，这两次获得的奖励服从相同的概率分布。正是这两个性质的结合，使得多臂老虎机问题避免了复杂的时序依赖和动态规划，问题简化为估计每个动作的平均奖励。

动作价值函数

要解决多臂老虎机问题，核心是评估每个动作的好坏。我们定义动作价值函数（或称Q函数）(简化版本，因为无状态)：

这里的期望是对奖励 R_t 的分布求平均。q^*(a) 表示选择动作 a 能够获得的平均奖励。由于多臂老虎机的平稳性，这个期望不依赖于时间 t，所以我们直接用 q^*(a) 而不带时间下标。

我们的最终目标也就是希望求得所有动作的真实价值 q^*(a)，这样我们直接看动作价值表，就可以知道那个动作带来的收益最大，那我们的策略就是一直选择这个收益最大的动作，多臂老虎机问题就完全解决了。具体来说，最优动作 a^* ：

这个策略保证了每次都选择期望奖励最高的臂，从而最大化长期累积奖励。但在实际中，q^*(a) 是未知的，我们需要通过与环境交互来估计 Q_t(a) 以近似 q^*(a) ，这就是多臂老虎机算法要解决的核心问题。

动作价值函数和状态价值函数的区别

• 状态价值函数 V^{\pi}(s)：评估在状态 s 有多好
• 动作价值函数 q^{\pi}(s,a)：评估在状态 s 选择动作 a 有多好

我们举一个例子，假设正在玩游戏，当前在某个位置（状态 s），有3个动作可选：

状态价值函数会告诉我们，如果继续按照当前策略（比如70%向左，20%向右，10%向上）来玩，那么这个位置的期望价值是

动作价值函数会告诉我们，在这个位置，向左走价值+10，向右走价值-5，向上走价值+3

这么看来，动作价值函数比状态价值函数直观的多，这也就是为什么后续算法都偏向直接使用动作价值函数。

估计动作价值的两种策略

在时刻 t，我们通过 t 时刻前的交互得到了对每个动作价值的估计 Q_t(a)，这个估计是对真实值 q^*(a) 的近似。就好比上面的例子，我们有了q(s, a)，我们下面有一个很关键的问题，到底选择哪个动作？有两种策略。

第一种策略是贪心行为（exploitation）：选择当前估计值最大的动作（选+10）。具体来说，时刻 t 的动作选择为：

这种策略的逻辑是利用已有的信息，选择目前看起来最好的动作来获取即时收益。但问题在于，Q_t(a) 只是对真实值的估计值，它可能并不准确。万一他只是这次凑巧价值很高呢？万一还有更好动作没有被充分发掘，被埋没了呢？因此如果我们一直选择当前看起来最好的动作，就永远不会去尝试其他动作，也就无法发现是否存在更好的选项。

第二种策略是探索（exploration）：选择当前估计值不是最大的动作。数学上表示为：

探索的目的是把其他动作都尝试一下，以收集更多信息，改进对各个动作价值的估计。可能会找到真实价值比我们估计的要高的动作，从而找到更优的选择。

探索与利用的权衡

这两种策略构成了强化学习中的经典问题：探索-利用权衡（exploration-exploitation tradeoff）。如果只进行利用，我们会陷入局部最优，可能错过真正的最佳动作。如果只进行探索，我们会不断尝试新动作而无法充分利用已知的好动作来获取收益。因此必须在两者之间找到平衡。这个平衡问题在试验次数有限时尤为关键，因为我们没有无限的时间来探索所有可能性，必须在有限的交互中既要学习又要获取尽可能高的累积奖励。

后悔值的定义

为了量化算法的性能，我们定义后悔值（regret）这个概念。假设总共进行 N 次试验，后悔值定义为：

• N \max_a q^*(a)：如果每次都选真实最优动作，N 次能得到的总奖励
• \sum_{t=1}^N r_t：我们实际得到的总奖励
• \rho：因为不知道最优动作，需要探索，损失了多少奖励

后悔值越小，说明算法越接近理想情况。但是注意，这个后悔值在学习过程中是无法计算的，因为我们我们并不知道真实的动作价值 q^*(a)，如果我们知道它，压根就不需要学习了，直接选择最优动作不就好了。因此后悔值是所有干完之后进行的衡量标准，换句话说，是用来比较不同算法的理论工具，比如说我们有两种算法，Q学习和DQN，都玩1000次老虎机，最后发现算法A的后悔值100远小于算法B的后悔值500，那么我们可以说算法A更好，因为它损失的奖励少

估计真实动作价值 q^*(a) 的方法

问题设定

我们前面说了，真实动作价值 q^*(a) 是未知的，因此我们用估计动作价值 Q_t(a) （通过和环境的交互）来近似真实值，这就是信号处理中经典的参数估计问题，我们假设样本是从某个真实分布中产生的，但这个真实分布是未知的，所以我们只能用估计分布去逼近真实分布，因此有了众多常用的参数估计方法，比如均值估计等，这里的核心思想类似

假设到目前为止已经进行了 T 次试验（或称为回合、episode）。在这 T 次试验中，我们记录了每次选择的动作 a_t 以及相应获得的奖励 r_t，其中 t = 1, 2, \ldots, T。下面我们利用这些历史数据来估计每个动作的真实价值 q^*(a)

样本平均估计方法

一个自然的想法是使用样本平均：对于每个动作 a，将所有选择该动作时获得的奖励求平均。具体的估计公式为：

• 分子 \sum_{t=1}^T r_t \cdot \mathbb{1}_{a_t = a} 是指示函数加权的奖励总和。指示函数 \mathbb{1}_{a_t = a} 定义为：当 a_t = a 时取值1，否则取值0。因此分子实际上是遍历所有时刻 t，只累加那些选择了动作 a 的时刻对应的奖励。

• 分母 \sum_{t=1}^T \mathbb{1}_{a_t = a} 同样使用指示函数，它统计的是动作 a 被选择的总次数。遍历所有时刻，每当 a_t = a 就计数加1，最终得到动作 a 的选择次数。

将分子除以分母，就得到了选择动作 a 时的平均奖励，这是对 q^*(a) 的一个无偏估计。根据大数定律，当动作 a 被选择的次数趋于无穷时，Q_t(a) 会收敛到真实值 q^*(a)​。

证明: Q_t(a) 是对 q^*(a) 的无偏估计

即证:

我们有:

简化记号，设动作 a 被选择了 N 次，对应的奖励样本为 \{r_1^{(a)}, r_2^{(a)}, ..., r_N^{(a)}\}，则：

对估计器取期望：

由于我们目前做的是老虎机简化情况，因此无记忆，奖励只取决于当前动作，和时间无关，因此每次选择动作 a 时，奖励 r_i^{(a)} 都是从同一个分布（比如70%概率给5元，30%概率给10元）中独立（每次奖励互不影响）抽取的：

因此每个样本的期望都相同：

因此原公式等于:

证毕

初始化

在算法开始之前，我们需要设定初始估计值。通常将所有动作的估计值初始化为0：

这个初始化不预先假设哪个动作更好。随着试验的进行，Q_t(a) 会根据观察到的奖励逐步更新，越来越接近真实值。

估计值的收敛性

由于环境是平稳的，我们可以利用大数定律来分析估计值的收敛性。当总试验次数 T 趋于无穷时，a 动作被选择的总频率为

这个极限意味着在无穷次试验中，任何特定动作被选择的比例会趋于某个固定值。结合大数定律，当某个动作 a 被选择的次数趋于无穷时，该动作的样本平均奖励会收敛到真实期望：

因此样本平均方法是无偏+收敛估计，前提是每个动作都被探索足够多次（选择频率 > 0）

存储问题及其解决

使用上述样本平均公式存在一个实际问题：为了计算 Q_t(a)，我们需要存储从开始到时刻 t 的所有动作和奖励历史。随着时间增长，存储需求线性增加，这在长时间运行的系统中是不可行的。

为了解决这个问题，我们推导一个增量更新公式。假设动作 a 在时间段 t=1 到 t=T 之间都被选择（化简假设，因此 a 被选择的次数为 T ）。此时的估计值为：

现在假设在时刻 T+1，我们再次选择了动作 a，即 a_{T+1} = a，并获得奖励 r_{T+1}。新的估计值应该是：

增量更新公式的推导

我们可以将新估计值改写为：

注意到 \sum_{t=1}^T r_t = T Q_T(a)，代入得：

继续展开：

简化后得到增量更新公式：

新估计值 = 旧估计值 + 修正量。修正项的大小由预测误差 (r_{T+1} - Q_T(a)) 决定。

当预测误差为正，即 r_{T+1} > Q_T(a) 时，说明这次实际得到的奖励超出了我们的预期，表明我们之前对这个动作的估计过于保守，低估了它的真实价值。因此我们需要向上调整估计值，让 Q_{T+1}(a) 比 Q_T(a) 更大一些。反之，当预测误差为负时，说明实际奖励不如预期，我们之前高估了这个动作，需要向下调整。

学习率 \frac{1}{T+1} 随着选择动作 a 的次数 T 增加而递减，意味着随着我们收集更多数据，每个新样本对估计值的影响逐渐减小。因为当我们刚开始探索时，只有很少的样本，每个新观察都包含大量新信息，应该对估计值产生较大影响。比如第一次选择动作 a（T=0），学习率是 \frac{1}{1}=1，此时新观察到的奖励 r_1 会完全决定 Q_1(a)，但随着我们积累了越来越多的经验，比如已经选择了100次，新的第101次观察只是众多样本中的一个，它不应该过度扭曲我们基于前100次形成的认知。此时学习率变成 \frac{1}{101} \approx 0.01，新样本只能轻微调整估计值。这种递减机制使得估计值在后期更加稳定，避免异常值带来的剧烈波动

使用这个增量公式，我们只需要存储当前的 Q_T(a) 和选择次数 T，无需保存全部历史数据，大大降低了存储需求。

增量更新公式的实际应用

我们之前是简化假设，假设到时刻 T 为止，动作 a 都被选择，但是实际中 a 不一定在每个时间点都别选择，我们假设到时刻 T 为止，动作 a 被选择了 N_T(a) 次。

当我们进入时刻 T+1 时，需要根据实际选择的动作进行不同的处理。如果在时刻 T+1 选择的是动作 a，那么需要更新两个量：

第一个式子将动作 a 的选择次数加1。第二个式子使用增量公式更新估计值，学习率是 \frac{1}{N_{T+1}(a)}。

如果在时刻 T+1 选择的不是动作 a（即选择了其他动作），那么动作 a 的相关信息保持不变：

这是因为我们没有获得关于动作 a 的新信息，无法更新它的估计值。这种条件更新机制确保了每个动作的估计值只在被实际选择时才会改变。通过更新每个动作的选择次数 N_T(a) 和当前估计值 Q_T(a) 这两个变量，我们就可以高效地实现样本平均估计，而不需要存储完整的历史数据。

贪心策略

贪心策略是最简单的动作选择方法。在每个时刻 t，它选择当前估计值最大的动作：

这个策略完全基于利用：总是选择目前看起来最好的动作，不进行任何探索。但这种策略存在一个严重问题：当试验次数 t \to \infty 时，后悔值的极限不是0。换句话说，即使我们进行无限多次试验，我们的估计值 Q_T(a) 不会收敛到真实值 q^*(a) 。因为贪心策略可能在早期就锁定在某个次优动作上。假设真正的最优动作在前几次试验中恰好给出了较低的奖励，而某个次优动作给出了较高的奖励。贪心策略会认为这个次优动作是最好的，并在后续一直选择它，永远不会去尝试其他动作，也就无法发现真正的最优动作。这导致每次选择都损失了一定的奖励，长期累积下来后悔值会线性增长。

ε-贪心策略

为了解决纯贪心策略的问题，我们引入ε-贪心策略。这个策略在利用和探索之间建立了一个平衡机制。

在每个时刻 t，ε-贪心策略采用如下规则：

• 以概率 1-\varepsilon 选择当前估计值最大的动作 (利用，选择当前看起来最好的动作来获取高奖励)：

  a_t \in \arg\max_a Q_t(a)

• 以概率 \varepsilon 从动作空间 \mathcal{A} 中随机均匀选择一个动作。这部分是探索，给所有动作一个被尝试的机会，避免过早陷入局部最优。

参数 \varepsilon \in [0,1] 控制了探索和利用的比例。当 \varepsilon = 0 时，策略退化为纯贪心策略，完全不探索。当 \varepsilon = 1 时，策略变成完全随机选择，不利用任何已学到的信息。实际应用中，\varepsilon 通常取一个较小的值（如0.1或0.05），保证在大部分时候利用当前最优动作，同时偶尔探索其他动作。通过这种随机探索，ε-贪心策略能够确保每个动作都有机会被选择无限多次，从而最终找到真正的最优动作。

ε-贪心策略的局限性

虽然ε-贪心策略解决了纯贪心策略的收敛问题，但它仍然存在一个缺陷：如果 \varepsilon > 0 ，那么当试验次数 t \to \infty 时，后悔值 \rho 仍然不会趋于0。

原因在于：即使经过长时间学习，我们已经准确估计出了每个动作的真实价值，知道了哪个动作是最优的，但ε-贪心策略仍然会以概率 \varepsilon 去选择非最优动作。这意味着即使在后期，我们依然会持续犯错，每次选择次优动作都会产生后悔。由于这种探索永远不会停止，后悔值会以线性速率持续累积，无法收敛到0。

ε随时间递减的策略

为了解决这个问题，一个自然的想法是让 \varepsilon 随着时间 t 递减。当我们积累了足够多的经验，对各个动作的价值有了较准确的估计后，就应该减少探索的频率，更多地利用已学到的知识。通过让 \varepsilon 逐渐趋于0，我们可以在后期几乎总是选择最优动作，从而使后悔值的增长速度逐渐减缓。这就是ε-first策略

ε-first策略

ε-first策略假设我们总共允许进行 T 个回合（episodes），并将这 T 个回合分为两个阶段。

在前 \varepsilon T 个回合中（探索阶段），智能体完全进行探索：从动作空间中均匀随机选择动作。这个阶段的目的是充分收集每个动作的信息，建立对各动作价值的初步估计。由于是均匀随机选择，每个动作都有相同的机会被尝试，保证了探索的全面性。

在剩下的 (1-\varepsilon)T 个回合中（利用阶段），智能体完全贪心地行动：每次都选择当前估计值最大的动作。此时探索阶段已经结束，我们基于前期收集的数据确定了最优动作（至少是估计的最优动作），然后在剩余时间里一直利用这个动作来最大化收益。

这种策略的优点是简单明确，将探索和利用严格分离。缺点是过于僵化：探索阶段完全不利用已有信息，利用阶段完全不探索，而且需要事先知道总回合数 T 来规划两个阶段的长度。

置信上界（UCB）策略

置信上界策略提供了一种更智能的方法来平衡探索和利用。与ε-贪心策略的随机探索不同，UCB策略通过量化每个动作估计值的不确定性，系统地选择具有潜在最优可能性的动作。

在时刻 t，UCB策略选择如下动作：

这个公式包含两部分。

• 第一部分 Q_t(a) 是动作 a 的当前估计值，代表了利用成分：选择目前看起来好的动作。
• 第二部分 c\sqrt{\frac{\ln t}{N_t(a)}} 是置信区间的宽度，代表了探索成分：鼓励选择那些被尝试次数较少、估计不确定性较高的动作。

不确定性项的含义

第二项 c\sqrt{\frac{\ln t}{N_t(a)}} 量化了我们对动作 a 价值估计的不确定性。这个不确定性与 \frac{1}{\sqrt{N_t(a)}} 成正比。当动作 a 被选择的次数 N_t(a) 很少时，这一项会很大，使得该动作的总得分（估计值加上不确定性）可能很高，从而被选中。这相当于给那些信息不足的动作一个"乐观"的评价，假设它们可能是最优的。

随着某个动作被选择的次数增多，N_t(a) 增大，不确定性项 \sqrt{\frac{\ln t}{N_t(a)}} 会减小。这意味着我们对该动作的估计越来越有信心，探索的必要性降低。同时，分子中的 \ln t 随总时间步增长，但增长速度很慢，这保证了即使在后期，如果某个动作长期未被选择，它仍然有机会被重新考虑。

参数 c 用于调节探索的强度。较大的 c 会使不确定性项占更大比重，鼓励更多探索；较小的 c 则更偏向利用当前最优动作。UCB策略的优势在于它不需要像ε-贪心那样进行随机选择，而是根据每个动作的估计值和不确定性做出确定性的、有原则的选择，从而在理论上能够达到更好的后悔值界限。

多臂老虎机算法的完整实现

现在我们将前面讨论的各个组件整合成一个完整的算法。算法分为初始化和主循环两个部分。

初始化阶段

对于动作空间中的每个动作 a \in \mathcal{A}，我们需要初始化两个量：

选择次数 N(a) 初始化为0，表示还没有尝试过任何动作。估计值 Q(a) 有两种初始化方式。第一种是初始化为0，这是中性的初始化，不对任何动作有偏好。第二种是初始化为一个较大的值 Q_0，这种方式称为乐观初始化。

补充: 乐观初始化

乐观初始化意味着我们给每个动作一个很高的初始估计值。如果初始值 Q_0 大于所有动作的真实价值 q^*(a)，即满足 Q_0 > q^*(a), \forall a \in \mathcal{A}，那么这种初始化会鼓励探索。

因为当所有动作的估计值都很高时，贪心策略会倾向于尝试不同的动作。一旦某个动作被选择，它的真实奖励（通常低于 Q_0）会将估计值向下拉，使得其他未被充分探索的动作（仍然保持高估计值）在下一轮更有可能被选中。这样，算法会自然地在早期阶段遍历所有动作，而不需要额外的探索机制。

主循环

从时刻 t=1 到 T，算法重复以下步骤。首先应用ε-贪心策略或其他探索策略来选择动作。如果使用ε-贪心策略，具体流程是：从 [0,1] 区间均匀随机抽取一个数 \rho。如果 \rho < 1-\varepsilon，则贪心地选择：

否则从动作空间 \mathcal{A} 中均匀随机选择一个动作。

更新步骤

选定动作 a_t 后，执行该动作并从环境获得奖励：

这里 \text{bandit}(a_t) 表示多臂老虎机系统返回的奖励，这是一个随机变量。接下来更新该动作的统计信息：

第一个更新将动作 a_t 的选择次数加1。第二个更新使用增量公式修正估计值，将新观察到的奖励 r_t 融入到当前估计中。这个过程不断重复，直到完成 T 轮试验。通过这种系统化的探索和利用，算法能够逐步学习每个动作的真实价值，并收敛到最优策略。

马尔可夫决策过程（MDP）

这一章节内容可以看作是多臂老虎机加上状态的扩展，但是加入状态后问题难度大幅度上升，但是分析思路是基本不变且很多内容重复的

从多臂老虎机到MDP

回顾多臂老虎机问题，我们面对的是一个极度简化的场景：智能体每次只需要从 K 个动作中选一个，观察到奖励，然后重复这个过程。关键的简化在于两点：第一，不存在状态的概念，或者说只有一个固定不变的状态；第二，每次选择是完全独立的，当前的选择不会影响未来面临的选择。这种独立性使得问题变得简单。我们的目标只是找到期望奖励最高的那个动作 a^* = \arg\max_a q^*(a)，然后一直选它就行了。

现在考虑一个更现实的场景：机器人在迷宫中导航。机器人在不同的位置（状态）面临不同的选择，同样是"向右走"这个动作，在迷宫入口执行和在接近出口执行，后果完全不同。更重要的是，当前的动作会改变机器人所处的位置，从而影响下一步可以做什么选择、会获得什么奖励。

这就是状态的引入带来的核心变化：当前的决策会影响未来所处的环境，进而影响未来的奖励和可选动作。

MDP的形式化定义

MDP中的三个核心变量：

• S_t \in \mathcal{S} 表示时刻 t 的状态，它属于状态空间 \mathcal{S}。
• R_t \in \mathcal{R}(S_t) \subset \mathbb{R} ，它评价当前状态的即时收益
• A_t \in \mathcal{A}(S_t) 表示时刻 t 选择的动作，它属于动作空间，这个空间也可能随状态变化。

在时刻 t，智能体观察到状态 S_t，根据这个状态选择动作 A_t，环境响应这个动作产生即时奖励 R_{t+1} 并转移到新状态 S_{t+1}。这个新状态又成为下一轮决策的起点，如此循环往复。这个循环结构是MDP的核心特征。

有限MDP的假设

我们考虑有限MDP，这意味着状态空间 \mathcal{S} 和动作空间 \mathcal{A}(S) 都是有限集合，即它们包含的元素个数是有限的。此外，为了简化记号，我们假设奖励空间 \mathcal{R}(s) 对所有状态都是有限的。这些有限性假设虽然限制了模型的一般性，但使得理论分析和算法实现都更加可行。

马尔可夫性质

MDP的核心假设是环境满足马尔可夫性质。马尔可夫性质是指环境的演化（动力学）可以用一个条件概率分布来描述：

这个条件概率描述了在状态 s 下执行动作 a 后，转移到状态 s' 并获得奖励 r 的可能性。马尔可夫性质的关键在于：这个转移概率只依赖于当前状态-动作对 (s,a)，而不依赖于历史上更早的状态或动作。换句话说，当前状态 S_t 已经包含了预测未来所需的全部信息，历史如何到达这个状态并不重要。这就像下棋时，你只需要看当前的棋盘布局就能决定下一步怎么走，不需要回忆前面50步是怎么走的。

这个无记忆性极大地简化了问题。如果没有马尔可夫性质，我们就需要考虑整个历史轨迹，状态空间会呈指数爆炸。马尔可夫性质允许我们只关注当前状态，把复杂的历史压缩到一个有限维度的表示中。

马尔可夫决策过程的状态转移机制

在马尔可夫决策过程中，我们首先要理解系统是如何运作的。想象你正在控制一个机器人，这个机器人当前处于某个状态（比如在房间的某个位置），你给它下达一个指令（动作），然后两件事会同时发生：机器人会移动到一个新的位置（新状态），并且会收到一个反馈信号（奖励，可能是正的表示好，负的表示不好）。整个过程是随机的，也就是说，即使你在相同的位置下达相同的指令，机器人也可能因为各种不确定因素而到达不同的位置。

这个随机过程由一个核心函数来刻画：

这个函数告诉我们：当智能体在 t 时刻位于状态 s，并且执行了动作 a 之后，系统转移到状态 s' 并且同时获得奖励 r 的概率是多少。注意这是一个联合概率分布，它同时描述了"状态会变成什么"和"会得到什么奖励"这两个随机事件。为什么要联合描述呢？因为在真实环境中，状态的转移和奖励的产生往往是相互关联的，比如机器人走到危险区域（状态转移）的同时就会受到惩罚（负奖励）。

这里要注意，一定要用概率来描述状态的转移。举一个例子，控制一个扫地机器人，机器人现在在客厅中央（状态 s），给它下达指令"向前走1米"（动作 a）。理论上来讲，既然我明确告诉它向前走1米，那它就应该确定地到达客厅中央前方1米处这个位置（状态 s'），但是现实中，由于不确定性存在，机器人走到了前方1米处的概率只有80%，可能因为地板太滑，只走了0.9米就打滑了（概率15%），或者因为轮子卡到地毯边缘，偏离方向走到了斜前方0.95米处（概率5%）。

用概率语言描述就是：

• P(s'=\text{前方1米}, r=0 | s=\text{中央}, a=\text{前进}) = 0.8
• P(s'=\text{前方0.9米}, r=0 | s=\text{中央}, a=\text{前进}) = 0.15
• P(s'=\text{斜前方0.95米}, r=0 | s=\text{中央}, a=\text{前进}) = 0.05

因此

从这个完整的联合分布出发，我们可以提取出两个有用的边缘信息。第一个是纯粹的状态转移概率，如果我们只关心"状态会变成什么"而不在乎具体得到多少奖励，那么就把所有可能的奖励值加起来：

这个求和的意思是：如果我只关心状态会转移到 s'，而不在乎具体得到多少奖励，那么这个转移发生的总概率是多少？

回到机器人例子。假设机器人在客厅中央执行"前进"动作，联合分布可能是：

• P(s'=\text{前方1米}, r=0 | s,a) = 0.70（顺利前进，无奖励）
• P(s'=\text{前方1米}, r=+5 | s,a) = 0.10（前进且捡到硬币，正奖励）
• P(s'=\text{前方0.9米}, r=0 | s,a) = 0.15（打滑）
• P(s'=\text{斜前方}, r=-2 | s,a) = 0.05（偏离，负奖励）

现在我只想知道"到达前方1米处"的总概率，不管有没有捡到硬币。那就把所有终点是"前方1米"的情况加起来：

这就是状态转移概率。它告诉我们：执行这个动作后，有80%的概率最终位置是前方1米，至于这80%里面有多少次会捡到硬币，我们不关心。

第二个提取出的信息是期望奖励，也就是在状态 s 执行动作 a 平均能得到多少奖励：

这个公式回答的问题是：在状态 s 执行动作 a，平均来说我能获得多少奖励？

我们遍历所有可能的"下一状态-奖励"组合 (s',r)，每个组合都有一定的概率 P(s',r|s,a) 发生，发生时我们会得到奖励 r。把每个可能的奖励乘以它的概率，然后全部加起来，就得到了期望奖励。

继续用上面的机器人例子：

• P(s'=\text{前方1米}, r=0 | s,a) = 0.70，奖励为0
• P(s'=\text{前方1米}, r=+5 | s,a) = 0.10，奖励为+5
• P(s'=\text{前方0.9米}, r=0 | s,a) = 0.15，奖励为0
• P(s'=\text{斜前方}, r=-2 | s,a) = 0.05，奖励为-2

计算期望奖励：

这意味着：如果我在这个状态执行这个动作，虽然每次的具体奖励可能不同（可能是0、可能是+5、可能是-2），但长期平均下来，每次执行这个动作期望能获得0.4的奖励。

片段式任务

在强化学习中，有些任务是有明确结束时刻的，我们称之为片段式任务。比如下一盘棋，总会有输赢或和棋的时刻；玩一局游戏，总会有游戏结束的画面；机器人完成一次搬运任务，总会有成功或失败的终点。这类任务的交互不是无限延续的，而是在某个时间步 T 就会终止。这个终止时刻 T 通常不是固定的，而是随机的，取决于交互过程中发生了什么（比如输的快，那么 T 就小）。

对于这类任务，我们定义从时刻 t 开始的回报（Return）为：

回报就是从当前时刻到任务结束这段时间内，所有获得的奖励的总和。这个定义非常直观：我们关心的不是某一步得到的单个奖励，而是整个任务过程中累积的总收益。因为任务会在 T 时刻结束，所以这是一个有限的求和，不会出现无穷大的问题。这里没有引入任何折扣，所有的奖励都是等权重的，无论它是在第 t+1 步获得的还是在最后的第 T 步获得的，对总回报的贡献都是一样的。

持续式任务与折扣机制

与片段式任务相对的是持续式任务，这类任务没有自然的终点，理论上可以永远进行下去。比如一个自动温度调节系统，它需要持续不断地工作来维持室温；或者一个股票交易系统，它可以一直进行交易决策。对于这类任务，如果我们还是简单地把所有未来奖励相加来定义回报：

会遇到一个严重的问题：这个无穷级数可能会发散到无穷大。如果每一步都能获得哪怕很小的正奖励，累加无穷多步后回报就会是无穷大；如果奖励有正有负但不收敛，回报可能也没有定义。这样的回报无法用来指导优化，因为无法比较两个都是无穷大的回报谁更好。

为了解决这个问题，我们引入折扣因子 \gamma，它是一个介于0和1之间的数（\gamma \in [0,1)）。折扣因子的作用是给未来的奖励打折扣，距离当前时刻越远的奖励，在计算回报时权重越小。具体来说，回报的定义变为：

在这个公式中，k 步之后获得的奖励 R_{t+k+1} 被乘以了 \gamma^k。当 k 增大时，\gamma^k 会指数级衰减（因为 \gamma < 1），这意味着远期奖励对当前回报的影响越来越小。只要奖励序列是有界的（不会无限大），这个带折扣的无穷级数就能收敛到一个有限值。从另一个角度理解，折扣因子体现了一种"近视"偏好：我们更看重眼前的收益，而对遥远未来的收益打折扣。折扣率越大（\gamma 越接近1），我们就越有远见；折扣率越小（\gamma 越接近0），我们就越短视。

还是之前那个扫地机器人，现在它在客厅中央（时刻 t），任务是清扫整个房间。奖励设计如下：

• 每移动一步，消耗电量，奖励 -1（能耗成本）
• 清扫到脏的区域，奖励 +10（完成清洁）
• 撞到墙壁，奖励 -5（碰撞惩罚）

假设机器人需要执行5步才能完成清扫：走到脏区域（3步）→ 清扫 → 返回充电桩（1步）。完整的回报是：

回报的时间递归性质

观察持续式MDP的回报定义，我们可以发现一个非常重要的数学性质。将回报的无穷级数展开并重新组合：

现在我们把第一项单独提出来，把剩余的项提取公因子 \gamma：

仔细观察括号里的部分，它的形式是 R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \cdots，这恰好就是从 t+1 时刻开始的回报 G_{t+1} 的定义。因此我们得到了一个简洁的递归关系：

这个递归关系揭示了：当前时刻的回报可以分解成两部分。第一部分是立即奖励 R_{t+1}，这是执行下一步动作后马上能获得的, 第二部分是折扣后的未来回报 \gamma G_{t+1}，这代表了从下一时刻往后的所有收益，但因为是"未来的"所以要打折扣。这个递归形式在强化学习中极其重要，因为它把一个涉及无穷未来的量（G_t）和一个同样涉及无穷未来的量（G_{t+1}）联系了起来，使得我们可以通过动态规划的思想来递推求解，而不需要真的去展开整个无穷级数。

机器人在客厅中央（t=0 时刻），它即将：

1. 执行下一步：向前走一步，产生立即奖励 R_1 = -1（消耗电量）
2. 面对剩余任务：走这一步后，机器人到达新位置（t=1 时刻），从那里开始还要继续完成剩余的清扫任务，这部分的未来收益是 G_1

所以当前的总回报分解为：

统一处理片段式任务的技巧

前面我们分别讨论了片段式和持续式MDP，它们的回报定义看起来不太一样。为了在理论推导和算法实现中能够统一处理这两种情况，我们采用一个巧妙的方法：在片段式MDP的状态空间中增加一个特殊的"终止状态"。

具体来说，假设原来的状态空间是 S_0，我们把它扩展为 S = S_0 \cup \{\text{Terminal}\}，其中Terminal是新增的终止状态。这个终止状态有一个特殊的性质：一旦进入它，系统就永远停留在这个状态，无论执行什么动作都无法离开，并且在终止状态中获得的奖励永远是0。

为什么要这样设计呢？通过引入终止状态，原本会"结束"的片段式任务现在可以被看作是"持续"的，只不过在任务自然结束后，系统进入了终止状态并在那里无限循环。因为终止状态的奖励是0，所以即使我们用无穷级数 \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} 来定义回报，在到达终止状态后，所有后续的项都是0，实际的回报还是有限的，等价于原来的有限求和 R_{t+1} + \cdots + R_T​。这种处理方式的好处是，我们可以用同一套数学框架（同一个回报公式、同一套方程）来处理片段式和持续式两类问题，大大简化了理论分析和算法设计。

扫地机器人完成清扫并返回充电桩后，任务就结束了。现实中它会停在充电桩上，不再移动。这是一个片段式任务。那么把充电桩定义为终止状态 s_{\text{terminal}}。机器人一旦到达充电桩，就永远停留在那里，无论给它下达什么指令，它都不会离开，即

与此同时，机器人在充电桩上"待机"时，不产生任何奖励或惩罚，不消耗电量（已充电），不清扫（任务完成），不移动（静止），即 R_t = 0（当 S_t = s_{\text{充电桩}}​）

回报定义的统一表示

基于前面的讨论，我们现在可以给出一个统一的回报公式，它同时适用于片段式和持续式MDP：

这里折扣因子 \gamma 的取值范围是 [0,1]。这个统一公式之所以能覆盖两种情况，关键在于对 \gamma 的灵活使用。

• 对于持续式MDP，我们必须让 \gamma 严格小于1（\gamma \in [0,1)），这样无穷级数才能收敛
• 对于片段式MDP，因为任务会在有限步 T 后终止（进入终止状态后奖励都是0），所以即使设 \gamma = 1 也没问题，此时回报就退化为简单的有限和。

当然，片段式MDP也完全可以使用 \gamma < 1，这在某些情况下是有意义的，比如我们希望尽快完成任务，那么引入折扣会让智能体倾向于获得近期的奖励，从而加快任务完成的速度。

有了这个统一的回报定义，我们在后续的推导中就不需要再分别讨论片段式和持续式两种情况了。所有的价值函数、贝尔曼方程、优化算法都可以基于这个统一的回报公式来建立，这极大地简化了理论体系，也让算法实现更加优雅。

机器人的回报变成：

从第5项开始全是0，所以：

策略的数学定义

在MDP框架下，智能体需要一个决策规则来指导它如何行动，这个决策规则就叫做策略（Policy）。策略 \pi 本质上是一个条件概率分布，它描述了在每个状态下应该以多大的概率选择各个动作。数学上，我们要求对于任何状态 s 和该状态下的任何可行动作 a \in A(s)，策略给出的概率必须是非负的：

这里需要注意，不同的状态可能有不同的可行动作集合 A(s)。比如在棋盘游戏中，不同的棋面状态下走法是不同的。策略只需要为可行动作分配概率，对于不可行的动作可以不定义或定义为0。

作为一个概率分布，策略还必须满足归一化条件：

这个条件确保了在任何状态 s 下，所有可行动作被选中的概率加起来等于1。这是概率的基本要求：智能体总得做点什么，不可能什么动作都不选。这两个条件（非负性和归一化）共同定义了随机策略的概念。随机策略允许智能体以一定的概率"掷骰子"来决定行动，这在探索未知环境时是很有用的，因为固定选择某一个动作可能会让智能体陷入局部最优，而随机尝试不同的动作能够发现更多的可能性。

扫地机器人在房间里移动时，每到一个位置（状态）都需要决定下一步做什么（动作）。策略 \pi 就是机器人的"大脑"，它告诉机器人在每个状态应该如何选择动作。

假设扫地机器人现在在客厅中央这个状态 s_1。它可以执行4个动作：

• a_1：向前
• a_2：向后
• a_3：向左
• a_4：向右

一个随机策略可能是这样的：

这意味着：机器人在客厅中央时，有50%的概率选择向前，20%的概率向后，20%的概率向左，10%的概率向右。每次到达这个位置，机器人会抛骰子，根据这些概率随机决定方向。

非负性就不说了，归一化的数学表达就是

关键的一点是：策略在不同状态下可以完全不同。

场景1：机器人在客厅中央（前面已经定义过）

场景2：机器人在墙角
假设机器人走到了房间的西北角，它的左边和后边都是墙。这时可行动作集合变了：\mathcal{A}(s_{\text{墙角}}) = \{\text{向前}, \text{向右}\}（不能向后或向左，会撞墙），策略可能变成：

因此策略取决于状态，并且可以是随机的，当然也可以是确定的

确定性策略的简化表示

虽然一般的策略是随机的，但在很多情况下，最优策略其实是确定性的，也就是在给定状态下总是选择同一个固定的动作。对于这种特殊情况，我们不需要用概率分布来描述，而是可以用一个简单的映射关系：

策略 \pi 把状态 s 直接映射到一个具体的动作，这个动作属于状态 s 的可行动作集合。从随机策略的角度看，确定性策略相当于存在某个动作 a^* 使得 \pi(a^*|s) = 1，而其他所有动作的概率都是0。在这种情况下，写成 \pi(s) = a^*

确定性策略在理论分析中有很好的性质，比如对于很多MDP问题，如果存在最优策略，那么必然存在一个确定性的最优策略。

假设经过学习，机器人找到了最优清扫策略，它是确定性的：

• \pi(s_{\text{客厅中央}}) = \text{向前}（确定地向前，因为前方有脏区域）
• \pi(s_{\text{墙角}}) = \text{向右}（确定地向右，因为这是离开墙角的最优方向）
• \pi(s_{\text{脏区域前}}) = \text{向前}（确定地向前清扫）
• \pi(s_{\text{充电桩附近}}) = \text{向充电桩移动}（确定地返回充电）

确定性策略其实是随机策略的特例，用扫地机器人的例子，确定性策略"在客厅中央向前"对应的随机策略表示是：

为了书写简洁，我们就直接写 \pi(s_{\text{客厅中央}}) = \text{向前}，而不用写出完整的概率分布。

状态价值函数的定义与意义

有了策略的概念之后，我们需要一个工具来评估一个策略的好坏。状态价值函数（State Value Function）就是这样一个评估工具。对于一个给定的策略 \pi，状态 s 的价值定义为：

这个定义的含义是：假设MDP在时刻 t 恰好处于状态 s，如果从这一刻开始，我们一直按照策略 \pi 来选择动作，那么我们能够获得的回报的期望值是多少。

这里的期望 E_{\pi} 是对所有可能的未来轨迹求平均，因为未来会发生什么仍然是随机的，这种随机性来自两个方面：第一，策略本身可能是随机的（在同一状态下不同次可能选择不同的动作）；第二，环境的转移是随机的（执行同一动作可能到达不同的下一状态）。

将回报的定义代入，状态价值函数可以展开写为：

价值函数本质上是把一个复杂的、涉及整个未来的随机过程（未来的奖励序列）压缩成了一个单一的实数。这个数越大，说明从状态 s 开始按策略 \pi 行动的前景越好。价值函数为我们提供了一个量化的指标来比较不同状态的好坏，也为比较不同策略提供了基础：如果策略 \pi_1 在每个状态的价值都不低于策略 \pi_2（即 V_{\pi_1}(s) \geq V_{\pi_2}(s) 对所有 s 成立），那么 \pi_1 就是更好的策略。

扫地机器人的具体场景，假设房间有以下几个位置（状态）：

• s_1：客厅中央
• s_2：脏区域附近
• s_3：墙角
• s_4：充电桩附近
• s_5：充电桩（终止状态）

机器人的策略 \pi 是：

• 在客厅中央：80%向前（朝脏区域），20%随机探索
• 在脏区域附近：90%清扫，10%随机
• 在墙角：60%向出口移动，40%随机
• 在充电桩附近：100%返回充电桩

奖励设置：

• 每移动一步：-1（电量消耗）
• 清扫脏区域：+50
• 到达充电桩：+20
• 撞墙：-5

现在我们计算 V_\pi(s_1)，即"机器人在客厅中央这个位置的价值"。价值函数是一个期望值，这个期望对所有可能的未来轨迹求平均。为什么会有多种可能的未来轨迹？因为存在两种随机性。

随机性来源1：策略本身是随机的

机器人在客厅中央按照策略 \pi，有80%概率向前，20%概率随机探索（可能向后、向左、向右）。

轨迹A（概率约80%）：

• 第1步：向前走到脏区域附近（s_1 \to s_2），奖励 R_1 = -1
• 第2步：清扫脏区域（s_2 \to s_4），奖励 R_2 = 50-1 = 49
• 第3步：返回充电桩（s_4 \to s_5），奖励 R_3 = 20-1 = 19
• 到达终止状态，后续奖励全为0

这条轨迹的回报（假设 \gamma=0.9）：

轨迹B（概率约5%）：
由于随机性，机器人可能向后走到墙角

• 第1步：向后走到墙角（s_1 \to s_3），奖励 R_1 = -1
• 第2步：在墙角挣扎，可能撞墙，奖励 R_2 = -5
• 第3步：终于离开墙角向脏区域（s_3 \to s_2），奖励 R_3 = -1
• 第4步：清扫脏区域（s_2 \to s_4），奖励 R_4 = 49
• 第5步：返回充电桩（s_4 \to s_5），奖励 R_5 = 19

这条轨迹的回报：

轨迹C、D、E...：还有很多其他可能的轨迹，每条轨迹都有不同的概率和不同的回报。

随机性来源2：环境转移是随机的

即使机器人执行相同的动作，环境的响应也可能不同（之前说的地板打滑、传感器误差等）。

比如机器人在客厅中央选择"向前"：

• 80%概率成功到达脏区域附近 s_2
• 15%概率打滑只前进一半，到达中间位置 s_6
• 5%概率偏离方向，到达其他位置

这进一步增加了未来轨迹的多样性。

状态价值函数 V_\pi(s_1) 就是对所有这些可能轨迹的回报进行加权平均：

假设计算出来 V_\pi(s_1) = 52.3。这个数字的含义是：机器人在客厅中央，按照策略 \pi 行动，平均能够获得52.3的回报。

动作价值函数的引入

状态价值函数告诉我们一个状态有多好，但它没有告诉我们应该采取什么动作。为了指导动作选择，我们需要一个更细的评估工具，那就是动作价值函数（Action Value Function），也常被称为Q函数：

与状态价值函数相比，动作价值函数多了一个参数 a，它回答的是一个更具体的问题：如果我们在状态 s 强制执行动作 a，然后从下一时刻开始按照策略 \pi 行动，期望能获得多少回报？这里的关键词是"强制执行"，意思是第一步的动作是我们指定的 a，不是由策略 \pi 随机选择的

动作价值函数提供的信息比状态价值函数更丰富。状态价值函数只告诉我们"这个状态有多好"，但没说"应该做什么"；而动作价值函数给出了状态下每个动作的具体价值，我们可以直接通过比较不同动作的Q值来做决策。也就是说：如果我们知道了 q_{\pi}(s,a) 对所有动作 a 的值，那么改进策略就很简单了，只要选择Q值最大的动作即可。这也是为什么Q-learning等很多强化学习算法都是基于动作价值函数而不是状态价值函数的原因。

扫地机器人在客厅中央（状态 s_1），有4个可选动作：

• a_1：向前（朝脏区域）
• a_2：向后
• a_3：向左
• a_4：向右

强制执行某动作

• q_\pi(s_1, a_1)：机器人在客厅中央，第一步强制向前，然后从下一步开始按策略 \pi 行动，能获得的期望回报

• q_\pi(s_1, a_2)：机器人在客厅中央，第一步强制向后（可能撞墙），然后从下一步开始按策略 \pi 行动，能获得的期望回报

**假设奖励设置：**每步-1，清扫+50，到充电桩+20，\gamma=0.9。

q_\pi(s_1, a_1)（向前）：

• 第1步强制向前到脏区域附近，R_1 = -1
• 第2步按策略清扫，R_2 = 49
• 第3步按策略返回充电桩，R_3 = 19
• 期望回报：q_\pi(s_1, a_1) \approx -1 + 0.9(49) + 0.81(19) = 58.5

q_\pi(s_1, a_2)（向后）：

• 第1步强制向后到墙角，R_1 = -1
• 第2步按策略挣扎，可能撞墙，R_2 = -5
• 后续慢慢走到脏区域...
• 期望回报：q_\pi(s_1, a_2) \approx 35.2（较差）

类似计算，可能得到 q_\pi(s_1, a_3) = 42.1，q_\pi(s_1, a_4) = 48.7

有了所有动作的Q值：

• q_\pi(s_1, a_1) = 58.5（向前）← 最大
• q_\pi(s_1, a_2) = 35.2（向后）
• q_\pi(s_1, a_3) = 42.1（向左）
• q_\pi(s_1, a_4) = 48.7（向右）

改进策略非常简单：选Q值最大的动作，即 a_1​（向前）。

状态价值与动作价值的内在联系

状态价值函数和动作价值函数不是孤立的，它们之间存在明确的数学关系。我们可以这样理解它们的联系：状态 s 的价值取决于在这个状态下我们会选择什么动作。如果策略是 \pi，那么我们会以概率 \pi(a|s) 选择动作 a，选择这个动作后能获得的期望回报是 q_{\pi}(s,a)。把所有可能的动作选择的情况加权平均，就得到了状态的总价值：

这个公式揭示了状态价值是动作价值的期望。如果我们把策略看作是一个"动作选择的概率分布"，那么状态价值就是在这个分布下动作价值的期望。这个关系可以帮助我们理解策略的质量：一个好的策略应该给高Q值的动作分配更大的概率。如果策略在某个状态下总是选择低Q值的动作，那么这个状态的价值就会被拉低，说明策略还有改进空间。

从另一个角度看，如果我们知道了所有的动作价值 q_{\pi}(s,a)，就可以通过这个公式计算出状态价值；反过来，如果我们知道了状态价值和环境动态，也可以推导出动作价值（后面会看到）。这种双向的联系是贝尔曼方程和动态规划方法的基础。

如果策略是随机的，比如在 s_1 处：

• 50%概率选 a_1（向前）
• 20%概率选 a_2（向后）
• 15%概率选 a_3（向左）
• 15%概率选 a_4（向右）

那么状态价值是所有动作价值的加权平均：

贝尔曼方程

现在我们来推导强化学习中最核心的方程：贝尔曼方程（Bellman Equation）。这个方程建立了当前状态价值与未来状态价值之间的递归关系，是动态规划方法的理论基础。

推导从状态价值函数的定义开始：

前面我们已经知道回报具有递归性质 G_t = R_{t+1} + \gamma G_{t+1}，现在我们利用这个性质，把它代入价值函数的定义：

这一步是整个推导的关键起点。通过这个代换，我们把对"整个未来回报"的期望，转化成了对"立即奖励加上折扣后的未来回报"的期望。由于期望算子是线性的，我们可以把这个期望拆成两部分：

现在问题变成了如何计算这两个期望。第一个是立即奖励的期望，第二个是未来回报的期望。我们需要分别对它们进行详细的推导。

立即奖励期望的展开

我们先处理立即奖励项 E_{\pi}(R_{t+1} | S_t = s)。要计算这个期望，我们需要理解奖励是如何产生的。在MDP中，给定当前状态 s，奖励的产生依赖于三个随机变量：我们选择的动作 A_t、转移到的下一状态 S_{t+1}，以及具体的奖励值 R_{t+1}。

按照条件期望的定义，我们对所有可能的奖励值 × 其概率加权求和：

这个公式就是离散随机变量期望的定义：

回到扫地机器人例子，它在客厅中央（状态 s_1），策略是：

• 60%向前
• 30%向左
• 10%向后

环境的随机性：

• 向前：80%成功（奖励-1），20%打滑撞墙（奖励-6）
• 向左：100%到墙边（奖励-1）
• 向后：100%撞墙（奖励-6）

从 s_1 出发，可能获得的奖励只有两种：

• r = -1（正常移动，消耗电量）
• r = -6（撞墙，消耗电量-1 + 撞墙惩罚-5）

获得 r=-1 的所有途径：

1. 选向前（60%）且成功（80%）：0.6 \times 0.8 = 0.48
2. 选向左（30%）且到墙边（100%）：0.3 \times 1.0 = 0.3

总概率：p(r=-1|S_t=s_1) = 0.48 + 0.3 = 0.78

获得 r=-6 的所有途径：

1. 选向前（60%）且打滑撞墙（20%）：0.6 \times 0.2 = 0.12
2. 选向后（10%）且撞墙（100%）：0.1 \times 1.0 = 0.1

总概率：p(r=-6|S_t=s_1) = 0.12 + 0.1 = 0.22

在 s 状态下获得奖励的期望是

机器人在客厅中央按策略行动，这一步平均会损失2.1的奖励（电量消耗+可能的撞墙惩罚）。

上一个公式 p(r|S_t=s) 的结果只告诉我们获得奖励 r 的总概率，我们现在把这个公式的中间变量（动作 a 和 状态 s'）都扩展出来，公式是不变的， 可见上面的例子，我们计算时也是考虑了不同动作的可能性和新状态来计算的最终奖励，只不过这里我们把公式细化一下

我们枚举所有可能的"动作-下一状态-奖励"三元组 (a, s', r)，每种组合都有一定的概率在给定 S_t=s 的条件下发生

我们继续上一个例子的状态动作转移情况，然后表达公式写成这个更细致的形式:

遍历所有可能的 (r, s', a) 组合：

求和得到期望

可见结果是相同的

接下来我们使用条件概率的链式法则来分解这个联合概率。在MDP中，动作选择和状态转移是有因果顺序的：首先根据策略 \pi(a|s) 选择动作 a，然后根据环境动态 p(r,s'|s,a) 确定下一状态和奖励。

因此联合概率可以分解为：

因此：

这个分解反映了MDP的结构：\pi(a|s) 是在状态 s 下选择动作 a 的概率（由策略决定），而 p(r,s'|s,a) 是执行动作 a 后转移到状态 s' 并获得奖励 r 的概率（由环境决定）。这两个因子是相互独立的

重新整理求和顺序，我们可以先对动作求和：

外层求和遍历所有可能的动作，每个动作以 \pi(a|s) 的概率被选中；内层求和计算在选定动作 a 后，该动作能带来的期望奖励（对所有可能的下一状态和奖励值求期望）。

回到扫地机器人例子

对于第一行，在状态 s_1 下，机器人有60%概率选择向前（\pi），在选择了向前之后有80%概率成功到脏区域 s' ，因此 策略选择该动作的概率 × 执行该动作后环境响应的概率 = 联合概率，再乘上对应的奖励 r ，就可以得到这个组合下的奖励期望，我们再遍历所有的组合，就可以得到总奖励期望

未来回报期望的推导

我们回到贝尔曼方程的价值函数推导结果:

我们上面已经干完了第一项期望，现在我们处理第二项，也就是未来回报的期望 E_{\pi}(G_{t+1} | S_t = s)。这一项更复杂，因为 G_{t+1} 代表了从下一时刻开始的整个未来，涉及的随机性更多。

未来回报 G_{t+1} 依赖于下一时刻的状态 S_{t+1}。如果我们知道了下一状态是 s'，那么从 s' 开始的期望回报恰好就是 V_{\pi}(s')（这是价值函数的定义）。但问题是我们现在还不知道会转移到哪个下一状态，所以需要对所有可能的下一状态求期望。

我们使用全期望公式（law of total expectation），引入下一状态和动作作为中间变量：

这里 g 代表未来回报的可能取值。我们对所有可能的"动作-下一状态-回报值"的组合求和。应用条件概率的链式法则：

用扫地机器人的例子来说，机器人在客厅中央 s_1，走一步后会到达某个新位置 S_{t+1}。从那个新位置开始的未来回报是 G_{t+1}。

• 如果我们知道下一位置是 s_2（脏区域附近）: 从 s_2 开始按策略行动的期望回报就是 V_\pi(s_2)（价值函数的定义）
• 如果我们知道下一位置是 s_3（墙边）: 从 s_3 开始的期望回报是 V_\pi(s_3)

问题是：现在还不知道会到哪里，需要对所有可能的下一位置求期望

情况1：选向前（60%），到脏区域 s_2（80%）

• 从 s_2 开始的未来回报是 G_{t+1}，它的期望值是 V_\pi(s_2)
• 这种情况的概率：0.6 \times 0.8 = 0.48
• 贡献：0.48 \times V_\pi(s_2)

情况2：选向前（60%），打滑到中间 s_6（20%）

• 从 s_6 开始的未来回报期望是 V_\pi(s_6)
• 概率：0.6 \times 0.2 = 0.12
• 贡献：0.12 \times V_\pi(s_6)

其他情况同理，把他们叠加起来，得到总的未来期望回报

现在的关键是要理解马尔可夫性质。给定当前状态 S_t=s 和当前动作 A_t=a，下一状态 S_{t+1} 的分布由环境的转移函数决定。一旦下一状态 S_{t+1}=s' 确定了，从 s' 往后的未来回报 G_{t+1} 的分布就只依赖于 s' 以及后续遵循的策略 \pi，而与之前的状态 s 和动作 a 无关了。这就是马尔可夫性质：未来只依赖于现在，不依赖于过去是怎么到达现在的。因此我们可以把联合概率分解为：

第一个因子 P(S_{t+1}=s'|S_t=s, A_t=a)：

• 机器人在 s_1 选择向前，到达 s_2 的概率
• 这由环境的转移函数决定，例如：80%到 s_2，20%到 s_6

第二个因子 P(G_{t+1}=g|S_{t+1}=s')：

• 一旦到达 s'，从那里开始的未来回报的分布
• 这只依赖于 s' 和策略 \pi，与之前的 s 和 a 无关（马尔可夫性质）

代入后得到：

现在我们重新整理求和的顺序。注意到关于 g 的求和可以单独提取出来：

括号内的部分 \sum_g g \cdot P(G_{t+1}=g | S_{t+1}=s') 是什么呢？这正是随机变量 G_{t+1} 在条件 S_{t+1}=s' 下的期望，也就是 E_{\pi}(G_{t+1} | S_{t+1}=s')。而根据价值函数的定义，这恰好等于 V_{\pi}(s')！

这是推导中最关键、最漂亮的一步：我们发现在计算当前状态的价值时，出现了未来状态的价值。价值函数在时间维度上呈现出自相似的递归结构。代入 V_{\pi}(s') 后：

这里的 P(S_{t+1}=s' | S_t=s, A_t=a) 是状态转移概率，它可以通过对所有可能的奖励进行边缘化得到：

代入得：

或者等价地写为：

这个式子的含义是：对于每个可能的动作 a（以概率 \pi(a|s) 选择），考虑该动作可能导致的所有"奖励-下一状态"组合 (r,s')（以概率 p(r,s'|s,a) 发生），下一状态的价值是 V_{\pi}(s')，把所有这些情况加权求和。

机器人在客厅中央 s_1，假设各状态价值：V_\pi(s_2)=60，V_\pi(s_6)=45，V_\pi(s_3)=40，V_\pi(s_1)=50

**动作1：**向前 ==> \pi(\text{向前}|s_1)=0.6

该动作贡献：0.6 \times 57.0 = 34.2

**动作2：**向左 ==> \pi(\text{向左}|s_1)=0.3

该动作贡献：0.3 \times 40.0 = 12.0

**动作3：**向后 ==> \pi(\text{向后}|s_1)=0.1

该动作贡献：0.1 \times 50.0 = 5.0

外层求和（所有动作）

贝尔曼方程的最终形式

现在我们可以把之前分别推导的立即奖励项和未来回报项合并起来了。回到最初的分解：

代入我们推导出的两个结果：

观察这两项，它们都有公共的求和结构 \sum_a \pi(a|s) \sum_{r,s'}，我们可以提取出来：

这就是状态价值函数的贝尔曼方程的最终形式。这个方程是：状态 s 的价值等于在该状态下按策略选择动作，每个动作会以一定概率导致某个"奖励-下一状态"组合，该组合的价值是立即奖励 r 加上折扣后的下一状态价值 \gamma V_{\pi}(s')，把所有可能性加权平均。

这个方程最重要的特点是它是一个递归方程：要计算 V_{\pi}(s)，我们需要知道 V_{\pi}(s')；而要计算 V_{\pi}(s')，又需要知道下一状态的价值。对于整个状态空间 S，每个状态 s \in S 都有一个这样的方程，因此贝尔曼方程构成了一个线性方程组，方程的个数等于状态的个数，未知数也是各个状态的价值。

贝尔曼方程的算子视角

为了更深入地理解贝尔曼方程的性质，我们可以从算子的角度来看待它。假设状态空间有 |S| 个状态，我们把所有状态的价值组织成一个列向量：

这个向量属于 |S| 维的实向量空间。现在我们定义一个算子 \underline{B}，它的作用是：给定一个价值向量 \underline{V}，计算出一个新的向量，新向量的第 s 个分量由贝尔曼方程的右端给出：

这个算子 \underline{B} 叫做贝尔曼算子。有了这个算子，贝尔曼方程可以简洁地写成：

这是一个不动点方程：真实的价值函数 \underline{V}_{\pi} 是贝尔曼算子 \underline{B} 的不动点，也就是说，把算子作用在真实价值上，得到的还是它自己。

这里本质上就是把每个状态分量合并成矩阵形式

然后 [\underline{B}(\underline{V})]_s 就是新价值的第 s 个分量，假设经过计算后得到下面结果

这个算子视角非常重要，因为它把求解贝尔曼方程的问题转化为了寻找不动点的问题。而不动点可以通过迭代的方法来逼近：我们从一个初始的价值估计 \underline{V}^{(0)} 开始，反复应用贝尔曼算子 \underline{V}^{(k+1)} = \underline{B}(\underline{V}^{(k)})，由于折扣因子 \gamma < 1，这个迭代序列会收敛到真实的价值函数 \underline{V}_{\pi}。这就是策略评估（Policy Evaluation）算法的理论基础，也是动态规划方法的核心思想。

通过这个推导，我们看到贝尔曼方程不仅仅是一个方程，它揭示了价值函数的深层结构：价值具有递归性、自相似性，当前的价值可以通过未来的价值来表达。这种结构使得我们不需要真的去模拟整个无穷的未来轨迹，而是可以通过有限次的局部计算（一步转移的期望）来递推求解全局的价值。这是强化学习能够高效求解的数学基础。

用备份图理解价值函数的计算

我们推导出了贝尔曼方程的数学形式。但数学公式有时候比较抽象，为了更直观地理解价值函数是如何计算的，我们可以使用一种叫做"备份图"的可视化工具。备份图用树状结构来展示价值计算的过程，每个节点代表一个状态或状态-动作对，每条边代表一种可能的转移或选择。

对于状态价值函数 V_{\pi}(s)，备份图的根节点是我们要评估的状态 s。从这个根节点出发，第一层的分支对应智能体可能选择的不同动作。因为智能体是按照策略 \pi 来选择动作的，所以每条边都带有一个权重，这个权重就是选择该动作的概率 \pi(a|s)。比如如果在状态 s 有三个可行动作，策略分别给它们分配了0.5、0.3、0.2的概率，那么就有三条边，权重分别是这些概率值。

第二层的分支则对应环境的随机性。当智能体选定了某个动作 a 之后，环境会根据其内在的动态规律，以一定的概率转移到不同的下一状态，并且给出相应的奖励。这些转移由环境的动态函数 p(r,s'|s,a) 决定。因此在每个动作节点下，会有多条边指向不同的"奖励-下一状态"组合，每条边的权重是该组合发生的概率。最后，叶节点就是下一状态的价值 V_{\pi}(s')。

整个备份图清晰地展现了贝尔曼方程的两步计算结构：第一步是策略层面的选择（加权平均不同的动作），第二步是环境层面的随机性（加权平均不同的转移结果）。计算 V_{\pi}(s) 就是从叶节点向上反向传播，按照边的权重进行加权求和，最终汇总到根节点。这个过程被称为"备份"，因为我们把未来的价值信息向当前时刻传递回来。

动作价值函数的贝尔曼方程推导

前面我们详细推导了状态价值函数 V_{\pi}(s) 的贝尔曼方程，现在我们来看动作价值函数 q_{\pi}(s,a) 的情况。动作价值函数的推导逻辑与状态价值函数是平行的，但起点不同，因此方程的形式也有差异。

回忆动作价值函数的定义：它表示在状态 s 强制执行动作 a，然后从下一时刻开始遵循策略 \pi 能够获得的期望回报。由于第一步的动作已经确定为 a，所以环境会首先根据动态函数 p(r,s'|s,a) 产生状态转移和奖励。这是第一层的随机性。到达下一状态 s' 之后，智能体重新按照策略 \pi 来选择下一个动作 a'，这引入了第二层的随机性。

具体推导如下：从 q_{\pi}(s,a) 的定义出发，它等于在条件 (S_t=s, A_t=a) 下回报 G_t 的期望。利用回报的递归性质 G_t = R_{t+1} + \gamma G_{t+1}，我们可以写成：

由于动作 a 已经固定，立即奖励和下一状态的分布完全由环境动态决定。因此：

到达下一状态 s' 后，智能体会根据策略 \pi 选择动作。从 s' 开始的期望回报依赖于策略会选择什么动作。具体来说，策略会以概率 \pi(a'|s') 选择各个动作 a'，选择动作 a' 后的期望回报是 q_{\pi}(s',a')。因此需要对所有可能的下一动作求期望：

这就是动作价值函数的贝尔曼方程。与状态价值函数的方程对比，可以看出它们的结构是相反的：V_{\pi} 的方程先对动作求和（策略选择），再对下一状态求和（环境转移）；而 q_{\pi} 的方程先对下一状态求和（环境转移），再对下一动作求和（策略选择）。

动作价值函数的备份图结构

动作价值函数的备份图与状态价值函数的备份图在层次结构上恰好相反。q_{\pi}(s,a) 的备份图从一个状态-动作对 (s,a) 作为根节点开始。由于动作已经确定，第一层的分支不再涉及策略选择，而是直接由环境的随机性决定。环境根据动态函数 p(r,s'|s,a)，以不同的概率转移到各个可能的"奖励-下一状态"组合 (r,s')。每条边的权重就是该组合发生的概率。

第二层才涉及策略的选择。当系统到达某个下一状态 s' 后，智能体需要根据策略 \pi 来决定下一步的动作 a'。因此从每个 s' 节点出发，会有多条边对应不同的可能动作，边的权重是策略给各个动作分配的概率 \pi(a'|s')。叶节点是 q_{\pi}(s',a')，表示选择动作 a' 后的价值。

策略之间的优劣比较

有了价值函数作为评估工具后，我们自然想要比较不同策略的好坏。但如何定义一个策略优于另一个策略呢？在强化学习中，我们采用一个相当严格的定义：策略 \pi' 优于策略 \pi，当且仅当 \pi' 在每一个状态下的价值都不低于 \pi，即：

注意这个定义的严格性：不是要求在某些状态下更好，或者在平均意义上更好，而是要求在所有状态下都至少一样好。这是一个非常强的要求。

这个定义在数学上构成了一个偏序关系。偏序的意思是，并非任意两个策略都可以比较。可能存在两个策略 \pi_1 和 \pi_2，\pi_1 在某些状态下价值更高，而 \pi_2 在另一些状态下价值更高，这时我们说这两个策略不可比。偏序关系的好处是，如果 \pi' 确实优于 \pi，那么无论系统从哪个初始状态出发，选择 \pi' 都比选择 \pi 好。因此如果存在一个策略在偏序意义下优于所有其他策略，那它就是我们要寻找的最优策略。

最优状态价值函数的定义

既然我们想要找到最好的策略，那么最好的策略能够达到什么样的性能呢？对于每个状态 s，我们定义最优状态价值为：

这个定义的含义是：对于状态 s，我们考虑所有可能的策略 \pi，每个策略都会给出一个价值 V_{\pi}(s)，我们取其中的最大值作为 V^*(s)。V^*(s) 代表了在状态 s 下，通过最优决策所能达到的最高期望回报。

这里有问题需要理解：这个最大化是对每个状态独立进行的。也就是说，对于不同的状态，达到 V^*(s) 的最优策略可能是不同的。强化学习的一个重要理论结果表明，对于几乎所有的MDP问题，都至少存在一个最优策略，它在每个状态下的价值都恰好等于最优状态价值 V^*(s)。

最优动作价值函数的定义

与最优状态价值函数类似，我们可以定义最优动作价值函数：

它表示在状态 s 执行动作 a 后，通过后续的最优行动所能达到的最高期望回报。最优动作价值函数提供了比最优状态价值函数更细致的信息：它不仅告诉我们每个状态最好能达到什么价值，还告诉我们在该状态下，每个具体动作最好能达到什么价值。

从实用角度看，如果我们知道了 q^*(s,a)，那么决策就变得非常简单了。在任何状态 s，我们只需要查看所有可行动作的 q^* 值，选择其中最大的那个，就是最优的决策。这就是为什么在很多强化学习算法中，我们更倾向于估计 q^* 而不是 V^*：q^* 直接给出了行动指南，而 V^* 还需要结合环境模型才能决定该做什么。

两个最优价值函数的联系

最优状态价值函数和最优动作价值函数之间存在简单而直接的关系：

这个等式的含义非常直观：状态 s 的最优价值等于在该状态下所有可行动作的最优价值中的最大值。因为如果我们想从状态 s 获得最大的期望回报，最优的做法就是选择那个能带来最高价值的动作。q^*(s,a) 已经告诉了我们每个动作能达到的最优价值，所以 V^*(s) 自然就是这些价值中的最大者。

这个关系与之前一般策略下 V_{\pi} 和 q_{\pi} 的关系形成了鲜明对比。对于一般策略，我们有 V_{\pi}(s) = \sum_a \pi(a|s) q_{\pi}(s,a)，这是一个加权平均的关系。而对于最优情况，关系变成了取最大值。这个差异揭示了最优策略的本质特征：最优策略不会在多个动作之间随机摇摆，而是确定性地选择最好的动作。如果有多个动作并列最优（q^* 值相同），那么随便选哪个都是最优的，但不需要在它们之间随机化。

从最优动作价值构造最优策略

如果我们已经知道了 q^*(s,a) 对所有状态-动作对的值，那么构造最优策略就轻而易举了。最优策略的构造规则是：在每个状态 s，选择使 q^*(s,a) 达到最大值的动作，即：

这里的 \arg\max 表示取最大值的那些动作的集合。为什么用 \in 而不是 =？因为可能有多个动作同时达到最大的 q^* 值，它们都是最优的选择。在这种情况下，我们可以任意选择其中一个，或者在它们之间随机选择，都不会影响最优性。

最优价值函数的唯一性与最优策略的多样性

关于最优性，有两个重要的理论结果。第一，最优价值函数 V^* 和 q^* 都是唯一的，因为它们的定义是对所有策略取最大值，这个最大值对于给定的MDP是客观确定的，不依赖于我们如何寻找或构造最优策略。无论用什么方法，只要找到的是真正的最优价值函数，它们的值就应该完全一样。

第二，最优策略 \pi^* 本身可能不是唯一的。某些状态可能有多个同样好的动作。如果在状态 s 有两个动作 a_1 和 a_2 满足 q^*(s,a_1) = q^*(s,a_2) = \max_a q^*(s,a)，那么在 s 选择 a_1 还是 a_2 都是最优的。不同的最优策略可能在这个状态做出不同的选择，但它们的整体表现是一样的，都达到了最优价值 V^* 和 q^*。

这个结果告诉我们，在寻找最优策略时，我们的目标是找到任意一个能达到最优价值的策略。

最优状态价值函数的贝尔曼最优性方程推导

前面我们推导了一般策略 \pi 的价值函数满足的贝尔曼方程。现在我们要推导最优价值函数满足的方程。这个方程被称为贝尔曼最优性方程（Bellman Optimality Equation），它是求解最优策略的理论基础。

推导从 V^* 和 q^* 的关系开始。我们知道：

现在的问题是，如何表达 q^*(s,a)？根据 q^* 的定义，它是在状态 s 执行动作 a 后，遵循最优策略所能获得的期望回报。我们可以把这个期望分解成立即奖励和未来回报两部分：

这里下标 \pi^* 表示期望是在最优策略下计算的。

关键的观察是:给定当前状态 s 和动作 a,下一时刻的回报 G_{t+1} 只依赖于转移到的下一状态 S_{t+1}。而如果从 S_{t+1} 开始按最优策略行动,其期望回报正是 V^*(S_{t+1})。因此:

这一步移除了下标 \pi^*,因为一旦用 V^* 表示未来价值,就不再需要显式指定策略。期望是对立即奖励和下一状态的分布求平均:

这就是最优状态价值函数的贝尔曼最优性方程。这个方程对状态空间中的每个状态 s 都成立，因此它构成了一个方程组。方程的个数等于状态的个数 |S|，未知数是各个状态的最优价值 V^*(s)。

贝尔曼最优性方程的非线性本质

仔细观察这个方程，我们会发现它与一般策略的贝尔曼方程有本质区别。对于固定策略 \pi，一般贝尔曼方程是：

这是一个线性方程组。右侧是各个状态价值 V_{\pi}(s') 的线性组合，系数由策略概率 \pi(a|s) 和转移概率 p(r,s'|s,a) 的乘积给出。

但贝尔曼最优性方程中引入了 \max 算子：

\max 算子破坏了线性性。右侧不再是 V^* 各分量的线性组合，而是多个线性组合中的最大值。这使得方程变成非线性的。非线性方程组通常比线性方程组更难求解，不能直接使用矩阵方法，需要依赖迭代算法。

但非线性性也带来了好处：\max 算子自动编码了最优性条件。它意味着在每个状态，我们要选择最好的动作。如果我们能求解这个非线性方程组，得到的解就直接是最优价值函数，而不需要事先知道最优策略是什么。从某种意义上说，\max 算子把"寻找最优策略"这个优化问题嵌入到了方程本身中。

最优动作价值函数的贝尔曼最优性方程

与最优状态价值类似，最优动作价值函数也满足自己的贝尔曼最优性方程。推导的逻辑是平行的。从 q^* 的定义出发，在状态 s 执行动作 a 后，环境转移到下一状态 s'。从 s' 开始，最优策略会选择使 q^*(s',a') 最大的动作 a'。因此：

这个方程的结构是：给定当前的状态-动作对 (s,a)，环境以概率 p(r,s'|s,a) 产生奖励 r 和下一状态 s'。到达 s' 后，我们在所有可行动作 a' \in A(s') 中选择价值最高的，对应的最优价值是 \max_{a'} q^*(s',a')。这个未来的最优价值经过折扣 \gamma 后，加上立即奖励 r，对所有可能的转移结果求期望，就得到了 q^*(s,a)。

这个方程同样是非线性的，同样包含 \max 算子。方程组的规模更大，因为未知变量是所有状态-动作对的最优价值，共有 |S| \times |A| 个（这里 |A| 是动作空间的平均大小）。虽然方程数量更多，但在某些算法中，直接求解 q^* 比求解 V^* 更方便，因为有了 q^* 就可以直接构造最优策略，不需要额外的环境模型。

最优价值函数备份图的结构

最优价值函数的备份图与一般策略的备份图有显著差异，这种差异反映了最优性的特殊性质。对于 V^*(s)，备份图从状态 s 开始。第一层分支对应所有可能的动作选择。但与 V_{\pi} 的备份图不同，这些分支不再有策略概率权重，因为我们不是按某个固定策略随机选择，而是要从这些动作中选出最好的。这在图上体现为一个 \max 节点：我们要对所有动作分支取最大值。

第二层是环境的随机转移。对于每个动作 a，环境会以概率 p(r,s'|s,a) 转移到不同的"奖励-下一状态"组合。这一层和一般策略的情况一样，都是对随机结果求期望。叶节点是下一状态的最优价值 V^*(s')。整个计算过程是：先对环境的随机性求期望（得到每个动作的期望价值），然后对所有动作取最大值。

对于 q^*(s,a)，备份图从状态-动作对 (s,a) 开始。第一层是环境的随机转移，这和 q_{\pi} 的情况一样。但第二层出现了差异：到达下一状态 s' 后，我们不是按某个策略的概率分布选择动作，而是在所有可行动作中取最优的。因此图上是一个 \max 节点，对 s' 的所有可行动作求最大值。叶节点是 q^*(s',a')。

对比两个最优价值的备份图和两个一般策略的备份图，我们可以总结出规律：V 的图总是"动作层-环境层"的结构，q 的图总是"环境层-动作层"的结构；而最优价值的图会在动作层引入 \max 节点，一般策略的图在动作层是按概率加权平均。

从最优动作价值到最优策略的简单构造

一旦我们通过某种方法求解出了最优动作价值函数 q^*(s,a)，构造最优策略就变成了一个简单的查表问题。最优策略采用贪心规则：在每个状态 s，遍历所有可行动作，选择 q^* 值最大的那个动作。用数学符号表示：

这个贪心策略为什么是最优的？因为 q^*(s,a) 已经完整地编码了从当前动作到未来所有时刻的最优行为。它不仅考虑了执行动作 a 的即时效果，还考虑了在到达的下一状态中继续做最优决策所能带来的所有未来收益。因此，选择当前 q^* 最大的动作，等价于选择了从现在到未来整个时间跨度上的最优路径。

这个简单的贪心构造突出了 q^* 的实用价值。如果我们有 V^*，要决定在状态 s 该做什么，还需要结合环境模型：对每个动作 a 计算 \sum_{r,s'} p(r,s'|s,a)[r + \gamma V^*(s')]，然后选最大的。但如果我们有 q^*，就不需要环境模型了，直接比较所有动作的 q^* 值即可。这就是为什么很多强化学习算法（特别是基于采样的方法）专注于估计 q^* 而不是 V^*。

表格方法

表格方法是求解MDP问题的一类经典算法，但它们只在特定条件下有效。理解这些条件对于知道何时应该使用表格方法、何时应该转向其他方法（如函数逼近方法）至关重要。

表格方法的第一个前提条件是：环境的动态特性必须是已知的。这意味着转移概率函数 p(r,s'|s,a) 是完全已知的，我们能够准确计算在任何状态 s 执行任何动作 a 后，转移到每个可能的下一状态 s' 并获得奖励 r 的概率。在很多实际问题中，这个条件并不满足。比如在机器人控制中，我们不知道精确的物理模型；在金融市场中，我们不知道市场如何响应我们的交易。当环境是黑盒时，表格方法无法直接应用，需要改用基于采样的方法（如蒙特卡洛方法或时序差分学习）。

第二个前提条件是：状态空间和动作空间必须是较小的。首先，状态和动作必须是离散的，因为我们要用表格来存储价值。其次，它们的数量必须足够少，使得我们可以为每个状态（或每个状态-动作对）分配一个存储位置，并且可以在合理的时间内遍历所有状态进行计算。如果状态空间非常大（比如围棋的 10^{170} 种局面），或者是连续的（比如机器人的关节角度可以取任意实数值），表格方法就不可行了，需要使用函数逼近来表示价值函数。

策略评估问题的定义

在表格方法的框架下，第一个基本问题是策略评估（Policy Evaluation）：给定一个策略 \pi，如何计算它的价值函数 V_{\pi}(s)？这个问题的输入是一个完整定义的MDP（包括状态空间、动作空间、转移函数、奖励函数、折扣因子）和一个策略 \pi，输出是该策略的状态价值函数。

我们在前面的课程中已经推导出，V_{\pi} 满足贝尔曼方程：

这个方程对每个状态都成立，因此形成了一个包含 |S| 个方程的线性方程组。理论上，我们可以直接求解这个线性方程组来得到 V_{\pi}。但在实践中，直接求解大规模线性方程组的计算代价很高（时间复杂度是 O(|S|^3)），并且当状态数量很大时，存储整个系数矩阵也不现实。因此，我们采用迭代的方法来逼近解。

用算子的语言，我们可以把贝尔曼方程写成不动点方程的形式：

这里 \underline{V}_{\pi} 是价值向量，B_{\pi} 是贝尔曼算子。真实的价值函数是算子的不动点，即应用算子后保持不变的点。

贝尔曼算子作为压缩映射

为了理解迭代方法为什么能够求解贝尔曼方程，我们需要了解贝尔曼算子的一个重要数学性质：它是一个压缩映射（Contraction Mapping）。

压缩映射的定义是：对于度量空间（比如实向量空间配备某种范数）中的任意两个点 \underline{V}_1 和 \underline{V}_2，存在一个常数 0 \leq \lambda < 1，使得应用算子后两点之间的距离缩小了至少 \lambda 倍：

对于贝尔曼算子 B_{\pi}，这个压缩系数 \lambda 恰好等于折扣因子 \gamma。直观地理解，贝尔曼算子把未来的价值打了 \gamma 折扣，因此两个不同价值估计之间的差异也会被缩小 \gamma 倍。

压缩映射性质带来两个关键的理论保证。第一，压缩映射必然存在唯一的不动点。这意味着方程 \underline{V}_{\pi} = B_{\pi}(\underline{V}_{\pi}) 有且仅有一个解，即策略 \pi 的真实价值函数是唯一确定的。第二，从任意初始点出发，反复应用压缩映射都会收敛到这个唯一的不动点。

不动点迭代的收敛保证

基于压缩映射性质，我们可以构造一个简单的迭代序列来求解贝尔曼方程。从任意初始价值向量 \underline{V}_{\pi}^{(0)} 开始，反复应用贝尔曼算子：

也就是说，第 k+1 次迭代的价值估计等于对第 k 次迭代的估计应用一次贝尔曼更新。压缩映射定理保证，无论我们选择什么样的初始估计 \underline{V}_{\pi}^{(0)}（可以是全0，可以是随机值，可以是任何向量），这个迭代序列都会收敛到真实的价值函数 \underline{V}_{\pi}。

收敛的速度由折扣因子 \gamma 控制。具体来说，第 k 次迭代的误差满足：

这个不等式告诉我们，误差以指数速率衰减。每进行一次迭代，误差就缩小到原来的 \gamma 倍。如果 \gamma = 0.9，那么10次迭代后误差大约是初始误差的 0.9^{10} \approx 0.35 倍；20次迭代后大约是 0.9^{20} \approx 0.12 倍。折扣因子越小，收敛越快；折扣因子越接近1，收敛越慢。

这个理论结果非常重要，因为它保证了我们不需要求解复杂的线性方程组，只需要反复进行简单的迭代更新，就能够以任意精度逼近真实的价值函数。

迭代策略评估算法的具体流程

基于不动点迭代的思想，我们可以设计具体的算法来计算 V_{\pi}。这个算法被称为迭代策略评估（Iterative Policy Evaluation）。算法的输入是我们想要评估的策略 \pi。

算法的第一步是初始化。我们需要为每个状态 s \in S 设定一个初始的价值估计 V(s)。这个初始值可以任意选择，比如全部设为0，或者设为随机值，或者根据某种启发式给定。唯一的硬性约束是：如果MDP有终止状态（比如在片段式任务中），终止状态的价值必须初始化为0，即 V(\text{terminal}) = 0。

算法的主体是一个循环过程，不断迭代更新价值估计，直到收敛。每轮迭代开始时，我们设置一个变量 \Delta 来跟踪本轮迭代中价值函数的最大变化量，初始化为 \Delta = 0。然后进入内层循环，遍历状态空间中的每一个非终止状态 s \in S。

对于当前考虑的状态 s，我们首先用一个临时变量 v 保存它的旧价值估计，即 v = V(s)。然后，我们根据贝尔曼方程计算该状态的新价值：

注意这个更新公式的右侧使用的是当前迭代中其他状态的价值估计 V(s')。如果 s' 在本轮迭代中已经被更新过，那么用的是新值；如果还没被更新，用的是旧值。这种"用新值覆盖旧值"的更新方式被称为原位更新（in-place update），它通常比"先全部计算出新值再统一替换"的方式收敛更快。

更新后，我们计算新旧价值的差异 |v - V(s)|，并更新最大变化量：\Delta = \max(\Delta, |v - V(s)|)。这个 \Delta 记录了本轮迭代中所有状态价值变化的最大值，它是衡量收敛程度的指标。

完成对所有状态的遍历后，我们检查收敛条件：如果 \Delta < \theta，其中 \theta 是一个预先设定的小正数阈值（比如 10^{-4}），就认为价值函数已经基本稳定，算法终止并输出当前的 V 作为 V_{\pi} 的近似。如果 \Delta \geq \theta，说明价值还在显著变化，继续下一轮迭代。

这个算法简单而有效。它的收敛性由压缩映射定理保证，收敛速度取决于折扣因子 \gamma 和阈值 \theta。在实际应用中，即使对于中等规模的状态空间（几千到几万个状态），这个算法也能在合理的时间内收敛。

扫地机器人实例

问题设置:

房间布局（4个状态）：

• s_1：客厅中央
• s_2：脏区域附近
• s_3：墙边
• s_4：充电桩（终止状态）

策略 \pi：

• 在 s_1：60%向前，30%向左，10%向后
• 在 s_2：100%清扫并移动到充电桩附近
• 在 s_3：100%向出口移动
• 在 s_4：终止

环境动态 p(r,s'|s,a)（已知）：

• s_1 向前：80%到 s_2（奖励-1），20%到 s_3（奖励-6）
• s_1 向左：100%到 s_3（奖励-1）
• s_1 向后：100%停在 s_1（奖励-6）
• 其他转移已知...

折扣因子：\gamma = 0.9

表格方法

用一个表格存储每个状态的价值，通过迭代更新表格，直到收敛。

迭代过程

第0次迭代

所有状态价值初始化为0（终止状态始终为0）。

第1次迭代，对每个状态应用贝尔曼方程：

更新 V^{(1)}(s_1)：

展开：

• 向前（0.6）：0.8[(-1) + 0.9(0)] + 0.2[(-6) + 0.9(0)] = -0.8 - 1.2 = -2.0
• 向左（0.3）：1.0[(-1) + 0.9(0)] = -1.0
• 向后（0.1）：1.0[(-6) + 0.9(0)] = -6.0

更新 V^{(1)}(s_2)（假设从 s_2 一步到充电桩附近 s_4，奖励+50）：

更新 V^{(1)}(s_3)（假设需要2步到充电桩）：

结果：

第2次迭代，现在用 V^{(1)} 的值来更新：

更新 V^{(2)}(s_1)：

• 向前（0.6）：0.8[(-1) + 0.9(50)] + 0.2[(-6) + 0.9(-1)] = 33.82
• 向左（0.3）：1.0[(-1) + 0.9(-1)] = -1.9
• 向后（0.1）：1.0[(-6) + 0.9(-2.1)] = -7.89

更新其他状态...

继续迭代...

收敛

当 \max_s |V^{(k+1)}(s) - V^{(k)}(s)| < \theta（比如 \theta = 0.01）时停止。

最终：

动作价值函数的评估

类似于状态价值函数的评估，我们也可以设计算法来评估动作价值函数 q_{\pi}(s,a)。算法的整体结构与状态价值评估相似，但有一些区别。首先，我们需要为所有的状态-动作对 (s,a) 而不仅仅是状态 s 设定初始值。其次，每次迭代中，我们遍历的是所有的 (s,a) 对，而不仅仅是状态。

对于每个 (s,a)，更新公式基于动作价值函数的贝尔曼方程：

这个更新涉及的计算量比状态价值的更新更大，因为我们需要对下一状态的所有可能动作求和。但在某些情况下，直接评估 q_{\pi} 是有意义的。特别是当我们需要比较不同动作的价值以进行策略改进时，有了 q_{\pi} 就可以直接查表，而不需要每次都从 V_{\pi} 推导。

另外，在基于采样的方法中（我们后续会学到），直接估计 q 函数往往比估计 V 函数更自然，因为采样得到的经验是"状态-动作-奖励-下一状态"的四元组，直接对应了 q 函数的参数。

表格结构的区别

状态价值函数：一维表格（只按状态索引）

动作价值函数：二维表格（按状态-动作对索引）

最终收敛：

动作价值函数的优势因此就是，如果想改进策略，在 s_1 应该选哪个动作？

如果只有 V 函数，那么就需要对每个动作计算：\sum_{r,s'} p(r,s'|s_1,a)[r + \gamma V(s')]，特别注意还得先知道环境模型 p(r,s'|s,a)。

但是对于动作价值函数，一目了然，直接查表，发现应该选向前，但是动作价值评估的计算量更大，换来的是策略改进的优势，即直接选择Q值最大的动作，无需依靠环境模型来计算。

策略改进

完成策略评估后，我们知道了当前策略 \pi 的表现如何（通过 V_{\pi} 或 q_{\pi}）。自然的问题是：能否找到比 \pi 更好的策略？这就是策略改进（Policy Improvement）要解决的问题。

假设我们已经通过迭代策略评估算法计算出了 V_{\pi}(s)。现在考虑这样一个场景：在某个状态 s，我们有两种选择。第一种选择是继续遵循策略 \pi，按照 \pi(a|s) 的概率分布随机选择动作，然后从下一时刻开始继续按 \pi 行动。这种方式给出的期望回报就是 V_{\pi}(s)，因为这正是状态价值函数的定义。

第二种选择是尝试一个不同的决策：在状态 s 强制执行某个特定的动作 a（不管 \pi 是否倾向于选它），然后从下一时刻开始重新按照策略 \pi 执行。这种方式给出的期望回报是 q_{\pi}(s,a)，即动作价值函数。

局部改进的可行性判断

比较这两个量，如果我们发现 q_{\pi}(s,a) > V_{\pi}(s)，这意味着在状态 s 强制选择动作 a，然后继续按 \pi 行动，比完全遵循 \pi（包括第一步也按 \pi 随机选择）能获得更高的期望回报。既然在第一步选择 a 能带来更好的结果，我们就有理由相信：每次到达状态 s 时，总是选择动作 a 而不是按 \pi 随机选择，应该是一个有益的改进。

更进一步，我们可以在每个状态都做这样的贪心选择。定义新策略 \pi' 为：

也就是说，新策略在每个状态都选择使 q_{\pi}(s,a) 最大的那个动作。这是一个确定性策略，因为我们明确指定了每个状态要选择的动作，不再随机化。

直觉上，这个贪心策略应该比原策略 \pi 更好，因为我们在每个状态都选择了看起来最优的动作。但这个直觉需要严格证明，因为改变一个状态的策略会影响到达其他状态的概率分布，进而影响整个价值函数，可能产生复杂的连锁反应。我们需要确保局部的贪心改进确实能带来全局的提升。

策略改进定理的精确陈述

策略改进定理（Policy Improvement Theorem）给出了判断新策略是否优于旧策略的充分条件。考虑两个确定性策略 \pi 和 \pi'（定理也可以推广到随机策略，但确定性情况更直观）。

定理的假设是：对于所有状态 s \in S，新策略在该状态选择的动作在旧策略下的动作价值，不低于旧策略的状态价值，即：

这个条件的含义是：如果我们在每个状态 s 都按照新策略 \pi' 的选择执行动作 \pi'(s)，然后从下一步开始按旧策略 \pi 行动，这样得到的期望回报至少和完全遵循旧策略 \pi 一样好。

定理的结论是：在这个条件下，新策略 \pi' 在所有状态的价值都不低于旧策略 \pi：

换句话说，如果新策略在每个状态的"第一步选择"都至少和旧策略一样好（从旧策略价值的角度看），那么新策略的整体表现也至少和旧策略一样好。局部的改进保证了全局的改进。

策略改进定理的证明

证明采用了一种巧妙的递归展开技巧。我们从假设不等式出发：

现在展开右侧的动作价值函数。根据 q_{\pi} 的定义，它表示在状态 s 执行动作 \pi'(s) 后，继续按策略 \pi 行动的期望回报。利用回报的递归性质：

因为第一步的动作是由新策略 \pi' 决定的，我们可以把这个期望写成在新策略下（但仅针对第一步）的形式：

注意这里的技巧：期望的下标是 \pi'，表示第一步的动作遵循 \pi'；但未来回报项是 V_{\pi}(S_{t+1})，表示从下一状态开始仍然按旧策略 \pi 评估。

现在的关键步骤来了。我们的假设对所有状态都成立，特别地，对于下一状态 S_{t+1} 也应该有 V_{\pi}(S_{t+1}) \leq q_{\pi}(S_{t+1}, \pi'(S_{t+1}))。将这个不等式代入上式：

再次展开 q_{\pi}(S_{t+1}, \pi'(S_{t+1}))，它又可以写成：

代入得：

应用迭代期望定理（也叫塔式性质），外层期望可以穿透内层期望：

我们可以继续这个过程。再次应用假设不等式于 V_{\pi}(S_{t+2})，再次展开，再次使用塔式性质。经过无限多步的递归展开，最终我们得到：

而这个无限求和的期望恰好就是从状态 s 开始，完全遵循策略 \pi'（不是只第一步，而是所有步都遵循 \pi'）的期望回报，也就是 V_{\pi'}(s)。

因此我们得到：

证明完成。

证明背后的深刻含义

这个证明揭示了一个重要结论: 如果在每个状态都选择当前看起来更好的动作，那么从长远来看，整个策略就一定会变好

我们从一步的比较开始（第一步选择新策略的动作是否比遵循旧策略更好），通过递归地应用相同的不等式假设于每一个未来时刻，最终证明了整个无限期回报的不等式（完全遵循新策略比完全遵循旧策略更好）。

这个证明的关键在于，虽然我们只是基于当前的价值函数 V_{\pi} 和 q_{\pi} 做局部的贪心决策（选择当前看起来最好的动作），但这些局部最优选择会在每一步积累起来，传播到整个未来，最终带来全局的改进。每一步的局部改进通过折扣因子 \gamma 的幂次累加，保证了总体性能的提升。

这也解释了为什么贪心策略改进是有效的：我们不需要进行全局的搜索或规划来找更好的策略，只需要在每个状态局部地选择最优动作。虽然改变一个状态的策略会影响其他状态的价值（因为状态转移概率分布改变了），但策略改进定理保证，只要每个状态的局部改进都是有益的，全局也必然改进。

从价值函数构造改进策略

策略改进定理给出了理论保证后，我们就可以放心地使用贪心策略来改进当前策略了。具体的构造方法是：一旦通过策略评估算法计算出了 q_{\pi}(s,a)（或者从 V_{\pi} 和环境模型推导出 q_{\pi}），就可以定义新策略为：

这个新策略在每个状态都选择使当前动作价值 q_{\pi}(s,a) 最大的动作。根据 q_{\pi} 的定义和 V_{\pi} 的定义的关系，我们知道 V_{\pi}(s) = \sum_a \pi(a|s) q_{\pi}(s,a) 是所有动作价值的加权平均，它必然不超过最大的那个动作价值。因此 q_{\pi}(s, \pi'(s)) \geq V_{\pi}(s) 自动满足。

策略改进定理的条件成立，所以我们可以断言新策略 \pi' 不比旧策略 \pi 差，即 V_{\pi'}(s) \geq V_{\pi}(s) 对所有状态成立。这样我们就完成了一次策略改进步骤：从旧策略到新的、至少和旧策略一样好的策略。

仅用状态价值函数进行策略改进

在实际应用中，我们通常只运行策略评估算法来计算 V_{\pi}(s)，而不是 q_{\pi}(s,a)。这是因为状态价值函数包含的未知数更少（|S| 个而不是 |S| \times |A| 个），计算和存储的开销更小。那么如何仅从 V_{\pi} 出发构造改进策略呢？

答案是我们可以通过一步前瞻（one-step lookahead）从 V_{\pi} 推导出 q_{\pi}。新策略的构造公式可以写成：

而 q_{\pi}(s,a) 可以表示为：

这是因为在状态 s 执行动作 a 后，环境产生奖励和转移到下一状态，然后从下一状态开始按策略 \pi 行动的期望回报正是 V_{\pi}(S_{t+1})。将期望展开为对环境动态的求和：

因此改进策略的公式变为：

环境模型在策略改进中的必要性

上述推导揭示了一个重要的事实：从 V_{\pi} 构造改进策略需要知道环境的转移概率函数 p(r,s'|s,a)。对于每个状态 s 和每个动作 a，我们需要能够计算执行 a 后转移到各个可能的 (r,s') 组合的概率，然后才能算出期望值 \sum_{r,s'} p(r,s'|s,a)[r + \gamma V_{\pi}(s')]。

这就是为什么我们在一开始强调表格方法要求环境动态已知。如果我们不知道 p，就无法直接应用这个公式进行策略改进。在这种情况下，我们需要转向基于采样的方法。比如蒙特卡洛方法直接从经验中估计 q_{\pi}，而不经过 V_{\pi}；或者时序差分学习使用采样来近似期望，而不需要显式的概率函数。

但当环境模型已知时，这个基于 V_{\pi} 的策略改进方法非常高效。我们只需要对每个状态遍历所有可能的动作，对每个动作计算上述期望值（这是一个简单的加权求和），然后选择期望值最大的动作。这个过程完全是确定性的计算，不需要采样或模拟，因此速度很快。

策略迭代算法的整体框架

策略改进定理保证了贪心策略不会比原策略更差。但通常一次改进还不够，新策略 \pi' 可能仍然不是最优的。自然的想法是继续这个改进过程：评估新策略 \pi' 得到 V_{\pi'}，然后基于 V_{\pi'} 再次贪心改进得到 \pi''，如此反复。这就是策略迭代（Policy Iteration）算法的核心思想。

策略迭代算法从一个任意的初始策略 \pi^{(0)} 开始。这个初始策略可以是随机策略（比如在每个状态等概率选择所有可行动作），也可以是根据某种启发式规则设计的策略。初始策略的好坏会影响算法收敛的速度，但不影响最终是否收敛到最优策略。

算法进入一个大循环，循环的每一轮包含两个交替的步骤。第一步是策略评估（Policy Evaluation）：使用迭代策略评估算法计算当前策略 \pi^{(k)} 的价值函数 V_{\pi^{(k)}}。这一步会运行多次迭代，直到价值函数收敛到足够精确的程度。第二步是策略改进（Policy Improvement）：基于刚刚计算出的 V_{\pi^{(k)}}，通过贪心规则构造新的改进策略 \pi^{(k+1)}。

这个"评估-改进"的循环持续进行，直到策略不再发生变化，即 \pi^{(k+1)} = \pi^{(k)}。当策略稳定后，说明我们找到了一个策略，它对自己的价值函数进行贪心改进后仍然得到自己。这意味着什么呢？这意味着在每个状态，当前策略选择的动作恰好就是使 q_{\pi} 最大的动作。而满足这个条件的策略，恰好就是最优策略。

策略迭代为什么能够收敛到最优

前面我们介绍了策略迭代算法的基本框架：交替进行策略评估和策略改进，不断产生一系列策略 \pi^{(0)}, \pi^{(1)}, \pi^{(2)}, \ldots。现在我们需要回答一个关键问题：这个过程会停下来吗？如果会停下来，停在哪里？答案的关键在于两个理论支撑点。

第一个支撑点来自策略改进定理。我们已经证明了，每次策略改进步骤都保证新策略不比旧策略差，即 V_{\pi^{(k+1)}}(s) \geq V_{\pi^{(k)}}(s) 对所有状态 s 都成立。这意味着策略序列的价值函数在单调递增（在偏序意义下）。如果某次改进产生了严格更好的策略，价值就会在至少一个状态上严格提升。

第二个支撑点来自状态空间的有限性。因为状态空间 S 是有限的，包含 |S| 个状态，而我们考虑的是确定性策略，所以可能的确定性策略总数是有限的。具体来说，如果每个状态都有 |A| 个可行动作，那么确定性策略的总数最多是 |A|^{|S|} 个（每个状态独立选择一个动作）。这是一个有限的数字。

将这两点结合起来：我们有一个单调递增的策略序列，而策略的总数是有限的。这意味着什么呢？这意味着严格改进的次数必然是有限的。我们不可能无限次地严格改进策略，因为那样会产生无限多个不同的策略，与策略总数有限矛盾。因此，算法必然会在有限步内到达一个策略 \pi，使得再进行贪心改进时，策略不再改变，即 \pi' = \pi。

收敛点的最优性证明

当算法到达一个不动点策略 \pi，使得贪心改进不再改变它时，会发生什么？根据策略改进的定义，这意味着对于所有状态 s，当前策略选择的动作恰好就是使动作价值最大的那个动作：

用环境模型来表达，就是：

现在观察策略 \pi 的价值函数满足的贝尔曼方程。对于一般策略，贝尔曼方程是：

但我们的 \pi 是确定性策略，并且在每个状态都选择最优动作，所以这个方程变成：

而 \pi(s) 又是使 \sum_{r,s'} p(r,s'|s,a)[r + \gamma V_{\pi}(s')] 最大的动作，因此：

这恰好就是贝尔曼最优性方程的形式！这个方程的解是唯一的，就是最优价值函数 V^*。因此 V_{\pi} = V^*，对应的策略 \pi 就是最优策略 \pi^*。

综上所述，如果一个策略对自己的价值函数进行贪心选择时不会改变，那这个策略就已经是最优的了，换句话说，策略改进一定会改到最优策略

这个推理链条揭示了策略迭代收敛性的深层逻辑：通过反复改进，我们最终到达一个对自己的价值函数是贪心的策略，而这样的策略恰好满足最优性的必要充分条件（贝尔曼最优性方程），因此它就是最优策略。

策略迭代算法的详细执行流程

现在我们来看策略迭代算法的完整实现细节。算法分为三个主要阶段，每个阶段都有明确的目的和操作。

第一阶段是初始化阶段。我们需要初始化两组数据：价值函数和策略。对于价值函数，为每个状态 s \in S 的价值 V(s) 赋予任意初值。这个初值可以是0，可以是随机数，或者根据问题的先验知识给定一个合理的估计。唯一的硬性约束是：如果存在终止状态，必须设置 V(\text{terminal}) = 0。这个约束反映了终止状态的定义：从终止状态出发，系统不再产生任何奖励，因此其价值为0。

对于策略的初始化，我们需要为每个状态 s 指定一个初始动作 \pi(s)。这个初始策略可以是完全随机的，只要满足 \pi(s) \in A(s)，即选择的动作必须是该状态下的可行动作。初始策略的选择会影响算法的收敛速度：如果初始策略接近最优，算法会更快收敛；但即使初始策略很差，算法仍然保证最终收敛到最优。

第二阶段是策略评估阶段，这是一个嵌套的内层循环。这个阶段的目标是精确计算当前策略 \pi 的价值函数 V_{\pi}。注意这里我们说的是"精确"计算，意思是要让价值函数收敛到足够接近真实的 V_{\pi}，而不是只进行一两次迭代。

策略评估循环的具体步骤是：首先初始化 \Delta = 0，这个变量用于跟踪本轮迭代中价值函数的最大变化量。然后遍历所有状态 s \in S（不包括终止状态），对每个状态进行价值更新。更新的过程是：先保存旧的价值估计 v = V(s)，然后根据贝尔曼方程计算新的价值：

这个公式与一般形式的贝尔曼方程略有不同。因为我们考虑的是确定性策略，所以不需要对动作 a 进行求和。策略 \pi(s) 直接告诉我们在状态 s 应该选择哪个动作，我们只需要计算选择这个动作后的期望价值即可。这简化了计算：我们遍历所有可能的"下一状态-奖励"对 (s',r)，按照转移概率 p(s',r|s,\pi(s)) 加权求和。

更新完 V(s) 后，我们计算新旧价值的差异 |v - V(s)|，并更新最大变化量 \Delta = \max(\Delta, |v - V(s)|)。这个 \Delta 在遍历完所有状态后，就记录了本轮迭代中价值变化最大的那个状态的变化量。

完成一轮对所有状态的遍历后，检查收敛条件 \Delta < \theta，其中 \theta 是预设的精度阈值。如果条件满足，说明价值函数的变化已经足够小，我们认为已经充分接近真实的 V_{\pi}，于是退出策略评估循环，进入策略改进阶段。如果条件不满足，继续下一轮迭代，再次遍历所有状态进行更新。

完成策略评估后，我们进入第三阶段：策略改进。这个阶段的目标是根据刚刚计算出的价值函数 V 来构造一个改进的策略。

策略改进的第一步是设置一个布尔标志 \text{policy-stable} = \text{true}。这个标志用于记录策略在本轮改进中是否发生了变化。我们将在遍历所有状态后检查这个标志：如果它仍然是真，说明策略已经稳定，算法可以终止；如果它变成了假，说明至少有一个状态的策略发生了改变，我们需要返回策略评估阶段重新评估新策略。

然后我们遍历所有状态 s \in S，对每个状态进行策略更新。更新的过程是：首先保存当前策略在该状态的旧动作选择，即 \text{old-action} = \pi(s)。然后根据贪心规则计算新的动作选择：

这个公式的含义是：对于状态 s，我们遍历所有可行动作 a \in A(s)，对每个动作计算如果选择它能获得的期望价值（一步前瞻），然后选择期望价值最大的那个动作作为新策略在该状态的选择。这就是贪心策略改进的核心：基于当前的价值估计，在每个状态都选择看起来最好的动作。

计算出新动作后，我们比较它与旧动作是否相同。如果 \pi(s) \neq \text{old-action}，说明策略在状态 s 发生了改变，此时我们设置 \text{policy-stable} = \text{false}，记录下策略有变化。如果新旧动作相同，则不改变标志。

完成对所有状态的策略更新后，检查标志 \text{policy-stable} 的值。如果标志为假，说明至少有一个状态的策略发生了变化，当前策略还不是最优的（因为它对自己的价值函数不是贪心的），因此我们需要返回第二阶段，重新评估新策略的价值函数，然后再次尝试改进。这样就形成了"评估-改进-评估-改进"的循环。

如果标志为真，说明贪心改进没有改变任何状态的策略。这意味着当前策略 \pi 对它自己的价值函数 V 是贪心的，即在每个状态都选择了使 \sum_{s',r} p(s',r|s,a)[r + \gamma V(s')] 最大的动作。根据前面的分析，这样的策略满足贝尔曼最优性方程，因此它就是最优策略。此时算法终止，输出当前的 V 作为最优价值函数的近似，输出当前的 \pi 作为最优策略的近似：

这里用"近似"是因为我们在策略评估阶段使用了阈值 \theta 来判断收敛，而不是精确求解到无限精度。但只要 \theta 足够小，这个近似就足够精确。

策略迭代算法的计算效率

虽然策略迭代算法在理论上很优雅，能够保证收敛到最优策略，但在实际应用中它有一个显著的效率问题。让我们仔细分析算法的计算成本分布。

算法的大部分时间都花在了策略评估阶段。每次策略改进后，我们都需要从头开始评估新策略的价值函数，运行内层循环直到价值函数收敛。这个内层循环本身是一个迭代过程，可能需要多次（甚至几十次、上百次）扫描整个状态空间才能使价值函数充分收敛。而在策略迭代的外层循环中，我们可能要经历多次策略改进，每次都要重新进行完整的策略评估。

从优化的角度看，这种做法存在浪费。我们花费大量计算资源去精确评估的这些中间策略 \pi^{(0)}, \pi^{(1)}, \ldots, \pi^{(k-1)} 都不是最优的。我们辛辛苦苦算出的精确价值函数 V_{\pi^{(k)}}，在下一次策略改进后就被抛弃了，需要重新评估新策略 \pi^{(k+1)} 的价值。

而且，精确评估每个中间策略的代价是很高的。策略评估的内层循环需要不断迭代，直到价值函数的最大变化量 \Delta 小于阈值 \theta。对于较大的状态空间，每次完整的策略评估可能需要数百甚至数千次迭代。如果我们在策略迭代的过程中需要评估10个中间策略，而每个策略的评估需要100次迭代，那么总的迭代次数就是1000次，这是非常昂贵的。

这引发了一个自然的问题：我们真的需要在每次策略改进前都等待价值函数完全收敛吗？能否在价值函数还没有完全稳定时就进行策略改进？这个问题的答案导向了价值迭代算法的设计。

策略迭代的流程

第1轮：

1. 策略评估（多次迭代直到收敛）：计算 V_{\pi_0}，可能需要100次迭代
2. 策略改进：基于 V_{\pi_0} 得到新策略 \pi_1

第2轮：

1. 策略评估：计算 V_{\pi_1}，又需要100次迭代
2. 策略改进：得到 \pi_2

如果有10个策略需要改进，总共需要 10 \times 100 = 1000 次迭代。

价值迭代算法

价值迭代算法对前面的问题给出了一个激进而有效的答案：我们根本不需要等待价值函数收敛，甚至不需要显式地维护一个中间策略，而是可以直接向最优价值函数迭代。更准确地说，价值迭代将策略评估和策略改进这两个步骤融合成了一个统一的更新操作。

价值迭代的核心更新规则非常简洁。对于每个状态 s \in S，我们执行以下更新：

仔细观察这个公式，它与策略评估的更新规则有本质区别。在策略评估中，我们对动作按照策略的概率分布求期望：

但在价值迭代中，我们对动作取最大值：

策略评估考虑"策略会选择哪些动作"，价值迭代直接选"最优动作"。这个 \max 的引入改变了整个算法的性质。

价值迭代不维护一个显式的中间策略 \pi。我们只有价值估计 V，每次迭代都直接基于当前的 V_k 来计算下一轮的 V_{k+1}，而没有"先固定策略，然后评估该策略"这个中间过程。从某种意义上说，策略被隐式地编码在了 \max 操作中：在每次更新时，我们都在考虑"如果在状态 s 选择最优动作会怎样"，但我们不需要明确记录这个最优动作是什么。

从形式上看，价值迭代就是在反复应用贝尔曼最优性方程。我们把最优价值函数应该满足的方程 V^*(s) = \max_a \sum_{r,s'} p(s',r|s,a)[r + \gamma V^*(s')] 转化为迭代格式，用当前的价值估计 V_k 来近似方程右边的 V^*，从而得到更新后的估计 V_{k+1}。

在扫地机器人的例子里，初始化状态为

状态：s_1 客厅，s_2 脏区域，s_3 墙边，s_4 充电桩

采用价值迭代算法: 第1次迭代

更新 V^{(1)}(s_1)（客厅中央）：

计算每个动作的价值：

取最大值：

策略评估vs价值迭代对比：

• 策略评估（假设策略是60%向前，30%向左，10%向后）：

  V^{(1)}(s_1) = 0.6(-2.0) + 0.3(-1.0) + 0.1(-6.0) = -2.1

• 价值迭代（直接选最优动作"向左"）：

  V^{(1)}(s_1) = -1.0

价值迭代的结果更优！

更新 V^{(1)}(s_2)（脏区域）：

假设只有清扫动作，100%到充电桩附近（奖励+50）：

V^{(1)}(s_3) V^{(1)}(s_4) 同理，因此 结果：

第2次迭代

更新 V^{(2)}(s_1)：

现在用 V^{(1)} 的值计算：

这次最优动作变成了"向前"

结果：

继续迭代...

最终收敛到最优价值函数：

换句话说，之前的策略迭代是对策略进行计算、改进，但是这里的价值迭代，是选择最优动作，因此这个选择最优动作这个策略已经定下来了，那么就相当于给定一个最优策略下的计算

价值迭代与最优性方程的深层联系

为了理解价值迭代为什么有效，我们需要回顾贝尔曼最优性方程。最优状态价值函数 V^* 满足：

这是一个不动点方程：V^* 在贝尔曼最优性算子的作用下保持不变。与策略评估中的贝尔曼算子相比，这个算子包含了 \max 操作，因此是非线性的。但它仍然具有压缩映射的性质，这可以严格证明（证明的技术细节涉及算子理论，但核心思想是折扣因子 \gamma 的作用）。

压缩映射性质保证了两件事。第一，方程有唯一解。不管我们用什么方法求解，只要求出的解满足这个方程，它就必然是 V^*。第二，从任意初始值出发反复应用算子，都会收敛到这个唯一解。也就是说，无论我们如何选择初始价值估计 V_0，序列 V_0, V_1, V_2, \ldots 都会收敛到 V^*，其中 V_{k+1} 是对 V_k 应用一次贝尔曼最优性算子的结果。

这正是价值迭代算法在做的事情。每次迭代，我们都对所有状态应用一次贝尔曼最优性方程的右端计算，把结果作为新的价值估计。理论保证告诉我们，这样的迭代序列必然收敛到 V^*，并且收敛速度由折扣因子 \gamma 控制：误差以 \gamma^k 的速度指数衰减。

与策略评估的区别在于，策略评估是在求解线性方程组（对于固定策略，贝尔曼方程是线性的），而价值迭代是在求解非线性方程组（因为 \max 算子）。但两者都是压缩映射，都有唯一的不动点，都可以通过简单的迭代来逼近。价值迭代的优势在于，它直接收敛到最优价值，而不需要经历多个非最优策略的评估过程。

从最优价值函数提取最优策略

价值迭代算法专注于寻找最优价值函数 V^*，一旦我们有了 V^*（或者其足够精确的近似），就可以得出最优策略。

提取策略的方法是选择使这个可行动作期望值最大的动作作为最优策略在该状态的选择：

换句话说，我们的最优策略就是在每个状态选择最优动作。

因此价值迭代的整体流程是两阶段的。第一阶段是主要的计算阶段：通过反复应用贝尔曼最优性方程，使价值估计收敛到 V^*。这个阶段可能需要多次迭代，每次迭代都要扫描所有状态，但每次迭代都在向最优价值靠近。第二阶段是提取阶段：在价值收敛后，做一次贪心扫描得到最优策略。这个两阶段的结构与策略迭代形成对比：策略迭代在两个步骤（评估和改进）之间反复循环，而价值迭代先集中完成价值收敛，然后一次性提取策略。

价值迭代中隐含的策略改进机制

虽然价值迭代不显式维护中间策略，但策略改进的思想实际上隐含在算法的更新规则中。每次执行更新：

这个 \max 操作本质上就是在进行策略改进。我们可以这样理解：如果我们在更新前基于当前的 V 定义一个贪心策略 \pi_{\text{greedy}}(s) = \arg\max_a \sum_{r,s'} p(r,s'|s,a)[r + \gamma V(s')]，那么更新后的价值 V(s) 恰好等于在状态 s 按照 \pi_{\text{greedy}} 选择动作并继续按当前价值估计行动的期望回报。

换句话说，每次价值迭代的更新都隐式地构造了一个关于当前价值估计的贪心策略，然后用这个贪心策略来更新价值。但与策略迭代不同，我们不需要显式存储这个中间策略，也不需要完整评估它（即不需要等待价值函数在该策略下收敛）。我们只是用它来指导一次价值更新，然后在下一轮迭代中，基于更新后的价值再次构造新的隐式贪心策略。

这种隐式的策略改进融合在价值更新中，使得算法更加简洁高效。我们避免了策略迭代中"固定策略→评估到收敛→改进策略→固定新策略→再次评估到收敛"这样的繁琐过程，而是在每一步都同时进行价值更新和隐式策略改进。这可以看作是策略迭代的一个极限情况：策略评估只进行一次迭代（而不是等待收敛），然后立即进行策略改进。

价值迭代算法的完整实现

算法分为两个主要阶段：初始化和迭代更新。

第一阶段是初始化。我们需要为算法设定起点。具体操作是：为每个状态 s \in S 的价值 V(s) 赋予一个任意的初值。这个初值的选择在理论上不影响收敛性（无论从哪里开始，算法都会收敛到 V^*），但在实践中会影响收敛速度。如果我们对问题有先验知识，可以给出一个合理的初始估计，比如基于启发式或者问题的下界上界。如果没有特别的信息，最简单的选择是全部初始化为0。

初始化的唯一硬性约束是：如果MDP有终止状态，必须设置 V(\text{terminal}) = 0。这个约束确保了终止状态的价值始终为0，符合其定义（从终止状态出发不再产生任何奖励）。对于片段式任务，正确设置终止状态的价值对算法的正确性至关重要。

第二阶段是主循环，进行价值函数的迭代更新。这是算法的核心部分，会反复执行直到收敛。每轮迭代的开始，我们设置 \Delta = 0，这个变量用于跟踪本轮迭代中所有状态价值变化的最大值。然后遍历状态空间中的每一个状态 s \in S（如果 s 是终止状态则跳过，因为终止状态的价值已经固定为0）。

对于当前考虑的状态 s，我们首先保存它的旧价值估计到临时变量 v = V(s)。然后执行价值迭代的核心更新操作，根据贝尔曼最优性方程计算新的价值：

这个更新的计算过程是：对状态 s 的每个可行动作 a，计算在当前价值估计下选择该动作的期望回报。具体来说，我们遍历所有可能的"奖励-下一状态"对 (r,s')，将它们按照转移概率 p(r,s'|s,a) 加权求和，每项的值是 r + \gamma V(s')（立即奖励加上折扣后的下一状态价值）。这给出了动作 a 的期望价值。计算出所有动作的期望价值后，取其中的最大值作为状态 s 的新价值 V(s)。

注意这里使用的是当前迭代中的价值估计 V(s')。如果 s' 在本轮迭代中已经被更新过，那么用的是新值；如果还没被更新，用的是旧值。这种原位更新方式（in-place update）通常比"先全部计算出新值到一个临时数组，然后统一复制回去"的方式收敛更快，因为新信息能够立即被利用。

完成更新后，我们计算新旧价值的绝对差值 |v - V(s)|，并更新全局最大变化量：\Delta = \max(\Delta, |v - V(s)|)。这个操作确保 \Delta 记录了本轮迭代中变化最大的那个状态的变化量。

完成对所有状态的遍历后，我们检查收敛条件 \Delta < \theta。如果满足，说明所有状态的价值变化都小于阈值 \theta，价值函数已经基本稳定，算法终止。此时我们输出当前的 V 作为最优价值函数 V^* 的近似。如果条件不满足，说明价值还在显著变化，继续下一轮迭代。

算法终止后，我们还需要执行一次策略提取，通过贪心选择得到最优策略：

最终输出的是近似最优价值函数 V 和近似最优策略 \pi。这就是完整的价值迭代算法的流程，它通过直接向最优价值收敛，避免了策略迭代中反复评估非最优策略的低效问题，是动态规划方法中的另一个重要算法。

SARSA和Q-learning和DQN

SARSA算法

在之前的课程中，我们学习了策略迭代（policy iteration）和价值迭代（value iteration）这两种经典的强化学习算法。但这两种算法都有一个关键的前提条件：它们需要知道环境的动态模型，也就是转移概率函数 p(s', r | s, a)。这个函数描述了在状态 s 下采取动作 a 后，转移到新状态 s' 并获得奖励 r 的概率分布。然而在实际应用中，我们往往无法获得这个完整的环境模型，那么我们该如何解决这个问题呢？

核心思路是：既然我们不知道环境的转移概率，那就不再去估计状态价值函数 v_{\pi}(s)，而是转而估计动作价值函数 q_{\pi}(s, a)。为什么要这样做？因为状态价值函数 v_{\pi}(s) 在选择动作时需要知道 p(s', r | s, a) 来计算期望，而动作价值函数 q_{\pi}(s, a) 直接告诉我们在状态 s 下采取动作 a 的价值，不需要对后续状态求期望。一旦我们得到了 q_{\pi}(s, a) 的估计，策略迭代和价值迭代的框架仍然可以使用，只是把对状态价值的操作替换为对动作价值的操作。

从多臂老虎机到SARSA：更新规则的演化

让我们从最简单的情况开始理解这个估计过程。考虑多臂老虎机（N-Armed Bandit, NAB）问题，这是一个只有一个状态的特殊强化学习问题。在这个问题中，如果我们在时刻 t 选择了动作 a（即 A_t = a），那么我们用以下方式更新对该动作价值的估计：

这个公式的含义是：用实际观察到的奖励 R_t 与当前估计 Q_t(a) 的差异来更新估计值，更新的步长是 \frac{1}{N_a}，其中 N_a 是动作 a 被选择的次数。这样做的效果是计算样本平均值。但这个更新规则有个问题：随着 N_a 增大，更新步长越来越小，对新信息的响应会变得很慢。

为了解决这个问题，我们引入一个固定的学习率 \alpha < 1，把更新规则改写为：

如何把这个思想扩展到完整的强化学习问题？在完整的MDP中，我们不仅有即时奖励 R_t，还有未来的回报。根据动作价值函数的定义，q_{\pi}(s, a) 应该等于在状态 s 采取动作 a 后获得的即时奖励加上后续所有奖励的折扣和的期望。因此，如果我们在状态 s 采取动作 a 后转移到状态 s'，并在 s' 选择了动作 a'，那么一个合理的更新目标应该是 R_t + \gamma Q_t(s', a')。这里 R_t 是即时奖励，\gamma Q_t(s', a') 是对未来回报的估计。

这就引出了SARSA的核心更新规则：

这个公式的结构与多臂老虎机的更新规则完全一致，只是把目标值从单纯的 R_t 变成了 R_t + \gamma Q_t(s', a')。这个新的目标值 R_t + \gamma Q_t(s', a') 就是我们对期望回报的估计。

Bootstrap：用估计值来更新估计值

这里有一个非常重要的概念：bootstrap（自举）。注意到我们用 Q_t(s', a') 来估计 Q_{t+1}(s, a)，也就是说，我们用一个估计值来更新另一个估计值。这种方法被称为bootstrap

为什么要这样做？因为在实际问题中，我们无法等到一个episode结束后才更新Q值（那样就变成蒙特卡洛方法了），我们希望能够在每一步都进行学习。通过使用 Q_t(s', a') 作为未来回报的近似，我们可以立即进行更新，而不需要等待完整的回报序列。这种方法的代价是引入了偏差（因为 Q_t(s', a') 本身不准确），但好处是可以从每一步交互中学习，大大提高了样本效率。

SARSA算法的执行流程

现在让我们详细理解SARSA算法的执行过程。假设当前智能体处于状态 S_t = s，那么算法的每一步操作如下：

首先，我们需要根据当前的Q值函数 Q_t(s, a) 选择一个动作 A_t = a。这里通常使用 \varepsilon-贪婪策略：以 1-\varepsilon 的概率选择当前Q值最大的动作，以 \varepsilon 的概率随机选择一个动作。这样做既能利用当前的知识（exploitation），又能探索未知的可能（exploration）。

接下来，我们在环境中执行这个动作 a，然后观察两个关键信息：获得的即时奖励 R_t = r 和转移到的新状态 S_{t+1} = s'。注意此时我们还没有更新Q值，因为SARSA需要更多信息。

这时SARSA与其他算法的关键区别出现了：我们需要再次使用策略（同样基于Q值的 \varepsilon-贪婪策略）在新状态 s' 中选择下一个动作 A_{t+1} = a'。为什么要选择 a'？因为我们的更新规则需要 Q_t(s', a')，我们必须知道在新状态下实际会采取什么动作。

现在我们拥有了完整的信息：状态 s、动作 a、奖励 r、新状态 s'、新动作 a'，这就是SARSA名字的由来（State-Action-Reward-State-Action）。有了这些信息，我们就可以执行更新了。

SARSA算法的完整流程

首先需要初始化：对所有的状态-动作对 (s, a)，我们任意初始化 Q(s, a) 的值，但有一个例外——对于终止状态，我们必须设置 Q(\text{terminal}, a) = 0，这对所有动作 a 都成立。这是因为在终止状态不会再有任何未来回报。

然后我们开始进行多个episode的训练。每个episode开始时，我们初始化起始状态 S，并根据Q值（比如使用 \varepsilon-贪婪策略）选择初始动作 A。

在每个episode的每一步中，我们执行以下循环：首先执行当前动作 A，观察得到的奖励 R 和新状态 S'。然后在新状态 S' 中，仍然使用基于Q值的策略选择下一个动作 A'。有了这些信息后，我们使用核心更新公式：

更新完成后，我们让 S \leftarrow S'，A \leftarrow A'，即把新状态和新动作变成当前状态和当前动作，然后继续下一步。这个过程一直持续到 S' 是终止状态为止。

On-Policy：策略的一致性

SARSA算法有一个重要的特性：它是一个on-policy算法。这意味着什么？这意味着我们用来与环境交互的策略（即选择动作的策略）和我们正在评估、改进的策略是同一个。具体来说，我们使用基于Q值的 \varepsilon-贪婪策略来选择动作 A 和 A'，同时我们估计的Q值函数 Q(s, a) 正是这个 \varepsilon-贪婪策略的动作价值函数。

方差问题与改进方案

然而SARSA的估计 R_t + \gamma Q_t(s', a') 存在一个问题：它的方差很高。为什么会有高方差？因为这个估计依赖于单次采样的动作 a'。由于我们使用 \varepsilon-贪婪策略，a' 是随机选择的，而不同的 a' 会导致 Q_t(s', a') 的值差异很大。这种单次采样的随机性会导致估计的不稳定。

那么如何降低这个方差呢？一个改进的思路是：与其只使用单个采样的 Q_t(s', a')，我们可以对所有可能的动作 a' 求期望。具体来说，我们使用：

这里 \pi(a' | s') 是策略 \pi 在状态 s' 选择动作 a' 的概率，也就是我们用来从Q值选择动作的那个策略。通过对所有动作加权求和，我们得到了期望值而不是单次采样值。这个期望值的方差会更小，因为它平均了所有可能动作的影响。虽然这需要计算所有动作的Q值，但在动作空间不太大的情况下，这种额外的计算成本是值得的，因为它能显著提高估计的稳定性和算法的收敛速度。

需要注意的是，这个改进方案中的策略 \pi 仍然是我们用来基于Q值选择动作的那个策略，通常是 \varepsilon-贪婪策略。这样做保持了算法的on-policy特性，只是把对单个后继动作的采样替换为对所有可能后继动作的期望，从而在保持无偏性的同时降低了方差。

机器人在客厅中央 s_1 执行"向前"，到达脏区域 s_2，获得奖励 R=-1。现在需要更新 Q(s_1, \text{向前})。

SARSA的更新方式，在 s_2 按照ε-贪婪策略（\varepsilon=0.2）随机采样一个动作 A'：

在 s_2 按照ε-贪婪策略（\varepsilon=0.2）随机采样一个动作 A'：

第1次采样：采样到"向左探索"

• 更新目标：R + \gamma Q(s_2, \text{向左}) = -1 + 0.9 \times 10 = 8

第2次采样：采样到"清扫"（贪心动作）

• 更新目标：R + \gamma Q(s_2, \text{清扫}) = -1 + 0.9 \times 50 = 44

第3次采样：采样到"向右探索"

• 更新目标：R + \gamma Q(s_2, \text{向右}) = -1 + 0.9 \times 5 = 3.5

同样是从 s_1 向前到达 s_2，由于下一个动作 A' 是随机采样的，更新目标在 3.5 到 44 之间剧烈波动！

因此，不使用单次采样的 Q(s', a')，而是计算所有可能动作的加权平均：

如果动作空间不大（比如机器人只有4个方向），这个额外计算是值得的，因为换来了更低的方差和更快的收敛。

Q-learning算法

Q-learning的基本思想与Off-Policy特性

Q-learning算法由Watkins在1989年提出，它与SARSA最根本的区别在于：Q-learning是一个off-policy算法。这个"off-policy"的含义需要仔细理解：我们在与环境交互时使用一个策略（比如 \varepsilon-贪婪策略，它会进行探索），但我们估计的Q值函数是针对最优策略 \pi^* 的动作价值函数 q^*(s, a)，而不是针对我们实际使用的探索策略。换句话说，我们的目标是学习最优策略应该怎么做，而不是学习当前这个包含随机探索的策略的价值。

这种分离带来了什么好处？它允许我们使用一个探索性的策略来收集数据，同时直接学习最优策略的价值函数。我们不需要等到策略收敛到最优才能得到正确的Q值估计，理论上在探索充分的情况下，即使我们一直使用 \varepsilon-贪婪这样的探索策略与环境交互，Q-learning也能收敛到真实的最优动作价值函数 q^*(s, a)。

Q-learning的更新规则

Q-learning同样使用bootstrap方法，但更新规则与SARSA有关键差异：

注意这里的核心变化：我们不再使用实际选择的下一个动作 a' 对应的 Q_t(s', a')，而是使用 \max_{a'} Q_t(s', a')，即在新状态 s' 中所有可能动作的Q值的最大值。为什么要这样做？因为最优策略的定义就是在每个状态都选择价值最高的动作，所以如果我们要估计最优策略的价值，就应该假设在 s' 状态会选择最优动作，也就是Q值最大的那个动作。

这个 \max_{a'} 操作是Q-learning能够学习最优策略的关键。无论我们在与环境交互时实际选择了什么动作（可能是随机探索的结果），我们的更新都基于最优动作的假设。这就实现了行为策略（behavior policy，用于探索）和目标策略（target policy，要学习的最优策略）的分离。

Q-learning算法的完整流程

Q-learning的算法流程与SARSA相似但更简洁。初始化阶段相同：对所有状态-动作对任意初始化 Q(s, a)，但终止状态的Q值必须设为0。

每个episode开始时初始化起始状态 S。然后在episode的每一步中，我们首先根据Q值使用 \varepsilon-贪婪策略在当前状态 S 中选择动作 A，执行这个动作后观察奖励 R 和新状态 S'。

注意接下来与SARSA的重要区别：我们不需要在新状态 S' 中实际选择下一个动作 A'。我们直接使用更新公式：

这里的 \max_{a'} Q(s', a') 是对所有可能动作求最大值，而不需要实际采样一个动作。更新完成后，我们只需要让 S \leftarrow S'，然后继续循环，直到达到终止状态。

对比SARSA，Q-learning的流程少了 在 S' 中选择 A' 这一步，也不需要更新 A \leftarrow A'。这是因为Q-learning的更新不依赖于下一步实际会采取的动作，而只依赖于理论上的最优动作。

最大化偏差问题（Maximization Bias）

然而Q-learning算法存在一个严重的问题：用同一套Q值既来选择动作又来评估动作，会导致系统性的高估。

Q-learning的更新公式是：

关键在于这个 \max_{a'} Q(s',a') 操作。当Q值估计还不准确时（特别是在学习早期），每个动作的Q值都带有随机误差。这些误差有正有负，但 \max 操作会优先选择那些误差为正、被高估的Q值。

要理解这个问题，让我们通过一个具体例子来说明。

考虑一个简单的环境，有两个状态A和B，以及终止状态。在状态A中，智能体可以选择向右直接到达终止状态（奖励为0），或者选择向左到达状态B（奖励为0）。在状态B中，可以选择多个动作（比如向左），每次执行这些动作会得到随机的奖励，这些奖励的期望值实际上是负的或者接近0的。

让我们追踪Q-learning的更新过程。假设我们从状态A开始，选择向右的动作，获得奖励 R = 0 并到达终止状态。此时更新：

因为没有未来回报。现在重新开始，在A选择向左，获得 R = 0，转移到状态 S' = B。此时的更新需要计算 \max_{a'} Q(B, a')，但由于Q值都初始化为0或接近0，这个最大值也接近0，所以：

接下来在状态B中选择向左的动作，假设这次很幸运得到了正奖励 R = 0.7（虽然这个动作的期望奖励可能是负的，但由于随机性这次得到了正值），到达终止状态。更新为：

现在的关键时刻到了。我们又回到状态A，选择向左，R = 0，转移到 S' = B。这次更新时：

因为 Q(B, \text{left}) = \alpha \cdot 0.7 是当前B状态所有动作Q值的最大值，所以：

也就是说，当我们在状态A选择向左并转移到B时，Q-learning会计算 \max_{a'} Q(B, a')。由于 Q(B, \text{left}) 暂时是最大的（因为那次运气好的采样），max操作就会选中这个被高估的值。这导致 Q(A, \text{left}) 也被高估了，虽然后续采样可能会让 Q(B, \text{left}) 逐渐回归真实值（负数），但在这个过程中，Q(A, \text{left}) 已经受到了影响。但是在B状态可能有很多动作，只要其中任何一个动作在某次采样中运气好得到了高奖励，max操作就会选中它，导致持续的高估。

这就是最大化偏差问题：使用同一组Q值来既选择动作（通过max操作）又评估动作的价值，会导致对价值的系统性高估。

Double Q-learning：解决最大化偏差

为了解决标准Q-learning的最大化偏差问题，我们使用double Q-learning方法。这个方法的核心思想是：把"选择动作"和"评估动作"这两件事交给不同的估计器来做，就能避免偏差。

具体来说，算法同时维护两个独立的Q值估计：Q_1 和 Q_2。这两个估计器是独立训练的，它们对同一个动作的估计误差是不相关的。

首先，使用 Q_1 来决定采取什么动作。这里我们仍然使用基于 Q_1 的 \varepsilon-贪婪策略来保证探索。

其次，在bootstrap更新时使用 Q_2。但关键在于如何使用：我们用 Q_1 来选择在新状态 s' 中哪个动作是"最优"的（即 \arg\max_{a'} Q_1(s', a')），但用 Q_2 来评估这个被选中的动作的价值。

更新公式为：

\arg\max_{a'} Q_1(s', a') 返回的是使 Q_1(s', a') 达到最大值的动作 a'，然后我们用 Q_2(s', a') 来评估这个动作。这样就实现了选择和评估的分离。

为什么这样能减少偏差？因为即使 Q_1 由于随机性高估了某个动作 a'（导致它被 \arg\max_{a'} Q_1(s', a') 选中），Q_2 对同一个动作 a' 的估计是独立的，不太可能也恰好高估同一个动作。因此 Q_2(s', a') 能提供一个相对无偏的评估。

在算法的另一些步骤中，我们交换 Q_1 和 Q_2 的角色：用 Q_2 来选择动作和决定最优动作，用 Q_1 来评估。这种交替更新保证了两个估计都能得到训练，同时避免了单一估计的偏差问题。

机器人在客厅中央 s_1 执行"向前"，到达脏区域附近 s_2。在 s_2 有3个动作可选：

Q-learning使用：

选择最大Q值：

更新目标：

虽然"向左探索"的真实价值只有10，但由于随机性导致Q值被高估到25，Q-learning会选择它作为最优动作，并用这个高估的25来更新 Q(s_1, \text{向前})，这就导致 Q(s_1, \text{向前}) 也被高估了。

Double Q-learning 假设两个Q表的当前估计：

Q_1 表：

Q_2 表：

注意：Q_1 高估了向左（25），但 Q_2 对向左的估计更接近真实（12）。

机器人从 s_1 向前到达 s_2，获得奖励 R=-1。

第1步：用 Q_1 选择最优动作

因为 Q_1(s_2, \text{向左}) = 25 最大。

第2步：用 Q_2 评估这个动作

第3步：更新 Q_1

虽然 Q_1 错误地认为"向左"是最优动作（Q值25），但我们不使用这个高估的25来更新，而是用 Q_2 的独立估计12。因此避免了偏差传播，然后后续中，进行角色互换，这样两个Q 表都能被训练

函数近似与参数化Q值函数

大规模状态空间的挑战

到目前为止，我们学习的SARSA和Q-learning算法都基于一个隐含的假设：状态空间和动作空间的规模是可以接受的，我们可以为每一个状态-动作对 (s, a) 都维护一个独立的Q值 Q(s, a)。这种方法在状态空间较小且离散的情况下工作得很好，比如简单的网格世界或者棋盘游戏。

但现实世界的很多问题远比这复杂。想象一下机器人控制问题，状态可能包含机器人各个关节的角度、速度、位置等连续变量；或者考虑图像作为输入的问题，一张图片就可能有数百万个像素。在这些情况下，状态空间可能是无限大的（如果状态是实数值的），或者虽然有限但大到无法枚举每一个状态。此时，之前学习的查表法（tabular method）——为每个状态-动作对存储一个Q值——变得要么效率极低，要么根本不可能实现。

即使勉强存储了所有状态-动作对的Q值，还有另一个严重问题：泛化能力。假设我们的机器人在关节角度为30.0度时学到了很好的策略，但当角度变成30.1度时，这是一个新的状态，我们对它一无所知。显然，这两个状态应该有相似的最优动作，但查表法无法利用这种相似性，必须重新学习。这导致学习效率极其低下。

参数化模型的核心思想

解决这个问题的关键思想是：不再为每个状态-动作对存储独立的Q值，而是建立一个参数化的模型 Q_{\Theta}(s, a)，用参数向量 \Theta 来表示整个Q函数。这里的 \Theta 是一个包含有限个元素的向量，比如 \Theta = [\Theta_1, \Theta_2, \ldots, \Theta_N]^T。

这个参数化模型本质上是一个函数近似器（function approximator）。我们不再试图精确记住每一个状态-动作对的Q值，而是用一个参数化的函数来近似整个Q函数。这个函数接受状态 s 和动作 a 作为输入，通过参数 \Theta 的某种组合，输出对 Q_{\pi}(s, a) 的估计值。

为什么这样做能解决问题？首先，无论状态空间有多大（甚至是连续的无限空间），我们只需要存储有限个参数 \Theta。其次，这种参数化表示天然具有泛化能力：相似的状态-动作对会通过模型的内在结构产生相似的Q值估计，因为它们共享同一组参数。当我们在某个状态学习时，这个学习信号会通过参数 \Theta 的更新影响到所有相似状态的Q值估计。

线性函数近似

让我们从最简单的参数化形式开始：线性函数近似。在这个模型中，Q函数被表示为：

这个公式的含义是：我们首先定义 N 个特征函数（或称为回归量、基函数）\phi_i(s, a)，每个特征函数将状态-动作对 (s, a) 映射到一个实数。然后用参数 \Theta_i 对这些特征进行线性组合，得到最终的Q值估计。

为什么叫"线性"？因为Q值关于参数 \Theta 是线性的：如果我们把 \Theta_i 翻倍，对应的Q值也会翻倍；如果我们把两组参数相加，得到的Q值等于分别用两组参数计算的Q值之和。这种线性性质使得优化变得相对简单。

特征函数 \phi_i(s, a) 的选择是这个方法的关键。它们扮演着"预处理"的角色，将原始的状态-动作对转换成更适合学习的表示。如果状态 s 和动作 a 都是实数（s \in \mathbb{R}，a \in \mathbb{R}），一个典型的选择是多项式特征。比如我们可以定义：

第一个特征 \phi_1(s, a) = 1 是常数项，对应着Q值的基线或偏置。第二个特征 \phi_2(s, a) = a 捕捉Q值与动作的线性关系。第三个特征 \phi_3(s, a) = s 捕捉Q值与状态的线性关系。第四个特征 \phi_4(s, a) = sa 是交互项，捕捉状态和动作之间的相互作用效应。通过组合这些特征，我们可以表示：

这实际上是一个关于 s 和 a 的多项式。通过调整参数 \Theta，我们可以让这个多项式拟合不同状态-动作对的真实Q值。

神经网络：更强大的函数近似器

虽然线性函数近似简单且易于分析，但它的表达能力受限于特征的选择。如果特征设计不当，线性组合可能无法很好地近似真实的Q函数。这时我们需要更强大的函数近似器，而神经网络正是一个理想的选择。

神经网络可以看作是一个通用的函数近似器。根据通用近似定理，一个足够大的神经网络可以近似任何连续函数。在强化学习中，我们用神经网络来近似Q函数，参数 \Theta 就是神经网络的所有权重和偏置。

但如何设计神经网络的输入输出结构呢？这里有两种主要的架构，它们适用于不同的场景。

神经网络结构一：状态和动作作为输入

第一种结构的设计逻辑很直观：既然我们要估计 Q_{\theta}(s, a)，而Q值取决于状态 s 和动作 a，那就把它们都作为神经网络的输入。从图中可以看到，状态 s 和动作 a 同时输入到神经网络（图中标记为"N.N."），经过若干隐藏层的非线性变换后，输出一个标量值 Q_{\theta}(s, a)。

这个结构特别适合动作空间是连续的情况。因为当动作 a 是连续变量时（比如机器人关节的扭矩，可以取任意实数值），我们无法枚举所有可能的动作。在这种情况下，如果我们想要找到最优动作 a^* = \arg\max_a Q(s, a)，我们可以把 a 看作自由变量，对神经网络的输出关于 a 求导，或者使用梯度上升等优化方法来找到使Q值最大的 a。

这种结构的优势是灵活性：可以为任意的 (s, a) 组合计算Q值。但它也有一个缺点：如果我们需要在某个状态 s 下找到最优动作（这在离散动作空间中是常见需求），我们必须对每一个可能的动作 a 都进行一次前向传播来计算 Q(s, a)，然后比较选出最大的。这在动作空间较大时会很低效。

神经网络结构二：只有状态作为输入

第二种结构采用了完全不同的设计思路。从图中可以看到，神经网络只接受状态 s 作为输入，但有多个输出，每个输出对应一个特定动作的Q值。具体来说，网络有 n 个输出神经元，第 i 个输出神经元的值是 Q_{\theta}(s, a_i)，表示在状态 s 下采取第 i 个动作 a_i 的Q值。

这个结构只适用于离散动作空间，即动作属于一个有限集合 \{a_1, a_2, \ldots, a_n\}。为什么要这样设计？因为在离散动作空间中，一个非常常见的操作是：给定状态 s，找到最优动作 \arg\max_a Q(s, a)，或者计算所有动作的Q值来使用 \varepsilon-贪婪策略。

使用第二种结构，这个操作变得极其高效：我们只需要一次前向传播，就能同时得到所有动作的Q值 Q_{\theta}(s, a_1), Q_{\theta}(s, a_2), \ldots, Q_{\theta}(s, a_n)。然后直接比较这些输出值，就能找到最优动作。这比第一种结构需要 n 次前向传播要高效得多。

这种结构在深度Q网络（DQN）等现代深度强化学习算法中被广泛使用。比如在玩Atari游戏时，输入是游戏画面（状态），输出是所有可能操作（上、下、左、右、开火等）的Q值，网络一次前向传播就能告诉我们应该采取哪个动作。

两种结构的选择本质上反映了一个权衡：第一种结构更通用（可以处理连续动作），第二种结构更高效（对于离散动作）。在实践中，我们根据具体问题的动作空间特性来选择合适的架构。

参数化Q函数的训练方法

损失函数的定义：学习目标的数学表达

现在我们已经有了参数化的Q函数模型 Q_{\Theta}(s, a)，其中 \Theta 代表神经网络的所有权重参数。但问题是：如何确定这些参数的最优值？我们需要一个明确的优化目标，这就引出了损失函数的概念。

损失函数的设计思想是：我们希望参数化的Q函数 Q_{\Theta}(s, a) 能够尽可能准确地逼近真实的Q函数 Q_{\pi}(s, a)。衡量两个函数之间差异的一个自然方式是使用均方误差（Mean Squared Error, MSE）。因此我们定义损失函数为：

这个公式需要仔细理解。首先，Q_{\pi}(s, a) - Q_{\Theta}(s, a) 是真实Q值与我们模型预测值之间的误差。我们对这个误差取平方，这样做有两个好处：一是消除了正负误差相互抵消的问题，二是对大误差施加了更重的惩罚（因为平方函数是凸的）。前面的系数 \frac{1}{2} 是为了数学上的方便，在求导时可以消掉平方带来的系数2。最外层的 \mathbb{E}_{\pi}[\cdot] 表示我们在策略 \pi 产生的状态-动作分布下求期望，因为不同的 (s, a) 对在实际运行中出现的频率是不同的。

我们的优化目标就是找到使损失函数最小的参数：

这个 \hat{\Theta} 就是我们要学习的最优参数。当损失函数达到最小值时，我们的参数化Q函数就最接近真实的Q函数。

梯度下降：迭代优化的基本方法

要找到最优参数 \hat{\Theta}，最常用的方法是梯度下降（gradient descent）。梯度下降的核心思想是：沿着损失函数减小最快的方向更新参数。数学上，这个"减小最快的方向"就是损失函数关于参数的负梯度方向。

首先我们需要计算损失函数的梯度。对 J(\Theta) 关于 \Theta 求偏导：

这个推导过程是这样的：首先对平方项 (Q_{\pi}(s, a) - Q_{\Theta}(s, a))^2 求导，根据链式法则得到 2(Q_{\pi}(s, a) - Q_{\Theta}(s, a)) \cdot \frac{\partial}{\partial \Theta}(-Q_{\Theta}(s, a))，其中系数2与前面的 \frac{1}{2} 相消，负号提出来后变成 (Q_{\pi}(s, a) - Q_{\Theta}(s, a)) \cdot (-1) \cdot \frac{\partial Q_{\Theta}(s, a)}{\partial \Theta}。但通常我们在写梯度下降公式时会明确考虑负号，所以这里先写成正的形式。期望算子 \mathbb{E}_{\pi} 可以与求导交换顺序，因为求导是关于 \Theta 的，而期望是关于 (s,a) 的分布。

有了梯度，我们就可以进行梯度下降迭代：

这个公式表示：在第 t 步，我们计算当前参数 \Theta_t 处的梯度，然后沿着梯度的反方向（负梯度方向）移动一小步。步长由学习率 \alpha 控制。如果 \alpha 太大，可能会越过最优点导致震荡甚至发散；如果 \alpha 太小，收敛会非常缓慢。

实际应用中的三大困难

理论上梯度下降方法看起来很完美，但在实际应用中我们面临三个严重的困难，每一个都需要特殊的技巧来解决。

第一个困难是学习率 \alpha 的选择问题。这不仅仅是一个超参数调优的问题，而是一个根本性的挑战。在强化学习中，损失函数的landscape（地形）是非平稳的——随着策略的改进，数据分布在变化，目标函数本身也在变化。一个固定的学习率很难在整个训练过程中都保持合适。太大会导致训练不稳定，太小会导致训练过慢甚至陷入局部最优。

第二个困难更加根本：Q_{\pi}(s, a) 是未知的。这听起来很矛盾——我们的目标是让 Q_{\Theta}(s, a) 逼近 Q_{\pi}(s, a)，但我们连 Q_{\pi}(s, a) 的真实值都不知道！如果知道真实的Q值，我们就可以直接用监督学习的方式训练，但问题恰恰在于我们不知道。这就像是在没有标准答案的情况下学习，我们必须通过与环境的交互来估计这个"标准答案"。

第三个困难是期望 \mathbb{E}_{\pi}[\cdot] 难以准确计算。这个期望是在策略 \pi 产生的所有可能的状态-动作对上求的，而状态空间可能非常大甚至是连续的。我们不可能枚举所有可能的 (s, a) 来计算精确的期望值。即使能枚举，计算每一项也需要知道该状态-动作对在分布中的概率，而这个分布本身就是未知的。

用采样替代期望：随机梯度下降的思想

解决第三个困难的关键思想是：用采样来替代期望。这基于一个统计学的基本原理——大数定律：如果我们从某个分布中独立采样足够多次，样本的平均值会收敛到真实的期望值。

在我们的情况下，期望 \mathbb{E}_{\pi}[\cdot] 是在策略 \pi 产生的分布下求的。当我们用策略 \pi 与环境交互时，我们自然地从这个分布中采样。因此，我们可以用单次采样的值来近似期望：

这里等号右边没有了期望符号，而是用当前采样到的 (s, a) 对来计算。这种用单个样本（或小批量样本）来近似梯度的方法叫做随机梯度下降（Stochastic Gradient Descent, SGD）。虽然单次采样的梯度估计会有很大的噪声（方差），但只要期望是正确的（即估计是无偏的），多次迭代后仍然能收敛到最优值。

用Bootstrap估计Q值：解决未知目标问题

现在来解决第二个更根本的困难：如何估计未知的 Q_{\pi}(s, a)？这里我们再次使用bootstrap的思想，这与SARSA算法的思路完全一致。

假设我们通过策略 \pi 与环境交互，获得了一个经验样本（experience）(s, a, r, s')：在状态 s 采取动作 a，获得奖励 r，转移到新状态 s'。根据Q函数的定义，Q_{\pi}(s, a) 应该等于即时奖励加上后续所有奖励的折扣和的期望。我们可以用 r 作为即时奖励的估计（这是精确的，因为 r 就是实际观察到的奖励），用当前的参数化Q函数来估计未来回报。

如果我们要估计的是某个特定策略 \pi 的Q值，那么在新状态 s' 中，我们应该按照策略 \pi 来选择后续动作，因此：

这个公式的含义是：用实际的奖励 r 加上对未来回报的估计。未来回报的估计方法是：对所有可能的下一步动作 a'，用策略 \pi 的概率 \pi(a'|s') 加权求和它们的Q值 Q_{\Theta}(s', a')。这实际上是在用当前的参数化Q函数 Q_{\Theta} 来bootstrap地估计真实的Q函数 Q_{\pi}。

另一方面，如果我们要估计的是最优策略的Q值（即 Q^*），那么我们应该假设在 s' 中会选择最优动作，因此：

这里不再对所有动作求期望，而是直接取最大值，因为最优策略就是总是选择Q值最大的动作。这正是Q-learning的思想。

自动微分：现代深度学习的基础工具

在得到了梯度的表达式后，我们需要计算 \frac{\partial Q_{\Theta}(s, a)}{\partial \Theta}。当 Q_{\Theta} 是一个深度神经网络时，手工计算这个梯度几乎是不可能的——一个现代神经网络可能有数百万甚至数十亿个参数，网络结构复杂，涉及大量的矩阵乘法、非线性激活函数等操作。

幸运的是，现代深度学习框架如PyTorch和TensorFlow提供了自动微分（automatic differentiation）功能。自动微分基于链式法则，能够自动计算任意复杂计算图的梯度。我们只需要定义前向传播的计算过程（即如何从输入 (s, a) 和参数 \Theta 计算输出 Q_{\Theta}(s, a)），框架就能自动计算反向传播的梯度。

这极大地简化了深度强化学习算法的实现。我们不需要关心梯度的具体计算细节，只需要专注于算法逻辑本身。当我们计算损失函数并调用反向传播时，框架会自动计算所有参数的梯度，然后我们就可以用这些梯度来更新参数。

经验回放：提高样本效率和训练稳定性

到目前为止，我们还没有充分解决期望难以计算的问题。虽然我们可以用单个样本来近似梯度，但这样做方差很大，训练会很不稳定。更重要的是，强化学习中的数据获取是昂贵的——每个样本都需要与环境进行一次真实的交互。如果我们每个样本只使用一次就丢弃，样本效率会很低。

经验回放（experience replay）机制正是为了解决这些问题而设计的。其核心思想是：在与环境交互的过程中，我们把观察到的经验样本 (s, a, r, s') 存储在一个回放缓冲区（replay buffer）\mathcal{D} 中。这个缓冲区可以看作是一个数据库，记录了智能体的历史经验。

当我们需要更新参数时，不是只用最新的一个样本，而是从回放缓冲区 \mathcal{D} 中随机采样一个子集 \mathcal{D}' \subset \mathcal{D}（通常称为mini-batch），用这个子集来近似期望。具体来说，梯度的估计变成：

这个公式对应于on-policy的情况（如SARSA）。对于off-policy的情况（如Q-learning），公式变为：

这两个公式的结构是相同的，只是对未来Q值的估计方式不同：前者用策略的期望，后者用最大值。

经验回放带来了多个重要好处。首先，它大大提高了样本效率——每个样本可以被使用多次（每次更新参数时都可能被采样到）。其次，它打破了样本之间的时间相关性——连续的样本往往高度相关（因为状态之间有转移关系），这种相关性会导致训练不稳定，而随机采样可以得到更独立的样本。第三，它使得我们可以用更大的batch size来估计梯度，降低估计的方差，使训练更稳定。

数据收集与存储的过程

在实际运行中，经验回放的使用流程是这样的。当智能体在环境中采取动作 a，观察到奖励 r 和新状态 s' 后，我们把这个四元组 (s, a, r, s') 添加到回放缓冲区中：

这个操作持续进行，缓冲区不断累积经验。通常回放缓冲区有一个最大容量限制，当缓冲区满了之后，新的经验会覆盖最旧的经验（先进先出，FIFO）。这样做既能保持足够多的历史经验用于训练，又能让缓冲区中的数据保持相对新鲜，反映当前策略的行为。

这种将数据收集和参数更新分离的机制，是现代深度强化学习（如DQN）取得成功的关键技术之一。它使得算法能够充分利用宝贵的交互数据，同时保持训练的稳定性。

上面所有内容用一句话总结，我们用神经网络来预测Q值，用梯度下降来调整参数，用采样来代替期望，用bootstrap来估计真实 Q 函数，用经验回放来提高效率和稳定性。

Neural Fitted Q-learning算法

算法初始化

算法开始时需要进行两项初始化工作。首先，我们用随机参数 \Theta 来初始化参数化的Q函数：

这个随机初始化为学习提供了起点。虽然初始的Q值估计完全不准确，但这正是学习过程的开始，网络将通过与环境的交互逐步改进这些估计。

同时，我们初始化一个空的经验回放缓冲区：

这个缓冲区将在后续过程中不断积累智能体与环境交互产生的经验样本。

Episode循环开始

算法的主体是一个episode级别的外层循环。对于每一个episode，我们执行以下过程。

首先设置起始状态：

这个初始状态 s_0 由环境提供，标志着新一轮交互的开始。

单步交互循环

接下来进入一个内层循环，只要当前状态 s 不是终止状态，我们就持续执行以下步骤。

步骤1：动作选择

使用基于当前Q函数 Q_{\Theta}(s, a) 的 \varepsilon-贪婪策略来选择动作。这个策略在利用当前知识和探索未知可能之间取得平衡：以 1-\varepsilon 的概率选择Q值最大的动作（利用），以 \varepsilon 的概率随机选择动作（探索）。

步骤2：执行动作并观察结果

在环境中执行选定的动作 a，然后观察获得的即时奖励 r 和转移到的新状态 s'。

步骤3：存储经验

将观察到的经验四元组存入回放缓冲区：

这一步持续积累智能体的交互经验，为后续的训练提供数据基础。

构建监督学习数据集

在收集了一定的经验后，我们开始构建用于训练的监督学习数据集。这个数据集记为：

构建过程如下：

步骤4：采样mini-batch

从回放缓冲区 \mathcal{D} 中选择一个子集 \mathcal{D}' \subset \mathcal{D}。这个子集通常是固定大小的，比如包含32或64个样本。同时初始化样本索引 i = 1。

步骤5：遍历采样的经验

对于子集 \mathcal{D}' 中的每一个经验样本 (s, a, r, s')，我们构建训练数据对 (x^{(i)}, y^{(i)})。

首先设置输入：

这里输入只是状态 s，因为我们使用的神经网络结构是：输入状态，输出该状态下所有动作的Q值。

然后根据新状态 s' 是否为终止状态，分两种情况设置目标输出 y^{(i)}：

情况A：如果 s' 是终止状态

此时episode已经结束，没有未来回报。对于实际采取的动作 a，目标Q值设为：

对于所有其他未采取的动作 a' \neq a，目标Q值设为当前网络的预测值：

情况B：如果 s' 不是终止状态

此时还有未来回报需要考虑。对于实际采取的动作 a，使用Q-learning的bootstrap目标：

这里 r 是即时奖励，\gamma \max_{a'} Q_{\Theta}(s', a') 是对未来最优回报的估计。我们用当前网络在新状态 s' 上所有可能动作的Q值的最大值来近似未来回报，这体现了Q-learning假设未来会采取最优动作的思想。

对于所有其他未采取的动作 a' \neq a，同样设为当前预测值：

这种设计确保只有实际采取的动作 a 的Q值会被更新，其他动作的Q值保持不变，因为我们没有关于它们的新信息。

完成一个样本的构建后，让索引增加：i = i + 1，继续处理下一个经验样本。

参数更新

步骤6：梯度下降更新

构建完整个训练数据集 \mathcal{T} 后，使用标准的梯度下降方法更新神经网络参数 \Theta。具体来说，我们计算所有训练样本上预测值与目标值的均方误差作为损失函数，然后通过反向传播算法计算梯度，最后沿着梯度的负方向更新参数。现代深度学习框架（如PyTorch或TensorFlow）会自动完成梯度的计算和参数的更新。

状态转移

步骤7：更新当前状态

参数更新完成后，让当前状态变为新状态：

然后返回到单步交互循环的开始，继续下一轮的动作选择、执行、经验存储和参数更新。这个过程不断重复，直到当前episode结束（即到达终止状态），然后开始下一个episode。通过这种持续的交互-学习循环，Q函数的估计逐渐接近真实值，策略也随之改进。

第六部分：Deep Q-learning (DQN)算法

NFQ算法的固有缺陷：最大化偏差问题

在前面我们学习了Neural Fitted Q-learning算法，它成功地将神经网络与Q-learning结合起来。然而，NFQ算法存在一个严重的问题：它继承了标准Q-learning的最大化偏差（maximization bias）。这个问题的根源在于NFQ在构建训练目标时使用了Q-learning风格的bootstrap。

回顾一下NFQ中非终止状态的目标值构建：

这里的问题在于：我们用同一个网络 Q_{\Theta} 既来选择最优动作（通过 \max 操作），又来评估这个动作的价值。当Q值的估计存在噪声时（这在学习早期是必然的），\max 操作会系统性地选中那些被高估的动作。即使所有动作的真实价值都差不多，由于估计的随机性，总会有一些动作的估计值偏高，而 \max 会选中这些被高估的值，导致目标值也被高估。这种高估会通过bootstrap传播：当前状态的Q值基于被高估的下一状态Q值来更新，结果当前状态的Q值也被高估了。这种高估会在整个状态空间中累积和传播，严重影响学习的质量和策略的性能。

Deep Q-learning的目标网络机制

Deep Q-learning（通常简称DQN）由Mnih等人在2015年提出（实际上最初版本是2013年，2015年是在Nature上发表的改进版本），它不仅继承了NFQ的所有核心技术（随机梯度下降、bootstrap、经验回放），还引入了一个关键的创新来缓解最大化偏差问题：使用两个神经网络而不是一个。

第一个网络记为 Q_{\Theta}，称为主网络（main network）或在线网络（online network）。它用于两个目的：第一，在与环境交互时通过 \varepsilon-贪婪策略来选择动作；第二，作为被训练的对象，参数 \Theta 会通过梯度下降频繁更新。

第二个网络记为 Q_{\Theta'}，称为目标网络（target network）。它的结构与主网络完全相同，但参数 \Theta' 的更新频率要低得多。目标网络专门用于计算bootstrap中的目标值，即计算 \max_{a'} Q_{\Theta'}(s', a')。

这样动作选择和价值评估的部分分离。虽然DQN还不是完全的双Q-learning（完全的双Q-learning会用一个网络选择动作，用另一个网络评估该动作），但通过让目标网络的更新滞后于主网络，我们在一定程度上降低了"用自己的估计强化自己的偏差"的问题。目标网络提供了一个相对稳定的参照点，避免了追逐快速变化的移动目标。

DQN算法的初始化阶段

DQN算法从三项初始化工作开始。首先，初始化一个空的经验回放缓冲区：

这与NFQ完全相同，缓冲区将用来存储所有的交互经验。

其次，用随机参数 \Theta 初始化主网络：

这个随机初始化打破对称性，为学习提供起点。

第三，这是DQN特有的步骤：将目标网络的参数初始化为主网络参数的拷贝：

这意味着训练开始时，两个网络是完全相同的。但在后续的训练过程中，它们会逐渐产生差异：主网络的参数 \Theta 会频繁更新，而目标网络的参数 \Theta' 会保持不变，只在特定的时刻才被更新为主网络的参数。

Episode级别的主循环

与NFQ类似，DQN的主体是一个episode级别的循环。每个episode开始时，设置初始状态：

然后进入内层循环，只要当前状态不是终止状态，就持续执行交互-学习的步骤。

交互步骤：选择动作并观察结果

在每一步中，首先使用基于主网络 Q_{\Theta} 的 \varepsilon-贪婪策略来选择动作 a。注意这里用的是主网络而不是目标网络，因为主网络代表了我们当前最新的知识和策略。

选定动作后，在环境中执行这个动作，观察获得的奖励 r 和新状态 s'。然后将这个经验四元组存入回放缓冲区：

这些步骤与NFQ完全相同，体现了数据收集的一致性。

构建训练数据集：引入目标网络

接下来构建监督学习数据集 \mathcal{T} = \{(x^{(i)}, y^{(i)})\}。首先从回放缓冲区 \mathcal{D} 中采样一个子集 \mathcal{D}' \subset \mathcal{D}，并初始化样本索引 i = 1。

对于子集中的每个经验样本 (s, a, r, s')，构建训练数据对的方式与NFQ类似，但有一个关键区别。输入仍然是状态：

目标输出的构建分两种情况：

如果新状态 s' 是终止状态，则对于采取的动作 a：

对于其他动作 a' \neq a：

这部分与NFQ相同，因为终止状态没有未来回报，不需要bootstrap。

但如果 s' 不是终止状态，这里出现了关键的不同。对于采取的动作 a，目标值变成：

注意这里使用的是目标网络 Q_{\Theta'} 而不是主网络 Q_{\Theta}。这是DQN与NFQ的核心区别。我们用目标网络来计算bootstrap目标，而不是用正在训练的主网络。这样做的好处是目标值相对稳定：在两次目标网络更新之间的所有训练步骤中，对于相同的 (s', a')，目标网络给出的 Q_{\Theta'}(s', a') 是固定的，不会因为主网络的更新而改变。

对于其他未采取的动作 a' \neq a，仍然使用主网络的当前预测：

这保证了只有实际采取的动作的Q值会被更新。

参数更新：只更新主网络

构建完训练数据集 \mathcal{T} 后，使用梯度下降来更新主网络的参数 \Theta。注意这里只更新主网络，目标网络的参数 \Theta' 保持不变。通过最小化预测值 Q_{\Theta}(s, a) 与目标值 y^{(i)}(a) 之间的均方误差，主网络逐渐学习到更准确的Q值估计。

更新完成后，让当前状态变为新状态：

然后继续下一步的交互和学习循环。

周期性更新目标网络

DQN的最后一个关键机制是：每隔 P 个episode（或者每隔 P 个时间步，具体取决于实现），执行一次目标网络的更新：

这个操作简单地将主网络的当前参数拷贝给目标网络。通过这种方式，目标网络能够"跟上"主网络的学习进度，但又不会跟得太紧。在两次更新之间的 P 个episode（或步骤）中，目标网络保持固定，提供稳定的训练目标。

这个更新频率 P 是一个重要的超参数。如果 P 太小，目标网络更新太频繁，就失去了稳定训练目标的作用，退化为类似NFQ的情况。如果 P 太大，目标网络会过于陈旧，与主网络的差距太大，导致训练目标不准确，学习效率降低。在实践中，P 通常设置为几千到一万个时间步，或者几十到几百个episode，具体取决于问题的复杂度和训练的总步数。

DQN的改进效果与深层意义

通过引入目标网络机制，DQN在实践中表现出比NFQ更好的稳定性和性能。虽然它没有完全消除最大化偏差（那需要真正的double Q-learning），但目标网络提供的稳定性大大改善了训练过程。Mnih等人用DQN在多个Atari游戏上达到了超越人类的表现，这标志着深度强化学习的真正突破。

DQN的成功不仅在于具体的技术创新，更在于它证明了深度神经网络可以作为强大的函数近似器应用于强化学习。它将深度学习的表示学习能力与强化学习的决策优化能力结合起来，开创了深度强化学习这一新的研究领域。此后的许多算法，如Double DQN、Dueling DQN、Rainbow等，都是在DQN的基础上进行改进，进一步提升了算法的性能和稳定性。