# Ambiguous Online Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 17 references that are in the map.
- First posted on arXiv 24 Jun 2025.

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

- [Conformal Prediction: a Unified Review of Theory and New Challenges](https://mlsanity.com/paper/2005.07972/) (2020)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [List Online Classification](https://mlsanity.com/paper/2303.15383/) (2023)
- [Probably Approximately Precision and Recall Learning](https://mlsanity.com/paper/2411.13029/) (2024)
- [Regret Bounds for Robust Online Decision Making](https://mlsanity.com/paper/2504.06820/) (2025)
- [Apple Tasting: Combinatorial Dimensions and Minimax Rates](https://mlsanity.com/paper/2310.19064/) (2023)
- [Deterministic Apple Tasting](https://mlsanity.com/paper/2410.10404/) (2024)
- [Imprecise Multi-Armed Bandits](https://mlsanity.com/paper/2405.05673/) (2024)

## Abstract (arXiv)

We propose a new variant of online learning that we call "ambiguous online learning". In this setting, the learner is allowed to produce multiple predicted labels. Such an "ambiguous prediction" is considered correct when at least one of the labels is correct, and none of the labels are "predictably wrong". The definition of "predictably wrong" comes from a hypothesis class in which hypotheses are also multi-valued. Thus, a prediction is "predictably wrong" if it's not allowed by the (unknown) true hypothesis. In particular, this setting is natural in the context of multivalued dynamical systems, recommendation algorithms and lossless compression. It is also strongly related to so-called "apple tasting". We show that in this setting, there is a trichotomy of mistake bounds: up to logarithmic factors, any hypothesis class has an optimal mistake bound of either Theta(1), Theta(sqrt(N)) or N.