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 vector. Previous works have applied self-concordance of the logistic function to remove this worst-case dependence providing regret guarantees that move the reduce the dependence on this worst case parameter to lower order terms with only polylogarithmic dependence on the main term and as well as linear dependence on the dimension of the unknown parameter. This work improves upon the prior art by 1) removing all scaling of the worst case term on the main term and 2) reducing the dependence on the dependence to scale with the square root of dimension in the fixed arm setting by employing an experimental design procedure. 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 exponentially reduce the lower order term's dependency on the worst case parameter in some instances. Finally, we discuss the impact of the bias of the MLE on the logistic bandit problem in d dimensions, providing an example where d^2 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.
Introduction
Logistic bandits are a fundamental framework for sequential decision-making with binary rewards, such as click-through rate prediction in online advertising. Unlike standard linear bandits where rewards are continuous, logistic bandits model the probability of a binary outcome using the logistic function $\mu(x^\top \theta) = (1 + \exp(-x^\top \theta))^{-1}$.
The primary mathematical hurdle in this setting is the "flatness" of the logistic curve. When the norm of the true parameter $\theta_*$ is large, the derivative of the logistic function, $\dot{\mu}$, can become exponentially small. The inverse of this minimum derivative, $\kappa = 1 / \min_x \dot{\mu}(x^\top \theta_*)$, often appears in regret bounds, leading to potentially exponential costs. Existing algorithms like OFULog and SupLogistic attempt to mitigate this, but often at the cost of suboptimal leading terms or excessive "warmup" phases—initial exploratory sampling that scales with $O(d^2 \kappa)$.
Methods: HOMER and WAR
This paper introduces an experimental design approach to overcome these limitations, centered on two novel algorithms:
HOMER (H-Optimal MEthod for Regret)
In linear bandits, G-optimal design (minimizing maximum variance) is standard. However, in logistic bandits, the confidence width depends on the local derivative of the logistic function. HOMER utilizes a novel H-optimal design that specifically minimizes the worst-case confidence width on the mean reward of the arms. By operating in phases—computing mixtures of H-optimal and G-optimal designs, rounding allocations, and eliminating suboptimal arms—HOMER achieves state-of-the-art regret bounds.
WAR (Warmup by Accepts and Rejects)
To address the prohibitive $O(d^2 \kappa)$ warmup cost, the authors propose WAR. This adaptive strategy employs an "optimistic probing" phase to identify arms with high variance (where the logistic curve is "steep").
By focusing on these high-information arms, WAR builds a safe basis for estimation, certifying necessary warmup conditions with significantly fewer samples than naive uniform exploration.
Key Results
The theoretical contributions are complemented by numerical simulations demonstrating the efficiency of the WAR procedure.
State-of-the-Art Regret
HOMER achieves a minimax regret bound of $\tilde{O}(\sqrt{d \dot{\mu}(x_*^\top \theta_*) T} + d^2 \kappa)$. This is the first bound to achieve optimal dependence on dimension $d$ and the best arm's variance $\dot{\mu}$ without a $\log(\kappa)$ penalty in the leading term. Furthermore, it provides the first instance-dependent bound for logistic bandits: $O(\frac{d \dot{\mu}(x_*^\top \theta_*) \log(|X|T)}{\Delta} + d^2 \kappa)$.
Empirical Warmup Efficiency
Numerical evaluations on synthetic data (20 arms in 3D, varying parameter norm $S$) highlight the practical impact of WAR. As shown in the table below, the sample savings are substantial.
For a parameter norm of $S=8$, WAR reduces the required warmup samples from approximately 2.6 million (Naive) to just 122,000—a 20x improvement that approaches the theoretical oracle baseline.
Discussion and Future Work
A significant insight of this work is the "MLE Bias Bottleneck." The authors argue that the $O(d^2)$ warmup requirement is fundamentally tied to the bias of the Maximum Likelihood Estimate in Generalized Linear Models. To ensure confidence intervals remain valid (i.e., bias is smaller than variance), oversampling by a factor of $d$ is required.
Future research directions include extending formal proofs for multi-dimensional WAR and exploring bias-corrected estimators (like the Krichevsky-Trofimov estimator) to potentially break the $d^2$ barrier and reach $O(d^{4/3})$ lower-order regret.
Summary updated