| Title: |
Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits |
| Authors: |
Besson, Lilian; Kaufmann, Emilie; Maillard, Odalric-Ambrym; Seznec, Julien |
| Contributors: |
Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio (PANAMA); Inria Rennes – Bretagne Atlantique; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5); Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA); Université de Rennes 1 (UR1); Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes); Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique); Institut Mines-Télécom Paris (IMT)-Institut Mines-Télécom Paris (IMT)-Université de Rennes 1 (UR1); Institut Mines-Télécom Paris (IMT)-Institut Mines-Télécom Paris (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA); Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique); Institut Mines-Télécom Paris (IMT)-Institut Mines-Télécom Paris (IMT); Scool (Scool); Inria Lille - Nord Europe; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL); Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS); Lelivrescolaire.fr; ANR-16-CE40-0002,BADASS,BANDITS MANCHOTS POUR SIGNAUX NON-STATIONNAIRES ET STRUCTURES(2016); ANR-19-CE23-0026,BOLD,Au delà de l'apprentissage séquentiel pour de meilleures prises de décisions(2019) |
| Source: |
https://hal.inria.fr/hal-02006471 ; 2020. |
| Publisher Information: |
HAL CCSD |
| Publication Year: |
2020 |
| Collection: |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
| Subject Terms: |
Multi-Armed Bandits; Non-Stationary Bandits; Change Point Detection; [STAT.OT]Statistics [stat]/Other Statistics [stat.ML] |
| Description: |
We introduce GLR-klUCB, a novel algorithm for the piecewise iid non-stationary bandit problem with bounded rewards. This algorithm combines an efficient bandit algorithm, kl-UCB, with an efficient, parameter-free, changepoint detector, the Bernoulli Generalized Likelihood Ratio Test, for which we provide new theoretical guarantees of independent interest. Unlike previous non-stationary bandit algorithms using a change-point detector, GLR-klUCB does not need to be calibrated based on prior knowledge on the arms' means. We prove that this algorithm can attain a $O(\sqrt{TA \Upsilon_T\log(T)})$ regret in $T$ rounds on some ``easy'' instances, where A is the number of arms and $\Upsilon_T$ the number of change-points, without prior knowledge of $\Upsilon_T$. In contrast with recently proposed algorithms that are agnostic to $\Upsilon_T$, we perform a numerical study showing that GLR-klUCB is also very efficient in practice, beyond easy instances. |
| Document Type: |
report |
| Language: |
English |
| Relation: |
info:eu-repo/semantics/altIdentifier/arxiv/1902.01575; hal-02006471; https://hal.inria.fr/hal-02006471; https://hal.inria.fr/hal-02006471v2/document; https://hal.inria.fr/hal-02006471v2/file/BKMS20.pdf; ARXIV: 1902.01575 |
| Availability: |
https://hal.inria.fr/hal-02006471; https://hal.inria.fr/hal-02006471v2/document; https://hal.inria.fr/hal-02006471v2/file/BKMS20.pdf |
| Rights: |
http://creativecommons.org/licenses/by-nc-sa/ ; info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.251F6DBE |
| Database: |
BASE |