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

arXiv: https://arxiv.org/abs/2307.15154 · HTML: https://mlsanity.com/paper/2307.15154/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 47 references that are in the map.
- First posted on arXiv 27 Jul 2023.

## Builds on (most cited first, 17 of 17)

- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (2017)
- [An Efficient Bandit Algorithm for Realtime Multivariate Optimization](https://mlsanity.com/paper/1810.09558/) (2018)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Tracking Most Significant Arm Switches in Bandits](https://mlsanity.com/paper/2112.13838/) (2021)
- [Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2106.04763/) (2021)
- [Taking a hint: How to leverage loss predictors in contextual bandits?](https://mlsanity.com/paper/2003.01922/) (2020)
- [Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory](https://mlsanity.com/paper/2304.12466/) (2023)

## Built on by (most cited first, 2 of 2)

- [Identifying the Best Arm in the Presence of Global Environment Shifts](https://mlsanity.com/paper/2408.12581/) (2024)
- [On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits](https://mlsanity.com/paper/2603.10346/) (2026)

## Abstract (arXiv)

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.