The Blinded Bandit: Learning with Adaptive Feedback Elad Hazan Technion
We study an online learning setting where the player is temporarily deprived of feedback each time it switches to a different action. Such model of adaptive feedback naturally occurs in scenarios where the environment reacts to the player's actions and requires some time to recover and stabilize after the algorithm switches actions. This motivates a variant of the multi-armed bandit problem, which we call the blinded multi-armed bandit, in which no feedback is given to the algorithm whenever it switches arms. We develop efficient online learning algorithms for this problem and prove that they guarantee the same asymptotic regret as the optimal algorithms for the standard multi-armed bandit problem. This result stands in stark contrast to another recent result, which states that adding a switching cost to the standard multi-armed bandit makes it substantially harder to learn, and provides a direct comparison of how feedback and loss contribute to the difficulty of an online learning problem. We also extend our results to the general prediction framework of bandit linear optimization, again attaining near-optimal regret bounds.
The paper considers an online learning game with a special sort of partial information, where the learner only gets bandit feedback on its loss whenever it sticks with its previously chosen action. The authors show the surprising fact that in this so-called blinded bandit setting, it is still possible to attain regret guarantees of the same order as in the standard multi-armed bandit setting by using a simple modification of the classic Exp3 strategy. The results are also extended to the case of bandit linear optimization.Originality & Significance--------------------------In light of recent results by Dekel et al., it is indeed surprising that this learning setting is no more difficult than the standard bandit setting. Even though I wouldn't call this observation groundbreaking, it still constitutes an interesting contribution to our general understanding of the role of information in online learning. The algorithm itself and its analysis are quite elegant: the approach is based on a simple and clever subsampling strategy of the stream of observations that effectively separates in time the selection of actions and observing the associated losses. While specifically tailored to this application, this strategy can be possibly applied in other online learning problems with delayed feedback.Quality & Clarity-----------------The paper is written very well and the technical quality is very good, apart from a few minor technical issues. Precisely, I have located one bit in the analysis that needs to be fixed.Expectations and conditional expectations are treated quite liberally throughout the paper. The first occurrence of this problem is to be found near line 264, where the authors use the fact that "b_{t+1}" is independent of l_t(x_t)(1-b_t)", which of course only holds when conditioned on the history up to time t. While this specific problem doesn't stir up any trouble, the same bug shows up on line 274, where the distributions of x_t and x_{t-1} are p_{t} and p_{t-1}, respectively, but under different conditions. Treating this issue complicates the analysis a bit (by an additional application of the tower rule and Jensen's inequality), but it seems that the analysis still goes through -- although the authors should provide a precise proof before the paper can be accepted.Detailed comments-----------------065: The example in this paragraph, while sensible, is probably not the best fit for this framework, as the increased activity *does* influence the true rewards, not only their observations -- the two are closely tied together. Either remove this example or elaborate if you still think it's correct.169: "maintains a probability" -> "maintains a probability distribution"172: p_1 -> p_t297: "The claim is trivial for rounds in which no update occurred" -- This statement is difficult to interpret, as the claim is about an expectation that integrates over the randomness inducing the updates. That is, it is meaningless to refer to action switches unless one conditions on the sequence of b_t's. Please fix this.388: Note that the last inequality follows from n \ge 2.332: The result of Dani et al. is proven for continuous decision spaces by laying an appropriately-sized grid on the decision space and running GeometricHedge on the resulting discrete action set. That is, their algorithm does not match the one presented as Algorithm 2. If you can prove Lemma 4 for this variant of the algorithm, please include it, otherwise, state that the decision space should be finite. In the latter case, the integrals in the proof of Lemma 5 should be replaced by sums.