Timezone: »
Poster
Pure Exploration and Regret Minimization in Matching Bandits
Flore Sentenac · Jialin Yi · Clément Calauzènes · Vianney Perchet · Milan Vojnovic
Finding an optimal matching in a weighted graph is a standard combinatorial problem. We consider its semi-bandit version where either a pair or a full matching is sampled sequentially. We prove that it is possible to leverage a rank-1 assumption on the adjacency matrix to reduce the sample complexity and the regret of off-the-shelf algorithms up to reaching a linear dependency in the number of vertices (up to to poly-log terms).
Author Information
Flore Sentenac (CREST)
Jialin Yi (London School of Economics)
Clément Calauzènes (Criteo AI Lab)
Vianney Perchet (ENSAE & Criteo AI Lab)
Milan Vojnovic (London School of Economics)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Pure Exploration and Regret Minimization in Matching Bandits »
Thu. Jul 22nd 01:45 -- 01:50 AM Room
More from the Same Authors
-
2023 Poster: Robust Consensus in Ranking Data Analysis: Definitions, Properties and Computational Issues »
Morgane Goibert · Clément Calauzènes · Ekhine IRUROZKI · Stephan Clemencon -
2023 Poster: On Preemption and Learning in Stochastic Scheduling »
Nadav Merlis · Hugo Richard · Flore Sentenac · Corentin Odic · Mathieu Molina · Vianney Perchet -
2023 Poster: Doubly Adversarial Federated Bandits »
Jialin Yi · Milan Vojnovic -
2022 Poster: Rotting Infinitely Many-Armed Bandits »
Jung-hun Kim · Milan Vojnovic · Se-Young Yun -
2022 Spotlight: Rotting Infinitely Many-Armed Bandits »
Jung-hun Kim · Milan Vojnovic · Se-Young Yun -
2021 Poster: Online A-Optimal Design and Active Linear Regression »
Xavier Fontaine · Pierre Perrault · Michal Valko · Vianney Perchet -
2021 Spotlight: Online A-Optimal Design and Active Linear Regression »
Xavier Fontaine · Pierre Perrault · Michal Valko · Vianney Perchet -
2020 Poster: Real-Time Optimisation for Online Learning in Auctions »
Lorenzo Croissant · Marc Abeille · Clément Calauzènes -
2020 Poster: Improved Optimistic Algorithms for Logistic Bandits »
Louis Faury · Marc Abeille · Clément Calauzènes · Olivier Fercoq -
2019 Poster: Exploiting structure of uncertainty for efficient matroid semi-bandits »
Pierre Perrault · Vianney Perchet · Michal Valko -
2019 Poster: Fairness-Aware Learning for Continuous Attributes and Treatments »
Jeremie Mary · Clément Calauzènes · Noureddine El Karoui -
2019 Oral: Exploiting structure of uncertainty for efficient matroid semi-bandits »
Pierre Perrault · Vianney Perchet · Michal Valko -
2019 Oral: Fairness-Aware Learning for Continuous Attributes and Treatments »
Jeremie Mary · Clément Calauzènes · Noureddine El Karoui -
2019 Poster: Learning to bid in revenue-maximizing auctions »
Thomas Nedelec · Noureddine El Karoui · Vianney Perchet -
2019 Oral: Learning to bid in revenue-maximizing auctions »
Thomas Nedelec · Noureddine El Karoui · Vianney Perchet