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

# Stochastic Reset Pathfinding: Path-Level Regret for Cascading Bandits over Graph Paths
Source: [https://arxiv.org/html/2607.15440](https://arxiv.org/html/2607.15440)
Guni Sharon Computer Science & Engineering Texas A&M University College Station, TX 77843 guni@tamu\.edu &Wei Zhang Computer Science & Engineering Texas A&M University College Station, TX 77843 komo@tamu\.edu

###### Abstract

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\.SRPcaptures 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, placingSRPwithin 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 forPathUCBthat decomposes regret over suboptimal paths via a per\-path*path complexity*C​\(π\)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 Erdős\-Rényi domains support the theory and show thatPathTStypically achieves the best empirical performance among algorithms tested\. We then exhibit an adversarial instance on whichPathTSfails to converge—consistent with a known exponential obstruction for combinatorial Thompson Sampling on multiplicative\-reward problems\. We recommendPathTSas the practical default while cautioning that adversarial instances exist\.

## 1Introduction

Several real\-world networked decision problems require an agent to traverse a known graph whose links may fail unpredictably, where any single failure forces a restart from the source\. Examples include entanglement distribution in quantum repeater networksWehneret al\.\([2018](https://arxiv.org/html/2607.15440#bib.bib28)\); Chakrabortyet al\.\([2020](https://arxiv.org/html/2607.15440#bib.bib36)\), payment routing on the Lightning NetworkPickhardt and Richter \([2021](https://arxiv.org/html/2607.15440#bib.bib3)\), and delivery in unreliable wireless mesh networksTalebiet al\.\([2018](https://arxiv.org/html/2607.15440#bib.bib20)\)\. Link success probabilities are unknown and must be learned through repeated interaction; the agent’s task is to find the most reliable source\-to\-goal path while minimizing failed attempts\.

We formalize this class of problems as*Stochastic Reset Pathfinding*\(SRP\): in each episode, the agent selects a pathπ\\pi, attempts to traverse it edge\-by\-edge, and resets to the source on the first failure\. The objective is to minimize cumulative regret with respect to the most reliable pathπ∗=arg⁡maxπ​∏e∈πpe\\pi^\{\*\}=\\arg\\max\_\{\\pi\}\\prod\_\{e\\in\\pi\}p\_\{e\}\.SRPsuperficially resembles a stochastic shortest\-path \(SSP\) problem, suggesting goal\-oriented RLBartoet al\.\([1993](https://arxiv.org/html/2607.15440#bib.bib33)\); Bonet and Geffner \([2003](https://arxiv.org/html/2607.15440#bib.bib34)\); Jafarnia\-Jahromiet al\.\([2023](https://arxiv.org/html/2607.15440#bib.bib10)\)as a candidate solver\. We show this framing is inappropriate: the global\-reset structure makes the optimal policy*open\-loop*\(Lemma[1](https://arxiv.org/html/2607.15440#Thmtheorem1)\), collapsing SSP’s closed\-loop machinery into combinatorial path search and placingSRPwithin the combinatorial cascading bandit \(CCB\) framework ofKvetonet al\.\([2015a](https://arxiv.org/html/2607.15440#bib.bib24)\)\. Our contributions are:

- •Problem reduction\.The optimal policy forSRPis an open\-loop simple path \(Lemma[1](https://arxiv.org/html/2607.15440#Thmtheorem1)\), identifiable by Dijkstra on log\-transformed edge weights\.
- •Algorithms\.A Log\-Dijkstra meta\-algorithm \(Algorithm[1](https://arxiv.org/html/2607.15440#alg1)\) with UCB and Thompson Sampling instantiationsPathUCBandPathTS\.PathUCBis closely related to CombCascadeKvetonet al\.\([2015a](https://arxiv.org/html/2607.15440#bib.bib24)\);PathTShas no CombCascade analogue and is the recommended practical choice in most regimes we test\.
- •Path\-level regret bound\.Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)bounds the regret ofPathUCBby∑π∉Ψ∗C​\(π\)2​ln⁡T/Δ​\(π\)\\sum\_\{\\pi\\notin\\Psi^\{\*\}\}C\(\\pi\)^\{2\}\\ln T/\\Delta\(\\pi\), where the per\-path*path complexity*C​\(π\)C\(\\pi\)encodes each edge’s prefix reliability \(probability of observation\) and suffix reliability \(downstream impact of estimation error\)\. This decomposition is complementary to the edge\-level CombCascade bound and more informative on structured graphs with many source\-to\-goal paths\.
- •Empirical study\.Experiments across four domains validate the theory and exhibit an adversarial instance on whichPathTSfails—consistent with theΩ​\(2k∗\)\\Omega\(2^\{k^\{\*\}\}\)obstruction ofWang and Chen \([2018](https://arxiv.org/html/2607.15440#bib.bib38)\)for combinatorial Thompson Sampling on multiplicative\-reward problems\.

## 2Problem Formulation

We consider an episodic learning setting where an agent navigates a known directed graph with unknown, stationary edge success probabilities\.

###### Definition 1\(SRPEnvironment\)\.

AnSRPenvironment is a tuple\(G,vs,vg,𝒫\)\(G,v\_\{s\},v\_\{g\},\\mathcal\{P\}\)whereG=\(V,E\)G=\(V,E\)is aknowndirected graph,vs≠vg∈Vv\_\{s\}\\neq v\_\{g\}\\in Vareknownsource and goal nodes, and𝒫=\(pe\)e∈E∈\[0,1\]\|E\|\\mathcal\{P\}=\(p\_\{e\}\)\_\{e\\in E\}\\in\[0,1\]^\{\|E\|\}is a vector of stationary edge success probabilitiesunknownto the agent\.

A*valid simple path*is a sequence of edgesπ=\(e1,…,ek\)\\pi=\(e\_\{1\},\\dots,e\_\{k\}\)withei=\(vi−1,vi\)∈Ee\_\{i\}=\(v\_\{i\-1\},v\_\{i\}\)\\in E,v0=vsv\_\{0\}=v\_\{s\},vk=vgv\_\{k\}=v\_\{g\}, and no repeated nodes; we write\|π\|=k\|\\pi\|=kand letΨ​\(vs,vg\)\\Psi\(v\_\{s\},v\_\{g\}\)denote the set of such paths\. We assumeΨ​\(vs,vg\)≠∅\\Psi\(v\_\{s\},v\_\{g\}\)\\neq\\emptyset\(the goal is reachable\)\.

Transition dynamics and feedback\.At episodett, the agent selectsπt∈Ψ​\(vs,vg\)\\pi\_\{t\}\\in\\Psi\(v\_\{s\},v\_\{g\}\)and traverses it sequentially\. Each edgeeie\_\{i\}produces an independent outcomeXei∼Bernoulli​\(pei\)X\_\{e\_\{i\}\}\\sim\\text\{Bernoulli\}\(p\_\{e\_\{i\}\}\): on success the agent advances, while on failure the episode terminates and a new one begins atvsv\_\{s\}\. The agent observes outcomes up to and including the first failure \(or the full path\(Xe1,…,Xek\)\(X\_\{e\_\{1\}\},\\dots,X\_\{e\_\{k\}\}\)if no failure occurs\)\.

###### Assumption 1\(Non\-degenerate edge reliability\)\.

There exists a known constantpmin\>0p\_\{\\min\}\>0such thatpe∈\[pmin,1\)p\_\{e\}\\in\[p\_\{\\min\},1\)for alle∈Ee\\in E\.

Objective\.The*reliability*ofπ\\piisP​\(π\)=∏e∈πpeP\(\\pi\)=\\prod\_\{e\\in\\pi\}p\_\{e\}, and the goal is to identify

π∗=arg⁡maxπ∈Ψ​\(vs,vg\)⁡P​\(π\)\.\\pi^\{\*\}=\\arg\\max\_\{\\pi\\in\\Psi\(v\_\{s\},v\_\{g\}\)\}P\(\\pi\)\.\(1\)Restricting to simple paths is without loss of generality \(Lemma[1](https://arxiv.org/html/2607.15440#Thmtheorem1)\)\. Performance is measured by the expected cumulative pseudo\-regret

R​\(T\)=𝔼​\[∑t=1T\(p∗−P​\(πt\)\)\],p∗=maxπ∈Ψ​\(vs,vg\)⁡P​\(π\),R\(T\)=\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\bigl\(p^\{\*\}\-P\(\\pi\_\{t\}\)\\bigr\)\\right\],\\qquad p^\{\*\}=\\max\_\{\\pi\\in\\Psi\(v\_\{s\},v\_\{g\}\)\}P\(\\pi\),\(2\)where the expectation is over the agent’s path selections,πt\\pi\_\{t\}\. The single\-episode regretr​\(πt\)=p∗−P​\(πt\)r\(\\pi\_\{t\}\)=p^\{\*\}\-P\(\\pi\_\{t\}\)is deterministic inπt\\pi\_\{t\}\.

### 2\.1Structural Properties ofSRP

Two structural properties placeSRPwithin the combinatorial bandit framework: \(1\) the optimal policy is open\-loop, and \(2\) planning reduces to shortest\-path search\.

###### Lemma 1\(Open\-Loop Optimality\)\.

Under Assumption[1](https://arxiv.org/html/2607.15440#Thmassumption1)and assumingΨ​\(vs,vg\)≠∅\\Psi\(v\_\{s\},v\_\{g\}\)\\neq\\emptyset, the optimal policy for anSRPenvironment is equivalent to an open\-loop simple pathπ∗∈Ψ​\(vs,vg\)\\pi^\{\*\}\\in\\Psi\(v\_\{s\},v\_\{g\}\)\.

###### Proof\.

The success probability of any randomized policy is an expectation over its deterministic realizations, hence no larger than that of the best such realization\. It therefore suffices to consider deterministic policiesμ:V→E\\mu:V\\to E, which are sufficient for optimality in finite MDPs byPuterman \([2014](https://arxiv.org/html/2607.15440#bib.bib43)\)\.

Fix a deterministicμ\\mu\. If its all\-success trajectory fromvsv\_\{s\}does not reachvgv\_\{g\}, thenP​\(μ\)=0P\(\\mu\)=0andμ\\muis dominated by any path inΨ​\(vs,vg\)\\Psi\(v\_\{s\},v\_\{g\}\)\(which exists by goal\-reachability and has positive reliability by Assumption[1](https://arxiv.org/html/2607.15440#Thmassumption1)\)\. Otherwise,μ\\muinduces a finite source\-to\-goal walkγμ=\(e1,…,em\)\\gamma\_\{\\mu\}=\(e\_\{1\},\\dots,e\_\{m\}\)\. Because any failure resets the agent tovsv\_\{s\}andμ\\muis stationary, the per\-attempt success probability ofμ\\muequals the probability that all edges inγμ\\gamma\_\{\\mu\}succeed:

P​\(μ\)=∏i=1mpei\.P\(\\mu\)=\\prod\_\{i=1\}^\{m\}p\_\{e\_\{i\}\}\.Ifγμ\\gamma\_\{\\mu\}contains a cycle, sayvi=vjv\_\{i\}=v\_\{j\}for somei<ji<j, deletingei\+1,…,eje\_\{i\+1\},\\dots,e\_\{j\}yields a shorter source\-to\-goal walkγ′\\gamma^\{\\prime\}with

P​\(γ′\)=P​\(γμ\)/∏ℓ=i\+1jpeℓ\>P​\(γμ\),P\(\\gamma^\{\\prime\}\)=P\(\\gamma\_\{\\mu\}\)\\Big/\\prod\_\{\\ell=i\+1\}^\{j\}p\_\{e\_\{\\ell\}\}\>P\(\\gamma\_\{\\mu\}\),where the strict inequality follows frompe<1p\_\{e\}<1\(Assumption[1](https://arxiv.org/html/2607.15440#Thmassumption1)\)\. Repeating this deletion yields a simple pathπ∈Ψ​\(vs,vg\)\\pi\\in\\Psi\(v\_\{s\},v\_\{g\}\)withP​\(π\)≥P​\(μ\)P\(\\pi\)\\geq P\(\\mu\)\. Hence every policy is dominated by some simple source\-to\-goal path\. SinceΨ​\(vs,vg\)\\Psi\(v\_\{s\},v\_\{g\}\)is finite and nonempty, a maximum\-reliability simple pathπ∗\\pi^\{\*\}exists, and committing toπ∗\\pi^\{\*\}at the start of each episode is an optimal open\-loop policy\. ∎

###### Lemma 2\(Reduction to Shortest Path\)\.

Given known edge probabilities𝒫\\mathcal\{P\}, any optimal pathπ∗∈arg⁡maxπ∈Ψ​\(vs,vg\)⁡P​\(π\)\\pi^\{\*\}\\in\\arg\\max\_\{\\pi\\in\\Psi\(v\_\{s\},v\_\{g\}\)\}P\(\\pi\)is a shortest path fromvsv\_\{s\}tovgv\_\{g\}under the transformed edge weightsw​\(e\)=−log⁡pew\(e\)=\-\\log p\_\{e\}, and can be found by Dijkstra’s algorithmDijkstra \([1959](https://arxiv.org/html/2607.15440#bib.bib37)\)\.

###### Proof\.

For any pathπ\\pi,−log⁡P​\(π\)=∑e∈π−log⁡pe=∑e∈πw​\(e\)\-\\log P\(\\pi\)=\\sum\_\{e\\in\\pi\}\-\\log p\_\{e\}=\\sum\_\{e\\in\\pi\}w\(e\)\. Since−log\-\\logis decreasing, maximizingP​\(π\)P\(\\pi\)is equivalent to minimizing∑e∈πw​\(e\)\\sum\_\{e\\in\\pi\}w\(e\)\. Assumption[1](https://arxiv.org/html/2607.15440#Thmassumption1)givesw​\(e\)∈\(0,−log⁡pmin\]w\(e\)\\in\(0,\-\\log p\_\{\\min\}\], so Dijkstra’s algorithm solves the positive\-weight shortest\-path problem exactly\. ∎

The log\-transform is standard in the most\-reliable\-path literatureMaheshwari \([1974](https://arxiv.org/html/2607.15440#bib.bib8)\); any exact shortest\-path algorithm may replace Dijkstra without affecting the theoretical guarantees below\.

## 3Related Work

##### Combinatorial cascading bandits\.

Cascading bandits were introduced byKvetonet al\.\([2015b](https://arxiv.org/html/2607.15440#bib.bib7)\)for disjunctive top\-K recommendation and extended to general feasible sets with conjunctive \(product\) rewards byKvetonet al\.\([2015a](https://arxiv.org/html/2607.15440#bib.bib24)\)under the name*combinatorial cascading bandits*\(CCB\)\.SRPis an instance of CCB with feasible setΨ​\(vs,vg\)\\Psi\(v\_\{s\},v\_\{g\}\)\. The affiliated CombCascade algorithm applies UCB to per\-edge success probabilities and uses the same \(−log\-\\log\) transformation that underpins our analysis, yielding the edge\-level regret bound of Eq\.[6](https://arxiv.org/html/2607.15440#S5.E6), against which we compare in Section[5](https://arxiv.org/html/2607.15440#S5)\. Subsequent work extends CCB to contextual featuresLiet al\.\([2016](https://arxiv.org/html/2607.15440#bib.bib17)\), adversarial corruptionXieet al\.\([2025](https://arxiv.org/html/2607.15440#bib.bib16)\), and state\-dependent RLDuet al\.\([2024](https://arxiv.org/html/2607.15440#bib.bib14)\); these extensions are complementary in scope but do not directly apply toSRP\. A related line studies stochastic shortest\-path routing as a combinatorial bandit with*additive*edge costsTalebiet al\.\([2018](https://arxiv.org/html/2607.15440#bib.bib20)\); Zhu and Modiano \([2018](https://arxiv.org/html/2607.15440#bib.bib19)\)which contrasts withSRP’s multiplicative∏epe\\prod\_\{e\}p\_\{e\}reward\.

##### Thompson Sampling for cascade feedback\.

Two related TS analyses exist but neither coversSRPdirectly\. Cheung et al\.Cheunget al\.\([2019](https://arxiv.org/html/2607.15440#bib.bib21)\)prove a regret bound for Beta\-Bernoulli TS on disjunctive cascading bandits, but their analysis exploits matroid structure that does not generalize to graph paths\. Wang & ChenWang and Chen \([2018](https://arxiv.org/html/2607.15440#bib.bib38)\)analyze combinatorial TS for general CMAB with non\-linear rewards under semi\-bandit \(not cascade\) feedback, and exhibit anΩ​\(2k∗\)\\Omega\(2^\{k^\{\*\}\}\)lower bound on the leading regret constant for multiplicative\-reward instances, wherek∗=\|π∗\|k^\{\*\}=\|\\pi^\{\*\}\|\. Remark[1](https://arxiv.org/html/2607.15440#Thmremark1)discusses the obstacles to extending these toSRP\.

##### Goal\-oriented reinforcement learning\.

The Stochastic Shortest Path \(SSP\) problemCohenet al\.\([2020](https://arxiv.org/html/2607.15440#bib.bib13)\); Tarbouriechet al\.\([2021](https://arxiv.org/html/2607.15440#bib.bib11)\); Jafarnia\-Jahromiet al\.\([2023](https://arxiv.org/html/2607.15440#bib.bib10)\); Johnsonet al\.\([2025](https://arxiv.org/html/2607.15440#bib.bib9)\)models action failures as transitions to neighboring “slip” states, requiring a closed\-loop policyμ:V→E\\mu:V\\to Eand yielding regret bounds that reflect this closed\-loop structureCohenet al\.\([2020](https://arxiv.org/html/2607.15440#bib.bib13)\)\. UnderSRP’s global\-reset dynamics the optimal policy is open\-loop \(Lemma[1](https://arxiv.org/html/2607.15440#Thmtheorem1)\), placing the problem in the bandit rather than the RL regime\. Existing SSP bounds and algorithms \(including the posterior\-sampling method ofJafarnia\-Jahromiet al\.\([2023](https://arxiv.org/html/2607.15440#bib.bib10)\), the closest analog toPathTS\) are therefore not directly applicable\.

## 4A Graph Search Approach forSRP

We frame the learning process \(listed in Algorithm[1](https://arxiv.org/html/2607.15440#alg1)\) as an iterative loop over: \(1\) estimate each edge’s reliability, \(2\) select a path via Dijkstra on log\-transformed estimates, \(3\) attempt to traverse it, and \(4\) update estimators on the observed prefix\. One subtlety: UCB\-style estimators can exceed11via their confidence bonus, which under−log\-\\logwould yield negative edge weights and invalidate Dijkstra\. Both instantiations defined below therefore clampp^e​\(t\)≤1\\hat\{p\}\_\{e\}\(t\)\\leq 1, ensuringwt​\(e\)≥0w\_\{t\}\(e\)\\geq 0and that Dijkstra returnsarg⁡maxπ∈Ψ​\(vs,vg\)​∏e∈πp^e​\(t\)\\arg\\max\_\{\\pi\\in\\Psi\(v\_\{s\},v\_\{g\}\)\}\\prod\_\{e\\in\\pi\}\\hat\{p\}\_\{e\}\(t\)\.

Algorithm 1Log\-Dijkstra Meta\-Algorithm0:Graph

G=\(V,E\)G=\(V,E\), source

vsv\_\{s\}, goal

vgv\_\{g\}, horizon

TT
1:Initialize estimator state for all

e∈Ee\\in E
2:for

t=1,…,Tt=1,\\dots,Tdo

3:

πt←Dijkstra​\(G,wt,vs,vg\)\\pi\_\{t\}\\leftarrow\\mathrm\{Dijkstra\}\(G,w\_\{t\},v\_\{s\},v\_\{g\}\)with

wt​\(e\)=−log⁡p^e​\(t\)w\_\{t\}\(e\)=\-\\log\\hat\{p\}\_\{e\}\(t\)
4:Traverse

πt\\pi\_\{t\}and let

KKbe the index of the first failure, or

K=\|πt\|K=\|\\pi\_\{t\}\|if all succeed

5:Update

p^ei\\hat\{p\}\_\{e\_\{i\}\}from

XeiX\_\{e\_\{i\}\}for

i=1,…,Ki=1,\\dots,K

The two instantiations below differ only in the estimator update at Line[5](https://arxiv.org/html/2607.15440#alg1.l5)\.

### 4\.1PathUCB: Upper Confidence Bound Exploration

PathUCBfollows the optimism\-in\-the\-face\-of\-uncertainty principleAueret al\.\([2002](https://arxiv.org/html/2607.15440#bib.bib1)\); Lai and Robbins \([1985](https://arxiv.org/html/2607.15440#bib.bib41)\)\. LetNe​\(t\)N\_\{e\}\(t\)andSe​\(t\)S\_\{e\}\(t\)denote the number of attempts and successes of edgeeeprior to episodett, with empirical meanp¯e​\(t\)=Se​\(t\)/Ne​\(t\)\\bar\{p\}\_\{e\}\(t\)=S\_\{e\}\(t\)/N\_\{e\}\(t\)\. The estimator is

p^e​\(t\)=\{1Ne​\(t\)=0,clip​\(p¯e​\(t\)\+ρ​ln⁡tNe​\(t\),pmin,1\)Ne​\(t\)\>0,\\hat\{p\}\_\{e\}\(t\)=\\begin\{cases\}1&N\_\{e\}\(t\)=0,\\\\ \\mathrm\{clip\}\\\!\\left\(\\bar\{p\}\_\{e\}\(t\)\+\\sqrt\{\\tfrac\{\\rho\\ln t\}\{N\_\{e\}\(t\)\}\},\\,p\_\{\\min\},\\,1\\right\)&N\_\{e\}\(t\)\>0,\\end\{cases\}\(3\)whereρ\>0\\rho\>0is an exploration parameter \(ρ≥2\\rho\\geq 2suffices for Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)\)\. The unvisited initializationp^e​\(t\)=1\\hat\{p\}\_\{e\}\(t\)=1yieldswt​\(e\)=0w\_\{t\}\(e\)=0, prioritizing unexplored edges in Dijkstra\. The upper clamp at11preserves optimism \(sincepe<1p\_\{e\}<1\), and the lower clamp atpminp\_\{\\min\}keepswt​\(e\)w\_\{t\}\(e\)finite; the latter is inactive on the optimism event below and acts only as a safety net\.

We define the optimism event𝒪t=\{p^e​\(t\)≥pe​for all​e∈E\}\\mathcal\{O\}\_\{t\}=\\\{\\hat\{p\}\_\{e\}\(t\)\\geq p\_\{e\}\\text\{ for all \}e\\in E\\\}\. The regret analysis \(Section[5\.1](https://arxiv.org/html/2607.15440#S5.SS1)\) partitions on𝒪t\\mathcal\{O\}\_\{t\}: under optimism, suboptimal selection implies an overestimation gap; the rare complementary event \(𝒪tc\\mathcal\{O\}\_\{t\}^\{c\}\) contributes a bounded regret constant via Lemma[7](https://arxiv.org/html/2607.15440#Thmtheorem7)\.

### 4\.2PathTS: Thompson Sampling

PathTSsamples each edge’s reliability from its posterior under a Beta\-Bernoulli conjugate modelThompson \([1933](https://arxiv.org/html/2607.15440#bib.bib15)\); Danielet al\.\([2018](https://arxiv.org/html/2607.15440#bib.bib6)\); DeGroot \([2005](https://arxiv.org/html/2607.15440#bib.bib40)\)and selects the path maximizing the sampled product\. With priorBeta​\(αe,0,βe,0\)\\text\{Beta\}\(\\alpha\_\{e,0\},\\beta\_\{e,0\}\)\(defaultαe,0=βe,0=1\\alpha\_\{e,0\}=\\beta\_\{e,0\}=1\) and the standard updateαe\+=Xe\\alpha\_\{e\}\\mathrel\{\+\}=X\_\{e\},βe\+=1−Xe\\beta\_\{e\}\\mathrel\{\+\}=1\-X\_\{e\}, the per\-episode estimator is

p^e​\(t\)=max⁡\(p~e​\(t\),pmin\),p~e​\(t\)∼Beta​\(αe​\(t\),βe​\(t\)\)\.\\hat\{p\}\_\{e\}\(t\)=\\max\\\!\\left\(\\tilde\{p\}\_\{e\}\(t\),\\,p\_\{\\min\}\\right\),\\qquad\\tilde\{p\}\_\{e\}\(t\)\\sim\\text\{Beta\}\(\\alpha\_\{e\}\(t\),\\beta\_\{e\}\(t\)\)\.\(4\)Since the Beta is supported on\[0,1\]\[0,1\], the upper clamp at11is automatic\. The lower clamp atpminp\_\{\\min\}is a safety net: asNe​\(t\)→∞N\_\{e\}\(t\)\\to\\inftythe posterior concentrates aroundpe≥pminp\_\{e\}\\geq p\_\{\\min\}and the clamp is asymptotically inactive; for finitettit introduces a small upward bias on data\-starved edges without affecting empirical behavior \(Section[6](https://arxiv.org/html/2607.15440#S6)\)\.

## 5Theoretical Analysis

SRPis an instance of the combinatorial cascading bandit \(CCB\) frameworkKvetonet al\.\([2015a](https://arxiv.org/html/2607.15440#bib.bib24)\)with feasible setΨ​\(vs,vg\)\\Psi\(v\_\{s\},v\_\{g\}\)\. Applying CombCascade gives the edge\-level baseline in Eq\.[6](https://arxiv.org/html/2607.15440#S5.E6)\. We provide a complementary path\-level regret bound forPathUCB, which uses the same log\-transformed path oracle but analyzes regret at the level of selected paths rather than individual edges\. The implementation differences between CombCascade andPathUCBare discussed in Appendix[B](https://arxiv.org/html/2607.15440#A2)\.

###### Definition 2\(Per\-Edge Gap\)\.

LetΨ∗=arg⁡maxπ∈Ψ​\(vs,vg\)⁡P​\(π\)\\Psi^\{\*\}=\\arg\\max\_\{\\pi\\in\\Psi\(v\_\{s\},v\_\{g\}\)\}P\(\\pi\)andE~=\{e∈E:e∉π​for all​π∈Ψ∗\}\\tilde\{E\}=\\\{e\\in E:e\\notin\\pi\\text\{ for all \}\\pi\\in\\Psi^\{\*\}\\\}\. Fore∈E~e\\in\\tilde\{E\}, the*per\-edge suboptimality gap*is

ΔeCCB=p∗−maxπ∈Ψ​\(vs,vg\):e∈π,P​\(π\)<p∗⁡P​\(π\)\.\\Delta\_\{e\}^\{\\mathrm\{CCB\}\}\\;=\\;p^\{\*\}\-\\max\_\{\\pi\\in\\Psi\(v\_\{s\},v\_\{g\}\):\\,e\\in\\pi,\\,P\(\\pi\)<p^\{\*\}\}P\(\\pi\)\.\(5\)

LettingLmax=maxπ∈Ψ​\(vs,vg\)⁡\|π\|L\_\{\\max\}=\\max\_\{\\pi\\in\\Psi\(v\_\{s\},v\_\{g\}\)\}\|\\pi\|, Theorem 1 ofKvetonet al\.\([2015a](https://arxiv.org/html/2607.15440#bib.bib24)\)translates to:

𝔼​\[R​\(T\)\]≤Lmaxp∗​∑e∈E~4272ΔeCCB​ln⁡T\+π23​\|E\|\.\\mathbb\{E\}\[R\(T\)\]\\;\\leq\\;\\frac\{L\_\{\\max\}\}\{p^\{\*\}\}\\sum\_\{e\\in\\tilde\{E\}\}\\frac\{4272\}\{\\Delta\_\{e\}^\{\\mathrm\{CCB\}\}\}\\ln T\\;\+\\;\\frac\{\\pi^\{2\}\}\{3\}\|E\|\.\(6\)This bound is*edge\-level*: it sums per\-edge contributionsΔeCCB\\Delta\_\{e\}^\{\\mathrm\{CCB\}\}without tracking where in a path an edge appears\. Section[5\.1](https://arxiv.org/html/2607.15440#S5.SS1)develops a complementary*path\-level*bound via a per\-path complexityC​\(π\)C\(\\pi\)that captures each edge’s prefix reliability \(probability of being observed\) and suffix reliability \(downstream impact of estimation error\)\. Section[5\.2](https://arxiv.org/html/2607.15440#S5.SS2)compares the two bounds analytically; Section[6\.1](https://arxiv.org/html/2607.15440#S6.SS1)compares them empirically\.

### 5\.1Path\-Dependent Regret Bound

###### Definition 3\(Per\-Edge Overestimation\)\.

The*per\-edge overestimation*isδe​\(t\)=p^e​\(t\)−pe\\delta\_\{e\}\(t\)=\\hat\{p\}\_\{e\}\(t\)\-p\_\{e\}, which is non\-negative on𝒪t\\mathcal\{O\}\_\{t\}\. For unvisited edges,δe​\(t\)=1−pe≤1−pmin\\delta\_\{e\}\(t\)=1\-p\_\{e\}\\leq 1\-p\_\{\\min\}\.

###### Definition 4\(Suffix Reliability\)\.

For a pathπ=\(e1,…,eL\)\\pi=\(e\_\{1\},\\dots,e\_\{L\}\)and positioni∈\{1,…,L\}i\\in\\\{1,\\dots,L\\\}, the*suffix reliability*after positioniiisSi​\(π\)=∏k=i\+1LpekS\_\{i\}\(\\pi\)=\\prod\_\{k=i\+1\}^\{L\}p\_\{e\_\{k\}\}, with the conventionSL​\(π\)=1S\_\{L\}\(\\pi\)=1\(empty product\)\.

For a suboptimal pathπ∉Ψ∗\\pi\\notin\\Psi^\{\*\}, we writeΔ​\(π\)=p∗−P​\(π\)\>0\\Delta\(\\pi\)=p^\{\*\}\-P\(\\pi\)\>0for the suboptimality gap, and letP^t​\(π\)=∏e∈πp^e​\(t\)\\hat\{P\}\_\{t\}\(\\pi\)=\\prod\_\{e\\in\\pi\}\\hat\{p\}\_\{e\}\(t\)denote the estimated path reliability at episodett\.

Estimation Properties\.Standard Hoeffding\-based concentration arguments give two facts \(Lemmas[7](https://arxiv.org/html/2607.15440#Thmtheorem7)and[8](https://arxiv.org/html/2607.15440#Thmtheorem8)in Appendix[C](https://arxiv.org/html/2607.15440#A3)\): \(i\)Pr⁡\(𝒪t\)≥1−\|E\|​t−3\\Pr\(\\mathcal\{O\}\_\{t\}\)\\geq 1\-\|E\|\\,t^\{\-3\}, contributingO​\(\|E\|\)O\(\|E\|\)regret on𝒪tc\\mathcal\{O\}\_\{t\}^\{c\}; and \(ii\) for any edge withNe​\(t\)\>0N\_\{e\}\(t\)\>0,δe​\(t\)≤2​ρ​ln⁡t/Ne​\(t\)\\delta\_\{e\}\(t\)\\leq 2\\sqrt\{\\rho\\ln t/N\_\{e\}\(t\)\}with probability≥1−t−3\\geq 1\-t^\{\-3\}\.

Suboptimal Selection and Weighted Overestimation\.Our next lemma is the structural step where the path\-level analysis diverges from CombCascade\. Lemma 2 ofKvetonet al\.\([2015a](https://arxiv.org/html/2607.15440#bib.bib24)\)bounds the product difference∏emin⁡\(p¯e\+ue,1\)−∏epe\\prod\_\{e\}\\min\(\\bar\{p\}\_\{e\}\+u\_\{e\},1\)\-\\prod\_\{e\}p\_\{e\}by the unweighted sum∑eue\\sum\_\{e\}u\_\{e\}of confidence radii; we instead weight each edge’s overestimation by its suffix reliabilitySi​\(πt\)S\_\{i\}\(\\pi\_\{t\}\), exposing position\-dependent structure\.

###### Lemma 3\(Suboptimal Selection Implies Weighted Overestimation\)\.

Under Assumption[1](https://arxiv.org/html/2607.15440#Thmassumption1), suppose the optimism event𝒪t\\mathcal\{O\}\_\{t\}holds at episodett, and a suboptimal pathπt=\(e1,…,eL\)∉Ψ∗\\pi\_\{t\}=\(e\_\{1\},\\dots,e\_\{L\}\)\\notin\\Psi^\{\*\}is selected\. Then

∑i=1LSi​\(πt\)​δei​\(t\)≥Δ​\(πt\)\.\\sum\_\{i=1\}^\{L\}S\_\{i\}\(\\pi\_\{t\}\)\\,\\delta\_\{e\_\{i\}\}\(t\)\\;\\geq\\;\\Delta\(\\pi\_\{t\}\)\.\(7\)

###### Proof\.

On𝒪t\\mathcal\{O\}\_\{t\}, every optimal pathπ∗∈Ψ∗\\pi^\{\*\}\\in\\Psi^\{\*\}satisfiesP^t​\(π∗\)≥p∗\\hat\{P\}\_\{t\}\(\\pi^\{\*\}\)\\geq p^\{\*\}\. Since the algorithm selectsπt∈arg⁡maxπ∈Ψ​\(vs,vg\)⁡P^t​\(π\)\\pi\_\{t\}\\in\\arg\\max\_\{\\pi\\in\\Psi\(v\_\{s\},v\_\{g\}\)\}\\hat\{P\}\_\{t\}\(\\pi\)via Dijkstra \(Lemma[2](https://arxiv.org/html/2607.15440#Thmtheorem2)\),P^t​\(πt\)≥P^t​\(π∗\)≥p∗\\hat\{P\}\_\{t\}\(\\pi\_\{t\}\)\\geq\\hat\{P\}\_\{t\}\(\\pi^\{\*\}\)\\geq p^\{\*\}, so

Δ​\(πt\)=p∗−P​\(πt\)≤P^t​\(πt\)−P​\(πt\)\.\\Delta\(\\pi\_\{t\}\)=p^\{\*\}\-P\(\\pi\_\{t\}\)\\;\\leq\\;\\hat\{P\}\_\{t\}\(\\pi\_\{t\}\)\-P\(\\pi\_\{t\}\)\.\(8\)The telescoping identity∏iai−∏ibi=∑i\(ai−bi\)​∏j<iaj​∏k\>ibk\\prod\_\{i\}a\_\{i\}\-\\prod\_\{i\}b\_\{i\}=\\sum\_\{i\}\(a\_\{i\}\-b\_\{i\}\)\\prod\_\{j<i\}a\_\{j\}\\prod\_\{k\>i\}b\_\{k\}applied toai=p^ei​\(t\)a\_\{i\}=\\hat\{p\}\_\{e\_\{i\}\}\(t\)andbi=peib\_\{i\}=p\_\{e\_\{i\}\}gives

P^t​\(πt\)−P​\(πt\)=∑i=1Lδei​\(t\)​\(∏j=1i−1p^ej​\(t\)\)​Si​\(πt\)\.\\hat\{P\}\_\{t\}\(\\pi\_\{t\}\)\-P\(\\pi\_\{t\}\)\\;=\\;\\sum\_\{i=1\}^\{L\}\\delta\_\{e\_\{i\}\}\(t\)\\left\(\\prod\_\{j=1\}^\{i\-1\}\\hat\{p\}\_\{e\_\{j\}\}\(t\)\\right\)S\_\{i\}\(\\pi\_\{t\}\)\.\(9\)The upper clamp givesp^ej​\(t\)≤1\\hat\{p\}\_\{e\_\{j\}\}\(t\)\\leq 1, andδei​\(t\)≥0\\delta\_\{e\_\{i\}\}\(t\)\\geq 0on𝒪t\\mathcal\{O\}\_\{t\}, so dropping the prefix product yieldsP^t​\(πt\)−P​\(πt\)≤∑iSi​\(πt\)​δei​\(t\)\\hat\{P\}\_\{t\}\(\\pi\_\{t\}\)\-P\(\\pi\_\{t\}\)\\leq\\sum\_\{i\}S\_\{i\}\(\\pi\_\{t\}\)\\,\\delta\_\{e\_\{i\}\}\(t\)\. Combining with the displayed inequality above completes the proof\. ∎

###### Definition 5\(Prefix Reliability and Path Complexity\)\.

Forπ=\(e1,…,eL\)\\pi=\(e\_\{1\},\\dots,e\_\{L\}\)andi∈\{1,…,L\}i\\in\\\{1,\\dots,L\\\}, the*prefix reliability*:Qi​\(π\)=∏j=1i−1pej​with​Q1​\(π\)=1Q\_\{i\}\(\\pi\)=\\prod\_\{j=1\}^\{i\-1\}p\_\{e\_\{j\}\}\\text\{ with \}Q\_\{1\}\(\\pi\)=1is the probability thateie\_\{i\}is reached whenπ\\piis attempted\. The*path complexity*ofπ\\piis

C​\(π\)=∑i=1LSi​\(π\)Qi​\(π\)\.C\(\\pi\)=\\sum\_\{i=1\}^\{L\}\\frac\{S\_\{i\}\(\\pi\)\}\{\\sqrt\{Q\_\{i\}\(\\pi\)\}\}\.\(10\)

The prefix and suffix factorizeP​\(π\)=Qi​\(π\)​pei​Si​\(π\)P\(\\pi\)=Q\_\{i\}\(\\pi\)\\,p\_\{e\_\{i\}\}\\,S\_\{i\}\(\\pi\)at every positionii\.

LetMπ​\(t\)M\_\{\\pi\}\(t\)be the number of timesπ\\pihas been selected by episodett\. A Chernoff bound \(full statement in Lemma[9](https://arxiv.org/html/2607.15440#Thmtheorem9), Appendix[D](https://arxiv.org/html/2607.15440#A4)\) gives that, with probability1−T−21\-T^\{\-2\}, the number of times edgeeie\_\{i\}at positioniihas been observed within thoseMπ​\(t\)M\_\{\\pi\}\(t\)selections is≥Qi​\(π\)​Mπ​\(t\)/2\\geq Q\_\{i\}\(\\pi\)\\,M\_\{\\pi\}\(t\)/2, providedMπ​\(t\)≥24​ln⁡T/Qi​\(π\)M\_\{\\pi\}\(t\)\\geq 24\\ln T/Q\_\{i\}\(\\pi\)\.

###### Lemma 4\(Per\-Path Selection Bound\)\.

Under Assumption[1](https://arxiv.org/html/2607.15440#Thmassumption1)withρ≥2\\rho\\geq 2, on the joint high\-probability event of Lemmas[7](https://arxiv.org/html/2607.15440#Thmtheorem7),[8](https://arxiv.org/html/2607.15440#Thmtheorem8), and[9](https://arxiv.org/html/2607.15440#Thmtheorem9), every suboptimal pathπ∉Ψ∗\\pi\\notin\\Psi^\{\*\}satisfies

Mπ​\(T\)≤24​ln⁡TQL​\(π\)\+8​ρ​C​\(π\)2​ln⁡TΔ​\(π\)2\.M\_\{\\pi\}\(T\)\\;\\leq\\;\\frac\{24\\,\\ln T\}\{Q\_\{L\}\(\\pi\)\}\+\\frac\{8\\rho\\,C\(\\pi\)^\{2\}\\,\\ln T\}\{\\Delta\(\\pi\)^\{2\}\}\.\(11\)

###### Proof\.

Fixπ=\(e1,…,eL\)∉Ψ∗\\pi=\(e\_\{1\},\\dots,e\_\{L\}\)\\notin\\Psi^\{\*\}and let𝒯π=\{t≤T:πt=π\}\\mathcal\{T\}\_\{\\pi\}=\\\{t\\leq T:\\pi\_\{t\}=\\pi\\\}, soMπ​\(T\)=\|𝒯π\|M\_\{\\pi\}\(T\)=\|\\mathcal\{T\}\_\{\\pi\}\|\. Partition𝒯π\\mathcal\{T\}\_\{\\pi\}into the warm\-up phase𝒯πwu=\{t∈𝒯π:Mπ​\(t\)<24​ln⁡T/QL​\(π\)\}\\mathcal\{T\}\_\{\\pi\}^\{\\mathrm\{wu\}\}=\\\{t\\in\\mathcal\{T\}\_\{\\pi\}:M\_\{\\pi\}\(t\)<24\\ln T/Q\_\{L\}\(\\pi\)\\\}and the saturation phase𝒯πsat=𝒯π∖𝒯πwu\\mathcal\{T\}\_\{\\pi\}^\{\\mathrm\{sat\}\}=\\mathcal\{T\}\_\{\\pi\}\\setminus\\mathcal\{T\}\_\{\\pi\}^\{\\mathrm\{wu\}\}\. SinceMπM\_\{\\pi\}increments by11on eacht∈𝒯πt\\in\\mathcal\{T\}\_\{\\pi\}, the warm\-up phase contributes\|𝒯πwu\|≤24​ln⁡T/QL​\(π\)\|\\mathcal\{T\}\_\{\\pi\}^\{\\mathrm\{wu\}\}\|\\leq 24\\ln T/Q\_\{L\}\(\\pi\)\.

Saturation phase\.For anyt∈𝒯πsatt\\in\\mathcal\{T\}\_\{\\pi\}^\{\\mathrm\{sat\}\},Mπ​\(t\)≥24​ln⁡T/Qi​\(π\)M\_\{\\pi\}\(t\)\\geq 24\\ln T/Q\_\{i\}\(\\pi\)for everyi≤Li\\leq L\(usingQi≥QLQ\_\{i\}\\geq Q\_\{L\}\), so Lemma[9](https://arxiv.org/html/2607.15440#Thmtheorem9)givesNei​\(t\)≥Qi​\(π\)​Mπ​\(t\)/2N\_\{e\_\{i\}\}\(t\)\\geq Q\_\{i\}\(\\pi\)\\,M\_\{\\pi\}\(t\)/2\. Chaining Lemmas[3](https://arxiv.org/html/2607.15440#Thmtheorem3)and[8](https://arxiv.org/html/2607.15440#Thmtheorem8)\(withln⁡t≤ln⁡T\\ln t\\leq\\ln T\),

Δ​\(π\)≤∑i=1LSi​\(π\)​δei​\(t\)≤∑i=1LSi​\(π\)⋅2​2​ρ​ln⁡TQi​\(π\)​Mπ​\(t\)=2​2​ρ​ln⁡TMπ​\(t\)​C​\(π\)\.\\Delta\(\\pi\)\\;\\leq\\;\\sum\_\{i=1\}^\{L\}S\_\{i\}\(\\pi\)\\,\\delta\_\{e\_\{i\}\}\(t\)\\;\\leq\\;\\sum\_\{i=1\}^\{L\}S\_\{i\}\(\\pi\)\\cdot 2\\sqrt\{\\tfrac\{2\\rho\\ln T\}\{Q\_\{i\}\(\\pi\)\\,M\_\{\\pi\}\(t\)\}\}\\;=\\;\\tfrac\{2\\sqrt\{2\\rho\\ln T\}\}\{\\sqrt\{M\_\{\\pi\}\(t\)\}\}\\,C\(\\pi\)\.Squaring yieldsMπ​\(t\)≤8​ρ​C​\(π\)2​ln⁡T/Δ​\(π\)2M\_\{\\pi\}\(t\)\\leq 8\\rho\\,C\(\\pi\)^\{2\}\\ln T/\\Delta\(\\pi\)^\{2\}for everyt∈𝒯πsatt\\in\\mathcal\{T\}\_\{\\pi\}^\{\\mathrm\{sat\}\}\. Evaluating att⋆=max⁡𝒯πsatt^\{\\star\}=\\max\\mathcal\{T\}\_\{\\pi\}^\{\\mathrm\{sat\}\}\(or noting\|𝒯πsat\|=0\|\\mathcal\{T\}\_\{\\pi\}^\{\\mathrm\{sat\}\}\|=0otherwise\) gives\|𝒯πsat\|≤Mπ​\(t⋆\)≤8​ρ​C​\(π\)2​ln⁡T/Δ​\(π\)2\|\\mathcal\{T\}\_\{\\pi\}^\{\\mathrm\{sat\}\}\|\\leq M\_\{\\pi\}\(t^\{\\star\}\)\\leq 8\\rho\\,C\(\\pi\)^\{2\}\\ln T/\\Delta\(\\pi\)^\{2\}\.

Combining:Mπ​\(T\)≤24​ln⁡T/QL​\(π\)\+8​ρ​C​\(π\)2​ln⁡T/Δ​\(π\)2M\_\{\\pi\}\(T\)\\leq 24\\ln T/Q\_\{L\}\(\\pi\)\+8\\rho\\,C\(\\pi\)^\{2\}\\ln T/\\Delta\(\\pi\)^\{2\}\. ∎

###### Theorem 5\(Path\-Dependent Regret ofPathUCB\)\.

Under Assumption[1](https://arxiv.org/html/2607.15440#Thmassumption1)withρ≥2\\rho\\geq 2, the expected cumulative regret ofPathUCBsatisfies

𝔼​\[R​\(T\)\]≤∑π∉Ψ∗8​ρ​C​\(π\)2​ln⁡TΔ​\(π\)\+∑π∉Ψ∗24​ln⁡TQL​\(π\)\+O​\(\|E\|\+\|Ψ​\(vs,vg\)\|​LmaxT\)\.\\mathbb\{E\}\[R\(T\)\]\\;\\leq\\;\\sum\_\{\\pi\\notin\\Psi^\{\*\}\}\\frac\{8\\rho\\,C\(\\pi\)^\{2\}\\,\\ln T\}\{\\Delta\(\\pi\)\}\\;\+\\;\\sum\_\{\\pi\\notin\\Psi^\{\*\}\}\\frac\{24\\,\\ln T\}\{Q\_\{L\}\(\\pi\)\}\\;\+\\;O\\\!\\left\(\|E\|\+\\frac\{\|\\Psi\(v\_\{s\},v\_\{g\}\)\|\\,L\_\{\\max\}\}\{T\}\\right\)\.\(12\)

###### Proof Sketch\.

On the joint high\-probability event of Lemmas[7](https://arxiv.org/html/2607.15440#Thmtheorem7),[8](https://arxiv.org/html/2607.15440#Thmtheorem8), and[9](https://arxiv.org/html/2607.15440#Thmtheorem9), Lemma[4](https://arxiv.org/html/2607.15440#Thmtheorem4)boundsMπ​\(T\)M\_\{\\pi\}\(T\)for every suboptimalπ\\pi\. The contribution of eachπ\\pito expected regret isΔ​\(π\)​Mπ​\(T\)\\Delta\(\\pi\)\\,M\_\{\\pi\}\(T\); summing and absorbing the warm\-up term viaΔ​\(π\)≤1\\Delta\(\\pi\)\\leq 1gives the leading two sums\. Off\-event contributions areO​\(\|E\|\)O\(\|E\|\)from optimism/UCB failures plusO​\(\|Ψ​\(vs,vg\)\|​Lmax/T\)O\(\|\\Psi\(v\_\{s\},v\_\{g\}\)\|L\_\{\\max\}/T\)from observation failures\. Full proof in Appendix[E](https://arxiv.org/html/2607.15440#A5)\. ∎

### 5\.2Discussion

Comparison with the CCB bound\.The edge\-level CombCascade bound \([6](https://arxiv.org/html/2607.15440#S5.E6)\) sumsO​\(1/Δe,min\)O\(1/\\Delta\_\{e,\\min\}\)over suboptimal edges and scales globally with1/p∗1/p^\{\*\}, avoiding any enumeration of paths\. In contrast, the path\-level bound sumsO​\(C​\(π\)2​ln⁡T/Δ​\(π\)\)O\(C\(\\pi\)^\{2\}\\ln T/\\Delta\(\\pi\)\)over suboptimal paths, withC​\(π\)C\(\\pi\)capturing position\-dependent structure discarded by the edge\-level analysis \(Remark[2](https://arxiv.org/html/2607.15440#Thmremark2)\)\. Neither dominates: the edge\-level bound is preferable when\|Ψ​\(vs,vg\)\|\|\\Psi\(v\_\{s\},v\_\{g\}\)\|is large relative to\|E\|\|E\|\(typically dense graphs\), while the path\-level bound is more informative when the path count is polynomial in\|V\|\|V\|\(layered DAGs, sparse networks\)\. Both bounds depend on unknown problem parameters and serve as theoretical guarantees rather than computable predictions; both are simultaneously valid, so the minimum applies\. The path\-level bound also carries the\|Ψ​\(vs,vg\)\|​Lmax/T\|\\Psi\(v\_\{s\},v\_\{g\}\)\|\\,L\_\{\\max\}/Tfailure\-event term, which vanishes asymptotically but can dominate at moderateTTin dense regimes\.

Absence of guarantees forPathTS\.The analysis above applies only toPathUCB\(Remark[1](https://arxiv.org/html/2607.15440#Thmremark1)\)\. Section[6](https://arxiv.org/html/2607.15440#S6)exhibits an adversarial instance on whichPathTSfails to converge overT=10,000T=10\{,\}000episodes—behavior consistent with theΩ​\(2k∗\)\\Omega\(2^\{k^\{\*\}\}\)obstruction ofWang and Chen \([2018](https://arxiv.org/html/2607.15440#bib.bib38)\)\.PathTStypically outperformsPathUCBin our experiments, but its performance can degrade sharply when the optimal path is long and suboptimal competitors are edge\-disjoint—the regime wherePathUCB’s position\-aware analysis remains tight\.

Further discussions regarding Variance\-awareness and warm\-up cost appear in Appendix[F](https://arxiv.org/html/2607.15440#A6)\.

## 6Experimental Evaluation

We empirically confirm Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)and evaluate practical performance through three experiments: regret\-curve validation \(Section[6\.1](https://arxiv.org/html/2607.15440#S6.SS1)\), comprehensive baseline comparison \(Section[6\.2](https://arxiv.org/html/2607.15440#S6.SS2)\), and scaling analysis \(Section[6\.3](https://arxiv.org/html/2607.15440#S6.SS3)\)\. All results are averaged over 10 random topologies per setting×\\times20 seeds per topology \(200 runs\)\. We consider the following four domains:

1\. Erdős–Rényi random graphsErdös and Rényi \([1959](https://arxiv.org/html/2607.15440#bib.bib27)\)serve as the primary validation domain: directed graphs with edge probability0\.40\.4, reliabilitiespe∼Uniform​\[0\.01,0\.99\]p\_\{e\}\\sim\\text\{Uniform\}\[0\.01,0\.99\], and\(vs,vg\)\(v\_\{s\},v\_\{g\}\)sampled uniformly withvs≠vgv\_\{s\}\\neq v\_\{g\}\.2\. Layered DAGsprovide a controlled path\-diversity benchmark withDDlayers and widthww\(vsv\_\{s\}alone in layer 1,vgv\_\{g\}alone in layerDD, full connectivity between adjacent layers\), giving\|V\|=w​\(D−2\)\+2\|V\|=w\(D\-2\)\+2and\|E\|=2​w\+w2​\(D−3\)\|E\|=2w\+w^\{2\}\(D\-3\)\.3\. Grid worldsaren×nn\\times ngrids with 4\-connectivity,\|V\|=n2\|V\|=n^\{2\},\|E\|=4​n​\(n−1\)\|E\|=4n\(n\-1\),vsv\_\{s\}at the top\-left andvgv\_\{g\}at the bottom\-right; reliabilities uniform on\[0\.01,0\.99\]\[0\.01,0\.99\]\.4\. Quantum repeater networksuse a 25\-node, 43\-edge abstraction of the SURFnet backbone\(Knightet al\.,[2011](https://arxiv.org/html/2607.15440#bib.bib31)\), with edge reliabilities following the standard fiber\-attenuation model\(Wehneret al\.,[2018](https://arxiv.org/html/2607.15440#bib.bib28)\)and endpoints sampled at topological distance≥3\\geq 3\. Full details in Appendix[G](https://arxiv.org/html/2607.15440#A7)\.

Convergence:An algorithm has converged at the first episodettat which its greedy policy \(the path extracted from current estimates without exploration bonuses; details in Appendix[H](https://arxiv.org/html/2607.15440#A8)\) equals someπ∗∈Ψ∗\\pi^\{\*\}\\in\\Psi^\{\*\}for 10 consecutive episodes\. The*convergence rate*is the fraction of \(topology, seed\) runs that converged before horizonTT\.Tie\-breaking:Exact floating\-point ties on path costs are broken by adding independentUniform​\(0,10−8\)\\mathrm\{Uniform\}\(0,10^\{\-8\}\)noise per edge—negligible relative to typical log edge costs\.Hyperparameters:PathUCBusesρ=2\.0\\rho=2\.0in Experiment 1 \(matching Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)\) andρ=1\.0\\rho=1\.0in Experiments 2 and 3 \(selected by a preliminary sweep on Erdős–Rényi optimizing median convergence episode\)\.PathTSuses the defaultBeta​\(1,1\)\\mathrm\{Beta\}\(1,1\)prior\.Baselines\.We compare against six baselines spanning CCB, SSP planning, RL, and ablations as listed below\. Full implementation details are provided in Appendix[I](https://arxiv.org/html/2607.15440#A9)\.

1\. CombCascadeKvetonet al\.\([2015a](https://arxiv.org/html/2607.15440#bib.bib24)\)is the canonical CCB algorithm; we use Dijkstra on−log⁡p^e\-\\log\\hat\{p\}\_\{e\}to implement its maximization oracle \(implementation differences fromPathUCBin Appendix[B](https://arxiv.org/html/2607.15440#A2)\)\.2\. RTDPBartoet al\.\([1993](https://arxiv.org/html/2607.15440#bib.bib33)\)is the standard SSP baseline\.3\. LRTDP\(Bonet and Geffner,[2003](https://arxiv.org/html/2607.15440#bib.bib34)\)extends RTDP with state\-level convergence labeling\.4\. Q\-Learningis a standard tabular RL baseline \(α=0\.1\\alpha=0\.1,γ=0\.99\\gamma=0\.99,ε\\varepsilon\-greedy with decayingε\\varepsilon, optimistic hop\-count initialization\)\.5\. CUCBis a log\-transform ablation: identical toPathUCBbut runs Dijkstra onw​\(e\)=1−p^e​\(t\)w\(e\)=1\-\\hat\{p\}\_\{e\}\(t\)instead of−log⁡p^e​\(t\)\-\\log\\hat\{p\}\_\{e\}\(t\), optimizing the wrong objective\.6\. Randomselects paths via random walks with cycle avoidance and dead\-end restart, providing a worst\-case floor\.

### 6\.1Experiment 1: Regret Curve Validation

We test theO​\(ln⁡T\)O\(\\ln T\)scaling predicted by Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)and compare the two bounds against empirical regret overT=200,000T=200\{,\}000episodes\.

O​\(ln⁡T\)O\(\\ln T\)Scaling\.We fit𝔼​\[R​\(T\)\]≈a​ln⁡T\+b\\mathbb\{E\}\[R\(T\)\]\\approx a\\ln T\+bover 40 log\-spaced episodes for each \(algorithm, domain\) pair \(Figure[1](https://arxiv.org/html/2607.15440#S6.F1); full per\-domain results in Appendix[J\.2](https://arxiv.org/html/2607.15440#A10.SS2)\)\.PathUCB, CombCascade, andPathTSall achieveR2≥0\.96R^\{2\}\\geq 0\.96across the four domains, consistent withO​\(ln⁡T\)O\(\\ln T\)regret \(Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)and Eq\.[6](https://arxiv.org/html/2607.15440#S5.E6)\); slope ranges are66–1717forPathTS\(an order of magnitude smaller than the UCB\-based methods\),9393–168168for CombCascade, and118118–227227forPathUCB\. By contrast, RTDP, LRTDP, and Random haveR2≈0\.75R^\{2\}\\approx 0\.75, suggesting their regret grows approximately linearly inTTrather than logarithmically\. We caution that high log\-linearR2R^\{2\}is suggestive rather than conclusive evidence ofO​\(ln⁡T\)O\(\\ln T\), since slowly\-growing power\-law curves can also fit\. Large standard deviations onR​\(T\)R\(T\)are observed, reflecting variation across random topologies and stochastic edge outcomes\.

Figure 1:Empirical regret of all algorithms across four domains overT=200,000T=200\{,\}000episodes\.![Refer to caption](https://arxiv.org/html/2607.15440v1/x1.png)\(a\)Erdős–Rényi
![Refer to caption](https://arxiv.org/html/2607.15440v1/x2.png)\(b\)Grid World
![Refer to caption](https://arxiv.org/html/2607.15440v1/x3.png)\(c\)Layered DAG
![Refer to caption](https://arxiv.org/html/2607.15440v1/x4.png)\(d\)Quantum Network
![Refer to caption](https://arxiv.org/html/2607.15440v1/x5.png)

Bound Comparison\.We empirically compare the edge\-level CombCascade bound \(Eq\.[6](https://arxiv.org/html/2607.15440#S5.E6)\) and the path\-levelPathUCBbound \(Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)\) againstPathUCB’s empirical regret \(Figure[5](https://arxiv.org/html/2607.15440#A10.F5)in Appendix[J\.1](https://arxiv.org/html/2607.15440#A10.SS1)\)\. Two observations align with Section[5\.2](https://arxiv.org/html/2607.15440#S5.SS2): \(i\) neither bound is uniformly tighter—the path\-level bound dominates on the sparse Layered DAG and Grid domains while the edge\-level bound dominates on the dense Erdős–Rényi and Quantum networks, matching the\|Ψ​\(vs,vg\)\|\|\\Psi\(v\_\{s\},v\_\{g\}\)\|\-vs\-\|E\|\|E\|tradeoff; and \(ii\) both bounds are loose which is consistent with the worst\-case nature of the gap\-dependent constants\. Nonetheless, the logarithmic regret accumulation guarantee \(at the limit\) is still valid and empirically observed over the2×1052\\times 10^\{5\}episodes\.

### 6\.2Experiment 2: Comprehensive Baseline Comparison

We evaluate all agents on the four primary domains overT=10,000T=10\{,\}000episodes \(Figure[2](https://arxiv.org/html/2607.15440#S6.F2)—bottom\-right is best\), then introduce a fifth adversarial domain,*Path Trap*, to stress\-testPathTSon the structure underlying Remark[1](https://arxiv.org/html/2607.15440#Thmremark1)\.

Figure 2:Empirical regretR​\(T\)±95%R\(T\)\\pm 95\\%CI atT=10,000T=10\{,\}000episodes, \(y\-axis\) versus convergence rate \(x\-axis\) for each algorithm across the four primary domains with domain size \(\|V\|\|V\|\) in parenthesis\.Bottom\-right is better\.![Refer to caption](https://arxiv.org/html/2607.15440v1/x6.png)\(a\)Erdős\-Rényi \(13\)
![Refer to caption](https://arxiv.org/html/2607.15440v1/x7.png)\(b\)Grid World \(36\)
![Refer to caption](https://arxiv.org/html/2607.15440v1/x8.png)\(c\)Layered DAG \(17\)
![Refer to caption](https://arxiv.org/html/2607.15440v1/x9.png)\(d\)Quantum Network \(25\)
![Refer to caption](https://arxiv.org/html/2607.15440v1/x10.png)

Primary Results\.PathTSachieves the lowest final regret on all four domains by a substantial margin—4×4\\timesto10×10\\timeslower thanPathUCBand CombCascade\. The three bandit\-style algorithms converge to an optimal policy in≥85%\\geq 85\\%of runs, while RTDP and LRTDP converge in only0–46%46\\%, confirming that SSP solvers are ill\-suited toSRP: the closed\-loop machinery they invoke is unnecessary under open\-loop equivalence \(Lemma[1](https://arxiv.org/html/2607.15440#Thmtheorem1)\) and does not exploit the combinatorial\-bandit structure\. LRTDP underperforms RTDP on every domain, plausibly because its convergence labeling locks in optimistic bias that RTDP eventually corrects via continued backupsMcMahanet al\.\([2005](https://arxiv.org/html/2607.15440#bib.bib32)\)—an effect amplified bySRP’s severe global\-reset penalty\.Log\-Transform Ablation\.CUCB underperformsPathUCBon every domain, incurring1\.2×1\.2\\times–2\.1×2\.1\\timeshigher final regret and lower convergence rates \(e\.g\.,47%47\\%vs\.89%89\\%on Grid World\)\. The gap confirms the necessity of the log\-transform \(Lemma[2](https://arxiv.org/html/2607.15440#Thmtheorem2)\): CUCB biases path selection toward edge\-rich, low\-individual\-failure routes rather than multiplicatively reliable ones\.

Figure 3:Path Trap topology\.![Refer to caption](https://arxiv.org/html/2607.15440v1/x11.png)Exploration Failure of Thompson Sampling\.*Path Trap*\(Figure[3](https://arxiv.org/html/2607.15440#S6.F3)\) is a deterministic\-parameter graph with a 7\-hop optimal chain \(pchain=0\.95p\_\{\\text\{chain\}\}=0\.95,P​\(π∗\)≈0\.698P\(\\pi^\{\*\}\)\\approx 0\.698\), a 2\-hop shortcut \(pshortcut=0\.75p\_\{\\text\{shortcut\}\}=0\.75,P≈0\.563P\\approx 0\.563each\), and one direct edge \(pdirect=0\.55p\_\{\\text\{direct\}\}=0\.55\)\. Edge probabilities are fixed; outcomes remain stochastic\. The construction penalizes algorithms that over\-commit to short paths with frequent positive feedback rather than explore the longer but more reliable chain—the failure mode of combinatorial Thompson Sampling on multiplicative\-reward instancesWang and Chen \([2018](https://arxiv.org/html/2607.15440#bib.bib38)\)\.

Figure 4:Regret vs\. convergence on the Path Trap domain\. Markers as in Figure[2](https://arxiv.org/html/2607.15440#S6.F2)\.![Refer to caption](https://arxiv.org/html/2607.15440v1/x12.png)As illustrated in Figure[4](https://arxiv.org/html/2607.15440#S6.F4),PathTS’s regret reachesR​\(T\)=1,421R\(T\)=1\{,\}421—worse than Random \(986986, which selects the optimal chain with probability1/31/3\)—whilePathUCBachieves the best result,R​\(T\)=66R\(T\)=66with100%100\\%convergence\. The asymmetry reflects the difference between UCB optimism and Thompson Sampling on this instance: the shortcuts generate frequent positive feedback that rapidly concentratesPathTS’s Beta posteriors around the suboptimal alternatives, whilePathUCBmaintains inflated estimates for the under\-explored chain edges via its UCB confidence radius and eventually routes along the optimal path\. This is consistent with theΩ​\(2k∗\)\\Omega\(2^\{k^\{\*\}\}\)obstruction ofWang and Chen \([2018](https://arxiv.org/html/2607.15440#bib.bib38)\)\(Theorem 3\) for combinatorial Thompson Sampling on multiplicative\-reward instances\. Withk∗=7k^\{\*\}=7, Path Trap sits in the regime where this obstruction predicts difficulty within practical horizons\. The practical takeaway is not thatPathTSshould be avoided—it remains the strongest performer on every other domain we tested—but that adversarial instances exist on which posterior\-sampling can fail dramatically, andPathUCB’s theoretical guarantee provides the safer fallback\.

### 6\.3Experiment 3: Scaling Analysis

A scaling study \(full results in Appendix[J\.3](https://arxiv.org/html/2607.15440#A10.SS3)\) confirms two trends\. First, on both Erdős–Rényi \(where\|Ψ​\(vs,vg\)\|\|\\Psi\(v\_\{s\},v\_\{g\}\)\|grows super\-polynomially in\|V\|\|V\|\) and Layered DAG \(where it grows polynomially in widthww\),PathUCBandPathTSexhibit approximately linear regret growth in\|E\|\|E\|, indicating edge\-count scalability; in dense graphs\|E\|=O​\(\|V\|2\)\|E\|=O\(\|V\|^\{2\}\), so this translates to polynomial\-in\-\|V\|\|V\|scaling\. Second, on Erdős–Rényi with\|V\|=15\|V\|=15, regret grows super\-linearly as the support spanpmax−pminp\_\{\\max\}\-p\_\{\\min\}shrinks, consistent with the gap\-dependent factor1/Δ​\(π\)1/\\Delta\(\\pi\)in Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5): as edge reliabilities concentrate, path reliabilities cluster and the per\-path gapsΔ​\(π\)\\Delta\(\\pi\)shrink approximately with the span\.

## 7Conclusion

We introduced*Stochastic Reset Pathfinding*\(SRP\) and showed that its global\-reset structure makes the optimal policy open\-loop, placing the problem within the combinatorial cascading bandit framework\. Building on this reduction, we developed a path\-level regret bound forPathUCBvia a per\-path complexityC​\(π\)C\(\\pi\)that captures how each edge’s prefix and suffix reliability jointly determine its contribution\. Our experiments validate theO​\(ln⁡T\)O\(\\ln T\)rate, demonstrate the strong empirical performance of the Thompson Sampling instantiationPathTS, and exhibit an adversarial instance on whichPathTSfails—consistent with a known exponential obstruction\. Natural future directions include a variance\-aware \(Bernstein\) extension of the path\-level analysis, a regret bound forPathTSbridging existing matroid\- and semi\-bandit\-style results, and adaptation of CombCascade’s prefix argument to close the warm\-up gap in1/QL​\(π\)1/Q\_\{L\}\(\\pi\)\.

## References

- \[1\]\(2002\-05\)Finite\-time analysis of the multiarmed bandit problem\.47\(2–3\),pp\. 235–256\.External Links:ISSN 0885\-6125,[Link](https://doi.org/10.1023/A:1013689704352),[Document](https://dx.doi.org/10.1023/A%3A1013689704352)Cited by:[§4\.1](https://arxiv.org/html/2607.15440#S4.SS1.p1.5)\.
- \[2\]A\. Barto, S\. Bradtke, and S\. Singh\(1993\-02\)Learning to act using real\-time dynamic programming\.Artificial Intelligence72,pp\. 81–138\.External Links:[Document](https://dx.doi.org/10.1016/0004-3702%2894%2900011-O)Cited by:[§I\.2](https://arxiv.org/html/2607.15440#A9.SS2.p1.9),[§1](https://arxiv.org/html/2607.15440#S1.p2.2),[§6](https://arxiv.org/html/2607.15440#S6.p4.7)\.
- \[3\]B\. Bonet and H\. Geffner\(2003\)Labeled rtdp: improving the convergence of real\-time dynamic programming\.InProceedings of the Thirteenth International Conference on International Conference on Automated Planning and Scheduling,ICAPS’03,pp\. 12–21\.External Links:ISBN 1577351878Cited by:[§I\.3](https://arxiv.org/html/2607.15440#A9.SS3.p1.1),[§1](https://arxiv.org/html/2607.15440#S1.p2.2),[§6](https://arxiv.org/html/2607.15440#S6.p4.7)\.
- \[4\]K\. Chakraborty, D\. Elkouss, B\. Rijsman, and S\. Wehner\(2020\)Entanglement distribution in a quantum network: a multicommodity flow\-based approach\.IEEE Transactions on Quantum Engineering1,pp\. 1–21\.Cited by:[Appendix G](https://arxiv.org/html/2607.15440#A7.p1.2),[§1](https://arxiv.org/html/2607.15440#S1.p1.1)\.
- \[5\]O\. Chapelle and L\. Li\(2011\)An empirical evaluation of thompson sampling\.Advances in neural information processing systems24\.Cited by:[Appendix A](https://arxiv.org/html/2607.15440#A1.p3.1)\.
- \[6\]W\. C\. Cheung, V\. Tan, and Z\. Zhong\(2019\-16–18 Apr\)A thompson sampling algorithm for cascading bandits\.InProceedings of the Twenty\-Second International Conference on Artificial Intelligence and Statistics,K\. Chaudhuri and M\. Sugiyama \(Eds\.\),Proceedings of Machine Learning Research, Vol\.89,pp\. 438–447\.External Links:[Link](https://proceedings.mlr.press/v89/cheung19a.html)Cited by:[Appendix A](https://arxiv.org/html/2607.15440#A1.p1.1),[Appendix A](https://arxiv.org/html/2607.15440#A1.p3.1),[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px2.p1.2),[Remark 1](https://arxiv.org/html/2607.15440#Thmremark1.p1.1)\.
- \[7\]A\. Cohen, H\. Kaplan, Y\. Mansour, and A\. Rosenberg\(2020\)Near\-optimal regret bounds for stochastic shortest path\.InProceedings of the 37th International Conference on Machine Learning,ICML’20\.Cited by:[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px3.p1.1)\.
- \[8\]J\. R\. Daniel, V\. R\. Benjamin, K\. Abbas, O\. Ian, and W\. Zheng\(2018\)A tutorial on thompson sampling\.Foundations and Trends® in Machine Learning11\(1\),pp\. 1–99\.Cited by:[§4\.2](https://arxiv.org/html/2607.15440#S4.SS2.p1.4)\.
- \[9\]M\. H\. DeGroot\(2005\)Optimal statistical decisions\.John Wiley & Sons\.Cited by:[§4\.2](https://arxiv.org/html/2607.15440#S4.SS2.p1.4)\.
- \[10\]E\. Dijkstra\(1959\)A note on two problems in connexion with graphs\.Numerische Mathematik1\(1\),pp\. 269–271\.Cited by:[Lemma 2](https://arxiv.org/html/2607.15440#Thmtheorem2.p1.5.5)\.
- \[11\]Y\. Du, R\. Srikant, and W\. Chen\(2024\)Cascading reinforcement learning\.InThe Twelfth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=KjOAHlKMF5)Cited by:[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px1.p1.3)\.
- \[12\]P\. Erdös and A\. Rényi\(1959\)On random graphs i\.Publicationes Mathematicae Debrecen6,pp\. 290\.Cited by:[§6](https://arxiv.org/html/2607.15440#S6.p2.18)\.
- \[13\]M\. Jafarnia\-Jahromi, L\. Chen, R\. Jain, and H\. Luo\(2023\-31 Jul–04 Aug\)Posterior sampling\-based online learning for the stochastic shortest path model\.InProceedings of the Thirty\-Ninth Conference on Uncertainty in Artificial Intelligence,R\. J\. Evans and I\. Shpitser \(Eds\.\),Proceedings of Machine Learning Research, Vol\.216,pp\. 922–931\.External Links:[Link](https://proceedings.mlr.press/v216/jafarnia-jahromi23a.html)Cited by:[§1](https://arxiv.org/html/2607.15440#S1.p2.2),[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px3.p1.1)\.
- \[14\]E\. Johnson, A\. Rumi, C\. Pike\-Burke, and P\. Rebeschini\(2025\)Stochastic shortest path with sparse adversarial costs\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=u7eIoTviuM)Cited by:[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px3.p1.1)\.
- \[15\]S\. Knight, H\. X\. Nguyen, N\. Falkner, R\. Bowden, and M\. Roughan\(2011\)The internet topology zoo\.IEEE Journal on Selected Areas in Communications29\(9\),pp\. 1765–1775\.Cited by:[Appendix G](https://arxiv.org/html/2607.15440#A7.p1.2),[§6](https://arxiv.org/html/2607.15440#S6.p2.18)\.
- \[16\]B\. Kveton, C\. Szepesvári, Z\. Wen, and A\. Ashkan\(2015\)Cascading bandits: learning to rank in the cascade model\.InProceedings of the 32nd International Conference on Machine Learning \- Volume 37,ICML’15,pp\. 767–776\.Cited by:[Appendix F](https://arxiv.org/html/2607.15440#A6.SS0.SSS0.Px2.p1.4),[§I\.1](https://arxiv.org/html/2607.15440#A9.SS1.p1.4),[2nd item](https://arxiv.org/html/2607.15440#S1.I1.i2.p1.1),[§1](https://arxiv.org/html/2607.15440#S1.p2.2),[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px1.p1.3),[§5\.1](https://arxiv.org/html/2607.15440#S5.SS1.p3.3),[§5](https://arxiv.org/html/2607.15440#S5.p1.1),[§5](https://arxiv.org/html/2607.15440#S5.p2.1),[§6](https://arxiv.org/html/2607.15440#S6.p4.7)\.
- \[17\]B\. Kveton, Z\. Wen, A\. Ashkan, and C\. Szepesvari\(2015\)Combinatorial cascading bandits\.Advances in Neural Information Processing Systems28\.Cited by:[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px1.p1.3)\.
- \[18\]T\. L\. Lai and H\. Robbins\(1985\)Asymptotically efficient adaptive allocation rules\.Advances in applied mathematics6\(1\),pp\. 4–22\.Cited by:[§4\.1](https://arxiv.org/html/2607.15440#S4.SS1.p1.5)\.
- \[19\]T\. Lattimore and C\. Szepesvári\(2020\)Bandit algorithms\.Cambridge University Press\.Cited by:[Appendix C](https://arxiv.org/html/2607.15440#A3.1.p1.4),[Appendix D](https://arxiv.org/html/2607.15440#A4.1.p1.13)\.
- \[20\]S\. Li, B\. Wang, S\. Zhang, and W\. Chen\(2016\-20–22 Jun\)Contextual combinatorial cascading bandits\.InProceedings of The 33rd International Conference on Machine Learning,M\. F\. Balcan and K\. Q\. Weinberger \(Eds\.\),Proceedings of Machine Learning Research, Vol\.48,New York, New York, USA,pp\. 1245–1253\.External Links:[Link](https://proceedings.mlr.press/v48/lif16.html)Cited by:[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px1.p1.3)\.
- \[21\]S\.N\. Maheshwari\(1974\)B74\-36 communication, transmission, and transportation networks\.IEEE Transactions on ComputersC\-23\(8\),pp\. 878–878\.External Links:[Document](https://dx.doi.org/10.1109/T-C.1974.224044)Cited by:[§2\.1](https://arxiv.org/html/2607.15440#S2.SS1.p2.1)\.
- \[22\]H\. B\. McMahan, M\. Likhachev, and G\. J\. Gordon\(2005\)Bounded real\-time dynamic programming: rtdp with monotone upper bounds and performance guarantees\.InProceedings of the 22nd international conference on Machine learning,pp\. 569–576\.Cited by:[§6\.2](https://arxiv.org/html/2607.15440#S6.SS2.p2.9)\.
- \[23\]R\. Pickhardt and S\. Richter\(2021\)Optimally reliable & cheap payment flows on the lightning network\.arXiv preprint arXiv:2107\.05322\.Cited by:[§1](https://arxiv.org/html/2607.15440#S1.p1.1)\.
- \[24\]M\. L\. Puterman\(2014\)Markov decision processes: discrete stochastic dynamic programming\.John Wiley & Sons\.Cited by:[§2\.1](https://arxiv.org/html/2607.15440#S2.SS1.1.p1.1)\.
- \[25\]M\. S\. Talebi, Z\. Zou, R\. Combes, A\. Proutiere, and M\. Johansson\(2018\)Stochastic online shortest path routing: the value of feedback\.IEEE Transactions on Automatic Control63\(4\),pp\. 915–930\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2017.2747409)Cited by:[§1](https://arxiv.org/html/2607.15440#S1.p1.1),[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px1.p1.3)\.
- \[26\]J\. Tarbouriech, M\. Pirotta, M\. Valko, and A\. Lazaric\(2021\-16–19 Mar\)Sample complexity bounds for stochastic shortest path with a generative model\.InProceedings of the 32nd International Conference on Algorithmic Learning Theory,V\. Feldman, K\. Ligett, and S\. Sabato \(Eds\.\),Proceedings of Machine Learning Research, Vol\.132,pp\. 1157–1178\.External Links:[Link](https://proceedings.mlr.press/v132/tarbouriech21a.html)Cited by:[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px3.p1.1)\.
- \[27\]W\. R\. Thompson\(1933\)On the likelihood that one unknown probability exceeds another in view of the evidence of two samples\.Biometrika25\(3/4\),pp\. 285–294\.Cited by:[§4\.2](https://arxiv.org/html/2607.15440#S4.SS2.p1.4)\.
- \[28\]D\. Vial, S\. Sanghavi, S\. Shakkottai, and R\. Srikant\(2022\)Minimax regret for cascading bandits\.InProceedings of the 36th International Conference on Neural Information Processing Systems,NIPS ’22,Red Hook, NY, USA\.External Links:ISBN 9781713871088Cited by:[Appendix F](https://arxiv.org/html/2607.15440#A6.SS0.SSS0.Px1.p1.2)\.
- \[29\]S\. Wang and W\. Chen\(2018\)Thompson sampling for combinatorial semi\-bandits\.InInternational Conference on Machine Learning,pp\. 5114–5122\.Cited by:[Appendix A](https://arxiv.org/html/2607.15440#A1.p1.1),[Appendix A](https://arxiv.org/html/2607.15440#A1.p3.1),[4th item](https://arxiv.org/html/2607.15440#S1.I1.i4.p1.1),[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px2.p1.2),[§5\.2](https://arxiv.org/html/2607.15440#S5.SS2.p2.2),[§6\.2](https://arxiv.org/html/2607.15440#S6.SS2.p3.5),[§6\.2](https://arxiv.org/html/2607.15440#S6.SS2.p4.7),[Remark 1](https://arxiv.org/html/2607.15440#Thmremark1.p1.1)\.
- \[30\]S\. Wehner, D\. Elkouss, and R\. Hanson\(2018\-10\)Quantum internet: a vision for the road ahead\.Science362,pp\. eaam9288\.External Links:[Document](https://dx.doi.org/10.1126/science.aam9288)Cited by:[Appendix G](https://arxiv.org/html/2607.15440#A7.p2.6),[§1](https://arxiv.org/html/2607.15440#S1.p1.1),[§6](https://arxiv.org/html/2607.15440#S6.p2.18)\.
- \[31\]J\. Xie, C\. Chen, Z\. Wang, and S\. Li\(2025\)Cascading bandits robust to adversarial corruptions\.External Links:2502\.08077,[Link](https://arxiv.org/abs/2502.08077)Cited by:[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px1.p1.3)\.
- \[32\]R\. Zhu and E\. H\. Modiano\(2018\)Learning to route efficiently with end\-to\-end feedback: the value of networked structure\.CoRRabs/1810\.10637\.External Links:[Link](http://arxiv.org/abs/1810.10637),1810\.10637Cited by:[§3](https://arxiv.org/html/2607.15440#S3.SS0.SSS0.Px1.p1.3)\.

## Appendix ATheoretical Status ofPathTS: Extended Discussion

The two prior analyses closest toPathTSare those of Cheung et al\.\[[6](https://arxiv.org/html/2607.15440#bib.bib21)\]and Wang & Chen\[[29](https://arxiv.org/html/2607.15440#bib.bib38)\]\. Neither directly extends toSRP\. Cheung et al\. prove anO​\(L​log⁡T/Δ\)O\(L\\log T/\\Delta\)regret bound for Beta\-Bernoulli Thompson Sampling on cascading bandits, but their analysis relies on the uniform matroid structure of the top\-K feasible set—specifically, exchangeability of items in the optimal solution—which fails for general graph paths\.

Wang & Chen analyze combinatorial Thompson Sampling for general CMAB with multiplicative rewards, but under semi\-bandit rather than cascade feedback\. Adapting their concentration arguments to cascade observations introduces position\-dependent factors that, in our analysis, take the form of the prefix reliabilitiesQi​\(π\)Q\_\{i\}\(\\pi\)governing per\-edge observation probabilities \(Definition[5](https://arxiv.org/html/2607.15440#Thmdefinition5)and the warm\-up term in Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)\)\. Their Theorem 3 also exhibits an instance with conjunctive product reward on which any Beta\-Bernoulli TS variant provably incursΩ​\(2k∗\)\\Omega\(2^\{k^\{\*\}\}\)regret, wherek∗k^\{\*\}is the size of the optimal solution\.

Together, these results suggest that a regret analysis forPathTSis within reach but would require combining\[[29](https://arxiv.org/html/2607.15440#bib.bib38)\]’s general\-feasible\-set techniques with\[[6](https://arxiv.org/html/2607.15440#bib.bib21)\]’s cascade\-feedback handling, and may inherit a path\-length\-exponential leading constant\.PathTSis presented as a practical alternative motivated by the strong empirical performance of Thompson Sampling in combinatorial settings\[[5](https://arxiv.org/html/2607.15440#bib.bib39),[29](https://arxiv.org/html/2607.15440#bib.bib38),[6](https://arxiv.org/html/2607.15440#bib.bib21)\]; see Section[6\.2](https://arxiv.org/html/2607.15440#S6.SS2)\.

## Appendix BImplementation Differences BetweenPathUCBand CombCascade

PathUCBand CombCascade share the same algorithmic template \(per\-edge UCB, log\-transformed shortest path selection\) but differ in three implementation choices:

Initialization\.PathUCBsetsp^e​\(t\)=1\\hat\{p\}\_\{e\}\(t\)=1for unvisited edges, ensuring strict optimism on the first visit\. CombCascade assumes an initial sweep that draws a Bernoulli outcome for every edge before the main loop, guaranteeingNe​\(t\)≥1N\_\{e\}\(t\)\\geq 1throughout\.

Confidence radius\.PathUCBusesρ​ln⁡t/Ne​\(t\)\\sqrt\{\\rho\\ln t/N\_\{e\}\(t\)\}withρ≥2\\rho\\geq 2\. CombCascade uses1\.5​ln⁡\(t−1\)/Tt−1​\(e\)\\sqrt\{1\.5\\ln\(t\-1\)/T\_\{t\-1\}\(e\)\}\. Both yieldt−3t^\{\-3\}tail probabilities under Hoeffding’s inequality\.

Clamping\.PathUCBclips two\-sided to\[pmin,1\]\[p\_\{\\min\},1\]\. CombCascade clips only above at11\(no lower clamp\)\.

The strict optimism and the upper clamp at11are used in Lemma[3](https://arxiv.org/html/2607.15440#Thmtheorem3)to bound the prefix product and isolate the suffix\-weighted overestimation sum that drives the path\-level analysis\. The lower clamp atpminp\_\{\\min\}keeps log\-weights finite throughout learning\. Apart from CombCascade’s initial sweep, the two algorithms perform comparably in our experiments \(Section[6](https://arxiv.org/html/2607.15440#S6)\)\.

## Appendix CConcentration Lemmas for the Clamped UCB Estimator

Both Lemmas[7](https://arxiv.org/html/2607.15440#Thmtheorem7)and[8](https://arxiv.org/html/2607.15440#Thmtheorem8)reduce to a single two\-sided concentration claim for the empirical meanp¯e​\(t\)\\bar\{p\}\_\{e\}\(t\)\.

###### Lemma 6\(Two\-Sided Concentration\)\.

Underρ≥2\\rho\\geq 2, for eache∈Ee\\in Eandt≥1t\\geq 1,

Pr⁡\(\|p¯e​\(t\)−pe\|≤ρ​ln⁡tNe​\(t\)\|Ne​\(t\)≥1\)≥1−2​t−3\.\\Pr\\\!\\left\(\\,\|\\bar\{p\}\_\{e\}\(t\)\-p\_\{e\}\|\\leq\\sqrt\{\\tfrac\{\\rho\\ln t\}\{N\_\{e\}\(t\)\}\}\\;\\Big\|\\;N\_\{e\}\(t\)\\geq 1\\right\)\\;\\geq\\;1\-2t^\{\-3\}\.\(13\)

###### Proof\.

By the fictitious sampling argument\[[19](https://arxiv.org/html/2607.15440#bib.bib42)\], couple the observed outcomes of edgeeeto a fixed i\.i\.d\. sequenceY1,Y2,⋯∼Bernoulli​\(pe\)Y\_\{1\},Y\_\{2\},\\dots\\sim\\mathrm\{Bernoulli\}\(p\_\{e\}\), sop¯e​\(t\)=1Ne​\(t\)​∑j=1Ne​\(t\)Yj\\bar\{p\}\_\{e\}\(t\)=\\tfrac\{1\}\{N\_\{e\}\(t\)\}\\sum\_\{j=1\}^\{N\_\{e\}\(t\)\}Y\_\{j\}\. SinceNe​\(t\)∈\{1,…,t\}N\_\{e\}\(t\)\\in\\\{1,\\dots,t\\\}is data\-dependent, a union bound combined with Hoeffding’s inequality gives

Pr⁡\(∃n∈\{1,…,t\}:\|1n​∑j=1nYj−pe\|\>ρ​ln⁡tn\)≤2​∑n=1te−2​ρ​ln⁡t=2​t1−2​ρ,\\Pr\\\!\\left\(\\exists\\,n\\in\\\{1,\\dots,t\\\}\\,:\\,\\bigl\|\\tfrac\{1\}\{n\}\\\!\\sum\_\{j=1\}^\{n\}\\\!Y\_\{j\}\-p\_\{e\}\\bigr\|\>\\sqrt\{\\tfrac\{\\rho\\ln t\}\{n\}\}\\right\)\\leq 2\\\!\\sum\_\{n=1\}^\{t\}e^\{\-2\\rho\\ln t\}=2t^\{1\-2\\rho\},which is at most2​t−32t^\{\-3\}forρ≥2\\rho\\geq 2\. ∎

###### Lemma 7\(UCB Optimism\)\.

Under Assumption[1](https://arxiv.org/html/2607.15440#Thmassumption1)withρ≥2\\rho\\geq 2,Pr⁡\(𝒪t\)≥1−\|E\|​t−3\\Pr\(\\mathcal\{O\}\_\{t\}\)\\geq 1\-\|E\|\\,t^\{\-3\}for allt≥1t\\geq 1\. Consequently, the cumulative expected regret on episodes where𝒪tc\\mathcal\{O\}\_\{t\}^\{c\}holds isO​\(\|E\|\)O\(\|E\|\), independent ofTT\.

###### Proof of Lemma[7](https://arxiv.org/html/2607.15440#Thmtheorem7)\.

Fixe∈Ee\\in Eandt≥1t\\geq 1\. IfNe​\(t\)=0N\_\{e\}\(t\)=0, thenp^e​\(t\)=1\>pe\\hat\{p\}\_\{e\}\(t\)=1\>p\_\{e\}deterministically\. IfNe​\(t\)≥1N\_\{e\}\(t\)\\geq 1, the event\{p^e​\(t\)<pe\}\\\{\\hat\{p\}\_\{e\}\(t\)<p\_\{e\}\\\}impliesp¯e​\(t\)−pe<−ρ​ln⁡t/Ne​\(t\)\\bar\{p\}\_\{e\}\(t\)\-p\_\{e\}<\-\\sqrt\{\\rho\\ln t/N\_\{e\}\(t\)\}, which has probability at mostt−3t^\{\-3\}by the lower\-tail half of Lemma[6](https://arxiv.org/html/2607.15440#Thmtheorem6)\. A union bound over\|E\|\|E\|edges yieldsPr⁡\(𝒪tc\)≤\|E\|​t−3\\Pr\(\\mathcal\{O\}\_\{t\}^\{c\}\)\\leq\|E\|\\,t^\{\-3\}\. The cumulative\-regret claim follows fromr​\(πt\)≤1r\(\\pi\_\{t\}\)\\leq 1and∑t=1∞t−3<∞\\sum\_\{t=1\}^\{\\infty\}t^\{\-3\}<\\infty\. ∎

###### Lemma 8\(UCB Convergence Rate\)\.

Under Assumption[1](https://arxiv.org/html/2607.15440#Thmassumption1)withρ≥2\\rho\\geq 2, for any edgee∈Ee\\in Eand any episodettwithNe​\(t\)\>0N\_\{e\}\(t\)\>0,

δe​\(t\)≤2​ρ​ln⁡tNe​\(t\)\\delta\_\{e\}\(t\)\\;\\leq\\;2\\sqrt\{\\frac\{\\rho\\ln t\}\{N\_\{e\}\(t\)\}\}\(14\)with probability at least1−t−31\-t^\{\-3\}\.

###### Proof of Lemma[8](https://arxiv.org/html/2607.15440#Thmtheorem8)\.

Fixe∈Ee\\in EandttwithNe​\(t\)≥1N\_\{e\}\(t\)\\geq 1\. LetUe​\(t\)=p¯e​\(t\)\+ρ​ln⁡t/Ne​\(t\)U\_\{e\}\(t\)=\\bar\{p\}\_\{e\}\(t\)\+\\sqrt\{\\rho\\ln t/N\_\{e\}\(t\)\}be the unclamped UCB, sop^e​\(t\)=clip​\(Ue​\(t\),pmin,1\)\\hat\{p\}\_\{e\}\(t\)=\\mathrm\{clip\}\(U\_\{e\}\(t\),p\_\{\\min\},1\)\. Clamping atpminp\_\{\\min\}only decreasesp^e​\(t\)\\hat\{p\}\_\{e\}\(t\)belowpep\_\{e\}\(givingδe​\(t\)≤0\\delta\_\{e\}\(t\)\\leq 0\); clamping at11givesδe​\(t\)=1−pe≤Ue​\(t\)−pe\\delta\_\{e\}\(t\)=1\-p\_\{e\}\\leq U\_\{e\}\(t\)\-p\_\{e\}sinceUe​\(t\)≥1U\_\{e\}\(t\)\\geq 1in that case; the unclamped case givesδe​\(t\)=Ue​\(t\)−pe\\delta\_\{e\}\(t\)=U\_\{e\}\(t\)\-p\_\{e\}directly\. In all cases,

δe​\(t\)≤Ue​\(t\)−pe=\(p¯e​\(t\)−pe\)\+ρ​ln⁡t/Ne​\(t\)\.\\delta\_\{e\}\(t\)\\leq U\_\{e\}\(t\)\-p\_\{e\}=\(\\bar\{p\}\_\{e\}\(t\)\-p\_\{e\}\)\+\\sqrt\{\\rho\\ln t/N\_\{e\}\(t\)\}\.By the upper\-tail half of Lemma[6](https://arxiv.org/html/2607.15440#Thmtheorem6),p¯e​\(t\)−pe≤ρ​ln⁡t/Ne​\(t\)\\bar\{p\}\_\{e\}\(t\)\-p\_\{e\}\\leq\\sqrt\{\\rho\\ln t/N\_\{e\}\(t\)\}with probability at least1−t−31\-t^\{\-3\}, givingδe​\(t\)≤2​ρ​ln⁡t/Ne​\(t\)\\delta\_\{e\}\(t\)\\leq 2\\sqrt\{\\rho\\ln t/N\_\{e\}\(t\)\}\. ∎

## Appendix DPath\-Conditional Observation Bound \(Lemma[9](https://arxiv.org/html/2607.15440#Thmtheorem9)\)

For brevity, letNeiπ​\(t\)N\_\{e\_\{i\}\}^\{\\pi\}\(t\)denote the number of selections ofπ\\piwithin the firstttepisodes in which edgeeie\_\{i\}at positioniiwas observed\.

###### Lemma 9\(Path\-Conditional Observation Bound\)\.

Under Assumption[1](https://arxiv.org/html/2607.15440#Thmassumption1), fix a pathπ\\piand positioni∈\{1,…,\|π\|\}i\\in\\\{1,\\dots,\|\\pi\|\\\}\. With probability at least1−T−21\-T^\{\-2\},

Neiπ​\(t\)≥Qi​\(π\)2​Mπ​\(t\)for all​t≤T​with​Mπ​\(t\)≥24​ln⁡TQi​\(π\)\.N\_\{e\_\{i\}\}^\{\\pi\}\(t\)\\;\\geq\\;\\frac\{Q\_\{i\}\(\\pi\)\}\{2\}\\,M\_\{\\pi\}\(t\)\\qquad\\text\{for all \}t\\leq T\\text\{ with \}M\_\{\\pi\}\(t\)\\geq\\frac\{24\\ln T\}\{Q\_\{i\}\(\\pi\)\}\.\(15\)

###### Proof\.

For each edgee∈πe\\in\\pi, letY1e,Y2e,⋯∼Bernoulli​\(pe\)Y^\{e\}\_\{1\},Y^\{e\}\_\{2\},\\dots\\sim\\mathrm\{Bernoulli\}\(p\_\{e\}\)be the exogenous fictitious\-sampling sequence\[[19](https://arxiv.org/html/2607.15440#bib.bib42)\], with eachYneY^\{e\}\_\{n\}giving the outcome ofeeon itsnn\-th attempt across the entire history\. On thejj\-th episode in whichπ\\piis selected, the observation indicatorIjI\_\{j\}—which equals11iff edgese1,…,ei−1e\_\{1\},\\dots,e\_\{i\-1\}all succeed on that episode—is determined by reading the next unused outcome from each of thei−1i\-1prefix sequences\. Because the prefix edges’ fictitious sequences are mutually independent,IjI\_\{j\}is, conditionally on the past, a Bernoulli draw with parameterQi​\(π\)=∏k<ipekQ\_\{i\}\(\\pi\)=\\prod\_\{k<i\}p\_\{e\_\{k\}\}\.

The counterMπ​\(t\)M\_\{\\pi\}\(t\)is data\-dependent: past outcomes influence UCB estimates and hence subsequent path selections\. We handle this via a union bound over the possible values ofMπ​\(t\)M\_\{\\pi\}\(t\)\. For each fixedm∈\{1,…,T\}m\\in\\\{1,\\dots,T\\\}, the partial sum∑j=1mIj\\sum\_\{j=1\}^\{m\}I\_\{j\}stochastically dominates aBinomial​\(m,Qi​\(π\)\)\\mathrm\{Binomial\}\(m,Q\_\{i\}\(\\pi\)\)random variable along the coupled sequences, so the multiplicative Chernoff bound withδ=1/2\\delta=1/2gives

Pr⁡\(∑j=1mIj<Qi​\(π\)​m2\)≤exp⁡\(−Qi​\(π\)​m8\)≤T−3\\Pr\\\!\\left\(\\sum\_\{j=1\}^\{m\}I\_\{j\}<\\frac\{Q\_\{i\}\(\\pi\)\\,m\}\{2\}\\right\)\\;\\leq\\;\\exp\\\!\\left\(\-\\frac\{Q\_\{i\}\(\\pi\)\\,m\}\{8\}\\right\)\\;\\leq\\;T^\{\-3\}\(16\)wheneverm≥24​ln⁡T/Qi​\(π\)m\\geq 24\\ln T/Q\_\{i\}\(\\pi\)\. A union bound over the at mostTTsuch values ofmmgives total failure probability at mostT−2T^\{\-2\}\. On the complementary event,Neiπ​\(t\)=∑j=1Mπ​\(t\)Ij≥Qi​\(π\)​Mπ​\(t\)/2N\_\{e\_\{i\}\}^\{\\pi\}\(t\)=\\sum\_\{j=1\}^\{M\_\{\\pi\}\(t\)\}I\_\{j\}\\geq Q\_\{i\}\(\\pi\)\\,M\_\{\\pi\}\(t\)/2for everyt≤Tt\\leq TwithMπ​\(t\)≥24​ln⁡T/Qi​\(π\)M\_\{\\pi\}\(t\)\\geq 24\\ln T/Q\_\{i\}\(\\pi\)\. ∎

## Appendix EPath\-Dependent Regret ofPathUCB\(Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)\)

###### Proof of Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)\.

Let𝒢\\mathcal\{G\}denote the joint event on which Lemmas[7](https://arxiv.org/html/2607.15440#Thmtheorem7),[8](https://arxiv.org/html/2607.15440#Thmtheorem8), and[9](https://arxiv.org/html/2607.15440#Thmtheorem9)all hold for everyt≤Tt\\leq T, edge, path, and position\. We split𝔼​\[R​\(T\)\]=𝔼​\[R​\(T\)​𝟏𝒢\]\+𝔼​\[R​\(T\)​𝟏𝒢c\]\\mathbb\{E\}\[R\(T\)\]=\\mathbb\{E\}\[R\(T\)\\mathbf\{1\}\_\{\\mathcal\{G\}\}\]\+\\mathbb\{E\}\[R\(T\)\\mathbf\{1\}\_\{\\mathcal\{G\}^\{c\}\}\]\.

Off𝒢\\mathcal\{G\}\.Optimism failures and per\-edge UCB convergence failures each contributeO​\(\|E\|\)O\(\|E\|\)via∑tt−3<∞\\sum\_\{t\}t^\{\-3\}<\\infty\. Path\-conditional observation failures occur with probabilityT−2T^\{\-2\}per \(path, position\) pair; summing over at most\|Ψ​\(vs,vg\)\|​Lmax\|\\Psi\(v\_\{s\},v\_\{g\}\)\|L\_\{\\max\}pairs and multiplying by the maximum regretTTgivesO​\(\|Ψ​\(vs,vg\)\|​Lmax/T\)O\(\|\\Psi\(v\_\{s\},v\_\{g\}\)\|L\_\{\\max\}/T\)\.

On𝒢\\mathcal\{G\}\.Optimal paths incur zero regret, and Lemma[4](https://arxiv.org/html/2607.15440#Thmtheorem4)boundsMπ​\(T\)M\_\{\\pi\}\(T\)for eachπ∉Ψ∗\\pi\\notin\\Psi^\{\*\}\. Multiplying byΔ​\(π\)\\Delta\(\\pi\), distributing, and usingΔ​\(π\)≤1\\Delta\(\\pi\)\\leq 1to absorb the warm\-up term:

𝔼​\[R​\(T\)​𝟏𝒢\]≤∑π∉Ψ∗Δ​\(π\)​Mπ​\(T\)≤∑π∉Ψ∗8​ρ​C​\(π\)2​ln⁡TΔ​\(π\)\+∑π∉Ψ∗24​ln⁡TQL​\(π\)\.\\mathbb\{E\}\[R\(T\)\\mathbf\{1\}\_\{\\mathcal\{G\}\}\]\\;\\leq\\;\\sum\_\{\\pi\\notin\\Psi^\{\*\}\}\\Delta\(\\pi\)\\,M\_\{\\pi\}\(T\)\\;\\leq\\;\\sum\_\{\\pi\\notin\\Psi^\{\*\}\}\\frac\{8\\rho\\,C\(\\pi\)^\{2\}\\ln T\}\{\\Delta\(\\pi\)\}\+\\sum\_\{\\pi\\notin\\Psi^\{\*\}\}\\frac\{24\\ln T\}\{Q\_\{L\}\(\\pi\)\}\.\(17\)Adding the off\-𝒢\\mathcal\{G\}contribution gives the theorem\. ∎

## Appendix FFurther Theoretical Discussion

##### Variance awareness\.

Vial et al\.\[[28](https://arxiv.org/html/2607.15440#bib.bib12)\]show that Hoeffding\-based UCB is order\-wise suboptimal for cascading bandits in the problem\-independent regret, with variance\-aware \(Bernstein\) confidence sets attaining the minimax lower bound\.PathUCBinherits this suboptimality onSRPinstances with high\-reliability paths\. We use Hoeffding bounds to keep the path\-level decomposition in Lemma[3](https://arxiv.org/html/2607.15440#Thmtheorem3)self\-contained; extending to Bernstein would augmentC​\(π\)C\(\\pi\)with edge variance terms in place of1/Qi​\(π\)1/\\sqrt\{Q\_\{i\}\(\\pi\)\}, recovering the variance\-aware rates at the path level\. We leave this as future work\.

##### Warm\-up cost\.

The term∑π24​ln⁡T/QL​\(π\)\\sum\_\{\\pi\}24\\ln T/Q\_\{L\}\(\\pi\)counts the selections of each suboptimal path before Lemma[9](https://arxiv.org/html/2607.15440#Thmtheorem9)takes effect at the deepest position\. SinceQL​\(π\)≥pminL−1Q\_\{L\}\(\\pi\)\\geq p\_\{\\min\}^\{L\-1\}, this term can grow exponentially inLLand dominate the bound on long paths\. CombCascade sidesteps this via a prefix argument \(Lemma 1 of\[[16](https://arxiv.org/html/2607.15440#bib.bib24)\]\): a suboptimal path can be distinguished from the optimum on a prefix alone\. Adapting this to the path level—whereC​\(π\)C\(\\pi\)is defined over the full path—is a natural future direction\.

## Appendix GQuantum Repeater Network: SURFnet Abstraction

The 25\-node abstraction of the SURFnet backbone provides a pragmatic baseline for near\-term regional quantum\-internet deployments\[[15](https://arxiv.org/html/2607.15440#bib.bib31),[4](https://arxiv.org/html/2607.15440#bib.bib36)\]\. Nominal link lengthsLnom∈\[15,100\]​kmL\_\{\\text\{nom\}\}\\in\[15,100\]\\,\\text\{km\}adhere to physical repeater spacing constraints; long\-haul routes exceeding a single quantum hop \(e\.g\., the approximately 175 km Amsterdam–Groningen route\) are logically segmented via intermediate hubs \(Almere, Zwolle\)\. Bidirectionality is enforced \(pep\_\{e\}identical in both directions per link\) since each link uses a single physical fiber\.

Edge reliability\.For each instance, an effective lengthLeff=max⁡\(1,Lnom\+ηe\)L\_\{\\text\{eff\}\}=\\max\(1,L\_\{\\text\{nom\}\}\+\\eta\_\{e\}\)is generated withηe∼𝒩​\(0,4\)\\eta\_\{e\}\\sim\\mathcal\{N\}\(0,4\)km \(modeling environmental drift and link\-characterisation uncertainty\)\. The success probability follows the standard fiber\-attenuation model

pe=exp⁡\(−κ​Leff\),κ=0\.02​km−1,p\_\{e\}=\\exp\(\-\\kappa L\_\{\\text\{eff\}\}\),\\qquad\\kappa=0\.02\\,\\text\{km\}^\{\-1\},\(18\)clipped to\[pmin,1\]\[p\_\{\\min\},1\]withpmin=0\.01p\_\{\\min\}=0\.01\. The chosenκ\\kappais optimistic relative to the standardκ=0\.046​km−1\\kappa=0\.046\\,\\text\{km\}^\{\-1\}\[[30](https://arxiv.org/html/2607.15440#bib.bib28)\], modeling near\-future low\-loss fiber or an effective transmission probability that absorbs multiplexing gains; this prevents extreme reward sparsity across multi\-hop topologies\.

Endpoint sampling\.\(vs,vg\)\(v\_\{s\},v\_\{g\}\)are sampled uniformly from node pairs separated by topological distance≥3\\geq 3, ensuring every instance requires combinatorial routing\.

The complete node mapping is given in Table[1](https://arxiv.org/html/2607.15440#A7.T1)and the bidirectional edges in Table[2](https://arxiv.org/html/2607.15440#A7.T2)\.

Table 1:Node index to city mapping for the 25\-node SURFnet abstraction\.Table 2:Bidirectional edges and nominal fiber lengths \(LnomL\_\{\\text\{nom\}\}\) bounded by quantum constraints\.
## Appendix HGreedy Policy Extraction by Algorithm

The greedy policy at episodettis extracted as follows:

- •PathUCBand CombCascade: Dijkstra on the empirical meansp¯e​\(t\)\\bar\{p\}\_\{e\}\(t\)\(no UCB bonus\)\.
- •PathTS: Dijkstra on the posterior means𝔼​\[p~e​\(t\)\]=αe​\(t\)/\(αe​\(t\)\+βe​\(t\)\)\\mathbb\{E\}\[\\tilde\{p\}\_\{e\}\(t\)\]=\\alpha\_\{e\}\(t\)/\(\\alpha\_\{e\}\(t\)\+\\beta\_\{e\}\(t\)\)\.
- •QQ\-Learning: the greedy path under currentQQ\-values\.
- •RTDP and LRTDP: the greedy path extracted from the current value function\.

This isolates each algorithm’s underlying policy from exploration noise\.

## Appendix IBaseline Implementation Details

This appendix gives full implementation details for the six baselines used in Section[6](https://arxiv.org/html/2607.15440#S6)\. The main text gives short identifiers; here we record hyperparameters, initialization schemes, and protocol choices\.

### I\.1CombCascade

CombCascade\[[16](https://arxiv.org/html/2607.15440#bib.bib24)\]is the canonical CCB algorithm\. It maintains UCB estimates with confidence radius1\.5​ln⁡\(t−1\)/Tt−1​\(e\)\\sqrt\{1\.5\\ln\(t\-1\)/T\_\{t\-1\}\(e\)\}and a one\-sided clamp at11\. The original algorithm assumes an exact maximization oracle forarg⁡maxπ∈Ψ​\(vs,vg\)​∏e∈πp^e\\arg\\max\_\{\\pi\\in\\Psi\(v\_\{s\},v\_\{g\}\)\}\\prod\_\{e\\in\\pi\}\\hat\{p\}\_\{e\}; we implement this oracle via Dijkstra on the log\-transformed weights−log⁡p^e\-\\log\\hat\{p\}\_\{e\}, identical toPathUCB\. The implementation differences fromPathUCB\(initialization, confidence radius constant, clamping\) are detailed in Appendix[B](https://arxiv.org/html/2607.15440#A2)\.

### I\.2RTDP

RTDP\[[2](https://arxiv.org/html/2607.15440#bib.bib33)\]is a stochastic\-shortest\-path solver that runs simulated trials fromvsv\_\{s\}and updates state values via Bellman backups along the trajectory, biasing computation toward states reachable under the current greedy policy\. We use a goal reward of\+1\+1on absorption atvgv\_\{g\}and0elsewhere; values are initialized via the hop\-count heuristicV0​\(s\)=γd​\(s,vg\)V\_\{0\}\(s\)=\\gamma^\{d\(s,v\_\{g\}\)\}for consistency withQQ\-Learning, whered​\(s,vg\)d\(s,v\_\{g\}\)is the unweighted shortest hop count fromsstovgv\_\{g\}\.

### I\.3LRTDP

LRTDP\[[3](https://arxiv.org/html/2607.15440#bib.bib34)\]extends RTDP with a convergence\-labeling mechanism: states whose Bellman residual falls belowε=10−3\\varepsilon=10^\{\-3\}and whose greedy successors are all similarly converged are labeled*solved*and excluded from subsequent trials\. LRTDP is generally considered a strict improvement over RTDP\. Reward and initialization follow RTDP\.

### I\.4Q\-Learning

Q\-Learning is a standard tabular off\-policy RL baseline with learning rateαQ​L=0\.1\\alpha\_\{QL\}=0\.1, discount factorγ=0\.99\\gamma=0\.99, andε\\varepsilon\-greedy exploration\. The exploration rate decays exponentially per episode asεt=max⁡\(0\.05,0\.999t\)\\varepsilon\_\{t\}=\\max\(0\.05,\\,0\.999^\{t\}\), reaching the floor att≈3000t\\approx 3000episodes\. Rewards are\+1\+1on reachingvgv\_\{g\}and−1\-1on edge failure\. Action\-values are initialized via the hop\-count heuristicQ0​\(s,a\)=γd​\(s,vg\)Q\_\{0\}\(s,a\)=\\gamma^\{d\(s,v\_\{g\}\)\}, whered​\(s,vg\)d\(s,v\_\{g\}\)is the unweighted shortest hop count fromsstovgv\_\{g\}\(an optimistic initialization that encourages systematic exploration\)\. The use of a discount factor and negative failure rewards introduces a slight objective bias relative to the pureSRPformulation, but reflects standard “off\-the\-shelf” RL deployment\.

### I\.5CUCB

CUCB \(Combinatorial UCB without log\-transform\) isolates the contribution of the log\-transform: it uses the same UCB estimates and Dijkstra solver asPathUCB, but runs Dijkstra on the weightsw​\(e\)=1−p^e​\(t\)w\(e\)=1\-\\hat\{p\}\_\{e\}\(t\)rather than−log⁡p^e​\(t\)\-\\log\\hat\{p\}\_\{e\}\(t\)\. Since minimizing∑e\(1−p^e\)\\sum\_\{e\}\(1\-\\hat\{p\}\_\{e\}\)is not equivalent to maximizing∏ep^e\\prod\_\{e\}\\hat\{p\}\_\{e\}except in the high\-reliability limitp^e→1\\hat\{p\}\_\{e\}\\to 1\(with discrepancy growing in path length\), CUCB optimizes the wrong objective\. We include it to confirm that the log\-transform is responsible for the optimality of Lemma[2](https://arxiv.org/html/2607.15440#Thmtheorem2)rather than a stylistic detail\.

### I\.6Random

Random selects a path via a random walk with cycle avoidance and dead\-end restart: at each step, a neighbor is chosen uniformly at random among unvisited outgoing neighbors; if all neighbors are already visited, the walk restarts fromvsv\_\{s\}, retrying up to 1000 times\. If no valid path is found, the episode is skipped and counts as a failure\. This provides a worst\-case performance floor\.

## Appendix JAdditional Experimental Results

This appendix collects supplementary experimental results referenced in Section[6](https://arxiv.org/html/2607.15440#S6)\.

### J\.1Experiment 1: Bound Comparison

Figure[5](https://arxiv.org/html/2607.15440#A10.F5)compares the edge\-level CombCascade bound \(Eq\.[6](https://arxiv.org/html/2607.15440#S5.E6)\) and the path\-levelPathUCBbound \(Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)\) against the empiricalPathUCBregret\. The interpretation is given in Section[6\.1](https://arxiv.org/html/2607.15440#S6.SS1)\.

Figure 5:Empirical comparison of regret bounds forPathUCBacross four domains\. Each plot shows three curves on alog10\\log\_\{10\}y\-axis: the edge\-level CombCascade bound \(Eq\.[6](https://arxiv.org/html/2607.15440#S5.E6)\), the path\-levelPathUCBbound \(Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)\), and the empiricalPathUCBcumulative regret\. The x\-axis is the episode indextt\.![Refer to caption](https://arxiv.org/html/2607.15440v1/x13.png)\(a\)Erdős\-Rényi
![Refer to caption](https://arxiv.org/html/2607.15440v1/x14.png)\(b\)Grid World
![Refer to caption](https://arxiv.org/html/2607.15440v1/x15.png)\(c\)Layered DAG
![Refer to caption](https://arxiv.org/html/2607.15440v1/x16.png)\(d\)Quantum Network
![Refer to caption](https://arxiv.org/html/2607.15440v1/x17.png)

### J\.2Experiment 1: Full Numerical Results

Table[3](https://arxiv.org/html/2607.15440#A10.T3)gives final cumulative regret, convergence rate, and log\-linear fit parameters for every \(algorithm, domain\) pair in Experiment 1\. The domain sizes where set as follows:

- •Erdős\-Rényi:\|V\|=12\|V\|=12\.
- •Layered DAG:k=4k=4,w=3w=3\.
- •Grid World:Grid size=3×3=3\\times 3
- •Quantum Network:As described in Appendix[G](https://arxiv.org/html/2607.15440#A7)\.

Table 3:Cumulative regret atT=200,000T=200\{,\}000, averaged over 10 topologies×\\times20 seeds \(200 runs\) per \(algorithm, domain\) pair\. Graph size\|V\|\|V\|is shown in parentheses next to each domain\.PathUCBuses the theoretical exploration parameterρ=2\.0\\rho=2\.0;PathTS, CombCascade, and the baselines use their default settings\.*Conv\. Rate*is the fraction of runs in which the greedy policy matched someπ∗∈Ψ∗\\pi^\{\*\}\\in\\Psi^\{\*\}for 10 consecutive episodes withinTT\.*Log\-fitaa*andR2R^\{2\}are the slope and goodness\-of\-fit of𝔼​\[R​\(T\)\]≈a​ln⁡T\+b\\mathbb\{E\}\[R\(T\)\]\\approx a\\ln T\+bat 40 log\-spaced episodes\.
### J\.3Experiment 3: Scaling Analysis

We study how performance scales with graph size \(\|V\|\|V\|,\|E\|\|E\|\) and edge\-reliability range\. SincePathUCBwithρ=1\\rho=1outperformed CombCascade on all five domains in Experiment 2, we focus onPathUCBandPathTS\.

#### J\.3\.1Scaling with Graph Size

We sweep two structurally different axes \(Figure[6](https://arxiv.org/html/2607.15440#A10.F6)a,b\): Erdős–Rényi with\|V\|∈\{6,8,10,12,15,18,20,25,30\}\|V\|\\in\\\{6,8,10,12,15,18,20,25,30\\\}at edge probability0\.40\.4\(path count super\-polynomial in\|V\|\|V\|\), and Layered DAG with a fixed 6\-layer spine and widthw∈\{2,…,8\}w\\in\\\{2,\\dots,8\\\}\(path countw6w^\{6\}, polynomial inww\)\. We useT=100,000T=100\{,\}000episodes\.

On both domains,PathUCBandPathTSexhibit approximately linear regret growth in\|E\|\|E\|\. In dense graphs\|E\|=O​\(\|V\|2\)\|E\|=O\(\|V\|^\{2\}\), so this translates to polynomial scaling in\|V\|\|V\|\.

#### J\.3\.2Scaling with Edge Reliability Range

On Erdős–Rényi graphs with\|V\|=15\|V\|=15, we sweeppmin∈\{0\.05,0\.15,0\.25,0\.35,0\.45,0\.55,0\.59\}p\_\{\\min\}\\in\\\{0\.05,0\.15,0\.25,0\.35,0\.45,0\.55,0\.59\\\}withpmax=pmin\+0\.4p\_\{\\max\}=p\_\{\\min\}\+0\.4\. The support spanpmax−pmin=0\.4p\_\{\\max\}\-p\_\{\\min\}=0\.4is held fixed throughout, so the sweep isolates the location of the reliability interval on\[0,1\]\[0,1\]as the source of variation\. Topologies and seeds are matched acrosspminp\_\{\\min\}values\.

With the spanpmax−pminp\_\{\\max\}\-p\_\{\\min\}fixed, increasingpminp\_\{\\min\}shrinks the relative spread of edge reliabilities \(pmax/pmin→1p\_\{\\max\}/p\_\{\\min\}\\to 1\)\. Path reliabilitiesP​\(π\)=∏e∈πpeP\(\\pi\)=\\prod\_\{e\\in\\pi\}p\_\{e\}therefore cluster, and the per\-path gapsΔ​\(π\)\\Delta\(\\pi\)contract\. Theorem[5](https://arxiv.org/html/2607.15440#Thmtheorem5)predicts regret scaling with1/Δ​\(π\)1/\\Delta\(\\pi\), and the number of episodes needed to separate a suboptimal path scales with1/Δ​\(π\)21/\\Delta\(\\pi\)^\{2\}\(Lemma[4](https://arxiv.org/html/2607.15440#Thmtheorem4)\), so the observed super\-linear growth ofPathUCBis consistent with the gap\-dependent terms of the bound\. This effect is partially offset by improved observability: higherpminp\_\{\\min\}raises the prefix reliabilitiesQi​\(π\)Q\_\{i\}\(\\pi\), so deeper edges are observed more often per episode\. The net trend in Figure[6](https://arxiv.org/html/2607.15440#A10.F6)c indicates that gap contraction dominates\.

Figure 6:Final cumulative regretR​\(T\)R\(T\)atT=100,000T=100\{,\}000versus graph size on Erdős–Rényi \(a\) and Layered DAG \(b\), and versuspminp\_\{\\min\}on Erdős–Rényi with\|V\|=15\|V\|=15\(c\)\.![Refer to caption](https://arxiv.org/html/2607.15440v1/x18.png)\(a\)ER:\|E\|\|E\|
![Refer to caption](https://arxiv.org/html/2607.15440v1/x19.png)\(b\)DAG:\|E\|\|E\|
![Refer to caption](https://arxiv.org/html/2607.15440v1/x20.png)\(c\)ER\(15\):pminp\_\{\\min\}