# Online Learning and Solving Infinite Games with an ERM Oracle

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 4 Jul 2023.

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

- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [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)
- [Improved Generalization Bounds for Adversarially Robust Learning](https://mlsanity.com/paper/1810.02180/) (2018)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [Majorizing Measures, Sequential Complexities, and Online Learning](https://mlsanity.com/paper/2102.01729/) (2021)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique](https://mlsanity.com/paper/2211.01443/) (2022)
- [Developing, Evaluating and Scaling Learning Agents in Multi-Agent Environments](https://mlsanity.com/paper/2209.10958/) (2022)

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

- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Steering Language Models with Game-Theoretic Solvers](https://mlsanity.com/paper/2402.01704/) (2024)
- [Simple online learning with consistent oracle](https://mlsanity.com/paper/2308.08055/) (2023)
- [Algorithmic Robust Forecast Aggregation](https://mlsanity.com/paper/2401.17743/) (2024)
- [Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?](https://mlsanity.com/paper/2406.11667/) (2024)
- [Effective Littlestone Dimension](https://mlsanity.com/paper/2411.15109/) (2024)
- [Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning](https://mlsanity.com/paper/2506.00135/) (2025)
- [Computable universal online learning](https://mlsanity.com/paper/2510.18352/) (2025)
- [Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning](https://mlsanity.com/paper/2605.07155/) (2026)
- [The Hidden Game Problem](https://mlsanity.com/paper/2510.03845/) (2025)
- [Encoding orders and trees in real-valued functions](https://mlsanity.com/paper/2607.21761/) (2026)

## Abstract (arXiv)

While ERM suffices to attain near-optimal generalization error in the stochastic learning setting, this is not known to be the case in the online learning setting, where algorithms for general concept classes rely on computationally inefficient oracles such as the Standard Optimal Algorithm (SOA). In this work, we propose an algorithm for online binary classification setting that relies solely on ERM oracle calls, and show that it has finite regret in the realizable setting and sublinearly growing regret in the agnostic setting. We bound the regret in terms of the Littlestone and threshold dimensions of the underlying concept class. We obtain similar results for nonparametric games, where the ERM oracle can be interpreted as a best response oracle, finding the best response of a player to a given history of play of the other players. In this setting, we provide learning algorithms that only rely on best response oracles and converge to approximate-minimax equilibria in two-player zero-sum games and approximate coarse correlated equilibria in multi-player general-sum games, as long as the game has a bounded fat-threshold dimension. Our algorithms apply to both binary-valued and real-valued games and can be viewed as providing justification for the wide use of double oracle and multiple oracle algorithms in the practice of solving large games.