Refined Lower Bounds for Adversarial Bandits
We provide new lower bounds on the regret that must be suffered by adversarial bandit algorithms. The new results show that recent upper bounds that either (a) hold with high-probability or (b) depend on the total loss of the best arm or (c) depend on the quadratic variation of the losses, are close to tight. Besides this we prove two impossibility results. First, the existence of a single arm that is optimal in every round cannot improve the regret in the worst case. Second, the regret cannot scale with the effective range of the losses. In contrast, both results are possible in the full-information setting.
This paper presents several lower bounds for adversarial bandit setting. In most cases, upper bounds matching these lower bounds  (within logarithmic factors) are known, but it was not known earlier if those upper bounds bounds were tight. In one case (second order bounds in terms quadratic variation) there is a gap between the best known upper bound and the lower bound shown by the authors. 
 Merits: It is a good paper to read, well-written and with very few typos. While most results provided in this paper are as one would expect in these problems (the authors also note this), I think it does the necessary job of filling the gaps in this literature and prove tightness of many existing algorithms.  From technical point of view, the construction of stochastic correlated losses used for Theorem 1 and 2 (zero order bounds) and its proof seems particularly interesting, and different from the common constructions for lower bounds in this literature (like the one used in Section 3 for first order bounds). It will be useful to provide some further intuition on why constructions like those used first order bounds don't work for zero order bounds. I can see that Section 3 techniques are good for proving expected bound, while for zero order bounds authors need a construction where they can employ Lemma 2. But, the authors may be able to provide a better high level intuition.   Critique:  As mentioned earlier, the results in these papers are not very surprising. Most of the techniques, barring the construction Section 2, are standard in the literature.  Summary of review: Overall, I think it is a good technical paper, which will be of interest and useful to researchers working in this area.