🤖 machine learning

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

This paper resolves long-standing theoretical gaps in combinatorial Thompson sampling for sleeping semi-bandits by establishing the first worst-case regret bounds for the standard Gaussian variant and introducing a novel CL-SG algorithm that achieves improved $\tilde{O}(\sqrt{mNT})$ regret while demonstrating superior empirical performance on real-world datasets.

Original authors: Zhiming Huang, Bingshan Hu, Jianping Pan

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhiming Huang, Bingshan Hu, Jianping Pan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Sleeping" Network Problem

Imagine you are a traffic controller for a massive city. Your job is to send delivery trucks (data) from Point A to Point B as quickly as possible.

In a perfect world, every road (arm) is open 24/7, and you know exactly how long each road takes. But in the real world, roads close unexpectedly due to construction, accidents, or weather. These are "sleeping arms." Sometimes a road is awake (open), and sometimes it is asleep (closed).

You don't know the true travel time of any road at the start; you have to learn by driving on them. However, you only get to see how long the roads you chose took. You don't know how long the roads you didn't pick would have taken. This is called "semi-bandit feedback."

Your goal is to pick the best combination of open roads every single day to minimize the total time wasted over a year. The "regret" is simply the extra time you spent because you didn't pick the perfect route.

The Problem: The "Gaussian" Guessing Game

For years, computer scientists have used a strategy called Thompson Sampling to solve this. Think of it like a chef guessing the taste of a new dish.

The Chef (Algorithm): Tries a dish, tastes it, and updates their mental recipe book.
The Guess: Before cooking, the chef draws a random number from a "Gaussian" (bell curve) distribution to guess how good the dish might be. If the guess is high, they cook it.

The paper points out three big problems with how this chef has been working so far:

No Worst-Case Safety Net: We knew the chef was good at learning if the dishes were slightly different from each other. But we had no proof that the chef wouldn't make a disaster if the dishes were tricky or if the available ingredients changed in a malicious way (like a rival chef sabotaging the pantry).
The "Sleeping" Mystery: We didn't have a mathematical guarantee for what happens when roads (ingredients) randomly disappear.
The "Gaussian" Glitch: Even though the Gaussian method is popular, in practice, it often performed worse than other methods. It seemed to be exploring too chaotically, like a chef trying every random spice combination at once.

The Solution: Two New Recipes

The authors of this paper fixed these problems with two main contributions.

1. The First Proof: "The Ghost Sample"

First, they took the standard Gaussian method (let's call it CTS-G) and finally proved mathematically that it does have a safety net, even in the worst-case scenarios.

The Analogy: Imagine the chef is trying to decide if a road is good. They usually guess based on their own history. The authors introduced a "Ghost Sample."
How it works: The chef creates a "ghost" version of the road's travel time that is identical to their current guess but completely independent. By comparing the real guess to the ghost, they can mathematically prove that the chef won't get stuck in a loop of bad choices forever.
The Result: They proved the "regret" (wasted time) grows at a predictable, manageable rate. This was the first time this specific "Gaussian" method was proven to be safe in this difficult "sleeping" environment.

2. The Upgrade: "The Shared Seed" (CL-SG)

While the first proof was good, the math showed the standard method was still a bit inefficient. It was like the chef drawing a new random number for every single ingredient in the recipe. This created too much noise and confusion.

The authors proposed a new, simpler version called CL-SG (Combinatorial Learning with a Single Gaussian Seed).

The Analogy: Instead of rolling a new die for every ingredient, the chef rolls one single die at the start of the day.
How it works: This single "seed" (the die roll) is used to adjust the estimated travel time for all roads simultaneously.
- If the die roll is high, the chef becomes optimistic about all roads.
- If the die roll is low, the chef becomes cautious about all roads.
Why it's better: This coordinates the exploration. The chef isn't randomly guessing on every road independently; they are exploring the whole city with a unified mood. This reduces the "noise" and makes the learning much faster.
The Result: This new method is mathematically proven to be even more efficient than the standard one. It achieves the best possible theoretical performance (minimax optimal) for this type of problem.

The Real-World Test

To prove this wasn't just math on paper, the authors tested it on real-world data:

A Synthetic City: A computer simulation of a wireless network with 16 nodes.
A Real City: Data from the UCSB MeshNet, a real wireless network testbed.

The Outcome:
The new CL-SG method consistently beat the old standard methods (including the original Gaussian method and other popular competitors). It learned the best routes faster and wasted less time.

Summary

The Problem: We needed a way to prove that a popular learning algorithm (Thompson Sampling) works safely when options disappear and reappear unpredictably.
The Breakthrough: They proved the standard method works, but it's a bit clunky.
The Innovation: They created a "Shared Seed" version (CL-SG) that coordinates its guesses, making it mathematically optimal and practically faster.
The Proof: It works better in simulations and on real network data than previous methods.

In short, they took a powerful but slightly chaotic tool, proved it was safe, and then gave it a "team captain" (the shared seed) to make it run a perfect race.

Technical Summary: First Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits

Problem Definition
This paper addresses the problem of combinatorial Thompson sampling (CTS) in the context of stochastic semi-bandits with "sleeping" arms. In this setting, an agent repeatedly selects a "super arm" (a feasible subset of at most $m$ base arms) from a dynamically changing set of available arms drawn from a pool of $N$ base arms. The availability of arms can vary adversarially over time, a scenario motivated by networking applications such as wireless mesh routing where link availability fluctuates due to congestion or failures. The agent observes individual rewards for the selected arms (semi-bandit feedback) and aims to maximize cumulative reward, or equivalently, minimize regret against an oracle that selects the optimal feasible subset given the current availability.

The authors identify three critical gaps in existing literature regarding CTS for this problem:

Lack of Worst-Case Guarantees: Prior CTS analyses in semi-bandits were predominantly problem-dependent (scaling with reward gaps $\Delta$ ), failing to provide meaningful worst-case regret bounds.
Adversarial Availability: Existing theoretical guarantees for Thompson sampling generally assumed stochastic arm availability, lacking analysis for adversarially varying availability.
Empirical Suboptimality: CTS with Gaussian priors (CTS-G), despite its theoretical appeal, has historically demonstrated weaker empirical performance compared to Upper Confidence Bound (UCB) methods and CTS with Beta priors (CTS-B).

Methodology and Algorithms
The paper proposes two primary algorithmic approaches:

Combinatorial Thompson Sampling with Gaussian Priors (CTS-G):
This is a direct adaptation of standard Thompson sampling to the sleeping semi-bandit setting. In each round, the algorithm maintains empirical mean estimates for each arm and draws independent Gaussian posterior samples for every base arm. It then selects the super arm that maximizes the sum of these samples within the current feasible set.
Combinatorial Learning with a Single Gaussian Seed (CL-SG):
To address the theoretical and empirical limitations of CTS-G, the authors propose CL-SG. This variant introduces a coordination mechanism: instead of drawing independent noise for each arm, it samples a single shared Gaussian seed $w_t \sim \mathcal{N}(0, 1)$ per round. This seed is used to perturb the empirical estimates of all base arms simultaneously. This design aims to coordinate exploration across arms and reduce the variance inflation inherent in independent sampling.

Key Contributions and Theoretical Results

First Worst-Case Analysis of CTS-G:
The paper provides the first frequentist worst-case regret analysis for standard CTS-G in sleeping semi-bandits.
- Upper Bound: The authors prove an upper bound of $\tilde{O}(m\sqrt{NT})$ .
- Lower Bound: They establish a matching lower bound of $\tilde{\Omega}(m\sqrt{NT})$ , demonstrating that CTS-G is worst-case optimal up to logarithmic factors.
- Proof Strategy: The analysis departs from traditional gap-based methods. It utilizes a "ghost-sample" argument and refined anti-concentration analysis for correlated Gaussian estimates to handle the unobservability of the optimal super arm and the dynamic feasibility constraints.
Improved Bounds via CL-SG:
The authors show that the standard CTS-G suffers from an extra $\sqrt{m}$ factor in its regret bound due to the variance inflation required to control the probability of selecting the optimal set when arms are sampled independently.
- Upper Bound: By using a single shared seed, CL-SG achieves a strictly improved worst-case regret bound of $\tilde{O}(\sqrt{mNT})$ .
- Lower Bound: A matching lower bound of $\Omega(\sqrt{mNT})$ is proven, establishing that CL-SG achieves the minimax-optimal rate for this problem class.
- Mechanism: The shared seed avoids the need for the variance to scale with $m$ to maintain a constant anti-concentration probability for the sum of errors, thereby removing the extraneous $\sqrt{m}$ factor.

Experimental Results
The authors evaluate CL-SG against strong baselines, including CTS-G, CTS-B, BG-CTS, and CombUCB, using two settings:

Synthetic Network: A 16-node wireless mesh grid with Bernoulli rewards.
Real-World Network: Traces from the UCSB MeshNet dataset involving time-varying link availability.

Results averaged over 100 runs demonstrate that CL-SG consistently outperforms CTS-G, CTS-B, and CombUCB in terms of cumulative regret. The experiments also indicate that CL-SG is robust to the exploration parameter $\gamma$ , achieving low regret even with larger $\gamma$ values where CTS-G suffers from excessive exploration.

Significance
The paper claims to resolve a long-standing open problem by establishing the first worst-case regret guarantees for Thompson sampling in combinatorial semi-bandits with adversarial sleeping arms. By bridging the gap between theory and practice, the work demonstrates that a simple modification to the sampling mechanism (using a shared seed) can yield both tighter theoretical bounds and superior empirical performance. The authors provide open-source implementations to ensure reproducibility and lay the groundwork for future research into the optimal trade-off between randomness and exploration in combinatorial optimization.