Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits

• URL: http://arxiv.org/abs/2605.09277v2
• Date: Tue, 12 May 2026 03:42:13 GMT
• Title: Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits
• Abstract summary: We provide the first worst-case regret analysis of Thompson sampling (CTS) for semi-bandits with sleeping arms.<n>We propose CL-SG, a simple CTS-G variant that samples a single shared Gaussian seed each round to coordinate exploration across arms.<n>We show that CL-SG achieves an improved regret bound of $tildeO(sqrtmNT)$, together with a matching lower bound $(sqrtmNT)$.
• Score: 6.725466985159166
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit combinatorial Thompson sampling (CTS) for semi-bandits with sleeping arms, where arm availability varies over time and actions must satisfy combinatorial constraints, as in wireless mesh routing with fluctuating link availability. Despite its practical relevance, CTS has been hindered by several long-standing problems: (i) the absence of worst-case regret guarantees in the semi-bandit setting even without sleeping arms, (ii) the lack of theory under adversarially varying availability, and (iii) the consistently weak empirical performance of CTS with Gaussian priors (CTS-G). This paper resolves these long-standing issues by providing the first worst-case regret analysis of CTS-G, proving an upper bound of $\tilde{O}(m\sqrt{NT})$ and a matching lower bound of $\tildeΩ(m\sqrt{NT})$. To bridge the gap between theory and practice, we further propose CL-SG, a simple CTS-G variant that samples a single shared Gaussian seed each round to coordinate exploration across arms. We show that CL-SG achieves an improved regret bound of $\tilde{O}(\sqrt{mNT})$, together with a matching lower bound $Ω(\sqrt{mNT})$. Experiments on real-world datasets demonstrate that CL-SG consistently outperforms strong baselines including CTS-G and CTS-B, and we open-source our implementation for reproducibility.

Related papers

• Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits [5.873949143662286]
  We study downlink beam and rate adaptation in a multi-user mmWave MISO system where multiple base stations (BSs) serve multiple single-antenna user equipments (UEs) with a unique beam per UE and discrete data transmission rates.<n>To encode service goals, we introduce a satisficing throughput threshold $_r$ and cast joint beam and rate adaptation as a semi-bandit over beam-rate bounds.<n>We show that SAT-CTS consistently reduces satising regret and maintains competitive standard regret, while achieving favorable average throughput and fairness across users.
  arXiv  Detail & Related papers  (2026-04-16T11:49:51Z)
• Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
  We study the statistical efficiency of online learning with respect to KL-regularized objectives.<n>We show that the KL-regularized regret for MABs is $$-independent and scales as $tilde(sqrtKT)$.
  arXiv  Detail & Related papers  (2026-03-02T18:17:33Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION converges iterations of $cal(sqrtdK-)$ measured by gradient Karush-Kuhn-T (sqrtdK-)$. We show that LION can achieve lower loss and higher performance compared to standard SGD.
  arXiv  Detail & Related papers  (2024-11-12T11:30:53Z)
• Discounted Thompson Sampling for Non-Stationary Bandit Problems [13.656518163592349]
  Non-stationary multi-armed bandit (NS-MAB) problems have recently received significant attention. We propose Discounted Thompson Sampling (DS-TS) with Gaussian priors to address both non-stationary settings. Our algorithm passively adapts to changes by incorporating a discounted factor into Thompson Sampling.
  arXiv  Detail & Related papers  (2023-05-18T05:29:52Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• When Combinatorial Thompson Sampling meets Approximation Regret [7.538482310185135]
  We study the Combinatorial Thompson Sampling policy (CTS) for multi-armed bandit problems (CMAB) We provide the first $mathcalO(log(T)/Delta)$ approximation regret upper bound for CTS, obtained under a specific condition on the approximation oracle.
  arXiv  Detail & Related papers  (2023-02-22T07:27:59Z)
• Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
  We study the semi-bandits (CMAB) and focus on reducing the dependency of the batch-size $K$ in the regret bound. First, for the setting of CMAB with probabilistically triggered arms (CMAB-T), we propose a BCUCB-T algorithm with variance-aware confidence intervals. Second, for the setting of non-triggering CMAB with independent arms, we propose a SESCB algorithm which leverages on the non-triggering version of the TPVM condition.
  arXiv  Detail & Related papers  (2022-08-31T13:09:39Z)
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits [61.490254407420906]
  We study the online restless bandit problem, where the state of each arm evolves according to a Markov chain. We propose Restless-UCB, a learning policy that follows the explore-then-commit framework.
  arXiv  Detail & Related papers  (2020-11-05T05:16:04Z)
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits [56.31950477139053]
  We investigate multi-armed bandit with semi-bandit feedback (CMAB) We analyze variants of the Combinatorial Thompson Sampling policy (CTS) This last result gives us an alternative to the Efficient Sampling for Combinatorial Bandit policy (ESCB)
  arXiv  Detail & Related papers  (2020-06-11T17:12:11Z)
• On Tight Convergence Rates of Without-replacement SGD [52.99237600875452]
  For solving finite-sum optimization problems, SGD without replacement sampling is empirically shown to outperform SGD. In this work, we overcome these limitations by analyzing step sizes that vary across epochs.
  arXiv  Detail & Related papers  (2020-04-18T16:14:11Z)
• A General Theory of the Stochastic Linear Bandit and Its Applications [8.071506311915398]
  We introduce a general analysis framework and a family of algorithms for the linear bandit problem. Our new notion of optimism in expectation gives rise to a new algorithm, called sieved greedy (SG) that reduces the overexploration problem in OFUL. In addition to proving that SG is theoretically rate optimal, our empirical simulations show that SG outperforms existing benchmarks such as greedy, OFUL, and TS.
  arXiv  Detail & Related papers  (2020-02-12T18:54:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.