Efficient learning by implicit exploration in bandit problems with side observations
We consider online learning problems under a a partial observability model capturing situations where the information conveyed to the learner is between full information and bandit feedback. In the simplest variant, we assume that in addition to its own loss, the learner also gets to observe losses of some other actions. The revealed losses depend on the learner's action and a directed observation system chosen by the environment. For this setting, we propose the first algorithm that enjoys near-optimal regret guarantees without having to know the observation system before selecting its actions. Along similar lines, we also define a new partial information setting that models online combinatorial optimization problems where the feedback received by the learner is between semi-bandit and full feedback. As the predictions of our first algorithm cannot be always computed efficiently in this setting, we propose another algorithm with similar properties and with the benefit of always being computationally efficient, at the price of a slightly more complicated tuning mechanism. Both algorithms rely on a novel exploration strategy called implicit exploration, which is shown to be more efficient both computationally and information-theoretically than previously studied exploration strategies for the problem.
Summary:This paper considers the multi-armed bandit problem with side information, previously studied by Alon et al. [1] and Mannor and Shamir [17], and a generalization of this problem called the combinatorial semi-bandit problem with side observations. In the first problem, we have a standard multi-armed bandit, and we observe the reward generated by the arm we pull, as well as rewards generated by some other arms, where the observations are determined by an observation graph chosen by an adversary. In the second problem, we may pull many arms at a time, observe the rewards for all pulled arms, as well as some additional arms, again determined by the adversarially chosen observation graph. The paper develops an algorithm Exp3-IX for the first problem that improves over previous algorithms (it is easier to compute, is anytime, and does not need to know the observation graph before each decision). It then develops another algorithm FPL-IX for the second problem with similar properties.  Both algorithms are provided with regret bounds.Quality:Overall, I think this is a good paper.  The problems studied are interesting and broad, the algorithms are reasonable, and the regret bounds seem well-constructed.  I do have some suggestions to improve the clarity of the paper below, but in terms of quality, I just have two points on which the paper could be improved:1. Even though the algorithms don't need to know G_t in order to make the decision I_t or V_t, they do need to know them in order to update the weights.  This felt hidden to me in the discussion in the introduction, and is an important limitation of the algorithm.2. For the m=1 case, one could also apply FPL-IX.  It would be helpful to provide a discussion of what, if anything, is lost when applying FPL-IX instead of EXP3-IX.Clarity:The paper overall is reasonably clear, but the paper could be made substantially more clear through some additional work to correct two issues:First, there are a number of small errors and omissions listed below. Second, the separate sections of the paper could flow more smoothly together. In reading section 3, I was left wondering why we went to the trouble of developing Exp3-IX in section 2.  While reading section 2, I had the impression that we were developing Exp3-IX in the simple case where we pull one arm per period, and then would generalize in section 3 to the combinatorial case, but then I was surprised when I got to section 3 and found that we were abandoning Exp3-IX in favor of FPL-IX.  I believe that I was given this impression by the first paragraph in section 2, which should more clearly state that Exp3-IX will not be developed further for the combinatorial case, and explain briefly why not.Also, in reading footnote 1 on page 3, and in the discussion of Exp3-IX in previous literature on lines 310-312, it was unclear whether Exp3-IX is being newly proposed in this manuscript, or whether this method already exists in the literature.  Based on examining these papers, it appears that Exp3-IX is new to this manuscript, but still the reader is left to wonder.Similarly, there was some notation defined in section 2 that was redefined in section 3 (\mathcal{F}_t on line 325), and some other notation that was changed or added which could have also been used in section 2 (O_{t,i} on line 326, the vector notation for L and \ell on line 317).Small errors and omissions:1. Reading the proof of Theorem 1, it seems that \ell_t is assumed bounded above by 1.  I assume it is also bounded below by 0.  I did not see this explicitly stated.  While of course this is a standard assumption, it should still be stated.2. The language defining \mathcal{F}_{t-1} on line 149 and (to a lesser extent) line 325 is vague.  I assume that what is meant is that \mathcal{F}_{t-1} is the sigma algebra generated by ( \ell_{s,j}, G_s  : 1\le s < t, (I_s -> i) \in G_s ),i.e., all observable losses and observation structures from interactions up to and including time t-1, but then in a number of conditional expectations in the paper, when conditioning on \mathcal{F}_{t-1} it seems that the paper is additionally conditioning on G_t and \ell_{t,i} for all i, so perhaps \mathcal{F}_{t-1} is meant to include these as well.This specifically seems to be true for equation (2), the unnumbered equations on lines 249, 253, 342, 329, and the statement on line 232 about the dependence of Q_t (Q_t also depends on G_t through o_{t,i}.)Similarly, the conditional expectation in the unnumbered equation on line 165 seems to additionally require conditioning on G_t (and could condition on \ell_{t,i} without affecting the result).If \mathcal{F}_{t-1} is meant to include G_t and \ett_{t,i}, then this should be explained more clearly.  If not, then the conditional expectations should be corrected.Also, the expectation on line 191 should be a conditional expectation.3. \gamma on line 203 should be \gamma_t.4. In Algorithm 1, steps 11 and 23 use the notation E(G_t) while the rest of the paper just uses G_t.  In step 5, why is the 1/d term included, while it isn't on line 214?5. On line 285, this assumption is made for all v \in S.6. On line 334, I believe that the expectation of U_{t,i} should be 1/\gamma_t, not \gamma_t.7. In step 9 of Algorithm 2, the algorithm also requires observing G_t itself, in addition to the observed losses.8. In step 3 of Algorithm 2, I think this should set \hat{L}_0 to 0.9. On line 097, "others" should have an apostrophe.  Also, on line 102, there are parens missing after sqrt{T} and sqrt{dT}.10. line 084, "the losses" is repeated.  Line 085, "thus" should be "this".11. The motivating application could be described more clearly.Significance: This paper represents an improvement over the previously developed EXP3-SET algorithm for the bandit with side-observations problem, both in terms of the convenience of the algorithm, and the quality of the regret bounds obtained.  Also, the second problem studied in section 3 is a significant generalization over previously considered models.Originality: This paper builds on several previous papers, both in terms of the problem studied and the algorithms and analysis developed, but the results presented are novel, and the model is a significant generalization of previously studied models.