针对图路径上的随机重置问题，提出新型路径级学习算法，提升复杂网络中可靠路径探索效率。
Stochastic Reset Pathfinding: Path-Level Regret for Cascading Bandits over Graph Paths
- 设计基于路径选择的元算法Log-Dijkstra，结合UCB与Thompson采样进行路径探索。
- 理论证明路径级后悔上界，关键指标为每条路径的前缀与后缀可靠性组合复杂度。
- 实测在量子网络等场景表现优异，推荐使用PathTS但需注意对抗性案例下的收敛风险。
我们提出随机重置路径寻优（SRP），一种在已知有向图上进行周期性学习的问题，其中边的成功概率未知且平稳。每轮中，智能体选定一条从起点到终点的路径，执行过程中任意边失败将导致状态重置至起点。该模型适用于量子中继网络中的纠缠分发、闪电网络支付路由以及不可靠网格网络中的数据传输等场景。我们发现全局重置结构使得最优策略为开环形式，因此将SRP归入组合级联强化学习（CCB）框架。本文提出一种名为Log-Dijkstra的元算法，并分别实现基于UCB（PathUCB）与Thompson采样（PathTS）的版本。主要技术成果是为PathUCB建立了路径级后悔上界，该上界通过每条路径的复杂度系数C(π)分解子优路径的后悔值，该系数结合了各边的前缀与后缀可靠性。该边界与边级CCB边界互补，在具有多项式数量源-目标路径的结构化图上更具信息量。在量子网络、分层有向无环图、网格世界及Erdos-Renyi图上的实验验证了理论结果，表明PathTS在测试算法中通常取得最佳实证性能。然而，我们进一步构造了一个对抗性实例，显示PathTS在此类情况下无法收敛，这与组合型Thompson采样在乘积奖励问题中已知的指数级障碍一致。因此建议将PathTS作为实用默认方案，同时提醒其存在对抗性失效风险。
原文摘要 · Abstract (English)
We introduce Stochastic Reset Pathfinding (SRP), an episodic learning problem on a known directed graph with unknown stationary edge success probabilities. In each episode, the agent commits to a source-to-goal path, and any edge failure during execution resets it to the source. SRP captures settings such as entanglement distribution in quantum repeater networks, payment routing on the Lightning Network, and delivery in unreliable mesh networks. We show that the global-reset structure makes the optimal policy open-loop, placing SRP within the combinatorial cascading bandit (CCB) framework. We propose a Log-Dijkstra meta-algorithm with UCB (PathUCB) and Thompson Sampling (PathTS) instantiations. Our main technical result is a path-level regret bound for PathUCB that decomposes regret over suboptimal paths via a per-path complexity C(pi) combining each edge's prefix and suffix reliability. The bound is complementary to the edge-level CCB bound and more informative on structured graphs with polynomially many source-to-goal paths. Experiments on quantum-network, layered-DAG, grid-world, and Erdos-Renyi domains support the theory and show that PathTS typically achieves the best empirical performance among the algorithms tested. We then exhibit an adversarial instance on which PathTS fails to converge, consistent with a known exponential obstruction for combinatorial Thompson Sampling on multiplicative-reward problems. We recommend PathTS as the practical default while cautioning that adversarial instances exist.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。