On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits
Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson, Maryam Fazel · 2026
Read On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits by Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson, Maryam Fazel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-10346.txt.
Introduction
Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson, and Maryam Fazel study best-arm identification in non-stationary linear bandits under a fixed time budget. The best arm has the largest total reward, while unknown parameters can shift in an adversarial way. Standard G-optimal sampling gives a minimax rate, yet they call that view too pessimistic, since it hides gains from richer arm-set geometry. They prove an arm-set-dependent lower bound and propose an adjacent-optimal design whose error matches it, pinning down the true complexity here.
Catalog record
| CREATOR | Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson, Maryam Fazel |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 82807 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.10346
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson, Maryam Fazel Abstract We study the fixed-budget best-arm identification (BAI) problem in non-stationary linear bandits. Concretely, given a fixed time budget T ∈ ℕ T\in\mathbb{N} , finite arm set 𝒳 ⊂ ℝ d \mathcal{X}\subset\mathbb{R}^{d} , and a potentially adversarial sequence of unknown parameters { θ t } t = 1 T \{\theta_{t}\}_{t=1}^{T} (hence non-stationary), a learner aims to identify the arm with the largest cumulative reward x ∗ = arg max x ∈ 𝒳 x ⊤ ∑ t = 1 T θ t x_{*}=\arg\max_{x\in\mathcal{X}}x^{\top}\sum_{t=1}^{T}\theta_{t} with high probability. In this setting, it is well-known that uniformly sampling arms from the G-optimal design yields a minimax-optimal error probability of exp ( − Θ ( T / H G ) ) \exp\left(-\Theta\left(T/H_{G}\right)\right) , where H G H_{G} scales proportionally with the dimension d d . However, this notion of complexity is overly pessimistic, as it is derived from a lower bound in which the arm set consists only of the standard basis vectors, thus masking any potential advantages arising from arm sets with richer geometric structure. To address this, we establish an arm-set-dependent lower bound that, in contrast, holds for any arm set. Motivated by the ideas underlying our lower bound, we propose the Adjacent-optimal design , a specialization of the well-known 𝒳 𝒴 \mathcal{XY} -optimal design, and develop the Adjacent-BAI algorithm. We prove that the error probability of Adjacent-BAI matches our lower bound up to constants, verifying the tightness of our lower bound, and establishing the arm-set-dependent complexity of this setting. 1 Introduction We focus on quantifying the difficulty of fixed-budget best-arm identification (BAI) problem in non-stationary linear bandits. The linear bandit framework generalizes the classical multi-armed bandit problem by associating each arm with a feature vector and modeling rewards as linear in an unknown parameter. Algorithms such as UCB and Thompson Sampling are known to perform optimally in the well-studied regret-minimization setting ( Lattimore and Szepesvári 2020 ) . However, in the best-arm identification setting, where exploration is more important than cumulative reward, these algorithms are suboptimal ( Bubeck et al. 2009 ) , thus requiring specialized attention. In the standard BAI setting, a stationary environment is assumed where the rewards of arms are sampled i.i.d ( Audibert and Bubeck 2010 ; Soare et al. 2014 ; Fiez et al. 2019 ) . However, algorithms designed for these environments can completely fail as soon as this assumption is lifted, for example, in settings where the value of an arm can change at any time step ( Abbasi-Yadkori et al. 2018 ; Xiong et al. 2024 ) . An interesting question is exactly how the difficulty of this setting changes once this stationary assumption is lifted . In recent work, Xiong et al. 2024 partially answered this question by showing that when the arm set is restricted to the standard basis, the difficulty of non-stationary BAI scales proportionally with the dimension. While informative, this result is ultimately unsatisfying as it collapses the linear bandit model back into a multi-armed bandit. Basis arm sets erase correlations between arms, precisely the geometric structure that linear bandits are meant to exploit. With this in mind, we aim to uncover precisely which relationship between arms truly governs the difficulty of non-stationary BAI. Inspired by Soare et al. 2014 , a natural conjecture is that the pairwise relationships between every arm should be considered when measuring difficulty. However, such a characterization implies that any arm set containing a basis is no easier than the basis itself, and thus no progress is made. To refine this view, we introduce adjacency, a geometric notion that captures which pairs of arms can compete for optimality. Accordingly, we find that the pairwise relationships between adjacent arms are necessary and sufficient to measure the difficulty of non-stationary BAI. Formally, by leveraging the adjacent structure of the arm set, we refine the previous notion of difficulty in non-stationary BAI by establishing a measure of complexity that adapts to the geometry of any arm set, which we term as arm-set-dependent . Our contributions. • Adjacency and Non-Stationary BAI. The main novelty of our paper stems from our characterization of non-stationary BAI as a problem of differentiating only between adjacent arms, a notion we formalize in later sections. The intuition for this restriction stems from our central Lemma 1 , which implies that if an arm is better than its adjacent arms, then it is the optimal arm. Accordingly, we introduce a new arm-set-dependent complexity measure H_{\mathrm{Adjacent}}(\mathcal{X}) and show it strictly refines the minimax-optimal complexity H_{G} . • Arm-set-dependent lower bound. We show in Theorem 1 that for fixed arm set \mathcal{X} , the error probability of any algorithm must be at least \exp\left(-O\left(T/H_{\mathrm{Adjacent}}(\mathcal{X})\right)\right) . Our lower bound builds off of previous works ( Kaufmann et al. 2016 ; Abbasi-Yadkori et al. 2018 ) concerning lower bounds in best-arm identification for the multi-armed bandit setting. However, these methods alone are not sufficient for the linear setting, which we address by characterizing the lower bound as an optimization problem in Lemma 3 , and which we solve in Lemma 4 by exploiting the adjacent geometry of the arm set. • Matching upper bound. We introduce the Adjacent-optimal design, a specialization of the well-known \mathcal{X}\mathcal{Y} -optimal design ( Soare et al. 2014 ) , that instead reduces variance only between adjacent arms. Using the Adjacent-optimal design, we introduce the algorithm Adjacent-BAI . Utilizing Lemma 1 , we obtain Theorem 2 showing that for fixed arm set \mathcal{X} , the error probability of Adjacent-BAI is at most \exp\left(-\Omega\left(T/H_{\mathrm{Adjacent}}(\mathcal{X})\right)\right) , verifying the tightness of our lower bound, and establishing H_{\mathrm{Adjacent}}(\mathcal{X}) as the arm-set-dependent complexity measure of this setting. 2 Related Work Best-arm identification (BAI) seeks to identify the optimal arm while ignoring cumulative reward or regret. Even-Dar et al. 2002 marked the first substantial result in this area and the problem is now studied under two canonical settings: (i) the fixed-confidence setting, where the learner attains a prescribed error probability target using as few pulls as possible, and (ii) the fixed-budget setting, where the learner minimizes the error probability under a prescribed sampling budget; the latter was introduced by Bubeck et al. 2009 . Best-arm identification with fixed confidence. For multi-armed bandits, Even-Dar et al. 2002 established the first sample-complexity upper bound, with a nearly matching lower bound later given by Mannor and Tsitsiklis 2004 . These bounds were subsequently tightened by Karnin et al. 2013 and Kaufmann et al. 2016 . Notably, Kaufmann et al. 2016 derived a general information-theoretic lower bound that underpins many linear-bandit lower bounds ( Fiez et al. 2019 ; Jedra and Proutiere 2020 ; Camilleri et al. 2021b ) . In linear bandits, Soare et al. 2014 proposed the seminal \mathcal{XY} -allocation strategy, which has been refined and generalized in follow-up work ( Tao et al. 2018 ; Xu et al. 2018 ; Degenne et al. 2020 ; Fiez et al. 2019 ; Jedra and Proutiere 2020 ; Katz-Samuels et al. 2020 ) . Nearly matching lower bounds were also established by Fiez et al. 2019 and Jedra and Proutiere 2020