Tracking the Best Expert in Non-stationary Stochastic Environments
We study the dynamic regret of multi-armed bandit and experts problem in nonstationary stochastic environments. We introduce a new parameter Λ, which measures the total statistical variance of the loss distributions over T rounds of the process, and study how this amount affects the regret. We investigate the interaction between Λ and Γ, which counts the number of times the distributions change, as well as Λ and V , which measures how far the distributions deviates over time. One striking result we find is that even when Γ, V , and Λ are all restricted to constant, the regret lower bound in the bandit setting still grows with T . The other highlight is that in the full-information setting, a constant regret becomes achievable with constant Γ and Λ, as it can be made independent of T , while with constant V and Λ, the regret still has a T 1/3 dependency. We not only propose algorithms with upper bound guarantee, but prove their matching lower bounds as well.
The paper considers online learning in a non-stationary stochastic environment, and considers the achievable regret as a function of the change in the mean loss vector (measured by the number of switches or the amount of shift) and the cumulative variance of the random losses. Algorithms are given with regret upper bounds, as well as matching lower bounds. 
ADDED AFTER THE REBUTTAL:  - Indeed, the proof of Theorem 4.1 is correct, and the constructed environment is oblivious; it was my mistake, sorry about it. - The generalization in the analysis of UCB-V seems quite straightforward, as--if I recall correctly--the applied concentration inequalities do not require that the random variables have the same distribution (neither in your nor in their case). - Comparison to Jadbabaie et al: If in their work one chooses M to be the previous gradient, then their D_T is essentially the same as your Lambda (up to some constants), and the difference is that you take expectation inside the norms in V. While I might be mistaken here, but it seems to me that with a slight modification of their proof you can move the expectation inside. Nevertheless, you have to check this, and describe the connection to related work with care (what follows easily and what not). - You should still argue why the proposed complexity parameters are interesting, e.g., present an example when Lambda is not zero or linear in T.   -----------------------------------------  While the paper might have some interesting contributions, it does not consider the existing literature and does not cite the references adequately. This, in fact, makes it hard to asses the novelty of the results, as several of them seem to easily follow from existing work. In fact, the paper of Jadbabaie, Rakhlin, Shahrampour, and Sridharan, whose arxiv version is "sort of" cited in the paper (included in the references but never discussed properly), which was published in AISTATS 2015, provides an algorithm quite similar to Algorithm 2, which achieves similar bounds, but in the stronger adversarial case.   The main addition of the paper to admitted existing work (Besbes et al., 2014--please correct the order of the authors in the reference) is to consider the variance of the random losses. As far as I can see, this is achieved by combining the techniques to derive second order bounds and some sort of shifting bounds (even blocking, in the simplest case). This would be interesting if it had not been done before by Jadbabaie et al. (2015). However, given the previous work, a thorough discussion of novelty would be required. Also, the writing of the paper has to be improved dramatically: e.g., not even the UCB-V algorithm of Audibert et al. (2009) is referenced (although used almost identically).    Concerning motivation, other than saying that the complexity measures used in the paper appear in the literature, why are they interesting? For example, if there is a clearly suboptimal arm, why does it matter if its mean changes or it has a relatively high variance (assume that even the smallest loss from this arm is bigger than the losses of any other arm)? What are the interesting cases when \Lambda is not constant or linear in time? Also, what is the connection to tracking/shifting bounds (Herbster and Warmuth 1998, 2001)? Note that in the standard online learning literature, tracking and shifting bounds usually correspond to properties of the comparator sequence, not of the loss functions, so this should be clarified to avoid confusion. The switching results should also relate to the large body of work done in information theory on coding piecewise stationary sources (although there usually the log-loss is considered, but the techniques are essentially the same, although instead of the variance the the entropy/entropy-rate of the source is considered). The sleeping expert-type reductions are also available in generic forms, see e.g., Gyorgy et al. (2012) and the references therein.     All in all, I see potential in the paper, but substantial improvements are needed before it can be published.  References:  J-Y. Audibert, R. Munos, and Cs Szepesvari. Exploration-exploitation trade-off using variance estimates in multi-armed bandits. Theoretical Computer Science, 410:1876-1902, 2009.   A. Gyorgy, T. Linder, and G. Lugosi, "Efficient Tracking of Large Classes of Experts," IEEE Transactions on Information Theory, vol. 58, pp. 6709-6725, November 2012.  Herbster, M. and Warmuth, M.K. (1998) “Tracking the Best Expert”, in the special issue on context sensitivity and concept drift of the Journal of Machine Learning, Vol. 32(2), pp. 151-178, August 1998.  Herbster, M. and Warmuth, M.K. (2001) “Tracking the Best Linear Predictor”, Journal of Machine Learning Research, Vol. 1, pp. 281-309, September 2001.