Exploiting structure of uncertainty for efficient matroid semi-bandits - École polytechnique Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Exploiting structure of uncertainty for efficient matroid semi-bandits

Michal Valko

Résumé

We improve the efficiency of algorithms for stochastic combinatorial semi-bandits. In most interesting problems, state-of-the-art algorithms take advantage of structural properties of rewards, such as independence. However, while being optimal in terms of asymptotic regret, these algorithms are inefficient. In our paper, we first reduce their implementation to a specific submod-ular maximization. Then, in case of matroid constraints , we design adapted approximation routines , thereby providing the first efficient algorithms that rely on reward structure to improve regret bound. In particular, we improve the state-of-the-art efficient gap-free regret bound by a factor √ m/ log m, where m is the maximum action size. Finally, we show how our improvement translates to more general budgeted combinato-rial semi-bandits.
Fichier principal
Vignette du fichier
supplementary.pdf (882.58 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02387478 , version 1 (29-11-2019)

Identifiants

  • HAL Id : hal-02387478 , version 1

Citer

Pierre Perrault, Vianney Perchet, Michal Valko. Exploiting structure of uncertainty for efficient matroid semi-bandits. International Conference on Machine Learning, 2019, Long Beach, United States. ⟨hal-02387478⟩
135 Consultations
115 Téléchargements

Partager

Gmail Facebook X LinkedIn More