# Adaptation to Easy Data in Prediction with Limited Advice

arXiv: https://arxiv.org/abs/1807.00636 · HTML: https://mlsanity.com/paper/1807.00636/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2018.

## Built on by (most cited first, 7 of 7)

- [Adaptively Exploiting d-Separators with Causal Bandits](https://mlsanity.com/paper/2202.05100/) (2022)
- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Nested bandits](https://mlsanity.com/paper/2206.09348/) (2022)
- [Fast rates for prediction with limited expert advice](https://mlsanity.com/paper/2110.14485/) (2021)
- [Constant regret for sequence prediction with limited advice](https://mlsanity.com/paper/2210.02256/) (2022)
- [Group Distributionally Robust Optimization with Flexible Sample Queries](https://mlsanity.com/paper/2505.15212/) (2025)
- [Leveraging Similarities in Multi-Armed Bandits](https://mlsanity.com/paper/2606.23414/) (2026)

## Abstract (arXiv)

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, varepsilon, and achieves an O(varepsilon √KT ln K) + tildeO(varepsilon K √[4]T) 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 Omega(varepsilon√T K), which almost matches the upper bound. In addition, we show that in the stochastic setting SODA achieves an Oleft(suma:Deltaa>0 fracK3 varepsilon2Deltaaright) 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.