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

27 Jul 2023arXiv:2307.15154archive 2025-07-28

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^* := max_(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 𝖯1-𝖱𝖠𝖦𝖤 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 𝖯1-𝖱𝖠𝖦𝖤 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.

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