机器学习数学基础 120 章

Markov 决策过程与 Bellman 方程

层级：B｜建议先修：05-09、08-05

Markov 决策过程（MDP）在 Markov 链上加入行动和奖励，用来描述智能体与环境的连续交互。Bellman 方程把长期回报分解为“当前奖励 + 下一状态的未来价值”。

1. MDP 五元组

一个有限 MDP 通常记为

(S,A,P,R,γ),(\mathcal S,\mathcal A,P,R,\gamma),

其中：

  • S\mathcal S：状态集合；
  • A\mathcal A：动作集合；
  • P(s′∣s,a)P(s'\mid s,a)：转移概率；
  • RR：奖励模型，如 R(s,a)=E[Rt+1∣St=s,At=a]R(s,a)=\mathbb E[R_{t+1}\mid S_t=s,A_t=a]；
  • γ∈[0,1]\gamma\in[0,1]：折扣因子。

环境满足 Markov 性质：给定当前状态和动作后，下一状态与奖励的分布不再依赖完整历史。

2. 策略

策略描述在状态下如何选动作：

π(a∣s)=P(At=a∣St=s).\pi(a\mid s)=P(A_t=a\mid S_t=s).

确定性策略写成 a=π(s)a=\pi(s)，随机策略则输出动作分布。固定策略后，MDP 诱导出一条 Markov 奖励过程。

3. 回报与折扣

从时刻 tt 起的折扣回报定义为

Gt=Rt+1+γRt+2+γ2Rt+3+⋯ .G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots.

它满足递归式

Gt=Rt+1+γGt+1.G_t=R_{t+1}+\gamma G_{t+1}.

折扣可表达对近期奖励的偏好，也能在持续任务中使有界奖励的无限和收敛。

4. 状态价值函数

策略 π\pi 下的状态价值为

Vπ(s)=Eπ[Gt∣St=s].V^\pi(s)=\mathbb E_\pi[G_t\mid S_t=s].

它表示从状态 ss 出发并一直遵循 π\pi 的预期长期回报。

5. 动作价值函数

Qπ(s,a)=Eπ[Gt∣St=s,At=a].Q^\pi(s,a) =\mathbb E_\pi[G_t\mid S_t=s,A_t=a].

它先固定第一步动作 aa，之后再遵循策略 π\pi。两者关系为

Vπ(s)=∑aπ(a∣s)Qπ(s,a).V^\pi(s)=\sum_a\pi(a\mid s)Q^\pi(s,a).

6. Bellman 期望方程

利用回报递归式和全期望公式：

Vπ(s)=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)[r+γVπ(s′)].V^\pi(s) =\sum_a\pi(a\mid s) \sum_{s',r}p(s',r\mid s,a) [r+\gamma V^\pi(s')].

相应地，

Qπ(s,a)=∑s′,rp(s′,r∣s,a)[r+γ∑a′π(a′∣s′)Qπ(s′,a′)].Q^\pi(s,a) =\sum_{s',r}p(s',r\mid s,a) \left[r+\gamma\sum_{a'}\pi(a'\mid s')Q^\pi(s',a')\right].

7. 矩阵形式

固定策略后，令 PπP^\pi 为策略诱导的转移矩阵，rπ\mathbf r^\pi 为期望即时奖励，则

vπ=rπ+γPπvπ.\mathbf v^\pi=\mathbf r^\pi+\gamma P^\pi\mathbf v^\pi.

因此当逆存在时

vπ=(I−γPπ)−1rπ.\mathbf v^\pi=(I-\gamma P^\pi)^{-1}\mathbf r^\pi.

实际大规模问题通常使用迭代法，而不显式求逆。

8. 最优价值函数

V∗(s)=max⁡πVπ(s),Q∗(s,a)=max⁡πQπ(s,a).V^*(s)=\max_\pi V^\pi(s), \qquad Q^*(s,a)=\max_\pi Q^\pi(s,a).

Bellman 最优方程为

V∗(s)=max⁡a∑s′,rp(s′,r∣s,a)[r+γV∗(s′)],V^*(s)=\max_a\sum_{s',r}p(s',r\mid s,a) [r+\gamma V^*(s')],

以及

Q∗(s,a)=∑s′,rp(s′,r∣s,a)[r+γmax⁡a′Q∗(s′,a′)].Q^*(s,a)=\sum_{s',r}p(s',r\mid s,a) [r+\gamma\max_{a'}Q^*(s',a')].

知道 Q∗Q^* 后，可取贪心动作 arg⁡max⁡aQ∗(s,a)\arg\max_aQ^*(s,a) 得到最优策略。

9. Bellman 算子与压缩映射

对固定策略定义

(TπV)(s)=Eπ[Rt+1+γV(St+1)∣St=s].(T^\pi V)(s)=\mathbb E_\pi[R_{t+1}+\gamma V(S_{t+1})\mid S_t=s].

当 0≤γ<10\le\gamma<1 时，它在最大范数下是 γ\gamma-压缩：

∥TπV−TπW∥∞≤γ∥V−W∥∞.\|T^\pi V-T^\pi W\|_\infty \le\gamma\|V-W\|_\infty.

因此有唯一不动点 VπV^\pi，反复应用算子会收敛。这是迭代策略评估和值迭代的理论基础。

10. 最优策略的存在

在有限折扣 MDP 中，存在一个确定性、平稳的最优策略。也就是说，为最大化期望折扣回报，不必依赖完整历史或时间变化，只根据当前状态选一个动作即可。

11. 部分可观测情形

若观测不能完整表示环境状态，直接把观测当状态可能违反 Markov 性质。POMDP 使用对隐状态的信念分布作为状态；循环神经网络也可学习历史摘要，但是否充分仍需验证。

12. 易错点

  1. 奖励是一步反馈，价值是未来折扣奖励的期望总和。
  2. VπV^\pi 与 V∗V^* 不同；前者评价固定策略，后者在策略中取最优。
  3. 环境转移概率与策略的动作概率是两套不同分布。
  4. 状态表示若不具 Markov 性，Bellman 方程的标准形式会失去依据。

常见问答

Q1：为什么使用期望，而不是保证获得的回报？
环境和策略可能随机，价值函数优化的是在给定概率模型下的平均长期表现；风险敏感目标需要额外建模。

Q2：γ=0\gamma=0 表示什么？
只关心下一步即时奖励。γ\gamma 越接近 1，未来奖励影响越大。

Q3：Bellman 方程是定义还是算法？
它是价值函数满足的递归一致性方程；动态规划和各种强化学习算法据此构造更新。

Q4：为什么不直接求矩阵逆？
状态数大时矩阵存储和求逆昂贵，且模型可能未知；迭代和采样方法更实际。

练习

  1. 从 Gt=Rt+1+γGt+1G_t=R_{t+1}+\gamma G_{t+1} 推导 Bellman 期望方程。
  2. 写出 Q∗Q^* 的 Bellman 最优方程，并说明最大化发生在哪一步。
  3. 若每步奖励恒为 1、0≤γ<10\le\gamma<1，持续任务中任意状态价值是多少？
  4. 解释为什么固定策略后 MDP 变成 Markov 奖励过程。

答案与提示

  1. 对给定状态下的动作、下一状态和奖励使用全期望公式。
  2. Q∗(s,a)=E[r+γmax⁡a′Q∗(s′,a′)]Q^*(s,a)=\mathbb E[r+\gamma\max_{a'}Q^*(s',a')]，第一步动作已固定，最大化发生在下一状态的后续动作。
  3. 1+γ+γ2+⋯=1/(1−γ)1+\gamma+\gamma^2+\cdots=1/(1-\gamma)。
  4. 策略把状态映射为动作分布，与环境转移合并后得到只依赖当前状态的转移和奖励分布。