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 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].
The paper solves an open problem presented at COLT 2015 [Koolen et. al. 2015] and proves the hardness of Online Sabotaged Shortest Path problem with per-action regret, and furthermore, establishes a hardness results for a general category of Online Sleeping Combinatorial Optimization (OSCO) Problems. It defines OSCO problems as online combinatorial optimization problems in sleeping setting in which in each trial a subset of actions become unavailable due to unavailability of a subset of elements. Basically, the paper shows that OSCO problems are as hard as PAC-Learning of DNF expressions -- which is a long standing open problem.  In a nutshell, the hardness result is shown as follows: the paper reduces the problem of "Online Agnostic Learnign of Disjuction" into "Hard Instances" of OSCO problems with per-action regret via a proof that has similarities to a proof in [Kanade and Steinke, 2014]. Incorporating the results of related works like [Kanade and Steinke, 2014], [Kearns et. al. 1994], [Kalai et. al. 2012], the paper mentions that "Online Agnostic Learning of Disjuction" is at least as hard as "Agnostic Improper PAC Learning of Disjuctions" which is also at least as hard as "PAC-Learning of DNF expression". Interestingly enough, because of the online-to-batch conversion argument in [Kanade and Steinke, 2014], the hardness results seem to be also true for a benign form of adversary namely stochastic availabilities and loss (i.e. they are drawn from an unknown but fixed joint distribution).  After proving the general hardness results, the paper provides "Hard Instances" of various well-known OSCO problems to establish their hardness in particularv -- including Online Sabotaged Shortest Path. 
The main proof of the general hardness result is clearly explained and looks sound and correct. The idea of the proof is similar to [Kanade, Steike 2014] and therefore not quite ground-breaking, but notably novel. Other technicalities of the paper are also well written to some extent; however, there are still some confusing parts. Concretely, section 3 is not straight-forward to follow. For example, in the first paragraph the difference between "Agnostic Improper PAC-learning of disjuction " vs "PAC-learning of DNF Expressions" is not clear -- perhaps mainly because there is a discrepency between the naming in the paper and the related work [Kalai et. al. 2012] in which the term "Reliable Agnostic Learning" is used instead. Also the reviewer could not see the hardness result even in iid case using [Kanade Steinke 2014] (it does not seem to be clearly mentioned in cited paper).  Generally, the paper has a good flow and it is well-organized. The presentation is quite readable and understandable. The reviewer believes the impact is significat since it not only solves an open problem presented in COLT 2015, but also establishes a more general hardness for a category of problems with a loose form of adversarial setting.