Online combinatorial optimization with stochastic decision sets and adversarial losses
Most work on sequential learning assumes a fixed set of actions that are available all the time. However, in practice, actions can consist of picking subsets of readings from sensors that may break from time to time, road segments that can be blocked or goods that are out of stock. In this paper we study learning algorithms that are able to deal with stochastic availability of such unreliable composite actions. We propose and analyze algorithms based on the Follow-The-PerturbedLeader prediction method for several learning settings differing in the feedback provided to the learner. Our algorithms rely on a novel loss estimation technique that we call Counting Asleep Times. We deliver regret bounds for our algorithms for the previously studied full information and (semi-)bandit settings, as well as a natural middle point between the two that we call the restricted information setting. A special consequence of our results is a significant improvement of the best known performance guarantees achieved by an efficient algorithm for the sleeping bandit problem with stochastic availability. Finally, we evaluate our algorithms empirically and show their improvement over the known approaches.
The paper is clear and well written. The paper proposes an algorithm for a problem close to the sleeping experts. As in the case of sleeping experts, the decision set is available stochastically and the rewards are chosen by a non oblivious adversary. Here, the goal of the learner is to sequentially select its actions from a combinatorial decision set. The sleeping expert problem is important in practice, and the combinatorial optimization corresponds to the case where the decision set is structured by a list of actions, for instance in the case of advertising, the list of ads to display for a profile. As in the case of sleeping experts, the proposed algorithm is based on the well-known Follow-the-Perturbed-Leader algorithm. It is analyzed for three different feedbacks: full information, restricted information (the value of the loss function is revealed for available actions), and semi-bandit (the feedback is revealed for chosen actions).  As in the case of sleeping expert, the regret bounds are given with respect to the best fixed policy.The originality of the paper lies in the way in which the availability of decisions is taken into account. The authors propose a smart and efficient method to obtain unbiased loss estimation when the availability distribution is unknown: when an action becomes unavailable, its loss is estimated by its last observation. The reason of this simple approach is well explained and analyzed.  This loss estimation allows improving experimental results of the previous approach BSFPL (sleeping experts) since there is no exploration time to estimate the availability of actions.However, except the availability of decisions, the algorithms and the mathematical framework come from “An Efficient Algorithm for Learning with Semi-Bandit Feedback”, which is given as reference. To sum up, this work is an adaptation of algorithms proposed in the above paper to the sleeping expert problem.Furthermore, the paper is not self-sufficient, and to reproduce the analysis, the reader has to extract some statements in the demonstrations of the above paper, which are used here. I suggest that the authors provide all the demonstrations in the extended version. To improve the paper, I also suggest that the distinction between the decision vector and the action is done: the learner chooses a decision vector $V_t$, where each dimension $V_{i,t}$ is an action.There are some typos: line 211, and line 232.