# Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 27 references that are in the map.
- First posted on arXiv 8 May 2026.

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

- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Efficient Algorithms for Adversarial Contextual Learning](https://mlsanity.com/paper/1602.02454/) (2016)
- [Oracle-Efficient Online Learning and Auction Design](https://mlsanity.com/paper/1611.01688/) (2016)
- [Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries](https://mlsanity.com/paper/2202.08549/) (2022)
- [On the Performance of Empirical Risk Minimization with Smoothed Data](https://mlsanity.com/paper/2402.14987/) (2024)
- [On Computable Online Learning](https://mlsanity.com/paper/2302.04357/) (2023)
- [Online Learning and Solving Infinite Games with an ERM Oracle](https://mlsanity.com/paper/2307.01689/) (2023)
- [Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique](https://mlsanity.com/paper/2211.01443/) (2022)
- [Simple online learning with consistent oracle](https://mlsanity.com/paper/2308.08055/) (2023)
- [Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning](https://mlsanity.com/paper/2506.00135/) (2025)

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

- [An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order](https://mlsanity.com/paper/2609.10196/) (2026)

## Abstract (arXiv)

Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner. However, the SOA is computationally intractable to execute even for a single round. To overcome this barrier, recent work in oracle-efficient online learning replaces the SOA with a realizable base learner that accesses the concept class exclusively through an offline empirical risk minimization (ERM) oracle. While such agnostic learners achieve near-optimal expected regret, they suffer from a doubly-exponential oracle complexity of Obig(T^2O(dLD)big), where dLD is the Littlestone dimension and T is the number of rounds. In this work, we significantly improve this oracle complexity while relying on an even weaker primitive: a weak-consistency oracle, which merely decides whether a given labeled dataset is realizable. At the core of our approach is an adaptive and dynamic agnostic-to-realizable reduction that actively prunes non-realizable label sequences on the fly. By using the VC dimension (dVC) to bound the number of dynamically maintained active paths, our algorithm reduces the total query complexity down to O(TdVC+1) while perfectly preserving near-optimal expected regret. Crucially, this dynamic pruning also yields a memory reduction over the standard reduction. Furthermore, we formally quantify the regret--oracle complexity tradeoff, providing upper bounds that smoothly interpolate between restricted query budgets and attainable expected regret. We complement these with lower bounds proving that any learner restricted to Q = o(√T) queries must suffer an expected regret of Omega(T/Q).