Timezone: »
Poster
Improved Optimistic Algorithms for Logistic Bandits
Louis Faury · Marc Abeille · Clément Calauzènes · Olivier Fercoq
Thu Jul 16 09:00 AM -- 09:45 AM & Thu Jul 16 11:00 PM -- 11:45 PM (PDT) @
The generalized linear bandit framework has attracted a lot of attention in recent years by extending the well-understood linear setting and allowing to model richer reward structures. It notably covers the logistic model, widely used when rewards are binary. For logistic bandits, the frequentist regret guarantees of existing algorithms are $\tilde{\mathcal{O}}(\kappa \sqrt{T})$, where $\kappa$ is a problem-dependent constant. Unfortunately, $\kappa$ can be arbitrarily large as it scales exponentially with the size of the decision set. This may lead to significantly loose regret bounds and poor empirical performance. In this work, we study the logistic bandit with a focus on the prohibitive dependencies introduced by $\kappa$. We propose a new optimistic algorithm based on a finer examination of the non-linearities of the reward function. We show that it enjoys a $\tilde{\mathcal{O}}(\sqrt{T})$ regret with no dependency in $\kappa$, but for a second order term. Our analysis is based on a new tail-inequality for self-normalized martingales, of independent interest.
Author Information
Louis Faury (Criteo AI Lab)
Marc Abeille (Criteo AI Lab)
Clément Calauzènes (Criteo AI Lab)
Olivier Fercoq (Telecom Paris)
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 -
2021 Poster: Pure Exploration and Regret Minimization in Matching Bandits »
Flore Sentenac · Jialin Yi · Clément Calauzènes · Vianney Perchet · Milan Vojnovic -
2021 Spotlight: Pure Exploration and Regret Minimization in Matching Bandits »
Flore Sentenac · Jialin Yi · Clément Calauzènes · Vianney Perchet · Milan Vojnovic -
2020 Poster: Real-Time Optimisation for Online Learning in Auctions »
Lorenzo Croissant · Marc Abeille · Clément Calauzènes -
2020 Poster: Random extrapolation for primal-dual coordinate descent »
Ahmet Alacaoglu · Olivier Fercoq · Volkan Cevher -
2020 Poster: Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation »
Marc Abeille · Alessandro Lazaric -
2019 Poster: Fairness-Aware Learning for Continuous Attributes and Treatments »
Jeremie Mary · Clément Calauzènes · Noureddine El Karoui -
2019 Oral: Fairness-Aware Learning for Continuous Attributes and Treatments »
Jeremie Mary · Clément Calauzènes · Noureddine El Karoui -
2018 Poster: Improved Regret Bounds for Thompson Sampling in Linear Quadratic Control Problems »
Marc Abeille · Alessandro Lazaric -
2018 Oral: Improved Regret Bounds for Thompson Sampling in Linear Quadratic Control Problems »
Marc Abeille · Alessandro Lazaric