# Lookahead identification in adversarial bandits: accuracy and memory bounds

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 19 references that are in the map.
- First posted on arXiv 28 Feb 2026.

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits](https://mlsanity.com/paper/2205.00984/) (2022)
- [Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits](https://mlsanity.com/paper/2306.02208/) (2023)
- [Memory-Constrained No-Regret Learning in Adversarial Bandits](https://mlsanity.com/paper/2002.11804/) (2020)
- [A Theory of Selective Prediction](https://mlsanity.com/paper/1902.04256/) (2019)

## Abstract (arXiv)

We study an identification problem in multi-armed bandits. In each round a learner selects one of K arms and observes its reward, with the goal of eventually identifying an arm that will perform best at a it future time. In adversarial environments, however, past performance may offer little information about the future, raising the question of whether meaningful identification is possible at all. In this work, we introduce lookahead identification, a task in which the goal of the learner is to select a future prediction window and commit in advance to an arm whose average reward over that window is within varepsilon of optimal. Our analysis characterizes both the achievable accuracy of lookahead identification and the memory resources required to obtain it. From an accuracy standpoint, for any horizon T we give an algorithm achieving varepsilon = Obigl(1/√log Tbigr) over Omega(√T) prediction windows. This demonstrates that, perhaps surprisingly, identification is possible in adversarial settings, despite significant lack of information. We also prove a near-matching lower bound showing that varepsilon = Omegabigl(1/log Tbigr) is unavoidable. We then turn to investigate the role of memory in our problem, first proving that any algorithm achieving nontrivial accuracy requires Omega(K) bits of memory. Under a natural local sparsity condition, we show that the same accuracy guarantees can be achieved using only poly-logarithmic memory.