Chapter 3 - Optimal State Values and Bellman Optimality Equation
Chapter 3 - Optimal State Values and Bellman Optimality Equation#
[!abstract] 本章导读
强化学习的最终目标是寻找最优策略（optimal policy）。本章先用状态价值定义“一个策略比另一个策略好”的含义，再引入贝尔曼最优方程（Bellman optimality equation, BOE）。BOE 把“选择策略”和“计算价值”统一成非线性不动点方程；借助压缩映射定理，可以证明最优价值存在且唯一、给出迭代求解算法，并证明从该价值贪心导出的策略确实最优。最后，本章分析折扣率和奖励设计如何改变最优行为，以及哪些奖励变换不会改变最优策略。
0. 本章知识结构#
图解： Chapter 3 位于基础工具层，承接 Chapter 2 针对给定策略的 Bellman 方程，并直接通向 Chapter 4 的 Value Iteration 与 Policy Iteration。Chapter 3 建立“最优性方程为何有解、解是否唯一、怎样求解、解为何对应最优策略”的理论基础。
flowchart LR
V["给定策略的价值 v_π"] --> C["比较策略<br/>逐状态不劣"]
C --> O["最优策略 π*<br/>最优价值 v*"]
O --> B["Bellman 最优方程<br/>对策略取最大"]
B --> F["不动点 v=f(v)"]
F --> T["压缩映射定理"]
T --> E["存在性 + 唯一性 + 迭代算法"]
E --> G["对 q* 贪心得到最优策略"] 本章的推理主线是：
动作价值改进策略 → 定义最优策略 → 建立 BOE → 证明 BOE 是压缩映射 → 唯一最优价值与迭代求解 → 贪心最优策略 . \text{动作价值改进策略}
\rightarrow \text{定义最优策略}
\rightarrow \text{建立 BOE}
\rightarrow \text{证明 BOE 是压缩映射}
\rightarrow \text{唯一最优价值与迭代求解}
\rightarrow \text{贪心最优策略}. 动作价值改进策略 → 定义最优策略 → 建立 BOE → 证明 BOE 是压缩映射 → 唯一最优价值与迭代求解 → 贪心最优策略 . 1. 动机示例：怎样改进策略？#
图解： 橙色 s 2 s_2 s 2 s 4 s_4 s 4 s 1 s_1 s 1 s 2 s_2 s 2 − 1 -1 − 1 s 1 s_1 s 1 s 3 s_3 s 3
1.1 先评价原策略# 给定策略 π \pi π
v π ( s 1 ) = − 1 + γ v π ( s 2 ) , v π ( s 2 ) = 1 + γ v π ( s 4 ) , v π ( s 3 ) = 1 + γ v π ( s 4 ) , v π ( s 4 ) = 1 + γ v π ( s 4 ) . \begin{aligned}
v_\pi(s_1)&=-1+\gamma v_\pi(s_2),\\
v_\pi(s_2)&=1+\gamma v_\pi(s_4),\\
v_\pi(s_3)&=1+\gamma v_\pi(s_4),\\
v_\pi(s_4)&=1+\gamma v_\pi(s_4).
\end{aligned} v π ( s 1 ) v π ( s 2 ) v π ( s 3 ) v π ( s 4 ) = − 1 + γ v π ( s 2 ) , = 1 + γ v π ( s 4 ) , = 1 + γ v π ( s 4 ) , = 1 + γ v π ( s 4 ) . 当 γ = 0.9 \gamma=0.9 γ = 0.9
v π ( s 4 ) = v π ( s 3 ) = v π ( s 2 ) = 10 , v π ( s 1 ) = 8. v_\pi(s_4)=v_\pi(s_3)=v_\pi(s_2)=10,
\qquad
v_\pi(s_1)=8. v π ( s 4 ) = v π ( s 3 ) = v π ( s 2 ) = 10 , v π ( s 1 ) = 8. 1.2 比较 s 1 s_1 s 1 # 动作 a 1 , a 2 , a 3 , a 4 , a 5 a_1,a_2,a_3,a_4,a_5 a 1 , a 2 , a 3 , a 4 , a 5
q π ( s 1 , a 1 ) = − 1 + γ v π ( s 1 ) = 6.2 , q π ( s 1 , a 2 ) = − 1 + γ v π ( s 2 ) = 8 , q π ( s 1 , a 3 ) = 0 + γ v π ( s 3 ) = 9 , q π ( s 1 , a 4 ) = − 1 + γ v π ( s 1 ) = 6.2 , q π ( s 1 , a 5 ) = 0 + γ v π ( s 1 ) = 7.2. \begin{aligned}
q_\pi(s_1,a_1)&=-1+\gamma v_\pi(s_1)=6.2,\\
q_\pi(s_1,a_2)&=-1+\gamma v_\pi(s_2)=8,\\
q_\pi(s_1,a_3)&=0+\gamma v_\pi(s_3)=9,\\
q_\pi(s_1,a_4)&=-1+\gamma v_\pi(s_1)=6.2,\\
q_\pi(s_1,a_5)&=0+\gamma v_\pi(s_1)=7.2.
\end{aligned} q π ( s 1 , a 1 ) q π ( s 1 , a 2 ) q π ( s 1 , a 3 ) q π ( s 1 , a 4 ) q π ( s 1 , a 5 ) = − 1 + γ v π ( s 1 ) = 6.2 , = − 1 + γ v π ( s 2 ) = 8 , = 0 + γ v π ( s 3 ) = 9 , = − 1 + γ v π ( s 1 ) = 6.2 , = 0 + γ v π ( s 1 ) = 7.2. 由于
q π ( s 1 , a 3 ) ≥ q π ( s 1 , a i ) , ∀ i ≠ 3 , q_\pi(s_1,a_3)\geq q_\pi(s_1,a_i),\qquad \forall i\neq3, q π ( s 1 , a 3 ) ≥ q π ( s 1 , a i ) , ∀ i = 3 , 可将策略在 s 1 s_1 s 1 a 3 a_3 a 3 在一个状态选择动作价值最大的动作，可以改进策略。
本例只在 s 1 s_1 s 1
2. 最优状态价值与最优策略# 先定义策略之间的偏序。若对任意状态都有
v π 1 ( s ) ≥ v π 2 ( s ) , ∀ s ∈ S , v_{\pi_1}(s)\geq v_{\pi_2}(s),\qquad \forall s\in\mathcal S, v π 1 ( s ) ≥ v π 2 ( s ) , ∀ s ∈ S , 则称 π 1 \pi_1 π 1 π 2 \pi_2 π 2
[!definition] Definition 3.1 - 最优策略与最优状态价值
若策略 π ∗ \pi^* π ∗ π \pi π s ∈ S s\in\mathcal S s ∈ S
v π ∗ ( s ) ≥ v π ( s ) , v_{\pi^*}(s)\geq v_\pi(s), v π ∗ ( s ) ≥ v π ( s ) , 则 π ∗ \pi^* π ∗ π ∗ \pi^* π ∗
记最优状态价值为
v ∗ = v π ∗ . v^*=v_{\pi^*}. v ∗ = v π ∗ . 这个定义要求同一个策略在每个状态 都不劣于任何其他策略，而不是只在某个初始状态上表现最好。它立即提出四个必须解决的问题：
存在性 ：最优策略是否存在？唯一性 ：最优策略是否唯一？随机性 ：最优策略是随机策略还是确定性策略？算法 ：怎样得到最优策略和最优状态价值？
[!warning] 教材适用范围说明
教材在本章 Q&A 中强调，上述逐状态比较定义面向表格型强化学习。使用函数近似表示价值或策略时，需要采用其他评价指标；相关内容将在 Chapter 8 和 Chapter 9 展开。
3. Bellman 最优方程# 3.1 逐状态形式# 对每个 s ∈ S s\in\mathcal S s ∈ S
v ( s ) = max π ( s ) ∈ Π ( s ) ∑ a ∈ A π ( a ∣ s ) ( ∑ r ∈ R p ( r ∣ s , a ) r + γ ∑ s ′ ∈ S p ( s ′ ∣ s , a ) v ( s ′ ) ) = max π ( s ) ∈ Π ( s ) ∑ a ∈ A π ( a ∣ s ) q ( s , a ) , \begin{aligned}
v(s)
&=\max_{\pi(s)\in\Pi(s)}
\sum_{a\in\mathcal A}\pi(a\mid s)
\left(
\sum_{r\in\mathcal R}p(r\mid s,a)r
+\gamma\sum_{s'\in\mathcal S}p(s'\mid s,a)v(s')
\right)\\
&=\max_{\pi(s)\in\Pi(s)}
\sum_{a\in\mathcal A}\pi(a\mid s)q(s,a),
\end{aligned} v ( s ) = π ( s ) ∈ Π ( s ) max a ∈ A ∑ π ( a ∣ s ) ( r ∈ R ∑ p ( r ∣ s , a ) r + γ s ′ ∈ S ∑ p ( s ′ ∣ s , a ) v ( s ′ ) ) = π ( s ) ∈ Π ( s ) max a ∈ A ∑ π ( a ∣ s ) q ( s , a ) , 其中
q ( s , a ) ≜ ∑ r ∈ R p ( r ∣ s , a ) r + γ ∑ s ′ ∈ S p ( s ′ ∣ s , a ) v ( s ′ ) . q(s,a)\triangleq
\sum_{r\in\mathcal R}p(r\mid s,a)r
+\gamma\sum_{s'\in\mathcal S}p(s'\mid s,a)v(s'). q ( s , a ) ≜ r ∈ R ∑ p ( r ∣ s , a ) r + γ s ′ ∈ S ∑ p ( s ′ ∣ s , a ) v ( s ′ ) .
π ( s ) \pi(s) π ( s ) s s s Π ( s ) \Pi(s) Π ( s ) s s s v ( s ) , v ( s ′ ) v(s),v(s') v ( s ) , v ( s ′ ) q ( s , a ) q(s,a) q ( s , a ) v v v BOE 与普通 Bellman 方程的区别是：普通 Bellman 方程固定 π \pi π v π v_\pi v π
3.2 怎样处理右侧最大化？# BOE 看似用一个方程同时求 v v v π \pi π 先在给定候选价值 v v v
Example 3.1：先解最大化变量，再解不动点变量# 考虑
x = max y ∈ R ( 2 x − 1 − y 2 ) . x=\max_{y\in\mathbb R}(2x-1-y^2). x = y ∈ R max ( 2 x − 1 − y 2 ) . 无论 x x x y y y y = 0 y=0 y = 0
max y ( 2 x − 1 − y 2 ) = 2 x − 1. \max_y(2x-1-y^2)=2x-1. y max ( 2 x − 1 − y 2 ) = 2 x − 1. 再解 x = 2 x − 1 x=2x-1 x = 2 x − 1 x = 1 x=1 x = 1 x = 1 , y = 0 x=1,y=0 x = 1 , y = 0
Example 3.2：概率加权平均的最大值# 给定 q 1 , q 2 , q 3 ∈ R q_1,q_2,q_3\in\mathbb R q 1 , q 2 , q 3 ∈ R
∑ i = 1 3 c i q i , \sum_{i=1}^3c_iq_i, i = 1 ∑ 3 c i q i , 约束为 c 1 + c 2 + c 3 = 1 c_1+c_2+c_3=1 c 1 + c 2 + c 3 = 1 c i ≥ 0 c_i\geq0 c i ≥ 0 q 3 ≥ q 1 , q 2 q_3\geq q_1,q_2 q 3 ≥ q 1 , q 2 c 3 ∗ = 1 , c 1 ∗ = c 2 ∗ = 0 c_3^*=1,c_1^*=c_2^*=0 c 3 ∗ = 1 , c 1 ∗ = c 2 ∗ = 0
q 3 = ( c 1 + c 2 + c 3 ) q 3 ≥ c 1 q 1 + c 2 q 2 + c 3 q 3 . q_3=(c_1+c_2+c_3)q_3
\geq c_1q_1+c_2q_2+c_3q_3. q 3 = ( c 1 + c 2 + c 3 ) q 3 ≥ c 1 q 1 + c 2 q 2 + c 3 q 3 . 同理，由 ∑ a π ( a ∣ s ) = 1 \sum_a\pi(a\mid s)=1 ∑ a π ( a ∣ s ) = 1
∑ a ∈ A π ( a ∣ s ) q ( s , a ) ≤ ∑ a ∈ A π ( a ∣ s ) max a ′ ∈ A q ( s , a ′ ) = max a ∈ A q ( s , a ) . \begin{aligned}
\sum_{a\in\mathcal A}\pi(a\mid s)q(s,a)
&\leq\sum_{a\in\mathcal A}\pi(a\mid s)
\max_{a'\in\mathcal A}q(s,a')\\
&=\max_{a\in\mathcal A}q(s,a).
\end{aligned} a ∈ A ∑ π ( a ∣ s ) q ( s , a ) ≤ a ∈ A ∑ π ( a ∣ s ) a ′ ∈ A max q ( s , a ′ ) = a ∈ A max q ( s , a ) . 等号可由确定性策略取得：
π ( a ∣ s ) = { 1 , a = a ∗ , 0 , a ≠ a ∗ , a ∗ ∈ arg max a q ( s , a ) . \pi(a\mid s)=
\begin{cases}
1,&a=a^*,\\
0,&a\neq a^*,
\end{cases}
\qquad
a^*\in\arg\max_aq(s,a). π ( a ∣ s ) = { 1 , 0 , a = a ∗ , a = a ∗ , a ∗ ∈ arg a max q ( s , a ) . 因此，对 BOE 右侧最大化的策略就是选择最大 q ( s , a ) q(s,a) q ( s , a )
[!note] 补充理解
若多个动作并列最大，任何只在这些最大动作之间分配概率的策略都能取得相同最大值。这解释了为什么最优价值可以唯一，而最优策略可能不唯一或是随机的。
3.3 矩阵—向量形式与不动点# 把所有状态的方程合并：
v = max π ∈ Π ( r π + γ P π v ) \boxed{
v=\max_{\pi\in\Pi}(r_\pi+\gamma P_\pi v)
} v = π ∈ Π max ( r π + γ P π v ) 其中最大化按元素进行，且
[ r π ] s ≜ ∑ a ∈ A π ( a ∣ s ) ∑ r ∈ R p ( r ∣ s , a ) r , [r_\pi]_s
\triangleq\sum_{a\in\mathcal A}\pi(a\mid s)
\sum_{r\in\mathcal R}p(r\mid s,a)r, [ r π ] s ≜ a ∈ A ∑ π ( a ∣ s ) r ∈ R ∑ p ( r ∣ s , a ) r , [ P π ] s , s ′ ≜ p π ( s ′ ∣ s ) = ∑ a ∈ A π ( a ∣ s ) p ( s ′ ∣ s , a ) . [P_\pi]_{s,s'}
\triangleq p_\pi(s'\mid s)
=\sum_{a\in\mathcal A}\pi(a\mid s)p(s'\mid s,a). [ P π ] s , s ′ ≜ p π ( s ′ ∣ s ) = a ∈ A ∑ π ( a ∣ s ) p ( s ′ ∣ s , a ) . 定义 Bellman 最优算子
f ( v ) ≜ max π ∈ Π ( r π + γ P π v ) , f(v)\triangleq\max_{\pi\in\Pi}(r_\pi+\gamma P_\pi v), f ( v ) ≜ π ∈ Π max ( r π + γ P π v ) , BOE 就是非线性不动点方程
v = f ( v ) . \boxed{v=f(v).} v = f ( v ) . 之所以非线性，是因为取得最大值的策略会随 v v v
3.4 固定点与压缩映射#
[!definition] 固定点（fixed point）
对函数 f : R d → R d f:\mathbb R^d\rightarrow\mathbb R^d f : R d → R d f ( x ∗ ) = x ∗ f(x^*)=x^* f ( x ∗ ) = x ∗ x ∗ x^* x ∗ f f f
[!definition] 压缩映射（contraction mapping）
若存在 γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) x 1 , x 2 ∈ R d x_1,x_2\in\mathbb R^d x 1 , x 2 ∈ R d
∥ f ( x 1 ) − f ( x 2 ) ∥ ≤ γ ∥ x 1 − x 2 ∥ , \lVert f(x_1)-f(x_2)\rVert
\leq\gamma\lVert x_1-x_2\rVert, ∥ f ( x 1 ) − f ( x 2 )∥ ≤ γ ∥ x 1 − x 2 ∥ , 则 f f f
直观上，压缩映射把任意两点之间的距离至少缩小一个小于 1 1 1
Example 3.3：三个压缩映射#
f ( x ) = 0.5 x f(x)=0.5x f ( x ) = 0.5 x 0 0 0
∣ 0.5 x 1 − 0.5 x 2 ∣ = 0.5 ∣ x 1 − x 2 ∣ . \lvert0.5x_1-0.5x_2\rvert
=0.5\lvert x_1-x_2\rvert. ∣ 0.5 x 1 − 0.5 x 2 ∣ = 0.5 ∣ x 1 − x 2 ∣ .
f ( x ) = A x f(x)=Ax f ( x ) = A x ∥ A ∥ ≤ γ < 1 \lVert A\rVert\leq\gamma<1 ∥ A ∥ ≤ γ < 1
∥ A x 1 − A x 2 ∥ ≤ ∥ A ∥ ∥ x 1 − x 2 ∥ ≤ γ ∥ x 1 − x 2 ∥ . \lVert Ax_1-Ax_2\rVert
\leq\lVert A\rVert\lVert x_1-x_2\rVert
\leq\gamma\lVert x_1-x_2\rVert. ∥ A x 1 − A x 2 ∥ ≤ ∥ A ∥ ∥ x 1 − x 2 ∥ ≤ γ ∥ x 1 − x 2 ∥ .
f ( x ) = 0.5 sin x f(x)=0.5\sin x f ( x ) = 0.5 sin x x 3 x_3 x 3 x 1 , x 2 x_1,x_2 x 1 , x 2
∣ 0.5 sin x 1 − 0.5 sin x 2 x 1 − x 2 ∣ = ∣ 0.5 cos x 3 ∣ ≤ 0.5. \left\lvert
\frac{0.5\sin x_1-0.5\sin x_2}{x_1-x_2}
\right\rvert
=\lvert0.5\cos x_3\rvert\leq0.5. x 1 − x 2 0.5 sin x 1 − 0.5 sin x 2 = ∣ 0.5 cos x 3 ∣ ≤ 0.5. 因而 ∣ 0.5 sin x 1 − 0.5 sin x 2 ∣ ≤ 0.5 ∣ x 1 − x 2 ∣ \lvert0.5\sin x_1-0.5\sin x_2\rvert\leq0.5\lvert x_1-x_2\rvert ∣ 0.5 sin x 1 − 0.5 sin x 2 ∣ ≤ 0.5 ∣ x 1 − x 2 ∣
[!theorem] Theorem 3.1 - 压缩映射定理
对实向量方程 x = f ( x ) x=f(x) x = f ( x ) f f f
固定点 x ∗ x^* x ∗
固定点唯一；
对任意初值 x 0 x_0 x 0 x k + 1 = f ( x k ) x_{k+1}=f(x_k) x k + 1 = f ( x k ) x ∗ x^* x ∗
收敛速度为指数级。
Example 3.4：用迭代求固定点# 上面的三个例子都可以从任意初值迭代：
x k + 1 = 0.5 x k , x k + 1 = A x k , x k + 1 = 0.5 sin x k . x_{k+1}=0.5x_k,
\qquad
x_{k+1}=Ax_k,
\qquad
x_{k+1}=0.5\sin x_k. x k + 1 = 0.5 x k , x k + 1 = A x k , x k + 1 = 0.5 sin x k . 它们都收敛到唯一固定点 x ∗ = 0 x^*=0 x ∗ = 0
3.5 Box 3.1：压缩映射定理证明# Part 1：迭代序列收敛# 令 x k = f ( x k − 1 ) x_k=f(x_{k-1}) x k = f ( x k − 1 )
∥ x k + 1 − x k ∥ ≤ γ ∥ x k − x k − 1 ∥ ≤ ⋯ ≤ γ k ∥ x 1 − x 0 ∥ . \lVert x_{k+1}-x_k\rVert
\leq\gamma\lVert x_k-x_{k-1}\rVert
\leq\cdots\leq\gamma^k\lVert x_1-x_0\rVert. ∥ x k + 1 − x k ∥ ≤ γ ∥ x k − x k − 1 ∥ ≤ ⋯ ≤ γ k ∥ x 1 − x 0 ∥ . 仅有相邻差趋零还不足以证明序列收敛。例如 x n = n x_n=\sqrt n x n = n x n + 1 − x n → 0 x_{n+1}-x_n\rightarrow0 x n + 1 − x n → 0
对任意 m > n m>n m > n
∥ x m − x n ∥ ≤ ∥ x m − x m − 1 ∥ + ⋯ + ∥ x n + 1 − x n ∥ ≤ ( γ m − 1 + ⋯ + γ n ) ∥ x 1 − x 0 ∥ ≤ γ n 1 − γ ∥ x 1 − x 0 ∥ . \begin{aligned}
\lVert x_m-x_n\rVert
&\leq\lVert x_m-x_{m-1}\rVert+\cdots+\lVert x_{n+1}-x_n\rVert\\
&\leq(\gamma^{m-1}+\cdots+\gamma^n)\lVert x_1-x_0\rVert\\
&\leq\frac{\gamma^n}{1-\gamma}\lVert x_1-x_0\rVert.
\end{aligned} ∥ x m − x n ∥ ≤ ∥ x m − x m − 1 ∥ + ⋯ + ∥ x n + 1 − x n ∥ ≤ ( γ m − 1 + ⋯ + γ n ) ∥ x 1 − x 0 ∥ ≤ 1 − γ γ n ∥ x 1 − x 0 ∥ . 因为 γ n → 0 \gamma^n\rightarrow0 γ n → 0 ε > 0 \varepsilon>0 ε > 0 N N N m , n > N m,n>N m , n > N ∥ x m − x n ∥ < ε \lVert x_m-x_n\rVert<\varepsilon ∥ x m − x n ∥ < ε x ∗ x^* x ∗
Part 2：极限是固定点# ∥ f ( x k ) − x k ∥ = ∥ x k + 1 − x k ∥ ≤ γ k ∥ x 1 − x 0 ∥ → 0. \lVert f(x_k)-x_k\rVert
=\lVert x_{k+1}-x_k\rVert
\leq\gamma^k\lVert x_1-x_0\rVert\rightarrow0. ∥ f ( x k ) − x k ∥ = ∥ x k + 1 − x k ∥ ≤ γ k ∥ x 1 − x 0 ∥ → 0. 取极限得到 f ( x ∗ ) = x ∗ f(x^*)=x^* f ( x ∗ ) = x ∗
Part 3：固定点唯一# 假设还有固定点 x ′ x' x ′
∥ x ′ − x ∗ ∥ = ∥ f ( x ′ ) − f ( x ∗ ) ∥ ≤ γ ∥ x ′ − x ∗ ∥ . \lVert x'-x^*\rVert
=\lVert f(x')-f(x^*)\rVert
\leq\gamma\lVert x'-x^*\rVert. ∥ x ′ − x ∗ ∥ = ∥ f ( x ′ ) − f ( x ∗ )∥ ≤ γ ∥ x ′ − x ∗ ∥ . 由于 γ < 1 \gamma<1 γ < 1 ∥ x ′ − x ∗ ∥ = 0 \lVert x'-x^*\rVert=0 ∥ x ′ − x ∗ ∥ = 0 x ′ = x ∗ x'=x^* x ′ = x ∗
Part 4：指数收敛# 让上面的 m → ∞ m\rightarrow\infty m → ∞
∥ x ∗ − x n ∥ ≤ γ n 1 − γ ∥ x 1 − x 0 ∥ . \boxed{
\lVert x^*-x_n\rVert
\leq\frac{\gamma^n}{1-\gamma}\lVert x_1-x_0\rVert.
} ∥ x ∗ − x n ∥ ≤ 1 − γ γ n ∥ x 1 − x 0 ∥ . 因此误差按 γ n \gamma^n γ n
3.6 BOE 右侧的压缩性质# 教材使用最大范数
∥ v ∥ ∞ = max i ∣ v i ∣ . \lVert v\rVert_\infty=\max_i\lvert v_i\rvert. ∥ v ∥ ∞ = i max ∣ v i ∣ .
[!theorem] Theorem 3.2 - Bellman 最优算子的压缩性
对任意 v 1 , v 2 ∈ R ∣ S ∣ v_1,v_2\in\mathbb R^{\lvert\mathcal S\rvert} v 1 , v 2 ∈ R ∣ S ∣
∥ f ( v 1 ) − f ( v 2 ) ∥ ∞ ≤ γ ∥ v 1 − v 2 ∥ ∞ . \lVert f(v_1)-f(v_2)\rVert_\infty
\leq\gamma\lVert v_1-v_2\rVert_\infty. ∥ f ( v 1 ) − f ( v 2 ) ∥ ∞ ≤ γ ∥ v 1 − v 2 ∥ ∞ . 因而 f f f
Box 3.2：Theorem 3.2 证明# 令
π 1 ∗ ∈ arg max π ( r π + γ P π v 1 ) , π 2 ∗ ∈ arg max π ( r π + γ P π v 2 ) . \pi_1^*\in\arg\max_\pi(r_\pi+\gamma P_\pi v_1),
\qquad
\pi_2^*\in\arg\max_\pi(r_\pi+\gamma P_\pi v_2). π 1 ∗ ∈ arg π max ( r π + γ P π v 1 ) , π 2 ∗ ∈ arg π max ( r π + γ P π v 2 ) . 由最大值定义，
f ( v 1 ) = r π 1 ∗ + γ P π 1 ∗ v 1 ≥ r π 2 ∗ + γ P π 2 ∗ v 1 , f(v_1)=r_{\pi_1^*}+\gamma P_{\pi_1^*}v_1
\geq r_{\pi_2^*}+\gamma P_{\pi_2^*}v_1, f ( v 1 ) = r π 1 ∗ + γ P π 1 ∗ v 1 ≥ r π 2 ∗ + γ P π 2 ∗ v 1 , f ( v 2 ) = r π 2 ∗ + γ P π 2 ∗ v 2 ≥ r π 1 ∗ + γ P π 1 ∗ v 2 . f(v_2)=r_{\pi_2^*}+\gamma P_{\pi_2^*}v_2
\geq r_{\pi_1^*}+\gamma P_{\pi_1^*}v_2. f ( v 2 ) = r π 2 ∗ + γ P π 2 ∗ v 2 ≥ r π 1 ∗ + γ P π 1 ∗ v 2 . 于是逐元素有
γ P π 2 ∗ ( v 1 − v 2 ) ≤ f ( v 1 ) − f ( v 2 ) ≤ γ P π 1 ∗ ( v 1 − v 2 ) . \gamma P_{\pi_2^*}(v_1-v_2)
\leq f(v_1)-f(v_2)
\leq\gamma P_{\pi_1^*}(v_1-v_2). γ P π 2 ∗ ( v 1 − v 2 ) ≤ f ( v 1 ) − f ( v 2 ) ≤ γ P π 1 ∗ ( v 1 − v 2 ) . 定义逐元素非负向量
z ≜ max { ∣ γ P π 2 ∗ ( v 1 − v 2 ) ∣ , ∣ γ P π 1 ∗ ( v 1 − v 2 ) ∣ } , z\triangleq\max\left\{
\left\lvert\gamma P_{\pi_2^*}(v_1-v_2)\right\rvert,
\left\lvert\gamma P_{\pi_1^*}(v_1-v_2)\right\rvert
\right\}, z ≜ max { γ P π 2 ∗ ( v 1 − v 2 ) , γ P π 1 ∗ ( v 1 − v 2 ) } , 则 ∣ f ( v 1 ) − f ( v 2 ) ∣ ≤ z \lvert f(v_1)-f(v_2)\rvert\leq z ∣ f ( v 1 ) − f ( v 2 )∣ ≤ z
∥ f ( v 1 ) − f ( v 2 ) ∥ ∞ ≤ ∥ z ∥ ∞ . \lVert f(v_1)-f(v_2)\rVert_\infty
\leq\lVert z\rVert_\infty. ∥ f ( v 1 ) − f ( v 2 ) ∥ ∞ ≤ ∥ z ∥ ∞ . 对 P π 1 ∗ P_{\pi_1^*} P π 1 ∗ P π 2 ∗ P_{\pi_2^*} P π 2 ∗ p i T p_i^T p i T 1 1 1
∣ p i T ( v 1 − v 2 ) ∣ ≤ p i T ∣ v 1 − v 2 ∣ ≤ ∥ v 1 − v 2 ∥ ∞ . \left\lvert p_i^T(v_1-v_2)\right\rvert
\leq p_i^T\lvert v_1-v_2\rvert
\leq\lVert v_1-v_2\rVert_\infty. p i T ( v 1 − v 2 ) ≤ p i T ∣ v 1 − v 2 ∣ ≤ ∥ v 1 − v 2 ∥ ∞ . 从而 ∥ z ∥ ∞ ≤ γ ∥ v 1 − v 2 ∥ ∞ \lVert z\rVert_\infty\leq\gamma\lVert v_1-v_2\rVert_\infty ∥ z ∥ ∞ ≤ γ ∥ v 1 − v 2 ∥ ∞
[!tip] 证明的核心思想
最大化可能让 v 1 v_1 v 1 v 2 v_2 v 2 γ < 1 \gamma<1 γ < 1
4. 从 BOE 求最优策略# 4.1 最优价值的存在、唯一与算法#
[!theorem] Theorem 3.3 - 存在性、唯一性与算法
BOE
v = f ( v ) = max π ∈ Π ( r π + γ P π v ) v=f(v)=\max_{\pi\in\Pi}(r_\pi+\gamma P_\pi v) v = f ( v ) = π ∈ Π max ( r π + γ P π v ) 总有唯一解 v ∗ v^* v ∗ v 0 v_0 v 0
v k + 1 = f ( v k ) = max π ∈ Π ( r π + γ P π v k ) v_{k+1}=f(v_k)=\max_{\pi\in\Pi}(r_\pi+\gamma P_\pi v_k) v k + 1 = f ( v k ) = π ∈ Π max ( r π + γ P π v k ) 都以指数速度收敛到 v ∗ v^* v ∗
证明直接来自 Theorem 3.1 与 Theorem 3.2。该迭代就是**价值迭代（value iteration）**的理论形式；具体实现放在 Chapter 4。
得到 v ∗ v^* v ∗
π ∗ ∈ arg max π ∈ Π ( r π + γ P π v ∗ ) \pi^*\in\arg\max_{\pi\in\Pi}
(r_\pi+\gamma P_\pi v^*) π ∗ ∈ arg π ∈ Π max ( r π + γ P π v ∗ ) 求策略。将其代回 BOE：
v ∗ = r π ∗ + γ P π ∗ v ∗ . v^*=r_{\pi^*}+\gamma P_{\pi^*}v^*. v ∗ = r π ∗ + γ P π ∗ v ∗ . 所以 BOE 确实是一个特殊 Bellman 方程，其对应策略是 π ∗ \pi^* π ∗ v ∗ = v π ∗ v^*=v_{\pi^*} v ∗ = v π ∗
4.2 为什么 BOE 解出的策略真正最优？#
[!theorem] Theorem 3.4 - v ∗ v^* v ∗ π ∗ \pi^* π ∗ v ∗ v^* v ∗ π ∗ \pi^* π ∗ π \pi π
v ∗ = v π ∗ ≥ v π , v^*=v_{\pi^*}\geq v_\pi, v ∗ = v π ∗ ≥ v π , 其中不等式为逐元素比较。
Box 3.3：Theorem 3.4 证明# 任意策略 π \pi π
v π = r π + γ P π v π . v_\pi=r_\pi+\gamma P_\pi v_\pi. v π = r π + γ P π v π . 而 BOE 的最大化保证
v ∗ = max π ′ ( r π ′ + γ P π ′ v ∗ ) ≥ r π + γ P π v ∗ . v^*=\max_{\pi'}(r_{\pi'}+\gamma P_{\pi'}v^*)
\geq r_\pi+\gamma P_\pi v^*. v ∗ = π ′ max ( r π ′ + γ P π ′ v ∗ ) ≥ r π + γ P π v ∗ . 两式相减：
v ∗ − v π ≥ γ P π ( v ∗ − v π ) . v^*-v_\pi
\geq\gamma P_\pi(v^*-v_\pi). v ∗ − v π ≥ γ P π ( v ∗ − v π ) . 反复应用得
v ∗ − v π ≥ γ n P π n ( v ∗ − v π ) . v^*-v_\pi
\geq\gamma^nP_\pi^n(v^*-v_\pi). v ∗ − v π ≥ γ n P π n ( v ∗ − v π ) . 由于 P π n P_\pi^n P π n 1 1 1 γ n → 0 \gamma^n\rightarrow0 γ n → 0 v ∗ − v π ≥ 0 v^*-v_\pi\geq0 v ∗ − v π ≥ 0 π \pi π v ∗ v^* v ∗
4.3 确定性贪心最优策略# 定义最优动作价值
q ∗ ( s , a ) ≜ ∑ r ∈ R p ( r ∣ s , a ) r + γ ∑ s ′ ∈ S p ( s ′ ∣ s , a ) v ∗ ( s ′ ) . q^*(s,a)\triangleq
\sum_{r\in\mathcal R}p(r\mid s,a)r
+\gamma\sum_{s'\in\mathcal S}p(s'\mid s,a)v^*(s'). q ∗ ( s , a ) ≜ r ∈ R ∑ p ( r ∣ s , a ) r + γ s ′ ∈ S ∑ p ( s ′ ∣ s , a ) v ∗ ( s ′ ) .
[!theorem] Theorem 3.5 - 贪心最优策略
对每个 s ∈ S s\in\mathcal S s ∈ S
a ∗ ( s ) ∈ arg max a q ∗ ( s , a ) , a^*(s)\in\arg\max_aq^*(s,a), a ∗ ( s ) ∈ arg a max q ∗ ( s , a ) , 并定义
π ∗ ( a ∣ s ) = { 1 , a = a ∗ ( s ) , 0 , a ≠ a ∗ ( s ) , \pi^*(a\mid s)=
\begin{cases}
1,&a=a^*(s),\\
0,&a\neq a^*(s),
\end{cases} π ∗ ( a ∣ s ) = { 1 , 0 , a = a ∗ ( s ) , a = a ∗ ( s ) , 得到的确定性贪心策略是最优策略。
Box 3.4：Theorem 3.5 证明# 最优策略的逐状态问题是
π ∗ ( s ) ∈ arg max π ( s ) ∈ Π ( s ) ∑ a ∈ A π ( a ∣ s ) q ∗ ( s , a ) . \pi^*(s)\in\arg\max_{\pi(s)\in\Pi(s)}
\sum_{a\in\mathcal A}\pi(a\mid s)q^*(s,a). π ∗ ( s ) ∈ arg π ( s ) ∈ Π ( s ) max a ∈ A ∑ π ( a ∣ s ) q ∗ ( s , a ) . 概率加权平均不可能超过最大分量；把全部概率赋给最大 q ∗ ( s , a ) q^*(s,a) q ∗ ( s , a )
4.4 唯一性与随机性#
图解： 左图在左上状态确定性向右；右图在该状态以 0.5 0.5 0.5 0.5 0.5 0.5
由此得到：
最优状态价值 v ∗ v^* v ∗ ；最优策略未必唯一 ，甚至可能有无穷多个；最优策略可以是确定性的，也可以是随机的；
但 Theorem 3.5 保证至少存在一个确定性贪心最优策略 。
对象 是否保证存在 是否唯一 是否可确定性 最优状态价值 v ∗ v^* v ∗ 是 是 不适用 最优策略 π ∗ \pi^* π ∗ 是 不一定 总能找到确定性最优策略
5. 影响最优策略的因素# 从 BOE 可见，最优价值与策略由三类量决定：
即时奖励 r r r
折扣率 γ \gamma γ
系统模型 p ( s ′ ∣ s , a ) p(s'\mid s,a) p ( s ′ ∣ s , a ) p ( r ∣ s , a ) p(r\mid s,a) p ( r ∣ s , a )
本节固定系统模型，比较折扣率和奖励设置的影响。
5.1 基准示例与折扣率#
图解： 每组左图是最优策略，右图是相应最优价值；橙色为禁止格，青色为目标格。
(a) 基准：γ = 0.9 \gamma=0.9 γ = 0.9 # 设置
r boundary = r forbidden = − 1 , r target = 1 , r other = 0. r_{\text{boundary}}=r_{\text{forbidden}}=-1,
\qquad
r_{\text{target}}=1,
\qquad
r_{\text{other}}=0. r boundary = r forbidden = − 1 , r target = 1 , r other = 0. 较大的折扣率使策略更“远视”。从第 4 行第 1 列出发，绕开所有禁止格的路线很长，而穿过禁止格虽然立即受罚，却能更快到达目标并获得更大的累计回报。因此最优策略可能选择穿越禁止格。
(b) 降至 γ = 0.5 \gamma=0.5 γ = 0.5 # 未来奖励被更强折扣，策略变得短视，不愿承担当前的禁止格惩罚，转而选择较长但避开禁止格的路线。
(c) 极端情形 γ = 0 \gamma=0 γ = 0 # BOE 只剩即时奖励：
q ∗ ( s , a ) = ∑ r ∈ R p ( r ∣ s , a ) r . q^*(s,a)=\sum_{r\in\mathcal R}p(r\mid s,a)r. q ∗ ( s , a ) = r ∈ R ∑ p ( r ∣ s , a ) r . 策略只选择即时奖励最大的动作，不考虑长期结果，因此可能无法到达目标。
图中还有一个空间规律：越靠近目标，状态价值通常越大；离目标越远，目标奖励经过的折扣次数越多，状态价值越低。
5.2 改变奖励大小# 在 Figure 3.4(d) 中，将禁止格奖励从 − 1 -1 − 1 − 10 -10 − 10 相对奖励 可以改变策略。
但并非所有奖励变化都会改变最优策略。教材给出如下不变性。
[!theorem] Theorem 3.6 - 最优策略对奖励仿射变换的不变性
将每个奖励按
r ⟼ α r + β , α > 0 , r\longmapsto\alpha r+\beta,
\qquad \alpha>0, r ⟼ α r + β , α > 0 , 变换后，新的最优价值为
v ′ = α v ∗ + β 1 − γ 1 , \boxed{
v'=\alpha v^*+\frac{\beta}{1-\gamma}\mathbf1,
} v ′ = α v ∗ + 1 − γ β 1 , 其中 1 = [ 1 , … , 1 ] T \mathbf1=[1,\ldots,1]^T 1 = [ 1 , … , 1 ] T v ′ v' v ′
Box 3.5：Theorem 3.6 证明# 对任意策略，奖励向量变为
r π ⟼ α r π + β 1. r_\pi\longmapsto\alpha r_\pi+\beta\mathbf1. r π ⟼ α r π + β 1 . 新的 BOE 是
v ′ = max π ( α r π + β 1 + γ P π v ′ ) . v'=\max_\pi(\alpha r_\pi+\beta\mathbf1+\gamma P_\pi v'). v ′ = π max ( α r π + β 1 + γ P π v ′ ) . 令 c = β / ( 1 − γ ) c=\beta/(1-\gamma) c = β / ( 1 − γ ) v ′ = α v ∗ + c 1 v'=\alpha v^*+c\mathbf1 v ′ = α v ∗ + c 1 P π 1 = 1 P_\pi\mathbf1=\mathbf1 P π 1 = 1
max π ( α r π + β 1 + γ P π v ′ ) = max π ( α r π + β 1 + α γ P π v ∗ + c γ 1 ) = α max π ( r π + γ P π v ∗ ) + ( β + c γ ) 1 = α v ∗ + c 1 , \begin{aligned}
\max_\pi(\alpha r_\pi+\beta\mathbf1+\gamma P_\pi v')
&=\max_\pi(\alpha r_\pi+\beta\mathbf1
+\alpha\gamma P_\pi v^*+c\gamma\mathbf1)\\
&=\alpha\max_\pi(r_\pi+\gamma P_\pi v^*)
+(\beta+c\gamma)\mathbf1\\
&=\alpha v^*+c\mathbf1,
\end{aligned} π max ( α r π + β 1 + γ P π v ′ ) = π max ( α r π + β 1 + α γ P π v ∗ + c γ 1 ) = α π max ( r π + γ P π v ∗ ) + ( β + c γ ) 1 = α v ∗ + c 1 , 因为 β + c γ = c \beta+c\gamma=c β + c γ = c v ′ v' v ′ α > 0 \alpha>0 α > 0
[!warning] 仿射不变性不等于“怎样改奖励都不影响策略”
定理要求对所有奖励统一 使用同一个 α > 0 \alpha>0 α > 0 β \beta β − 1 -1 − 1 − 10 -10 − 10
5.3 为什么最优策略不会无意义绕路？#
图解： 两个策略只在 s 2 s_2 s 2 s 2 s_2 s 2 s 4 s_4 s 4 s 2 s_2 s 2 s 2 → s 1 → s 3 → s 4 s_2\rightarrow s_1\rightarrow s_3\rightarrow s_4 s 2 → s 1 → s 3 → s 4 0 0 0 s 2 s_2 s 2 10 10 10 8.1 8.1 8.1
直接路线的折扣回报为
1 + γ + γ 2 + ⋯ = 1 1 − γ = 10 ( γ = 0.9 ) . 1+\gamma+\gamma^2+\cdots
=\frac{1}{1-\gamma}=10
\qquad(\gamma=0.9). 1 + γ + γ 2 + ⋯ = 1 − γ 1 = 10 ( γ = 0.9 ) . 绕路路线多经历两个零奖励步骤：
0 + γ ⋅ 0 + γ 2 ⋅ 1 + γ 3 ⋅ 1 + ⋯ = γ 2 1 − γ = 8.1. 0+\gamma\cdot0+\gamma^2\cdot1+\gamma^3\cdot1+\cdots
=\frac{\gamma^2}{1-\gamma}=8.1. 0 + γ ⋅ 0 + γ 2 ⋅ 1 + γ 3 ⋅ 1 + ⋯ = 1 − γ γ 2 = 8.1. 即使每个普通移动没有负奖励，越晚获得目标奖励，折扣越严重。因此折扣率本身已经鼓励更短的有效路线。
给每一步统一再加 − 1 -1 − 1
6. 本章总结# 本章从策略改进的直观规则出发：比较同一状态的动作价值，并选择最大的动作。为了把局部改进提升为全局最优性，教材用逐状态价值比较定义最优策略和唯一的最优状态价值。
BOE 把“在每个状态选择最优动作”与“价值必须满足递归关系”合并成 v = f ( v ) v=f(v) v = f ( v ) γ < 1 \gamma<1 γ < 1 v ∗ v^* v ∗ q ∗ ( s , a ) q^*(s,a) q ∗ ( s , a )
价值的唯一性并不推出策略唯一；并列最优动作可以产生多个确定性或随机最优策略。最后，折扣率控制策略的远视程度，相对奖励改变风险偏好，而统一的正比例缩放与常数平移只对最优价值做仿射变换，不改变最优动作的排序。折扣还会自动惩罚延迟获得目标奖励的无意义绕路。
7. 教材 Q&A# Q1：怎样定义最优策略？
若一个策略的状态价值对所有状态都不小于任何其他策略，它就是最优策略。教材说明这一特定定义面向表格型强化学习。
Q2：为什么 BOE 重要？它是 Bellman 方程吗？
BOE 同时刻画最优价值和最优策略；求解它即可得到二者。它是对应策略为最优策略的特殊 Bellman 方程。
Q3：BOE 的解唯一吗？
最优价值解 v ∗ v^* v ∗
Q4：分析 BOE 的关键性质是什么？
其右侧 Bellman 最优算子是压缩映射，因此可用压缩映射定理证明存在性、唯一性和迭代收敛。
Q5：最优策略存在吗？唯一吗？是随机还是确定？
最优策略总存在，但可能有多个甚至无穷多个；它可以是随机的或确定的，而且总能找到确定性贪心最优策略。
Q6：怎样获得最优策略？
用 Theorem 3.3 的迭代算法求解 BOE，再对最终的最优动作价值贪心。具体 Value Iteration 实现见 Chapter 4。
Q7：降低折扣率会怎样？若 γ = 0 \gamma=0 γ = 0
折扣率越小，策略越短视、越不愿为远期收益承担当前风险；γ = 0 \gamma=0 γ = 0
Q8：给所有奖励加同一个常数会怎样？
最优价值会增加 β / ( 1 − γ ) \beta/(1-\gamma) β / ( 1 − γ )
Q9：为了避免绕路，是否必须给每一步加负奖励？
不必。统一加常数不改变最优策略；而折扣本身会让更晚获得的目标奖励价值更低，从而抑制无意义绕路。
8. 一页式复习#
策略比较 ：若 v π 1 ( s ) ≥ v π 2 ( s ) v_{\pi_1}(s)\geq v_{\pi_2}(s) v π 1 ( s ) ≥ v π 2 ( s ) s s s π 1 \pi_1 π 1 π 2 \pi_2 π 2 最优策略 ：v π ∗ ( s ) ≥ v π ( s ) v_{\pi^*}(s)\geq v_\pi(s) v π ∗ ( s ) ≥ v π ( s ) s , π s,\pi s , π BOE ：v = max π ( r π + γ P π v ) = f ( v ) v=\max_\pi(r_\pi+\gamma P_\pi v)=f(v) v = max π ( r π + γ P π v ) = f ( v ) 右侧最大化 ：概率加权平均的最大值由把概率集中到最大动作价值上取得。压缩性 ：∥ f ( v 1 ) − f ( v 2 ) ∥ ∞ ≤ γ ∥ v 1 − v 2 ∥ ∞ \lVert f(v_1)-f(v_2)\rVert_\infty\leq\gamma\lVert v_1-v_2\rVert_\infty ∥ f ( v 1 ) − f ( v 2 ) ∥ ∞ ≤ γ ∥ v 1 − v 2 ∥ ∞ 唯一最优价值 ：压缩映射定理保证 v ∗ v^* v ∗ 价值迭代原型 ：v k + 1 = f ( v k ) v_{k+1}=f(v_k) v k + 1 = f ( v k ) 最优动作价值 ：q ∗ ( s , a ) = E [ R t + 1 + γ v ∗ ( S t + 1 ) ∣ S t = s , A t = a ] q^*(s,a)=\mathbb E[R_{t+1}+\gamma v^*(S_{t+1})\mid S_t=s,A_t=a] q ∗ ( s , a ) = E [ R t + 1 + γ v ∗ ( S t + 1 ) ∣ S t = s , A t = a ] 贪心策略 ：a ∗ ( s ) ∈ arg max a q ∗ ( s , a ) a^*(s)\in\arg\max_aq^*(s,a) a ∗ ( s ) ∈ arg max a q ∗ ( s , a ) 唯一性区别 ：v ∗ v^* v ∗ π ∗ \pi^* π ∗ 折扣率 ：较大更远视；较小更短视；γ = 0 \gamma=0 γ = 0 奖励仿射变换 ：r ↦ α r + β r\mapsto\alpha r+\beta r ↦ α r + β α > 0 \alpha>0 α > 0 α v ∗ + β 1 / ( 1 − γ ) \alpha v^*+\beta\mathbf1/(1-\gamma) α v ∗ + β 1 / ( 1 − γ ) 9. 公式清单#
公式 名称 作用 使用场景 v π ∗ ( s ) ≥ v π ( s ) v_{\pi^*}(s)\geq v_\pi(s) v π ∗ ( s ) ≥ v π ( s ) 最优策略定义 逐状态比较所有策略 定义全局最优性 v = max π ( r π + γ P π v ) v=\max_\pi(r_\pi+\gamma P_\pi v) v = max π ( r π + γ P π v ) BOE 矩阵形式 联立最优选择与价值递归 求最优价值 f ( v ) = max π ( r π + γ P π v ) f(v)=\max_\pi(r_\pi+\gamma P_\pi v) f ( v ) = max π ( r π + γ P π v ) Bellman 最优算子 把 BOE 写成不动点问题 压缩映射分析 ∥ f ( v 1 ) − f ( v 2 ) ∥ ∞ ≤ γ ∥ v 1 − v 2 ∥ ∞ \lVert f(v_1)-f(v_2)\rVert_\infty\leq\gamma\lVert v_1-v_2\rVert_\infty ∥ f ( v 1 ) − f ( v 2 ) ∥ ∞ ≤ γ ∥ v 1 − v 2 ∥ ∞ BOE 压缩性 保证唯一固定点和迭代收敛 理论证明 v k + 1 = f ( v k ) v_{k+1}=f(v_k) v k + 1 = f ( v k ) 价值迭代原型 从任意初值逼近 v ∗ v^* v ∗ 数值求解 BOE q ∗ ( s , a ) = ∑ r ∈ R p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v ∗ ( s ′ ) q^*(s,a)=\sum_{r\in\mathcal R}p(r\mid s,a)r+\gamma\sum_{s'}p(s'\mid s,a)v^*(s') q ∗ ( s , a ) = ∑ r ∈ R p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v ∗ ( s ′ ) 最优动作价值 对动作做一步前瞻 导出最优策略 a ∗ ( s ) ∈ arg max a q ∗ ( s , a ) a^*(s)\in\arg\max_aq^*(s,a) a ∗ ( s ) ∈ arg max a q ∗ ( s , a ) 贪心动作 选择最大最优动作价值 构造确定性最优策略 v ′ = α v ∗ + β 1 − γ 1 v'=\alpha v^*+\frac{\beta}{1-\gamma}\mathbf1 v ′ = α v ∗ + 1 − γ β 1 奖励仿射变换 描述价值随统一奖励变换的变化 奖励设计分析 ∥ x ∗ − x n ∥ ≤ γ n 1 − γ ∥ x 1 − x 0 ∥ \lVert x^*-x_n\rVert\leq\frac{\gamma^n}{1-\gamma}\lVert x_1-x_0\rVert ∥ x ∗ − x n ∥ ≤ 1 − γ γ n ∥ x 1 − x 0 ∥ 压缩迭代误差界 说明指数收敛速度 固定点迭代分析
10. 符号表#
符号 含义 π , π ∗ \pi,\pi^* π , π ∗ 一般策略、最优策略 Π ( s ) , Π \Pi(s),\Pi Π ( s ) , Π 单个状态上的策略集合、整体策略集合 v π , v ∗ v_\pi,v^* v π , v ∗ 策略 π \pi π q π , q ∗ q_\pi,q^* q π , q ∗ 策略动作价值、最优动作价值 r π r_\pi r π 策略诱导的平均即时奖励向量 P π P_\pi P π 策略诱导的状态转移矩阵 f f f Bellman 最优算子 x ∗ x^* x ∗ 一般不动点方程的固定点 γ \gamma γ 折扣率，也是本章压缩系数 ∥ ⋅ ∥ ∞ \lVert\cdot\rVert_\infty ∥ ⋅ ∥ ∞ 最大范数，即最大绝对分量 1 \mathbf1 1 全 1 列向量 α , β \alpha,\beta α , β 奖励仿射变换的缩放和偏移参数 a ∗ ( s ) a^*(s) a ∗ ( s ) 状态 s s s
11. 术语表#
English 中文 简要解释 optimal policy 最优策略 在每个状态都不劣于任何其他策略 optimal state value 最优状态价值 最优策略对应的唯一价值函数 Bellman optimality equation Bellman 最优方程 对策略最大化的价值递归方程 fixed point 固定点 / 不动点 满足 f ( x ∗ ) = x ∗ f(x^*)=x^* f ( x ∗ ) = x ∗ contraction mapping 压缩映射 把任意两点距离按小于 1 的比例缩小的映射 contraction mapping theorem 压缩映射定理 保证固定点存在、唯一及迭代收敛的定理 Cauchy sequence Cauchy 序列 尾部任意元素彼此可任意接近的序列 maximum norm 最大范数 向量分量绝对值的最大值 value iteration 价值迭代 反复应用 Bellman 最优算子的算法 greedy policy 贪心策略 在每个状态选择当前动作价值最大的动作 affine transformation 仿射变换 r ↦ α r + β r\mapsto\alpha r+\beta r ↦ α r + β policy invariance 策略不变性 变换后最优策略集合保持不变
12. 常见误区#
[!warning] 最优价值唯一，所以最优策略也唯一
错。v ∗ v^* v ∗ q ∗ q^* q ∗
[!warning] 最优策略一定是确定性的
不一定；随机策略也可能最优。但一定存在至少一个确定性贪心最优策略。
[!warning] BOE 只是把普通 Bellman 方程中的 π \pi π π ∗ \pi^* π ∗ π ∗ \pi^* π ∗
[!warning] γ \gamma γ γ \gamma γ
[!warning] 给每一步加负奖励一定能改变最优策略
若对所有奖励统一加同一常数，在本章设定下只是仿射平移，不改变最优策略。改变某一类事件的相对奖励才可能改变动作排序。
[!warning] 相邻迭代差 ∥ x k + 1 − x k ∥ → 0 \lVert x_{k+1}-x_k\rVert\rightarrow0 ∥ x k + 1 − x k ∥ → 0 x n = n x_n=\sqrt n x n = n
13. 自测题# 13.1 概念题#
最优状态价值和最优策略的唯一性分别如何？
[!success]- 点击查看答案
v ∗ v^* v ∗
判断：只要某策略在一个常用初始状态上的价值最大，它就是本章定义的最优策略。
[!success]- 点击查看答案
错误。本章定义要求该策略对所有状态的价值都不小于任何其他策略。
为什么 BOE 的压缩性要使用最大范数？
[!success]- 点击查看答案
每个转移矩阵的行是概率分布。对任意行做加权平均，其绝对值不超过输入向量的最大绝对分量，因此 P π P_\pi P π γ < 1 \gamma<1 γ < 1
若多个动作同时达到最大 q ∗ ( s , a ) q^*(s,a) q ∗ ( s , a )
[!success]- 点击查看答案
可确定性地选择任意一个并列最大动作，也可只在这些最大动作之间任意随机化；它们在该状态都达到同一最优值。
13.2 推导与计算题#
给定某状态的动作价值 q ( s , a 1 ) = 2 q(s,a_1)=2 q ( s , a 1 ) = 2 q ( s , a 2 ) = 5 q(s,a_2)=5 q ( s , a 2 ) = 5 q ( s , a 3 ) = 5 q(s,a_3)=5 q ( s , a 3 ) = 5
[!success]- 点击查看答案
最大值为 5 5 5
确定性策略：π ( a 2 ∣ s ) = 1 \pi(a_2\mid s)=1 π ( a 2 ∣ s ) = 1
随机策略：π ( a 2 ∣ s ) = 0.4 \pi(a_2\mid s)=0.4 π ( a 2 ∣ s ) = 0.4 π ( a 3 ∣ s ) = 0.6 \pi(a_3\mid s)=0.6 π ( a 3 ∣ s ) = 0.6
两者都不给 a 1 a_1 a 1 5 5 5
若压缩系数 γ = 0.8 \gamma=0.8 γ = 0.8 ∥ x 1 − x 0 ∥ = 3 \lVert x_1-x_0\rVert=3 ∥ x 1 − x 0 ∥ = 3 n n n
[!success]- 点击查看答案
∥ x ∗ − x n ∥ ≤ 0.8 n 1 − 0.8 × 3 = 15 × 0.8 n . \lVert x^*-x_n\rVert
\leq\frac{0.8^n}{1-0.8}\times3
=15\times0.8^n. ∥ x ∗ − x n ∥ ≤ 1 − 0.8 0. 8 n × 3 = 15 × 0. 8 n .
奖励统一变换为 r ′ = 2 r − 3 r'=2r-3 r ′ = 2 r − 3 γ = 0.9 \gamma=0.9 γ = 0.9 v ∗ v^* v ∗
[!success]- 点击查看答案
这里 α = 2 , β = − 3 \alpha=2,\beta=-3 α = 2 , β = − 3
v ′ = 2 v ∗ + − 3 1 − 0.9 1 = 2 v ∗ − 301. v'=2v^*+\frac{-3}{1-0.9}\mathbf1
=2v^*-30\mathbf1. v ′ = 2 v ∗ + 1 − 0.9 − 3 1 = 2 v ∗ − 30 1 . 因为 α > 0 \alpha>0 α > 0
说明为什么 γ = 0 \gamma=0 γ = 0
[!success]- 点击查看答案
将 γ = 0 \gamma=0 γ = 0
q ∗ ( s , a ) = ∑ r ∈ R p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v ∗ ( s ′ ) q^*(s,a)=\sum_{r\in\mathcal R}p(r\mid s,a)r
+\gamma\sum_{s'}p(s'\mid s,a)v^*(s') q ∗ ( s , a ) = r ∈ R ∑ p ( r ∣ s , a ) r + γ s ′ ∑ p ( s ′ ∣ s , a ) v ∗ ( s ′ ) 后，未来价值项完全消失。因此每个状态只选择平均即时奖励最大的动作，不考虑其长期后果。
用一句公式说明 Theorem 3.4 的证明如何从 BOE 比较任意策略 π \pi π
[!success]- 点击查看答案
关键不等式是
v ∗ − v π ≥ γ P π ( v ∗ − v π ) ≥ ⋯ ≥ γ n P π n ( v ∗ − v π ) → 0 , v^*-v_\pi
\geq\gamma P_\pi(v^*-v_\pi)
\geq\cdots\geq\gamma^nP_\pi^n(v^*-v_\pi)
\rightarrow0, v ∗ − v π ≥ γ P π ( v ∗ − v π ) ≥ ⋯ ≥ γ n P π n ( v ∗ − v π ) → 0 , 因此 v ∗ ≥ v π v^*\geq v_\pi v ∗ ≥ v π
