简介：面向机器学习与强化学习初学者的 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; % 状态转移 P：P{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在第一行第二列，执行动作“上”时nr=max(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时的经验参考。

4.1 gamma从0.9到0.99：长期收益的“眼光”换来多少迭代开销

gamma决定未来奖励的权重。一个直观解释是：V(s)=R(s)+γV(s_next)中，每往后推一步，贡献权重乘一次γ。gamma=0.9时，大约10步之外的奖励权重缩到0.35，30步之外基本可以忽略。gamma=0.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的误差没有改变动作排序，策略依然正确。所以theta=1e-3通常也能收敛到最优策略，只是中间多几轮反复。

theta=1e-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 gamma=1且环境中存在环路，策略评估死循环

现象：策略评估的内层while循环一直不退出，delta始终不小于theta，程序卡死或V值越算越大。

原因：gamma=1意味着不对未来折扣，如果策略在某个环路里转圈（比如沿着边界绕一圈回到起点），每步奖励都是-1，累计收益趋向负无穷。贝尔曼方程在这种情况下没有有限解，迭代自然不可能收敛。

解决：把gamma改成小于1的值，比如0.9到0.99。如果业务上确实不能折现，应该改用平均奖励准则（average reward MDP），而不是硬套折扣框架。排查时先在评估循环里加一个计数器，超过一定次数就break并打印V的变化趋势，V呈直线增长基本就是gamma=1加环路的问题。

5.3 状态空间稍大就内存爆炸：cell数组的边界

现象：状态数从16涨到5000，程序还没算几步就开始内存不足，或者运行极慢。

原因：很多人习惯把转移概率存成三维矩阵P(n_states, n_actions, n_states)，这四个维度一乘就是5000×4×5000=一亿个数。即使每个数只占8字节，也要800MB。这种稠密表示在状态规模超过1万时基本不可用。

解决：确定性环境用cell数组存单个索引，随机环境用稀疏矩阵存每行概率。更彻底的做法是把转移写成函数nxt=trans(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值”的解决办法，和这里的区别只在于用采样代替了查表。

我自己的习惯是：遇到一个决策优化问题，先用策略迭代在玩具环境上把转移和奖励的定义调对，再考虑换更快的算法。有一次我把奖励函数里负数写成了正数，策略迭代跑出来的路径全在绕远路，而值迭代对照一眼就看出了问题。先小后大、先看策略后信数字，这个习惯帮我省了不少时间。希望帮到你。

本文还有配套的精品资源，点击获取