# Bounds on the price of feedback for mistake-bounded online learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 6 of its 29 references that are in the map.
- First posted on arXiv 11 Jan 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [The price of bandit information in multiclass online classification](https://mlsanity.com/paper/1302.1043/) (2013)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [A note on the price of bandit feedback for mistake-bounded online learning](https://mlsanity.com/paper/2101.06891/) (2021)
- [Near-tight closure bounds for Littlestone and threshold dimensions](https://mlsanity.com/paper/2007.03668/) (2020)
- [Sharp bounds on the price of bandit feedback for several models of mistake-bounded online learning](https://mlsanity.com/paper/2209.01366/) (2022)
- [Online Learning of Smooth Functions](https://mlsanity.com/paper/2301.01434/) (2023)

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

- [Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs](https://mlsanity.com/paper/2402.07453/) (2024)
- [Mistake-bounded online learning with operation caps](https://mlsanity.com/paper/2509.03892/) (2025)
- [Online learning of smooth functions on ℝ](https://mlsanity.com/paper/2604.03525/) (2026)
- [Optimal Randomized Proper Online Learning](https://mlsanity.com/paper/2609.21445/) (2026)

## Abstract (arXiv)

We improve several worst-case bounds for various online learning scenarios from (Auer and Long, Machine Learning, 1999). In particular, we sharpen an upper bound for delayed ambiguous reinforcement learning by a factor of 2 and an upper bound for learning compositions of families of functions by a factor of 2.41. We also improve a lower bound from the same paper for learning compositions of k families of functions by a factor of Theta(lnk), matching the upper bound up to a constant factor. In addition, we solve a problem from (Long, Theoretical Computer Science, 2020) on the price of bandit feedback with respect to standard feedback for multiclass learning, and we improve an upper bound from (Feng et al., Theoretical Computer Science, 2023) on the price of r-input delayed ambiguous reinforcement learning by a factor of r, matching a lower bound from the same paper up to the leading term.