Papers βΊ A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity
A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity
Zhihan Xiong, Romain Camilleri, Maryam Fazel, Lalit Jain, Kevin Jamieson
We investigate the fixed-budget best-arm identification (BAI) problem for linear bandits in a potentially non-stationary environment. Given a finite arm set π³ββα΅, a fixed budget T, and an unpredictable sequence of parameters {ΞΈβ}βββα΅, an algorithm will aim to correctly identify the best arm x^* := argmax_(xβπ³)x^β€ββββα΅ΞΈβ with probability as high as possible. Prior work has addressed the stationary setting where ΞΈβ = ΞΈβ 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 π³ at each time then the error probability decreases as exp(-TΞΒ²βββ/d), where Ξβββ = min_(x β x^*) (x^* - x)^β€ 1/Tββββα΅ ΞΈβ. As there exist environments where ΞβββΒ²/ d βͺ1/ Ο^*, we are motivated to propose a novel algorithm P1-RAGE 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 P1-RAGE 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.
Syntology This paper's arXiv id is not in Syntology's Atlas id list (549,449 ids, as this build read them; the read time is in the build record), so this page links to no Syntology page for it. The list is not the whole graph; Syntology's feed shows papers as they enter the graph.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Report a problem or propose a change Β· a person checks every report against the paper or source before anything changes; decisions are listed on /corrections