A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity

We investigate the fixed-budget best-arm identification (BAI) problem for linear bandits in a potentially non-stationary environment. Given a finite arm set Xsubsetℝd, a fixed budget T, and an unpredictable sequence of parameters leftlbraceθtrightrbracet=1T, an algorithm will aim to correctly identify the best arm x^* := argmaxx∈Xx^topsumt=1Tθt with probability as high as possible. Prior work has addressed the stationary setting where θt = θ1 for all t and demonstrated that the error probability decreases as exp(-T /ρ^*) for a problem-dependent constant ρ^*. But in many real-world A/B/n multivariate testing scenarios that motivate our work, the environment is non-stationary and an algorithm expecting a stationary setting can easily fail. For robust identification, it is well-known that if arms are chosen randomly and non-adaptively from a G-optimal design over X at each time then the error probability decreases as exp(-TDelta2(1)/d), where Delta(1) = minx neq x^* (x^* - x)^top frac1Tsumt=1T θt. As there exist environments where Delta(1)2/ d ll 1/ ρ^*, we are motivated to propose a novel algorithm mathsfP1-mathsfRAGE that aims to obtain the best of both worlds: robustness to non-stationarity and fast rates of identification in benign settings. We characterize the error probability of mathsfP1-mathsfRAGE and demonstrate empirically that the algorithm indeed never performs worse than G-optimal design but compares favorably to the best algorithms in the stationary setting.