Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit
Multi-armed bandit (MAB) is a class of online learning problems where a learning agent aims to maximize its expected cumulative reward while repeatedly selecting to pull arms with unknown reward distributions. We consider a scenario where the reward distributions may change in a piecewise-stationary fashion at unknown time steps. We show that by incorporating a simple change-detection component with classic UCB algorithms to detect and adapt to changes, our so-called M-UCB algorithm can achieve nearly optimal regret bound on the order of $O(\sqrt{MKT\log T})$, where $T$ is the number of time steps, $K$ is the number of arms, and $M$ is the number of stationary segments. Comparison with the best available lower bound shows that our M-UCB is nearly optimal in $T$ up to a logarithmic factor. We also compare M-UCB with the state-of-the-art algorithms in numerical experiments using a public Yahoo! dataset to demonstrate its superior performance.
Code (0)
등록된 구현이 없습니다.
Tasks
Change DetectionSimilar Papers 제목 키워드 기반
Nearly second-order asymptotic optimality of sequential change-point detection with one-sample updates
Sequential change-point detection when the distribution parameters are unknown is a fundamental problem in statistics and machine learning. When the post-change parameters are unknown, we consider a set of detection proc…
Change Point DetectionMulti-Sensor Slope Change Detection
We develop a mixture procedure for multi-sensor systems to monitor data streams for a change-point that causes a gradual degradation to a subset of the streams. Observations are assumed to be initially normal random vari…
Change DetectionOptimal Sequential Detection of Signals with Unknown Appearance and Disappearance Points in Time
The paper addresses a sequential changepoint detection problem, assuming that the duration of change may be finite and unknown. This problem is of importance for many applications, e.g., for signal and image processing w…
Change DetectionOptimal Sub-sampling to Boost Power of Kernel Sequential Change-point Detection
We present a novel scheme to boost detection power for kernel maximum mean discrepancy based sequential change-point detection procedures. Our proposed scheme features an optimal sub-sampling of the history data before t…
Change Point DetectionA sub-sampling algorithm preventing outliers
Nowadays, in many different fields, massive data are available and for several reasons, it might be convenient to analyze just a subset of the data. The application of the D-optimality criterion can be helpful to optimal…