Stochastic Reset Pathfinding Optimizes Graph Path Selection

Stochastic Reset Pathfinding (SRP) is a new episodic learning problem defined on known directed graphs where edge success probabilities are unknown. A key characteristic is that any edge failure during path execution causes a reset to the source, making the optimal policy open-loop. This framework is relevant to various real-world applications, including entanglement distribution in quantum networks, payment routing in the Lightning Network, and delivery in unreliable mesh networks. The researchers propose a Log-Dijkstra meta-algorithm, instantiated as PathUCB and PathTS, to tackle SRP. A significant technical contribution is a path-level regret bound for PathUCB, which offers a more informative decomposition of regret over suboptimal paths compared to traditional edge-level bounds, especially for structured graphs. Empirical evaluations across diverse domains demonstrate that PathTS generally achieves superior performance, though the paper also identifies adversarial instances where PathTS can fail to converge, consistent with known limitations for combinatorial Thompson Sampling in multiplicative-reward problems.