An Experimental Design Approach for Regret Minimization in Logistic Bandits

Blake Mason, Kwang-Sung Jun, Lalit Jain

Abstract

Logistic bandits are a fundamental framework for modeling binary rewards in sequential decision-making, yet they are plagued by a problem-dependent constant $\kappa$ that can scale exponentially with the norm of the unknown parameter $\theta_{\ast}$. This work introduces HOMER, an algorithm utilizing H-optimal experimental design to achieve a minimax regret of $O(\sqrt{d \dot\mu T \log(|\mathcal{X}|)})$, where $\dot\mu$ is the variance of the optimal arm. We further propose WAR (Warmup by Accepts and Rejects), a novel sampling strategy that reduces the lower-order regret dependency on $\kappa$ to $\log^2(\kappa)$ for specific instances. Finally, we analyze the impact of Maximum Likelihood Estimator (MLE) bias, explaining why a $d^2$ lower-order term persists in logistic bandits compared to the $d$ term in linear bandits.

Introduction

In online recommendation systems, binary outcomes like clicks are typically modeled using logistic bandits. Unlike linear bandits, the logistic model's curvature—captured by the constant $\kappa$—can lead to exploding variance in parameter estimation when the true parameters are large. Existing approaches often require a massive "warmup" phase of $O(d^2 \kappa)$ samples to stabilize estimates, which is often impractical. This paper addresses these challenges by optimizing the experimental design for reward prediction rather than parameter estimation and by introducing an adaptive warmup procedure.

Methodology

HOMER: H-Optimal Design for Regret

Standard bandit algorithms often rely on G-optimal design to minimize parameter uncertainty. However, for regret minimization, the primary concern is the variance of the predicted mean reward $\mu(x^\top \theta_{\ast})$. The proposed HOMER (H-Optimal MEthod for Regret) algorithm maintains an active set of promising arms and solves an H-optimal design problem in each round. This approach ensures that the variance is minimized specifically in the directions that matter for reward estimation, leading to tighter regret bounds that scale optimally with both dimensionality $d$ and the variance of the best arm.

WAR: Efficient Warmup

The WAR (Warmup by Accepts and Rejects) algorithm replaces the expensive global warmup phase with an adaptive probing mechanism. By using empirical Bernstein inequalities, WAR identifies arms that provide sufficient information to stabilize the MLE without over-sampling arms that contribute to the exponential $\kappa$ penalty. This allows the algorithm to build a reliable estimation basis with significantly fewer samples.

Key Insights: The MLE Bias Bottleneck

A critical contribution of this work is the analysis of the MLE's inherent bias in high-dimensional logistic models. In linear bandits, the lower-order regret term scales with $d$. In logistic bandits, the bias of the MLE can dominate the variance unless $O(d^2)$ samples are collected.

Visualization of the bias/variance trade-off in the MLE, highlighting the specific parameter regimes where estimation becomes difficult.

This "bias bottleneck" suggests that the $d^2$ term is not merely a proof artifact but a fundamental challenge of using the MLE in this setting. The authors suggest that bias-corrected estimators or the Krichevsky-Trofimov (KT) estimator might eventually reduce this dependency.

Empirical Results

Numerical simulations on synthetic datasets validate the theoretical advantages of the proposed methods. The WAR algorithm demonstrates a dramatic reduction in sample complexity compared to naive warmup strategies, especially as the parameter norm $S$ increases.

Table 1: Comparison of warmup sample complexity (mean ± std) for Naive, WAR, and Oracle strategies across different parameter norms S.

As shown in Table 1, for a parameter norm of $S=8$, WAR requires approximately 122,405 samples—a 20x improvement over the 2.6 million samples required by the naive approach. This efficiency allows logistic bandit algorithms to transition to the regret-minimization phase much earlier in the time horizon.

Conclusion

By combining H-optimal experimental design with an adaptive warmup strategy, this work provides the first instance-dependent regret bounds for logistic bandits that effectively manage the $\kappa$ constant. While computational overhead for solving the design problem remains a factor, the significant reduction in sample complexity and the theoretical refinement of the MLE bias provide a clear path forward for high-dimensional logistic bandit applications.

Summary updated

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 $\kappa$ that can at worst scale exponentially with the norm of the unknown parameter $\theta_{\ast}$. Abeille et al. (2021) have applied self-concordance of the logistic function to remove this worst-case dependence providing regret guarantees like $O(d\log^2(\kappa)\sqrt{\dot\mu T}\log(|\mathcal{X}|))$ where $d$ is the dimensionality, $T$ is the time horizon, and $\dot\mu$ 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(\sqrt{d \dot\mu T\log(|\mathcal{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 $\kappa$ to $\log^2(\kappa)$ for some instances. Finally, we discuss the impact of the bias of the MLE on the logistic bandit problem, 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$.
BibTeX
@inproceedings{mason2022experimental,
  author = {Blake Mason and Kwang-Sung Jun and Lalit Jain},
  title = {{An Experimental Design Approach for Regret Minimization in Logistic Bandits}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=FoNDJyx8H9},
}
Figure