RL-02-01-MDP与Bellman方程

← 上级：RL-02.原理与数学基础 · 系列：RL-00.系列概述

本文在 RL-02 概要基础上，展开 MDP 数学结构与 Bellman 方程的推导逻辑，并给一个可手算的网格例子。读完后应能解释：为什么 Q-Learning 的 TD 目标长成 $r + \gamma \max Q(s’,a’)$ 那样。

段末注释：马尔可夫决策过程（Markov Decision Process，MDP）为 $(S,A,P,R,\gamma)$ 五元组；后文沿用 MDP。

一、MDP 五元组再述

$$
\mathcal{M} = (S, A, P, R, \gamma)
$$

符号	数学含义	工程对应
$S$	状态集合	`observation` 的抽象
$A$ 或 $A(s)$	动作集合	`action_space`
$P(s’\|s,a)$	转移核	环境 `step` 的随机性
$R(s,a,s’)$ 或 $r(s,a)$	期望即时奖励	`reward`
$\gamma \in [0,1]$	折扣因子	未来奖励权重

Episode：$S_0, A_0, R_1, S_1, A_1, R_2, \ldots$ 直至终止状态。

二、马尔可夫性

$$
P(S_{t+1}=s’ \mid S_t, A_t, S_{t-1}, \ldots) = P(S_{t+1}=s’ \mid S_t, A_t)
$$

含义：给定当前状态 $S_t$，未来与更早历史无关。历史信息若重要，应被编码进 $S_t$（如帧堆叠、RNN 隐状态），否则问题升级为 POMDP。

段末注释：部分可观测 MDP（Partially Observable MDP，POMDP）中 Agent 只能获得观测 $O_t$，而非真实状态 $S_t$；后文沿用 POMDP。

三、折扣回报

从 $t$ 时刻起的回报（Return）：

$$
G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}
$$

3.1 为何需要 $\gamma$

原因	说明
数学收敛	有界奖励下 $
经济直觉	远期的同样奖励不如当下
算法稳定	有限 horizon 近似无限任务

$\gamma \to 0$：极短视；$\gamma \to 1$：极长远（稀疏奖励任务常取 0.99+）。

3.2 递归形式

$$
G_t = R_{t+1} + \gamma G_{t+1}
$$

这是 Bellman 方程的回报版本，价值函数即对 $G_t$ 取期望。

四、Bellman 期望方程（给定策略 $\pi$）

Bellman 备份示意

状态价值 $V^\pi(s) = \mathbb{E}_\pi[G_t \mid S_t=s]$。

对 $V^\pi$ 在 $t$ 时刻展开：

$$
\begin{aligned}
V^\pi(s) &= \mathbb{E}\pi[R{t+1} + \gamma G_{t+1} \mid S_t=s] \
&= \sum_a \pi(a|s) \sum_{s’} P(s’|s,a) \left[ R(s,a,s’) + \gamma V^\pi(s’) \right]
\end{aligned}
$$

解读：$V^\pi(s)$ 等于「按 $\pi$ 选 $a$ → 按 $P$ 到 $s’$ → 得即时奖励 + 折扣后继价值」的期望。称为 Bellman 备份（Bellman Backup）。

动作价值形式：

$$
Q^\pi(s,a) = \sum_{s’} P(s’|s,a) \left[ R(s,a,s’) + \gamma \sum_{a’} \pi(a’|s’) Q^\pi(s’,a’) \right]
$$

五、Bellman 最优方程

最优价值 $V^*(s) = \max_\pi V^\pi(s)$ 满足：

$$
V^(s) = \max_a \sum_{s’} P(s’|s,a) \left[ R(s,a,s’) + \gamma V^(s’) \right]
$$

$$
Q^(s,a) = \sum_{s’} P(s’|s,a) \left[ R(s,a,s’) + \gamma \max_{a’} Q^(s’,a’) \right]
$$

关键：$\max$ 出现在动作选择上——永远选使期望后继价值最大的动作。

方程	策略
Bellman 期望	固定 $\pi$，求对应 $V^\pi$
Bellman 最优	无固定 $\pi$，嵌入 $\max_a$

六、从 Bellman 最优到 Q-Learning

环境模型 $P,R$ 未知时，用样本 $(s,a,r,s’)$ 近似：

$$
Q(s,a) \leftarrow Q(s,a) + \alpha \left[ \underbrace{r + \gamma \max_{a’} Q(s’,a’)}_{\text{对 } Q^* \text{ 的采样近似}} - Q(s,a) \right]
$$

括号内即为 TD 目标；减 $Q(s,a)$ 得 TD 误差 $\delta$。详见 RL-03-02-算法-Q-Learning。

七、手算例：2×2 网格（确定性）

[S0] --a1--> [S1]
 |              |
a2            a2
 ↓              ↓
[S2] --a1--> [S3=终点, r=+10]

设 $\gamma=0.9$，非终止步 $r=0$，终止 $S_3$ 得 $r=10$ 后结束。确定性策略：每格都选「向右/向下」朝终点。

在 $S_0$：一步到 $S_1$ 或 $S_2$，递推可解 $V^\pi(S_0)$。动态规划在已知 $P,R$ 时反复 Bellman 备份直至收敛。

八、动态规划（已知模型时）

算法	步骤
策略评估	固定 $\pi$，迭代 Bellman 期望至 $V^\pi$ 收敛
策略改进	$\pi’(s) = \arg\max_a \sum_{s’} P(s’
策略迭代	评估 + 改进交替
价值迭代	直接用 Bellman 最优方程更新 $V$，最后贪心导出 $\pi$

Model-Free RL 可看作在无 $P$ 时对上述备份的采样近似（MC / TD）。

九、小结

MDP = 马尔可夫转移 + 奖励 + 折扣目标。
Bellman 方程 = 当前价值 = 即时奖励 + 折扣后继价值（期望或 max）。
Q-Learning / DQN 采样近似 Bellman 最优方程。
下一篇：价值函数与策略