# Sleeping Combinatorial Bandits

arXiv: https://arxiv.org/abs/2106.01624 · HTML: https://mlsanity.com/paper/2106.01624/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 32 references that are in the map.
- First posted on arXiv 3 Jun 2021.

## Builds on (most cited first, 7 of 7)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)

## Abstract (arXiv)

In this paper, we study an interesting combination of sleeping and combinatorial stochastic bandits. In the mixed model studied here, at each discrete time instant, an arbitrary availability set is generated from a fixed set of base arms. An algorithm can select a subset of arms from the availability set (sleeping bandits) and receive the corresponding reward along with semi-bandit feedback (combinatorial bandits). We adapt the well-known CUCB algorithm in the sleeping combinatorial bandits setting and refer to it as CSUCB. We prove -- under mild smoothness conditions -- that the CSUCB algorithm achieves an O(log (T)) instance-dependent regret guarantee. We further prove that (i) when the range of the rewards is bounded, the regret guarantee of CSUCB algorithm is O(√T log (T)) and (ii) the instance-independent regret is O(√[3]T2 log(T)) in a general setting. Our results are quite general and hold under general environments -- such as non-additive reward functions, volatile arm availability, a variable number of base-arms to be pulled -- arising in practical applications. We validate the proven theoretical guarantees through experiments.