Adaptation to Easy Data in Prediction with Limited Advice
We derive an online learning algorithm with improved regret guarantees for "easy" loss sequences. We consider two types of "easiness": (a) stochastic loss sequences and (b) adversarial loss sequences with small effective range of the losses. While a number of algorithms have been proposed for exploiting small effective range in the full information setting, Gerchinovitz and Lattimore [2016]  have shown the impossibility of regret scaling with the effective range of the losses in the bandit setting. We show that just one additional observation per round is sufficient to circumvent the impossibility result. The proposed Second Order Difference Adjustments (SODA) algorithm requires no prior knowledge of the effective range of the losses, ε, and achieves an O(ε
expected regret guarantee, where T is the time horizon and K is the number of actions. The scaling with the effective loss range is achieved under significantly weaker assumptions than those made by Cesa-Bianchi and Shamir [2018]  in an earlier attempt to circumvent the impossibility result. We also provide a regret lower bound of Ω(ε √ T K), which almost matches the upper bound. In addition, we show that in the stochastic setting SODA achieves an O a:∆a>0
Kε 2 ∆a pseudo-regret bound that holds simultaneously with the adversarial regret guarantee. In other words, SODA is safe against an unrestricted oblivious adversary and provides improved regret guarantees for at least two different types of "easiness" simultaneously.
The paper presents an novel online algorithm for stochastic losses and adversarial losses with a small range under the assumption that they can observe an additional loss per round. In the adversarial setting, they provide a lower bound that almost matched their upper bound. In the stochastic setting, their regret bound remarkably does not depend on the rounds T.   Even though the setting described in the paper can be characterized by a sequence of feedback graphs, the authors do not cite or compare to the large body of literature of online learning with feedback graphs (i.e. "Online Learning with Feedback Graphs: Beyond Bandits" by Alon at al. 2015, "Online Learning with Feedback Graphs Without the Graphs" Cohen et al. 2016, "Leveraging Side Observations in Stochastic Bandits" by Caron et al. 2012).  Leveraging Side Observations in Stochastic Bandits by Caron et al. 2012 prove a lower bound of log(T) for stochastic losses when the feedback graph is fixed. The feedback graph used in the current paper is more complex than a fixed graph so it is surprising that they can attain a bound that does not depend on log T. I am not sure how the lower bound of Caron et al. can be reconciled with the stochastic bound in the paper, but it might be because in the current paper, they are allowed to chose which second arm they want to observe. Nevertheless, a thorough discussion and analysis is warranted here.   Another criticism is that they claim their assumptions are weak. Via their assumptions, they can bypass the impossibility result of Gerchinovitz and Lattimore [2016], but allowing an extra loss observation is essentially changing the setting and moreover they allow the algorithm to chose the second arm that they get to observe.  Adding extra loss observations even if it's just one more at each round can be hugely beneficial as shown in the above feedback graphs papers.   The paper is understandable, but not well written or polished.   Due to the lack of comparison to on-line learning with feedback graphs and the fact that Caron et al. 2012 have a lower bound that depends on log(T), I cannot vote to accept unless these issues are addressed by the authors in the rebuttal.   ----------------------------------------------------------------------------------------------- The authors have adequately addressed my concerns and hence I increased their overall score.