Fixed-Budget Target-Time Best-Arm Identification in Temporally Evolving Bandits

Best-arm identification (BAI) in multi-armed bandits usually assumes stationary reward distributions while existing works on non-stationary BAI typically chase an arm with largest average reward over a predefined timespan. We introduce the new setting of *fixed-budget target-time BAI* where rewards may evolve away from a target decision time, and the learner must identify the best arm at that target without knowing the relevant temporal scale of non-stationarity in advance. This setting is motivated by laboratory studies that seek to identify the intervention producing the most favorable outcome at a target time –for example, at the beginning or at the end of a prescribed treatment schedule. Observations farther from the target may be less representative (ie *biased*) and deploying or evaluating an arm can be costly. This introduces a unique challenge where a learner has to manage the budget constraint using the right amount of data that can strike an optimal bias-variance tradeoff when performing BAI. In this work, we explore the limits of identifiability for the target-time non-stationary BAI problem and propose an algorithm that is information-theoretically near *optimal* (upto polylog factors) and *do not* require apriori knowledge of drift. Experiments on synthetic and real-world data expose the strengths and weaknesses of the proposed methods over existing BAI algorithms.