马尔科夫决策过程(MDP)详解：从五元组到贝尔曼方程的强化学习基石

1. 为什么强化学习必须从MDP讲起初学强化学习的时候很多人第一眼看到的是 Q-learning、策略梯度这些具体算法然后被一堆函数逼近、奖励归一化的细节淹没。但不管用什么算法所有强化学习问题都有一个共同的底子——马尔科夫决策过程业内一般直接叫 MDP。可以说没把 MDP 吃透后面看任何强化学习论文都会觉得隔了一层而一旦把 MDP 的框架和几个关键公式弄明白那些算法书里的符号突然就都通了。这篇文章我就是想用最直白的方式把 MDP 从定义到推导再到代码完整讲一遍。不堆公式吓人但该有的公式一个不少每一个都解释清楚它到底在说什么、为什么长这样。适合刚入门强化学习的研究生、正在看论文但被公式卡住的工程师也适合想从原理层面理解机器人决策、推荐系统、游戏 AI 这类系统为什么能自动学会策略的人。跟着走一遍你会获得一个非常清晰的坐标系之后再看 PPO、DQN 这些都顺很多。1.1 马尔可夫性只看“现在”不看“过去”MDP 的核心假设就一句话未来的状态只依赖于当前状态与过去的历史无关。这就是马尔可夫性。听起来很苛刻但实际工程里这是一个非常实用的简化——它等于给决策问题装了一个“失忆开关”无论之前走了多少弯路只要现在站在同一个状态接下来的一切都以同样方式发展。我举个特别生活化的例子。想象你正站在一家商场的一楼想去三楼看电影。站在一楼电梯口的时候你过去是从地下车库上来的还是从侧门走进来的对“坐电梯还是走扶梯”这个决策来说几乎没有区别。真正有用的信息是“我现在在几楼、电梯在哪个位置、还有多少时间”。把这些信息压缩成“当前状态”之后决策就只跟这个状态有关了。这就是马尔可夫性给我们的底气。当然现实世界几乎不存在严格意义上的马尔可夫性。你站在商场一楼但脚旁边有个水坑这个细节会影响你选哪条路而“水坑”并不一定在你定义的“状态”里。因此工程上真正的做法是尽量把决策相关的信息全部纳入状态定义中让近似马尔可夫性成立。MDP 框架本身允许误差重要的是你在建模时心里清楚自己做了这个“只看当前”的假设并且知道这个假设什么时候会害了你。这一点我在后面“常见问题”部分会详细展开先留个记号。1.2 从马尔可夫链到马尔科夫决策过程动作和奖励的加入很多教材直接从马尔可夫链讲起马尔可夫链是一个无决策的随机过程状态转移完全由概率表决定人没有选择权。MDP 在这个基础上加了两样东西动作和奖励。动作让“转移概率”变成了条件概率我不再问“从状态 s 转移到 s 的概率是多少”而是问“我在状态 s 执行动作 a 之后转移到 s 的概率是多少”。这个概率记作 P(s | s, a)它反映的是环境对行为的响应。奖励函数则是决策的目标信号。它告诉智能体执行这个动作之后你获得了多少即时反馈。这个反馈可以是正数、负数也可以为零。比如倒立摆实验中每保持一秒钟不倒下给 1围棋中赢棋 1、输棋 -1推荐系统里用户点击 1长时间停留 0.5。把这两个量加上去之后问题从“描述状态怎么演化”变成了“我该如何选择动作才能让长期累积奖励最大”。这也正是 MDP 这个名称的来历——你面对的是一个包含决策的随机过程。表格对比一下会更清楚对比项马尔可夫链马尔科夫决策过程MDP核心要素状态、转移概率状态、动作、转移概率、奖励、折扣因子谁在做决策无人纯随机演化智能体在每个状态选择动作目标描述过程演化规律最大化长期累积奖励典型问题未来天气如何演变雨雪天该选择哪种通勤方式一句话总结马尔可夫链描述世界MDP 则让你成为世界中那个做选择的人。2. MDP 的五个核心要素定义、直觉与选择2.1 状态集合与动作集合粒度就是建模哲学MDP 最基础的两个集合是状态集合 S 和动作集合 A。它们既是建模的起点也决定了问题求解的难度。状态集合就是智能体感知到的环境快照。状态定义得多细直接反映你对问题的理解深度。以自动驾驶为例最粗的状态可能是“当前路段是否拥堵”细一点可以是“本车的位置、速度、朝向”再细一点还要加入周围车辆的相对位置。状态越细信息越充分但状态空间规模也急剧膨胀这让后续所有计算都变得昂贵。经验法则状态能区分不同最优动作时才值得加进去。一个永远不影响决策的变量定义到状态里只会增加计算压力。动作集合则是智能体可选择的“干预手段”。需要注意动作集合可以依赖状态在某些状态下某些动作是非法或不可执行的。比如电梯在维修时你按下上行按钮没有意义。动作粒度同样有讲究机器人的动作可以是“向左移动1米”也可以是“左轮转速300rpm”。后者更加精细但也会让学习空间变大。实际建模时大部分新手犯的错误是试图直接输入原始传感信号作为状态。这也不是不行但原始信号往往高度冗余且不一定包含决策所需的关键信息。做项目的时候我习惯先问自己在这个状态下到底哪些信息会影响我下一步该做什么把它们列成列表再决定哪些作为状态变量。与其一上来追求“全”不如先把明显关键的信息放进去跑通之后再逐步增加复杂度。2.2 转移概率、奖励函数和折扣因子环境如何回应你正式定义一个 MDP 通常用五元组 (S, A, P, R, γ)。P 是状态转移概率分布R 是奖励函数γ 是折扣因子。前两者描述“环境怎么响应你”后者回答“你有多在乎未来”。转移概率 P(s | s, a) 的直觉非常好懂在状态 s 做动作 a环境以什么概率把我弹到状态 s。有一个很容易被初学者忽略的细节奖励和转移概率可以捆绑定义即 P(s, r | s, a) 的联合分布。这意味着同一个转移在不同的剧情下可能给出不同的奖励。不过绝大多数教材为了方便会写成分别定义的 P 和 R但心里要清楚真实世界中奖励通常不是一个确定性函数而是随转移一起抽样得到的。这一点在实现强化学习环境时尤其重要后面代码部分我会再提到。奖励函数 R(s, a, s) 定义了局部目标。它只衡量当前这一步的好坏不回答“长期好不好”。长期好不好是价值函数的事后面再说。很多初学者会误以为奖励函数应该设计成“这一步走得对不对、策略好不好”然后拼命调奖励想引导智能体走出最优轨迹。这种思路常常适得其反——奖励设计的目标应该是忠实反映任务目标而不是变成“人工指挥棒”。最典型的错误是给中间状态加分比如“靠近目标 0.1”结果智能体学会了在目标附近来回抖动刷分。这个坑我后面会重点聊。折扣因子 γ 是 MDP 里最容易被忽略但影响极其深远的参数。它是一个 0 到 1 之间的数决定了未来奖励折算成当前价值的比例γ0只看眼前γ 趋近 1几乎无限远视。为什么需要这个因子原因有两层数学上如果累计奖励的期数是无限的直接求和可能发散而乘以 γ 的 k 次幂之后只要奖励有界序列就会收敛直觉上它表达了一种经济学中常见的偏好——今天的 100 元比一年后的 100 元更值钱。从这两个要素可以看出MDP 的建模根本不是单纯的数学工作而是对现实问题本质的抽象。你选择的 P 和 R 是否反映真实环境直接决定了算法学出来的“最优策略”在实际中到底好不好用。我见过不少项目R 定义得离谱转移模型也粗糙后面算法怎么调都没用——问题不在算法而在 MDP 建模这一步。3. 价值函数与贝尔曼方程MDP 的灵魂3.1 状态价值函数与动作价值函数有了五元组下一步就是定义“什么叫好”。我们需要一个量来衡量处在某个状态或者在某状态执行某动作从长远看能获得多少奖励。这就引出了价值函数。先看状态价值函数 V(s)它表示从状态 s 出发按照某种策略 π 选择动作未来能获得的折扣累计奖励的期望值。写成公式就是V_π(s) E[ R_t γ R_{t1} γ² R_{t2} ... | S_t s, π ]这个期望暗含了两层随机性策略 π 给出的动作选择是随机的环境对动作的响应转移和奖励也是随机的。V 值越大说明这个状态在当前策略下越“有利可图”。再看动作价值函数 Q(s, a)它的定义几乎相同差别只在于第一步动作已经确定是 aQ_π(s, a) E[ R_t γ R_{t1} γ² R_{t2} ... | S_t s, A_t a, π ]V 和 Q 的关系非常紧密V 是 Q 在动作分布下的平均。给定策略 π有 V_π(s) Σ π(a|s) Q_π(s, a)。V 少了一个维度适合评估状态好坏Q 多了一个动作维度适合做出决策——要知道某个状态下该选什么动作直接比较不同动作的 Q 值大小取最大者即可。这也是为什么几乎所有决策算法最终都依赖 Q 值或它的变体。这里需要强调一个常见误解V(s) 并不是“处于状态 s 能拿多少奖励”而是“在策略 π 下从这个状态出发能得到多少累积奖励的期望”。同一个状态在不同的策略下价值完全不同。一个残局棋盘对会下棋的人是财富对新手可能就是负资产。3.2 从贝尔曼期望方程到贝尔曼最优方程价值函数最大的威力在于它可以自身嵌套。把第一项奖励从期望里拆出来剩下的部分还是同一个价值函数的折扣期望。这个自举式的关系就是贝尔曼方程。贝尔曼期望方程的推导过程很简单。从状态 s 出发按照策略 π 选择动作 a环境转移到 s 并给出奖励 r。于是V_π(s) Σ_a π(a|s) [ R(s,a) γ Σ_{s} P(s|s,a) V_π(s) ]把公式翻译成人话当前状态的价值等于“所有可能动作的即时奖励期望加上转移到下一个状态后、把下一个状态的价值打折算回来”。于是 V 出现在等式两侧变成了一个带有递归结构的方程。这一条看起来简单的等式是整个强化学习理论的地基。对 Q 也有类似的方程Q_π(s,a) R(s,a) γ Σ_{s} P(s|s,a) Σ_{a} π(a|s) Q_π(s,a)。如果目标从“评估策略”变为“寻找最优策略”方程右端就变成取最大动作价值。贝尔曼最优方程是V_(s) max_a [ R(s,a) γ Σ_{s} P(s|s,a) V_(s) ]这个 max 是最优性的核心。它说最优状态下第一步必须选能让“即时奖励后续折扣最优价值”最大的动作。有意思的是最优价值函数虽然还是在递归定义但它已经不再依赖某个具体策略——它就是所有策略里最好的那个。有了这些方程标准解法学过的人应该都清楚如果模型完全已知可以用动态规划求解如果模型未知就需要用免模型算法Q-learning、策略梯度等去估计价值函数。关键是理解所有算法其实都在求解同一个方程区别只是解决不确定性的手段不同。4. 从理论到代码用动态规划求解一个小型 MDP4.1 搭建一个 3 状态 2 动作的示例环境理论说得再多不如跑一段代码直观。我搭一个非常小的环境完整展示值迭代和策略迭代是怎么求解 MDP 的。环境设计三个状态排成一条线编号 0、1、2。状态 2 是终止状态到达之后游戏结束。每一步只能向左动作 0或向右动作 1。环境的噪声会让动作以 20% 的概率执行反方向也就是你选左实际可能会向右。奖励规则只要转移到状态 2奖励 10其他转移奖励 -1。终止状态不会再执行动作。这个环境虽然小但它完整包含了随机转移、正负奖励和终止条件足够演示 MDP 的所有核心机制。在写代码之前有一个非常容易踩的坑值得先说转移概率和奖励在 MDP 里是“环境定义”不是“算法能感知的东西”。动态规划算法需要直接访问这个概率表而免模型算法只能通过采样来间接感知环境。我这份代码用动态规划因此要显式写出概率函数import numpy as np # 状态0, 1, 22 是终止状态 # 动作0 向左1 向右 # 噪声有 0.2 概率执行相反动作 S [0, 1, 2] A [0, 1] gamma 0.9 def get_transitions(s, a): 返回 (概率, 下一状态, 奖励) 的列表。 注意这里返回的是联合分布奖励与转移一同抽样。 results [] for actual_a in [a, 1 - a]: prob 0.8 if actual_a a else 0.2 if actual_a 0: s_next max(0, s - 1) else: s_next min(2, s 1) reward 10 if s_next 2 else -1 results.append((prob, s_next, reward)) return results这里有一个即使写过不少代码的人也容易忽略的点get_transitions 返回的是“概率 下一状态 奖励”的三元组而不是仅返回下一状态。这正是我在 2.2 节强调的 P(s, r | s, a) 联合分布写法。现实中奖励常常伴随转移产生把它和转移捆绑抽样是更自然、也更贴近物理意义的环境建模方式。4.2 策略迭代与值迭代的实现与对比现在实现两种标准算法。第一种是值迭代——直接从贝尔曼最优方程出发反复更新价值表直到收敛def value_iteration(): V np.zeros(len(S)) for _ in range(100): V_new V.copy() for s in [0, 1]: # 状态 2 是终止跳过 q_values [] for a in A: q 0 for prob, s_next, reward in get_transitions(s, a): q prob * (reward gamma * V[s_next]) q_values.append(q) V_new[s] max(q_values) if np.max(np.abs(V_new - V)) 1e-6: break V V_new # 恢复最优策略 policy {} for s in [0, 1]: qs [] for a in A: q 0 for prob, s_next, reward in get_transitions(s, a): q prob * (reward gamma * V[s_next]) qs.append(q) policy[s] int(np.argmax(qs)) return V, policy V, policy value_iteration() print(V , V) print(policy , policy)值迭代的精髓在于它不维护一个显式的策略而是每步都基于当前价值表为每个状态选“当前看起来最好的动作”。随着价值函数逐渐逼近最优 V贪心动作自然就是最优动作。整个过程自洽而且简洁。第二种是策略迭代。思路完全相反先固定一个策略反复用贝尔曼期望方程评估它的价值策略评估然后根据价值改善策略策略改进循环往复直到策略不再变化。代码如下def policy_evaluation(policy): V np.zeros(len(S)) for _ in range(100): V_new V.copy() for s in [0, 1]: a policy[s] V_new[s] 0 for prob, s_next, reward in get_transitions(s, a): V_new[s] prob * (reward gamma * V[s_next]) if np.max(np.abs(V_new - V)) 1e-6: break V V_new return V def policy_iteration(): # 初始策略全部向左 policy np.array([0, 0]) while True: V policy_evaluation(policy) improved False for s in [0, 1]: qs [] for a in A: q 0 for prob, s_next, reward in get_transitions(s, a): q prob * (reward gamma * V[s_next]) qs.append(q) best_a int(np.argmax(qs)) if best_a ! policy[s]: policy[s] best_a improved True if not improved: break return V, policy V2, policy2 policy_iteration() print(V2 , V2) print(policy2 , policy2)我实际跑出来的结果是V [ -8.xx, -0.xx, 0 ]最优策略两处都选择动作 1向右策略迭代和值迭代收敛到完全一致的策略。这个结果很符合直觉向右无论噪声怎么扰动最终更容易到达状态 2因为从状态 1 向右 80% 直接进入终点20% 向左退回 0再从 0 继续向右。对比这两种算法你会发现值迭代更直观、代码更短适合快速验证策略迭代每轮需要完整评估成本高但收敛轮次明显更少。在状态空间大的时候这两种动态规划方法都会因为需要显式遍历所有状态而变得困难所以实际工程里更多用采样型算法。但我强烈建议每个学强化学习的人都亲手跑一遍这两种动态规划它们能帮你在发生其他算法问题时分清到底是环境建模错了还是求值方式错了。5. 那些年我踩过的坑MDP 实践中的常见问题5.1 状态怎么定义才合理太粗与太细的代价这一节是从我自己做项目时的惨痛教训里总结出来的。第一个坑就是状态粒度的选择。状态太粗是一种常见陷阱。做一个路径规划任务我把状态只定义为“当前位置所在区域”忽略了朝向信息。结果智能体学到的策略在部分区域反复折返——它其实无法判断“面向目标”和“背对目标”是两个不同的局面。马尔可夫性对这个场景是失效的因为决策所需的信息根本不在状态里。解决办法很简单把朝向加入状态定义。但需要注意的是同样的错误也可能是反向的过度细化状态让状态空间爆炸。状态太细也有代价而且这个代价是隐性的。状态空间维度高了之后很多采样型算法需要指数级更多的数据才能覆盖到不同状态。而且状态越细每个状态被访问到的次数越少价值估计方差越大。我在做一个小型机器人导航实验时就吃过这个亏把几十个连续传感器特征原封不动塞进状态结果训练耗时翻了十倍还不一定收敛。实践经验是先做基线实验的时候状态能省则省确认基线可行之后再逐步加特征每次只加一个观察效果。千万不要一上来就堆砌特征。5.2 折扣因子与奖励设计最影响收敛的两个旋钮接下来是我认为 MDP 建模里最容易翻车的两个参数折扣因子 γ 和奖励函数 R。这两个东西连在一起决定了算法收敛的方向和速度。γ 的选择直接反映你对“远视程度”的假设。γ 太小比如 0.5算法会严重偏向即时奖励很多“先苦后甜”的策略学不出来γ 太接近 1比如 0.99虽然理论上更能找到长期最优但价值传播一步只衰减 1%导致前面几步的价值差异很小需要更多次迭代才能让差异显性化训练时长会明显拉长。我一般的经验值是短流程任务用 0.9-0.95长流程任务用到 0.99但需要配合更多的训练步数和更大的批大小。奖励设计的坑比 γ 更深。最常见的问题是“奖励泄漏”——给智能体一个目标却在奖励函数里加入了与目标无关的引导信息让它在实现目标前先学会了刷奖励。一位做推荐系统的朋友跟我说过他们公司早期的排序模型里奖励包含了“页面停留时长”结果系统学会了把用户引导到冗长而无意义的内容页停留很久点击率却一塌糊涂。这个案例后来成了团队内部“奖励函数不是指挥棒”的标准教材。还有一个我反复遇到的问题是奖励的数值尺度差异过大。如果中间奖励动辄加减几百而终极目标奖励只有 1那么价值更新会被中间奖励淹没算法几乎无视最终目标。相反如果终极奖励非常大中间奖励又显得可忽略不计学习会变得极端稀疏。设计奖励的第一原则是让所有奖励保持相近数量级并确保奖励值能真实区分目标达成程度。5.3 模型已知与模型未知别把 MDP 求解思路带错地方最后一个想说的是dynamic programming 和强化学习算法适用的场景完全不同很多人会把两者混淆。当你知道 MDP 的完整定义——概率表、奖励、折扣因子——时用动态规划可以精确求解。可现实中几乎没有人能拿到动能方程、光流场和传感器噪声分布的精确模型。所以绝大部分真实项目走的是免模型路线用试错采样估计价值函数或策略而不是直接求解贝尔曼方程。这个区别解释了一个让很多人困惑的现象为什么炼丹式的调参在强化学习里如此常见。因为一旦没有显式转移概率动态规划那套精确求解就失效了所有算法只能靠有限样本去近似真实期望每一步都有方差。你调的学习率、batch size、探索率本质都是在与这个方差做斗争。我每次做新项目时都会先问自己一件事我到底有没有这个环境的精确模型如果有直接动态规划或基于模型的方法精度高、数据效率好如果没有才轮到无模型算法。很多团队一上来就抢着上深度强化学习算法问也不问能不能先建立环境模型最后效果很差问题往往不在算法而在于信息利用方式不对。5.4 实践中的调试心得最后分享一点调试 MDP 求解代码的实用技巧。每次迭代之后打印出 V 的变化曲线这是判断算法是否正常的第一个信号。如果 V 来回震荡不收敛优先检查终止状态有没有被错误地纳入更新如果收敛值和你预期不符再检查转移概率的方向和奖励的数值符号。我调试时经常从确定性转移开始把噪声概率设为 0跑通之后再加入随机性这能快速定位是逻辑错误还是噪声带来的方差问题。再补一个看起来琐碎但实际很重要的点状态编号最好从 0 开始且保证连续这会让所有数组索引、矩阵运算都顺滑很多。一旦状态编号出现空洞或从 1 开始不仅很容易出现越界错误后续画图、调试的时候也会被这类低级问题反复绊住。我在项目里遇到过太多这一类错误多花两分钟设计好状态编码后面能省大量排错时间。附上这个 3 状态 MDP 的完整运行结果供大家验证自己的实现是否正确状态值迭代 V最优策略动作0-6.19向右1-0.86向右20.00终止从状态 1 出发最优策略是向右这个方向有 80% 概率直接进入终点得到 10虽然也有 20% 概率被噪声弹回状态 0但长远看仍然是收益期望最高的选择。这个小结论值得手动验算一遍验证一次之后你对 MDP 的直觉会比单纯看书深刻得多。我个人在实际操作中最大的体会是MDP 的数学框架看似简单但它逼着你把“目标是什么、环境如何响应、未来有多重要”这三件最基本的事情想清楚。很多后面看起来玄乎的强化学习算法问题归根到底都是这三件事的某一件没有定义好。如果你正在困惑一个强化学习项目为何学不出来回退一步重新审视你的状态定义、奖励函数和折扣因子通常答案就藏在这三个变量之中。