Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits

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.