随机重置寻路：图路径上级联强盗的路径级遗憾

arXiv:2607.15440v1 公告类型：新 摘要：我们引入随机重置寻路（SRP），这是一个已知有向图上的情景学习问题，具有未知的固定边成功概率。在每个情节中，代理都会提交到源到目标的路径，并且执行期间的任何边缘故障都会将其重置为源。 SRP 捕获量子中继器网络中的纠缠分布、闪电网络上的支付路由以及不可靠的网状网络中的交付等设置。我们表明，全局重置结构使最优策略开环，将 SRP 置于组合级联老虎机 (CCB) 框架内。我们提出了一种具有 UCB (PathUCB) 和 Thompson Sampling (PathTS) 实例化的 Log-Dijkstra 元算法。我们的主要技术成果是 PathUCB 的路径级遗憾界限，它通过结合每条边的前缀和后缀可靠性的每条路径复杂度 C(pi) 来分解次优路径的遗憾。该界限是边级 CCB 界限的补充，并且在具有多项式多个源到目标路径的结构化图上提供更多信息。量子网络、分层 DAG、网格世界和鄂尔多斯-仁义域的实验支持了该理论，并表明 PathTS 通常在测试的算法中实现了最佳的经验性能。然后，我们展示了一个 PathTS 无法收敛的对抗性实例，与乘法奖励问题上组合汤普森采样的已知指数阻碍一致。我们建议将 PathTS 作为实际默认值，同时警告存在对抗性实例。