# Online Learning with Bounded Recall

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 33 references that are in the map.
- First posted on arXiv 28 May 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Failing Loudly: An Empirical Study of Methods for Detecting Dataset Shift](https://mlsanity.com/paper/1810.11953/) (2018)
- [A Fine-Grained Analysis on Distribution Shift](https://mlsanity.com/paper/2110.11328/) (2021)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [On the optimality of the Hedge algorithm in the stochastic regime](https://mlsanity.com/paper/1809.01382/) (2018)
- [Econometrics for Learning Agents](https://mlsanity.com/paper/1505.00720/) (2015)
- [Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning](https://mlsanity.com/paper/1605.06439/) (2016)
- [Privacy Accounting and Quality Control in the Sage Differentially Private ML Platform](https://mlsanity.com/paper/1909.01502/) (2019)
- [Online Prediction With History-Dependent Experts: The General Case](https://mlsanity.com/paper/2008.00052/) (2020)
- [Exponential Weights Algorithms for Selective Learning](https://mlsanity.com/paper/2106.15662/) (2021)

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

- [Adversarial Online Learning with Temporal Feedback Graphs](https://mlsanity.com/paper/2407.00571/) (2024)
- [Next-Token Prediction and Regret Minimization](https://mlsanity.com/paper/2603.28499/) (2026)

## Abstract (arXiv)

We study the problem of full-information online learning in the "bounded recall" setting popular in the study of repeated games. An online learning algorithm A is M-textitbounded-recall if its output at time t can be written as a function of the M previous rewards (and not e.g. any other internal state of A). We first demonstrate that a natural approach to constructing bounded-recall algorithms from mean-based no-regret learning algorithms (e.g., running Hedge over the last M rounds) fails, and that any such algorithm incurs constant regret per round. We then construct a stationary bounded-recall algorithm that achieves a per-round regret of Theta(1/√M), which we complement with a tight lower bound. Finally, we show that unlike the perfect recall setting, any low regret bound bounded-recall algorithm must be aware of the ordering of the past M losses -- any bounded-recall algorithm which plays a symmetric function of the past M losses must incur constant regret per round.