arXiv：cs.LG· Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal, Christina Katsimerou, Dirk van der Hoeven·· 4 小时前AI 评分28
Shifting Means 环境下 bandit 最优臂识别：GLRT 停止规则失效，ISM 算法给出样本复杂度上界
Best Arm Identification for Bandits with Shifting Means
AI 导读
针对均值奖励可被对抗性偏移的 Shifting Means 环境，论文提出重要性加权算法 ISM，在固定置信度设定下实现 δ-correct，样本复杂度为 K(σ²+U²)Δ_min⁻² ln(1/δ)。研究同时证明，包括 Track-and-Stop 在内的 GLRT 停止规则算法在时变偏移下会失效，并给出匹配的 worst-case 下界与实验验证。该工作已被 NeurIPS 2026 接收。
正文
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 $\boldsymbol{\Delta}$ 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 ($\mathsf{ISM}$). Assuming means bounded by $U$ and $\sigma^2$-sub-Gaussian rewards, we show $\mathsf{ISM}$ to be $\delta$-correct and to enjoy a sample complexity bound of order $K (\sigma^2 + U^2) \Delta_{\min}^{-2} \ln \frac{1}{\delta}$. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.
| Comments: | Accepted at NeurIPS 2026 |
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.10488 [stat.ML] |
| (or arXiv:2610.10488v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.10488 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Lukas Zierahn [view email]
[v1]
Wed, 7 Oct 2026 17:44:34 UTC (931 KB)
来源：arXiv：cs.LG · arxiv.org