Skip to content
DraconiticResearch
Search Sources API
190,839 studies31 sourcesUpdated 23 min ago
PreprintCC BY 4.0arXiv

Best Arm Identification for Bandits with Shifting Means

  • Lukas Zierahn
  • Wouter M. Koolen
  • Shubhada Agrawal
  • Christina Katsimerou
  • Dirk van der Hoeven
Open at sourcePDFDOICite

Abstract

We study the best arm identification problem in a stochastic environment with a novel form of adversarial perturbations, which we coin Shifting Means. While classically the mean rewards of the K arms are stable in time, in Shifting Means only the gaps Δ between mean rewards are stable, while their common shift may be determined adversarially in each round. The objective of the learner is to identify the best arm with high probability while minimizing sample complexity (the fixed confidence setting). Handling shifts requires new tools: we show that algorithms employing a Generalized Likelihood Ratio Test (GLRT) stopping rule, including the popular Track-and-Stop, fail under time-varying shifts. Instead, we propose Importance Weights for Shifting Means (ISM). Assuming means bounded by U and σ2-sub-Gaussian rewards, we show ISM to be δ-correct and to enjoy a sample complexity bound of order K (σ2 + U2) Δmin−2 ln 1/δ. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.

Related

  1. Cost-Aware Best-LLM Identification using Dueling Feedback
    Sarvesh Gharat, Nikhil Karamchandani, Jayakrishnan Nair
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  2. Tight Sample Complexity Bounds for Entropic Best Policy Identification
    Amer Essakine, Claire Vernade
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  3. Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
    Khang Luong, Dinh Thai Son, Hoang Ta +2
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  4. Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
    Keqin Chen, Jie Bian, Yulian Wu +1
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv
  5. Bayesian Fixed-Confidence Best-Arm Identification with Abstention
    Yuqi Huang, Yunlong Hou, Vincent Y. F. Tan
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{zierahn2026best,
  title = {{Best Arm Identification for Bandits with Shifting Means}},
  author = {Lukas Zierahn and Wouter M. Koolen and Shubhada Agrawal and Christina Katsimerou and Dirk van der Hoeven},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.10488},
  eprint = {2610.10488},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.10488},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Best Arm Identification for Bandits with Shifting Means
AU  - Lukas Zierahn
AU  - Wouter M. Koolen
AU  - Shubhada Agrawal
AU  - Christina Katsimerou
AU  - Dirk van der Hoeven
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.10488
UR  - https://arxiv.org/abs/2610.10488
AB  - We study the best arm identification problem in a stochastic environment with a novel form of adversarial perturbations, which we coin Shifting Means. While classically the mean rewards of the K arms are stable in time, in Shifting Means only the gaps Δ between mean rewards are stable, while their common shift may be determined adversarially in each round. The objective of the learner is to identify the best arm with high probability while minimizing sample complexity (the fixed confidence setting). Handling shifts requires new tools: we show that algorithms employing a Generalized Likelihood Ratio Test (GLRT) stopping rule, including the popular Track-and-Stop, fail under time-varying shifts. Instead, we propose Importance Weights for Shifting Means (ISM). Assuming means bounded by U and σ^2-sub-Gaussian rewards, we show ISM to be δ-correct and to enjoy a sample complexity bound of order K (σ^2 + U^2) Δ_min^−2 ln 1/δ. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.
ER  -