马尔科夫决策过程入门：从五元组到价值迭代的强化学习基石

如果你最近开始啃强化学习不管翻教材还是跟着公开课走前两章几乎都会落到同一个概念上马尔科夫决策过程也就是 MDP。我当年第一次看到“马尔科夫决策过程”这七个字第一反应是这到底是个数学问题还是计算机问题和“强化”又有什么关系后来自己动手用 MDP 搭过几个小环境、跑过价值迭代和 Q-learning 之后才彻底想明白MDP 就是整个强化学习的地基。它回答的问题其实特别实在——在一个充满随机性的环境里怎么通过一连串动作让长期收益最大。这篇文章我不会只堆公式。我想带着你把这套框架一层层拆开先看它到底在描述什么场景再看五个核心元素各自扮演什么角色然后搞懂策略、回报、价值函数和贝尔曼方程这些“高频词”背后的直觉最后我会直接给你一个可以运行的格子世界小项目把价值迭代落在代码上。看到最后你会发现MDP 没那么高高在上它就是一个把“试错决策”翻译成数学语言的标准格式。1. 为什么所有强化学习书都从 MDP 讲起1.1 一个决策过程的通用骨架我们先不聊数学先看一个特别日常的画面你打游戏屏幕上显示当前画面你按下一个键画面变了分数也变了。这个循环重复无数次你的目标不是把“这一帧”的分数拿满而是让“整局游戏”的分数尽可能高。强化学习里的智能体Agent和环境Environment就是这么互动的。智能体观察当前状态State做出一个动作Action环境返回一个奖励Reward然后把状态推进到下一个状态。听起来很简单但这套循环里藏着一个和监督学习完全不同的本质区别你的动作会影响下一个状态而下一个状态又会影响你之后的所有决策。这不是“喂一批静态样本、学一个映射”的问题而是一段互相牵连的序列决策问题。MDP 的价值就是把这套“观察—行动—反馈—再观察”的循环变成一个严格可计算的数学结构。有了这个结构算法才能讨论“什么叫做更好的策略”才能推导怎么改进策略。你可以把 MDP 理解成一张标准表格不管什么问题只要你能把它填进这张表格里后面就有现成的数学工具帮你找最优解。1.2 “马尔科夫”到底在强调什么“马尔科夫决策过程”这个定语里的“马尔科夫”通常是新手第一个犯糊涂的地方。教材里的标准说法是未来只与当前状态有关与过去的历史无关。这个说法本身没错但特别容易被误解成“这个系统没有记忆”。我更喜欢另外一个解释当前状态已经包含了做决策所需的全部信息历史里该记的事都已经沉淀在当前状态里了。下棋就是最好的例子。你不需要回忆“我前三步是怎么走的”你只需要看当前棋盘上的局面就足够决定下一步。就算对手有出招习惯你也可以把“我对对手习惯的估计”作为一个新的特征拼进当前状态里它照样满足马尔可夫性质。这个性质真正的意义是把状态空间从“所有可能的完整历史”压缩成“所有可能的状态”。如果每一步都要记整个历史状态数量会随着时间指数爆炸任何算法都跑不动。所以马尔可夫性质不是限制它是在帮你做合理抽象。1.3 MDP 和“强化学习”的分工顺带说清楚一个常见困惑MDP 是问题框架强化学习是求解手段。MDP 负责“把一个问题描述清楚”比如状态是什么、动作是什么、奖励怎么算、状态怎么转移。至于怎么找到那个最优策略是后续价值迭代、Q-learning、策略梯度这些算法要做的事。很多入门材料把这两层混在一起讲导致人越看越乱。你自己心里先把这个界限划清楚先有 MDP再有求解算法。2. 拆解 MDP 的五元组从符号到直觉2.1 五个核心元素各管哪一块一个 MDP 通常写成五元组 (S, A, P, R, γ)。乍一看全是符号其实每个符号对应一个特别具体的现实问题。符号名称数学表示大白话S状态集合s ∈ S所有可能出现的局面A动作集合a ∈ A(s)当前局面下你可以做的选择P状态转移概率P(s′ | s, a)你做了动作 a 之后局面变成 s′ 的概率R奖励函数R(s, a, s′)这次转移给你多少分γ折扣因子γ ∈ [0, 1]未来的奖励在今天看来值多少钱这里需要注意动作集合 A 不一定每个状态下都一样。比如机器人电量低的时候能做的动作集合可能就不包括“开启高功耗模式”。写环境代码的时候不要假设每个状态的动作空间都相同。状态转移概率 P 是整个 MDP 里最核心也最麻烦的部分。它描述的是环境对动作的“响应随机性”你按了“向右”结果可能因为打滑、风速或者对手干扰实际走到了别的方向。这个随机性不是噪声而是环境本身的属性合理建模它后面所有价值计算才靠谱。2.2 奖励函数才是真正的“设计重灾区”奖励函数 R 的任务是告诉智能体“什么结果值得追求”。很多人以为奖励函数随便给个正数就行大错特错。我见过一个模拟清扫任务设定“清扫面积越大奖励越高”结果智能体学会了反复推垃圾制造面积变化实际房间反而更乱。这就是典型的奖励被钻空子。奖励设计有两种极端分别是稀疏奖励和稠密奖励。稀疏奖励就是只有完成最终目标才给一个奖励比如整间屋子扫完才给 10。好处是不容易被钻空子坏处是探索期智体根本不知道自己在往哪个方向走学习极慢。稠密奖励则是每一步都有一点反馈比如“离目标近一点就给 0.1”能显著加速学习但又必须小心“刷分捷径”。我的实操建议是第一版奖励宁可稀疏一点先让整个训练流程跑通再根据失败模式逐步补充过程奖励。不要一开始就设计一套带八个参数的奖励函数你根本分不清最后的策略是因为奖励好还是因为环境巧。2.3 转移概率 P 的三种来源直接决定算法选型P(s′ | s, a) 在实际项目里有三种来源不同来源对应完全不同的技术路线。第一种模型已知。比如棋盘游戏、规则明确的谜题你精确知道每个动作后会出现什么新状态。这种场景可以直接用动态规划求解。第二种模型可学。比如机器人控制你大概知道运动学方程但摩擦力、电机噪声不确定需要用样本去拟合一个环境模型。这是 model-based 强化学习的典型场景。第三种模型完全未知。比如推荐系统、广告竞价用户点击行为没有一个确定公式只能靠真实交互数据一点点估计。这是 model-free 强化学习的天下。我见过很多入门者在这条线上纠结“哪个算法最好”其实先问一句“我知道状态转移规则吗”问题就解决了一半。MDP 的理论框架假设模型已知但真实世界里大多数时候未知所以后续算法才会分化出那么多流派。3. 策略、回报与价值函数怎么定义“好”3.1 策略 π(a|s) 是智能体的“行动手册”有了 MDP 的五个元素接下来要找一个规则告诉智能体看到状态 s你应该选哪个动作。这个规则就是策略记作 π(a | s)。它可以是确定性的也就是“看到 s 就执行 a”也可以是随机的比如“看到 s 时以 70% 概率选 a30% 概率选 b”。不少新手觉得随机策略是“没训练好的策略”其实不是。石头剪刀布这个游戏里任何确定性策略都会被对手针对唯一最优策略就是完全随机。对抗场景、探索需求、博弈均衡都会让随机策略成为理性选择。这也是为什么很多现代强化学习算法输出的不是单个动作而是一个动作分布。从策略出发就可以定义“这个策略有多好”按照这个策略行动长期累积能拿多少奖励。这个“长期累积”不是简单相加要经过折扣处理。3.2 折扣因子 γ为什么未来的钱要打折回报Return的定义是Gₜ Rₜ₊₁ γRₜ₊₂ γ²Rₜ₊₃ ...用大白话翻译当前这一步之后的收益第一步奖励全算第二步奖励要打个折第三步要折两次越往后越不值钱。为什么要这么干三个理由。第一数学上如果 γ 1无限长的回报序列加起来仍然是一个有限值算法才有收敛的可能。否则在无限视野任务里回报直接发散到无穷大什么都比较不了。第二现实上未来充满不确定性。今天确定拿到的 100 块比承诺十年后给你的 100 块更值钱。这和“钱的时间价值”是一个道理。第三实践上γ 的大小直接影响策略偏好。γ 0 表示“只在乎眼前利益”γ 0.9 表示“稍微看重未来”γ 0.99 表示“未来收益和眼前收益几乎一样重要”。你训练一个下棋 AI需要 γ 接近 1因为一盘棋几十步之后才会决出胜负你训练一个即时决策机器人γ 就不能设太大否则它会把算力都花在无意义的远期幻想上。3.3 价值函数和贝尔曼方程递归是核心武器策略有了回报公式有了接下来怎么算“某个状态有多好”这就需要价值函数。状态价值函数 V^π(s) 表示从状态 s 出发按照策略 π 行动未来能拿到的期望回报。动作价值函数 Q^π(s, a) 表示从状态 s 出发先执行动作 a之后按照策略 π 行动未来能拿到的期望回报。两者关系很直观V^π(s) 就是对所有可能动作的 Q 值求加权平均权重就是策略 π(a|s)。反过来Q 值等于“当前动作带来的即时奖励 环境转移到的下一个状态的 V 值的折扣”。把上面这段写成公式就是贝尔曼期望方程V^π(s) Σ π(a|s) Σ P(s′|s,a) [ R(s,a,s′) γV^π(s′) ]第一次看到这个式子觉得头大很正常我帮你在脑子里画个树状图。从状态 s 出发你按策略选动作每个动作是一个树枝环境收到动作后随机转移到新状态每个转移又是一个小树枝。理论上你要枚举出未来所有可能的路径才能算清期望回报。可这个方程的精妙之处在于不用展开整棵树只需要知道“下一步的奖励”和“下一个状态的期望价值”就够了。因为 V^π(s′) 已经把“从 s′ 出发的所有未来”都打包好了。这就是递归拆解问题也是贝尔曼方程整个家族的核心思想。最优价值函数 V*(s) 则是在所有策略中取最大期望回报它对应的贝尔曼最优方程是V*(s) max_a Σ P(s′|s,a) [ R(s,a,s′) γV*(s′) ]后面 Q-learning、DQN 这些算法本质上都是想近似逼近这个最优方程。4. 从 MDP 到求解算法动态规划、蒙特卡洛与时序差分4.1 动态规划开着上帝视角的“暴力美学”如果环境模型完全已知也就是 P(s′|s,a) 和 R(s,a,s′) 都明确那可以直接用动态规划来解 MDP。动态规划的核心是策略迭代先固定一个策略用贝尔曼方程反复计算每个状态的价值这叫策略评估等价值稳定后再根据新价值调整策略每个状态都改成选择“当前 Q 值最大”的动作这叫策略改进。两者交替进行不断逼近最优策略。价值迭代是策略迭代的简化版它不再严格区分评估和改进而是每一步直接用最优贝尔曼方程同步更新所有状态的价值。代码实现起来相当干净后面第 6 部分我会直接写一个完整的价值迭代 Demo。动态规划的局限很明显它需要你精确知道状态转移概率和奖励函数也就是“上帝视角”。现实世界大多数场景给不了这个条件所以动态规划更多承担“理论基线”的角色用来验证其他算法在一个已知环境上做得有多接近最优。4.2 蒙特卡洛不建模跑完整轨迹再回头总结没有模型怎么办最直接的想法就是“跑一遍看看”。蒙特卡洛方法的思路很简单让智能体按照策略从头玩到结束得到一条完整轨迹把轨迹里每一步的真实累计回报 Gₜ 记下来。一个状态被访问过多次就取这些累计回报的平均值作为该状态的价值的估计。优点是无偏只要你采样足够多估计值就会收敛到真实价值。缺点是方差大因为一整条轨迹里积累的随机性太多某一次跑出来的回报可能和平均水平差得很远。而且你必须要等到回合结束才能更新价值如果任务是长期不结束的蒙特卡洛根本没法用。4.3 时序差分走一步就更新一次时序差分TD方法走在两者中间。它从蒙特卡洛那里拿了“用真实采样替代完整模型”的思路又从动态规划那里拿了“用估计更新估计”的递归策略。更新公式长这样V(Sₜ) ← V(Sₜ) α [ Rₜ₊₁ γV(Sₜ₊₁) − V(Sₜ) ]方括号里那一整项叫 TD 误差。它的意思是智能体走了一步看到真实奖励 Rₜ₊₁又看到新的状态 Sₜ₊₁于是能凑出一个“当前状态价值的即时估计”Rₜ₊₁ γV(Sₜ₊₁)。拿这个估计和当前 V(Sₜ) 的差距做修正把 V(Sₜ) 稍微往目标方向推一点。这里有个经典的偏差方差权衡。蒙特卡洛用的是完整真实回报无偏但方差大TD 只走一步用了一部分估计值偏差可能有一点但方差小得多。实际训练中 TD 往往比蒙特卡洛收敛快得多这也是为什么 Q-learning 和 DQN 这些主流强化学习算法都建立在 TD 思想上。三个方法对比一下就很清楚了方法模型需求更新时机偏差方差适用场景动态规划需要完整模型任意时刻低低规则清晰的小规模问题蒙特卡洛无需模型回合结束后无偏高回合制游戏、离线策略评估时序差分无需模型每走一步可能有一定偏差低在线学习、长视野任务5. 入门者最容易踩的四个理解误区5.1 “马尔可夫性质 系统没有记忆”这个误区我见过太多次。马尔可夫性质说的是“当前状态包含了决策所需的全部信息”不是“系统不能看历史”。你完全可以在状态里携带历史摘要比如把上一帧画面、上一步动作拼进当前状态只要新状态满足“给定它就能决策”MDP 依然成立。工程上这叫“状态增强”。5.2 “状态必须完全可观测”真实世界几乎没有完全可观测的状态。你的传感器有盲区、有延迟地图有遮挡对手策略会隐藏。严格来说这些场景属于部分可观测马尔科夫决策过程POMDP。但你不必一碰到部分可观测就觉得自己不能用强化学习。常规做法是把最近 N 步的观测堆叠起来作为“伪状态”或者用循环网络把历史信息编码进隐藏状态把它近似成一个 MDP 再求解。先把基础 MDP 搞明白后面遇到部分可观测才不会慌。5.3 “奖励设得越大智能体学得越快”这个直觉在强化学习里经常翻车。我做过一个模拟清扫环境最初把“成功清扫 10”改成“每个动作 0.1”本意是让信号更密集结果智能体找到了一个在原地反复移动的动作循环靠刷动作把奖励刷到爆炸真实清扫效果反而下降。这就是 reward hacking。奖励的绝对值大小不是越爽越好关键要让“奖励最大”和“你的真实目标”对齐。每次设计完奖励函数可以问自己一句如果我是天生懒惰的智能体我会怎么钻这个空子挣钱5.4 “MDP 只能在游戏里用”游戏确实是最适合入门的 MDP 场景因为它奖励清晰、状态可定义、回合边界明确。但 MDP 的应用范围远不止游戏。电商推荐可以建模成“用户状态 → 推荐动作 → 点击购买奖励”的 MDP库存管理是“库存状态 → 补货动作 → 缺货成本奖励”机器人路径规划是“位姿状态 → 移动动作 → 到达目标奖励”。判断一个任务适不适合用 MDP只看三件事是不是序贯决策、有没有延迟奖励、状态转移是否存在随机性。满足这三条就可以尝试用 MDP 来思考。6. 从理论到实践搭一个 4×4 格子世界跑价值迭代6.1 一个从零写出的 MDP 环境理论知识差不多齐了下面动手。我准备了一个最简单的 4×4 格子世界你就当成一个迷你版“寻宝游戏”起点在左上角 (0,0)终点在右下角 (3,3)踩到终点 1 分进入陷阱 (1,1) -1 分其他格子 0 分。动作有四个上、下、左、右。我故意引入一点随机性按意图方向移动的概率是 0.8剩下 0.2 均分给另外三个方向如果撞墙就留在原地。import numpy as np N 4 ACTIONS [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上、下、左、右 ACTION_NAMES [上, 下, 左, 右] GAMMA 0.9 TARGET (3, 3) TRAP (1, 1) def is_terminal(pos): return pos TARGET or pos TRAP def reward_at(pos): if pos TARGET: return 1.0 if pos TRAP: return -1.0 return 0.0 def move(pos, action_idx): 按意图方向移动随机性简化为0.8/0.2的软概率选择。 r, c pos results [] for i, prob in enumerate([0.8, 0.2/3, 0.2/3, 0.2/3]): dr, dc ACTIONS[(action_idx i) % 4] nr, nc r dr, c dc if 0 nr N and 0 nc N: results.append((prob, (nr, nc))) else: results.append((prob, (r, c))) # 撞墙原地不动 return results这段代码把所有和规则相关的东西都抽象成了一个小接口给定一个状态和动作它返回一组概率下一状态的列表。你现在手上就有了一个真正的 MDP 环境。哪怕后面换成 10×10 迷宫、或者换成机器人坐标状态只要接口长得差不多算法部分基本不用大改。6.2 用价值迭代解这个格子世界环境有了接下来写价值迭代。它的核心逻辑只有一行反复执行贝尔曼最优方程直到价值表变化足够小。V np.zeros((N, N)) def expected_q(pos, action_idx): total 0.0 for prob, nxt in move(pos, action_idx): total prob * (reward_at(nxt) GAMMA * V[nxt]) return total def value_iteration(theta1e-4, max_iter1000): global V for it in range(max_iter): V_new V.copy() delta 0.0 for r in range(N): for c in range(N): pos (r, c) if is_terminal(pos): V_new[pos] 0.0 continue best_q max(expected_q(pos, a) for a in range(4)) delta max(delta, abs(V_new[pos] - best_q)) V_new[pos] best_q V V_new if delta theta: print(f迭代第 {it1} 次收敛) break value_iteration() policy np.full((N, N), *) for r in range(N): for c in range(N): pos (r, c) if is_terminal(pos): continue best_a np.argmax([expected_q(pos, a) for a in range(4)]) policy[pos] ACTION_NAMES[best_a] print(状态价值表:) print(np.round(V, 2)) print(最优策略:) print(policy)跑完你会看到左上角附近的价值都是正的但不高靠近陷阱的状态价值会变成负数最优策略则会主动避开陷阱朝终点走。这一步跑通之后贝尔曼方程在你眼里不再是符号而是一张实实在在的数字表格每个格子的 V 值就是“从这个格子开始认真走长期能拿到的回报”。6.3 动手项目里的实操检查清单最后分享几个我在写这类小项目时踩过的坑你可以当检查单用。第一终止状态一定要单独处理。如果不把终点的价值强制置 0价值迭代会把终点自身也当成一个普通状态反复更新策略会变得很怪。第二折扣因子 GAMMA 别拍脑袋定。先试着改成 0.1 和 0.99 对比你会发现策略偏好差异特别大这样你对“远期视野”的理解会立体很多。第三随机转移的期望更新务必写对。上面代码里 move() 返回的是概率和下一状态的配对价值迭代用期望求和一不留神写成“只按意图方向移动”看起来也能跑但环境其实已经被你悄悄改了。第四也是我最想提醒的不要一上来就用现成的强化学习库。我见过太多人直接调库跑 PPO环境问题、奖励问题、状态定义问题全都糊在一个黑盒里出了问题根本定位不到。花一个晚上写一个这样的小格子世界把 V 表和策略表打出来看收获抵得上盲调十天。我自己的体会是MDP 这类理论概念读十遍不如亲手把五元组写一遍。这个 4×4 格子世界总共不过几十行代码却把状态、动作、转移概率、奖励、折扣因子、贝尔曼方程全串了一遍。等你跑通这个项目再回头看 Q-learning、DQN 这些算法的推导思路会顺畅很多。理论不落地永远是纸上的符号落了地才算真正变成你能用的东西。