# Oracle-Efficient Hybrid Online Learning with Unknown Distribution

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 25 references that are in the map.
- First posted on arXiv 27 Jan 2024.

## Builds on (most cited first, 9 of 9)

- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits](https://mlsanity.com/paper/1602.02196/) (2016)
- [Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits](https://mlsanity.com/paper/1606.00313/) (2016)
- [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022)
- [Online Learning in Dynamically Changing Environments](https://mlsanity.com/paper/2302.00103/) (2023)
- [Smoothed Analysis of Sequential Probability Assignment](https://mlsanity.com/paper/2303.04845/) (2023)
- [An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits](https://mlsanity.com/paper/2310.19025/) (2023)

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

- [Oracle-efficient Hybrid Learning with Constrained Adversaries](https://mlsanity.com/paper/2603.04546/) (2026)
- [Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs](https://mlsanity.com/paper/2609.33760/) (2026)
- [Agnostic Smoothed Online Regression with Adversarial Responses](https://mlsanity.com/paper/2609.32478/) (2026)
- [Sample-Optimal Multi-Group Learning with an ERM Oracle](https://mlsanity.com/paper/2610.15916/) (2026)

## Abstract (arXiv)

We study the problem of oracle-efficient hybrid online learning when the features are generated by an unknown i.i.d. process and the labels are generated adversarially. Assuming access to an (offline) ERM oracle, we show that there exists a computationally efficient online predictor that achieves a regret upper bounded by tildeO(T^frac34) for a finite-VC class, and upper bounded by tildeO(T^fracp+1p+2) for a class with α fat-shattering dimension α-p. This provides the first known oracle-efficient sublinear regret bounds for hybrid online learning with an unknown feature generation process. In particular, it confirms a conjecture of Lazaric and Munos (JCSS 2012). We then extend our result to the scenario of shifting distributions with K changes, yielding a regret of order tildeO(T^frac45K^frac15). Finally, we establish a regret of tildeO((K^frac23(log|H|)^frac13+K)· T^frac45) for the contextual K-armed bandits with a finite policy set H, i.i.d. generated contexts from an unknown distribution, and adversarially generated costs.