Lookahead identification in adversarial bandits: accuracy and memory bounds

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.