Best Arm Identification for Bandits with Shifting Means
ISM identifies the best arm when shared mean shifts are adversarial but gaps stay fixed.
The paper studies fixed-confidence best-arm identification when gaps between arm means are stable but a common shift may change adversarially each round. It shows that GLRT stopping rules, including Track-and-Stop, fail under these shifts. Importance Weights for Shifting Means (ISM) is delta-correct for bounded, sub-Gaussian rewards, with sample complexity on the order of K(sigma squared plus U squared) over Delta-min squared times ln(1/delta). A matching worst-case lower bound and empirical results are also given.
- Only reward gaps stay fixed; a shared mean shift can be adversarial.
- GLRT stopping rules, including Track-and-Stop, fail under time-varying shifts.
- ISM is delta-correct with a near-matching sample-complexity bound.
From the original article
1 min read at arxiv.orgWe 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Δ$ between mean rewards are stable, while their common shift may be determined adversarially in each round.
By Lukas Zierahn · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.