On Limited-Memory Subsampling Strategies for Bandits

Baudry, Dorian; Russac, Yoan; Cappé, Olivier

Type de document :

Communication dans un congrès avec actes

Titre :

On Limited-Memory Subsampling Strategies for Bandits

Auteur(s) :

Baudry, Dorian [Auteur]
Scool [Scool]
Centre National de la Recherche Scientifique [CNRS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Russac, Yoan [Auteur]
Value from Data [VALDA]
Centre National de la Recherche Scientifique [CNRS]
Département d'informatique - ENS-PSL [DI-ENS]
Cappé, Olivier [Auteur]
Value from Data [VALDA]
Centre National de la Recherche Scientifique [CNRS]
Département d'informatique - ENS-PSL [DI-ENS]

Titre de la manifestation scientifique :

ICML 2021- International Conference on Machine Learning

Ville :

Vienna / Virtual

Pays :

Autriche

Date de début de la manifestation scientifique :

2021-07-18

Discipline(s) HAL :

Informatique [cs]/Intelligence artificielle [cs.AI]

Résumé en anglais : [en]

There has been a recent surge of interest in nonparametric bandit algorithms based on subsampling. One drawback however of these approaches is the additional complexity required by random subsampling and the storage of the ...
Lire la suite >There has been a recent surge of interest in nonparametric bandit algorithms based on subsampling. One drawback however of these approaches is the additional complexity required by random subsampling and the storage of the full history of rewards. Our first contribution is to show that a simple deterministic subsampling rule, proposed in the recent work of Baudry et al. (2020) under the name of "last-block subsampling", is asymptotically optimal in one-parameter exponential families. In addition, we prove that these guarantees also hold when limiting the algorithm memory to a polylogarithmic function of the time horizon. These findings open up new perspectives, in particular for non-stationary scenarios in which the arm distributions evolve over time. We propose a variant of the algorithm in which only the most recent observations are used for subsampling, achieving optimal regret guarantees under the assumption of a known number of abrupt changes. Extensive numerical simulations highlight the merits of this approach, particularly when the changes are not only affecting the means of the rewards.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal.archives-ouvertes.fr/hal-03265442/document
Accès libre
Accéder au document

http://arxiv.org/pdf/2106.10935
Accès libre
Accéder au document

https://hal.archives-ouvertes.fr/hal-03265442/document
Accès libre
Accéder au document

https://hal.archives-ouvertes.fr/hal-03265442/file/main.pdf
Accès libre
Accéder au document

https://hal.archives-ouvertes.fr/hal-03265442/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

main.pdf
Accès libre
Accéder au document

2106.10935
Accès libre
Accéder au document

document
Accès libre
Accéder au document

main.pdf
Accès libre
Accéder au document

On Limited-Memory Subsampling Strategies ... BibTeX CSV Excel RIS

Fichiers

On Limited-Memory Subsampling Strategies ...

BibTeX

CSV

Excel

RIS