📊 statistics

Bayesian learning for the stochastic shortest path problem

本文为随机最短路径问题提出了一种贝叶斯框架，该框架通过贝尔曼最优方程直接构建最优动作价值函数的后验信念，从而提供了一种比现有的基于时序差分的方法更具数据效率且具备不确定性感知能力的替代方案，同时解决了与似然松弛和不可识别性相关的挑战。

原作者： Chon Wai Ho, Sumeetpal S. Singh, Jiaqi Guo

发布于 2026-06-04

📖 1 分钟阅读☕ 轻松阅读

原作者： Chon Wai Ho, Sumeetpal S. Singh, Jiaqi Guo

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图在一条充满浓雾的巨大迷宫中，寻找一条最快、最安全的路径，以到达终点的宝箱。这就是随机最短路径 (Stochastic Shortest Path, SSP) 问题。你没有地图。每当你走一步（采取一个动作），你可能会获得奖励（比如发现线索），或者受到惩罚（比如撞到死胡同），并且你会到达一个新的位置（状态）。你的目标是通过试错法来学习最佳路线，但你希望高效地完成，以免在漫无目的的游荡中浪费时间。

这篇论文提出了一种更聪明的新方法，利用贝叶斯学习 (Bayesian Learning) 来学习这条路径。你可以把它想象成一种“通过信念进行学习”的系统。计算机不仅仅是在猜测最佳路径，它还维护着一个关于最佳路径可能性的“云团”（概率分布）。随着它收集的数据越来越多，这个云团会缩小并收缩，最终锁定在真实的最佳路径上。

以下是使用简单类比对他们方法的拆解：

1. 核心思想：学习“计分卡”

在标准的学习中，计算机通常尝试直接猜测一个动作的分数。这篇论文说：“让我们直接猜测计分卡（称为 $Q^*$ ）。”

计分卡： 想象一张巨大的电子表格，其中每个可能的移动在每个可能的房间里都有一个分数。这个分数代表了如果你从那里开始并完美执行后续所有操作，你最终能获得的总宝藏。
规则书 (Bellman Equations)： 有一条严格的数学规则（贝尔曼最优方程）规定：“一个动作的分数必须等于即时奖励加上下一个动作的最佳可能分数。”
创新点： 大多数现有方法试图通过以一种杂乱且随意的形式调整数字，来强迫它们的猜测符合这条规则。而这篇论文说：“让我们直接基于这条规则书来构建整个学习系统。”他们将规则书视为物理定律，数据必须遵守这一定律。

2. “流形”与“模糊云团”

这是技术性最强但也最有趣的部分。

完美世界 (The Manifold/流形)： 如果迷宫中的奖励非常明确（没有噪声），计算机对计分卡的信念并不会在三维空间中到处漂浮。相反，它会坍缩到该空间内的一张薄薄的平面上（即流形）。
- 类比： 想象你在纸上寻找一条画好的特定线条。如果你拥有完美的信息，你知道答案就在那条线上。你不需要观察整张纸，只需要观察那条线。在数学上，这很难计算，因为你是在尝试从一个“房间”里的“线条”中进行采样。
现实世界 (The Fuzzy Cloud/模糊云团)： 为了让数学计算更容易，作者们稍微“模糊化”了规则。他们说：“好吧，答案不必完全在直线上；它可以处于距离直线极小的范围内。”
- 类比： 与其在干草堆里找针，不如在一个小的、模糊的干草云里找针。这使得计算机使用（一种称为蒙特卡洛采样的方法）采样答案变得更加容易。

3. 陷阱：“不恰当”的路径

论文发现了一个由于使规则变得“模糊”而产生的棘手副作用。

问题： 在迷宫中，有些路径会让你陷入无限循环，永远无法到达宝藏。这些被称为不恰当策略 (improper policies)。
陷阱： 当作者为了简化数学计算而放宽规则时，他们无意中让计算机很容易相信这些“无限循环”的路径。
- 类比： 想象你正在教一个机器人走向一扇门。如果你给出的指令过于宽松，机器人可能会认为：“噢，我可以一直在走廊里绕圈子；这也是一个有效的计划！”数学表明，如果计算机不够小心，即使它已经看过了整个迷宫，它也可能会对这些无用的无限循环分配巨大的“信念”。
解决方法： 论文警告说，你必须非常小心地设置规则有多“模糊”。如果你把规则设得太模糊，机器人会被无限循环所迷惑；如果你设得太精确，数学计算又会变得无法解决。

4. 结果：优于竞争对手

作者们在名为 “深海” (Deep Sea) 的著名基准测试（一个数字迷宫，你必须在每一步选择向左还是向右以寻找宝藏）上测试了他们的方法。

数据效率： 他们的这种方法比其他流行的贝叶斯方法学得更快。它需要更少的尝试次数就能摸清地图。
准确性： 当他们观察“信念云团”时，他们的方法正确识别了最佳路径并忽略了错误的路径。其他方法有时会陷入对“无限循环”路径的错误相信，或者需要更长的时间才能收敛。
“金标准”： 他们甚至为较小规模的问题计算了精确答案（不使用模糊近似法），以证明他们的模糊近似法是一个很好的近似。

总结

这篇论文提出了一种让计算机在复杂且不确定的世界中学习最佳路径的新方法。

它直接建立在奖励运作的数学定律之上，而不是使用捷径。
它承认完美知识会产生一个“细线”的可能性空间，这难以计算，因此它使用“模糊云团”使其变得可处理。
它警告说这种“模糊性”可能会误导计算机，让它认为无用的无限循环是好的计划，因此必须仔细调整“模糊度”。
在测试中，这种方法比其他当前方法学得更快、更准确，证明了紧贴基本数学原理是值得的。

作者得出结论，虽然他们的方法很强大，但未来的工作需要找到更好的方法，让计算机学会忽略这些“无限循环”陷阱，而不必依赖于如此精细的参数调节。

技术摘要：随机最短路径问题的贝叶斯学习

1. 问题定义

本文研究了随机最短路径 (Stochastic Shortest Path, SSP) 问题，该问题被定义为一个具有吸收终止状态的无限时界、无折扣马尔可夫决策过程 (MDP)。与标准的有折扣 MDP 不同，SSP 形式 ( $\gamma = 1$ ) 要求存在一个唯一的、零奖励的吸收目标状态 ( $s_g$ )，并且至少存在一个“适当”策略（即从任何状态出发都能以概率 1 到达 $s_g$ 的策略）。

主要目标是学习最优动作价值函数 $Q^*$ ，它满足贝尔曼最优方程 (Bellman Optimality Equations, BOEs)。挑战在于 $Q^*$ 无法直接观测；只能通过交互观测到状态-动作-奖励三元组 $(s, a, r)$ 。作者旨在构建一个贝叶斯框架，以量化 $Q^*$ 的不确定性，并通过汤普森采样 (Thompson Sampling，即后验采样) 来促进探索与利用之间的权衡，且无需依赖现有贝叶斯强化学习 (RL) 文献中常见的非现实假设或权宜近似。

2. 方法论

2.1 通过贝尔曼方程构建似然函数

其核心方法论贡献是直接基于 BOEs 构建似然函数，而非使用随机逼近算法（如 Q-learning）或时序差分 (TD) 误差。

参数化： 最优价值函数由参数化函数 $Q_\theta$ 近似。
约束： 对于状态-动作对 $(s, a)$ ，期望奖励 $\bar{r}_{s,a}$ 必须满足 BOE： $\bar{r}_{s,a} = Q_\theta(s, a) - \mathbb{E}[\max_{a'} Q_\theta(S', a')]$ 。
似然： 作者定义了一个似然函数 $p(r_t | \theta, \psi, s_t, a_t)$ ，其中观测到的奖励 $r_t$ 被建模为确定性的期望奖励加上噪声。这约束了参数 $\theta$ 必须与观测到的 BOEs 一致。

2.2 处理确定性奖励与流形后验

当奖励是确定性（无噪声）时，会出现显著的理论挑战。在这种情况下，BOEs 对 $\theta$ 施加了严格的等式约束。

流形密度： $\theta$ 的后验分布从全参数空间坍缩到由 BOE 约束定义的低维流形上。
豪斯多夫测度 (Hausdorff Measure)： 作者利用相对于 豪斯多夫测度 的密度（定理 2）来刻画该后验分布，而非使用标准的勒贝格密度 (Lebesgue density)。这为无噪声奖励下的后验提供了严谨的数学描述。

2.3 似然松弛与近似

直接从流形密度中采样对于标准蒙特卡洛方法来说在计算上是不可行的。为了便于推理，作者提出了松弛似然的方法：

卷积： 将精确的似然函数与一个具有容差 $\epsilon$ 的核函数（例如高斯核或均匀核）进行卷积。
勒贝格密度： 这种松弛使流形“增厚”，从而产生一个具有标准勒贝格密度的后验分布，适用于 MCMC 采样。
权衡： 本文严谨地分析了这种松弛带来的后果。虽然它实现了可计算的采样，但也引入了不可识别性问题。具体而言，对于表格化参数化 (tabular parametrizations)，松弛后的似然可能会给对应于不当策略（never reach the goal 的策略）的参数集分配无限质量，而精确的后验分布则不会。

2.4 用于探索的后验采样

该框架利用汤普森采样 (Thompson Sampling，即后验采样) 进行探索。在每个回合中，从 $Q_\theta$ 的后验分布中采样一个策略（通过直接采样 $\theta$ 或计算策略的概率质量），并部署该策略直到到达目标或检测到不当循环。

3. 核心贡献

严谨的贝叶斯公式化： 本文为 SSP 提供了一个基于第一性原理的贝米斯公式化方案，直接从贝尔曼最优方程导出似然函数，避免了在基于 TD 的贝叶斯 RL 中常用的启发式似密函数。
流形刻画： 本文证明了对于确定性奖励，后验分布位于低维流形上，并提供了关于豪斯多夫测度的显式密度公式（定理 2）。
松弛与不可识别性的分析： 作者从数学上证明，将似然函数松弛为高斯核（以实现勒贝格密度）会产生特定的不可识别性问题：如果先验方差较大，后验分布可能会被不当策略所主导（定理 4）。这与精确后验形成对比，后者能正确排除不当策略。
表格后验推导： 对于具有高斯先验和松弛似然的表格化参数化，后验被证明是截断高斯分布的混合（命题 1）。
基准测试与实证验证： 本文引入了一个使用 "Deep Sea" 环境变体进行基准测试的协议，以将其方法与基于 TD 的贝叶斯方法（Bayes-TD, Bayes-TD-En, Bayes-TD-Max）进行比较。

4. 结果

4.1 理论发现

收敛性： 当松弛容差 $\epsilon \to 0$ 时，近似后验收敛于精确的流形后验。
不当策略的主导地位： 在存在不当策略的情况下，高斯先验结合松弛似然可能导致后验质量沿着对应于不当策略的方向“拉伸”，从而可能偏置最优动作的选择。通过减小 $\epsilon$ 或使用显式惩罚不当策略的先验可以缓解这一效应。

4.2 数值实验

实验在 Deep Sea 基准的变体（标准型、金字塔型和旋涡型环境）上进行：

数据效率： 所提框架 (Bayes-BR) 展示了比基于 TD 的贝叶斯方法更优越的数据效率，尤其是在 $\epsilon$ 较小（如 0.01）时。
收敛性： 在标准 Deep Sea 环境中（深度为 3），最优策略的后验概率迅速收敛至 1（仅需 8 个回合）。
多重最优解： 在具有多个最优策略的 "Deep Sea Pyramid" 变体中，后验正确地在所有最优策略之间均匀分布了质量。
不当策略： 在包含不当策略的 "Deep Sea Swirl" 变体中，只要 $\epsilon$ 足够小，该框架仍能成功恢复出最优策略类，尽管存在理论上的不当策略主导风险。
采样挑战： 研究指出，当 $\epsilon$ 非常小时（0.01），标准的哈密顿蒙特卡洛 (HMC) 在从松弛后验中有效采样方面表现挣扎，凸显了即使经过松弛，在流形附近采样的难度。

5. 意义与主张

本文声称其框架能够在 SSP 设置下忠实地量化不确定性，而不依赖于许多现有贝叶斯 RL 工作中存在的“不现实建模假设”或“权宜近似”（这些工作通常源于 Q-learning 更新）。

忠实性： 通过从 BOEs 导出似然函数，所得后验在理论上是基于 MDP 最优条件的。
对近似的洞察： 本研究对实践中常用的“松弛”步骤进行了批判性的数学分析。它揭示了虽然松弛使推理变得可行，但它从根本上改变了后验几何结构，如果管理不当，可能会导致选择不当策略。
基准测试： 作者提供了一个比较贝叶斯 RL 方法的新基准，表明其方法在 SSP 设置下比竞争性的基于 TD 的贝叶斯方法更具数据效率。

本文结论较为谦逊，承认虽然该框架是鲁棒的，但未来仍需设计能显式排除不当策略的先验，并开发更先进的采样方法来应对处理小 $\epsilon$ 值带来的挑战。