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