Online learning

Littlestone dimension, the optimal mistake bound, and where online learning sits relative to PAC.

• MTH.C-2026-6010littlestone_characterization

  Littlestone characterization: C is online-learnable iff LittlestoneDim(C) < ∞.

• MTH.C-2026-6011optimal_mistake_bound_eq_ldim

  The optimal mistake bound equals the Littlestone dimension (for nonempty C). Path B: OptimalMistakeBound : WithTop ℕ, LittlestoneDim : WithBot (WithTop ℕ). For nonempty C, LittlestoneDim ≥ 0, so the coercion ↑(OptimalMistakeBound) works.

• MTH.C-2026-6028online_strictly_stronger_pac

  Online learning is strictly stronger than PAC learning.