最近几年但凡做强化学习入门，不管是课程设计还是自己练手，十个人里有八个都会碰一次"用Q-learning走迷宫"。这个题目我也带人做过好几轮，说实话，它确实是强化学习里最容易讲清楚、最容易出效果、也最容易埋坑的一个Demo。标题里"随机生成的方形迷宫""ε-greedy策略""Matlab实现"这三个关键词放在一起，基本就锁定了这是一个从零搭建、训完还要能跑出路径的完整小项目。
这篇东西我按自己实际做过的流程来写，不绕弯子。先讲清楚为什么这套组合能解决迷宫问题，再把随机迷宫的生成、状态建模、Q表更新、参数调节全部拆开，最后把我在Matlab里踩过的坑和排查思路列成速查表。无论你是刚接触强化学习，还是已经跑通了一点基础代码但路径总是不理想，照着这个思路改参数、改奖励、改迷宫生成方式，基本都能得到一个能看的结果。
1. 为什么偏偏是Q-learning和ε-greedy
1.1 迷宫问题的本质是序列决策问题
方形迷宫不管怎么随机生成，最后都可以抽象成一张网格图。Agent在格子上移动，每一步只能往上下左右走，遇到墙就不能走。目标是从起点走到终点。这件事的本质就是：在未知或部分未知的环境里，做出一个连续的动作序列，让累积奖励最大。
用强化学习的语言翻译一遍：状态就是当前所在的格子，动作就是上下左右四个方向，奖励规则由你自定义，策略就是把每个状态映射到动作的规则。这样一个网格迷宫天然就是离散状态、离散动作、有限步数的序列决策问题。而这恰好是Q-learning最舒服的适用场景，因为它本来就基于表格存储Q值，状态和动作都少时，一张Q表就能覆盖所有情况。
1.2 Q-learning是tabular方法里最稳的选择
迷宫场景下你可以选很多算法，比如Sarsa、DQN、策略梯度，但大多数时候我会先给Q-learning。原因很简单：状态数可控，一个N×N的迷宫也就N²个状态，每个状态4个动作，Q表大小是N²×4。这个规模在Matlab里直接用矩阵存就行，不需要神经网络，不需要GPU，不需要复杂的回放缓冲区。训练速度快，代码逻辑直白，出了问题也容易排查。
而且Q-learning是异策略算法，它的更新用的是目标策略下的最大Q值。也就是说，它在探索过程中学到的东西，理论上可以收敛到最优策略，不受当前探索动作的干扰。迷宫这种确定性环境里，Q-learning的收敛性表现很好，实测下来比Sarsa更激进一点，路径往往能更快逼近最短路线。
1.3 ε-greedy解决的是探索与利用的平衡
如果一直选Q值最大的动作，Agent会很快陷入局部最优，比如在某个死胡同附近反复走同一条路，永远不会发现另一条更短的通道。如果一直随机选动作，Agent永远在乱逛，Q表得不到有效更新。
ε-greedy的思路很朴素：以ε的概率随机选择动作，以1-ε的概率选择当前Q值最大的动作。训练前期ε设得高一点，让Agent多探索；训练后期ε降下来，让Agent更多利用已经学到的经验。配合一个衰减系数，就能实现从"乱试"到"稳走"的自然过渡。标题里特意点出ε-greedy，说明这个项目不是单纯跑通Q-learning，而是希望你把探索策略也当做一个可调的核心变量来对待，这点我在后面参数部分会重点展开。
2. 随机方形迷宫的生成与建模细节
2.1 先说清楚"随机生成"的坑
很多初学者一上来就生成一个随机0/1矩阵，0是通路、1是墙，结果训练了半天发现Agent永远到不了终点。原因不是Q-learning没学好，而是迷宫本身就不连通，起点和终点之间压根没有通路。
所以随机生成迷宫的核心不是"随机"，而是"随机但有解"。我常用两种做法。第一种是随机铺墙再用广度优先搜索检查连通性，不连通就撤销这面墙。第二种是用DFS回溯直接生成一个完美迷宫，天然保证任意两点之间都有唯一通路。前者实现简单，适合快速实验；后者生成的迷宫更有"迷宫感"，通道曲折、死胡同多，也更考验强化学习算法。
两种方法我都用过，给个对比：
| 生成方式 | 实现难度 | 迷宫特点 | 适合场景 |
|---|---|---|---|
| 随机铺墙+BFS校验 | 低 | 通道比较松散，死胡同较少 | 快速验证算法，调参数阶段 |
| DFS回溯完美迷宫 | 中 | 通道曲折，死胡同多，路径唯一 | 展示效果，测试算法收敛能力 |
2.2 随机铺墙加连通性校验的实现
用Matlab写第一种方法比较快。先生成全0矩阵，起点和终点固定为通路，然后随机选一些格子放墙，每放一堵就BFS检查一次起点能否到达终点，如果不能就撤销。这个思路本质上是"构造后验证"，简单粗暴但可靠。
function maze = genMazeWithCheck(n, wallRatio) maze = zeros(n, n); % 随机铺墙 total = n * n; numWalls = floor(total * wallRatio); idx = randperm(total, numWalls); for k = 1:numWalls [r, c] = ind2sub([n, n], idx(k)); if (r == 1 && c == 1) || (r == n && c == n) continue; end maze(r, c) = 1; if ~isConnected(maze, n) maze(r, c) = 0; % 破坏连通性就撤销 end end end function ok = isConnected(maze, n) visited = false(n, n); queue = [1, 1]; visited(1, 1) = true; head = 1; while head <= size(queue, 1) r = queue(head, 1); c = queue(head, 2); head = head + 1; dirs = [-1 0; 1 0; 0 -1; 0 1]; for k = 1:4 nr = r + dirs(k, 1); nc = c + dirs(k, 2); if nr >= 1 && nr <= n && nc >= 1 && nc <= n ... && ~visited(nr, nc) && maze(nr, nc) == 0 visited(nr, nc) = true; queue(end + 1, :) = [nr, nc]; end end end ok = visited(n, n); endwallRatio我一般取0.2到0.35，太大容易生成过程反复撤销，效率变低；太小迷宫几乎全是通道，看起来不怎么像迷宫。
2.3 DFS回溯生成完美迷宫
第二个方法更有意思。用一个奇数尺寸的矩阵表示迷宫，比如(2N+1)×(2N+1)，外围全是墙，内部格子之间用墙隔开。从起点格子开始，随机挑一个未访问的相邻格子，打通它们之间的墙，然后递归继续。这样生成的迷宫没有环，任意两个格子之间只有一条通路。
Matlab里用迭代栈写DFS会比递归稳妥，避免递归层数太深导致栈溢出。核心体会是：不要试图在原始的N×N网格上直接打通墙，因为那样很难处理"两个格子之间隔着墙"的表达。改成奇数尺寸矩阵，让每个通路格子周围都自然围着一圈墙，打通时只需要把中间的墙置0，逻辑非常干净。
function maze = genPerfectMaze(N) % 尺寸为 2N+1 maze = ones(2*N + 1, 2*N + 1); % 内部格子全部置为通路 maze(2:2:end-1, 2:2:end-1) = 0; visited = false(N, N); stack = [1, 1]; visited(1, 1) = true; dirs = [-1 0; 1 0; 0 -1; 0 1]; while ~isempty(stack) r = stack(end, 1); c = stack(end, 2); candidates = []; for k = 1:4 nr = r + dirs(k, 1); nc = c + dirs(k, 2); if nr >= 1 && nr <= N && nc >= 1 && nc <= N && ~visited(nr, nc) candidates(end + 1, :) = [nr, nc, k]; end end if isempty(candidates) stack(end, :) = []; else pickIdx = randi(size(candidates, 1)); nr = candidates(pickIdx, 1); nc = candidates(pickIdx, 2); k = candidates(pickIdx, 3); % 打通对应墙 wallR = 2*r - 1 + dirs(k, 1); wallC = 2*c - 1 + dirs(k, 2); maze(wallR, wallC) = 0; visited(nr, nc) = true; stack(end + 1, :) = [nr, nc]; end end % 开入口和出口 maze(2, 1) = 0; maze(2*N, 2*N + 1) = 0; end这个生成的迷宫因为是奇数尺寸，Q-learning的状态空间不是简单N×N了，而是(2N+1)²，训练规模略大，但效果很好。如果只是交作业或快速复现，第一种就够了；如果是想真正展示算法能力，第二种更出彩。
2.4 状态、动作和奖励的建模要点
状态我一般直接用线性索引，也就是把二维坐标(r, c)映射成标量state = (r-1)*n + c。这样Q表就是一个n²×4的矩阵，Matlab索引和更新都方便。动作定义成1到4，对应上、下、左、右。从状态反推坐标用ind2sub，更新后用sub2ind转回索引，不会出错。
奖励设计是决定路径质量的关键。不要只给终点正奖励，那样Agent虽然能到终点，但可能绕很远的路。我常用的奖励方案是：
- 到达终点：+10
- 撞墙：-1，留在原地
- 每走一步：-0.1，用来惩罚绕路
那个每步-0.1的作用很多人忽略，但它非常关键。没有它，Agent对路径长短无感，只要最终能到达终点就满意，走500步和走50步没区别。有了它，Q-learning才会自己去找更短的路径。这个细节，基本能决定你的Agent走出来的是一条正常路线还是一条龟速瞎逛路线。
3. Q-learning核心逻辑与Matlab代码实现
3.1 Q表初始化与五个关键参数
Q表直接zeros初始化就行，不需要随机。有一点要注意：如果Q表全零，而奖励全为正，Agent会倾向于"先试所有动作再收敛"；如果奖励有负值，全零初始化本身就带着乐观偏差，会鼓励探索。迷宫问题里我倾向于全零初始化，配合ε-greedy探索，效果很好。
训练前先把参数列清楚，我惯用的一组初始值：
| 参数 | 含义 | 推荐值 | 调节直觉 |
|---|---|---|---|
| alpha | 学习率 | 0.1~0.3 | 太大震荡，太小龟速 |
| gamma | 折扣因子 | 0.9~0.99 | 越大越看重远期奖励 |
| epsilon | 初始探索率 | 0.8~1.0 | 前期必须充分乱走 |
| epsMin | 最小探索率 | 0.01~0.1 | 防止后期永远在乱走 |
| decay | ε衰减系数 | 0.99~0.995 | 衰减越快，后期越保守 |
gamma这个值你细品一下：它决定了未来奖励折算到当前的价值。迷宫问题里最终奖励只有终点那一次+10，如果gamma太小，比如0.5，终点奖励传递不了几步就衰减没了，Agent根本学不到"往终点方向走"这件事。我一般不低于0.9，N越大越要靠近0.99，因为路径更长，奖励往回传递的步数也更多。
3.2 训练主循环与Q值更新
Q-learning的更新公式是：
Q(s,a) ← Q(s,a) + α × [r + γ × maxₐ'Q(s',a') - Q(s,a)]
理解这个公式的诀窍是看中括号里那一坨。r是当前动作拿到的即时奖励，γ×maxₐ'Q(s',a')是下一步状态里所有动作最大Q值的折现，两者加一起代表"当前动作实际能带来的长期价值"。再减去原来的Q(s,a)，就是这次更新要修正的误差。乘上α，表示只修正一点点，不让单次经验把Q值彻底改写。
主循环结构很直白：每个episode从起点出发，按ε-greedy选动作，执行动作拿到下一个状态和奖励，更新Q值，直到到达终点或者超过单局步数上限。一个episode结束之后，把ε衰减一次。
n = 9; maze = genMazeWithCheck(n, 0.3); numStates = n * n; numActions = 4; Q = zeros(numStates, numActions); alpha = 0.2; gamma = 0.95; eps = 0.9; epsMin = 0.05; decay = 0.995; episodes = 3000; maxSteps = 500; startState = 1; goalState = n * n; for ep = 1:episodes state = startState; done = false; for step = 1:maxSteps if rand < eps action = randi(numActions); else [~, action] = max(Q(state, :)); end [nextState, reward, done] = stepOnce(maze, state, action, goalState, n); Q(state, action) = Q(state, action) + alpha * ... (reward + gamma * max(Q(nextState, :)) - Q(state, action)); state = nextState; if done break; end end eps = max(epsMin, eps * decay); end3.3 step函数：边界、撞墙和奖励
stepOnce函数负责把"动作"变成"下一个状态和奖励"。最容易写错的地方就是撞墙处理。有些写法是Agent撞墙后直接结束episode，或者给很大的负奖励，这会让Agent变得极其畏缩，停在起点不敢动。我建议撞墙后状态不变、只给一个较小的负惩罚，让Agent知道"这条路不通"但不用过度恐惧。
边界处理要看清楚：Matlab里数组索引从1开始，所以r=1时不能往上走，c=1时不能往左走，r=n时不能往下，c=n时不能往右。边界、墙、终点这三个条件都要判断，顺序别乱。
function [ns, reward, done] = stepOnce(maze, state, action, goalState, n) [r, c] = ind2sub([n, n], state); dirs = [-1 0; 1 0; 0 -1; 0 1]; % 上、下、左、右 nr = r + dirs(action, 1); nc = c + dirs(action, 2); if nr < 1 || nr > n || nc < 1 || nc > n || maze(nr, nc) == 1 ns = state; reward = -1; done = false; return; end ns = sub2ind([n, n], nr, nc); if ns == goalState reward = 10; done = true; else reward = -0.1; done = false; end end3.4 训练完怎么把路径画出来
训练结束后，从起点开始，每一步都选Q值最大的动作，直到到达终点。这里要加一个步数上限，防止Q表没收敛时陷入死循环。路径可视化可以用plot在imagesc画的迷宫图上叠加，效果比较直观。
function path = extractPath(Q, n, startState, goalState, maxSteps) path = startState; state = startState; for step = 1:maxSteps [~, action] = max(Q(state, :)); dirs = [-1 0; 1 0; 0 -1; 0 1]; [r, c] = ind2sub([n, n], state); nr = r + dirs(action, 1); nc = c + dirs(action, 2); if nr < 1 || nr > n || nc < 1 || nc > n break; end state = sub2ind([n, n], nr, nc); path(end + 1) = state; if state == goalState break; end end end % 绘图 figure; imagesc(maze); colormap(gray); axis square; hold on; [pr, pc] = ind2sub([n, n], path); plot(pc, pr, 'r-', 'LineWidth', 2);如果希望看训练过程，而不是只看最终路径，可以在每个episode里记录该episode是否到达终点，以及到达终点所需的步数，画两条曲线。到达终点后步数逐渐下降，基本就是收敛曲线了。
4. 参数调试经验：收敛速度与路径质量的平衡
4.1 五个参数的调节顺序
参数不要一起乱调。我习惯的调节顺序是：先定奖励，再调gamma，然后调epsilon衰减，最后微调alpha。
奖励决定学习信号的质量，这个错了后面全白搭。比如你发现Agent到了终点附近还绕来绕去，说明正奖励不够突出，或者步数惩罚太弱。把终点奖励加到20，每步惩罚从-0.1改成-0.2，路径立刻会收紧。
gamma决定了远期奖励能不能传回来。迷宫越大路径越长，gamma越要往0.99靠。一个9×9迷宫用0.95没问题，换成21×21的完美迷宫，0.95就不太够了，终点奖励传到起点附近已经衰减得没多少，Agent前期完全不知道该往哪走。
epsilon衰减最容易被忽视。我见过很多同学把epsilon固定成0.1，结果Agent从头到尾都在利用，很少探索，一旦初始路径不是最优就永远学不好。正确的做法是让epsilon从接近1开始，每轮乘一个接近1的系数，比如0.995，让探索率缓慢下降。3000个episode跑完，epsilon大约从0.9降到0.9×0.995^3000≈0.019，刚好落在0.05以下的水平。
alpha我反而放在最后调，因为它对最终性能的影响相对小。0.1和0.3在迷宫这种稳定环境下都能收敛，只是收敛速度有差异。如果你看到Q值反复横跳，曲线不光滑，把alpha调小一点就行。
4.2 训练过程中怎么判断收敛
不要只盯着一开始的步数曲线看。前几百个episode里，可能Agent大部分时间都到不了终点，步数曲线全是上限值，这很正常。关键看两个指标：一是到达终点的成功率是否接近100%，二是成功时的平均步数是否稳定在一个低位不再下降。
我有一次跑一个11×11的完美迷宫，前600个episode成功率不到三成，步数曲线也乱跳。当时差点想放弃，后来把epsilon衰减调慢到0.997，多跑了2000个episode，成功率逐渐冲到95%以上，平均步数也从两百多降到五十几。强化学习训练就像熬汤，前面看着没动静，其实Q表一直在积累信息，等到了临界点，曲线就突然往下掉。要有耐心。
4.3 我在这个项目上踩过的几个坑
第一个坑：撞墙后直接把episode结束。这样Agent会疯狂撞墙然后快速结束，Q表里撞墙的教训被不断强化，结果Agent变得畏手畏脚，宁可原地不动也不往前探索。正确处理是撞墙留在原地，只给一点惩罚，继续下一步。
第二个坑：给了太大的正奖励，比如100，又把gamma设成0.99，导致Q值爆炸式增长。这不是发散，是数值范围太大导致可视化时Q表差异不明显，路径提取时容易被微小波动干扰。正奖励不需要很大，10就够了。
第三个坑：路径提取时没有步数上限。Q表没完全收敛时，贪心策略可能在一个环里反复循环，比如从A到B到C再到B，肉眼看着路径在打转。加一个maxSteps保护，提取不到终点就提示"未收敛"，不要硬画。
第四个坑：随机迷宫生成后没有保存。如果你每次运行都重新生成迷宫，训练结果不可复现，调参时没法对比。建议把迷宫的随机种子固定下来，或者把maze矩阵存成.mat文件。我通常就是rng(1)固定随机种子，这样每次跑都是同一个迷宫，方便对比参数效果。
5. 常见问题排查与扩展思路
5.1 失败模式速查表
我把实际调试中遇到的典型问题整理成一张表，方便你对照排查：
| 现象 | 可能原因 | 处理办法 |
|---|---|---|
| Agent一直撞墙不敢走 | 撞墙惩罚过重或撞墙后结束episode | 撞墙留在原地，惩罚设为-1 |
| 能到终点但路径绕远 | 步数惩罚太弱 | 把每步-0.1改成-0.2或-0.5 |
| 必须跑很多episode才开始收敛 | epsilon衰减太快 | decay从0.99改成0.995 |
| 最终路径一直在打转 | Q表未收敛或路径提取没上限 | 增加episode，提取时加maxSteps |
| Q值曲线剧烈震荡 | alpha过大 | 从0.3降到0.1 |
| 迷宫生成后无解 | 随机铺墙没做连通性校验 | 用BFS校验或换DFS生成 |
| 训练稳定但可视化闪烁 | 每episode都重绘 | 只绘最终路径或每隔100轮绘一次 |
5.2 从方形迷宫到更复杂的强化学习场景
这个项目做完之后，往上走的路其实很清晰。一个是换算法，把Q-learning换成Sarsa，对比一下两者在探索策略不同时的表现差异；再往上就是DQN，把Q表替换成神经网络，状态输入加一点迷宫的局部感知信息，就能处理更大的地图。
另一个方向是改环境。把方形迷宫换成带移动障碍的动态迷宫，或者把离散格子改成连续坐标，奖励函数设计会完全不一样。我在实际工程里接触过的路径规划问题，很多本质上都是迷宫问题的变形：机器人避障、仓储拣货路径、游戏寻路。Q-learning在这些场景里当然不是最终答案，但它的建模思路是你理解更复杂算法的一块很好的跳板。
我个人在做完这个项目后的体会是：强化学习入门的瓶颈不在算法公式有多难，而在你能不能把一个具体问题干净地建模成状态、动作、奖励三个要素。迷宫这个题目刚好能逼着你把这三件事想明白。你也别急着把代码里加一堆花哨的东西，先把Q表更新、epsilon衰减、奖励设计这三件事跑透，后面再扩展就顺很多。
如果你也正在折腾这个题目，我最后再提醒一句：多花点时间在奖励设计和迷宫生成上，这两个地方是最不显眼但影响最大的。Q-learning代码本身半小时就能写完，但一个看起来很简单的撞墙惩罚，就可能让你的Agent从"傻站在原地"变成"果断绕路"。调参的过程虽然磨人，但每一步都能看得见反馈，这大概就是这个项目最迷人的地方了。
