{"id":"72303530-e7a4-4dc1-9343-7ed5b72858a5","arxiv_id":"2607.15440","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"On known graphs with unknown edge success probabilities and full restart on failure, a UCB algorithm achieves provable O(log T) path-level regret via a prefix/suffix path complexity, while Thompson Sampling wins most experiments but collapses on a deliberately built network.","lead":"The paper formalizes \"stochastic reset pathfinding\": learning which source-to-goal route is most reliable when any failed link forces a full restart, with applications to quantum repeater networks and crypto payment routing. It proves an O(log T) path-level regret bound for a UCB algorithm and shows that Thompson Sampling, usually better, can fail badly on a crafted network.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's guarantee rests on i.i.d. stationary Bernoulli edge outcomes; the motivating applications likely violate this, so the practical claim is not established.","rationale":"I independently checked the proof chain for Theorem 5. Lemma 3's telescoping argument, Lemma 4's two-phase decomposition, and the concentration lemmas are internally consistent under the stated i.i.d. Bernoulli model. The path-conditional observation bound (Lemma 9) is valid because, under the fictitious-sampling coupling, the observation indicator for each selection of a fixed path is conditionally Bernoulli(Q_i) with a constant parameter, making successive indicators independent and the sum Binomial. No internal inconsistency or missing step was found in the mathematical argument. The reader's weakest_assumption correctly identifies the fragility: the i.i.d. stationarity of edge outcomes is what makes Lemmas 6, 8, and 9 go through. This is a standard modeling assumption for cascading bandits, but it is not defended for the real-world systems named in the abstract and introduction. Since the theorem is a conditional guarantee, this does not invalidate the mathematics; it limits the strength of the claim that SRP 'captures' those settings. The proposed test would empirically probe whether the log-regret behavior survives realistic dependence; without such evidence, the practical scope of the central claim remains open. Therefore I recommend keeping the reader's ACCEPT verdict unchanged.","tokens_in":18662,"tokens_out":30072,"duration_ms":286993,"concrete_test":"Run PathUCB on the four benchmark domains with edge outcomes generated by a correlated/time-varying process (e.g., a latent common-cause variable per episode that shifts all p_e, or a Markov-switching model for p_e), keeping the same graph and parameter distributions. Fit E[R(T)] vs ln T and compute the log-linear R^2; compare to the i.i.d. baseline. If R^2 degrades substantially or the fitted slope increases with correlation strength, the independence assumption is practically load-bearing.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorem is internally consistent under Assumption 1, but that assumption is the load-bearing premise: each edge outcome is an independent Bernoulli draw, stationary across episodes (Definition 1; used in Lemmas 6, 8, 9). Lemma 9's binomial coupling and Lemma 3's gap argument both require that prefix-edge outcomes are independent and identically distributed across attempts. In the cited applications — Lightning Network channel failures, quantum repeater links, mesh network interference — failures are commonly positively correlated (shared congestion, common environmental causes) and time-varying. Under such dependence, the concentration lemmas do not hold, and the O(ln T) regret guarantee may fail. The paper provides no robustness or misspecification analysis, so the transfer of the central claim to the motivating settings is unverified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Stochastic Reset Pathfinding (SRP), an episodic problem on a known directed graph with unknown stationary edge success probabilities, where any edge failure resets the agent to the source. It shows the optimal policy is open-loop and reduces the problem to a combinatorial cascading bandit (CCB). The main contribution is a path-level regret bound for PathUCB that decomposes regret over suboptimal paths via a per-path complexity C(pi) combining prefix and suffix reliabilities. The paper also presents PathTS experiments, an adversarial instance where PathTS fails, and empirical studies across four domains. The central theorem (Theorem 5) is claimed under Assumption 1 (i.i.d. stationary Bernoulli edge outcomes with known lower bound p_min) and yields logarithmic regret.","tokens_in":18774,"tokens_out":25197,"duration_ms":219973,"significance":"If the path-level regret bound is correct, it provides a new, position-aware complexity measure for graph-path cascading bandits, complementary to the edge-level CombCascade bound. The paper also gives a concrete negative result for Thompson Sampling in a graph-path cascading setting, connects to known obstructions, and validates the O(log T) rate experimentally. The theoretical chain appears internally consistent, with detailed proofs and a clear statement of assumptions; the empirical study is broad and includes a reproducibility-friendly appendix.","major_comments":[{"comment":"The regret guarantee of Theorem 5 is derived under Assumption 1: i.i.d. stationary Bernoulli edge outcomes, independent across edges and episodes (used in Lemmas 6, 8, 9). The Introduction claims SRP 'captures' Lightning Network, quantum repeater, and mesh network settings, where link failures are plausibly correlated and time-varying. Under such dependence the concentration lemmas and the O(ln T) bound may fail, and the paper provides no robustness analysis or non-i.i.d. experiments. Please add a paragraph acknowledging this limitation and either soften the applicability claims or add a misspecification check. This does not affect the internal validity of Theorem 5 under Assumption 1, but it is load-bearing for the paper's motivational significance.","section":"2 (Assumption 1) and 1 (Introduction)"}],"minor_comments":[{"comment":"The O term in Eq. (12) is typeset as O((|E|+|Psi|L_max)/T), but the proof in Appendix E and the abstract indicate O(|E| + |Psi|L_max/T). The |E| contribution is independent of T. Please correct the typesetting.","section":"5.1 (Theorem 5)"},{"comment":"The proof asserts that the partial sum of the indicators stochastically dominates a Binomial(m, Q_i(pi)) random variable. This is true — in fact the sum is exactly Binomial(m, Q_i(pi)) by compounding two independent binomials — but the claim is nontrivial and should be justified (e.g., via the probability generating function).","section":"D (Lemma 9)"},{"comment":"The description of edge outcomes says 'each edge produces an independent outcome' but does not explicitly state independence across episodes. Please clarify that outcomes for each edge are i.i.d. across attempts, as required by the concentration lemmas.","section":"2 (Definition 1)"},{"comment":"Experiments 2 and 3 use PathUCB with rho=1.0, while Theorem 5 requires rho>=2. The paper notes this, but it should explicitly state that the theoretical guarantee does not cover those runs, to avoid implying the bound applies to the reported settings.","section":"6 (Experimental Setup)"},{"comment":"The log-fit R^2 values for RTDP, LRTDP, and Random are exactly 0.752 for all domains, and Q-Learning values are 0.754/0.756/0.799. The identical repeated value is suspicious and may indicate a rounding or plotting artifact; please double-check the fits.","section":"Table 3"}],"recommendation":"minor_revision","confidential_remarks":"The main theorem is sound under the stated i.i.d. assumption; I verified the key steps (Lemma 3's telescoping identity, Lemma 4's warm-up/saturation split, and Lemma 9's observation bound). The only substantive concern is the gap between the formal model and the motivating applications, which is a limitation rather than a mathematical flaw. A well-scoped revision adding a limitations paragraph and the minor clarifications above would make the paper fully convincing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the main theorem is real and the proof chain holds up under inspection. The paper is also unusually honest about its own limits. My main concerns are that the i.i.d. stationary Bernoulli assumption is load-bearing and likely false in the motivating applications, and that no code or data accompanies the experiments. Neither kills the theoretical contribution.\n\nWhat is actually new: Lemma 3's telescoping inequality, which trades the prefix product for suffix reliability, and the path complexity C(pi) = sum S_i / sqrt(Q_i). That gives a legitimate path-level alternative to CombCascade's edge-level bound, with a real claim about position-dependent observability. The paper also correctly tells you the open-loop reduction and the log-Dijkstra transform are standard—it cites [21] and does not oversell. The missing regret bound for PathTS and the exponential warm-up cost in 1/Q_L are explicitly flagged, and the adversarial Path Trap instance is a useful, if not conclusive, demonstration of Thompson Sampling failure.\n\nSoft spots: Lemmas 6, 8, and 9 all assume edge outcomes are independent Bernoulli draws, stationary across episodes and independent across edges. Lemma 9's coupling and Lemma 3's gap argument both lean on that. In the Lightning Network and mesh routing settings the paper cites, failures correlate across edges and drift over time, so the O(ln T) guarantee does not transfer to those settings as stated. That is a real limitation, but it is the standard assumption in cascading bandit theory and the paper does not claim robustness. It is worth a caveat, not a rejection. A minor issue: the [16]/[17] reference swap in Related Work needs fixing. The log-linear fit R^2 >= 0.96 is suggestive, and the authors themselves caution against over-reading it; the unreleased code and data mean the figures cannot be checked. I traced Lemma 3 to Lemma 4 to Theorem 5 and the algebra is consistent.\n\nWho this is for: people working on cascading bandits, and anyone with a restart-based routing problem who wants a principled UCB variant with a position-aware regret guarantee. Worth a serious referee. I would send it out and ask for code/data release plus a paragraph acknowledging the i.i.d. assumption's limits relative to the motivating applications.","headline":"A clean, honest path-level regret bound for restart-based pathfinding; the i.i.d. edge assumption is the fragile link to practice, but the theory itself checks out.","tokens_in":19356,"tokens_out":1981,"would_cite":true,"duration_ms":21232,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A position-aware complexity score yields logarithmic regret for stochastic reset pathfinding.","keywords":["stochastic reset pathfinding","cascading bandits","combinatorial bandits","path-level regret","UCB","Thompson sampling","graph paths","log-Dijkstra"],"falsifier":"Run PathUCB on a small graph with known edge probabilities (e.g., a 2-edge path) and compare the empirical cumulative regret against the predicted envelope (8 rho C(pi)^2 ln T)/Delta(pi): if the regret grows faster than logarithmic, the telescoping decomposition in Lemma 3 fails. Alternatively, set one edge's success probability to 1; the open-loop reduction relies on strict inequality for cycle deletion, and a looping policy could then outperform every simple path.","tokens_in":1371,"feed_emoji":"🛣️","tokens_out":1567,"duration_ms":72695,"temperature":0.7,"pith_summary":"Stochastic Reset Pathfinding (SRP) models situations where an agent repeatedly attempts a source-to-goal path and is sent back to the start when any link fails. The paper shows that this global-reset structure makes the optimal policy an open-loop path, so the problem becomes a combinatorial cascading bandit rather than a reinforcement-learning problem. Its main result is a path-level regret bound for a UCB algorithm (PathUCB), in which each suboptimal path contributes a logarithmic amount of regret scaled by a path complexity that combines prefix reliability (how often an edge is observed) and suffix reliability (how far its estimation error propagates). If the bound is correct, restart-based pathfinding on known graphs is learnable with logarithmic regret, and the paper's experiments suggest a Thompson Sampling variant is faster in practice, though it can fail on an adversarial instance.","feed_headline":"Restart pathfinding hits logarithmic regret","feed_subtitle":"A position-aware path complexity predicts how much exploration each route needs, making UCB the safe choice.","key_machinery":"The load-bearing object is the path complexity C(pi) = sum_i S_i(pi)/sqrt(Q_i(pi)), where Q_i(pi) is the probability an edge is observed (prefix reliability) and S_i(pi) is the reliability of the downstream tail (suffix reliability). The analysis uses a telescoping identity that turns the gap between estimated and true path reliability into a suffix-weighted sum of per-edge overestimations, plus a binomial-coupling lemma that guarantees every edge in a frequently selected path is observed a fraction of the time. Planning is reduced to Dijkstra on the transformed weights w(e) = -log p_e, so the learner's oracle is shortest-path search on estimated log-reliabilities.","core_discovery":"The paper's central claim is Theorem 5: assuming stationary, independent Bernoulli edge outcomes with a known lower bound p_min, the expected cumulative regret of PathUCB is at most the sum over suboptimal paths of 8 rho C(pi)^2 ln T / Delta(pi), plus a warm-up term 24 ln T / Q_L(pi) and lower-order factors. Here Delta(pi) is the gap in path reliability, and C(pi) = sum_i S_i(pi) / sqrt(Q_i(pi)), where Q_i(pi) is the probability that the i-th edge is reached and S_i(pi) is the reliability of the path's suffix after that edge. The proof rests on a telescoping identity that bounds the estimated-versus-true reliability difference by a suffix-weighted sum of per-edge overestimations, together wi","pith_inferences":["The complexity measure C(pi) suggests a testable diagnostic: on a given graph, paths with deep edges (small Q_i) and long suffixes (large S_i) dominate regret, so reweighting exploration by position could improve finite-horizon performance beyond the paper's UCB choice.","The independence and stationarity assumption on edge outcomes is fragile for the motivating applications; a robustness study with correlated or Markov-switching edge failures would clarify whether the logarithmic guarantee survives real-world channel behavior.","The warm-up term 24 ln T / Q_L(pi) grows with path depth; if the prefix-elimination technique used in edge-level cascading bandits could be lifted to the path level, the bound would no longer need to enumerate every suboptimal path.","The Path Trap failure points to a practical selection rule: use Thompson Sampling when optimal paths are short or share edges with alternatives, and fall back to PathUCB when the optimum is long and competitors are edge-disjoint."],"forward_implications":["If the bound holds, expected regret remains logarithmic in the time horizon, so restart-based pathfinding can be deployed over long horizons without accumulating linear regret.","The path-level decomposition complements the edge-level CombCascade bound: it is tighter on sparse graphs with polynomially many paths (layered DAGs, grids) while the edge-level bound is preferable on dense graphs.","The open-loop reduction means standard stochastic-shortest-path and RL solvers are unnecessary; a bandit algorithm with a log-Dijkstra oracle suffices.","The log-transform is essential: replacing it with a linear surrogate raises final regret by 1.2 to 2.1 times and lowers convergence rates.","PathTS is recommended for practice but carries no regret guarantee; the Path Trap instance shows a concrete failure mode where Thompson Sampling over-commits to short, frequently rewarding shortcuts while PathUCB converges."],"fun_headline_variants":["PathUCB guarantees logarithmic regret in reset pathfinding","Reset pathfinding: UCB beats Thompson on adversarial graphs","Path-level regret bound makes UCB the safe choice","Logarithmic regret for stochastic reset pathfinding","PathUCB: log regret, PathTS: adversarial failure"],"cache_read_input_tokens":20736,"weakest_assumption_plain":"The regret bound assumes every edge succeeds independently from episode to episode with a fixed probability, and that these probabilities never drift or correlate; if real channel failures are correlated or time-varying, the stated guarantee is not proven.","fun_headline_variants_meta":{"raw":{"variants":["PathUCB guarantees logarithmic regret in reset pathfinding","Reset pathfinding: UCB beats Thompson on adversarial graphs","Path-level regret bound makes UCB the safe choice","Logarithmic regret for stochastic reset pathfinding","PathUCB: log regret, PathTS: adversarial failure"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000272,"raw_usage":{"total_tokens":1510,"prompt_tokens":828,"completion_tokens":682,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":572,"completion_tokens_details":{"reasoning_tokens":614}},"tokens_in":572,"tokens_out":682,"duration_ms":6050,"temperature":1.0,"reasoning_tokens":614,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T23:24:29.723066+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run PathUCB on a small graph with known edge probabilities (e.g., a 2-edge path) and compare the empirical cumulative regret against the predicted envelope (8 rho C(pi)^2 ln T)/Delta(pi): if the regret grows faster than logarithmic, the telescoping decomposition in Lemma 3 fails. Alternatively, set one edge's success probability to 1; the open-loop reduction relies on strict inequality for cycle deletion, and a looping policy could then outperform every simple path.","supporting_citations":[],"review_version":1}