Hardness of Online Sleeping Combinatorial Optimization Problems

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 P AC learning DNF expressions, a long standing open problem.