Bridging the Regret Gap in Combinatorial Thompson Sampling: Worst-Case Guarantees and Algorithmic Refinement

This paper revisits combinatorial Thompson sampling (CTS) in the semi-bandit setting with sleeping arms, where only a subset of arms is available each round under combinatorial constraints. Such settings frequently arise in networking applications and pose significant challenges due to the need for combinatorial optimization over a dynamically changing action space. A canonical example is wireless mesh routing, where fluctuating link availability and routing constraints lead to a time-varying set of feasible paths between source and destination nodes.The existing works have three key limitations: (1) the lack of worst-case regret guarantees for CTS in semi-bandit settings, even without accounting for sleeping arms; (2) the absence of theoretical guarantees for CTS under adversarially varying arm availability; and (3) the subpar empirical performance of CTS with Gaussian priors (CTS-G).To address these issues, we propose CL-SG, a simple yet effective CTS-G variant that samples a single shared Gaussian seed each round to coordinate exploration across arms. Theoretically, CL-SG achieves a worst-case regret bound of $\tilde O(\sqrt {mNT} )$ and a matching lower bound of $\Omega (\sqrt {mNT} )$. Our analysis can also easily recover a regret bound for CTS-G. With experiments driven by real-world datasets, CL-SG consistently outperforms diverse benchmark algorithms such as CTS-G and CTS-B. We open-source our implementation and experiments to support reproducibility and further research.