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.
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.
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