@inproceedings{
hou2024almost,
title={Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits},
author={Yunlong Hou and Vincent Y. F. Tan and Zixin Zhong},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=Q5e3ftQ3q3}
}
We propose a 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 Piecewise-Stationary $\varepsilon$-Best Arm Identification$^+$ (PS$\varepsilon$BAI$^+$), an algorithm that is guaranteed to identify an $\varepsilon$-optimal arm with probability $\ge 1-\delta$ and with a minimal number of samples.
PS$\varepsilon$BAI$^+$ consists of two subroutines, PS$\varepsilon$BAI and Naïve $\varepsilon$-BAI (N$\varepsilon$BAI), which are executed in parallel. PS$\varepsilon$BAI actively detects changepoints and aligns contexts to facilitate the arm identification process.
When  PS$\varepsilon$BAI and N$\varepsilon$BAI are utilized judiciously in parallel,  PS$\varepsilon$BAI$^+$ is shown to have a finite expected sample complexity. 
By proving a  lower bound, we show the expected sample complexity of PS$\varepsilon$BAI$^+$ is optimal up to a logarithmic factor.
We compare PS$\varepsilon$BAI$^+$ to baseline algorithms using numerical experiments which demonstrate its   efficiency.
Both our analytical and numerical results corroborate that the efficacy   of PS$\varepsilon$BAI$^+$ is due to   the delicate change detection and context alignment procedures embedded in PS$\varepsilon$BAI.
Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits
Yunlong Hou Vincent Y. F. Tan Zixin Zhong