Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits

Code

• github.com/Y-Hou/BAI-in-PSLB
  Officialnone★ 0

Abstract

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 -Best Arm Identification^+ (PSBAI^+), an algorithm that is guaranteed to identify an -optimal arm with probability 1- and with a minimal number of samples. PSBAI^+ consists of two subroutines, PSBAI and Na\"ive -BAI (NBAI), which are executed in parallel. PSBAI actively detects changepoints and aligns contexts to facilitate the arm identification process. When PSBAI and NBAI are utilized judiciously in parallel, PSBAI^+ is shown to have a finite expected sample complexity. By proving a lower bound, we show the expected sample complexity of PSBAI^+ is optimal up to a logarithmic factor. We compare PSBAI^+ to baseline algorithms using numerical experiments which demonstrate its efficiency. Both our analytical and numerical results corroborate that the efficacy of PSBAI^+ is due to the delicate change detection and context alignment procedures embedded in PSBAI.

Tasks

Reproductions