Improved Online Confidence Bounds for Multinomial Logistic Bandits

Thank you very much for your positive evaluation of our paper and for your valuable feedback! Below is our response to your question:

The online confidence sequence is claimed to be the "tightest", so could the authors provide some lower bounds on the width confidence radius itself, or at least some intuition on why couldn't we do better?

When we referred to our result as the "sharpest online confidence bound," we meant that, to the best of our knowledge, it is the sharpest among existing works—not that it is fundamentally optimal or cannot be further improved. In the final version, we will clarify this point to prevent any potential misunderstanding or impression of overclaiming. We sincerely appreciate your constructive feedback, and please don’t hesitate to reach out if you have any further questions.

Thank you for your positive review! We are very pleased that the reviewer appreciates the significance of our technical contributions. In particular, we’re delighted that you found our proposed $\ell_\infty$-norm self-concordant property interesting. We hope this new property will inspire further research on MNL models, extending beyond the MNL bandit setting.

Please find our responses to your questions below:

Motivation and Applications

The MNL bandit model offers a powerful and flexible framework for modeling choice behavior in sequential decision-making settings, where a decision-maker presents a subset of items (an assortment) and observes user selections based on relative utilities. This structure naturally arises in a wide range of real-world applications, making the study of MNL bandits both practically relevant and theoretically important. Some key domains include:

• E-commerce and Online Retail: Platforms choose a subset of products to display to each customer. The customer's purchase behavior is naturally modeled using discrete choice models such as MNL.

• Recommender Systems: Services like Netflix or Spotify present a small selection of items (e.g., movies or songs), and the user selects one. Modeling this behavior with an MNL model enables the system to learn user preferences and optimize engagement.

• Online Advertising: Ad platforms select a set of ads to display, aiming to maximize click-through rate (CTR) or conversions. The MNL model captures how user choice probabilities depend on both the ad features and the composition of the ad set.

• Dynamic Pricing and Assortment Optimization: Retailers dynamically select assortments subject to pricing or inventory constraints. The MNL model reflects how customer choices shift in response to changes in availability and pricing.

• Potential Application to RLHF: The MNL bandit framework also has promising applications in Reinforcement Learning from Human Feedback (RLHF). Human preferences in RLHF are often modeled using BTL or Plackett-Luce (PL) models. Since MNL generalizes BTL to multi-choice settings and serves as a building block for PL (ranking models), it provides a natural and flexible foundation for modeling richer forms of preference feedback in RLHF.

We believe that the MNL bandit model provides not only a unifying theoretical framework but also a practically impactful tool for real-world sequential decision-making. We will consider expanding this motivation section in the final version. We sincerely appreciate the suggestion to highlight these broader applications.

Variance-dependent lower bound

As discussed in Remark 4.7, our proposed algorithm achieves a regret upper bound that is nearly minimax optimal in both uniform and non-uniform reward settings, when compared to the worst-case (variance-independent) lower bounds established by Lee and Oh (2024). To the best of our knowledge, a formal variance-dependent lower bound has not yet been established for MNL bandits. The most closely related result is the instance-dependent lower bound (specifically, $\kappa^\star_t$-dependent) proposed by Lee and Oh (2024); see Proposition 1 in their paper. Here, $\kappa^\star_t$ is the variance of the optimal assortment $S^\star_t$ under uniform rewards (see Appendix E.2 of our paper for further discussion), rather than the assortment $S_t$ selected by an algorithm.

Thus, whether a fully variance-dependent lower bound can be derived in the MNL bandit setting remains an open question. Very recently (less than three weeks ago), He and Gu (2025) [1] established the first variance-dependent lower bound for general variance sequences in linear contextual bandits [1]. Their techniques may be adaptable to the MNL setting, and we view this as an interesting direction for future research.

[1] He, Jiafan, and Quanquan Gu. "Variance-Dependent Regret Lower Bounds for Contextual Bandits." arXiv preprint arXiv:2503.12020 (2025).

Thank you for taking the time to review our paper and provide valuable feedback.

We would like to clarify that our main contribution is the development of the first $B,K$-free, variance-dependent optimal regret bound for MNL bandits, which cannot be achieved by existing algorithms such as those proposed by Faury et al. (2022) or Lee and Oh (2024). We provide detailed explanations below and sincerely hope this clarification helps convey the novelty of our approach.

Comparison to Faury et al. (2022)

While our algorithm shares some conceptual similarities with Faury et al. (2022)—notably the adaptive warm-up strategy—it fundamentally differs from their method in several key aspects beyond just the use of online updates:

• Decision rule: The decision rule used in the adaptive algorithm (ada-OFU-ECOLog) by Faury et al. (2022) does NOT yield a $B$-free confidence bound. Their confidence bound, $\eta_t(\delta)$ (defined in Equation (15) of their paper), has an order of $\mathcal{O}(B d \log t)$. This $B$-dependence arises primarily because their method does not guarantee that the diameter of the search space, $\text{diam}_{\mathcal{A}}(\Theta_t)$, remains small or bounded by a constant over time.

  This is notably distinct from their non-adaptive algorithm (OFU-ECOLog, fixed-arm setting), which achieves a tighter confidence bound $\sigma_t(\delta)$ of order $\mathcal{O}(d \log t + B)$. We believe the reviewer may have inadvertently confused the confidence bound of ada-OFU-ECOLog with that of the non-adaptive version (OFU-ECOLog).

  In contrast, our proposed decision rule always guarantees a confidence bound that is completely independent of $B$. Combined with our new decision rule and the novel online confidence bound established in Theorem 4.2—which incorporates several technical novelties such as $\ell_\infty$-norm self-concordance, bounded intermediate terms, and a $d$-free regularization parameter—we successfully achieve a $B$-free regret bound.

• Prior knowledge of $\kappa$: Faury et al. (2022) require prior knowledge of $\kappa$, which is often impractical or even impossible to know beforehand in real-world settings. In contrast, our algorithm does not rely on any prior knowledge of $\kappa$, making it significantly more practical.

• Gram matrix update: In Faury et al. (2022), the Gramm matrix $V^{\mathcal{H}}\_t$ is updated overly conservatively using a weight parameter $\kappa$ as $V^{\mathcal{H}}\_t \leftarrow \sum_{ a\in \mathcal{H}\_{t+1}} \kappa a a^\top + \gamma_t(\delta)I_d$. Since $\kappa$ is very small—specifically, $\kappa = \mathcal{O}(e^{-3B})$ in logistic bandits, and even smaller in MNL bandits with $\kappa = \mathcal{O}(K^{-2} e^{-3B})$—the updates become too conservative. As a result, their search space $\Theta_t$ shrinks too slowly. In contrast, our algorithm does NOT apply such conservative updates to the warm-up Hessian matrix $H^w_{t+1}$. Instead, we update it using the second derivative of the loss, which enables the search space $\mathcal{W}^w_t(\delta)$ to shrink more rapidly and tightly.

$\ell_\infty$-norm self-concordance

Our self-concordant property is constructed with respect to the $\ell_\infty$-norm, whereas Lee and Oh (2024) use the $\ell_2$-norm. This distinction is crucial: naively applying an $\ell_2$-norm-based self-concordant property leads to a step size $\eta$ that depends on $K$ and $B$, which in turn causes the confidence bound to also depend on these parameters.

We believe this novel $\ell_\infty$-norm self-concordant property is of independent theoretical interest and has potential applicability beyond bandits, extending more broadly into the literature on MNL models.

Variance-dependent bound

It appears the reviewer may be confusing the definition of variance used in the cited papers [1,2]. To clarify, similar to our setting—where variance depends on the selected assortment $S_t$—the variance in [1,2] also explicitly depends on the chosen arm $x_t$. Moreover, the regret bounds in both our work and [1,2] are not dependent on the learner’s predictions—they depend solely on the variance under the true parameter.

Tightness of $B$ in non-leading term

Since Theorem 4.12 (MLE version) achieves a regret bound with a non-leading term that is free of any polynomial dependence on $B$, we believe that the $B$-dependence in the non-leading term of Theorem 4.5 is likely not optimal. Eliminating this dependency is an interesting direction for future work. We appreciate the insightful question that brought attention to this issue.

We sincerely believe that we have addressed all of your concerns. If you agree, we would greatly appreciate it if you could kindly reconsider your evaluation. Additionally, please feel free to reach out if you have any further questions or require clarification on any point.

We sincerely appreciate your positive support and recognition of the value of our work! We truly hope that this research helps to illuminate a new direction for MNL models and bandit algorithms. Please feel free to reach out if you have any further questions.