On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits

• URL: http://arxiv.org/abs/2603.10346v1
• Date: Wed, 11 Mar 2026 02:34:29 GMT
• Title: On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits
• Abstract summary: We study the fixed-budget best-arm identification problem in non-stationary linear bandits.<n>A learner aims to identify the arm with the largest cumulative reward $x_* = argmax_x in mathcalX xtopsum_t=1T _t$ with high probability.
• Score: 15.93884263655552
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the fixed-budget best-arm identification (BAI) problem in non-stationary linear bandits. Concretely, given a fixed time budget $T\in \mathbb{N}$, finite arm set $\mathcal{X} \subset \mathbb{R}^d$, and a potentially adversarial sequence of unknown parameters $\lbrace θ_t\rbrace_{t=1}^{T}$ (hence non-stationary), a learner aims to identify the arm with the largest cumulative reward $x_* = \arg\max_{x \in \mathcal{X}} x^\top\sum_{t=1}^T θ_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\left(-Θ\left(T / H_{G}\right)\right)$, where $H_{G}$ scales proportionally with the dimension $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{X}\mathcal{Y}$-optimal design, and develop the $\textsf{Adjacent-BAI}$ algorithm. We prove that the error probability of $\textsf{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.

Related papers

• Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification? [11.223878908981725]
  $1/2$-Tsallis-INF is a canonical best-of-both-worlds FTRL algorithm.<n>It achieves logarithmic pseudo-regret in bandits while retaining minimax-optimal regret in adversarial bandits.<n>This raises a natural question: can the same algorithm, without additional exploration, also identify the best arm reliably?
  arXiv  Detail & Related papers  (2026-08-15T18:38:36Z)
• Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing [52.124267908936396]
  The model is composed of $M$ arms and $K$ plays.<n>Each arm has a number of capacities, and each unit of capacity is associated with a reward function.<n>When multiple plays compete for the arm capacity, the arm capacity is allocated in a larger priority weight first manner.
  arXiv  Detail & Related papers  (2025-12-25T11:19:09Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  We develop a general framework for clustering and distribution matching problems with bandit feedback.<n>We derive a non-asymptotic lower bound on the average number of arm pulls for any online algorithm with an error probability not exceeding $delta$.<n>Our refined analysis uncovers a novel bound on the speed at which the average number of arm pulls of our algorithm converges to the fundamental limit as $delta$ vanishes.
  arXiv  Detail & Related papers  (2024-09-08T12:19:12Z)
• A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity [28.068960555415014]
  We investigate the fixed-budget best-arm identification problem for linear bandits in a potentially non-stationary environment. An algorithm will aim to correctly identify the best arm $x* := argmax_xinmathcalXxtopsum_t=1Ttheta_t$ with probability as high as possible.
  arXiv  Detail & Related papers  (2023-07-27T19:03:36Z)
• Revisiting Simple Regret Minimization in Multi-Armed Bandits [33.88679679593314]
  Simple regret is less popular than the probability of missing the best arm or an $epsilon$-good arm. In this paper, we achieve improved simple regret upper bounds for both data-rich ($Tge n$) and data-poor regime ($T le n$) For the more challenging data-poor regime, we propose Bracketing SH (BSH) that enjoys the same improvement even without sampling each arm at least once.
  arXiv  Detail & Related papers  (2022-10-30T18:31:03Z)
• Best-Arm Identification in Correlated Multi-Armed Bandits [9.180690233707645]
  We propose a novel correlated bandit framework that captures domain knowledge about correlation between arms. We show that the total samples obtained by C-LUCB are of the form $mathcalOleft(sum_k in mathcalC logleft(frac1deltaright)$ as opposed to the typical $mathcalOleft(sum_k in mathcalC logleft(frac1deltaright)$ samples required in the independent reward setting
  arXiv  Detail & Related papers  (2021-09-10T15:41:07Z)
• Bandits with many optimal arms [68.17472536610859]
  We write $p*$ for the proportion of optimal arms and $Delta$ for the minimal mean-gap between optimal and sub-optimal arms. We characterize the optimal learning rates both in the cumulative regret setting, and in the best-arm identification setting.
  arXiv  Detail & Related papers  (2021-03-23T11:02:31Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  We present a reward model that captures set-dependent reward distribution and assumes no total order for arms. We develop a novel regret analysis and show an $Oleft(frack2 n log Tepsilonright)$ gap-dependent regret bound as well as an $Oleft(k2sqrtn T log Tright)$ gap-independent regret bound.
  arXiv  Detail & Related papers  (2021-03-03T23:08:59Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  We study the top-$k$ extreme contextual bandits problem, where the total number of arms can be enormous. We first propose an algorithm for the non-extreme realizable setting, utilizing the Inverse Gap Weighting strategy. We show that our algorithm has a regret guarantee of $O(ksqrt(A-k+1)T log (|mathcalF|T))$.
  arXiv  Detail & Related papers  (2021-02-15T19:10:52Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners [17.224805430291177]
  We study the problem of best arm identification in linearly parameterised multi-armed bandits. We propose an explicitly implementable and provably order-optimal sample-complexity algorithm to solve this problem.
  arXiv  Detail & Related papers  (2020-06-13T05:00:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.