近日，一篇題為《隨機重置路徑尋找：圖路徑上級聯賭博機的路徑級遺憾》的論文被提交至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作為實際應用中的默認算法，但同時也提醒用户注意對抗實例的存在。這項研究為處理具有重置特性的路徑規劃問題提供了理論框架和實用工具，有望推動量子網絡、支付路由等領域的算法設計。