强化学习的数学原理（二）：贝尔曼公式
强化学习核心：贝尔曼方程详解
在强化学习（Reinforcement Learning）中，我们的目标是让智能体（Agent）学会如何在一个环境中采取行动，以最大化累积奖励。为了评估一个策略（Policy）的好坏，我们需要一个标准来衡量在某个状态或采取某个动作后，未来可能获得的奖励总和。价值函数（Value Function）应运而生，而贝尔曼方程（Bellman Equation）则是连接价值函数的核心桥梁。
一、基本概念：智能体与环境的交互
强化学习问题可以被描述为一个智能体与环境交互的单步或多步过程。
1. 单步过程 (Single-step Process)
在任意一个时间步（time instance）$t$，交互过程包含以下元素：
- 状态 (State, $S_t$): 智能体观察到的环境情况。
- 动作 (Action, $A_t$): 智能体根据当前状态 $S_t$ 执行的操作。
- 奖励 (Reward, $R_{t+1}$): 智能体执行动作 $A_t$ 后，环境给予的即时反馈。
- 下一状态 (Next State, $S_{t+1}$): 环境在智能体执行动作后进入的新状态。
这个过程可以用下图表示： $$S_t \xrightarrow{A_t} R_{t+1}, S_{t+1}$$
这个单步转移是由两个核心的概率分布决定的：
- 策略 (Policy) $\pi(a|s)$: 描述智能体的行为，即在状态 $s$ 下选择动作 $a$ 的概率。
- $S_t \to A_t$ 由策略决定: $\pi(A_t=a | S_t=s)$
- 环境动态 (Dynamics) $p(s’, r|s, a)$: 描述环境的特性，即在状态 $s$ 下执行动作 $a$ 后，转移到下一状态 $s’$ 并获得奖励 $r$ 的概率。
- $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’ | S_t=s, A_t=a)$
2. 多步轨迹与回报 (Multi-step Trajectory & Return)
将单步过程连接起来，就构成了一条轨迹 (Trajectory)： $$S_t \xrightarrow{A_t} R_{t+1}, S_{t+1} \xrightarrow{A_{t+1}} R_{t+2}, S_{t+2} \xrightarrow{A_{t+2}} \dots$$
我们真正关心的是未来奖励的总和，而不仅仅是即时奖励。这个未来的累积奖励被称为回报 (Return)。为了避免无限时间序列导致回报无限大，我们引入一个折扣因子 (discount factor) $\gamma \in [0, 1)$。
折扣回报 (Discounted Return, $G_t$) 的定义如下： $$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$
$\gamma$ 的作用是权衡短期奖励和长期奖励的重要性。$\gamma$ 越接近 0，智能体越“近视”，只关心眼前的奖励；$\gamma$ 越接近 1，智能体越有“远见”，会更多地考虑长远利益。
需要注意的是，由于动作的选择（策略）和环境的状态转移都可能是随机的，因此 $R_{t+1}, S_{t+1}, G_t$ 等都是随机变量 (random variables)。
二、价值函数：衡量“好坏”的标尺
为了评估一个策略 $\pi$ 的优劣，我们需要知道从某个状态出发，遵循这个策略能够获得的期望回报。这就是价值函数的意义。
State value: the average return the agent can get starting from a state;
Action value: the average return the agent can get starting from a state and taking an action.
1. 状态价值函数 (State-Value Function, $V_{\pi}(s)$)
它表示从状态 $s$ 开始，遵循策略 $\pi$ 所能获得的期望回报。
定义: $$V_{\pi}(s) = E_{\pi}[G_t | S_t=s]$$ 其中 $E_{\pi}[\cdot]$ 表示在给定策略 $\pi$ 下的期望。
$V_{\pi}(s)$ 的值取决于状态 $s$ 和策略 $\pi$。对于同一个状态，不同的策略会产生不同的价值。通常来说，如果一个策略能让状态的价值更高，那么这个策略就更好。
2. 动作价值函数 (Action-Value Function, $q_{\pi}(s, a)$)
它表示在状态 $s$ 下，执行一个特定的动作 $a$，然后继续遵循策略 $\pi$ 所能获得的期望回报。这个函数也常被称为 Q-value。
定义: $$q_{\pi}(s, a) = E_{\pi}[G_t | S_t=s, A_t=a]$$
我们为什么要关心动作价值？因为它直接告诉我们在某个状态下，采取不同动作的好坏。如果知道了所有动作的价值，就可以通过选择价值最高的那个动作来做出最优决策。
3. 状态价值与动作价值的关系
状态价值是该状态下所有可能动作的价值，按照策略 $\pi$ 的概率分布进行的加权平均。 $$V_{\pi}(s) = \sum_{a \in A} \pi(a|s) q_{\pi}(s, a)$$
三、贝尔曼方程：价值函数的递归关系
贝尔曼方程的核心思想是：当前状态的价值与下一步状态的价值之间存在递归关系。
1. 贝尔曼方程的推导
我们从状态价值函数的定义开始推导： $$V_{\pi}(s) = E_{\pi}[G_t | S_t=s]$$ 将回报 $G_t$ 展开为即时奖励 $R_{t+1}$ 和后续的折扣回报 $\gamma G_{t+1}$： $$G_t = R_{t+1} + \gamma G_{t+1}$$ 代入价值函数定义中： $$V_{\pi}(s) = E_{\pi}[R_{t+1} + \gamma G_{t+1} | S_t=s]$$ 利用期望的线性性质，可以将其拆分为两部分： $$V_{\pi}(s) = E_{\pi}[R_{t+1} | S_t=s] + \gamma E_{\pi}[G_{t+1} | S_t=s]$$
现在，我们分别计算这两项：
即时奖励的期望: 对所有可能的动作 $a$ 和所有可能的下一状态 $s’$ 与奖励 $r$ 进行求和。 $$E[R_{t+1} | S_t=s] = \sum_{a}\pi(a|s) E[R_{t+1}|S_t=s, A_t=a] = \sum_a \pi(a|s) \sum_r p(r|s,a) r$$
未来回报的期望:
$$\begin{aligned} E\left[G_{t+1} \mid S_{t}=s\right] & =\sum_{s^{\prime}} E\left[G_{t+1} \mid S_{t}=s, S_{t+1}=s^{\prime}\right] P\left(s^{\prime} \mid s\right) \\ & =\sum_{s^{\prime}} E\left[G_{t+1} \mid S_{t+1}=s^{\prime}\right] P\left(s^{\prime} \mid s\right) \\ & =\sum_{s^{\prime}} V_{\pi}\left(s^{\prime}\right) P\left(s^{\prime} \mid s\right) \\ & =\sum_{s^{\prime}} V_{\pi}\left(s^{\prime}\right) \sum_{a} \pi(a \mid s) p\left(s^{\prime} \mid s, a\right) \end{aligned}$$
将这两部分合并，我们就得到了贝尔曼期望方程 (Bellman Expectation Equation)： $$V_{\pi}(s) = \sum_a \pi(a|s) \left[ \sum_r p(r|s,a)r + \gamma \sum_{s’} V_{\pi}(s’) p(s’|s,a) \right]$$
这个方程揭示了当前状态 $s$ 的价值 $V_{\pi}(s)$ 与所有可能的下一状态 $s’$ 的价值 $V_{\pi}(s’)$ 之间的关系。
同样，我们也可以推导出动作价值函数 $q_{\pi}(s, a)$ 的贝尔曼方程： $$q_{\pi}(s, a) = \sum_r p(r|s,a)r + \gamma \sum_{s’} V_{\pi}(s’) p(s’|s,a)$$
四、求解贝尔曼方程
对于一个给定的策略 $\pi$，计算其价值函数的过程称为策略评估 (Policy Evaluation)。如果环境模型（即 $p(s’, r|s, a)$）已知，我们可以通过求解贝尔曼方程来完成评估。
为了方便求解，我们可以将贝尔曼方程写成矩阵向量的形式。假设状态空间是有限的，包含 $n$ 个状态 ${s_1, \dots, s_n}$。
$$\vec{V}_{\pi} = \vec{r}_{\pi} + \gamma P_\pi \vec{V}_{\pi}$$
其中：
- $\vec{V}_{\pi} \in \mathbb{R}^n$ 是一个列向量，包含了所有状态的价值，$[V_{\pi}(s_1), \dots, V_{\pi}(s_n)]^T$。
- $\vec{r}_{\pi} \in \mathbb{R}^n$ 是一个列向量，代表了在策略 $\pi$ 下每个状态的期望即时奖励。 $$r_{\pi}(s) = E[R_{t+1}|S_t=s] = \sum_{a} \pi(a|s) \sum_r p(r|s,a)r$$
- $P_{\pi} \in \mathbb{R}^{n \times n}$ 是状态转移概率矩阵。其中每个元素 $P_{\pi}(s’|s)$ 表示从状态 $s$ 出发，遵循策略 $\pi$，下一步转移到状态 $s’$ 的概率。 $$P_{\pi}(s’|s) = \sum_a \pi(a|s) \sum_{s’} p(s’|s,a)$$
求解这个线性方程组有两种主要方法：
1. 解析解 (Closed-form Solution)
通过矩阵运算直接求解： $$(I - \gamma P_{\pi}) \vec{V}_{\pi} = \vec{r}_{\pi}$$ $$\vec{V}_{\pi} = (I - \gamma P_{\pi})^{-1} \vec{r}_{\pi}$$ 这种方法在理论上很完美，但计算矩阵的逆复杂度为 $O(n^3)$，当状态空间很大时，计算量巨大，几乎不可行。
2. 迭代解 (Iterative Solution)
这是一种更实用、更常见的方法。我们可以将贝尔曼方程变成一个迭代更新的公式： $$\vec{V}_{k+1} = \vec{r}_{\pi} + \gamma P_{\pi} \vec{V}_k$$ 从一个任意的初始价值向量 $\vec{V}_0$ 开始，反复应用这个更新规则。可以证明，当 $k \to \infty$ 时，$\vec{V}_k$ 会收敛到真实的价值函数 $\vec{V}_{\pi}$。这种方法是许多动态规划和强化学习算法的基础。
总结
贝尔曼方程是强化学习的基石。它优美地将一个复杂、长期的回报问题，分解成了一个关于当前状态价值和下一状态价值的递归式。无论是基于模型的动态规划，还是模型无关（Model-Free）的蒙特卡洛和时序差分学习，其背后都闪耀着贝尔曼方程的思想光辉。理解它，是通往强化学习殿堂的关键一步。