Multi-armed Bandits: Competing with Optimal Sequences
We consider sequential decision making problem in the adversarial setting, where regret is measured with respect to the optimal sequence of actions and the feedback adheres the bandit setting. It is well-known that obtaining sublinear regret in this setting is impossible in general, which arises the question of when can we do better than linear regret? Previous works show that when the environment is guaranteed to vary slowly and furthermore we are given prior knowledge regarding its variation (i.e., a limit on the amount of changes suffered by the environment), then this task is feasible. The caveat however is that such prior knowledge is not likely to be available in practice, which causes the obtained regret bounds to be somewhat irrelevant. Our main result is a regret guarantee that scales with the variation parameter of the environment, without requiring any prior knowledge about it whatsoever. By that, we also resolve an open problem posted by Gur, Zeevi and Besbes [8]. An important key component in our result is a statistical test for identifying non-stationarity in a sequence of independent random variables. This test either identifies nonstationarity or upper-bounds the absolute deviation of the corresponding sequence of mean values in terms of its total variation. This test is interesting on its own right and has the potential to be found useful in additional settings.
The paper studies the stochastic Multi Armed Bandit problem, where the distributions of the arms could change over time. The authors approach the problem by first proposing a testing procedure to detect if there is a significant change in the means in an offline set (Test 1) and online series (Test 2) of independent random variables. They use these tests to design an online alg for the problem in the case of two arms The alg could be outlined as follows:  - It dynamically divides the time horizon into blocks; each block consists of an exploration phase, and a possibly null exploitation phase.  - During the exploration phase, the alg randomly pulls each arm with equal probability. If a change in either of the arms is detected, it goes to the next block (nil exploitation phase). If no (essential) change is detected and one arm is "significantly" better than the others, it goes to the exploitation phase.   - The exploitation phase favors playing the better arm, but the length of the phase and the probability of playing the perceived better arm are weighed according to the probability that the exploration phase makes the correct identification.   The main novelty of the algorithm is the proposal of Test 2, which requires the decision maker to actively and explicitly detect the change in the arms' distributions. This appears a novel aspect (at least to my knowledge) that is not featured in the current stochastic and adversarial MAB literature. While the paper is very closely related to a recent work by Gur, Zeevi and Besbes (2014), a main difference is that the amount of variation in the arms distributions is not known in the current paper's setting.  
Minor typos:  Line 238 - 239: In the definition of \epsilon_2(n_1, n_2) on page 6 (between line 238 and 239), the quantity is undefined when n_2 = n, n_1 = 1. Is there a typo?  Line 302: \Delta \geq \tau^{-\lambda^2} should be \Delta \geq \Theta(\tau^{-\lambda^2})  Line 424: The reference for Hoeffding inequality is missing.  Suggested additional references:  A. Garivier and E. Moulines, "On upper-confidence bound policies for non-stationary bandit problems" in Algorithm Learning Theory (ALT), ser. Lectures notes in Computer Science, vol. 6925, 2011   Comments:  The proposed algorithm is novel in the sense that it actively detects if there is any change in the arms' distribution, which is quite different from the current literature, including the one above. Designing online algorithm that competes well against the dynamic benchmark is clearly an important topic in MAB, and the paper makes a major step by designing such an algorithm without knowing the variation budget. Indeed, previous works such as [1, 7] referred in the manuscript requires knowing the variation budget beforehand to tune the learning rate, and it is quite surprising that one can achieves a sublinear regret without the knowledge. Thus, I think this submission will be interesting to the MAB community. The paper is quite clearly written, given the level of technicality.   Finally, what is the regret order bound with K arms?