随机重置路径寻找：图路径上级联赌博机的路径级遗憾
研究背景与问题定义
在量子中继网络、闪电网络支付路由以及不可靠网格网络中的投递等场景中，智能体常需在已知有向图上寻找从源点到目标点的可靠路径，但每条边的成功概率未知且固定。每次执行路径时，若某条边失败，智能体将立即被重置回起点，并需重新开始新一轮尝试。这种“随机重置”问题被研究者称为 Stochastic Reset Pathfinding (SRP)，并首次被形式化为一个情节式学习问题。
核心发现：最优策略是开环的
SRP 的关键特性在于全局重置结构：任何边失败都会将智能体完全重置到源点，这意味着历史信息（已成功经过的边）对后续选择没有帮助。因此，最优策略并非依赖状态的自适应策略，而是开环策略——即智能体在每轮开始时固定一条路径，然后整条路径执行。这一性质将 SRP 问题归入组合级联赌博机框架，为后续算法设计提供了理论基础。
算法设计：Log-Dijkstra 元算法
研究者提出了一个名为 Log-Dijkstra 的元算法，其核心思想是利用对数变换将边成功概率转换为权重，再通过 Dijkstra 算法寻找最优路径。具体实现包括两种变体：
- PathUCB：基于上置信界算法，为每条边维护一个置信区间，选择对数权重下界最小的路径。
- PathTS：基于汤普森采样，从每条边成功概率的后验分布中采样，再选择对数权重最小的路径。
理论贡献：路径级遗憾界
主要理论成果是 PathUCB 的路径级遗憾界。不同于传统级联赌博机中基于单边遗憾的边界，该界将遗憾分解为每条次优路径的复杂度 (C(\pi))，该复杂度综合了路径中每条边的前缀可靠性和后缀可靠性。当图中源点到目标点路径数量为多项式级时，该边界比边级边界更紧，且能更好解释结构化图上的学习行为。
实验验证与建议
在量子网络、分层有向无环图、网格世界和随机图等多种域上的实验表明，PathTS 通常在实证表现上最优。然而，研究者也构造了一个对抗性实例，在该实例中 PathTS 无法收敛，这与已知的“组合汤普森采样在乘性奖励问题上的指数级障碍”一致。因此，作者推荐 PathTS 作为实践中的默认算法，同时提醒用户注意对抗性实例的存在。
总结与展望
SRP 问题的提出为处理重置型路径选择提供了严谨的数学框架，其算法可直接应用于量子密钥分发网络中的纠缠分发路线选择、闪电网络中的支付通道选择，以及灾难场景下不可靠通信网络的报文投递。未来工作可探索更复杂的重置模式（如部分重置）、边概率随时间变化的环境，以及与其他组合学习问题的交叉。