An Experimental Design Approach for Regret Minimization in Logistic Bandits

Blake Mason, Kwang Sung Jun, Lalit Jain

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this work we consider the problem of regret minimization for logistic bandits. The main challenge of logistic bandits is reducing the dependence on a potentially large problem dependent constant κ that can at worst scale exponentially with the norm of the unknown parameter θ∗. Prior works have applied self-concordance of the logistic function to remove this worst-case dependence providing regret guarantees like O(dlog2(κ)√µT log(∣X ∣)) where d is the dimensionality, T is the time horizon, and µ is the variance of the best-arm. This work improves upon this bound in the fixed arm setting by employing an experimental design procedure that achieves a minimax regret of O(√dµT log(∣X ∣)). Our regret bound in fact takes a tighter instance (i.e., gap) dependent regret bound for the first time in logistic bandits. We also propose a new warmup sampling algorithm that can dramatically reduce the lower order term in the regret in general and prove that it can replace the lower order term dependency on κ to log2(κ) for some instances. Finally, we discuss the impact of the bias of the MLE on the logistic bandit problem, providing an example where d2 lower order regret (cf., it is d for linear bandits) may not be improved as long as the MLE is used and how bias-corrected estimators may be used to make it closer to d.

Original languageEnglish (US)
Title of host publicationAAAI-22 Technical Tracks 7
PublisherAssociation for the Advancement of Artificial Intelligence
Pages7736-7743
Number of pages8
ISBN (Electronic)1577358767, 9781577358763
StatePublished - Jun 30 2022
Event36th AAAI Conference on Artificial Intelligence, AAAI 2022 - Virtual, Online
Duration: Feb 22 2022Mar 1 2022

Publication series

NameProceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022
Volume36

Conference

Conference36th AAAI Conference on Artificial Intelligence, AAAI 2022
CityVirtual, Online
Period2/22/223/1/22

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'An Experimental Design Approach for Regret Minimization in Logistic Bandits'. Together they form a unique fingerprint.

Cite this