# Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 33 references that are in the map.
- First posted on arXiv 10 Oct 2024.

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

- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [The Role of Contextual Information in Best Arm Identification](https://mlsanity.com/paper/2106.14077/) (2021)
- [Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds](https://mlsanity.com/paper/2302.02988/) (2023)
- [An varepsilon-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond](https://mlsanity.com/paper/2305.16041/) (2023)

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

- [BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms](https://mlsanity.com/paper/2505.15141/) (2025)
- [DAK-UCB: Diversity-Aware Prompt Routing for LLMs and Generative Models](https://mlsanity.com/paper/2603.23140/) (2026)
- [Competing Bandits in Decentralized Contextual Matching Markets](https://mlsanity.com/paper/2411.11794/) (2024)
- [Fixed-Confidence Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2507.08994/) (2025)
- [Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity](https://mlsanity.com/paper/2605.20269/) (2026)
- [The Cost of Learning Under Multiple Change Points](https://mlsanity.com/paper/2602.11406/) (2026)

## Abstract (arXiv)

We propose a em novel piecewise stationary linear bandit (PSLB) model, where the environment randomly samples a context from an unknown probability distribution at each changepoint, and the quality of an arm is measured by its return averaged over all contexts. The contexts and their distribution, as well as the changepoints are unknown to the agent. We design em Piecewise-Stationary varepsilon-Best Arm Identification^+ (PSvarepsilonBAI^+), an algorithm that is guaranteed to identify an varepsilon-optimal arm with probability ≥ 1-δ and with a minimal number of samples. PSvarepsilonBAI^+ consists of two subroutines, PSvarepsilonBAI and sc Na"ive varepsilon-BAI (NvarepsilonBAI), which are executed in parallel. PSvarepsilonBAI actively detects changepoints and aligns contexts to facilitate the arm identification process. When PSvarepsilonBAI and NvarepsilonBAI are utilized judiciously in parallel, PSvarepsilonBAI^+ is shown to have a finite expected sample complexity. By proving a lower bound, we show the expected sample complexity of PSvarepsilonBAI^+ is optimal up to a logarithmic factor. We compare PSvarepsilonBAI^+ to baseline algorithms using numerical experiments which demonstrate its efficiency. Both our analytical and numerical results corroborate that the efficacy of PSvarepsilonBAI^+ is due to the delicate change detection and context alignment procedures embedded in PSvarepsilonBAI.