Reliable Routing with Thompson Sampling: Discovery Barriers and Route Calibration

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 $\mathrm{Beta}(1,1)$ priors, we show that $\log \mathbb{E}[{\tau }_{\mathcal{F}}]\ge m\log m-\log K-O_p(m)$ on a controlled overlapping path-trap family with online competitor learning, where ${\tau }_{\mathcal{F}}$ is the first selection of one of $K$ target routes, each containing $m$ unresolved private edges, and $p$ 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 $m$. 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 $m$ on the same instance family for fixed $p$ and calibration $\lambda$. 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.