有限马尔可夫决策过程

本章我们将学习有限马尔可夫决策过程（finite Markov decision processes, 简称有限MDPs）的形式化问题（classical formalization）。我们将在本书的其余部分尝试解决该问题。

MDPs是对序列决策制定（sequential decision making）的一种经典形式化方法，其中的动作不仅影响即时的奖励，还会影响后续的情境或状态，并通过这些未来的奖励产生影响。因此，MDPs涉及延迟奖励，并且需要在即时奖励与延迟奖励之间进行权衡。

在赌博机问题中，我们估计每个动作\(a\)的值\(q_*(a)\)；而在MDPs中，我们估计在每个状态\(s\)下每个动作\(a\)的值\(q_*(s,a)\)，或者在给定最优动作选择的情况下的值\(v_*(s)\)。这些与状态相关的量对于准确地将长期后果归因于个体动作选择是至关重要的。

值得注意的是，MDPs是强化学习问题的一种数学理想化形式。在本章中，我们将学习一些可以被建模为有限MDPs的广泛应用种类。在人工智能领域，广泛适用性和数学可处理性之间存在一种张力（tension），我们将在本章了解这种张力，并讨论它所带来的权衡与挑战。

---

3.1 智能体-环境接口

MDPs旨在构建一个框架，用于解决通过交互学习来实现目标的问题（learning from interaction to achieve a goal）。本节标题“The Agent-Environment Interface”（智能体-环境接口）就是描述智能体和环境之间如何交互的标准方式。Interface在这里指的是该框架定义了：谁负责什么、信息流的走向、如何正式建模强化学习等，是一套规范。

学习者（learner）和决策者（decision maker）被称为智能体（agent）；智能体所交互的对象，包括除了智能体之外的一切，被称为环境（environment）。

如上图所示，智能体和环境持续交互：智能体选择动作（action），环境对这些动作作出反应并向智能体呈现新的情境（即状态 state）。环境还会产生奖励（reward），即一些特殊的数值，这些数值是智能体希望随着时间的推移通过其动作选择来最大化的。

我们把这个过程复述一遍：在每个时间步t，agent接收到环境状态St的某种表示，基于这种状态，agent选择了动作At。接着，在时间步t之后，agent完成了这个动作，时间步进入t+1，而环境会根据t的动作返回一个奖励\(R_{t+_1}\)，并将其写入新的状态\(S_{t+1}\)。该轨迹（trajectory）如下：

\[ S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, \dots \\ \tag{3.1 交互序列} \]

---

在有限MDP中，状态集合 \(\mathcal{S}\)、动作集合 \(\mathcal{A}\)、奖励集合 \(\mathcal{R}\)都是有限的元素集合。在这种情况下，随机变量Rt和St的分布是离散的，且仅依赖于前一个动作和状态，因此可以得到四参数的\(p\)函数：

\[ \underbrace{p(s', r \mid s, a)}_{\text{四参数函数}} \overset{\text{定义}}{\doteq} \underbrace{\Pr\{S_t = s', R_t = r \mid S_{t-1} = s, A_{t-1} = a\}}_{\text{条件概率表示}} \]

\[ \underbrace{p : \mathcal{S} \times \mathcal{R} \times \mathcal{S} \times \mathcal{A} \to [0, 1]}_{\text{函数类型：输入四个变量，输出概率值}} \]

\[ \tag{3.2 MDP的动态函数 / 四参数p函数} \]

该函数即MDP的动态函数（dynamics of the MDP），一般简称为\(p\)函数或四参数形式的\(p\)函数，是本书中使用较多的形式。

---

由于上述所示的四参数函数\(p(s',r|s,a)\)是一个联合概率分布，因此对于每一对状态-动作对\((s,a)\)，其对应的所有可能的下一状态\(s'\)和奖励\(r\)的联合概率之和必须等于1：

\[ \sum_{s' \in \mathcal{S}} \sum_{r \in \mathcal{R}} p(s', r \mid s, a) = 1 \quad \forall s \in \mathcal{S},\ a \in \mathcal{A}(s) \\ \tag{3.3 MDP动态函数的规范性条件} \]

对于忘记概率论知识点的同学，这里回顾一下联合概率分布：联合概率分布（joint probability distribution）描述的是两个或多个随机变量同时取某些值得概率，比如如果你同时投硬币和掷骰子，那么P(正面, 结果=3)就是一个联合概率。所以对于上面的3.3式，就是在给定状态s和a后，即智能体针对状态s做出动作a后，环境反馈的新的状态s'和反馈的奖励r的联合出现的概率。至于为什么等于1，这就像你投骰子和掷硬币的时候，两面的情况和6种骰子结果全部组合起来，一定代表了全部的情况，即总概率100%。

同时，我们也能看出，在马尔可夫决策过程中，系统的未来状态只取决于当前的状态和动作，而不依赖于更早之前的状态或动作，这种特性叫做马尔可夫性质（Markov property）。这个性质非常重要，因为它反映了一种对“状态”的限制条件：状态必须包含所有能影响未来结果的信息。在本书的大部分内容中，特别是在涉及近似方法（approximation methods）之前，将默认状态具有马尔可夫性质。

我们必须重视马尔可夫性质，因为如果马尔科夫性质不成立，那么基于马尔可夫决策过程设计的算法（比如Q-learning, Policy Gradient, DQN）对当前状态的估计就会出错，学到的策略就会失效，后果就会非常严重。这里我们来举例说明一下：

序号	状态描述	是否满足马尔可夫性	理由简述
1	棋盘当前局面（如围棋、国际象棋）	✅ 是	当前局面已包含所有对胜负有用的信息，无需过去记录
2	迷宫中当前坐标位置	✅ 是	坐标已足够描述位置决策所需信息
3	当前帧图像（无历史）	❌ 否	缺少速度、方向等信息，不能判断动态行为
4	当前帧图像 + 上一帧图像	✅（近似）	差分图像可估计速度，能较好近似马尔可夫性
5	股票当前价格	❌ 否	价格序列中趋势依赖过去信息，当前价格不足以判断未来走势
6	最近 10 天的股票价格序列	✅（近似）	包含了一定的历史上下文，可近似地作为马尔可夫状态
7	游戏角色的血量 + 位置 + 敌人状态	✅ 是	包含全部决策相关的当前信息
8	仅玩家血量（无位置、敌人信息）	❌ 否	状态信息不全，未来不确定
9	智能体上一步的观察和动作（无当前观察）	❌ 否	没有当前状态，无法准确预测下一步
10	当前传感器读数 + 内部隐状态（如LSTM的隐藏层）	✅（近似）	包含一定记忆能力，适用于部分可观察环境，增强了马尔可夫性

了解了马尔可夫性质后，如果我们想只关注联合概率中的一个变量，那么我们就可以关注其边缘概率（marginal probability）。

如果我们对奖励\(r\)进行边缘化，只保留状态转移\(s'\)的概率，则可以得到状态转移概率函数（state-transition probabilities）：

\[ \underbrace{p(s' \mid s, a)}_{\text{状态转移概率函数}} \doteq \Pr\{S_t = s' \mid S_{t-1} = s, A_{t-1} = a\} = \underbrace{\sum_{r \in \mathcal{R}} p(s', r \mid s, a)}_{\text{边缘化联合概率，消去奖励}} \]

\[ \underbrace{p : \mathcal{S} \times \mathcal{S} \times \mathcal{A} \to [0, 1]}_{\text{函数类型：输入三个变量，输出概率值}} \]

\[ \tag{3.4 MDP的状态转移概率函数} \]

---

接着，我们需要关注，当agent在状态s下选择动作a后，期望获得的奖励是多少。这个值并非实际奖励，而是长期来看执行该动作后会获得的期望值。一般我们使用状态-动作对（state-action pairs）的期望奖励函数\(r : \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}\)

\[ r(s, a) \doteq \mathbb{E}[R_t \mid S_{t-1} = s, A_{t-1} = a] = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} r \cdot p(s', r \mid s, a) \]

\[ \tag{3.5 “状态-动作”对的期望奖励函数} \]

这个公式非常重要，是策略评估中的核心组成部分。由于很多时候我们只关心期望奖励而非奖励的具体分布，此时这个公式就提供了一个非常便捷的计算。比如在值函数中，我们常常需要使用这个期望奖励：（这个公式之后会讲到，这里只是提前拿出来说明一下期望奖励函数的重要性）

\[ V(s) = \sum_a \pi(a \mid s) \left[ \underbrace{r(s, a)}_{\text{就是这个！}} + \gamma \sum_{s'} p(s' \mid s, a) V(s') \right] \]

---

同理，也可以计算“状态-动作-下一个状态”三元组的期望奖励（expected rewards for state-action-next_state triples as a three-argument function）\(r : \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}\)：

\[ r(s, a, s') \doteq \mathbb{E}[R_t \mid S_{t-1} = s, A_{t-1} = a, S_t = s'] = \sum_{r \in \mathcal{R}} r \cdot \frac{p(s', r \mid s, a)}{p(s' \mid s, a)} \]

\[ \tag{3.6 “状态-动作-下一个状态”三元组的期望奖励函数} \]

---

以上即是MDP框架的主要的几个公式，其中3.2的四参数p函数在本书中出现较多，其他公式也都有涉及。

MDP框架的优点在于其灵活性，比如说：时间步不一定必须是真实的时间变化，也可以是决策过程中的任意连续阶段；动作可以是低层次的电压控制，也可以是高层次的决策比如是否去读研究生；状态可以是低层次的传感器，也可以是高层次的比如说房间中的物体的符号性描述，甚至还可以是完全主观的或者心理的内容。一些动作可能完全是心理上的，也可能控制智能体选择去思考什么。

通常来说，动作可以是我们想要学习如何做出的任何决策，而状态可以是我们已知的、在做出决策时可能有用的任何信息。特别值得注意的是，智能体与环境之间的边界通常不是机器人或动物体的物理边界，而是一个更加靠近智能体自身的边界。比如说，机器人的马达、机械部分、传感器等硬件，通常应被视为环境的一部分。类似的，人类的骨骼、肌肉、感官器官等也应被视为是环境的一部分。奖励也是这样的，在MDP中被视为环境的组成部分，即使直观上来看似乎并不是环境的一部分。

我们一般遵从这样一个原则：任何智能体不能任意改变的东西，都应该被认为在它之外，是环境的一部分。（anything that cannot be changed arbitrarily by the agent is considered to be outside of it and thus part of its environment）

我们并不假设环境中的一切对智能体而言都是未知的。智能体知道奖励及奖励相关的计算过程，但我们必须将奖励计算看作智能体之外的内容，因为奖励定义了智能体所面临的任务，必须超出智能体随意改变的能力范围。

这里看起来很绕，举个例子就是：假设智能体要去解决魔方问题，而魔方怎么运作显然是一目了然的，但是这却是一个困难的强化学习任务。因此，智能体-环境边界（agent-environment boundary）代表的不是其知识（knowledge）的边界，而是智能体绝对控制（absolute control）的边界。

智能体-环境边界可以根据具体的问题具体分析设置，在复杂的问题中，多个智能体同时操作并保有自己的边界。例如，一个智能体可以做出高层次的决策，而这些决策所对应的状态是由另一个低层次的智能体感知并提供的。在实际操作中，智能体-环境边界是根据我们选定的状态、动作和奖励来确定的，从而定义了一个具体的决策学习任务（a specific decision-making task）。

MDP框架是对通过交互实现目标导向的学习问题的一种高度抽象表达。它提出：不论感知、记忆和控制机制的具体细节如何，也不论目标是什么，任何目标导向的学习行为都可以被简化为三类信号在智能体和环境之间来回传递：

• 一个信号表示智能体做出的选择，即动作 action
• 一个信号表示智能体做选择的依据，即状态 state
• 一个信号定义智能体的目标，即奖励 reward

这个框架可能不足以表示所有的决策学习问题，但已被证明是广泛实用和适用的。在强化学习中，不同任务中的具体状态和动作差异巨大，它们的表示方式会极大地影响学习效果，因此有时候这些表示选择（representational choices）更像是一门艺术而不是一门科学。

下面给出一些例子：

任务/目标	动作	状态	奖励
自动驾驶安全抵达	转向、加速、刹车	当前位置、速度、前方障碍物、红绿灯状态	是否避障、安全驾驶、是否到达终点
玩超级马里奥游戏	向左/右移动、跳跃、攻击	当前画面信息、角色位置、敌人位置	得分、击败敌人、通过关卡
股票自动交易	买入、卖出、持有	历史价格趋势、技术指标、账户余额	投资收益（利润或亏损）
聊天机器人持续对话	回复一句话	上下文、当前输入、情感状态	用户满意度、保持对话
机械臂抓取物体	旋转关节、闭合夹爪	摄像头画面、目标位置、夹爪位置	成功抓起物体
清洁机器人覆盖房间	前进、转向、启动吸尘	当前地图位置、剩余电量、周围障碍物	每覆盖新区域得分
推荐系统提高点击率	推荐一个视频/商品	用户画像、历史行为、当前时间	用户是否点击或购买
无人机自主导航	上升、下降、向前、转向	当前高度、障碍位置、目标坐标	是否靠近目标、是否避开障碍
教育平台个性化教学	推送题目、提供提示、切换难度	学生答题记录、当前知识点、时间投入	学生成绩提升、持续学习时长
医疗诊断建议优化	推荐检查、建议治疗	患者病史、症状、检验结果	治疗效果提升、减少误诊

在本书中，我们会提供一些关于如何良好表示状态和动作的建议和示例，但我们的主要关注点在于：在状态与动作的表示方式已经确定之后，如何学习正确的行为策略。

书中还给出了三个较为详细的例子，分别是Example 3.1 生物反应器，Example 3.2 抓取-放置机器人，Example 3.3 回收机器人。例3.3比较长，详细介绍说明了如何将一个真实问题建模为一个有限MDP。

在例3.3中，作者展示了一种叫做transition graph（转移图）的结构，这种结构在离散数学和图论中有所涉及，感兴趣的同学可以自行查阅图论中的有向图、状态转移图等内容。图论可以帮助建模，但是没学过的话对学习强化学习也没有大的影响，毕竟CS科目那么多，能学精一个方向就算有很大的收获了。

Exercise 3.1 - 3.4见附录部分。

---

3.2 目标和奖励

在强化学习中，智能体的目标（goal）是通过奖励（reward）来形式化的。奖励是一个特殊信号，从环境传递给智能体。在每一个时间步，奖励是一个简单的数字，记为\(R_t \in \mathbb{R}\)。这个概念是强化学习的一个标志性特色。

非正式地说，智能体的目标是最大化其获得的总奖励。换句话说，智能体想要最大化的是长期的累积奖励而非即时奖励。这就是奖励假设（reward hypothesis）：

That all of what we mean by goals and purposes can be well thought of as the maximization of the expected value of the cumulative sum of a received scalar signal (called reward).

我们所说的所有目标与意图，都可以很好地被理解为最大化某个接收的标量信号（即奖励）累积和的期望值。

在实践中，这种方式非常适用且普遍。书中举了一些已经或可能被使用的例子：

• 为了让机器人学会行走，研究人员会在每一个时间步根据机器人的前进速度给予奖励。
• 为了让机器人学会如何从迷宫中逃脱，奖励通常是每经过一个时间步就给予 -1；这促使机器人尽可能快地逃脱。
• 为了让机器人学会寻找并收集空的易拉罐进行回收，可以大部分时间给予 0 的奖励，只有在收集到一个易拉罐时给予 +1 的奖励。
• 我们还可以为机器人设计负面奖励，比如当它撞到东西或者被人责骂时扣分。
• 对于学习玩跳棋或国际象棋的智能体，自然的奖励方式是：胜利得 +1，失败得 -1，平局和非终止状态得 0。

在这些例子中，智能体总是学会了最大化它的奖励。如果我们想让智能体为我们做某些事情，我们必须以某种方式设置奖励，使得在智能体最大化奖励的过程中，也实现了我们的目标。

因此，关键在于如何设置奖励，如何让奖励准确反映我们的目标。值得注意的是，奖励信号不是用来向智能体传达关于如何实现我们目标的先验知识（prior knowledge）的。例如，对于一个下棋的智能体，我们应当只在其实际获胜时给予奖励，而不是在它实现某些子目标时（比如吃子）就给予奖励。如果这些子目标被奖励，那么智能体可能会招到一些方法去实现这些子目标，而忽视了真正的目标。比如，它会找到能快速吃子的方法，但却导致输掉比赛。

所以，奖励信号是你用来告诉智能体“你希望它实现什么”的，而不是告诉它“你应该怎么做”。在设置奖励信号时，你应该关注于你想要实现什么目标，而不是纠结于如何让智能体去实现那个目标。

---

3.3 Returns and Episodes

智能体的目标是在长期内最大化其获得的累积奖励（cumulative reward），那么这一目标如何形式化定义呢？我们把时间步t之后接收到的奖励记为\(R_{t+1},R_{t+2},R_{t+3},...\)，那么我们希望得到的最大化的期望回报（expected return）\(G_t\)就是：

\[ G_t \doteq R_{t+1} + R_{t+2} + R_{t+3} + \cdots + \underbrace{R_T}_{\text{终止时间步}} \]

\[ \tag{3.7} \]

终止时间步（final time step）表明上式存在一个明确的终结点，即有限过程。整个的过程我们称为一个事件（episodes），例如一局游戏、一次迷宫穿越。这种情况不适用于持续型而无终结点的事件。

终止事件\(T\)是一个随机变量，通常会因事件而异。有时候我们需要区分包含终止状态的状态集合，记为\(\mathcal{S}^+\)；而不包含终止状态的集合则记为\(\mathcal{S}\)。

当事件终止时，他会处于终止状态（terminal state），之后要么重置到一个标准起始状态，要么从一组标准起始状态中随机采样一个状态作为下次起始状态。换句话说，无论事件的结果如何，即使奖励不同，下一轮还是从同一机制中开始，所以这些事件在形式上是终止于相同的终止状态的，只是终止时的奖励并不相同。

我们一般将所有事件视为在相同的终止状态结束，但对应不同结果的奖励，这类时间任务称为事件型任务（episodic tasks）。

---

与之不同的是没有终止状态的持续型任务（continuing tasks），常用于过程控制任务的持续建模或是寿命较长的机器人应用。

对于持续型任务，考虑到数值和优化，我们引入一个新的重要概念折扣（discounting）。加入折扣后，智能体会选择其动作，使得在未来获得的折扣奖励之和最大化。具体而言，智能体选择动作\(A_t\)，以最大化期望折扣回报（expected discounted return）：

\[ G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}, \]

\[ \tag{3.8 折扣回报公式} \]

公式中的参数\(\gamma (gamma， 0 \le \gamma \le 1)\)被称为折扣因子（discount rate），用来衡量未来奖励的当前价值。在\(k\)个时间步之后收到的奖励，其当前价值只有\(\gamma^{k-1}\)倍于立即收到该奖励时的价值。如果\(\gamma < 1\)，那么只要奖励序列\(\{ R_k \}\) 有界，期望折扣回报公式中的无穷级数就会有一个有限值。

该公式可适用于有限步数的情节型任务，只需要设定终止时间步：

\[ G_t = \sum_{k=0}^{T - t - 1} \gamma^k R_{t + k + 1} \]

\[ \tag{情节型任务的折扣回报公式} \]

该公式还有一个常用的变体（在Exercise3.6中提到），即假如任务是一个类似于平衡杆这样的在结束之前一直没有奖励，而在结束的时刻统一给予一个\(-X\)的奖励，那么该式可以代入并简化为：

\[ G_t = -X \cdot \gamma^{T - t - 1} \]

这个式子表示离失败（T）越远，回报的绝对值就越小，只有在失败的那一刻才有奖励。

---

如果\(\gamma=0\)，则智能体只关注即时奖励（immediate rewards），此时智能体的行为是短视的（myopic）。但是如果智能体的每个动作仅影响即时奖励而不影响未来奖励，那么短视的策略也能最大化回报。

然而，在实际中，如果仅最大化即时奖励，将会限制未来奖励的获取，从而降低总回报。

随着\(\gamma\)趋近于1，优化目标会更强烈地考虑未来奖励，智能体的行为会变得更具前瞻性（farsighted）。

在强化学习的理论中，不同时间步的回报之间存在重要的递推关系：

\[ \begin{align*} G_t &\doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots \\ &= R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \cdots) \\ &= R_{t+1} + \gamma G_{t+1} \end{align*} \]

\[ \tag{3.9} \]

这一定义适用于所有\(t<T\)的时间步。如果交互在\(t+1\)时终止，即从\(t+1\)开始就不再有后续奖励了，我们仍然可以用统一的递归公式来计算回报\(G_t\)，只要我们人为定义\(G_T=0\)（其中\(T\)是终止时间步）。

举例来说，假如时间步t = 100的时候任务就终止了，那么我们就可以定义G_100 = 0，然后用递推公式来计算G_99 = R_100 + 0。这个技巧简化了计算和编程，十分实用。

当奖励为非零且恒定，并且\(\gamma<1\)的时候，回报仍然是有限的。例如，当奖励恒定为+1时，回报为：

\[ G_t = \sum_{k=0}^{\infty} \gamma^k = \frac{1}{1 - \gamma} \]

\[ \tag{3.10} \]

本节的Exercise 3.5 - 3.10见附录部分。

注：在本章的练习题中，提到了一个关于平衡杆的经典问题。书中没有对本例提出编程要求，但鉴于这个任务太过经典，因此读者在这里增加一个实验环节，展示一下如何将我们本章所学的内容运用到实践操作环境中。该部分我放在了附录：Programming中的Programming 3.1 平衡杆中。感兴趣的同学可以看一下。

---

3.4 统一性描述

在上一节我们讨论了情节型任务（episodic task）和持续型任务（continuing task），这一节我们来将两种任务的记号进行统一（Unified Notation）。换句话说，将3.7式和3.8式进行统一。

上图（状态转移示意图）中的实心方块表示情节型任务结束时的特殊的吸收状态（absorbing state）。如此一来，无论只对前3步的回报进行求和，还是对所有的回报进行求和，其回报总和都是相同的。

也就是说，我们可以沿用3.8式的定义来给出一般情况下的回报公式：

\[ G_t \;\doteq\; \sum_{k=t+1}^{T} \gamma^{\,k - t - 1}\,R_k \]

\[ 其中 \;T = \infty \;\text{或}\; \gamma = 1 \;不能同时成立 \]

\[ \tag{3.11} \]

这里之所以不能让两者同时成立的原因是为了保证\(G_t\)能够收敛。

---

3.5 策略与价值函数

几乎所有的强化学习算法都涉及对价值函数的估计——即对状态（或状态–动作对）的函数，它们用于估计：在某一状态下，代理处于该状态“有多好”，或在某一状态下执行某一动作“有多好”。这里的“有多好”是从未来可能获得的奖励的角度来定义的，更准确地说，是从期望回报（expected return）的角度来定义的。当然，代理在未来可能获得的奖励取决于它将采取的动作。因此，价值函数是相对于特定的行为方式定义的，这些行为方式称为 策略 （policies）。

形式上，策略（policy） 是一个从状态映射到各个可能动作的选择概率的函数。如果智能体在时刻 \(t\) 遵循策略 \(\pi\)，则 \(\pi(a \mid s)\) 是代理在 \(S_t = s\) 时采取动作 \(A_t = a\) 的概率。像 \(p\) 一样，\(\pi\) 是一个普通函数；中间的“\(|\)”只是提醒我们，它定义了一个在每个 \(s \in \mathcal{S}\) 上关于 \(a \in \mathcal{A}(s)\) 的概率分布。强化学习方法具体说明了智能体如何根据其经验改变策略。

状态价值函数（Value function） 是在策略 \(\pi\) 下，从状态 \(s\) 开始并之后始终遵循 \(\pi\) 时的期望回报，记为 \(v_\pi(s)\)。对于马尔可夫决策过程（MDP），我们可以形式地定义 \(v_\pi\) 为：

\[ v_\pi(s) \doteq \mathbb{E}_\pi \left[ G_t \mid S_t = s \right] = \mathbb{E}_\pi \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \,\middle|\, S_t = s \right], \quad \text{for all } s \in \mathcal{S} \]

\[ \tag{3.12} \]

其中 \(\mathbb{E}_\pi[\cdot]\) 表示在代理遵循策略 \(\pi\) 的条件下，随机变量的期望值，\(t\) 是任意时间步。注意，终止状态（如果有）对应的价值恒为零。我们称函数 \(v_\pi\) 为策略 \(\pi\) 的状态价值函数（state-value function for policy \(\pi\)）。

类似地，我们定义在状态 \(s\) 下，在策略 \(\pi\) 下执行动作 \(a\) 的价值函数，记作 \(q_\pi(s, a)\)，它表示从状态 \(s\) 开始，执行动作 \(a\)，然后按策略 \(\pi\) 行动所得的期望回报：

\[ q_\pi(s, a) \doteq \mathbb{E}_\pi \left[ G_t \mid S_t = s, A_t = a \right] = \mathbb{E}_\pi \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \,\middle|\, S_t = s, A_t = a \right] \]

\[ \tag{3.13} \]

我们称 \(q_\pi\)为 策略 \(\pi\)的动作价值函数（action-value function for policy \(\pi\)）。

价值函数 \(v_\pi\) 和 \(q_\pi\) 可以通过经验进行估计。例如，如果一个智能体遵循策略 \(\pi\)，并对每次遇到某一状态时实际获得的回报取平均，那么随着该状态被访问的次数趋近于无穷，这个平均值将收敛到该状态的价值 \(v_\pi(s)\)。

如果我们在每个状态下的每个动作上也分别维护平均值，那么这些平均值也会收敛到对应的动作价值 \(q_\pi(s, a)\)。我们将这种基于随机样本回报平均的估计方法称为 蒙特卡洛方法（Monte Carlo methods），相关方法将在第5章中详细介绍。

当然，如果状态数非常多，为每个状态单独维护平均值就不切实际。此时，智能体可以将 \(v_\pi\) 和 \(q_\pi\) 作为参数化函数（其参数数量少于状态数）来维护，并调整参数以更好地匹配观察到的回报。虽然这种方法的准确性在很大程度上取决于所使用函数逼近器的性质，但它同样可以产生准确的估计。这类可能性将在本书第二部分进一步探讨。

---

强化学习与动态规划中使用的价值函数有一个根本性的性质：它们满足类似于我们在（3.9）中为回报所建立的递归关系。对于任意策略 \(\pi\) 和任意状态 \(s\)，以下一致性条件在该状态与其所有后继状态之间成立：

\[ v_\pi(s) \doteq \mathbb{E}_\pi \left[ G_t \mid S_t = s \right] = \mathbb{E}_\pi \left[ R_{t+1} + \gamma G_{t+1} \mid S_t = s \right] \]

根据公式 (3.9) 可进一步展开为：

\[ = \sum_a \pi(a \mid s) \sum_{s'} \sum_r p(s', r \mid s, a) \left[ r + \gamma \mathbb{E}_\pi \left[ G_{t+1} \mid S_{t+1} = s' \right] \right] \]

由于：

\[ \mathbb{E}_\pi \left[ G_{t+1} \mid S_{t+1} = s' \right] = v_\pi(s') \]

最终得到：

\[ v_\pi(s) = \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma v_\pi(s') \right], \quad \text{for all } s \in \mathcal{S} \]

\[ \tag{3.14 Bellman Equation 贝尔曼方程} \]

在上述表达中，动作 \(a\) 来自集合 \(\mathcal{A}(s)\)，后继状态 \(s'\) 来自 \(\mathcal{S}\)（对于终止问题可能来自 \(\mathcal{S}^+\)），奖励 \(r\) 来自集合 \(\mathcal{R}\)。

需要注意的是，在最后一个公式中，我们将对 \(s'\) 和 \(r\) 的两个求和合并为一个对所有 \((s', r)\) 对的求和，这是为了简化公式表达。这个合并后的表达实际上可以被理解为一个期望值：我们对所有可能的三元组 \((a, s', r)\) 求和，计算其概率 \(\pi(a \mid s) p(s', r \mid s, a)\)，并将括号中的表达乘以该概率，然后对所有可能性求和以得到期望值。

方程 (3.14) 是 \(v_\pi\) 的 Bellman 方程（Bellman equation）。它表达了一个状态的价值与其后继状态价值之间的关系。可以将其理解为：从某一状态开始，向前展望其所有可能的后继状态（如下图所示）。

图中每个空心圆代表一个状态，每个实心圆代表一个状态–动作对。从根节点状态 \(s\) 出发，智能体可以根据策略 \(\pi\) 从多个动作中选择（图中示意了三个）。对于每个动作，环境可能转移到某个后继状态 \(s'\)（图中展示了两个），并给出一个奖励 \(r\)，这些转移由函数 \(p\) 描述其概率。

Bellman 方程 (3.14) 对所有可能的情况进行加权求和，权重为发生的概率。它说明了：某一状态的价值等于所有可能的动作和后继状态下的奖励与折扣后的未来价值的加权和，即：

\[ v_\pi(s) = \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma v_\pi(s') \right] \]

价值函数 \(v_\pi\) 是其 Bellman 方程的唯一解。在后续章节中，我们将展示该 Bellman 方程如何作为多种计算、逼近和学习 \(v_\pi\) 方法的基础。

我们将这种图称为 备份图（backup diagrams），因为它们直观展示了更新（或称备份）操作的结构，这些操作是强化学习方法的核心。这些操作将价值信息向后传播到一个状态或状态–动作对，来源是其后继状态（或状态–动作对）。

我们在整本书中反复使用备份图来提供各个算法的图形摘要说明。（请注意，与转移图不同，备份图中的状态节点不一定代表不同的状态；例如，一个状态也可能是它自己的后继状态。）

对于贝尔曼方程，我们可以视为对同一套MDP的不同切面：

\[ v_\pi(s) = \sum_a \pi(a \mid s) \, q_\pi(s, a), \quad q_\pi(s, a) = r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, v_\pi(s'). \]

其中状态值函数的贝尔曼方程拆开写的话可以记为：

\[ \boxed{ v_\pi(s) = \underbrace{\sum_a \pi(a \mid s) r(s, a)}_{\text{当前期望奖励}} + \gamma \underbrace{\sum_a \pi(a \mid s) \sum_{s'} p(s' \mid s, a) v_\pi(s')}_{\text{折扣后未来价值期望}}. } \]

动作值函数的贝尔曼方程拆开写的话可以记为：

\[ \boxed{ q_\pi(s, a) = r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \sum_{a'} \pi(a' \mid s') q_\pi(s', a'). } \]

根据实际应用的不同，在编程的时候可以灵活书写贝尔曼方程。简单来说，贝尔曼方程就是把当下的期望奖励和未来的期望奖励一起计算，得到一个确切的数值解。

本章节的Example3.5 Gridworld的解和编程详见Programming 3.2。

本章节的Example3.6 关于高尔夫球，略过。详情见书中P62页。

本章节的Exercise 3.11 - 3.19见附录部分。

---

3.6 最优贝尔曼方程

解决强化学习任务大致上意味着找到一种在长期内能获得大量奖励的策略。对于有限马尔可夫决策过程（MDP），我们可以通过以下方式精确定义最优策略。

价值函数对策略之间建立了一个偏序关系。如果一个策略 \(\pi\) 的期望回报在所有状态下都大于或等于另一个策略 \(\pi'\) 的期望回报，则称 \(\pi\) 优于或等于 \(\pi'\)。 换句话说，若对所有 \(s \in \mathcal{S}\)，都有 \(v_\pi(s) \geq v_{\pi'}(s)\)，则认为 \(\pi \geq \pi'\)。

总会至少存在一个优于或等于所有其他策略的策略，这种策略被称为最优策略（optimal policy）。 尽管最优策略可能不止一个，但我们通常用 \(\pi_*\) 表示所有的最优策略。 这些最优策略共享同一个状态价值函数，该函数被称为最优状态价值函数（optimal state-value function），记作 \(v_*\)，定义如下：

\[ v_*(s) \doteq \max_\pi v_\pi(s), \quad \text{对所有 } s \in \mathcal{S}。 \]

\[ \tag{3.15} \]

最优策略也共享同一个最优动作价值函数（optimal action-value function），记作 \(q_*\)，定义如下：

\[ q_*(s, a) \doteq \max_\pi q_\pi(s, a), \quad \text{对所有 } s \in \mathcal{S}, a \in \mathcal{A}(s)。 \]

\[ \tag{3.16} \]

对于状态-动作对 \((s, a)\)，该函数表示在状态 \(s\) 采取动作 \(a\)，随后遵循一个最优策略所获得的期望回报。 因此，我们可以如下地用 \(v_*\) 表示 \(q_*\)：

\[ q_*(s, a) = \mathbb{E} \left[ R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t = s, A_t = a \right]。 \]

\[ \tag{3.17} \]

\(q_*\) 的贝尔曼最优性方程如下所示：

\[ q_*(s, a) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') \mid S_t = s, A_t = a \right] \]

\[ = \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma \max_{a'} q_*(s', a') \right] \]

\[ \tag{3.20} \]

我们要记住的是，对于有限马尔可夫决策过程MDPs，贝尔曼最优方程对于\(v_*\)有唯一的解。

贝尔曼最优方程是一组方程系统，每个状态对应一个方程。如果关于环境的动态函数\(p\)是已知的，那么原则上我们就可以使用多种非线性方程求解方法中的任何一种来求解这组关于\(v_*\)的方程系统。

而当我们得到最优值函数后，此基础上使用贪婪（greedy）的策略就是最优策略。因为我们这里得到的方程系统已经考虑了长期结果，因此贪婪策略也意味着长期意义上的最优。

而对于动作价值函数，如果我们能获得\(q_*\)，那么对于任意状态\(s\)，只需找到能使\(q_*(s,a)\)最大的动作即可。换句话说，只要有最优动作价值函数，就可以直接让智能体做出最优动作选择。

不过贝尔曼最优方程虽然在理论上可解，但在实际中非常难以运用，因为它需要评估所有可能路径的期望奖励，属于穷举搜索。同时，三大前提假设：

• 环境动态已知道，即\(p(s', r \mid s, a)\)准确
• 计算资源足够强大，能够解非线性方程组
• 状态具有MDP性质

以国际象棋为例，国际象棋拥有\(10^{43}\sim10^{50}\)个状态数量，用2025年世界上最强的超级计算机，大概也需要才能解出\(v_*\)。因此，在求解实际问题时，必然要用到依赖近似值函数和策略，而非直接用最优贝尔曼显式求解。

书中的Example3.8，3.10略过；3.9见Programming 3.2。

练习Exercise 3.20 - 3.29见附录部分。

---

3.7 最优性与近似

尽管理论上可以通过求解Bellman最优性方程获得最优策略，但是对于几乎所有现实问题，这都是无法实现的。因此，最优性（optimality）是一个非常理想的状态，对于几乎所有的现实问题，智能体都只能做到近似（approximation）。

因此，对于强化学习问题的表述本质决定了函数近似是强化学习中的核心手段。

强化学习能够在线更新策略（online policy update），优先优化在实际中经常遇到的状态，这是强化学习在近似求解MDP时相比其他方法的一大优势。具体来说，就是智能体在每一个时间步的交互后，都能立即使用新获得的经验来更新策略或价值函数，而非等所有数据收集完才开始。

在1990年代，基于时序差分（第六章会学习）的TD-Gammon达到了世界级水准，打败了大多数人类西洋双陆棋冠军。

---

3.8 总结

让我们总结一下本章所介绍的强化学习问题的各个要素。强化学习的核心是：通过与环境的交互学习如何行动以达成目标。强化学习中的智能体（agent）与其环境（environment）在离散的时间步骤中交互。环境接口的定义确定了一个特定任务：

• 动作（actions） 是由智能体做出的选择；
• 状态（states） 是智能体做出选择的依据；
• 奖励（rewards） 是用于评估选择结果的依据。

智能体内部的一切都是已知且可控的，而环境则可能是不可控的，也可能不是完全已知的。 策略（policy） 是智能体根据状态来选择动作的一种随机规则。智能体的目标是最大化其获得的累计奖励。

当强化学习问题的设置包含已定义好的转移概率时，它就构成了一个马尔可夫决策过程（Markov Decision Process，MDP）。如果这是一个有限 MDP（finite MDP），那么状态、动作和奖励集合都是有限的（我们本书使用此类表述）。目前的强化学习理论多数是基于有限 MDP 的，但很多思想在更一般的情况下同样适用。

---

回报（Return） 是智能体试图最大化的未来奖励的函数（通常是期望值形式）。它有多个不同的定义，取决于任务的性质以及是否希望对延迟奖励进行折扣（discount）。

• 未折扣形式适用于回合制任务（episodic tasks），即智能体与环境的交互自然地分为一个个“回合”。
• 折扣形式适用于连续任务（continuing tasks），即交互没有自然的终点，会无限持续下去（参见第 10.3–10.4 节）。

我们尝试对这两种类型的任务统一建模，使得同一组方程可以同时适用于回合制任务和连续任务。

---

策略的值函数（value functions）（\(v_\pi\) 和 \(q_\pi\)）给每个状态或状态-动作对赋予一个期望回报的值，这个值是在智能体遵循该策略的前提下从那个状态或状态-动作对出发所能获得的期望回报。

最优值函数（optimal value functions）（\(v_*\) 和 \(q_*\)）则给每个状态或状态-动作对赋予在所有可能策略中可达的最大期望回报。

一个策略如果其值函数等于最优值函数，我们就称它为最优策略（optimal policy）。 虽然对于一个给定的 MDP 来说，状态-动作对的最优值函数是唯一的，但最优策略可能不止一个。 任何对最优值函数贪婪（greedy）的策略都可以是最优策略。

Bellman 最优性方程（Bellman optimality equations） 是一组特殊的约束条件，最优值函数必须满足这些条件。原则上，只要解出这些方程，就可以得到最优值函数，从而导出一个相应的最优策略。

---

一个强化学习问题可以从多个不同的角度来建模，具体取决于对智能体初始知识的假设。

• 在完全知识（complete knowledge）的设定中，智能体拥有环境动态的完整、准确模型。如果环境是 MDP，这个模型就包括完整的四元组状态转移函数 \(p\)（见 3.2 节）。
• 在不完全知识（incomplete knowledge）的问题中，环境的完整且准确的模型是不可用的。

即使智能体拥有完整且准确的环境模型，它通常也无法充分利用该模型，原因在于其内存与计算能力的限制，特别是在每个时间步所能进行的计算量有限。

尤其在实践中，可能需要大量内存来近似值函数、策略和模型。而在大多数实际感兴趣的问题中，状态数量远远超过可用的表格容量，因此必须进行近似。

---

一个明确的最优性概念是本书所描述学习方法的组织核心，它为我们理解各种学习算法的理论性质提供了方式。但最优性是一个理想状态，在实际中，强化学习的智能体只能做到不同程度的近似。

强化学习特别关注那些最优解无法直接求得，但可以通过近似方式逐步逼近的任务情形。

---

附：Exercise

Exercise 3.1 设计任务

问：请你自己设计三个符合MDP框架的示例任务，并为每个示例明确指出他的状态、动作、奖励。让这三个示例尽可能彼此不同。尝试挑战一下框架的极限，拓展应用边界。

答：

（1）用强化学习算法让机器人学会走迷宫

• 目标：走出迷宫
• 状态：机器人所处环境的情况，比如是否旁边有墙壁
• 动作：前进、后退、左拐、右拐
• 奖励：每过1s奖励-1

（2）用强化学习算法炒股

• 目标：获得更高的收益
• 状态：股市大盘情况
• 动作：购买股票、卖出股票
• 奖励：月均收益率越高奖励越高

（3）让机械臂学会抓取物品

• 目标：让机械臂抓取物品并放到指定位置（固定）
• 状态：机械臂的姿态、物品的位置、机械手的姿态
• 动作：机械臂的移动、机械手的抓取动作
• 奖励：成功抓取、成功放到指定位置可以获得奖励

我写的是比较normal的，然后ChatGPT设计了一些大胆的创意，可以参考一下：

（1）AI写诗的风格控制器

• 目标：生成具有高度情感共鸣和美感的诗
• 状态：当前诗的风格向量（情绪色彩、押韵结构、当前节数、上一行语义嵌入）
• 动作：调节风格参数、切换主题、引入象征手法
• 奖励：+10 情感真挚；+5 押韵自然； +20 被收藏； -10 风格突兀

（2）DNA序列设计优化器

• 目标：设计出稳定且表达良好的DNA序列片段，用于制造蛋白质
• 状态：当前序列片段的碱基组成、生物功能预测分值、结构稳定性评分
• 动作：插入、删除或替换要给碱基对
• 奖励：+50 达到目标蛋白表达水平；+20 结构稳定； -30 有毒或不表达

（3）即兴舞台剧演员策略学习

• 目标：作为AI演员参与即兴表演，提升观众反应和剧情推进效果
• 状态：剧情当前情节节点、其他角色的行为、观众情绪指标
• 动作：即兴加入角色设定、提出新剧情冲突、模仿其他演员风格
• 奖励：+15 观众笑/鼓掌；+10 推动剧情发展； -10 打断节奏或冷场

（4）冥想引导系统中的意识调节代理

• 目标：通过动态语音或提示，引导用户进入更深层次的冥想状态，实现情绪平稳和脑波放松
• 状态：用户的生理状态和环境状态，比如脑波、引导强度、环境音强度等
• 动作：调整语速、插入自然音效、沉默片段等
• 奖励：+20 脑波进入深度冥想状态；-10 用户走神或烦躁

读者的题外话：没想到ChatGPT的答案比读者的更具想象力、创造力。这几个AI举的例子让读者突然意识到，如果能把人类生物体整体搬迁到虚拟世界中，那么强化学习将迎来爆发式的发展，因为可以根据虚拟人体来进行大规模的试验。但是这个想法又觉得有点黑暗了，比如舞台策略那个，假设把跟人一样的假人造出来了，那么那个假人具备意识吗？那么如果进行个500万次模拟，岂不是让一个假人死亡了500万次吗？这个角度是我从来没有想过的，而ChatGPT的例子让我突然意识到AI的道德观、伦理观终将和人类截然不同。Sutton的苦涩教训证明了人类经验在AI发展中的副作用，反过来讲，如果AI的发展将独立于人类意识，仅依赖于算力、算法等，那么最终如果我们真的创造出了AGI，那AGI的道德伦理观也一定不会等同于人类。

这道题引入了更多的话题：模拟人类的伦理边界在哪里？人类主观体验能否被编码？道德输入是否要作为奖励之一？AGI的价值体系真的是从人类经验中学来的吗？

读者最喜欢Sutton的一点就是，他一直在思考人类智能和人工智能在哲学意义上的问题。Hinton也是一样的，现在在各处游走宣扬人工智能的潜在危害性。他们作为人工智能界的祖师爷当之无愧，希望更多的从业者能多关注一下伦理上的问题。我们都知道AGI是必不可免的一定会被创造出来的东西，那么在创造出来之前，还是要更多地去关注其安全性和伦理性的问题。以及，这个东西一定不能只被一个组织实体所掌握，也难怪Hinton对中国大力发展AI表示“希望能看到中美的相互制衡”了。

---

Exercise 3.2 MDP的适用范围

问：MDP框架足够表示所有的目标导向学习任务吗？你能想到任何清晰的解释吗？（Is the MDP framework adequate to usefully represent all goal-directed learning tasks? Can you think of any clear exceptions?）

答：

首先，MDP框架只适用于满足马尔可夫性质的任务：未来状态仅依赖于当前状态、离散时间步、环境可以被完全观测、固定的转移和奖励规则。

MDP框架不适用的情况举例：

1. 在雾中导航，无法完全观测环境状态
2. 只有执行特定动作序列才能获得奖励
3. 异步事件，比如自动驾驶中可能会发生其他车辆突然变道的情况
4. 多个智能体的环境，每个智能体的角度环境都是非平稳的（比如星际争霸游戏）
5. 分层目标，比如炖红烧肉包括切肉、煮饭等多个子任务

---

Exercise 3.3 智能体与环境的界限

问：考虑最常见的驾驶问题。你可以把“动作”定义为加速、改变方向、踩刹车等，这个时候动作就是你的身体与机器交互的地方。你也可以认为轮胎和地面处的产生动力的扭矩是动作。又或者说，动作可以被认为是你的身体中对肌肉的控制。甚至我们还可以说，动作是选择在哪里开车。可以看到，区分动作和环境是非常主观的，那么怎样才能找到一个合适的层次、更合适的地方来进行区分呢？（What is the right level, the right place to draw the line between agent and environment?）有没有某种基础来进行设定？（On what basis is one location of the line to be preferred over another?）有没有根本性的理由来进行确定？（Is there any fundamental reason for preferring onte location over another, or is it a free choice?）

答：这道题是一个开放性思考题，这也是Sutton经常考虑的问题。这道题并没有一个正确的答案，不同的动作设置取决于我们要解决的任务目标。这也是强化学习不同于如今大火的LLM的一个重要原因。在强化学习中，任务的目标本身会限制这一条界限，而建模的复杂度和可行性又会影响你如何去设置动作。还有，数据是否能获得，也将影响动作的设置。

---

Exercise 3.4 Trace Table

这道题要求你给出一个类似例3.3中的表格，针对四参数状态转移函数。

原表格如图所示。这道题可以在第一次解决实际问题的时候自己做一个试试，这里就不展开讲了。

---

Exercise 3.5

问：在3.1节中的公式适用于持续型任务：

\[ \sum_{s' \in \mathcal{S}} \sum_{r \in \mathcal{R}} p(s', r \mid s, a) = 1 \quad \forall s \in \mathcal{S},\ a \in \mathcal{A}(s) \]

如何修改来适配情节型任务（episodic task）呢？

答：该方程描述了在某个状态s执行动作a后，所有可能的下一个状态和奖励的组合加起来的概率必须是1。在情节型任务中，终止状态后没有“下一个状态”，因此我们引入新的符号：

\[ \mathcal{S}^+ = \mathcal{S} \cup \{\text{terminal}\} \]

于是，方程修改为：

\[ \sum_{s' \in \mathcal{S}^+} \sum_{r \in \mathcal{R}} p(s', r \mid s, a) = 1, \quad \forall s \in \mathcal{S},\ a \in \mathcal{A}(s) \]

也就是说，我们要允许\(s'\)是终止状态，用\(\mathcal{S}^+\)来表示所有普通状态加上终止状态。

---

Exercise 3.6 Pole-Balancing

Pole-Balancing，即杆平衡，是一个非常经典的强化学习任务。该任务的目标就是给轨道上移动的小车施加力，使得连接在小车上的杆子始终保持直立，防止其倒下。

如果杆子偏离垂直超过某个给定角度，或者小车跑出轨道，则视为失败。失败之后状态会被重置。

该任务可以被看作是一个 情节性任务（episodic task） ，其自然的情节（episode）是多次尝试平衡杆的过程。每次在未失败的时间步，奖励为 +1，因此每个时间点的回报（return）就是失败之前的时间步数。在这种情形下，若杆始终保持平衡（永远不失败），则回报将趋于无穷大。

另一种方式是将杆平衡视为一个 持续性任务（continuing task） ，并使用折扣因子（discounting）。此时，每次失败会带来 −1 的奖励，其他时间步奖励为 0。于是每个时间点的回报与\(-\gamma^{K-1}\)有关，其中\(K\)是到失败发生所经历的时间步数（也可能包括之后失败的时间点）。在这两种设定下，最大化回报的策略都是尽可能长时间地保持杆平衡。

这里注意，一般对于任务失败的记录，人们有两种习惯，一种是用\(T\)来代表任务失败时的时间步；另一种记录\(K\)为episode的长度（从时间步0开始计数），然后\(K-1\)记为最后一个有效的时间步，即失败发生的那一刻。

Exercise3.6的问题是：假设你将杆平衡任务视为 情节性任务 ，但同时使用折扣机制，且所有时间步奖励均为 0， 只有失败时奖励为 −1 。那么，在每个时间点的回报应该是多少？在此设定下的回报与前面“折扣式持续任务”中的回报有何不同？

答：

（1）如果所有事件步的奖励均为0，只有失败时奖励为-1，那么如果t是当前的时间步，T为终止的时间步，折扣因子为\(\gamma \in (0,1]\)，因此，在当前episode中，回报是：

\[ G_t = \sum_{k=0}^{T - t} \gamma^k R_{t + k} = \gamma^{T - t} \cdot (-1) = -\gamma^{T - t} \]

这个回报能真实地反映一次尝试中维持平衡的时长，并且失败越晚、惩罚越小。agent改进后，每次episode的回报也会改进（更少惩罚）。

（2）同时，如果环境不会重置，那么agent会永远运行下去，而失败可能发生很多次。回报是所有未来失败惩罚的折扣和：

根据持续型任务折扣回报标准定义公式：

\[ G_t = \sum_{k=0}^{\infty} \gamma^k R_{t + k + 1} \]

如果某个失败发生在时间\(K\)，即\(R_K = -1\)，那么如果想知道它对\(G_t\)的贡献，令：

\[ K = t + k + 1 \Rightarrow k = K - t - 1 \]

所以该失败对\(G_t\)的贡献为：

\[ \gamma^{K-t-1} \cdot (-1) \]

即：

\[ G_t = -\sum_{K \in \mathcal{K},\, K > t} \gamma^{K - t - 1} \]

---

Exercise 3.7

问：

假设你正在设计一个机器人去穿越迷宫。你决定为其设置如下奖励机制：如果成功逃出迷宫，则给予 +1 的奖励；在其他所有时刻，奖励为 0。这个任务看起来自然地可以被分为多个“回合”——也就是一次次穿越迷宫的尝试——因此你决定将其建模为一个 回合式任务 ，目标是最大化期望的总奖励（3.7 式）。

在你运行学习代理一段时间之后，你发现它在逃出迷宫方面没有任何改进。

请思考：问题出在哪里？你是否真正向代理清楚地传达了你希望它实现的目标？

答：

很显然，只要能逃出迷宫，agent就能得到+1的奖励。这个策略并没有奖励尽快逃出迷宫，自然也就不会有任何改进了。正确的做法应该是对时间拖得越来越长给予惩罚，比如每在迷宫中停留1s就给予-1的惩罚，这样agent才有动机去减少在迷宫中花费的步数。

另一种方法就是使用折扣因子来减少延迟奖励的价值。

---

Exercise 3.8

假设折扣因子 \(\gamma = 0.5\)，且你收到如下奖励序列：

\[ R_1 = -1,\quad R_2 = 2,\quad R_3 = 6,\quad R_4 = 3,\quad R_5 = 2 \]

终止时间为 \(T = 5\)。 请计算下列回报值：

\[ G_0, G_1, G_2, G_3, G_4, G_5 \]

答：

根据公式3.9：

\[ G_t = R_{t+1} + \gamma G_{t+1} \]

可知，如果想得到Gt的值，就必须要先计算\(G_{t+1}\)的值，因此要从后往前计算。

由于T=5，因此\(G_T=G_5=0\)

1. 计算 \(G_4\)：

\[ G_4 = R_5 + \gamma G_5 = 2 + 0.5 \times 0 = 2 \]

2. 计算 \(G_3\)：

\[ G_3 = R_4 + \gamma G_4 = 3 + 0.5 \times 2 = 3 + 1 = 4 \]

3. 计算 \(G_2\)：

\[ G_2 = R_3 + \gamma G_3 = 6 + 0.5 \times 4 = 6 + 2 = 8 \]

4. 计算 \(G_1\)：

\[ G_1 = R_2 + \gamma G_2 = 2 + 0.5 \times 8 = 2 + 4 = 6 \]

5. 计算 \(G_0\)：

\[ G_0 = R_1 + \gamma G_1 = -1 + 0.5 \times 6 = -1 + 3 = 2 \]

得到最终结果如下：

\[ G_0 = 2,\quad G_1 = 6,\quad G_2 = 8,\quad G_3 = 4,\quad G_4 = 2,\quad G_5 = 0 \]

---

Exercise 3.9

Suppose \(\gamma = 0.9\) and the reward sequence is \(R_1 = 2\) followed by an infinite sequence of 7s. What are \(G_1\) and \(G_0\)?

假设折扣因子 \(\gamma = 0.9\)，奖励序列为

\[ R_1 = 2, \]

随后是无限多个

\[ R_2 = R_3 = R_4 = \cdots = 7. \]

请计算回报

\[ G_1 \quad\text{和}\quad G_0. \]

答：

根据公式3.10和公式3.9可以直接计算：

1. 计算 \(G_1\)

从 \(t=1\) 开始，所有后续奖励都是 7，所以

$$ G_1 = \sum_{k=0}^{\infty} \gamma^k \cdot 7 = 7 \sum_{k=0}^{\infty} (0.9)^k = 7 \times \frac{1}{1 - 0.9} = 7 \times 10 = 70. $$ 2. 计算 \(G_0\) 从 \(t=0\) 开始，首先收到 \(R_1=2\)，然后是无穷个 7，因此

$$ G_0 = R_1 + \gamma\,G_1 = 2 + 0.9 \times 70 = 2 + 63 = 65. $$

因此最终答案：

\[ G_1 = 70,\qquad G_0 = 65. \]

---

Exercise 3.10 - 3.13

Exercise 3.10

证明式3.10。本证明参见附：Math中的Math3.1。

---

Exercise 3.11

If the current state is \(S_t\), and actions are selected according to a stochastic policy \(\pi\), then what is the expectation of \(R_{t+1}\) in terms of \(\pi\) and the four-argument function \(p\) (3.2)?

Answer:

根据四参数转移函数定义：

\[ p(s', r \mid s, a) = \Pr\{S_{t+1} = s', R_{t+1} = r \mid S_t = s, A_t = a\} \]

由于动作是按策略 \(\pi\) 采样的，我们对所有可能的动作和结果求期望：

\[ \mathbb{E}[R_{t+1} \mid S_t = s] = \sum_{a} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \cdot r \]

---

Exercise 3.12

Give an equation for \(v_\pi\) in terms of \(q_\pi\) and \(\pi\).

Answer:

状态价值函数是动作价值函数的加权平均，权重为策略在该状态下对动作的选择概率：

\[ v_\pi(s) = \sum_{a \in \mathcal{A}(s)} \pi(a \mid s) \cdot q_\pi(s, a) \]

---

Exercise 3.13

Give an equation for \(q_\pi\) in terms of \(v_\pi\) and the four-argument \(p\).

Answer:

动作价值函数表示从状态 \(s\) 执行动作 \(a\) 后的期望回报，可以表示为：

\[ q_\pi(s, a) = \sum_{s', r} p(s', r \mid s, a) \cdot \left[ r + \gamma \cdot v_\pi(s') \right] \]

---

Exercise 3.14 - 3.19

Exercise 3.14

对于Example3.5（即Programming3.2）的GridWorld，请数值证明中心格子是否成立：

答：

已知：

• 策略\(\pi\)代表在上下左右四个动作上等概率选择，即\(\pi(a \mid s) = \frac{1}{4}\)
• 环境是确定的，每个格子的具体动作有对应的结果
• 折扣因子gamma=0.9

根据贝尔曼方程：

\[ v_\pi(s) = \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma v_\pi(s') \right]. \]

如果想求中心状态\(s_c\)，可得：

\[ v(s_c) = \sum_a \frac{1}{4} \left[ 0 + 0.9 \, v(\text{neighbor after } a) \right] = \frac{1}{4} \times 0.9 \sum_{i=1}^{4} v_i, \]

从图中可以看到中心点周围四个点的值，代入可得：

\[ v_1 + v_2 + v_3 + v_4 = 2.3 + 0.4 + (-0.4) + 0.7 = 3.0. \]

\[ v(s_c) = \frac{1}{4} \times 0.9 \times 3.0 = \frac{2.7}{4} = 0.675 \approx 0.7. \]

即图中中心点的值。本例的更多详细解释和代码实验参见Programming 3.2

---

Exercise 3.15

在网格世界的例子中，到达目标的奖励为正，撞到世界边缘的奖励为负，其余情况下的奖励为零。请思考：是这些奖励的正负号重要，还是只有它们之间的间隔（差值）才重要？

利用式 (3.8) 证明：如果在所有的即时奖励上都加上一个常数 \(c\)，那么所有状态的值函数都会增加同一个常数 \(v_c\)，因此在任何策略下，各状态之间的相对价值都不受影响。

问：\(v_c\) 用常数 \(c\) 和折扣因子 \(\gamma\) 表示应当是多少？

答：很显然，我们定义累积回报为：

\[ G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}. \]

如果对每一步的奖励都加上一个常数 \( c \)，定义新奖励为：

\[ R'_{t+k+1} = R_{t+k+1} + c, \]

那么对应的新的回报就是：

\[ G'_t = \sum_{k=0}^{\infty} \gamma^k (R_{t+k+1} + c) = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} + c \sum_{k=0}^{\infty} \gamma^k = G_t + c \sum_{k=0}^{\infty} \gamma^k. \]

而：

\[ \sum_{k=0}^{\infty} \gamma^k = \frac{1}{1 - \gamma}, \quad \text{（当 } 0 \leq \gamma < 1 \text{ 时收敛）} \]

所以额外添加的那一项就是：

\[ c \sum_{k=0}^{\infty} \gamma^k = \frac{c}{1 - \gamma}. \]

因此，为所有状态值都加上一个常数，并不影响不同状态之间的相对价值，只是把整个价值函数的图像在竖直方向上平移了，并且平移量就是\(c/({1-\gamma})\)。注意，该结论只适用于持续型任务，情节型任务见下一道练习题。

---

Exercise 3.16

现在考虑在一个情节性任务（episodic task，例如迷宫奔跑）中，将所有即时奖励都加上一个常数 \(c\)。

1. 这会对任务本身产生影响吗？
2. 或者，它会像在持续性任务（continuing task）中那样，使任务保持不变？ 请说明原因，并举一个具体的例子。

答：

情节型人物的折扣回报（从t开始到终止T）：

\[ G_t = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1} \]

对每一步的即时奖励增加一个常数c：

\[ G'_t = \sum_{k=0}^{T-t-1} \gamma^k \bigl(R_{t+k+1} + c\bigr) = G_t + c \sum_{k=0}^{T-t-1} \gamma^k = G_t + c \frac{1 - \gamma^{T-t}}{1 - \gamma} \]

对状态值函数的影响：

\[ v_\pi(s) = \mathbb{E}_\pi\bigl[G_t \mid S_t = s\bigr] \]

增加常数后：

\[ v'_\pi(s) = \mathbb{E}_\pi\bigl[G'_t \mid S_t = s\bigr] = v_\pi(s) + \frac{c}{1-\gamma}\,\Delta(s) \]

故而可得：

\[ \Delta(s) = \mathbb{E}_\pi\bigl[1 - \gamma^{T-t} \mid S_t = s\bigr] \]

从上可知，在持续性任务中，\(T \to \infty\) 且 \(0 \leq \gamma < 1\) 时有 \(\gamma^{T - t} \to 0\)，所以 \(\Delta(s) = 1\) 对所有状态相同，

\[ v'_\pi(s) = v_\pi(s) + \frac{c}{1 - \gamma}, \]

只是在所有状态上加同一个常数，不改变相对次序。

在情节型任务中，\(\gamma^{T - t}\) 随“到终止的步数” \(T - t\) 而变，\(\Delta(s)\) 依赖于状态 \(s\)（或策略 \(\pi\) 导致的平均剩余长度），因此不同状态会被加上不同的偏移量，可能改变状态价值的相对大小，从而影响最优策略。

---

Exercise 3.17 - 3.19暂时略过，都是关于贝尔曼方程的，在书中P61-62。

---

Exercise 3.20 - 3.29

最优贝尔曼方程章节的练习题，懒得做了，有空补。略过。

---

附：Programming

Programming 3.1 平衡杆

在本小节读者将介绍如何使用Gymnasium来进行强化学习实验。

Gymnasium是一个持续维护强化学习常见的经典实验环境的项目，继承了现在已经停止维护的Gym项目。

在第二章中我们学习了老虎机的实验实现，但是老虎机问题中没有状态的概念，每一次动作后都是立刻结束试验，并用样本平均更新来估计动作价值：

\[ Q(a) \leftarrow Q(a) + \frac{1}{N(a)}\bigl(R - Q(a)\bigr) \]

那么虽然现在还没有讲到Monte Carlo Methods，但是我们可以在这里很容易地把上面的样本平均更新方法扩展到包含状态的情况中：

\[ Q(s,a) \leftarrow Q(s,a) + \frac{1}{N(s,a)}\bigl(G_t - Q(s,a)\bigr) \]

Gymnasium的实验环境网址可以点击这里。

对于该实验，状态空间为：

动作空间为：

• 0：移动小车往左
• 1：移动小车往右

该环境内置了两种奖励设置：

• Sutton_Barto_Reward=True：即我们讨论的在结束前都是0，结束时刻为-1
• 也可以设置为每一个时间步+1，这种方法在v1版本中的threshold是500

超参数及训练环境设置如下：

• 折扣因子 \(\gamma = 0.99\)
• 探索率 \(\epsilon = 0.1\)（训练阶段）；演示阶段设为 \(\epsilon = 0\)
• 学习率：\(\displaystyle \alpha_t = \frac{1}{N(s,a)}\)（样本平均更新）
• 训练集数：episodes = \(500\)
• 单集最大步数：环境默认 \(500\) 步
• 策略执行（采样）

训练阶段使用 \(\epsilon\)-greedy$ 策略：

\[ \pi(a \mid s) = \begin{cases} 1 - \epsilon + \dfrac{\epsilon}{|A|}, & a = \arg\max_{a'} Q(s,a'),\\ \dfrac{\epsilon}{|A|}, & \text{otherwise}, \end{cases} \]

演示阶段使用纯贪心策略：\(\epsilon = 0\)。

• 数据收集每个 episode 从 env.reset() 开始，循环调用 env.step(action)，直至失败或达到最大步数。
• 折扣回报计算对轨迹 \((s_t, a_t, r_{t+1})_{t=0}^{T-1}\)，计算

$$ G_t = \sum_{k=0}^{T-1-t} \gamma^k\,r_{t+1+k}. $$ - Q 表样本平均更新

$$ N(s_t,a_t) \leftarrow N(s_t,a_t) + 1, $$

$$ Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \frac{1}{N(s_t,a_t)}\bigl(G_t - Q(s_t,a_t)\bigr). $$

结果展示：

• 绘制两种奖励模式下的总回报曲线（500 episodes）。
• 演示 Sutton–Barto 模式下的最优（贪心）策略动画并输出示例回报。

训练后的结果如下所示：

这里我们会发现，如果用第二章老虎机的奖励图，Sutton-Barto方法会变成一条直线，因为最终奖励永远都是-1。从原理上来说，两个方法的最终结果实际上是一样的，他们都是在用同一个策略来最大化杆子的存活时长T，只不过在数值尺度、方差和收敛速度上不同：

• 奖励方法给回报设置了一个不断累加的较大的正信号
• Sutton-Barto方法则是给了一个衰减的负信号

因此我修改了代码，展示了多个角度的结果图（因为没有用随机种子，所以每次训练情况不同，所以奖励法的Reward图和上面的不太一样）

最后展示一段训练的结果（Sutton-Barto法）：

代码见附录中的代码部分 Code 3.1。

---

Programming 3.2 Gridworld

本案例为书中Example3.5.

如上图所示，在该网格世界中呢，能执行的动作只有上下左右移动，如果移动会导致agent离开网格，则获得奖励-1并保持位置不变。特殊状态A会获得+10并传送至A'，特殊状态B会获得+5并传送至B'。除此之外其他动作奖励都是0。

根据这个图，求解这个网格世界每个格子对应的状态价值分布。

我们来看一下这个案例所对应的MDP：

1. 有限状态空间：25个各自对应25个状态
2. 确定性转移：每个动作都会导致唯一的后继状态
3. 固定的奖励函数分布
4. （书中采用的统一设置）gamma=0.9

由于该场景给定的状态转移和奖励函数是固定的，并且我们可以直接确切求解，因此得到的状态价值分布一定是唯一的。

我们先来构建一下这个Gridworld：

 0  1  2  3  4  
 5  6  7  8  9  
10 11 12 13 14  
15 16 17 18 19  
20 21 22 23 24  

接着定义状态转移函数：

def step(s, a):
    if s == 1: return 21, 10   # A
    if s == 3: return 13, 5    # B
    i, j = s // 5, s % 5
    if a == 0: i2, j2 = i-1, j      # up
    if a == 1: i2, j2 = i+1, j      # down
    if a == 2: i2, j2 = i, j-1      # left
    if a == 3: i2, j2 = i, j+1      # right
    if i2 < 0 or i2 > 4 or j2 < 0 or j2 > 4:
        return s, -1  # hit wall
    return i2*5 + j2, 0  # move

接着采用随机策略：

\[ \pi(a \mid s) = \frac{1}{4}, \quad \text{for all } s \text{ and } a \]

这里之所以是1/4，是因为每个状态下都可以执行四个动作，我们采用的是等概率随机策略，因此每个状态下的四个动作选择是均匀的。

接着对对每个状态 $$ 写出：

\[ v(s) = \sum_a \pi(a \mid s)\left[ r(s, a) + \gamma \cdot v(s') \right] \]

这就是：

\[ v(s) = \frac{1}{4} \sum_{a=0}^{3} \left[ r(s, a) + \gamma v(s') \right] \]

共 25 个状态，即 25 个线性方程。

伪代码可以参考如下：（具体代码可在代码附录的Code3.2查看）

1. 初始化：
   - 网格大小为 5x5，总共 25 个状态
   - 折扣因子 γ = 0.9
   - 每个状态允许四个动作：上、下、左、右
   - 定义特殊状态 A 和 B 的奖励与传送规则

2. 定义状态转移函数 step(s, a)：
   - 如果当前状态是 A 或 B，返回对应的传送状态和特殊奖励
   - 否则按动作方向移动一格，若撞墙则保持原地并给予 -1 奖励

3. 构建 Bellman 方程系统 (Av = b)：
   - 初始化系数矩阵 A 和常数项向量 b 为全零
   - 对每个状态 s：
       对每个动作 a：
           - 根据 step(s, a) 得到后继状态 s′ 和即时奖励 r
           - 将 0.25 × γ 加入 A[s, s′]（均匀策略）
           - 将 0.25 × r 加入 b[s]
       - 将 A[s, s] 减去 1，把所有项移到等式左边

4. 求解线性系统 Av = b，得到每个状态的 v(s)

5. 将结果重排为 5x5 网格，输出每个格子的状态价值

运行代码得到结果：

到这里，我们完成了该问题的“评估”，即根据给定策略，得到其状态价值函数。（该步骤一般被称为策略评估，policy evaluation）。

通过上述求解，我们找到了每个格子所代表的该状态下按当前策略（即四个方向等概率）行动时，所有方向对应的回报加权平均之后的期望值。

如果想要获得更加详细的解，即在每个格子处对应的四个方向分别的价值，我们就需要求解状态动作价值函数了。

在书中3.5章节中介绍了最优贝尔曼方程后，给出了Gridworld的具体解。

---

附：Math

Math 3.1

证明：式3.10的右半部分，即以下几何级数恒等式在\(0 \leq \gamma < 1\)的前提下成立：

\[ G_t = \sum_{k=0}^{\infty} \gamma^k = \frac{1}{1 - \gamma} \]

证明：

考虑无穷级数：

\[ S = \sum_{k=0}^{\infty} \gamma^k = 1 + \gamma + \gamma^2 + \gamma^3 + \cdots \]

这是一个公比为 \(\gamma\) 的等比数列。我们使用以下等比级数求和公式（适用于 \(|\gamma| < 1\)）：

\[ \sum_{k=0}^{\infty} r^k = \frac{1}{1 - r} \]

所以直接代入得到：

\[ \sum_{k=0}^{\infty} \gamma^k = \frac{1}{1 - \gamma} \]

另一个代数方法（构造法）：

令：

\[ S = 1 + \gamma + \gamma^2 + \gamma^3 + \cdots \]

两边同时乘以 \(\gamma\)：

\[ \gamma S = \gamma + \gamma^2 + \gamma^3 + \cdots \]

两式相减：

\[ S - \gamma S = 1 \\ S(1 - \gamma) = 1 \\ S = \frac{1}{1 - \gamma} \]

证毕。

---

math 3.2