最优策略与最优价值函数

解决一个强化学习任务，本质上是找到一种能在长期运行中最大化累积奖励的策略。

对于有限 MDP，价值函数在策略之间定义了一种偏序关系，若策略 $\pi$ 在所有状态下的期望回报都不小于另一策略 ${\pi }^{\prime }$，即$v_{\pi }(s)\ge v_{{\pi }^{\prime }}(s),\forall s\in \mathcal{S}$，则称 $\pi$ 优于或等于 ${\pi }^{\prime }$，记作 $\pi \ge {\pi }^{\prime }$。同时总存在至少一个策略，它优于或等于所有其他策略，这样的策略称为最优策略，记为 ${\pi }_{\ast }$。可能存在多个最优策略，但它们都具有相同的长期性能。

所有最优策略共享同一个状态价值函数，称为最优状态价值函数：

$$v_{\ast }(s)\doteq \underset{\pi }{\max }{v}_{\pi }(s),\forall s\in \mathcal{S}\text{\hspace{1em}(3.15)}$$

$v_{\ast }(s)$ 表示从状态 $s$ 出发，遵循某个最优策略所能获得的最大期望回报。

所有最优策略共享同一个动作价值函数，称为最优动作价值函数：

$$q_{\ast }(s,a)\doteq \underset{\pi }{\max }{q}_{\pi }(s,a),\forall s\in \mathcal{S},a\in \mathcal{A}(s)\text{\hspace{1em}(3.16)}$$

$q_{\ast }(s,a)$ 表示在状态 $s$ 执行动作 $a$ 后，再遵循某个最优策略所能获得的最大期望回报。

$$q_{\ast }(s,a)=\mathbb{E}[R_{t+1}+\gamma v_{\ast }(S_{t+1})\mid S_t=s,A_t=a]\text{\hspace{1em}(3.17)}$$

执行动作 $a$ 后的最优价值 = 即时奖励期望 + 折扣后的最优后继状态价值期望。

贝尔曼最优方程

$v_{\ast }$ 的贝尔曼最优方程

由于 $v_{\ast }$ 是某个最优策略的价值函数，它必须满足贝尔曼方程。但由于其“最优性”，该方程可以写成不依赖具体策略的形式。

$$\begin{array}{rl}{v}_{\ast }(s)& =\underset{a\in \mathcal{A}(s)}{\max }{q}_{\ast }(s,a)\\ & =\underset{a}{\max }\mathbb{E}\left[R_{t+1}+\gamma v_{\ast }(S_{t+1})\mid S_t=s,A_t=a\right]\\ & =\underset{a}{\max }\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)\left[r+\gamma v_{\ast }(s^{\prime })\right]\end{array}\text{\hspace{1em}(3.19)}$$

最优状态下，价值等于所有可能动作中最大期望回报。

$q_{\ast }$ 的贝尔曼最优方程

$$\begin{array}{rl}{q}_{\ast }(s,a)& =\mathbb{E}\left[R_{t+1}+\gamma \underset{a^{\prime }}{\max }{q}_{\ast }(S_{t+1},a^{\prime })|S_t=s,A_t=a\right]\\ & =\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)\left[r+\gamma \underset{a^{\prime }}{\max }{q}_{\ast }(s^{\prime },a^{\prime })\right]\end{array}\text{\hspace{1em}(3.20)}$$

区别于普通贝尔曼方程：这里对未来取最大值而非策略期望。

与普通备份图类似，但选择点增加弧线；弧线表示：此处取最大值，而非期望（${\mathbb{E}}_{\pi }$）。

唯一解与最优策略的构造

对于有限 MDP，贝尔曼最优方程 (3.19) 有唯一解。它是一个包含 $n=|\mathcal{S}|$ 个方程和 $n$ 个未知数（每个状态的 $v_{\ast }(s)$）的非线性方程组。若动态函数 $p$ 已知，原则上可通过数值方法求解。

一旦求得 $v_{\ast }$，最优策略可通过贪心策略（greedy policy）构造：对每个状态 $s$，选择使贝尔曼最优方程中最大值成立的动作：
$${\pi }_{\ast }(a|s)>0\text{仅当}a\in \arg \underset{a^{\prime }}{\max }\sum _{s^{\prime },r}p(s^{\prime },r|s,a^{\prime })[r+\gamma v_{\ast }(s^{\prime })]$$
任何仅以非零概率选择这些动作的策略都是最优策略。

“贪心”通常指仅考虑短期收益的策略；但 $v_{\ast }$ 已经包含了所有未来最优行为的长期奖励；因此，基于 $v_{\ast }$ 的一步前瞻贪心选择，实际上就是长期最优选择。

$v_{\ast }$ 将长期最优决策“压缩”为每个状态的局部值。

拥有 $q_{\ast }$ 则可使决策更简单：智能体无需知道环境动态 $p$；无需计算后继状态价值；只需对每个状态 $s$，选择：

$$a^{\ast }=\arg \underset{a}{\max }{q}_{\ast }(s,a)$$
因为$q_{\ast }$ 缓存了所有一步搜索的结果，是最直接的最优动作指南

上文案例

网格世界

图 3.5： 网格世界的最优解

• 左图：任务结构（同图 3.2）
• 中图：最优状态价值函数 $v_{\ast }$
• 右图：最优策略（箭头表示最优动作，多个箭头表示多个动作同优）

易见：

• $A$ 和 $B$ 附近价值高
• 边缘区域价值低（避免撞墙）
• 从任意位置出发，策略引导朝向 $A$ 或 $B$

回收机器人

状态：high (h), low (l)
动作：search (s), wait (w), recharge (re)
简写期望奖励：$r_s=r_{\text{search}},r_w=r_{\text{wait}}$

$v_{\ast }(h)$ 的贝尔曼最优方程
v∗(h)=max⁡{选择 search:α[rs+γv∗(h)]+(1−α)[rs+γv∗(l)]选择 wait:1⋅[rw+γv∗(h)]}=max⁡{rs+γ[αv∗(h)+(1−α)v∗(l)],rw+γv∗(h)} \begin{aligned} v_*(h) &= \max \left\{ \begin{array}{l} \text{选择 search:} \quad \alpha [r_s + \gamma v_*(h)] + (1 - \alpha) [r_s + \gamma v_*(l)] \\ \text{选择 wait:} \quad 1 \cdot [r_w + \gamma v_*(h)] \end{array} \right\} \\ &= \max \left\{ r_s + \gamma [\alpha v_*(h) + (1 - \alpha) v_*(l)],\quad r_w + \gamma v_*(h) \right\} \end{aligned} v∗​(h)​=max{选择 search:α[rs​+γv∗​(h)]+(1−α)[rs​+γv∗​(l)]选择 wait:1⋅[rw​+γv∗​(h)]​}=max{rs​+γ[αv∗​(h)+(1−α)v∗​(l)],rw​+γv∗​(h)}​

$v_{\ast }(l)$ 的贝尔曼最优方程
$$v_{\ast }(l)=\max \left\{\begin{array}{l}\text{search:}\beta r_s-3(1-\beta )+\gamma [(1-\beta )v_{\ast }(h)+\beta v_{\ast }(l)]\\ \text{wait:}{r}_w+\gamma v_{\ast }(l)\\ \text{recharge:}\gamma v_{\ast }(h)\end{array}\right\}$$

对任意 $0\le \gamma <1$，$0\le \alpha ,\beta \le 1$，存在唯一解 $(v_{\ast }(h),v_{\ast }(l))$

显式求解与近似方法

虽然理论上可通过求解贝尔曼最优方程得到最优策略，但极少直接实用，因为依赖以下三个理想假设：

假设	是否常成立	说明
1. 环境动态 $p$ 已知	很少	需要完整模型
2. 足够计算资源	常不成立	状态空间巨大时不可行
3. 马尔可夫性质成立	通常假设成立	本书基础

3.7 最优性与近似

理论上，实现最优策略意味着智能体表现完美。但在实际任务中，达到最优极为罕见。 最优性是一个理想化的理论目标，实践中我们追求的是“足够好”的近似解。

即使满足以下理想条件，求解最优仍面临巨大挑战：

挑战	说明
计算资源限制	单个时间步内可执行的计算量有限
内存限制	无法存储所有状态的价值或策略
状态空间爆炸	实际任务的状态数远超计算机存储能力

例如国际象棋状态数巨大，远超当前算力可穷举范围。即使拥有完整环境模型（即知道所有规则和转移概率），也无法直接求解贝尔曼最优方程智能体必须在有限时间内做出决策，不能等待“全局最优解”。

强化学习的一个关键特性是其在线学习能力，智能体在与环境交互中逐步学习，可以将学习资源集中在高频出现的状态上，对极少访问的状态，允许次优决策，不影响整体性能。 “在重要状态上做得好”比“在所有状态上都最优”更实用

总结

1. 强化学习的基本范式

通过与环境交互来学习如何行为以实现目标

智能体-环境交互流程：

• 时间步：$ t = 0, 1, 2, \dots $

• 每步发生：
  $$S_t\stackrel{\text{agent}}{\to }{A}_t\stackrel{\text{environment}}{\to }{R}_{t+1},S_{t+1}$$

• 形成轨迹：
  $$S_0,A_0,R_1,S_1,A_1,R_2,\dots$$

---

2. 三大核心信号

信号	含义	作用
状态 $S_t$	当前情境的表示	决策的基础
动作 $A_t$	智能体的选择	实现目标的手段
奖励 $R_{t+1}$	标量反馈信号	定义目标（“你想要什么”）

智能体-环境边界：任何不能被智能体任意改变的事物都属于环境

---

3. 策略（Policy）

• 定义：从状态到动作选择概率的映射
  π(a∣s)=Pr⁡{At=a∣St=s} \pi(a|s) = \Pr\{A_t = a \mid S_t = s\} π(a∣s)=Pr{At​=a∣St​=s}

• 目标：通过经验不断改进策略，使其趋向最优

---

4. 回报（Return）——智能体的目标

智能体的目标是最大化期望回报 $ \mathbb{E}[G_t] $

回报定义因任务类型而异：

任务类型	回报定义	公式
回合制任务（Episodic）	有限步内奖励总和	$ G_t = \sum_{k=0}^{T-t-1} R_{t+k+1} $
持续性任务（Continuing）	折扣无限和	$ G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} $

统一记号：可通过引入吸收状态（absorbing state）将两类任务统一为折扣形式

约束：$ T = \infty $ 与 $ \gamma = 1 $ 不能同时成立，否则回报可能发散

---

5. 价值函数（Value Functions）

价值函数衡量状态或动作的“长期好坏”，基于期望回报。

类型	定义	公式
状态价值函数 $v_{\pi }(s)$	遵循策略 $\pi$ 时，从状态 $s$ 出发的期望回报	$ v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s] $
动作价值函数 $q_{\pi }(s,a)$	执行动作 $a$ 后遵循 $\pi$ 的期望回报	$ q_\pi(s,a) = \mathbb{E}_\pi[G_t \mid S_t = s, A_t = a] $

---

6. 最优价值函数与最优策略

概念	定义	公式
最优状态价值函数 $v_{\ast }(s)$	所有策略中最大的状态价值	$ v_*(s) = \max_\pi v_\pi(s) $
最优动作价值函数 $q_{\ast }(s,a)$	所有策略中最大的动作价值	$ q_*(s,a) = \max_\pi q_\pi(s,a) $
最优策略 ${\pi }_{\ast }$	达到 $v_{\ast }$ 或 $q_{\ast }$ 的任意策略	存在且不唯一

任何关于 $v_{\ast }$ 或 $q_{\ast }$ 贪心的策略都是最优策略

---

7. 贝尔曼最优方程（Bellman Optimality Equations）

最优价值函数满足以下自洽方程：

$v_{\ast }$ 的贝尔曼最优方程：
$$v_{\ast }(s)=\underset{a}{\max }\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)\left[r+\gamma v_{\ast }(s^{\prime })\right]\text{\hspace{1em}(3.19)}$$

$q_{\ast }$ 的贝尔曼最优方程：
$$q_{\ast }(s,a)=\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)\left[r+\gamma \underset{a^{\prime }}{\max }{q}_{\ast }(s^{\prime },a^{\prime })\right]\text{\hspace{1em}(3.20)}$$

这些方程原则上可求解最优价值函数，但实践中常因计算/内存限制而不可行

---

8. 知识假设分类

类型	智能体是否知道环境模型？	说明
完全知识问题	是	拥有完整的动态函数 $p(s’,r
不完全知识问题	否	必须通过交互经验学习模型或直接学习策略

即使在“完全知识”下，也可能因计算限制而无法求解最优

---

9. 近似是必然选择

原因	说明
状态空间过大	无法为每个状态单独存储价值
计算时间有限	无法在每一步完成完整搜索
现实任务复杂	马尔可夫性可能不完全成立

因此，强化学习的核心是：**如何有效地近似最优策略