Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities

Thank you for taking the time to review our paper and for your thoughtful and valuable feedback. We deeply appreciate your recognition of our work and the constructive comments you have provided. Below, we address each of your comments and questions in detail:

[Dependence on $\kappa$ (Q1)]

By the definition of $\kappa$, $\kappa$ is lower bounded by $\Omega(1/K^2)$, i.e., $\kappa^{-1} = O(K^2)$. However, we would like to emphasize that its behavior is often far more favorable in practice. For example, as shown in the experiments of Lee & Oh [17] (Figure 1), the gap between the regret of $\kappa^{-1}$-dependent algorithms (e.g., UCB-MNL [23], TS-MNL [22]) and that of $\kappa^{-1}$-improved algorithm (e.g., OFU-MNL+ [17]) diminishes as $K$ increases. This implies that the regret of $\kappa^{-1}$-dependent algorithms [22, 23] does not grow significantly with $K$, even as $K$ increases. This suggests that equating $\kappa$ with $1/K^2$ or treating it as equivalent to $K$ is overly pessimistic.

For intuition behind $\kappa$, the parameter $\kappa$ is closely related to the curvature of the expected negative log-likelihood function. Consider the expected loss defined as $L(\mathbf{w}) = \mathbb{E}[- \log p(i \mid X, S, \mathbf{w})]$. Then, the Hessian of $L(\mathbf{w})$ is given by

Using standard calculations (see Lemma B.5 in [25]), this Hessian can be lower-bounded as:

where $p(0 \mid X, S, \mathbf{w})$ denotes the probability of outside option. In this context, $\kappa$ serves as a uniform lower bound on the product $p(i \mid X,S, \mathbf{w}) p(0 \mid X,S, \mathbf{w})$, and therefore provides a lower bound on the minimum eigenvalue of $\nabla^2 L(\mathbf{w})$. Since smaller eigenvalues indicate a more ill-conditioned log-loss landscape, a smaller $\kappa$ implies that the learning problem is more challenging.

Alternatively, we can think of how the probability of outside option relate to learning difficulty as follows. Consider the following example with two items $i_1, i_2$:

• [Case 1] $p(0) = 0.3, \quad p(i_1) = 0.35, \quad p(i_2) = 0.35, \quad \kappa = 0.3 \times 0.35 = 0.105$
• [Case 2] $p(0) = 0.9, \quad p(i_1) = 0.09, \quad p(i_2) = 0.01, \quad \kappa = 0.9 \times 0.01 = 0.009$

In Case 2, the high probability of the outside option reduces the likelihood of observing for items $i_1$ and $i_2$. As a result, the expected number of rounds needed to observe feedback for those items is significantly higher than in Case 1. This demonstrates that small value of $\kappa$ require more samples to gather informative feedback on individual items, thus increasing the overall sample complexity of learning.

[Role of Phase I (Q2)]

We are happy to answer your question. As described in Assumption 3, the context distribution is assumed to be supported on the context space $\mathcal{X}$. This implies that the distribution in Phase I is not restricted to a single direction. Therefore, the case where all Phase I contexts lie along a single direction—rendering them obsolete when Phase II contexts are orthogonal to that direction—would not occur.

Thank you for taking the time to review our paper and for your thoughtful and valuable feedback. We deeply appreciate your recognition of our work and the constructive comments you have provided. Below, we address each of your comments and questions in detail:

[Computation tractability (W, Q1)]

We are glad to address this comment. We would like to clarify that the notion of tractability in both Zhang & Luo [34] and our work refers to the computational feasibility of the exploration strategy, i.e., the process of selecting an assortment given a current utility estimator. The computation required for obtaining our pilot estimator is comparable to what is already used in [34]; for instance, their use of offline regression oracles in the stochastic setting and online regression oracles in the adversarial setting (see Assumptions 2 and 3 in [34]). As in [34], any tractable empirical risk minimization method (e.g., SGD) is sufficient for computing our pilot estimator in practice. We will incorporate this point into the revised manuscript.

[$\kappa$ dependence (W, Q2)]

We are happy to answer this question. By the definition of $\kappa$, we have $\kappa^{-1} = O(K^2)$ in the worst-case scenario. Note that the exponential dependence can be adjusted by rescaling the utility values. Zhang & Luo [34], for instance, define the MNL probability model using bounded utilities without applying the exponential transformation; see Eq. (1) in [34]. Consequently, our reverse Lipschitzness result (Lemma 4) can be used to recover the reverse Lipschitz bound in [34] (Lemma B.3). Nevertheless, we adopt a $\kappa$-dependent analysis because, while $\kappa^{-1}$ can scale as $O(K^2)$ in the worst case, its behavior is often far more favorable in practice. For example, as shown in the experiments of Lee & Oh [17] (Figure 1), the gap between the regret of $\kappa^{-1}$-dependent algorithms (e.g., UCB-MNL [23], TS-MNL [22]) and that of $\kappa^{-1}$-improved algorithm (e.g., OFU-MNL+ [17]) diminishes as $K$ increases. This implies that the regret of $\kappa^{-1}$-dependent algorithms [22, 23] does not grow significantly with $K$, even as $K$ increases. This suggests that equating $\kappa$ with $1/K^2$ or treating it as equivalent to $K$ is overly pessimistic.

In contrast, the dependence on $N$—the total number of items—is a more serious limitation. As discussed in the main text, our regret bound is independent of $N$. However, all algorithms in [34] exhibit polynomial dependence on $N$, regardless of tractability. This poses a significant obstacle for real-world applications involving large item sets—for example, platforms like Amazon, where the number of items can reach into the millions.

[Assumption 4 (W, Q3)]

Even though Assumption 4 is used as a sufficient condition to establish the fast convergence rate of the pilot estimator, we do not believe it a necessary condition. We expect that comparable convergence rates could still be achieved without relying on Assumption 4, if one instead uses parametric models with specific structures—such as one-hidden-layer neural networks with ReLU activation [31] or quadratic activation [32]—rather than broad classes of non-linear parametric functions. However, it is worth noting that even with such structural assumptions, existing convergence analyses often require the context vectors to be sampled from specific distributions (e.g., uniform over the unit sphere [31]), which limits their applicability in practical settings.

Thank you for taking the time to review our paper and for your thoughtful and valuable feedback. We deeply appreciate your recognition of our work and the constructive comments you have provided. Below, we address each of your comments and questions in detail:

[Reasonableness of assumptions (W1, W3, Q1)]

We thank the reviewer for providing us with the opportunity to clarify this point. First, we respectfully clarify that Assumption 2 is a condition on the utility function $f$ itself, not on the loss function. The properties in Assumption 2—boundedness, differentiability, and smoothness—are standard in the bandit literature that employs parametric reward models [1, 8, 9, 10, 18, 19, 20, 27], and they are also satisfied in NTK-based neural bandits [36, 38]. For instance, in over-parameterized neural networks, both the gradient and the Hessian are bounded; see Lemmas B.6 and C.2 in [38]. Moreover, in most existing MNL bandit literature [17, 22, 23, 25, 37], the utility function is assumed to be linear, in which case Assumption 2 holds trivially.

We also clarify that Assumption 4 does not require a quadratic growth condition. Instead, it introduces local strong convexity and a $(\tau, \gamma)$-growth condition (for $0 < \gamma < 2$) on the expected loss $\ell(w)$ around the equivalence set. Also, Assumption 4 is satisfied by a broad class of neural networks studied in prior work. For example, the local strong convexity of the population risk has been shown for two-layered neural networks (Zhong et al., 2017), quadratic neural networks [31], and ReLU networks (Zhang et al., 2019), all of which fall within the scope of our assumption. These models typically involve multiple global minimum (due to symmetries), and thus fall outisde the scope of earlier geometric conditions that rely on uniqueness of the global minimum. We will add this comment on the revised version.

Now, we would like to reiterate that Assumption 4 is strictly weaker than the global strong convexity assumed in prior parametric bandits [1, 8, 9, 10, 19], and does not require the existence of a unique global minimum [18, 20, 27]. This allows for an arbitrary number of spurious local minima and global minima in the landscape of the expected loss, enabling our analysis to cover highly non-convex and non-linear utility functions. In summary, the function class covered by Assumption 4 generalizes the parametric function classes studied in prior bandit literature, and additionally includes a broader family of non-linear, non-convex functions that have not been addressed in earlier works.

(References)

• Zhong et al. (2017), "Recovery Guarantees for One-hidden-layer Neural Networks", ICML
• Zhang et al. (2019), "Learning One-hidden-layer ReLU Networks via Gradient Descent", AISTATS

[Comparison with Zhang & Luo (2024) (W2, Q2)]

We appreciate the reviewer's suggestion and will include a table that compares the assumptions and regret bounds of prior work and ours.

We would like to clarify that Zhang & Luo [34] also make boundedness and Lipschitz continuity assumptions. As mentioned in the main text, Assumption 4 is required in Phase I to establish the convergence rate of the pilot estimator. In contrast, the analysis in [34] relies on the generalization error of the (offline or online) regression oracle measured in terms of log-loss (Assumption 2 & 3 in [34]), rather than on the distance between the estimator and the true parameter. This implies that even if a geometric condition like our Assumption 4 were imposed in the setting of [34], it would not yield any advantage in terms of computational tractability.

On the other hand, under the same generalization error rate of $O(1/n)$ established in [34], we show that, when combined with Assumption 4, this is sufficient to guarantee a fast convergence rate of the estimator. The main contribution of our work lies in proposing an algorithm for MNL bandits with non-linear utilities that is both computationally tractable and statistically efficient, under Assumption 4, which is satisfied by a broad class of parametric models and neural networks. We believe it remains an open question how large the class of utility functions is in practical scenarios where Assumption 4 does not hold, and whether a suitable regression oracle, as required in [34], exists for such function classes.

[About $\kappa$ (W4, Q3)]

By definition, $\kappa^{-1} = O(K^2)$ in the worst-case scenario, and we use $\kappa = \frac{\exp(-1)}{(1 + K \exp(1))^2}$ in our numerical experiments. We would like to note that in our current analysis, the dependence of $n$ or $T$ on $\kappa$ serves as a sufficient condition for achieving the $\tilde{O}(\sqrt{T})$ regret bound. However, as shown in our experiments, the algorithm performs well even with a small number of pure exploration rounds, suggesting that the theoretical $\kappa$-dependence may be overly conservative in practice. We believe that closing this gap, or deriving regret bounds with improved dependence on $\kappa$ in the context of non-linear MNL models, remains a valuable direction for future research.

Thank you for taking the time to review our paper and for your thoughtful and valuable feedback. We deeply appreciate your recognition of our work and the constructive comments you have provided. Below, we address each of your comments and questions in detail:

[Real-world dataset (W1)]

Since the sequential assortment selection problem addressed in our paper involves online decision making, it is inherently challenging to obtain real-world datasets that exactly match our problem setting. First, ground-truth choice probabilities are typically unobservable in real-world environments. Second, suppose there are $N$ total base items that a user can choose from. In practice, a real-world dataset would not contain responses for all combinatorially many assortments (at least $N$ choose $K$ combinations). If we only have responses for a small subset of these assortments, it becomes unclear how to evaluate an algorithm when it selects an assortment for which no feedback is available in the dataset.

Furthermore, even if suitable offline datasets exist, semi-synthetic experiments are still necessary to compute online regret—an essential evaluation metric in our setting. For these reasons, we—along with the majority of prior MNL bandit work [2, 3, 4, 17, 22, 23, 24, 25, 37]—rely on synthetic datasets that simulate realistic choice behavior, enabling reliable and consistent comparisons between algorithms. Additionally, we emphasize that we evaluate our method under model misspecification, where the true utility function differs from the estimated model, in order to better reflect practical scenarios.

[Scalability (W1)]

We conducted experiments across a wide range of values for $K$, $d$, and different network structures, as much as time permitted. We adopted the default configuration used in the original paper, setting $N = 100$, $K = 5$, $d = 3$, $L = 2$, and $m = 3$ where $L$ denotes the number of layers and $m$ denotes the number of hidden units per layer. In each experiment, we varied one or more of these parameters to assess performance of the algorithms. We report the cumulative regret at $T = 1000$, averaged over 5 independent runs.

Across all tested settings, our algorithm consistently achieves lower cumulative regret than baselines. We also note that experiments with larger $N$ are already provided in Appendix G for the reviewer’s reference.

[Multiple global minima (W2)]

The existence of multiple global minima does not affect the main regret bound presented in Theorem 1. This is because our regret analysis depends not on convergence to a particular global minimizer, but rather on how quickly the algorithm approaches the equivalence set $\mathcal{W}^{\ast}$. Based on Assumption 4, which characterizes the local geometry of the expected loss around the equivalence set $\mathcal{W}^{\ast}$ (as opposed to the unknown utility parameter $\mathbf{w}^{\ast}$), we establish a convergence guarantee for the pilot estimator $\hat{\mathbf{w}}\_0$ relative to $\mathcal{W}^{\ast}$. Subsequently, the construction of the confidence set and the computation of the optimistic utility are both based on this convergence behavior with respect to the equivalence set. Thus, the regret bound remains valid no matter which global minimum the algorithm converges to.

[Density (W3)]

Since non-linear utility functions in the MNL bandit setting have not been extensively explored in prior literature, we aimed to provide as much technical detail as possible to clearly convey the challenges of learning non-linear utilities within this framework. We respectfully believe that this level of depth is a strength rather than a weakness of the paper.

In response to the reviewer's concern, we have supplemented the intuition behind our regret analysis. As the reviewer is likely aware, the core technical components of the UCB algorithm involve:

(i) constructing a confidence set for the unknown true parameter (see Lemmas 1 and 2), and

(ii) computing an optimistic estimate within that confidence set (see Lemma 3).

In Section 3.3, we explain how these two elements are instantiated in the context of MNL bandits with non-linear utility functions. If additional space becomes available at the camera-ready stage, we would be happy to further incorporate intuition and discussion behind our regret analysis.

[$\kappa$ dependence (W4)]

Since we do not use an $\varepsilon$ in our manuscript, we believe the reviewer’s question as referring to the problem-dependent instance $\kappa$. Indeed, our current regret bound depends on $\kappa$. This type of dependence has also been observed in prior work on MNL bandits with linear utilities [10, 19, 22, 23], and only recently have algorithms been proposed that achieve regret bounds with improved dependence on $\kappa$ [8, 17, 37]. A key ingredient such improvements were possible is that the negative log-likelihood in the linear MNL model exhibits a self-concordant-like property. However, this property is generally not expected to hold in non-linear utility settings, because it requires the underlying utility function to satisfy a strong third-order smoothness condition—specifically, that the third derivative is controlled by the second derivative. Such functions constitute a very restricted class. Therefore, we believe that developing regret bounds with weaker $\kappa$-dependence in the non-linear utility setting remains an open and challenging problem, likely requiring new analytical tools.

[Baselines (W5)]

To the best of our knowledge, except for Zhang & Luo [34], almost all prior work on contextual MNL bandits assumes a linear utility function [5, 24, 22, 4, 23, 25, 2, 37, 17]. This is why the baselines we compare against are predominantly based on linear models.

Meanwhile, reward models used in neural bandits are fundamentally mismatched with the MNL bandit setting. Neural bandit algorithms are designed for multi-armed bandit problems that learn reward functions for individual arms, whereas MNL bandit algorithms are designed for assortment selection problem, where the goal is to model choice probabilities over item sets. This model mismatch is also why standard linear contextual bandits like LinUCB or LinTS are not typically included in comparisons within the linear MNL bandit literature. However, we would be happy to include additional baselines if the reviewer could suggest any methods that handle non-linear utilities in the MNL setting; we are more than willing to run further experiments within the remaining review period!