# Hardness of Online Sleeping Combinatorial Optimization Problems

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2015.

## Built on by (most cited first, 5 of 5)

- [Optimal cross-learning for contextual bandits with unknown context distributions](https://mlsanity.com/paper/2401.01857/) (2024)
- [Dueling Bandits with Adversarial Sleeping](https://mlsanity.com/paper/2107.02274/) (2021)
- [One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Bandits](https://mlsanity.com/paper/2210.14998/) (2022)
- [Adversarial Sleeping Bandit Problems with Multiple Plays: Algorithm and Ranking Application](https://mlsanity.com/paper/2307.14549/) (2023)
- [Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits](https://mlsanity.com/paper/2605.09277/) (2026)

## Abstract (arXiv)

We show that several online combinatorial optimization problems that admit efficient no-regret algorithms become computationally hard in the sleeping setting where a subset of actions becomes unavailable in each round. Specifically, we show that the sleeping versions of these problems are at least as hard as PAC learning DNF expressions, a long standing open problem. We show hardness for the sleeping versions of Online Shortest Paths, Online Minimum Spanning Tree, Online k-Subsets, Online k-Truncated Permutations, Online Minimum Cut, and Online Bipartite Matching. The hardness result for the sleeping version of the Online Shortest Paths problem resolves an open problem presented at COLT 2015 (Koolen et al., 2015).