Pith. sign in

REVIEW 1 major objections 5 minor 32 references

A position-aware complexity score yields logarithmic regret for stochastic reset pathfinding.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 23:24 UTC pith:FNQ46YQC

load-bearing objection 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. the 1 major comments →

arxiv 2607.15440 v1 pith:FNQ46YQC submitted 2026-07-16 cs.LG

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

Guni Sharon , Wei Zhang This is my paper
classification cs.LG MSC 68T0568R10
keywords stochastic reset pathfindingcascading banditscombinatorial banditspath-level regretUCBThompson samplinggraph pathslog-Dijkstra
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

Core claim

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

What carries the argument

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.

Load-bearing premise

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.

What would settle it

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.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • 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.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 5 minor

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.

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 (1)
  1. [2 (Assumption 1) and 1 (Introduction)] 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.
minor comments (5)
  1. [5.1 (Theorem 5)] 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.
  2. [D (Lemma 9)] 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).
  3. [2 (Definition 1)] 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.
  4. [6 (Experimental Setup)] 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.
  5. [Table 3] 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.

Circularity Check

0 steps flagged

No significant circularity: Theorem 5 follows from stated assumptions and standard concentration arguments; no load-bearing self-citation or fitted-input-as-prediction found.

full rationale

The central derivation (Lemma 1 through Theorem 5) is self-contained. Lemma 3 derives the suffix-weighted overestimation inequality (Eq. 7) directly from the optimism event and the telescoping product identity; Lemma 4 combines this with the Hoeffding concentration of the clamped UCB estimator (Lemmas 6-8) and Lemma 9's path-conditional observation bound, which is a binomial coupling argument on independent Bernoulli edge outcomes. Theorem 5 sums the per-path selection bounds and multiplies by the gaps Delta(pi); the constants C(pi), Q_L(pi), and Delta(pi) are functions of the true stationary probabilities, which is standard for gap-dependent regret bounds rather than a fit or an input renamed as a prediction. No load-bearing self-citations appear: [16], [6], and [29] are external prior work invoked for framework placement and known lower bounds, not to supply the paper's own result. The experimental validation fits log-linear curves and explicitly cautions that high R^2 is suggestive rather than conclusive; fitting a curve to a claimed rate is a weak validation, but the paper does not present fitted coefficients as predictions from Theorem 5's constants. The admitted lack of a PathTS regret bound and the adversarial Path Trap instance are honest limitations, not circular steps. The main fragility is the i.i.d. stationary Bernoulli assumption (Assumption 1) relative to the motivating applications; that is a correctness/robustness concern, not circularity.

Axiom & Free-Parameter Ledger

4 free parameters · 7 axioms · 0 invented entities

The central bound rests on: (i) i.i.d. Bernoulli edge outcomes, which real-world channel failure processes may violate; (ii) Assumption 1's known p_min and sub-1 reliabilities; (iii) standard concentration inequalities and the fictitious-sampling coupling; (iv) a product-telescoping identity. No free parameters are fitted in the theoretical derivation itself; the algorithm's rho is the only algorithmic constant, set to rho >= 2 for the theorem, with rho = 1 used empirically after tuning on the evaluation family. The experimental constants (kappa, p_min = 0.01, log-fit slopes) are fitted/design choices that do not enter the theorem.

free parameters (4)
  • PathUCB exploration constant rho = rho = 2.0 (Experiment 1); rho = 1.0 (Experiments 2-3)
    Scales the confidence radius in Eq. (3). Theorem 5 requires rho >= 2; Experiment 1 uses 2; Experiments 2-3 use rho = 1.0 tuned by a sweep on Erdos-Renyi (Section 6 hyperparameters). Does not change the theoretical rate.
  • Log-fit slope a and intercept b = a = 6-227 across domains/algorithms; b fitted
    Section 6.1 fits E[R(T)] ~ a ln T + b to claim O(ln T); these are fitted constants, not predictions from Theorem 5.
  • Quantum fiber attenuation kappa = 0.02 km^-1
    Eq. (18), Appendix G; authors note it is optimistic vs. the standard 0.046 km^-1, chosen so rewards are not too sparse. Affects only the quantum-network experiment.
  • p_min clamp value = 0.01 in experiments
    Lower clamp in Eqs. (3)-(4) and Assumption 1; chosen per experimental domain (Appendices G). Theory treats p_min as given but not value-dependent.
axioms (7)
  • domain assumption Edge outcomes are independent across edges and episodes and stationary: X_e ~ Bernoulli(p_e) i.i.d.
    Definition 1, "Transition dynamics and feedback". All concentration arguments (Lemmas 6, 8, 9) and the fictitious-sampling couplings rest on this. Most likely to be violated in the motivating applications (correlated Lightning channel failures, time-varying link quality).
  • domain assumption Known lower bound p_min with p_e in [p_min, 1) for all edges (Assumption 1)
    p_e < 1 is needed for the strict cycle-deletion inequality in Lemma 1; p_min keeps the lower clamp of Eq. (3) and the log-weights finite. If p_e = 1, ties weaken the domination argument; if p_min is unknown, the clamp is ungrounded.
  • domain assumption Goal reachability: Psi(v_s, v_g) nonempty
    Definition 1; used in Lemma 1 to guarantee a positive-reliability dominating path exists.
  • standard math Hoeffding's inequality and multiplicative Chernoff bounds
    Lemma 6 (two-sided concentration of edge means) and Lemma 9 (path-conditional observation counts) apply these to i.i.d. Bernoulli sums.
  • standard math Fictitious-sampling coupling (as in Lattimore & Szepesvari [19])
    Used in Lemmas 6 and 9 to treat data-dependent observation counts N_e(t), M_pi(t) as fixed-sample sums.
  • standard math Product telescoping identity: prod a_i - prod b_i = sum (a_i - b_i) prod_{j<i} a_j prod_{k>i} b_k
    Eq. (9) in Lemma 3; the structural identity that converts path-reliability gaps into suffix-weighted overestimations.
  • standard math Dijkstra's algorithm solves the shortest-path problem for nonnegative weights and returns a simple path
    Lemma 2 and Algorithm 1; the zero-weight unvisited-edge initialization (p_hat = 1) is consistent with nonnegative weights.

pith-pipeline@v1.3.0-alltime-deepseek · 18151 in / 37585 out tokens · 339598 ms · 2026-08-01T23:24:29.723066+00:00 · methodology

0 comments
read the original 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. SRP captures settings such as entanglement distribution in quantum repeater networks, payment routing on the Lightning Network, and delivery in unreliable mesh networks. We show that the global-reset structure makes the optimal policy open-loop, placing SRP within the combinatorial cascading bandit (CCB) framework. We propose a Log-Dijkstra meta-algorithm with UCB (PathUCB) and Thompson Sampling (PathTS) instantiations. Our main technical result is a path-level regret bound for PathUCB that decomposes regret over suboptimal paths via a per-path complexity C(pi) combining each edge's prefix and suffix reliability. The bound is complementary to the edge-level CCB bound and more informative on structured graphs with polynomially many source-to-goal paths. Experiments on quantum-network, layered-DAG, grid-world, and Erdos-Renyi domains support the theory and show that PathTS typically achieves the best empirical performance among the algorithms tested. We then exhibit an adversarial instance on which PathTS fails to converge, consistent with a known exponential obstruction for combinatorial Thompson Sampling on multiplicative-reward problems. We recommend PathTS as the practical default while cautioning that adversarial instances exist.

Figures

Figures reproduced from arXiv: 2607.15440 by Guni Sharon, Wei Zhang.

Figure 2
Figure 2. Figure 2: Empirical regret R(T) ± 95% CI at T = 10,000 episodes, (y-axis) versus convergence rate (x-axis) for each algorithm across the four primary domains with domain size (|V |) in parenthesis. Bottom-right is better. 0.00 0.25 0.50 0.75 1.00 Convergence Rate 0 1000 2000 3000 4000 Fin al R(T) Convergence Rate vs Final Regret — Primary comparison domain (a) Erdos-Rényi (13) ˝ 0.00 0.25 0.50 0.75 1.00 Convergence … view at source ↗
Figure 3
Figure 3. Figure 3: Path Trap topology. v0 vg t pchain = 0.95 per edge P(π * ) = 0.95 7 ≈ 0.698 direct: P = 0.55 psc = 0.75 per edge P(πsc) = 0.75 2 = 0.562 Path Trap Domain (p * = 0.698 > pdirect = 0.55 > p 2 sc = 0.562) Optimal chain (7 hops) Direct shortcut (1 hop) 2-hop trap (×1) Exploration Failure of Thompson Sampling. Path Trap ( [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Regret vs. convergence on the Path Trap domain. Markers as in [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 6
Figure 6. Figure 6: Final cumulative regret R(T) at T = 100,000 versus graph size on Erdos–Rényi (a) and ˝ Layered DAG (b), and versus pmin on Erdos–Rényi with ˝ |V | = 15 (c). 0 100 200 300 |E| (number of edges) 0 2000 4000 6000 8000 Fin al R(T) Regret Scaling with Graph Size PathUCB PathTS (a) ER: |E| 50 100 |E| (number of directed edges) 0 500 1000 1500 Fin al R(T) Regret Scaling with Layer Width (b) DAG: |E| 0.2 0.4 0.6 p… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 2 linked inside Pith

  1. [1]

    Finite-time analysis of the multiarmed bandit problem

    Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. 47(2–3):235–256, May 2002

    2002

  2. [2]

    Learning to act using real-time dynamic programming.Artificial Intelligence, 72:81–138, 02 1993

    Andrew Barto, Steven Bradtke, and Satinder Singh. Learning to act using real-time dynamic programming.Artificial Intelligence, 72:81–138, 02 1993

    1993

  3. [3]

    Labeled rtdp: improving the convergence of real-time dynamic programming

    Blai Bonet and Héctor Geffner. 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, page 12–21. AAAI Press, 2003

    2003

  4. [4]

    Entanglement distribution in a quantum network: A multicommodity flow-based approach.IEEE Transactions on Quantum Engineering, 1:1–21, 2020

    Kaushik Chakraborty, David Elkouss, Bruno Rijsman, and Stephanie Wehner. Entanglement distribution in a quantum network: A multicommodity flow-based approach.IEEE Transactions on Quantum Engineering, 1:1–21, 2020

    2020

  5. [5]

    An empirical evaluation of thompson sampling.Advances in neural information processing systems, 24, 2011

    Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling.Advances in neural information processing systems, 24, 2011

    2011

  6. [6]

    A thompson sampling algorithm for cascading bandits

    Wang Chi Cheung, Vincent Tan, and Zixin Zhong. A thompson sampling algorithm for cascading bandits. In Kamalika Chaudhuri and Masashi Sugiyama, editors,Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 438–447. PMLR, 16–18 Apr 2019

    2019

  7. [7]

    Near-optimal regret bounds for stochastic shortest path

    Alon Cohen, Haim Kaplan, Yishay Mansour, and Aviv Rosenberg. Near-optimal regret bounds for stochastic shortest path. InProceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020

    2020

  8. [8]

    A tutorial on thompson sampling.Foundations and Trends® in Machine Learning, 11(1):1–99, 2018

    J Russo Daniel, Van Roy Benjamin, Kazerouni Abbas, Osband Ian, and Wen Zheng. A tutorial on thompson sampling.Foundations and Trends® in Machine Learning, 11(1):1–99, 2018

    2018

  9. [9]

    John Wiley & Sons, 2005

    Morris H DeGroot.Optimal statistical decisions. John Wiley & Sons, 2005

    2005

  10. [10]

    A note on two problems in connexion with graphs.Numerische Mathematik, 1(1):269–271, 1959

    EW Dijkstra. A note on two problems in connexion with graphs.Numerische Mathematik, 1(1):269–271, 1959

    1959

  11. [11]

    Srikant, and Wei Chen

    Yihan Du, R. Srikant, and Wei Chen. Cascading reinforcement learning. InThe Twelfth International Conference on Learning Representations, 2024

    2024

  12. [12]

    Erdös and A

    P. Erdös and A. Rényi. On random graphs i.Publicationes Mathematicae Debrecen, 6:290, 1959

    1959

  13. [13]

    Posterior sampling-based online learning for the stochastic shortest path model

    Mehdi Jafarnia-Jahromi, Liyu Chen, Rahul Jain, and Haipeng Luo. Posterior sampling-based online learning for the stochastic shortest path model. In Robin J. Evans and Ilya Shpitser, editors,Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, volume 216 ofProceedings of Machine Learning Research, pages 922–931. PMLR, 31 Ju...

    2023

  14. [14]

    Stochastic shortest path with sparse adversarial costs

    Emmeran Johnson, Alberto Rumi, Ciara Pike-Burke, and Patrick Rebeschini. Stochastic shortest path with sparse adversarial costs. InThe Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025

    2025

  15. [15]

    The internet topology zoo.IEEE Journal on Selected Areas in Communications, 29(9):1765–1775, 2011

    Simon Knight, Hung X Nguyen, Nickolas Falkner, Rhys Bowden, and Matthew Roughan. The internet topology zoo.IEEE Journal on Selected Areas in Communications, 29(9):1765–1775, 2011

    2011

  16. [16]

    Cascading bandits: learning to rank in the cascade model

    Branislav Kveton, Csaba Szepesvári, Zheng Wen, and Azin Ashkan. Cascading bandits: learning to rank in the cascade model. InProceedings of the 32nd International Conference on Machine Learning - Volume 37, ICML’15, page 767–776. JMLR.org, 2015

    2015

  17. [17]

    Combinatorial cascading bandits.Advances in Neural Information Processing Systems, 28, 2015

    Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Combinatorial cascading bandits.Advances in Neural Information Processing Systems, 28, 2015

    2015

  18. [18]

    Asymptotically efficient adaptive allocation rules.Ad- vances in applied mathematics, 6(1):4–22, 1985

    Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules.Ad- vances in applied mathematics, 6(1):4–22, 1985. 10

    1985

  19. [19]

    Cambridge University Press, 2020

    Tor Lattimore and Csaba Szepesvári.Bandit algorithms. Cambridge University Press, 2020

    2020

  20. [20]

    Contextual combinatorial cascading bandits

    Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In Maria Florina Balcan and Kilian Q. Weinberger, editors,Proceedings of The 33rd International Conference on Machine Learning, volume 48 ofProceedings of Machine Learning Research, pages 1245–1253, New York, New York, USA, 20–22 Jun 2016. PMLR

    2016

  21. [21]

    Maheshwari

    S.N. Maheshwari. B74-36 communication, transmission, and transportation networks.IEEE Transactions on Computers, C-23(8):878–878, 1974

    1974

  22. [22]

    Bounded real-time dynamic programming: Rtdp with monotone upper bounds and performance guarantees

    H Brendan McMahan, Maxim Likhachev, and Geoffrey J Gordon. Bounded real-time dynamic programming: Rtdp with monotone upper bounds and performance guarantees. InProceedings of the 22nd international conference on Machine learning, pages 569–576, 2005

    2005

  23. [23]

    Optimally reliable & cheap payment flows on the lightning network.arXiv preprint arXiv:2107.05322, 2021

    Rene Pickhardt and Stefan Richter. Optimally reliable & cheap payment flows on the lightning network.arXiv preprint arXiv:2107.05322, 2021

    Pith/arXiv arXiv 2021

  24. [24]

    John Wiley & Sons, 2014

    Martin L Puterman.Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014

    2014

  25. [25]

    Stochastic online shortest path routing: The value of feedback.IEEE Transactions on Automatic Control, 63(4):915–930, 2018

    Mohammad Sadegh Talebi, Zhenhua Zou, Richard Combes, Alexandre Proutiere, and Mikael Johansson. Stochastic online shortest path routing: The value of feedback.IEEE Transactions on Automatic Control, 63(4):915–930, 2018

    2018

  26. [26]

    Sample complexity bounds for stochastic shortest path with a generative model

    Jean Tarbouriech, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Sample complexity bounds for stochastic shortest path with a generative model. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors,Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 ofProceedings of Machine Learning Research, pages 115...

    2021

  27. [27]

    On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.Biometrika, 25(3/4):285–294, 1933

    William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.Biometrika, 25(3/4):285–294, 1933

    1933

  28. [28]

    Daniel Vial, Sujay Sanghavi, Sanjay Shakkottai, and R. Srikant. Minimax regret for cascading bandits. InProceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY , USA, 2022. Curran Associates Inc

    2022

  29. [29]

    Thompson sampling for combinatorial semi-bandits

    Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits. InInternational Conference on Machine Learning, pages 5114–5122. PMLR, 2018

    2018

  30. [30]

    Quantum internet: A vision for the road ahead.Science, 362:eaam9288, 10 2018

    Stephanie Wehner, David Elkouss, and Ronald Hanson. Quantum internet: A vision for the road ahead.Science, 362:eaam9288, 10 2018

    2018

  31. [31]

    Cascading bandits robust to adversarial corruptions, 2025

    Jize Xie, Cheng Chen, Zhiyong Wang, and Shuai Li. Cascading bandits robust to adversarial corruptions, 2025

    2025

  32. [32]

    off-the- shelf

    Ruihao Zhu and Eytan H. Modiano. Learning to route efficiently with end-to-end feedback: The value of networked structure.CoRR, abs/1810.10637, 2018. 11 A Theoretical Status ofPathTS: Extended Discussion The two prior analyses closest toPathTSare those of Cheung et al. [ 6] and Wang & Chen [ 29]. Neither directly extends toSRP. Cheung et al. prove an O(Ll...

    Pith/arXiv arXiv 2018