Papers › Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits
Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits
Yunlong Hou, Vincent Y. F. Tan, Zixin Zhong
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 ε-Best Arm Identification^+} (PSεBAI^+), an algorithm that is guaranteed to identify an ε-optimal arm with probability ≥1-δ and with a minimal number of samples. PSεBAI^+ consists of two subroutines, PSεBAI and {\sc Na\"ive ε-BAI} (NεBAI), which are executed in parallel. PSεBAI actively detects changepoints and aligns contexts to facilitate the arm identification process. When PSεBAI and NεBAI are utilized judiciously in parallel, PSεBAI^+ is shown to have a finite expected sample complexity. By proving a lower bound, we show the expected sample complexity of PSεBAI^+ is optimal up to a logarithmic factor. We compare PSεBAI^+ to baseline algorithms using numerical experiments which demonstrate its efficiency. Both our analytical and numerical results corroborate that the efficacy of PSεBAI^+ is due to the delicate change detection and context alignment procedures embedded in PSεBAI.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections