Non-asymptotic analysis of a sequential breakpoint detection test and application to non-stationary bandits.

Summary We study a test for sequential break detection based on the generalized likelihood ratio (GLR) and expressed as a function of the binary relative entropy. It is applied to the detection of breaks on the mean of a bounded distribution, and we obtain a non-asymptotic control of its false alarm probability and its detection delay. We explain its use for sequential decision making by proposing the GLR-klUCB bandit strategy, which is efficient in piecewise stationary bandit models.