马尔可夫决策过程（MDP）

一句话总结 · 要点速览

• 马尔可夫决策过程（MDP）由状态集合、动作集合、转移概率 p(s'|s,a)、奖励函数和折扣因子 γ 组成，是强化学习问题的标准数学模型。
• 马尔可夫性指：下一时刻的状态和奖励只依赖当前状态和动作，而与更早的历史无关。
• 回报 G_t 是从时刻 t 开始的折扣奖励之和 G_t = R_{t+1} + γR_{t+2} + γ²R_{t+3} + …。
• 状态价值 v_π(s) 是从 s 出发遵循策略 π 的期望回报；动作价值 q_π(s,a) 是在 s 先执行 a 再遵循 π 的期望回报。
• 马尔可夫过程（MP）加上奖励得到马尔可夫奖励过程（MRP），再加上动作得到 MDP；固定策略后的 MDP 就是一个 MRP。
• 占用度量 ρ^π(s,a) 描述策略 π 访问各状态—动作对的折扣频率，策略的期望回报等于 ⟨ρ^π, r⟩/(1−γ)，这是 GAIL、约束 RL 和线性规划解法的基础。

术语不熟悉？查看 强化学习术语表。

马尔可夫决策过程（Markov Decision Process，MDP）是强化学习的标准数学框架，几乎所有强化学习算法都建立在它之上。它用状态、动作、转移概率、奖励和折扣因子五个要素刻画“序贯决策”问题，并在此基础上定义策略和价值函数。上一节的 多臂老虎机 只有一个状态、动作不影响未来；MDP 把状态转移和延迟奖励加了回来。本节从马尔可夫性出发，经由马尔可夫过程和马尔可夫奖励过程，逐步给出 MDP、策略、价值函数、最优性和占用度量的定义。

马尔可夫性

如果一个状态满足：未来只依赖于当前状态，而与过去的历史无关，就称该状态具有马尔可夫性：

$$Pr(S_{t+1}\mid S_t)=Pr(S_{t+1}\mid S_0,S_1,\dots ,S_t)$$

直观地说，当前状态已经包含了历史中对预测未来有用的全部信息。比如国际象棋的棋盘局面就是马尔可夫的：知道当前局面就足以决定下一步，不需要知道之前是怎么走到这里的。

从马尔可夫过程到马尔可夫奖励过程

MDP 可以看作在更简单的模型上逐步“加东西”得到的。

马尔可夫过程（Markov Process，MP，也叫马尔可夫链）只有状态和转移：一个二元组 $(\mathcal{S},P)$，其中 $P(s^{\prime }\mid s)$ 是从 $s$ 转移到 $s^{\prime }$ 的概率。把所有转移概率排成矩阵 $P$（每行之和为 1），从某个初始分布 ${\mu }_0$ 出发，$t$ 步后的状态分布就是 ${\mu }_0^{\mathrm{\top }}{P}^t$。在一定条件下（不可约、非周期），这个分布会收敛到唯一的平稳分布 $\mu$，满足 ${\mu }^{\mathrm{\top }}P={\mu }^{\mathrm{\top }}$。

马尔可夫奖励过程（Markov Reward Process，MRP）在 MP 上加上奖励函数 $r(s)$ 和折扣因子 $\gamma$：$(\mathcal{S},P,r,\gamma )$。这时可以谈论“从某个状态出发能累积多少奖励”，即状态价值 $v(s)=\mathbb{E}[G_t\mid S_t=s]$。由回报的递归关系 $G_t=R_{t+1}+\gamma G_{t+1}$（见下文“回报”一节）可以得到

$$v(s)=r(s)+\gamma \sum _{s^{\prime }}P(s^{\prime }\mid s)v(s^{\prime })⟺v=r+\gamma Pv⟹v=(I-\gamma P{)}^{-1}r$$

（$\gamma <1$ 时 $I-\gamma P$ 一定可逆。）这就是下一节贝尔曼方程的最简形式。

MDP 再加上动作：转移和奖励都依赖智能体选择的动作。反过来看，一旦固定了策略 $\pi$，MDP 就退化成一个 MRP：转移矩阵 $P_{\pi }(s^{\prime }\mid s)=\sum _a\pi (a\mid s)p(s^{\prime }\mid s,a)$，奖励 $r_{\pi }(s)=\sum _a\pi (a\mid s)r(s,a)$。所以“评估一个策略”本质上就是求解一个 MRP。

一个三状态的例子：天气在“晴、阴、雨”之间按下面的矩阵转移（行是今天，列是明天），每天的“出行满意度”奖励为晴 2、阴 0.5、雨 −1，$\gamma =0.9$。

今天 \ 明天	晴	阴	雨
晴	0.7	0.2	0.1
阴	0.3	0.4	0.3
雨	0.2	0.4	0.4

本页末尾的代码求出平稳分布约为（晴 0.462，阴 0.308，雨 0.231），MRP 价值为 $v$（晴）≈ 10.463、$v$（阴）≈ 7.575、$v$（雨）≈ 5.641，并用模拟验证了这两个结果。

MDP 的定义

一个 MDP 由五元组 $(\mathcal{S},\mathcal{A},p,r,\gamma )$ 定义：

• $\mathcal{S}$：状态集合；
• $\mathcal{A}$：动作集合；
• $p(s^{\prime },r\mid s,a)$：动力学函数，在状态 $s$ 执行动作 $a$ 后，转移到 $s^{\prime }$ 并获得奖励 $r$ 的概率；
• $r(s,a)$：期望奖励，$r(s,a)=\mathbb{E}[R_{t+1}\mid S_t=s,A_t=a]$；
• $\gamma \in [0,1]$：折扣因子。

由动力学函数可以导出状态转移概率：

$$p(s^{\prime }\mid s,a)=\sum _{r}p(s^{\prime },r\mid s,a)$$

回报

从时刻 $t$ 开始的回报定义为折扣奖励之和：

$$G_t=\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}$$

它满足一个非常重要的递归关系，这是后面贝尔曼方程的基础：

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

当 $\gamma <1$ 且奖励有界（$|R|\le R_{max}$）时，回报也有界：$|G_t|\le {\displaystyle \frac{R_{max}}{1-\gamma }}$。

策略

策略 $\pi$ 描述智能体的行为方式：

• 随机性策略：$\pi (a\mid s)=Pr(A_t=a\mid S_t=s)$；
• 确定性策略：$a=\mu (s)$。

在 MDP 中，策略只依赖于当前状态（这正是马尔可夫性带来的便利），并且可以证明，总存在一个确定性的最优策略。

价值函数

状态价值函数：从状态 $s$ 出发，之后一直遵循策略 $\pi$ 的期望回报

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

动作价值函数：在状态 $s$ 执行动作 $a$，之后遵循策略 $\pi$ 的期望回报

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

两者的关系：

$$v_{\pi }(s)=\sum _a\pi (a\mid s)q_{\pi }(s,a)$$$$q_{\pi }(s,a)=\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_{\pi }(s^{\prime })]$$

最优策略与最优价值函数

最优状态价值函数和最优动作价值函数定义为所有策略中能取得的最大值：

$$v_{\ast }(s)=\underset{\pi }{max}{v}_{\pi }(s),q_{\ast }(s,a)=\underset{\pi }{max}{q}_{\pi }(s,a)$$

一旦得到 $q_{\ast }$，最优策略就可以直接贪心地得到：

$${\pi }_{\ast }(s)=\arg \underset{a}{max}{q}_{\ast }(s,a)$$

这就是 Q-learning 和 DQN 等基于价值的方法的核心思路：先学 $q_{\ast }$，再贪心选动作。

一个小例子：两状态 MDP

考虑一个只有两个状态的 MDP：状态 A 和状态 B。

• 在 A 执行“停留”：获得奖励 1，留在 A；执行“前往”：获得奖励 0，转移到 B。
• 在 B 执行任何动作：获得奖励 2，留在 B。

取 $\gamma =0.9$。如果一直停留在 A，价值为 ${\displaystyle \frac{1}{1-0.9}}=10$；如果先去 B，价值为 $0+0.9\times {\displaystyle \frac{2}{1-0.9}}=18$。所以最优策略是在 A 选择“前往”。这个例子说明了放弃眼前奖励、换取长期收益的思想。

占用度量

价值函数从“每个状态值多少”的角度描述策略；另一个等价的角度是看策略把时间花在哪里。给定初始状态分布 ${\mu }_0$，策略 $\pi$ 的（归一化）占用度量（occupancy measure）定义为

$${\rho }^{\pi }(s,a)=(1-\gamma )\sum _{t=0}^{\mathrm{\infty }}{\gamma }^{t}Pr(S_t=s,A_t=a\mid S_0\sim {\mu }_0,\pi )$$

乘上 $(1-\gamma )$ 是为了让 $\sum _{s,a}{\rho }^{\pi }(s,a)=1$，因此它是一个概率分布：可以理解为“按 ${\gamma }^t$ 加权的访问频率”。它有两个重要性质：

1. 回报是占用度量的线性函数：

$$J(\pi )=\mathbb{E}\left[\sum _t{\gamma }^t{R}_{t+1}\right]=\frac{1}{1-\gamma }\sum _{s,a}{\rho }^{\pi }(s,a)r(s,a)$$

2. 策略与占用度量一一对应：由 ${\rho }^{\pi }$ 可以还原出策略 $\pi (a\mid s)={\rho }^{\pi }(s,a)/\sum _{a^{\prime }}{\rho }^{\pi }(s,a^{\prime })$；反过来，满足“流量守恒”线性约束 $\sum _a\rho (s^{\prime },a)=(1-\gamma ){\mu }_0(s^{\prime })+\gamma \sum _{s,a}p(s^{\prime }\mid s,a)\rho (s,a)$ 的非负 $\rho$ 都对应某个策略。

于是“求最优策略”可以改写成在一个多面体上最大化线性函数的线性规划。这个视角在后面会反复出现：GAIL 让学生的占用度量逼近专家的占用度量，约束强化学习对占用度量施加额外的线性约束，离线强化学习 中的分布偏移也可以理解为数据的占用度量与新策略的占用度量不一致。

用上面的两状态例子验证（初始总在 A，$\gamma =0.9$）：

策略	$\rho$(A, 停留)	$\rho$(A, 前往)	$\rho$(B, ·)	$⟨\rho ,r⟩/(1-\gamma )$	$v(A)$
总是停留	1.000	0.000	0.000	10.000	10.000
总是前往	0.000	0.100	0.900	18.000	18.000
随机 50/50	0.091	0.091	0.818	17.273	17.273

“总是前往”的策略只在第 0 步位于 A，所以 $\rho (\text{A},\text{前往})=1-\gamma =0.1$，其余 0.9 的“折扣时间”都在 B 上。三种策略的 $⟨\rho ,r⟩/(1-\gamma )$ 都与直接求解得到的 $v(\text{A})$ 完全一致。

代码：MP、MRP 与占用度量

"""从马尔可夫过程（MP）到马尔可夫奖励过程（MRP），再到 MDP 的占用度量（occupancy measure）。
1) MP：三状态天气链，求平稳分布；2) MRP：加上奖励，用 v = (I - γP)^{-1} r 求价值并用蒙特卡洛验证；
3) 占用度量：在本章的两状态 MDP（A/B）上计算 ρ^π(s, a)，并验证 V^π(s0) = <ρ^π, r> / (1 - γ)。"""
import numpy as np

rng = np.random.default_rng(0)
gamma = 0.9

# ---------- 1) 马尔可夫过程：状态 0=晴 1=阴 2=雨 ----------
names = ["晴", "阴", "雨"]
P = np.array([[0.7, 0.2, 0.1],
              [0.3, 0.4, 0.3],
              [0.2, 0.4, 0.4]])
w, V = np.linalg.eig(P.T)                                    # 平稳分布：P^T μ = μ 的特征向量
mu = np.real(V[:, np.argmin(np.abs(w - 1))]); mu /= mu.sum()
print("MP 平稳分布：", {n: round(float(m), 4) for n, m in zip(names, mu)})
s, counts = 0, np.zeros(3)
for _ in range(200_000):
    s = rng.choice(3, p=P[s]); counts[s] += 1
print("MP 模拟 20 万步的状态频率：", {n: round(float(c), 4) for n, c in zip(names, counts / counts.sum())})

# ---------- 2) 马尔可夫奖励过程：每天的“出行满意度”奖励 ----------
r = np.array([2.0, 0.5, -1.0])
v = np.linalg.solve(np.eye(3) - gamma * P, r)
print("MRP 解析价值 v = (I-γP)^{-1} r：", {n: round(float(x), 3) for n, x in zip(names, v)})
mc = []
for _ in range(5000):                                        # 从“雨”出发的蒙特卡洛估计（截断 150 步）
    s, G = 2, 0.0
    for t in range(150):
        G += gamma ** t * r[s]; s = rng.choice(3, p=P[s])
    mc.append(G)
print(f"MRP 蒙特卡洛估计 v(雨)：{np.mean(mc):.3f} ± {np.std(mc) / np.sqrt(len(mc)):.3f}")

# ---------- 3) 占用度量：两状态 MDP，状态 A=0, B=1；A 的动作 0=停留 1=前往，B 只有一个动作 ----------
# 为了写成统一的矩阵形式，B 的两个动作效果相同（奖励 2，留在 B）
Pmdp = np.zeros((2, 2, 2)); R = np.zeros((2, 2))
Pmdp[0, 0, 0], R[0, 0] = 1.0, 1.0                            # A 停留：奖励 1，留在 A
Pmdp[0, 1, 1], R[0, 1] = 1.0, 0.0                            # A 前往：奖励 0，到 B
Pmdp[1, :, 1], R[1, :] = 1.0, 2.0                            # B：奖励 2，留在 B
s0 = np.array([1.0, 0.0])                                    # 初始总在 A


def occupancy(pi):
    """ρ(s,a) = (1-γ) Σ_t γ^t Pr(s_t=s, a_t=a)。先解 d = (1-γ) s0 + γ P_π^T d，再乘 π。"""
    P_pi = np.einsum("sa,sat->st", pi, Pmdp)
    d = np.linalg.solve(np.eye(2) - gamma * P_pi.T, (1 - gamma) * s0)
    return d[:, None] * pi


def value(pi):
    P_pi = np.einsum("sa,sat->st", pi, Pmdp); r_pi = (pi * R).sum(1)
    return np.linalg.solve(np.eye(2) - gamma * P_pi, r_pi)


for name, pA in [("总是停留", 0.0), ("总是前往", 1.0), ("随机 50/50", 0.5)]:
    pi = np.array([[1 - pA, pA], [0.5, 0.5]])
    rho = occupancy(pi)
    print(f"策略「{name}」：ρ(A,停留)={rho[0, 0]:.3f} ρ(A,前往)={rho[0, 1]:.3f} ρ(B,·)={rho[1].sum():.3f} "
          f"| Σρ={rho.sum():.3f} | <ρ,r>/(1-γ)={(rho * R).sum() / (1 - gamma):.3f} | V(A)={value(pi)[0]:.3f}")

实际运行输出：

MP 平稳分布： {'晴': 0.4615, '阴': 0.3077, '雨': 0.2308}
MP 模拟 20 万步的状态频率： {'晴': 0.4629, '阴': 0.3075, '雨': 0.2296}
MRP 解析价值 v = (I-γP)^{-1} r： {'晴': 10.463, '阴': 7.575, '雨': 5.641}
MRP 蒙特卡洛估计 v(雨)：5.646 ± 0.051
策略「总是停留」：ρ(A,停留)=1.000 ρ(A,前往)=0.000 ρ(B,·)=0.000 | Σρ=1.000 | <ρ,r>/(1-γ)=10.000 | V(A)=10.000
策略「总是前往」：ρ(A,停留)=0.000 ρ(A,前往)=0.100 ρ(B,·)=0.900 | Σρ=1.000 | <ρ,r>/(1-γ)=18.000 | V(A)=18.000
策略「随机 50/50」：ρ(A,停留)=0.091 ρ(A,前往)=0.091 ρ(B,·)=0.818 | Σρ=1.000 | <ρ,r>/(1-γ)=17.273 | V(A)=17.273

小结与下一步

MDP 给出了强化学习问题的形式化描述，价值函数则衡量了策略的好坏。下一节 贝尔曼方程 将推导价值函数满足的递归方程，它是几乎所有强化学习算法的出发点。

练习题

1. 在两状态例子中，若 $\gamma =0.5$，最优策略还是“前往”吗？求使两种策略价值相等的 $\gamma$。
2. 证明 $v_{\pi }(s)=\sum _a\pi (a\mid s)q_{\pi }(s,a)$。
3. 举一个不满足马尔可夫性的状态表示的例子，并说明如何扩充状态使其满足马尔可夫性。
4. 若奖励满足 $|R|\le 1$、$\gamma =0.99$，回报的取值范围是多少？
5. 为什么在 MDP 中只需要考虑依赖当前状态的策略，而不需要依赖历史的策略？
6. 对天气 MRP，手算 $\gamma =0$ 时的价值，并解释为什么此时 $v=r$。
7. 证明占用度量满足流量守恒约束，并利用它推导 $J(\pi )=⟨{\rho }^{\pi },r⟩/(1-\gamma )$。

参考文献

• Bellman, R. (1957). A Markovian decision process. Journal of Mathematics and Mechanics, 6(5), 679–684.
• Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley.
• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.), 第 3 章.
• Altman, E. (1999). Constrained Markov Decision Processes. Chapman & Hall/CRC.（占用度量与线性规划视角）
• Syed, U., Bowling, M., & Schapire, R. E. (2008). Apprenticeship learning using linear programming. ICML.