简介面向机器学习与强化学习初学者的 MATLAB 策略迭代实现包围绕马尔科夫决策过程MDP建模与求解展开。压缩包基于 MDPtoolbox 提供完整可运行的策略迭代算法并附带值迭代、有限时域、线性规划求解等关联函数适合正在学习动态规划或准备上手强化学习实验的读者。包内共有 93 个文件核心为 33 个 m 脚本可直接调用和修改20 个 html 文档用于函数说明与使用教程18 个 dat 数据文件提供示例模型其余还包括 tex/PDF 文档、图片等辅助材料整体体积仅 2.32MB便于下载与本地调试。目前已有 312 人学习。通过这套资源读者可以在 MATLAB 环境中直观理解策略评估与策略改进的交替过程掌握策略迭代收敛到最优策略的完整实现思路同时随包附带的示例数据和可视化文档也能帮助快速定位每一步的状态值变化为后续扩展到更复杂的强化学习问题打下基础。1. MDP策略迭代入门强化学习第一个能算出最优策略的matlab程序Matlab里跑通一个MDP策略迭代是很多人强化学习启蒙的第一个里程碑。它解决的是这样一个决策问题在一个状态转移完全已知、奖励规则明确的有限环境中怎么为每个状态挑选动作让累计折扣收益最大。路径规划、库存控制、游戏AI里的不少小规模问题都能用它直接算最优策略。本文面向两类人正在学机器学习、课程设计拿到MDP策略迭代matlab作业的同学以及想快速验证一个决策方案却不想引入深度学习框架的工程师。读完你会有一个可以直接复现的网格世界策略迭代代码并且知道为什么策略迭代能保证收敛调参时哪些位置最容易翻车。2. 从MDP数学定义到策略迭代代码先立住框架再碰键盘策略迭代的代码量不大难的是先想明白它到底在算什么。很多同学拿到作业就急着写矩阵、写循环结果P矩阵的定义和奖励函数对不上号调试一晚上没头绪。所以先用两小节把MDP的结构和策略迭代的本质讲透再进入可直接抄的MATLAB实现。2.1 网格世界与MDP四元组把决策问题翻译成MATLAB数据结构策略迭代属于基于模型的动态规划方法。所谓基于模型就是状态转移概率P和环境奖励R都提前已知这和Q-learning、策略梯度靠采样估计有本质区别。策略迭代的适用场景非常明确你清楚知道每个动作会导致什么后果只是不知道选哪条路长期收益最大。如果环境模型未知第一件事应该是去做系统辨识或采集数据而不是直接套策略迭代。经典的教学环境是4×4网格世界16个格子智能体从左上角出发目标是右下角终点每走一步惩罚-1碰到边界就停在原地。动作集合是上下左右四个。用这个环境验证策略迭代有一个好处最优路径可以直接人工画出来任何误算都能一眼发现。我见过不少同学一上来就调gym环境复杂度高、状态编码绕结果算法有问题根本看不出来。数学上MDP由四元组(S, A, P, R)加上折扣因子γ定义。S和A用整数索引表示R定义为一个n_states×1的向量终止状态奖励直接设0。P则建议用cell数组P{s,a}存转移结果对确定性环境P{s,a}是一个整数表示从s执行动作a之后的下一个状态对随机环境P{s,a}应该放一个稀疏概率向量。为什么不用三维矩阵P(s,a,s)而是cell数组三个原因。第一cell数组天然按状态和动作分块调试时打印P{5,3}比切片P(5,3,:)直观得多。第二确定性环境下存储量从n×n×n的冗余变成n×|A|个整数内存完全不是一个量级。第三后续写策略评估和策略改进时代码结构是两层for循环加查表几乎不可能写错索引。这里有个容易被绕晕的概念价值函数V(s)在策略迭代里到底指什么。它指在给定策略π下从状态s出发一路上按π执行动作累计折扣奖励的期望。在网格世界里它就是“距离终点还要亏多少分”的一个负值度量。离终点越远V越负一旦策略选了一条不该走的路某个状态的V立刻会偏离合理范围。这正是策略评估阶段能暴露问题的地方。初始化和R时有个细节容易被忽略终止状态虽然不参与决策但必须保留在P的定义中所有动作都转移到自身。这能保证贝尔曼更新式V(s)R(s)γV(s_next)在迭代过程中不会访问空索引也等于把“到达终点后游戏结束”这个语义天然编码进方程。2.2 策略评估与策略改进一步迭代里藏着两个贝尔曼方程策略迭代的核心思想是两步交替给定一个策略π先算出这个策略下的长期价值函数V这是策略评估再拿着V对每个状态重新挑动作、更新策略这是策略改进。两步循环往复直到策略不再变化。策略评估用的是贝尔曼期望方程。对确定性环境方程化简为V(s)R(s)γV(s′)其中s′P{s,π(s)}。这是一个线性方程组可以直接解矩阵方程但工程上更常用迭代法把V初始化为零反复套用更新式直到相邻两次V的差值最大值小于阈值θ。迭代法代码简单、天然支持随机转移而且不需要矩阵求逆是这个场景下更稳的选择。策略改进用的是贝尔曼最优方程的思路。拿到V之后对每个状态s计算每个动作的动作价值Q(s,a)R(s)γV(P{s,a})然后取Q最大的动作作为新策略。这里关键的一件事是策略改进定理贪心选择后的新策略其价值不会差于旧策略每一步都保证性能单调上升。数学证明不展开直觉上因为V已经描述了旧策略的未来收益任何比V更大的单步选择只会让后续收益更好。既然策略空间是有限的——16个状态每个有4个动作策略总数是4^16≈43亿个——而改进过程每一步都在策略空间中单调移动策略迭代就必然在有限步内收敛。实际运行中收敛远快于理论上的极限小规模MDP通常迭代几十轮就能稳定。数值上有另一个常用变体modified policy iteration策略评估不等到θ完全收敛就提前进入策略改进做几轮迭代即可。这在状态空间大的时候能省大量时间后续章节的参数选择里我们会看到θ对收敛质量的实际影响。3. 用MATLAB跑通策略迭代完整可复现的网格世界代码现在进入可以直接照抄的部分。下面的代码分两个代码块第一段是环境定义第二段是策略迭代主循环。整体思路是先把网格世界翻译成两个MATLAB变量再在变量上做两层迭代。3.1 环境定义的MATLAB实现转移cell数组与奖励向量% 网格世界定义4x4状态1~16终止状态16 n_rows 4; n_cols 4; n_states n_rows * n_cols; n_actions 4; terminal 16; % 奖励函数 R(s)非终止状态每步 -1终止状态 0 R -ones(n_states, 1); R(terminal) 0; % 状态转移 PP{s, a} 执行动作 a 后的下一个状态索引 % 动作编号1上, 2下, 3左, 4右 P cell(n_states, n_actions); for s 1:n_states [r, c] ind2sub([n_rows, n_cols], s); for a 1:n_actions if s terminal P{s, a} terminal; % 终止状态是吸收态所有动作留在原地 continue; end nr r; nc c; if a 1, nr max(r - 1, 1); end % 上 if a 2, nr min(r 1, n_rows); end % 下 if a 3, nc max(c - 1, 1); end % 左 if a 4, nc min(c 1, n_cols); end % 右 P{s, a} sub2ind([n_rows, n_cols], nr, nc); end end这段代码的逻辑是用ind2sub把状态编号还原成行列坐标然后根据动作修改行列值越界就通过max/min钳位回边界。sub2ind把新的行列坐标重新编码为状态编号存进cell数组。最后一行P{s,a}sub2ind(...)是关键它把“物理移动”翻译成了“状态索引跳跃”。边界条件值得单独说。状态5在第一行第二列执行动作“上”时nrmax(1-1,1)1状态编号不变相当于原地停留。这种原地动作不代表“撞墙损失一步”的额外惩罚只是一个确定性转移结果。如果需求是撞墙还要额外扣分奖励函数就必须按(s,a)拆分不能只在R(s)里统一扣。3.2 策略评估、策略改进与主循环核心代码块逐行解释% 策略迭代参数 gamma 0.9; % 折扣因子 theta 1e-4; % 策略评估收敛阈值 max_iter 500; % 外层最大迭代次数 % 随机初始化策略每个状态随机选一个动作1~4 pi randi([1, 4], n_states, 1); pi(terminal) 1; % 终止状态不参与决策固定为动作1 fprintf(开始策略迭代...\n); for iter 1:max_iter % ---------- 1) 策略评估求当前策略下的 V ---------- V zeros(n_states, 1); while true delta 0; for s 1:n_states v_old V(s); s_next P{s, pi(s)}; V(s) R(s) gamma * V(s_next); delta max(delta, abs(V(s) - v_old)); end if delta theta break; end end % ---------- 2) 策略改进对每个状态贪心选动作 ---------- policy_stable true; for s 1:n_states if s terminal continue; % 终止状态没有决策空间跳过 end old_action pi(s); q zeros(n_actions, 1); for a 1:n_actions q(a) R(s) gamma * V(P{s, a}); end [~, best_action] max(q); pi(s) best_action; if best_action ~ old_action policy_stable false; end end % ---------- 收敛判断 ---------- if policy_stable fprintf(策略迭代在第 %d 轮收敛\n, iter); break; end end % 把策略显示成4x4网格方便人工核对 policy_grid reshape(pi, n_rows, n_cols); disp(最终策略1上 2下 3左 4右); disp(policy_grid);策略评估里用到了“原地更新”V(s)在同一个循环里被覆盖后更新的状态会用到新值。这和雅可比迭代相比收敛更快是高斯的赛德尔风格的更新且数学上仍然保证收敛到同一个不动点。delta记录本轮所有状态中最大的V变化量当这个变化小于θ时我们认为已经逼近真解。策略改进里q(a)的计算只有一行因为P{s,a}直接给出了下一个状态的索引不需要遍历转移概率。max(q)返回最大Q值和对应动作索引best_action就是改进后的策略。policy_stable初始为true只要有一个状态的动作被改变就置为false外层循环继续。收敛后reshape(pi,4,4)能把策略向量恢复成网格形状。我这里没有做方向旋转变换直接按MATLAB的列优先顺序展示。要说的是状态编号是按列扫的但网格世界的物理布局恰好和display矩阵一致——第一行是状态1、5、9、13所在的行看起来就是从左到右从上到下人工核对路径非常方便。4. 策略迭代参数怎么设折扣因子、收敛阈值和初始化策略的影响策略迭代跑通之后第一个问题往往是“这些参数怎么来的”。gamma、theta、max_iter、初始策略都会影响收敛速度和最终结果质量。下面这张表是我做小规模MDP时的经验参考。参数影响对象经验取值说明gamma0.9价值传播范围约10步小任务默认收敛快适合状态空间小的课程作业gamma0.99价值传播范围约100步需要长期规划的决策评估阶段迭代次数明显增加theta1e-4V的数值精度默认价值函数四位小数精度足够theta1e-6V的精度更高需要精确V时对策略本身影响很小属于过度收敛max_iter500外层循环保险丝500足够策略迭代理论上必收敛max_iter只是防止编码错误导致死循环4.1 gamma从0.9到0.99长期收益的“眼光”换来多少迭代开销gamma决定未来奖励的权重。一个直观解释是V(s)R(s)γV(s_next)中每往后推一步贡献权重乘一次γ。gamma0.9时大约10步之外的奖励权重缩到0.3530步之外基本可以忽略。gamma0.99时100步之外的权重还有0.37算法必须非常“远视”。这个差异在策略评估阶段特别明显。gamma越大未来奖励传播得越慢评估循环需要更多次迭代让信息从终点“倒灌”回起点。4×4网格世界这种小环境里感受不深换成20×20或者更大的地图gamma从0.9改成0.99评估时间可能翻几倍。课程作业如果没有特殊要求0.9够用如果问题本身要求长远决策比如库存补货、投资组合再提到0.99。gamma还影响策略的“胆子”。gamma较小时算法更偏好尽快拿到奖励的路径gamma较大时愿意绕路换取未来更大的累计收益。网格世界里如果所有奖励都是-1两条路径步数一样时gamma不影响最优策略但一旦有正奖励在远处gamma直接决定算法敢不敢绕路走过去。4.2 theta与最大迭代次数把收敛判据调到什么程度才算严谨theta是策略评估的停止阈值。theta越大评估精度越差V可能离真解还很远就进入了策略改进。这在策略迭代里不一定是坏事因为策略改进用的是Q值的相对大小只要V的误差没有改变动作排序策略依然正确。所以theta1e-3通常也能收敛到最优策略只是中间多几轮反复。theta1e-6则属于过度收敛。对4×4网格世界V值本身就在-5到0之间1e-6的精度意味着小数后六位都对得上而策略其实在小数后两位就已经确定了。实际工程里我一般用1e-4起步跑完看策略有没有震荡有震荡再收紧。max_iter纯粹是保护机制。策略迭代在有限策略空间里单调改进理论上必然比4^16次更快收敛。如果max_iter设成10000还是没退出说明代码逻辑出问题了不是参数问题。我会在max_iter循环结束后加一个warning打印出当前策略是否还有变化方便定位。初始策略对收敛速度的影响容易被低估。随机初始化需要多几轮策略改进来纠正错误决策如果初始策略是“全左”这种极端动作第一轮策略评估会把路径偏左导致V严重偏小随后改进阶段要花额外轮次把方向掰回来。比较稳的做法是初始策略选“朝着终点方向的动作”或者直接全部随机但把随机种子固定住便于复现调试。5. 策略迭代的典型踩坑记录四个翻车现场与处理方式策略迭代代码不长但翻车方式比想象中多。下面四条是我自己和带过的同学踩过的坑按“现象、原因、解决”的顺序写方便对照排查。5.1 终止状态参与策略改进导致策略反复横跳现象外层循环跑满max_iter都没退出打印策略发现某个状态通常是终点附近的动作一直在换每轮结果都不一样。原因终止状态被写进了策略改进循环。正常设计里终止状态代表游戏结束不需要决策但如果你给R(terminal)设置了一个绝对值很大的奖励且奖励和动作绑定比如不同动作给不同奖励终止状态下四个动作的Q值就会各不相同argmax每轮都可能选中不同动作策略永远无法收敛。解决策略改进循环里对终止状态直接continue跳过并把动作固定成1。我在3.2的代码里已经这样写了实际项目里也要养成这个习惯。检查招数也很简单打印策略时看终止状态是否一直在变变就是没跳过。5.2 gamma1且环境中存在环路策略评估死循环现象策略评估的内层while循环一直不退出delta始终不小于theta程序卡死或V值越算越大。原因gamma1意味着不对未来折扣如果策略在某个环路里转圈比如沿着边界绕一圈回到起点每步奖励都是-1累计收益趋向负无穷。贝尔曼方程在这种情况下没有有限解迭代自然不可能收敛。解决把gamma改成小于1的值比如0.9到0.99。如果业务上确实不能折现应该改用平均奖励准则average reward MDP而不是硬套折扣框架。排查时先在评估循环里加一个计数器超过一定次数就break并打印V的变化趋势V呈直线增长基本就是gamma1加环路的问题。5.3 状态空间稍大就内存爆炸cell数组的边界现象状态数从16涨到5000程序还没算几步就开始内存不足或者运行极慢。原因很多人习惯把转移概率存成三维矩阵P(n_states, n_actions, n_states)这四个维度一乘就是5000×4×5000一亿个数。即使每个数只占8字节也要800MB。这种稠密表示在状态规模超过1万时基本不可用。解决确定性环境用cell数组存单个索引随机环境用稀疏矩阵存每行概率。更彻底的做法是把转移写成函数nxttrans(s,a)用规则计算而不是查表。比如网格世界里trans就是在坐标上做加减根本不需要存矩阵。状态规模到百万级仍然能跑这就是基于函数的思想。5.4 奖励只用R(s)没建R(s,a)最优策略不合物理直觉现象策略能正常收敛但打印出来的最优路径和实际期望不一致。比如向上走比向下走更费电策略却总选向上。原因不同的动作代价可能不同但奖励函数只按状态编码成了R(s)-1。策略迭代在策略改进时计算的是q(a)R(s)γV(s_next)这个公式里根本没有动作信息四个动作的差额完全由V决定。如果向上、向下都是-1算法当然认为它们等代价。解决把奖励扩展成R(s,a)在网格世界里用n_states×n_actions矩阵存每个状态执行每个动作的奖励。策略改进的q(a)改为R_sa(s,a)γV(P{s,a})。改动不大但需要记住策略评估阶段也要同步改因为V的定义同样依赖动作奖励。这个问题很隐蔽因为策略看起来是收敛的只有和真实物理模型对照时才发现算错了。6. 策略迭代之后的进阶用值迭代验证再往无模型走做完了策略迭代我建议顺手做一件事写一个值迭代版本跑同一个网格世界把两边的V和策略对照一遍。值迭代代码更短逻辑也更“暴力”% 值迭代直接迭代价值函数不再显式维护策略 V zeros(n_states, 1); while true delta 0; for s 1:n_states q zeros(n_actions, 1); for a 1:n_actions q(a) R(s) gamma * V(P{s, a}); end v_new max(q); delta max(delta, abs(v_new - V(s))); V(s) v_new; end if delta theta break; end end [~, policy_from_value] max(reshape(cellfun((nexts) R gamma * V(nexts), P), n_states, n_actions), [], 2);对照验证的具体做法是跑完策略迭代之后用同样的gamma和theta跑值迭代比较两个V是否一致、两个策略是否一致。策略迭代和值迭代理论上收敛到同一个最优策略如果结果对不上问题多半出在奖励定义或者转移矩阵上。这是排查“策略看着合理但实际不对”最有效的手段。实际工程里用哪个我一般会看状态空间的大小。状态少、模型已知、需要解释最优路径时策略迭代更好用因为每轮迭代都能看到明确的策略变化和收敛轮次方便汇报状态多到评估循环成为瓶颈时值迭代每轮开销更小配合函数式转移能跑出更大的规模。再从策略迭代往Q-learning走时你会发现Q-learning其实就是“不知道P和R也要硬学Q值”的解决办法和这里的区别只在于用采样代替了查表。我自己的习惯是遇到一个决策优化问题先用策略迭代在玩具环境上把转移和奖励的定义调对再考虑换更快的算法。有一次我把奖励函数里负数写成了正数策略迭代跑出来的路径全在绕远路而值迭代对照一眼就看出了问题。先小后大、先看策略后信数字这个习惯帮我省了不少时间。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/30 16:10:11 · 阅读 1.2k MDP策略迭代入门：用MATLAB实现最优策略的强化学习算法
简介面向机器学习与强化学习初学者的 MATLAB 策略迭代实现包围绕马尔科夫决策过程MDP建模与求解展开。压缩包基于 MDPtoolbox 提供完整可运行的策略迭代算法并附带值迭代、有限时域、线性规划求解等关联函数适合正在学习动态规划或准备上手强化学习实验的读者。包内共有 93 个文件核心为 33 个 m 脚本可直接调用和修改20 个 html 文档用于函数说明与使用教程18 个 dat 数据文件提供示例模型其余还包括 tex/PDF 文档、图片等辅助材料整体体积仅 2.32MB便于下载与本地调试。目前已有 312 人学习。通过这套资源读者可以在 MATLAB 环境中直观理解策略评估与策略改进的交替过程掌握策略迭代收敛到最优策略的完整实现思路同时随包附带的示例数据和可视化文档也能帮助快速定位每一步的状态值变化为后续扩展到更复杂的强化学习问题打下基础。1. MDP策略迭代入门强化学习第一个能算出最优策略的matlab程序Matlab里跑通一个MDP策略迭代是很多人强化学习启蒙的第一个里程碑。它解决的是这样一个决策问题在一个状态转移完全已知、奖励规则明确的有限环境中怎么为每个状态挑选动作让累计折扣收益最大。路径规划、库存控制、游戏AI里的不少小规模问题都能用它直接算最优策略。本文面向两类人正在学机器学习、课程设计拿到MDP策略迭代matlab作业的同学以及想快速验证一个决策方案却不想引入深度学习框架的工程师。读完你会有一个可以直接复现的网格世界策略迭代代码并且知道为什么策略迭代能保证收敛调参时哪些位置最容易翻车。2. 从MDP数学定义到策略迭代代码先立住框架再碰键盘策略迭代的代码量不大难的是先想明白它到底在算什么。很多同学拿到作业就急着写矩阵、写循环结果P矩阵的定义和奖励函数对不上号调试一晚上没头绪。所以先用两小节把MDP的结构和策略迭代的本质讲透再进入可直接抄的MATLAB实现。2.1 网格世界与MDP四元组把决策问题翻译成MATLAB数据结构策略迭代属于基于模型的动态规划方法。所谓基于模型就是状态转移概率P和环境奖励R都提前已知这和Q-learning、策略梯度靠采样估计有本质区别。策略迭代的适用场景非常明确你清楚知道每个动作会导致什么后果只是不知道选哪条路长期收益最大。如果环境模型未知第一件事应该是去做系统辨识或采集数据而不是直接套策略迭代。经典的教学环境是4×4网格世界16个格子智能体从左上角出发目标是右下角终点每走一步惩罚-1碰到边界就停在原地。动作集合是上下左右四个。用这个环境验证策略迭代有一个好处最优路径可以直接人工画出来任何误算都能一眼发现。我见过不少同学一上来就调gym环境复杂度高、状态编码绕结果算法有问题根本看不出来。数学上MDP由四元组(S, A, P, R)加上折扣因子γ定义。S和A用整数索引表示R定义为一个n_states×1的向量终止状态奖励直接设0。P则建议用cell数组P{s,a}存转移结果对确定性环境P{s,a}是一个整数表示从s执行动作a之后的下一个状态对随机环境P{s,a}应该放一个稀疏概率向量。为什么不用三维矩阵P(s,a,s)而是cell数组三个原因。第一cell数组天然按状态和动作分块调试时打印P{5,3}比切片P(5,3,:)直观得多。第二确定性环境下存储量从n×n×n的冗余变成n×|A|个整数内存完全不是一个量级。第三后续写策略评估和策略改进时代码结构是两层for循环加查表几乎不可能写错索引。这里有个容易被绕晕的概念价值函数V(s)在策略迭代里到底指什么。它指在给定策略π下从状态s出发一路上按π执行动作累计折扣奖励的期望。在网格世界里它就是“距离终点还要亏多少分”的一个负值度量。离终点越远V越负一旦策略选了一条不该走的路某个状态的V立刻会偏离合理范围。这正是策略评估阶段能暴露问题的地方。初始化和R时有个细节容易被忽略终止状态虽然不参与决策但必须保留在P的定义中所有动作都转移到自身。这能保证贝尔曼更新式V(s)R(s)γV(s_next)在迭代过程中不会访问空索引也等于把“到达终点后游戏结束”这个语义天然编码进方程。2.2 策略评估与策略改进一步迭代里藏着两个贝尔曼方程策略迭代的核心思想是两步交替给定一个策略π先算出这个策略下的长期价值函数V这是策略评估再拿着V对每个状态重新挑动作、更新策略这是策略改进。两步循环往复直到策略不再变化。策略评估用的是贝尔曼期望方程。对确定性环境方程化简为V(s)R(s)γV(s′)其中s′P{s,π(s)}。这是一个线性方程组可以直接解矩阵方程但工程上更常用迭代法把V初始化为零反复套用更新式直到相邻两次V的差值最大值小于阈值θ。迭代法代码简单、天然支持随机转移而且不需要矩阵求逆是这个场景下更稳的选择。策略改进用的是贝尔曼最优方程的思路。拿到V之后对每个状态s计算每个动作的动作价值Q(s,a)R(s)γV(P{s,a})然后取Q最大的动作作为新策略。这里关键的一件事是策略改进定理贪心选择后的新策略其价值不会差于旧策略每一步都保证性能单调上升。数学证明不展开直觉上因为V已经描述了旧策略的未来收益任何比V更大的单步选择只会让后续收益更好。既然策略空间是有限的——16个状态每个有4个动作策略总数是4^16≈43亿个——而改进过程每一步都在策略空间中单调移动策略迭代就必然在有限步内收敛。实际运行中收敛远快于理论上的极限小规模MDP通常迭代几十轮就能稳定。数值上有另一个常用变体modified policy iteration策略评估不等到θ完全收敛就提前进入策略改进做几轮迭代即可。这在状态空间大的时候能省大量时间后续章节的参数选择里我们会看到θ对收敛质量的实际影响。3. 用MATLAB跑通策略迭代完整可复现的网格世界代码现在进入可以直接照抄的部分。下面的代码分两个代码块第一段是环境定义第二段是策略迭代主循环。整体思路是先把网格世界翻译成两个MATLAB变量再在变量上做两层迭代。3.1 环境定义的MATLAB实现转移cell数组与奖励向量% 网格世界定义4x4状态1~16终止状态16 n_rows 4; n_cols 4; n_states n_rows * n_cols; n_actions 4; terminal 16; % 奖励函数 R(s)非终止状态每步 -1终止状态 0 R -ones(n_states, 1); R(terminal) 0; % 状态转移 PP{s, a} 执行动作 a 后的下一个状态索引 % 动作编号1上, 2下, 3左, 4右 P cell(n_states, n_actions); for s 1:n_states [r, c] ind2sub([n_rows, n_cols], s); for a 1:n_actions if s terminal P{s, a} terminal; % 终止状态是吸收态所有动作留在原地 continue; end nr r; nc c; if a 1, nr max(r - 1, 1); end % 上 if a 2, nr min(r 1, n_rows); end % 下 if a 3, nc max(c - 1, 1); end % 左 if a 4, nc min(c 1, n_cols); end % 右 P{s, a} sub2ind([n_rows, n_cols], nr, nc); end end这段代码的逻辑是用ind2sub把状态编号还原成行列坐标然后根据动作修改行列值越界就通过max/min钳位回边界。sub2ind把新的行列坐标重新编码为状态编号存进cell数组。最后一行P{s,a}sub2ind(...)是关键它把“物理移动”翻译成了“状态索引跳跃”。边界条件值得单独说。状态5在第一行第二列执行动作“上”时nrmax(1-1,1)1状态编号不变相当于原地停留。这种原地动作不代表“撞墙损失一步”的额外惩罚只是一个确定性转移结果。如果需求是撞墙还要额外扣分奖励函数就必须按(s,a)拆分不能只在R(s)里统一扣。3.2 策略评估、策略改进与主循环核心代码块逐行解释% 策略迭代参数 gamma 0.9; % 折扣因子 theta 1e-4; % 策略评估收敛阈值 max_iter 500; % 外层最大迭代次数 % 随机初始化策略每个状态随机选一个动作1~4 pi randi([1, 4], n_states, 1); pi(terminal) 1; % 终止状态不参与决策固定为动作1 fprintf(开始策略迭代...\n); for iter 1:max_iter % ---------- 1) 策略评估求当前策略下的 V ---------- V zeros(n_states, 1); while true delta 0; for s 1:n_states v_old V(s); s_next P{s, pi(s)}; V(s) R(s) gamma * V(s_next); delta max(delta, abs(V(s) - v_old)); end if delta theta break; end end % ---------- 2) 策略改进对每个状态贪心选动作 ---------- policy_stable true; for s 1:n_states if s terminal continue; % 终止状态没有决策空间跳过 end old_action pi(s); q zeros(n_actions, 1); for a 1:n_actions q(a) R(s) gamma * V(P{s, a}); end [~, best_action] max(q); pi(s) best_action; if best_action ~ old_action policy_stable false; end end % ---------- 收敛判断 ---------- if policy_stable fprintf(策略迭代在第 %d 轮收敛\n, iter); break; end end % 把策略显示成4x4网格方便人工核对 policy_grid reshape(pi, n_rows, n_cols); disp(最终策略1上 2下 3左 4右); disp(policy_grid);策略评估里用到了“原地更新”V(s)在同一个循环里被覆盖后更新的状态会用到新值。这和雅可比迭代相比收敛更快是高斯的赛德尔风格的更新且数学上仍然保证收敛到同一个不动点。delta记录本轮所有状态中最大的V变化量当这个变化小于θ时我们认为已经逼近真解。策略改进里q(a)的计算只有一行因为P{s,a}直接给出了下一个状态的索引不需要遍历转移概率。max(q)返回最大Q值和对应动作索引best_action就是改进后的策略。policy_stable初始为true只要有一个状态的动作被改变就置为false外层循环继续。收敛后reshape(pi,4,4)能把策略向量恢复成网格形状。我这里没有做方向旋转变换直接按MATLAB的列优先顺序展示。要说的是状态编号是按列扫的但网格世界的物理布局恰好和display矩阵一致——第一行是状态1、5、9、13所在的行看起来就是从左到右从上到下人工核对路径非常方便。4. 策略迭代参数怎么设折扣因子、收敛阈值和初始化策略的影响策略迭代跑通之后第一个问题往往是“这些参数怎么来的”。gamma、theta、max_iter、初始策略都会影响收敛速度和最终结果质量。下面这张表是我做小规模MDP时的经验参考。参数影响对象经验取值说明gamma0.9价值传播范围约10步小任务默认收敛快适合状态空间小的课程作业gamma0.99价值传播范围约100步需要长期规划的决策评估阶段迭代次数明显增加theta1e-4V的数值精度默认价值函数四位小数精度足够theta1e-6V的精度更高需要精确V时对策略本身影响很小属于过度收敛max_iter500外层循环保险丝500足够策略迭代理论上必收敛max_iter只是防止编码错误导致死循环4.1 gamma从0.9到0.99长期收益的“眼光”换来多少迭代开销gamma决定未来奖励的权重。一个直观解释是V(s)R(s)γV(s_next)中每往后推一步贡献权重乘一次γ。gamma0.9时大约10步之外的奖励权重缩到0.3530步之外基本可以忽略。gamma0.99时100步之外的权重还有0.37算法必须非常“远视”。这个差异在策略评估阶段特别明显。gamma越大未来奖励传播得越慢评估循环需要更多次迭代让信息从终点“倒灌”回起点。4×4网格世界这种小环境里感受不深换成20×20或者更大的地图gamma从0.9改成0.99评估时间可能翻几倍。课程作业如果没有特殊要求0.9够用如果问题本身要求长远决策比如库存补货、投资组合再提到0.99。gamma还影响策略的“胆子”。gamma较小时算法更偏好尽快拿到奖励的路径gamma较大时愿意绕路换取未来更大的累计收益。网格世界里如果所有奖励都是-1两条路径步数一样时gamma不影响最优策略但一旦有正奖励在远处gamma直接决定算法敢不敢绕路走过去。4.2 theta与最大迭代次数把收敛判据调到什么程度才算严谨theta是策略评估的停止阈值。theta越大评估精度越差V可能离真解还很远就进入了策略改进。这在策略迭代里不一定是坏事因为策略改进用的是Q值的相对大小只要V的误差没有改变动作排序策略依然正确。所以theta1e-3通常也能收敛到最优策略只是中间多几轮反复。theta1e-6则属于过度收敛。对4×4网格世界V值本身就在-5到0之间1e-6的精度意味着小数后六位都对得上而策略其实在小数后两位就已经确定了。实际工程里我一般用1e-4起步跑完看策略有没有震荡有震荡再收紧。max_iter纯粹是保护机制。策略迭代在有限策略空间里单调改进理论上必然比4^16次更快收敛。如果max_iter设成10000还是没退出说明代码逻辑出问题了不是参数问题。我会在max_iter循环结束后加一个warning打印出当前策略是否还有变化方便定位。初始策略对收敛速度的影响容易被低估。随机初始化需要多几轮策略改进来纠正错误决策如果初始策略是“全左”这种极端动作第一轮策略评估会把路径偏左导致V严重偏小随后改进阶段要花额外轮次把方向掰回来。比较稳的做法是初始策略选“朝着终点方向的动作”或者直接全部随机但把随机种子固定住便于复现调试。5. 策略迭代的典型踩坑记录四个翻车现场与处理方式策略迭代代码不长但翻车方式比想象中多。下面四条是我自己和带过的同学踩过的坑按“现象、原因、解决”的顺序写方便对照排查。5.1 终止状态参与策略改进导致策略反复横跳现象外层循环跑满max_iter都没退出打印策略发现某个状态通常是终点附近的动作一直在换每轮结果都不一样。原因终止状态被写进了策略改进循环。正常设计里终止状态代表游戏结束不需要决策但如果你给R(terminal)设置了一个绝对值很大的奖励且奖励和动作绑定比如不同动作给不同奖励终止状态下四个动作的Q值就会各不相同argmax每轮都可能选中不同动作策略永远无法收敛。解决策略改进循环里对终止状态直接continue跳过并把动作固定成1。我在3.2的代码里已经这样写了实际项目里也要养成这个习惯。检查招数也很简单打印策略时看终止状态是否一直在变变就是没跳过。5.2 gamma1且环境中存在环路策略评估死循环现象策略评估的内层while循环一直不退出delta始终不小于theta程序卡死或V值越算越大。原因gamma1意味着不对未来折扣如果策略在某个环路里转圈比如沿着边界绕一圈回到起点每步奖励都是-1累计收益趋向负无穷。贝尔曼方程在这种情况下没有有限解迭代自然不可能收敛。解决把gamma改成小于1的值比如0.9到0.99。如果业务上确实不能折现应该改用平均奖励准则average reward MDP而不是硬套折扣框架。排查时先在评估循环里加一个计数器超过一定次数就break并打印V的变化趋势V呈直线增长基本就是gamma1加环路的问题。5.3 状态空间稍大就内存爆炸cell数组的边界现象状态数从16涨到5000程序还没算几步就开始内存不足或者运行极慢。原因很多人习惯把转移概率存成三维矩阵P(n_states, n_actions, n_states)这四个维度一乘就是5000×4×5000一亿个数。即使每个数只占8字节也要800MB。这种稠密表示在状态规模超过1万时基本不可用。解决确定性环境用cell数组存单个索引随机环境用稀疏矩阵存每行概率。更彻底的做法是把转移写成函数nxttrans(s,a)用规则计算而不是查表。比如网格世界里trans就是在坐标上做加减根本不需要存矩阵。状态规模到百万级仍然能跑这就是基于函数的思想。5.4 奖励只用R(s)没建R(s,a)最优策略不合物理直觉现象策略能正常收敛但打印出来的最优路径和实际期望不一致。比如向上走比向下走更费电策略却总选向上。原因不同的动作代价可能不同但奖励函数只按状态编码成了R(s)-1。策略迭代在策略改进时计算的是q(a)R(s)γV(s_next)这个公式里根本没有动作信息四个动作的差额完全由V决定。如果向上、向下都是-1算法当然认为它们等代价。解决把奖励扩展成R(s,a)在网格世界里用n_states×n_actions矩阵存每个状态执行每个动作的奖励。策略改进的q(a)改为R_sa(s,a)γV(P{s,a})。改动不大但需要记住策略评估阶段也要同步改因为V的定义同样依赖动作奖励。这个问题很隐蔽因为策略看起来是收敛的只有和真实物理模型对照时才发现算错了。6. 策略迭代之后的进阶用值迭代验证再往无模型走做完了策略迭代我建议顺手做一件事写一个值迭代版本跑同一个网格世界把两边的V和策略对照一遍。值迭代代码更短逻辑也更“暴力”% 值迭代直接迭代价值函数不再显式维护策略 V zeros(n_states, 1); while true delta 0; for s 1:n_states q zeros(n_actions, 1); for a 1:n_actions q(a) R(s) gamma * V(P{s, a}); end v_new max(q); delta max(delta, abs(v_new - V(s))); V(s) v_new; end if delta theta break; end end [~, policy_from_value] max(reshape(cellfun((nexts) R gamma * V(nexts), P), n_states, n_actions), [], 2);对照验证的具体做法是跑完策略迭代之后用同样的gamma和theta跑值迭代比较两个V是否一致、两个策略是否一致。策略迭代和值迭代理论上收敛到同一个最优策略如果结果对不上问题多半出在奖励定义或者转移矩阵上。这是排查“策略看着合理但实际不对”最有效的手段。实际工程里用哪个我一般会看状态空间的大小。状态少、模型已知、需要解释最优路径时策略迭代更好用因为每轮迭代都能看到明确的策略变化和收敛轮次方便汇报状态多到评估循环成为瓶颈时值迭代每轮开销更小配合函数式转移能跑出更大的规模。再从策略迭代往Q-learning走时你会发现Q-learning其实就是“不知道P和R也要硬学Q值”的解决办法和这里的区别只在于用采样代替了查表。我自己的习惯是遇到一个决策优化问题先用策略迭代在玩具环境上把转移和奖励的定义调对再考虑换更快的算法。有一次我把奖励函数里负数写成了正数策略迭代跑出来的路径全在绕远路而值迭代对照一眼就看出了问题。先小后大、先看策略后信数字这个习惯帮我省了不少时间。希望帮到你。本文还有配套的精品资源点击获取