网格世界：价值迭代 / 策略迭代可视化

使用方法

1. 选择算法：价值迭代每点一次“单步”做一轮同步扫描；策略迭代每点一次做一轮完整的“策略评估 + 策略改进”。
2. 运行：点击“运行”自动执行，直到收敛（价值迭代：最大变化 $\mathrm{\Delta }<{10}^{-4}$；策略迭代：策略不再变化）。
3. 编辑地图：选择“墙 / 终点 / 陷阱 / 清除”后点击格子。终点和陷阱是终止状态，可以设置奖励大小；还可以增减行列。修改地图或参数后价值会自动清零。
4. 读图：格子颜色表示价值（绿色为正、红色为负，越深绝对值越大），左上角小字是价值数值，箭头是贪心动作或当前策略。

环境设定

• 动作：上、右、下、左。以 $1-p$ 的概率按意图移动，各以 $p/2$ 的概率滑向两侧（$p$ 即“滑动概率”）；撞墙或出界则留在原地。
• 奖励：每走一步得到“每步奖励”，进入终点或陷阱时再得到该格的奖励；进入后回合结束，终止状态价值为 0。

价值迭代的更新（与 动态规划 教程一致）：

$$V_{k+1}(s)=\underset{a}{max}\sum _{s^{\prime }}p(s^{\prime }\mid s,a)[r(s,a,s^{\prime })+\gamma V_k(s^{\prime })]$$

策略迭代交替执行策略评估（反复应用 $V(s)\leftarrow \sum _{s^{\prime }}p(s^{\prime }\mid s,\pi (s))[r+\gamma V(s^{\prime })]$ 直到收敛）和策略改进（$\pi (s)\leftarrow \arg \underset{a}{max}Q(s,a)$）。初始策略为“全部向上”。

可以试试

• $\gamma$ 的作用：把 $\gamma$ 从 0.9 调到 0.5，左下角格子的价值从约 0.33 降到约 0.001，远离终点的格子几乎“看不到”终点；调到 0.99，价值传播得更远（左下角约 0.90），但价值迭代需要两百多轮扫描才能收敛。
• 滑动概率与风险：把滑动概率从 0.2 调到 0.4，紧挨陷阱的格子会改变策略：右上角陷阱左侧的格子不再向上走（向上时有一定概率滑进陷阱），而是先向左退开；陷阱正下方的格子从“向左”改为“向下”远离陷阱。这就是随机环境中“安全”与“最短”的权衡。
• 每步奖励为负：设为 −0.5，最下面一行的格子会选择一路向右直接跳进右下角的陷阱——与其慢慢走到终点、每步都被扣分，不如尽快结束回合。
• 每步奖励为正：设为 +0.2，几乎所有格子的四个动作都变得同样好，智能体没有任何动力去终点，只想永远留在场上（$0.2/(1-0.9)=2$ 大于终点奖励 1）。这是奖励设计不当的经典例子。
• 两种算法的对比：在默认地图上，策略迭代通常只需要几轮“评估 + 改进”就能收敛，而价值迭代需要几十轮扫描；但策略迭代每一轮内部的评估本身要扫描很多次（状态栏会显示扫描次数）。
• 墙与死胡同：用墙围出一个死胡同，观察里面格子的价值如何受出口距离影响。

验证方式

我们用 Node.js 对工具使用的算法模块做了检查：在默认地图（$\gamma =0.9$、滑动概率 0.2、每步奖励 0）上，价值迭代扫描 44 轮后（$\mathrm{\Delta }<{10}^{-10}$），与策略迭代（3 轮后收敛）得到的价值函数最大差异约为 ${10}^{-8}$，两者给出相同的策略。

相关教程

• 贝尔曼方程：价值函数满足的方程。
• 动态规划：策略迭代与价值迭代的推导和 Python 实现。
• 马尔可夫决策过程：状态、动作、转移概率与奖励。