Lookahead identification in adversarial bandits: accuracy and memory bounds

Nataly Brukhim; Nicolò Cesa-Bianchi; Carlo Ciliberto

cs.LGFeb 28, 2026

Lookahead identification in adversarial bandits: accuracy and memory bounds

Authors: Nataly Brukhim, Nicolò Cesa-Bianchi, Carlo Ciliberto

Organizations: DIMACS, Rutgers University · Institute for Advanced Study · Universit`a degli Studi di Milano · Politecnico di Milano · Centre for artificial intelligence · University College London

Abstract

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 = O\bigl(1/\sqrt{\log T}\bigr)$ over $Ω(\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 $\varepsilon = Ω\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)$ bits of memory. Under a natural local sparsity condition, we show that the same accuracy guarantees can be achieved using only poly-logarithmic memory.

Figures & tables

	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.

\hat{i}=\arg\max_{i\in[K]}\ {\tilde{n}}_{i}

Algorithm 1 Bandit lookahead best-arm identification

Explore similar work

Apr 16, 2026

Best of both worlds: Stochastic & adversarial best-arm identification

We study bandit best-arm identification with arbitrary and potentially adversarial rewards. A simple random uniform learner obtains the optimal rate of error in the adversarial scenario. However, this type of strategy is suboptimal when the rewards are sampled stochastically. Therefore, we ask: Can we design a learner that performs optimally in both the stochastic and adversarial problems while not being aware of the nature of the rewards? First, we show that designing such a learner is impossible in general. In particular, to be robust to adversarial rewards, we can only guarantee optimal rates of error on a subset of the stochastic problems. We give a lower bound that characterizes the optimal rate in stochastic problems if the strategy is constrained to be robust to adversarial rewards. Finally, we design a simple parameter-free algorithm and show that its probability of error matches (up to log factors) the lower bound in stochastic problems, and it is also robust to adversarial ones.

Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon +2

Adobe Research, USA · University of California, Berkeley, USA · Queensland University of Technology - ACEMS, Australia +2

Multi-Armed Bandits Best-Arm Identification Adversarial Bandits

Ask PDF

Mar 11, 2026

On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits

We study the fixed-budget best-arm identification (BAI) problem in non-stationary linear bandits. Concretely, given a fixed time budget

T\in \mathbb{N}

, finite arm set

\mathcal{X} \subset \mathbb{R}^d

, and a potentially adversarial sequence of unknown parameters

\lbrace θ_t\rbrace_{t=1}^{T}

(hence non-stationary), a learner aims to identify the arm with the largest cumulative reward

x_* = \arg\max_{x \in \mathcal{X}} x^\top\sum_{t=1}^T θ_t

with high probability. In this setting, it is well-known that uniformly sampling arms from the G-optimal design yields a minimax-optimal error probability of

\exp\left(-Θ\left(T / H_{G}\right)\right)

, where

H_{G}

scales proportionally with the dimension

d

. However, this notion of complexity is overly pessimistic, as it is derived from a lower bound in which the arm set consists only of the standard basis vectors, thus masking any potential advantages arising from arm sets with richer geometric structure. To address this, we establish an arm-set-dependent lower bound that, in contrast, holds for any arm set. Motivated by the ideas underlying our lower bound, we propose the Adjacent-optimal design, a specialization of the well-known

\mathcal{X}\mathcal{Y}

-optimal design, and develop the

\textsf{Adjacent-BAI}

algorithm. We prove that the error probability of

\textsf{Adjacent-BAI}

matches our lower bound up to constants, verifying the tightness of our lower bound, and establishing the arm-set-dependent complexity of this setting.

Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson +1

University of Washington

Multi-Armed Bandits Best-Arm Identification Non-Stationary Bandits

Ask PDF

May 1, 2026

Trading off rewards and errors in multi-armed bandits

In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.

Akram Erraqabi, Alessandro Lazaric, Michal Valko +2

Inria SequeL · CMU · EnLearn

Multi-Armed Bandits Exploration-Exploitation Tradeoff Best-Arm Identification Regret Minimization

Ask PDF