马尔可夫决策过程 · 机器学习 POD

从监督学习到决策

在监督学习里，模型做的事情很简单：给一个输入，输出一个预测。训练集里每个样本都有正确答案，模型学完就拿去用，训练和使用是分开的两个阶段。

强化学习（Reinforcement Learning, RL）面对的问题完全不同。一个智能体（agent）置身于环境中，需要反复做出决策，而且——

序贯决策：每一步的决策会改变环境状态，影响后续所有可能。不是一次性给答案，而是一连串动作。
延迟奖励：好的结果可能要很多步之后才显现。下棋时一步妙手的价值，可能 50 步后才以胜负的形式兑现。
探索 vs. 利用：已知某个动作不错，是继续用（exploit），还是尝试没试过的动作，看看有没有更好的（explore）？这个矛盾贯穿整个学习过程。

要让"决策"变成一个可以用数学求解的问题，我们需要一个形式化框架。这就是马尔可夫决策过程（Markov Decision Process, MDP）——强化学习的数学骨架。

MDP 形式化

基本概念

一个 MDP 由五元组 $(S, A, P, R, \gamma)$ 定义：

符号	名称	含义
$S$	状态空间	所有可能的状态集合
$A$	动作空间	所有可能的动作集合（也可写成 $A(s)$ 表示状态 $s$ 下可选的动作）
$P$	状态转移概率	$P(s' \mid s, a)$ —— 在状态 $s$ 执行动作 $a$ 后转移到 $s'$ 的概率
$R$	奖励函数	$R(s, a, s')$ —— 从 $s$ 执行 $a$ 到达 $s'$ 获得的即时奖励
$\gamma$	折扣因子	$\gamma \in [0, 1)$ —— 未来奖励的衰减系数

马尔可夫性质

MDP 的"马尔可夫"三个字意味着一个关键假设：下一步只取决于当前状态，与历史无关。

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

通俗地说，"当前状态"已经浓缩了过去所有的信息。你不需要回忆整段历史，只要看到当前局面就够了。下棋时棋盘局面就是状态——你不需要知道每步棋是怎么走到这里的。

折扣因子的意义

为什么需要 $\gamma$ ？如果不打折扣，一个永远不停的过程的总奖励可能是无穷大，数学上没法处理。加上 $\gamma < 1$ ，远期奖励被指数衰减：

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}

$G_t$ 叫回报（return），是从时刻 $t$ 开始的折扣累积奖励。 $\gamma$ 越接近 1，智能体越"有远见"； $\gamma$ 越小，越"目光短浅"。

一个简单的例子

考虑一个 $4 \times 4$ 的网格世界（GridWorld）：

智能体在网格中移动（上、下、左、右）
右上角是目标格，到达获得 $+1$ 奖励
目标旁边有一个陷阱格，到达获得 $-1$ 奖励
撞墙则停在原地，其他移动奖励为 $0$

这就是一个完整的 MDP：状态是格子坐标，动作是四个方向，转移是确定性的（往哪走就到哪，除非撞墙），奖励由到达的格子决定。

策略与价值函数

策略

策略（policy） $\pi$ 描述智能体的行为方式。它可以是确定性的，也可以是随机的：

确定性策略： $a = \pi(s)$ —— 在状态 $s$ 直接给出动作
随机策略： $\pi(a \mid s)$ —— 在状态 $s$ 以某个概率分布选择动作

随机策略更一般。确定性策略是特例——把所有概率集中到一个动作上。

状态价值函数

给定策略 $\pi$ ，状态价值函数 $V^\pi(s)$ 衡量"从状态 $s$ 出发，按策略 $\pi$ 行动，期望能拿到多少回报"：

V^\pi(s) = \mathbb{E}_\pi \left[ G_t \mid S_t = s \right] = \mathbb{E}_\pi \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \mid S_t = s \right]

$V^\pi(s)$ 回答的是：状态 $s$ 有多"好"？

动作价值函数

动作价值函数 $Q^\pi(s, a)$ 比 $V^\pi$ 多了一层：不仅指定了起始状态 $s$ ，还指定了第一步动作 $a$ ，之后再按策略 $\pi$ 行动：

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

$Q^\pi(s, a)$ 回答的是：在状态 $s$ 执行动作 $a$ ，然后跟着 $\pi$ 走，期望回报是多少？

$V$ 和 $Q$ 的关系

两个价值函数之间有简洁的关系：

V^\pi(s) = \sum_{a \in A} \pi(a \mid s) \, Q^\pi(s, a)

状态价值就是在策略 $\pi$ 下对所有动作价值的加权平均。如果策略是确定性的 $\pi(s) = a^*$ ，则 $V^\pi(s) = Q^\pi(s, a^*)$ 。

最优策略与最优价值函数

存在最优策略 $\pi^*$ ，它在每一个状态上都不比其他任何策略差：

V^*(s) = \max_\pi V^\pi(s), \quad \forall s \in S

Q^*(s, a) = \max_\pi Q^\pi(s, a), \quad \forall s, a

MDP 的一个基本定理保证：对于有限状态和动作的 MDP，最优策略一定存在，而且可以是确定性的。

贝尔曼方程

贝尔曼期望方程

价值函数有一个递归结构：当前状态的价值可以分解为"即时奖励 + 折扣后的下一状态价值"。这就是贝尔曼期望方程（Bellman Expectation Equation）。

对状态价值函数：

V^\pi(s) = \sum_{a} \pi(a \mid s) \sum_{s'} P(s' \mid s, a) \Big[ R(s, a, s') + \gamma V^\pi(s') \Big]

对动作价值函数：

Q^\pi(s, a) = \sum_{s'} P(s' \mid s, a) \Big[ R(s, a, s') + \gamma \sum_{a'} \pi(a' \mid s') Q^\pi(s', a') \Big]

直觉上很自然：在状态 $s$ 按策略 $\pi$ 选动作 $a$ ，环境按转移概率跳到 $s'$ ，拿到奖励 $R$ ，然后剩下的期望回报就是 $\gamma V^\pi(s')$ 。把所有可能的 $a$ 和 $s'$ 用概率加权平均，就得到 $V^\pi(s)$ 。

贝尔曼最优方程

把 $\pi$ 换成最优策略 $\pi^*$ ，期望变成了取最大：

V^*(s) = \max_{a} \sum_{s'} P(s' \mid s, a) \Big[ R(s, a, s') + \gamma V^*(s') \Big]

Q^*(s, a) = \sum_{s'} P(s' \mid s, a) \Big[ R(s, a, s') + \gamma \max_{a'} Q^*(s', a') \Big]

贝尔曼最优方程刻画了最优价值函数的自洽条件：如果我在每一步都选让后续价值最大的那个动作，得到的就是最优价值。

一旦求出 $V^*$ （或 $Q^*$ ），最优策略就是贪心地选 $\arg\max$ ：

\pi^*(s) = \arg\max_{a} \sum_{s'} P(s' \mid s, a) \Big[ R(s, a, s') + \gamma V^*(s') \Big]

动态规划求解

贝尔曼方程给了我们递归关系，但怎么实际算出来？当 MDP 的模型（ $P$ 和 $R$ ）完全已知时，可以用动态规划（Dynamic Programming, DP）精确求解。

策略评估

给定一个固定策略 $\pi$ ，我们想计算它的 $V^\pi$ 。方法是迭代地应用贝尔曼期望方程。

初始化 $V_0(s) = 0$ ，然后反复更新：

V_{k+1}(s) = \sum_{a} \pi(a \mid s) \sum_{s'} P(s' \mid s, a) \Big[ R(s, a, s') + \gamma V_k(s') \Big]

可以证明 $V_k \to V^\pi$ （ $k \to \infty$ ）。每一轮"扫描"（sweep）遍历所有状态，用旧的 $V_k$ 计算新的 $V_{k+1}$ 。

策略迭代

策略迭代（Policy Iteration）交替进行两步：

策略评估：固定当前策略 $\pi_k$ ，算出 $V^{\pi_k}$
策略改进：根据 $V^{\pi_k}$ 贪心地更新策略—— $\pi_{k+1}(s) = \arg\max_a \sum_{s'} P(s' \mid s, a) [R + \gamma V^{\pi_k}(s')]$

策略改进定理保证 $V^{\pi_{k+1}} \geq V^{\pi_k}}$ （逐状态不递减）。有限 MDP 的策略数有限，每步都严格改进，因此算法必在有限步收敛到 $\pi^*$ 。

价值迭代

价值迭代（Value Iteration）更直接——直接迭代贝尔曼最优方程：

V_{k+1}(s) = \max_{a} \sum_{s'} P(s' \mid s, a) \Big[ R(s, a, s') + \gamma V_k(s') \Big]

每一步把"评估"和"改进"融合在一起：先取 max（隐式的策略改进），然后用更新后的值继续。收敛后提取 $\pi^*$ 即可。

策略迭代 vs. 价值迭代

	策略迭代	价值迭代
每轮做什么	完整评估 $V^\pi$ + 一次策略改进	一次 Bellman 最优更新
收敛速度	通常迭代次数更少	每轮计算量更小
适合场景	动作空间小时高效	大状态空间、需要快速近似时

GridWorld 演示

下面的 $4 \times 4$ 网格世界展示了动态规划的求解过程。你可以切换"价值迭代"和"策略迭代"两种模式，点击"运行"观看价值函数逐步收敛，每个格子会显示当前 $V(s)$ 和贪心最优动作的方向。 $\gamma = 0.9$ 。

迭代 0

目标 (+1)陷阱 (-1)S起点X墙壁

4x4 GridWorld：点击「运行」观看价值迭代逐步收敛，每个格子显示 V(s) 和最优动作方向。

试试观察：

靠近目标的格子价值最先变高，然后"扩散"到远处——这就是动态规划的信息传播过程
陷阱格附近的格子价值为负，最优策略会绕开它
两种迭代方式最终收敛到相同的最优策略

这个想法在前沿里

MDP 不只是教科书上的抽象框架——它是今天最前沿的 AI 系统的底层语言：

RLHF（人类反馈强化学习） —— ChatGPT 背后的对齐技术。LLM 生成文本的过程被建模为 MDP：状态是已生成的 token 序列，动作是选择下一个 token，奖励来自人类偏好模型（reward model）。PPO 算法在这个 MDP 上优化策略，使模型的输出更符合人类期望。
AlphaGo —— 围棋被建模为一个巨大的 MDP：状态是棋盘局面（ $19 \times 19$ 的棋子配置），动作是落子位置，转移由对手的应对决定（对手的策略也在学习中），奖励在终局时给出（胜 $+1$ ，负 $-1$ ）。蒙特卡罗树搜索（MCTS）本质上是在这个 MDP 上做前向规划。
机器人控制 —— 连续状态空间的 MDP：关节角度和角速度是状态，电机力矩是动作，奖励衡量任务完成度。深度强化学习算法（SAC、TD3）在连续 MDP 上求解近似最优策略。

从 GridWorld 到 LLM 对齐，数学骨架始终是 $(S, A, P, R, \gamma)$ ——变的只是规模和求解方法。