Non-asymptotic analysis of a sequential rupture detection test and its application to non-stationary bandits - Archive ouverte HAL Access content directly
Conference Papers Year :

Non-asymptotic analysis of a sequential rupture detection test and its application to non-stationary bandits

Analyse non asymptotique d'un test séquentiel de détection de rupture et application aux bandits non stationnaires

(1, 2, 3, 4, 5) , (6, 3, 7)
1
2
3
4
5
6
7

Abstract

We study a strategy for online change-point detection based on generalized likelihood ratios (GLR) and that can be expressed with the binary relative entropy. This test is used to detect a change in the mean of a bounded distribution, and we propose a non-asymptotic control of its false alarm probability and detection delay. We then explain how it can be useful for sequential decision making by proposing the GLR-klUCB bandit strategy, which is efficient in piece-wise stationary multi-armed bandit models.
Nous étudions un test pour la détection séquentielle de rupture, basé sur le rapport de vraisemblance généralisé (GLR) et qui s'exprime en fonction de l'entropie relative binaire. Il s'applique à la détection de rupture sur la moyenne d'une distribution bornée, et nous obtenons un contrôle non-asymptotique de sa probabilité de fausse alarme et de son délai de détection. Nous expliquons son utilisation pour la prise de décision séquentielle en proposant la stratégie de bandit GLR-klUCB, efficace dans des modèles de bandit stationnaires par morceaux.
Fichier principal
Vignette du fichier
GRESTI__2019__Paper__Lilian_Besson__03-19.pdf (339.27 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02152243 , version 1 (11-06-2019)

Licence

Attribution - NonCommercial - ShareAlike - CC BY 4.0

Identifiers

  • HAL Id : hal-02152243 , version 1

Cite

Lilian Besson, Emilie Kaufmann. Analyse non asymptotique d'un test séquentiel de détection de rupture et application aux bandits non stationnaires. GRETSI 2019 - XXVIIème Colloque francophone de traitement du signal et des images, Aug 2019, Lille, France. ⟨hal-02152243⟩
165 View
324 Download

Share

Gmail Facebook Twitter LinkedIn More