Lookahead identification in adversarial bandits: accuracy and memory bounds

Nataly Brukhim, Nicolò Cesa-Bianchi, Carlo Ciliberto · 2026

Read Lookahead identification in adversarial bandits: accuracy and memory bounds by Nataly Brukhim, Nicolò Cesa-Bianchi, Carlo Ciliberto (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-00803.txt.

Introduction

Brukhim, Cesa-Bianchi, and Ciliberto introduce lookahead identification for adversarial bandits, where past performance says little about the future. The learner picks a future window in advance and commits to an arm whose window average reward sits within epsilon of optimal. For any horizon, an algorithm reaches epsilon of order one over root log horizon across many windows, proving identification possible despite scarce information. A near matching lower bound shows epsilon of order one over log horizon cannot be beaten. The paper turns to the memory such identification requires.

Catalog record

CREATORNataly Brukhim, Nicolò Cesa-Bianchi, Carlo Ciliberto
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65497
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.00803

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lookahead identification in adversarial bandits: accuracy and memory bounds Nataly Brukhim, Nicolò Cesa-Bianchi, Carlo Ciliberto Abstract We study an identification problem in multi-armed bandits. In each round a learner selects one of K K arms and observes its reward, with the goal of eventually identifying an arm that will perform best at a 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 T we give an algorithm achieving ε = O ⁡ ( 1 / log ⁡ T ) \varepsilon=O\bigl(1/\sqrt{\log T}\bigr) over Ω ⁡ ( T ) \Omega(\sqrt{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 ε = Ω ⁡ ( 1 / log ⁡ T ) \varepsilon=\Omega\bigl(1/\log T\bigr) is unavoidable. We then turn to investigate the role of memory in our problem, first proving that any algorithm achieving nontrivial accuracy requires Ω ⁡ ( K ) \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. Finally, we contrast lookahead identification with the more standard objective of regret minimization. We show a sharp separation between identification and regret: despite strong memory lower bounds for identification, sublinear regret can be attained using only limited memory. Specifically, we give an algorithm achieving O ~ ​ ( T 2 / 3 ​ K 1 / 3 ) \tilde{O}(T^{2/3}K^{1/3}) regret using poly-logarithmic memory. Our result significantly improves upon prior work both in terms of the regret and the memory bounds. \coltauthor DIMACS, Rutgers University Institute for Advanced Study and Università degli Studi di Milano Politecnico di Milano and Centre for artificial intelligence University College London 1 Introduction The multi-armed bandit (MAB) model serves as a canonical framework in sequential prediction. In each round t=1,\ldots,T the algorithm may query any arm i\in[K] , it then gets to observe a reward value X_{t,i}\in[0,1] , and updates its strategy for future rounds. The two primary tasks considered under this model are the best-arm identification (BAI), also known as pure exploration, and regret minimization . In the identification task, we are interested in finding the best arm, defined as the arm with the highest mean reward, using minimal number of queries T . On the other hand, in regret minimization, the goal is to minimize the difference between the cumulative reward achieved by the algorithm and that of the single best arm in hindsight. While the stochastic MAB setting has been studied extensively, prior work on adversarial MAB has focused almost exclusively on regret minimization, and not addressed the BAI task. The reason for this gap is clear; the standard BAI objective is essentially futile under adversarial rewards. That is, identifying the arm with the largest past cumulative reward seems to offer no guidance about which arm will perform best in the future , precisely because of the adversarial nature of the problem. To address this gap, we formulate the task of lookahead BAI , where instead of identifying the arm with the best historical performance, the goal of lookahead BAI is to find an arm that will provide the highest expected cumulative gain over a future time window. The algorithm is allowed to choose the starting time, as well as the length, of the prediction window (within pre-specified ranges), possibly depending on the observations so far. The lookahead BAI task is motivated by applications of the classic BAI task in stochastic bandits ( Bubeck et al. 2009 ; Garivier and Kaufmann 2016 ; Karnin et al. 2013 ) , including online advertising, web content optimization and A/B testing, and clinical trials. In these applications the algorithm may choose a stopping-time but must then commit to a single decision without further experimentation as additional exploration is resource-intensive. However, while this setting is well-motivated, it has not been studied in the adversarial regime. Removing unrealistic (stochastic, or other) assumptions makes the problem substantially more challenging, and to the best of our knowledge,our work provides the first positive results in adversarial best-arm identification. Our first contribution is that even under no assumptions on the data , non-trivial guarantees can be achieved with error at most O(1/\sqrt{\log(T)}) . We then show that this bound is near-tight with a lower bound of \Omega(1/{\log(T)}) . Next, we turn to study memory-accuracy trade-offs for lookahead-BAI, as well as for the classical regret minimization objective. Memory constraints In recent years, the study of online learning under bounded memory constraints has attracted considerable attention. While most works consider the stochastic MAB setting Agarwal et al. 2022 ; Maiti et al. 2021 ; Wang 2023 , recent work ( Srinivas et al. 2022 ; Peng and Rubinstein 2023 ; Peng and Zhang 2023 ) initiated the study of memory bounds for the adversarial expert problem , providing a tight characterization of the memory-regret tradeoff. However, this does not generalize to the bandit setting with limited feedback. Upper bounds Lower bounds BAI \epsilon=O(\frac{1}{\sqrt{\log{T}}}) , \sigma=\tilde{O}(K) (Theorem 2 ) \epsilon=\Omega(\frac{1}{{\log{T}}}) , \sigma={\Omega}(K) (Theorem 5 , Theorem 8 ) BAI, Sparse case \epsilon=O(\frac{1}{\sqrt{\log{T}}}) , \sigma=\tilde{O}(1) (Theorem 14 ) – Regret R=\tilde{O}(T^{2/3}K^{1/3}) , \sigma=\tilde{O}(1) (Theorem 17 ) R=\Omega(\sqrt{KT}),\sigma=\Omega(\text{poly-log}(KT)) ( Srinivas et al. 2022 ; Peng and Rubinstein 2023 ) Table 1: Summary of results . The above table presents our main results in this work, where in all cases the MAB bandit model is assumed, with K arms and T rounds. The bounds for the lookahead BAI task (see Definition 1 ) are given in the first row, for the error \epsilon , and \sigma the total number of memory bits required. The second row also addresses the lookahead BAI task, under a general sparsity condition (see Definition 10 ). The last row gives regret bounds R , as well as memory bounds. The \tilde{O}(\cdot) hides poly-logarithmic factors in both K and T . Characterizing the lower bounds BAI in the sparse setting remains an open question. In this work, we consider both the lookahead BAI and regret minimization tasks under bounded memory constraints. First, we show that while our algorithm for the lookahead BAI problem incurs a large memory cost of \Omega(K) , that is unavoidable in general. Then, we consider a relaxed setting in which we assume a general sparsity condition applies. We prove that when this condition is satisfied, significant memory improvements can be achieved. Specifically, we give an algorithm for the lookahead BAI task that requires at most O(\text{poly-log}(KT)) bits of memory, for a broad family of sparse bandit instances. To understand whether this \Omega(K) memory requirement is inherent to adversarial bandits or specific to lookahead prediction, we also investigate the regret minimization task. Srinivas et al.

Read the complete text