acceptodds
Under review as a conference paper at ICLR 2027

Reliable Routing with Thompson Sampling: Discovery Barriers and Route Calibration

Abstract

Learning the most reliable route under initially unknown link success probabilities is a fundamental problem in stochastic routing, where route reliability is multiplicative. Thompson sampling (TS), with component-wise Bayesian learning and information sharing across overlapping routes, is highly competitive on such problems. However, multiplying independent posterior samples can sharply suppress the probability that an underexplored route receives a competitive score. Consequently, TS may repeatedly select suboptimal competitors while a more reliable route remains unexplored. We formalize this phenomenon as a compositional discovery barrier, driven by unresolved family-private edges, whose uncertainty persists as competing routes are explored. We establish a general posterior-dependent upper bound on route-selection probability and corresponding lower bounds on first-selection round and cumulative regret. For standard TS with priors, we show that on a controlled overlapping path-trap family with online competitor learning, where is the first selection of one of target routes, each containing unresolved private edges, and is the reliability of the competitor's exclusive edge. At a fixed positive optimality gap, this delay yields linear regret over horizons that scale factorially with . Guided by this analysis, we propose Route-Calibrated Thompson Sampling (RC-TS), which compensates for multiplicative pessimism through a theoretically motivated calibration of edge-level prior optimism. The calibrated prior preserves competitive tail probabilities, yielding a first-discovery upper bound uniform in on the same instance family for fixed and calibration . Experiments under both semi-bandit and cascade feedback show that RC-TS substantially improves robustness in challenging cold-start regimes while preserving competitive performance on ordinary routing instances.

Primary area:
learning theory
Keywords:
Reliable routing, Thompson sampling, Combinatorial bandits

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_hjnBOpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

My apologies in advance as this is probably due to my ignorance of the field. But I had a hard time understanding this paper. For example, in the introduction, the authors go directly into the limitation of Thompson Sampling without talking about how it works in such settings. The example illustrated by Figure 1 is also hard to follow as the explanation contains so many terminologies that are not defined, including but not limited to target routes, target family, exclusive-edge product, family-private edge. Therefore, I honestly do not understand the research question so cannot provide a summary of this paper. Again, I apologize if these are common sense in the field.

Critical strengths

As I mentioned earlier, I do not understand the research question. Please feel free to ignore my review if this is due to my ignorance of the field.

Critical weaknesses

As I mentioned earlier, I do not understand the research question. Please feel free to ignore my review if this is due to my ignorance of the field.

Questions for authors

As I mentioned earlier, I do not understand the research question. Please feel free to ignore my review if this is due to my ignorance of the field.

Reviewer_AUP3OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies reliable routing with unknown link success probabilities under multiplicative route rewards. It shows that standard component-wise Thompson sampling can severely under-explore promising routes containing many unresolved private edges, since multiplying independent posterior samples suppresses their sampled route scores. To address this compositional discovery barrier, the paper proposes Route-Calibrated Thompson Sampling (RC-TS), which uses a route-length-calibrated optimistic Beta prior to preserve sufficient exploration probability, and validates the method theoretically and empirically under semi-bandit and cascade feedback.

Critical strengths

First, the paper provides a clear and technically solid characterization of how multiplicative composition can suppress exploration in component-wise Thompson sampling, including posterior-dependent selection bounds and a factorial-scale first-discovery lower bound on a controlled routing family. This makes the failure mode precise rather than only empirical.

Second, RC-TS is algorithmically very simple: it preserves independent Beta sampling and standard posterior updates while using a length-calibrated optimistic prior, yet it achieves a strong separation in first-discovery time and performs well in several cascade-routing experiments.

Critical weaknesses

The most consequential weakness is that the conceptual advance over prior work may be somewhat incremental. Severe exploration failures of independent Thompson sampling in combinatorial settings have already been established, and more general coordinated-sampling approaches have been proposed; this paper provides a routing-specific characterization and a different remedy, but the gap in generality is relatively narrow.

A second weakness is that the strongest positive guarantee is specialized: RC-TS obtains a length-uniform first-discovery bound on the controlled path-trap family, but the paper does not provide a general cumulative-regret guarantee for arbitrary routing graphs. This limitation also appears empirically, as RC-TS is particularly effective under cascade feedback but does not consistently outperform stronger baselines in the semi-bandit benchmarks.

Questions for authors
  1. How do the authors view the novelty of the compositional discovery barrier relative to Zhang & Combes (2021), which already established severe exploration failures of independent Thompson sampling in combinatorial settings? In particular, which part of the current analysis is fundamentally new beyond the routing-specific overlap structure and online competitor learning?

  2. RC-TS achieves a length-uniform first-discovery bound on the path-trap family, but there is no general cumulative-regret guarantee for arbitrary routing graphs. Can the authors clarify whether such a guarantee is expected to hold, or whether there are instances where the optimistic prior may hurt long-run regret?

  3. In the general routing experiments, RC-TS is strongest mainly under cascade feedback, while CTS^3 performs better in several semi-bandit settings. What mechanism do the authors believe explains this feedback-dependent behavior, and does it indicate a limitation of prior calibration relative to coordinated sampling?

Reviewer_SwwnOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies reliable routing with unknown edge success probabilities under semi-bandit and cascade feedback. It identifies a discovery bottleneck: multiplying independent posterior samples suppresses the scores of routes containing many unexplored private edges, preventing their selection and subsequent learning. On a controlled family of overlapping routes, standard Thompson sampling has factorial-scale first-discovery delay and linear regret over correspondingly long horizons, even with a fixed positive optimality gap.

The proposed Route-Calibrated Thompson Sampling uses a Beta(1,λ/H)Beta(1, \lambda/H) prior, where H bounds route length. A competitive-tail guarantee yields an expected first-discovery bound independent of private-route length on the same instance family. Experiments examine discovery, overlap, prior calibration, and general routing performance. The proposed algorithm substantially improves difficult cold starts and performs well under cascade feedback, while existing one leads the reported general semi-bandit benchmarks.

Critical strengths
  1. The analysis identifies persistent family-private uncertainty and proves a factorial-scale versus length-uniform separation while explicitly accounting for competitor learning. This makes the discovery mechanism more convincing than an example with a fixed competing score.

  2. RC-TS preserves independent Beta sampling, conjugate updates, and shortest-path optimization. Establishing a lower bound on competitive sampled scores goes beyond calibrating their mean and directly supports the proposed exploration mechanism.

Critical weaknesses
  1. Multiplicative sampling and super-exponential discovery difficulties were established by Zhang and Combes (2021). Here, the common suffix cancels exactly, and the discovery analysis reduces to unresolved target products competing with one observed Bernoulli edge. The extension to online competitor learning is useful, but the guarantee ends at first selection and does not establish efficient subsequent learning, particularly under cascade censoring. This limits the broader significance of the theoretical separation.

  2. CTS3CTS^3 is absent from the central path-trap tables and discovery plots, despite being a directly relevant coordinated-exploration baseline. Moreover, fixed Beta(1,0.01)Beta(1, 0.01) priors remain competitive throughout the reported length sweep, but their cumulative regret on general graphs is not reported. Reproduction is also hindered by missing graph-generation and edge-reliability specifications; Appendix A.1 does not give the numerical configuration or vertex counts for the overlap experiment. These omissions weaken the evidence that the proposed calibration offers a distinctive practical advantage.

Questions for authors
  1. Were CTS3CTS^3 and fixed optimistic priors evaluated on the same path-trap instances under both feedback models?

  2. What are the graph-generation procedures and edge-reliability distributions? Do seeds vary graph instances or only interaction randomness?

Comments on the paper

1 comment

Dear AC and Reviewers,

We thank the reviewers for their constructive feedback. We have updated the manuscript to incorporate the additional experiments and clarifications discussed in our responses.

The main revisions include:

  1. Extended baseline comparisons. We added comparisons with CTS³ and fixed optimistic Beta priors on controlled path-trap instances, extending the private-route length to m=800m=800. RC-TS maintains approximately constant first-discovery time, while CTS³ exhibits increasing discovery delay and fixed-prior TS deteriorates sharply.

  2. Cumulative regret and post-discovery learning. We added experiments under both semi-bandit and cascade feedback using 100 seeds and T=10,000T=10,000. At m=800m=800, RC-TS achieves cumulative regret of 15.81 and 14.17, respectively, compared with 1,450.50 and 1,473.65 for CTS³. RC-TS also selects the optimal route in 99.8% of the final 1,000 rounds under both feedback models, demonstrating effective learning beyond first discovery on these instances.

  3. Presentation and reproducibility. We clarified the Thompson-sampling procedure and key terminology, expanded the experimental descriptions, and documented graph-generation procedures, edge reliabilities, random seeds, and evaluation metrics.

The updated manuscript includes these results and their discussion. Reproducible code and experimental configurations are available in our anonymous repository:

https://anonymous.4open.science/r/RCTS-573B/

We have also clarified the scope of our theoretical guarantees and the empirical trade-offs of route-length calibration.

We appreciate your time and consideration and welcome any further feedback on the revised manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.