PathUCB and PathTS: New algorithms tackle pathfinding under uncertainty

Stochastic Reset Pathfinding (SRP) defines a new learning problem: in each episode, an agent chooses a source-to-goal path on a known directed graph where each edge has an unknown stationary success probability. When an edge fails during traversal, the agent is reset to the source, making it a combinatorial cascading bandit with a global-reset structure. This setting directly mirrors real-world systems such as entanglement distribution in quantum repeater networks, payment routing on the Lightning Network, and unreliable mesh delivery networks. The authors prove that the optimal policy is open-loop, meaning the agent can commit to a fixed path per episode, which simplifies the problem into the combinatorial cascading bandit framework.

The paper introduces two meta-algorithms: PathUCB (built on Log-Dijkstra with UCB) and PathTS (with Thompson Sampling). The main theoretical contribution is a path-level regret bound for PathUCB that decomposes regret over suboptimal paths using a per-path complexity measure combining each edge's prefix and suffix reliability. This bound complements existing edge-level bounds and is more informative on structured graphs with polynomially many paths. Empirical evaluations on quantum-network topologies, layered DAGs, grid worlds, and Erdős–Rényi random graphs confirm the theory and show that PathTS typically yields the best performance. However, the authors also construct an adversarial instance where PathTS fails to converge—consistent with known exponential obstructions for combinatorial Thompson Sampling on multiplicative-reward problems. Their practical recommendation is to use PathTS as a default while remaining aware of potential adversarial pitfalls.