Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion

Junghyun Lee, Se-Young Yun, Kwang-Sung Jun

TL;DR

This paper introduces Regret-to-Confidence-Set Conversion (R2CS), a novel framework that constructs tighter, convex confidence sets for logistic and multinomial logistic (MNL) bandits. By leveraging the theoretical guarantees of optimal online learning algorithms without actually running them, the authors achieve state-of-the-art regret bounds that significantly improve dependency on the parameter norm $S$ while maintaining computational tractability.

What Problem Does This Paper Address?

In sequential decision-making, logistic bandits are widely used to model binary user choices, such as whether a user will click an ad or not. At each step, an algorithm selects an action (or "arm") based on estimated user preferences ($\theta_\star$). To balance exploration and exploitation, algorithms typically construct a "confidence set" around their current estimate to remain optimistic about uncertain options.

However, prior state-of-the-art approaches suffered from a major flaw: their performance guarantees (regret bounds) scaled poorly with $S$, where $S \geq \lVert\theta_\star\rVert_2$ represents the maximum possible magnitude of the true parameter vector. When $S$ is large, existing confidence sets become excessively loose, leading to sub-optimal decisions. Furthermore, designing a confidence set that is both tight (for low regret) and convex (so finding the best arm is computationally feasible) has proven incredibly difficult for logistic models.

Methods

The authors propose a generic approach called Regret-to-Confidence-Set Conversion (R2CS).

The core mathematical "magic trick" of R2CS is that it builds a loss-based confidence set by utilizing the existence of a minimax-optimal online learning algorithm (specifically, the improper learning algorithm by Foster et al., 2018b), without ever actually running the computationally expensive online algorithm itself.

The method works by decomposing the logistic loss difference into three parts:

  1. An online learning regret term (bounded logarithmically with respect to $S$).
  2. A martingale difference sequence term (bounded using a newly derived anytime variant of Freedman’s inequality).
  3. A Kullback-Leibler (KL) divergence term (controlled via information-geometric properties and self-concordant analysis).

This framework is used to design OFULog+ for standard logistic bandits and MNL-UCB+ for multinomial logistic bandits.

Datasets

The paper evaluates the proposed OFULog+ algorithm using synthetic simulations, closely following the experimental setup of Faury et al. (2022).

  • Environment: Time-varying arm sets are generated by sampling 20 random vectors within a $d$-dimensional unit ball ($d=2$) at each time step $t$, up to $T=4000$.
  • Parameters: Evaluated under different parameter magnitudes $S \in \{5, 10\}$.
  • No real-world datasets were used in this study.

Key Insights and Ideas

  • The Existential Shortcut: Traditionally, online-to-confidence-set conversions require executing the underlying online algorithm. R2CS breaks this requirement. It uses the mathematical guarantee of an intractable online algorithm purely as an analytical tool to draw a tight boundary around the MLE estimate.
  • Separation of Dimensions and Norms: R2CS shrinks the confidence set radius from the prior art's $O(\sqrt{dS^3 \log t})$ down to $O(\sqrt{(d + S) \log t})$. This decouples the dimension $d$ from the norm bound $S$, preventing the confidence set from exploding when $S$ is large.
  • Robustness to Approximation: Because the confidence set is defined directly via the loss function rather than being geometrically centered around a biased estimator, even an approximate maximum likelihood estimate (MLE) preserves the high-probability validity of the confidence set.

Key Results

The theoretical improvements are summarized in the paper's main look-up table:

Comparison of regret upper bounds for contextual logistic and MNL bandits.

Theoretical Improvements:

  • Logistic Bandits: OFULog+ improves the leading regret term by a factor of $\sqrt{S}$ and the lower-order term by a factor of $S$ compared to previous best bounds, all while remaining computationally tractable ($\checkmark$).
  • MNL Bandits: MNL-UCB+ reduces the leading regret term dependency by $\sqrt{S}$ and $\sqrt{K}$ (where $K$ is the number of choices), achieving tractability where previous tight variants failed ($\times$).

Empirical Performance:

In synthetic experiments, OFULog+ consistently outperformed previous state-of-the-art algorithms (ada-OFU-ECOLog and OFULog-r) by a wide margin, demonstrating that tighter theoretical confidence sets translate directly into superior real-world data efficiency.

Limitations and Future Work

While OFULog+ and the baseline MNL-UCB+ are computationally tractable, the authors note that their Improved MNL-UCB+ variant—which achieves the absolute tightest regret bound for multinomial models—is currently computationally intractable. This intractability stems from the need to calculate minimal elements under the Loewner ordering of matrices. Finding an algorithm for MNL bandits that is simultaneously minimax-optimal and computationally efficient remains an open challenge.

Additionally, the authors highlight exciting avenues for extending R2CS to Thompson Sampling, generalized linear bandits, and reinforcement learning from human feedback (RLHF) via the Bradley-Terry preference model.

Summary updated

Abstract

Logistic bandit is a ubiquitous framework of modeling users' choices, e.g., click vs. no click for advertisement recommender system. We observe that the prior works overlook or neglect dependencies in $S \geq \lVert θ_\star \rVert_2$, where $θ_\star \in \mathbb{R}^d$ is the unknown parameter vector, which is particularly problematic when $S$ is large, e.g., $S \geq d$. In this work, we improve the dependency on $S$ via a novel approach called {\it regret-to-confidence set conversion (R2CS)}, which allows us to construct a convex confidence set based on only the \textit{existence} of an online learning algorithm with a regret guarantee. Using R2CS, we obtain a strict improvement in the regret bound w.r.t. $S$ in logistic bandits while retaining computational feasibility and the dependence on other factors such as $d$ and $T$. We apply our new confidence set to the regret analyses of logistic bandits with a new martingale concentration step that circumvents an additional factor of $S$. We then extend this analysis to multinomial logistic bandits and obtain similar improvements in the regret, showing the efficacy of R2CS. While we applied R2CS to the (multinomial) logistic model, R2CS is a generic approach for developing confidence sets that can be used for various models, which can be of independent interest.
BibTeX
@inproceedings{lee2024improved,
  author = {Junghyun Lee and Se-Young Yun and Kwang-Sung Jun},
  title = {{Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=vsOmJQxfR3},
}
Figure