# Stochastic Reset Pathfinding: Path-Level Regret for Cascading Bandits over Graph Paths

arXiv: https://arxiv.org/abs/2607.15440 · HTML: https://mlsanity.com/paper/2607.15440/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 32 references that are in the map.
- First posted on arXiv 16 Jul 2026.

## Builds on (most cited first, 11 of 11)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Minimax Regret for Cascading Bandits](https://mlsanity.com/paper/2203.12577/) (2022)
- [Cascading Reinforcement Learning](https://mlsanity.com/paper/2401.08961/) (2024)
- [Learning to Route Efficiently with End-to-End Feedback: The Value of Networked Structure](https://mlsanity.com/paper/1810.10637/) (2018)
- [Optimally Reliable & Cheap Payment Flows on the Lightning Network](https://mlsanity.com/paper/2107.05322/) (2021)
- [Stochastic Shortest Path with Sparse Adversarial Costs](https://mlsanity.com/paper/2511.00637/) (2025)
- [Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model](https://mlsanity.com/paper/2604.16111/) (2026)

## Abstract (arXiv)

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.