# Identifying the Best Arm in the Presence of Global Environment Shifts

arXiv: https://arxiv.org/abs/2408.12581 · HTML: https://mlsanity.com/paper/2408.12581/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 39 references that are in the map.
- First posted on arXiv 22 Aug 2024.

## Builds on (most cited first, 13 of 13)

- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Review on Ranking and Selection: A New Perspective](https://mlsanity.com/paper/2008.00249/) (2020)
- [Best Arm Identification for Contaminated Bandits](https://mlsanity.com/paper/1802.09514/) (2018)
- [Simulation optimization: A review of algorithms and applications](https://mlsanity.com/paper/1706.08591/) (2017)
- [Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2106.04763/) (2021)
- [Ranking and Selection with Covariates for Personalized Decision Making](https://mlsanity.com/paper/1710.02642/) (2017)
- [Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions](https://mlsanity.com/paper/2010.07904/) (2020)
- [Best of Three Worlds: Adaptive Experimentation for Digital Marketing in Practice](https://mlsanity.com/paper/2402.10870/) (2024)
- [A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity](https://mlsanity.com/paper/2307.15154/) (2023)
- [Regret Bounds and Reinforcement Learning Exploration of EXP-based Algorithms](https://mlsanity.com/paper/2009.09538/) (2020)

## Built on by (most cited first, 1 of 1)

- [Best Arm Identification for Bandits with Shifting Means](https://mlsanity.com/paper/2610.10488/) (2026)

## Abstract (arXiv)

This paper formulates a new Best-Arm Identification problem in the non-stationary stochastic bandits setting, where the means of all arms are shifted in the same way due to a global influence of the environment. The aim is to identify the unique best arm across environmental change given a fixed total budget. While this setting can be regarded as a special case of Adversarial Bandits or Corrupted Bandits, we demonstrate that existing solutions tailored to those settings do not fully utilise the nature of this global influence, and thus, do not work well in practice (despite their theoretical guarantees). To overcome this issue, in this paper we develop a novel selection policy that is consistent and robust in dealing with global environmental shifts. We then propose an allocation policy, LinLUCB, which exploits information about global shifts across all arms in each environment. Empirical tests depict a significant improvement in our policies against other existing methods.