强化学习的数学基础 - Chapter 2

赵老师开源的 Github 仓库、赵老师的 B站 课程视频

背景来自 XHS 汉堡夹星Stella

Overview

本章主要内容：

• 一个核心概念：状态价值（state value）
• 一个基础工具：贝尔曼方程（Bellman equation）

Outline：

• 动机与例子：为何要研究 state value 和 Bellman equation？
• 正式定义 state value
• Bellman equation 的推导以及 matrix-vector form，如何利用 Bellman equation 求解 state value
• 从 state value 到 action value

---

Lecture 3: Motivating Examples

3.1 Why return is important?

• 什么是 return？沿一条 trejectory 获得的（折扣）reward 总和。
• return 为何重要？见以下示例。

Example 1：蓝色为 target，橙色是 forbidden area，白色是 accessible area.

• 问题：从起点 $s_1$ 出发，哪种策略是“最优”的？哪种是“最劣”的？
• 直觉：第一种最优；第二种最劣，进入了禁区；第三种一般，因为有一定概率进入橙色区域。

如何用数学描述这种直觉？return 可用于评估策略。

基于策略 1（左图）

从 $s_1$ 出发，折扣回报（discounted reward）为

$$\begin{align*} \text{return}_1 &= 0 + \gamma 1 + \gamma^2 1 + \dots, \\ &= \gamma(1 + \gamma + \gamma^2 + \dots), \\ &= \frac{\gamma}{1 - \gamma}. \end{align*}$$

基于策略 2（中图）

从 $s_1$ 出发，折扣回报为

$$\begin{align*} \text{return}_2 &= -1 + \gamma 1 + \gamma^2 1 + \dots, \\ &= -1 + \gamma(1 + \gamma + \gamma^2 + \dots), \\ &= -1 + \frac{\gamma}{1 - \gamma}. \end{align*}$$

基于策略 3（右图）

注意，策略 3 是随机的：从 $s_1$ 出发，折扣回报是

$$\begin{align*} \text{return}_3 &= 0.5\left(-1 + \frac{\gamma}{1 - \gamma}\right) + 0.5\left(\frac{\gamma}{1 - \gamma}\right), \\ &= -0.5 + \frac{\gamma}{1 - \gamma}. \end{align*}$$

综上，从 $s_1$ 出发，

$$\text{return}_1 > \text{return}_3 > \text{return}_2$$

上述不等式表明，第一种策略最优，第二种策略最劣，这与我们的直觉完全一致。

3.2 How to calculate return?

Example 2

Method 1

设 $v_i$ 表示从 $s_i$（$i=1,2,3,4$）出发获得的回报，则

$$\begin{align*} v_1 &= r_1 + \gamma r_2 + \gamma^2 r_3 + \dots \\ v_2 &= r_2 + \gamma r_3 + \gamma^2 r_4 + \dots \\ v_3 &= r_3 + \gamma r_4 + \gamma^2 r_1 + \dots \\ v_4 &= r_4 + \gamma r_1 + \gamma^2 r_2 + \dots \\ \end{align*}$$

Method 2

$$\begin{align*} v_1 &= r_1 + \gamma(r_2 + \gamma r_3 + \dots) = r_1 + \gamma v_2 \\ v_2 &= r_2 + \gamma(r_3 + \gamma r_4 + \dots) = r_2 + \gamma v_3 \\ v_3 &= r_3 + \gamma(r_4 + \gamma r_1 + \dots) = r_3 + \gamma v_4 \\ v_4 &= r_4 + \gamma(r_1 + \gamma r_2 + \dots) = r_4 + \gamma v_1 \\ \end{align*}$$

可以发现，从不同状态出发得到的 return 实际上依赖于从其他状态出发得到的 return（return 相互依赖）。这个 idea 在强化学习中称为 自举（Bootstrapping）！

如何解方程？

写成如下矩阵-向量形式：

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

可改写为

$$\mathbf{v} = \mathbf{r} + \gamma \mathbf{P} \mathbf{v}$$

这就是针对这个简单的确定性问题的 贝尔曼方程（Bellman equation）！

• 尽管简单，但它展示了核心思想：一个状态的价值依赖于其他状态的价值。
• 矩阵-向量形式更清晰地展示了如何求解状态价值。

Exercise 1

考虑图中所示的策略，请写出回报之间的关系（即写出贝尔曼方程）

沿用 Example 1 中的左图

可以得到，

$$\begin{align*} v_1 &= 0 + \gamma v_3 \\ v_2 &= 1 + \gamma v_4 \\ v_3 &= 1 + \gamma v_4 \\ v_4 &= 1 + \gamma v_4 \\ \end{align*}$$

我们可以先计算 $v_4$，然后计算 $v_3$、$v_2$、$v_1$。

---

Lecture 4: State Value

4.1 Some Notation

考虑如下单步过程：

$$S_t \stackrel{A_t}{\to} R_{t+1}, S_{t+1}$$

• $t, t+1$：离散时间点
• $S_t$：时间 $t$ 的状态
• $A_t$：在状态 $S_t$ 采取的动作
• $R_{t+1}$：采取 $A_t$ 后获得的奖励
• $S_{t+1}$：采取 $A_t$ 后转移到的状态

注意 $S_t, A_t, R_{t+1}$ 都是随机变量，既然是随机变量，我就可以进行求期望等操作。

该步骤由以下概率分布决定：

• $S_t \to A_t$，由 $\pi(A_t = a|S_t = s)$ 决定
• $S_t, A_t \to R_{t+1}$，由 $p(R_{t+1} = r|S_t = s, A_t = a)$ 决定
• $S_t, A_t \to S_{t+1}$，由 $p(S_{t+1} = s^\prime|S_t = s, A_t = a)$ 决定

此时，我们假设已知模型（即概率分布）！

4.2 Multi-Step Trajectory & Discounted Return

考虑如下多步轨迹：

$$S_t \stackrel{A_t}{\to} R_{t+1}, S_{t+1} \stackrel{A_{t+1}}{\to} R_{t+2}, S_{t+2} \stackrel{A_{t+2}}{\to} R_{t+3}, \dots$$

discounted return 为

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

• $\gamma \in [0, 1)$ 是折扣率。
• 由于 $R_{t+1}, R_{t+2}, \dots$ 是随机变量，$G_t$ 也是随机变量。

4.3 State Value

$G_t$ 的期望被定义为 (state-value function)，或简称为 (state value)：

$$v_\pi(s) = \mathbb{E}[G_t|S_t = s]$$

Remarks：

• state value 是 $s$ 的函数：它是状态从 $s$ 开始的条件期望。
• state value 是策略 $\pi$ 的函数：对于不同的策略，状态价值可能不同。
• 它表示一个状态的“价值”。如果状态价值更大，那么该策略更好，因为可以获得更大的累积奖励。

Q：return 和 state value 之间的关系是什么？

A：return 是对 单个 trajectory 而言的；而 state value 是对 多个 trajecotry 得到的 returns 求期望。
特别地，如果策略 $\pi(a|s)$、奖励 $p(r|s,a)$、状态转移概率 $p(s^\prime |s,a)$ 都是确定性的，那么只有一条 trajectory，此时状态价值与回报相同。

Eample 1 续

设从左到右的策略分别为 1、2、3

计算策略 $\pi_1$、$\pi_2$、$\pi_3$ 在同一状态下的 state value：

$$\begin{align*} v_{\pi_1}(s_1) &= 0 + \gamma \times 1 + \gamma^2 \times 1 + \dots = \gamma(1 + \gamma + \gamma^2 + \dots) = \frac{\gamma}{1 - \gamma} \\ v_{\pi_2}(s_1) &= -1 + \gamma \times 1 + \gamma^2 \times 1 + \dots = -1 + \gamma(1 + \gamma + \gamma^2 + \dots) = -1 + \frac{\gamma}{1 - \gamma} \\ v_{\pi_3}(s_1) &= 0.5\left(-1 + \frac{\gamma}{1 - \gamma}\right) + 0.5\left(\frac{\gamma}{1 - \gamma}\right) = -0.5 + \frac{\gamma}{1 - \gamma} \\ \end{align*}$$

---

Lecture 5: Bellman Equation - Derivation

我们已经定义了 state value，现在需要求解它。计算的工具就是 Bellman Equation。

一句话解释 Bellman Equation：它描述了不同状态的 state value 之间的关系。

5.1 Deriving the Bellman equation

考虑一条随机轨迹：

$$S_t \stackrel{A_t}{\to} R_{t+1}, S_{t+1} \stackrel{A_{t+1}}{\to} R_{t+2}, S_{t+2} \stackrel{A_{t+2}}{\to} R_{t+3}, \dots$$

折扣回报 $G_t$ 可写为：

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

由状态价值的定义，将其拆分为 即时奖励（immediate reward) 和 未来奖励（future reward）：

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

第一项 $\mathbb{E}[R_{t+1}|S_t=s]$（即时奖励的期望）：

$$\begin{align*} \mathbb{E}[R_{t+1}|S_t=s] &= \sum_a \pi(a|s) \mathbb{E}[R_{t+1}|S_t=s,A_t=a] \\ &= \sum_a \pi(a|s) \sum_r p(r|s,a) r \\ \end{align*}$$

第二项 $\mathbb{E}[G_{t+1}|S_t=s]$（未来奖励的期望）：

$$\begin{align*} \mathbb{E}[G_{t+1}|S_t=s] &= \sum_{s^\prime} \mathbb{E}[G_{t+1}|S_t=s, S_{t+1}=s^\prime] \ p(s^\prime|s) \\ &= \sum_{s^\prime} \mathbb{E}[G_{t+1} |S_{t+1}=s^\prime]\ p(s^\prime|s) \\ &= \sum_{s^\prime} v_\pi(s^\prime) \ p(s^\prime|s) \\ &= \sum_{s^\prime} v_\pi(s^\prime) \sum_a p(s^\prime|s,a)\pi(a|s) \end{align*}$$

其中，$\mathbb{E}[G_{t+1}|S_t=s,S_{t+1}=s^\prime] = \mathbb{E}[G_{t+1}|S_{t+1}=s^\prime]$ 利用了马尔可夫性质（无记忆性）。

贝尔曼方程（元素形式）

$$\begin{align*} v_\pi(s) &= \mathbb{E}[R_{t+1}|S_t=s] + \gamma \mathbb{E}[G_{t+1}|S_t=s]\\ &= \sum_a \pi(a|s) \sum_r p(r|s,a) r + \gamma \sum_{s^\prime} v_\pi(s^\prime) \sum_a p(s^\prime|s,a)\pi(a|s) \\ &= \sum_a \pi(a|s) \left[ \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_\pi(s^\prime) \right], \quad \forall s \in \mathcal{S} \end{align*}$$

要点：

• 上式称为贝尔曼方程（Bellman equation），它刻画了不同状态的 state value（$v_\pi(s)$ 与 $v_\pi(s^\prime)$）之间的关系。
• 由两项组成：即时奖励项和未来奖励项。
• 这不是一个式子，而是一组方程：每个状态都有一个这样的方程！（如果有 $n$ 个状态，我们就能得到 $n$ 个方程）
• $v_\pi(s)$ 和 $v_\pi(s^\prime)$ 是待计算的状态价值。计算方法就是 Bootstrapping！
• 上式中的 $\pi(a|s)$ 是给定策略，所以 Bellman Equation 是依赖于 policy 的。求解该方程，即求解 policy 的 state value，因此也称为 策略评估（policy evaluation）。
• $p(r|s,a)$ 和 $p(s^\prime|s,a)$ 代表动态模型（dynamic model）：我们可能知道这个 model，也可能不知道这个 model，会有不同的方法用于计算。

5.2 Example 1

Bellman equation 示例 1

状态价值函数的通用贝尔曼方程为，

$$v_\pi(s) = \sum_a \pi(a|s) \left[ \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a)v_\pi(s^\prime) \right]$$

先推导 $s_1$ 的贝尔曼方程，本案例为确定性策略：

1. 策略分布：$\pi(a=a_3|s_1)=1$，$\pi(a \neq a_3|s_1)=0$
2. 状态转移：$p(s^\prime=s_3|s_1,a_3)=1$，$p(s^\prime \neq s_3|s_1,a_3)=0$
3. 奖励分布：$p(r=0|s_1,a_3)=1$，$p(r \neq 0|s_1,a_3)=0$

将条件代入通用公式，化简得：

$$v_\pi(s_1) = 0 + \gamma v_\pi(s_3)$$

同理推导剩余状态，完整方程组：

$$\begin{align*} v_\pi(s_1) &= 0 + \gamma v_\pi(s_3) \\ 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{align*}$$

可以解出，

$$\begin{align*} v_\pi(s_4) &= \frac{1}{1-\gamma} \\ v_\pi(s_3) &= \frac{1}{1-\gamma} \\ v_\pi(s_2) &= \frac{1}{1-\gamma} \\ v_\pi(s_1) &= \frac{\gamma}{1-\gamma} \end{align*}$$

如果取 $\gamma = 0.9$，则：

$$\begin{align*} v_\pi(s_4) &= \frac{1}{1-0.9} = 10 \\ v_\pi(s_3) &= \frac{1}{1-0.9} = 10 \\ v_\pi(s_2) &= \frac{1}{1-0.9} = 10 \\ v_\pi(s_1) &= \frac{0.9}{1-0.9} = 9 \\ \end{align*}$$

说明：因为 $s_1$ 距离 target 较远，因此 $v_\pi(s_1)$ 值较小。

5.3 Example 2

Bellman equation 示例 2

列出每个状态的贝尔曼方程，

$$\begin{aligned} v_\pi(s_1) &= 0.5\big[0 + \gamma v_\pi(s_3)\big] + 0.5\big[-1 + \gamma v_\pi(s_2)\big], \\ 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_\pi(s_4) = \frac{1}{1-\gamma},\quad v_\pi(s_3) = \frac{1}{1-\gamma},\quad v_\pi(s_2) = \frac{1}{1-\gamma}$$

将 $v_\pi(s_2),v_\pi(s_3)$ 代入 $s_1$ 的方程化简：

$$\begin{aligned} v_\pi(s_1) &= 0.5\big[0 + \gamma v_\pi(s_3)\big] + 0.5\big[-1 + \gamma v_\pi(s_2)\big] \\ &= -0.5 + \frac{\gamma}{1-\gamma}. \end{aligned}$$

将 $\gamma=0.9$ 带入，得到各状态价值数值：

$$v_\pi(s_4)=10,\quad v_\pi(s_3)=10,\quad v_\pi(s_2)=10,\quad v_\pi(s_1) = -0.5 + 9 = 8.5$$

注意到，在上一个策略中我们得到的 $v_\pi(s_1) = 9 > 8.5$，说明策略评估结果下降。（当前策略不如旧策略好）

---

Lecture 6: Bellman Equation - Matrix-Vector Form and Solution

对上面得到的元素形式的 Bellman equation，我们无法直接求解。但如果我们列出所有状态的方程，就可以得到一个方程组！

6.1 Bellman 方程的矩阵-向量形式

我们可以重写贝尔曼方程为：

$$v_\pi(s) = r_\pi(s) + \gamma \sum_{s^\prime} p_\pi(s^\prime|s) v_\pi(s^\prime)$$

• $r_\pi(s)$ 表示当前策略 $\pi$ 在状态 $s$ 下的即时奖励的期望，

  $$r_\pi(s) \triangleq \sum_a \pi(a|s) \sum_r p(r|s,a) r$$

• $p_\pi(s^\prime|s)$ 表示当前策略 $\pi$ 在状态 $s$ 下转移到状态 $s^\prime$ 的概率，

  $$p_\pi(s^\prime|s) \triangleq \sum_a \pi(a|s) p(s^\prime|s,a)$$

将 $n$ 个状态的方程合并为 矩阵-向量形式（Matrix-Vector Form）：

$$v_\pi = r_\pi + \gamma P_\pi v_\pi$$

其中：

• $v_\pi = [v_\pi(s_1), \ldots, v_\pi(s_n)]^T \in \mathbb{R}^n$
• $r_\pi = [r_\pi(s_1), \ldots, r_\pi(s_n)]^T \in \mathbb{R}^n$
• $P_\pi \in \mathbb{R}^{n \times n}$，$[P_\pi]_{ij} = p_\pi(s_j|s_i)$，是状态转移矩阵

为什么考虑矩阵-向量形式？

1. 一个未知量依赖于另一个未知量。
2. 元素形式对每个状态 $s \in \mathcal{S}$ 都成立，意味着有 $|\mathcal{S}|$ 个这样的方程！
3. 将所有方程放在一起得到一个线性方程组，可以简洁地写成矩阵-向量形式。
4. 矩阵-向量形式非常优雅且重要。

例子回顾

回顾刚刚的两个例子

当环境存在4个状态时，矩阵形式贝尔曼方程 $v_\pi = r_\pi + \gamma P_\pi v_\pi$ 可展开写作：

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

针对本网格确定性策略案例（中图），代入数值后矩阵方程为：

$$\begin{bmatrix} v_\pi(s_1) \\ v_\pi(s_2) \\ v_\pi(s_3) \\ v_\pi(s_4) \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 1 \end{bmatrix} + \gamma \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} v_\pi(s_1) \\ v_\pi(s_2) \\ v_\pi(s_3) \\ v_\pi(s_4) \end{bmatrix}$$

针对随机策略案例（右图），代入数值后矩阵方程为：

$$\begin{bmatrix} v_\pi(s_1) \\ v_\pi(s_2) \\ v_\pi(s_3) \\ v_\pi(s_4) \end{bmatrix} = \begin{bmatrix} 0.5(0) + 0.5(-1) \\ 1 \\ 1 \\ 1 \end{bmatrix} + \gamma \begin{bmatrix} 0 & 0.5 & 0.5 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} v_\pi(s_1) \\ v_\pi(s_2) \\ v_\pi(s_3) \\ v_\pi(s_4) \end{bmatrix}$$

6.2 求解状态价值

为什么求解状态价值？

• 给定一个策略，找出相应的状态价值称为 （policy evaluation）！这是强化学习中的基本问题，是寻找更好策略的基础。

方法 1：闭式解

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

在实践中，状态空间往往维数较大，仍需使用数值工具计算矩阵逆。

方法 2：迭代解

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

该算法生成序列 $\{v_0, v_1, v_2, \ldots\}$。可以证明：当 $k \to \infty$ 时，

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

收敛性证明概要：定义误差 $\delta_k = v_k - v_\pi$，可得

$$\delta_{k+1} = \gamma P_\pi \delta_k \implies \delta_{k+1} = \gamma^{k+1} P_\pi^{k+1} \delta_0$$

由于 $\gamma < 1$ 且 $P_\pi^k$ 的每个元素不超过 $1$，故 $\delta_k \to 0$。

网格世界示例

奖励设置：$r_{\text{boundary}} = r_{\text{forbidden}} = -1$，$r_{\text{target}} = +1$，$\gamma = 0.9$。

比较好的两个策略。

可以看到，在左图、右图的两个策略里，我们在 (1,4)(2,4) 采用的 action 是不一样的，但最后可以得到相同的状态价值。这说明：不同策略可以得到相同的状态价值。

比较差的两个策略。

"好"策略的状态价值较大，"差"策略的状态价值较小。策略评估结果展示了不同策略的定量比较。

---

Lecture 7: Action Value

7.1 动作价值

状态价值与动作价值定义

• 状态价值：智能体从某个状态出发，能获得的平均回报。
• 动作价值：智能体从某个状态出发、执行某一特定动作后，能获得的平均回报。

为什么要引入动作价值？

• 我们需要判断哪个动作的效果更好。这一点在后续课程中会讲解得更清晰，后续内容会频繁使用动作价值。

7.2 动作价值的数学定义

$$q_\pi(s,a) = \mathbb{E}\left[G_t \mid S_t = s,\ A_t = a\right]$$

• $q_\pi(s,a)$ 是 状态-动作二元组 $(s,a)$ 的函数
• $q_\pi(s,a)$ 的取值依赖策略 $\pi$

由条件期望的性质可得：

$$\underbrace{\mathbb{E}\left[G_t \mid S_t = s\right]}_{v_\pi(s)} = \sum_a \underbrace{\mathbb{E}\left[G_t \mid S_t = s,A_t = a\right]}_{q_\pi(s,a)} \pi(a|s)$$

因此得到，

$$\color{red}{v_\pi(s)} = \sum_a \pi(a|s)\, \color{red}{q_\pi(s,a)} \tag{2}$$

回顾 state value 的贝尔曼公式：

$$v_\pi(s) = \sum_a \pi(a|s) \color{red}{\left[ \sum_r p(r|s,a)\,r + \gamma \sum_{s^\prime} p(s^\prime|s,a)\,v_\pi(s^\prime) \right]} \tag{3}$$

于是上式方括号内整体即为动作价值 $q_\pi(s,a)$。我们就此得到 动作价值函数（action-value function） 的贝尔曼方程，

$$q_\pi(s,a) = \sum_r p(r|s,a)\,r + \gamma \sum_{s^\prime} p(s^\prime|s,a)\,v_\pi(s^\prime) \tag{4}$$

两个公式的互补关系

式(2) 和 式(4) 是同一枚硬币的两面，二者互为转换关系：

1. 式(2)：由 action value 加权求和，推导出 state value；
2. 式(4)：由即时奖励 + 后续 state value，推导出 action value。

7.3 例子

例子

action-value = immediate reward + discounted future state-value

写出 $s_1$ 的 action value：

$$q_\pi(s_1,a_2) = -1 + \gamma v_\pi(s_2)$$

注意，虽然图中的 policy 只能往 $s_2$ 转移，但实际上 $a_1,a_3,a_4,a_5$ 的 action-value 也可以计算！

$$\begin{align*} q_\pi(s_1,a_1) &= -1 + \gamma v_\pi(s_1) \\ q_\pi(s_1,a_3) &= 0 + \gamma v_\pi(s_3) \\ q_\pi(s_1,a_4) &= -1 + \gamma v_\pi(s_1) \\ q_\pi(s_1,a_5) &= 0 + \gamma v_\pi(s_1) \\ \end{align*}$$

要点

• 动作价值（Action value）很重要，因为我们关心应该采取哪个动作（选择 action value 最高的那个动作）
• 我们可以先计算所有状态价值，然后再计算动作价值。
• 我们也可以直接计算动作价值，无论是否使用模型。

Summary

核心概念与结果

• 状态价值（State value）：

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

• 动作价值（Action value）：

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

• 贝尔曼方程（逐元素形式 / elementwise form）：

  $$\begin{align*} v_\pi(s) &= \sum_{a} \pi(a \mid s) \underbrace{\left[ \sum_{r} p(r \mid s,a) r + \gamma \sum_{s^\prime} p(s^\prime \mid s,a) v_\pi(s^\prime) \right]}_{q_\pi(s,a)} \\ &= \sum_{a} \pi(a \mid s) q_\pi(s,a) \end{align*}$$

• 贝尔曼方程（矩阵-向量形式 / matrix-vector form）：

  $$v_\pi = r_\pi + \gamma P_\pi v_\pi$$

• 求解贝尔曼方程的方法：

  • 闭式解（closed-form solution）

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

  • 迭代解（iterative solution）

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