近日，一篇题为《随机重置路径寻找：图路径上级联赌博机的路径级遗憾》的论文被提交至arXiv。该研究由Guni Sharon等人完成，提出了一种全新的学习问题——随机重置路径寻找（Stochastic Reset Pathfinding, SRP），并对其进行了深入的理论与实验分析。
SRP定义在一个已知的有向图上，其中每条边具有未知但固定的成功概率。在每个情节（episode）中，智能体承诺一条从源点到目标点的路径，如果执行过程中任何一条边失败，智能体将被重置回源点。这一模型能够捕捉多种实际应用场景，例如量子中继网络中的纠缠分发、闪电网络（Lightning Network）中的支付路由，以及不可靠网状网络中的包裹投递。
论文的核心贡献之一在于揭示了SRP的全局重置结构使得最优策略是开环的（open-loop），即策略不依赖于执行历史。这一特性将SRP纳入组合级联赌博机（Combinatorial Cascading Bandit, CCB）框架。在此基础上，作者提出了一个Log-Dijkstra元算法，并实现了两种具体算法：基于置信上限（UCB）的PathUCB和基于汤普森采样（Thompson Sampling）的PathTS。
理论方面，论文的主要技术成果是为PathUCB推导了路径级的遗憾界。该界限通过每条次优路径的复杂度C(π)来分解遗憾，其中C(π)综合了路径中各边的前缀和后缀可靠性。这一界限与传统的边级CCB界限互补，并且在具有多项式多条源到目标路径的结构化图上提供更多信息。
实验部分，作者在量子网络、分层有向无环图（DAG）、网格世界和埃尔德什-雷尼图等领域进行了测试。结果支持了理论分析，并显示PathTS通常在所有测试算法中取得最佳经验性能。然而，作者也构造了一个对抗实例，在该实例中PathTS无法收敛，这与组合汤普森采样在乘法奖励问题上已知的指数级障碍一致。
基于这些发现，作者推荐将PathTS作为实际应用中的默认算法，但同时也提醒用户注意对抗实例的存在。这项研究为处理具有重置特性的路径规划问题提供了理论框架和实用工具，有望推动量子网络、支付路由等领域的算法设计。