Improved Confidence Regions and Optimal Algorithms for Online and Offline Linear MNL Bandits

Thank you for your valuable questions and suggestions! We greatly appreciate your feedback and provide our point-by-point responses below.

Q1: Difference between Assumption 1 and i.i.d. assumption.

Compared to the i.i.d. assumption over $(X_t,S_t)$, Assumption 1 requires only independence among $(i\_t)\_{t=1}^T$ conditional on $\{ (X\_t,S\_t) \} \_{t=1}^T$. This still allows complicate dependence among $(X\_t,S\_t)$ across $t$.

An example of generating samples that satisfy conditional independence in $i_t$ is the SupCB algorithm we present in Section 4, originally inspired by [8]. The key to achieving this property is ensuring that the decision-making process does not depend on past choice observations. After the warm-up phase, each layer of Algorithm 2 uses only the $(X_t, S_t)$ information from samples collected during step (a) to compute the confidence region, which then guides future exploration actions in subsequent rounds of step (a). This design ensures that the samples used to construct the confidence region are independent of the observed choices at this layer, thereby satisfying the conditional-independence requirement on $(i_t)$.

Q2: Comparison of our burn-in condition to those in [42].

Under our notation with $\lambda = 0$, the confidence bound result in [42] can be stated as follows:

Under the burn-in condition, \lambda\_{\min}(V_t) \gtrsim \kappa^{-4}d^2 \text{ with } V_t = \sum_{k=1}^t \sum_{j\in S_t} x_{k,j}x_{k,j}^\top, \tag{R1}

it holds with probability at least $1-\delta$ that

\lvert x^\top(\hat\theta_D - \theta^\star) \rvert \lesssim \kappa^{-1} \lVert x \rVert_{V_t^{-1}} \tag{R2}.

Now we compare the result in [42] with ours:

• Burn-in condition. Comparing the burn-in condition in (R1) and the corresponding confidence bound in (R2) with our results, note that from the inequality H_t(\theta^\star) \succeq \kappa V_t, \tag{R3} we have

$\text{(R1) holds }\implies \lambda_{\min}(H_t(\theta^\star)) \geq \kappa \lambda_{\min}(V_t) \gtrsim \kappa^{-3} d \gtrsim d \implies \lVert x \rVert_{H_t(\theta^\star)^{-1}} \lesssim 1/\sqrt{d}, \forall \lVert x \rVert_2\leq 1.$

Therefore, the burn-in condition required in [42] holds implies that our burn-in condition is also satisfied.

• Confidence interval length. By (R3), we have for any $x$,

$\lVert x\rVert_{H_t^{-1} (\theta)} \lesssim \kappa^{-1} \lVert x \rVert_{V_t^{-1}} ,$

this shows our confidence interval length is smaller than (R2) result provided in [42].

Typos.

We thank the reviewer for pointing out the typos and limitations mentioned in the weaknesses and minor comments. We will correct the typos and further acknowledge the limitations regarding the $\kappa$ prior in the revised version. Specifically, we will discuss the related results from [35, 44] below our theoretical guarantee for the initialization phase in Algorithm 2 to improve clarity.

Empirical results

Regarding the experiment results, we have added several numerical experiments, including the

• Illustration of burn-in condition: We provide an empirical illustration of our confidence bounds under varying burn-in constants, demonstrating the sensitivity to the burn-in condition in Theorem 1. Please refer to our response to Reviewer nFhi for detailed results and setup.

• Offline MNL bandits: We compare our approach with the PASTA algorithm [26] for offline linear MNL bandits under full coverage, partial coverage, and misspecified settings. Details can be found in our response to Reviewer LNHW.

We hope these additional experiments can offer empirical evidence to complement our theoretical contributions.

Thank you for your valuable questions and suggestions! We greatly appreciate your feedback and provide our point-by-point responses below.

Q1: The sensitivity of algorithm performance under burn-in conditions and the trade-off.

Thank you for this insightful question. In the revised version, we have included several numerical studies examining the sensitivity of our confidence interval (CI). Below, we highlight some key observations related to this issue and refer the reviewer to our response to Reviewer nFhi for additional details. For clarity, we denote the burn-in factor as $\zeta:= \max\_{k\leq t, j \in S\_k} \lVert x\_{kj} \rVert\_{H^{-1}(\theta^\star)}$ for simplicity.

• Sensitivity of CI result in Theorem 1. While there is no clear phase-transition threshold $\alpha^\star$ for the burn-in constant $\zeta$—i.e., no sharp point at which the CI fails for $\zeta > \alpha^\star$ and holds for $\zeta < \alpha^\star$—our results show that the CI ratio increases with $\zeta$. This trend may indicate a potential violation of the our CI guarantee in Theorem 1 in the large $\zeta$ regime.

• Stability of the CI bound in Proposition 2( from [44]). The CI ratio of [44] remains stable as $\zeta$ increases. This aligns with the theoretical guarantee in Proposition 2, which does not require a burn-in condition.

• Better Trade-off between the two CI in algorithm design. In practice, we may wish to adaptively select between the two confidence intervals to perform well in both small and large $\zeta$ regimes.

One way to enable such adaptivity is by computing a data-driven upper bound on $\zeta$: First, note that $V_t$, defined in line 170 of our paper, is computable. From the dominance relation $H_t(\theta^\star) \succeq \kappa V_t$, we have $\zeta = \max\_{k\leq t, j \in S\_k} \lVert x\_{kj} \rVert\_{H_t^{-1}(\theta^\star)} \leq \kappa^{-1/2} \max\_{k\leq t, j \in S\_k} \lVert x\_{kj} \rVert\_{V_t^{-1}}.$ Letting $\hat{\zeta}:= \max\_{k\leq t, j \in S\_k} \lVert x\_{kj} \rVert\_{V_t^{-1}},$ we arrive at a fully data-driven quantity. Then for any threshold $\alpha > 0$, a sufficient condition for $\zeta \leq \alpha$ is $\hat{\zeta} \leq \kappa^{1/2} \alpha$. Moreover, if an upper bound on the parameter norm $W$ is available, we can obtain a (possibly conservative) lower bound on $\kappa$, making this condition verifiable from observed data.

In particular, we can simply switch to the CI from Theorem 1 if and only if $\hat{\zeta} \leq \kappa^{1/2} \alpha$, where $\alpha$ could be, for example, the burn-in threshold in Theorem 1. We hope this provides a practical guideline for balancing the two types of confidence bounds.

Q2: Practical heuristics to improve computational efficiency for Algorithm 2.

Thank you for this interesting question! While several heuristics have been proposed in the MNL setting to improve enumeration efficiency in MNL bandits (e.g., the DP-based approach and greedy swapping heuristics discussed in Section 5 of [18]), we believe that developing similar heuristics in our setting may be significantly more challenging.

The main difficulty lies in the nature of the assortment space $\mathcal{A}\_\ell$: Unlike [18], where enumeration is performed over all $K$-sized assortments—a well-structured and easily verifiable set—the collection $\mathcal{A}\_\ell$ in our setting is exponentially large and unstructured. This means that for any given assortment $S$, determining whether it belongs to $\mathcal{A}_\ell$ may require searching through (or storing) all $\lvert \mathcal{A}\_\ell \rvert$ elements. In contrast, in [18], one can simply check whether $S$ is of size $K$ to verify feasibility. This lack of structure makes heuristic design for our setting particularly difficult.

We will include the above discussion in the revised version to clarify the challenges involved.

Q3& Q4(a): Empirical studies and performance under model misspecification.

We thank the reviewer for pointing out direction for taking numerical studies. While our algorithm 2 is computationally in-efficient thus hard to take empirical studies. We have added several numerical studies on our Algorithm 1 in the offline setting. We have compared Algorithm 1 with two types of CI( Theorem 1 and Proposition 2), denoted by LCB-MLE and LCB-MLE-v2, to illustrate the trade-off author raised in question 1. We have also compared our result with the PASTA algorithm in [26]. We have conduct the experiment in 4 different settings, as detailed below:

Setting 1: Full Coverage Setting.

Table 1: Comparison of SubOpt Gap (smaller is better) under full coverage, $N = 30, d = K =10, W = 1$, over 10 repetitions.

In this setting, both the item features $X$ and the true parameter $\theta^\star$ are independently drawn from spherical uniform distributions. The observed assortments are sampled uniformly from all possible $K$-sized subsets of $[N]$. Under this setup, every item is guaranteed to be sufficiently covered. We observe that PASTA outperforms both LCB-MLE algorithms, and that LCB-MLE-v2—with its larger LCB penalty—performs worse than LCB-MLE. A possible explanation is that the increased penalty in LCB-MLE-v2 results in overly conservative decisions in this well-covered setting.

Setting 2: Partial Coverage Setting.

Table 2: Comparison of SubOpt Gap (smaller is better) under partial coverage

In this setting, we use the same $X$ and $\theta^\star$ generation and $N,K,d$ as in Setting 1, with a fixed sample size of $n = 500$. For each $n^\star$, assortments are constructed by sampling $n^\star$ items from the optimal set and the remaining $K - n^\star$ from other items, creating partial coverage. As $n^\star$ increases, coverage of the optimal set improves. We observe that both LCB-MLE algorithms outperform PASTA, with LCB-MLE-v2 performing best, likely due to its stronger conservativeness under partial coverage.

Setting 3: Misspecification under mixture of MNL I.

Table 3: Comparison of Expected Revenue (larger is better) under mixed MNL model I.

In this setting, we consider a mixture MNL model with two subgroups, where the second group is selected with probability $\mu$, and total sample size is $n = 500$. The generation of $X$, $\theta^\star$, and parameters $N$, $K$, $d$ follows Setting 1. Each assortment consists of 5 items sampled from the first group's optimal set and 5 from the rest.

Since computing the optimal assortment under a mixture MNL is intractable, we evaluate performance using expected revenue instead of SubOpt.

As $\mu$ approaches 0.5, model misspecification increases and performance degrades. All three algorithms perform similarly across settings.

Setting 4: Misspecification under mixture of MNL II.

Table 4: Comparison of Expected Revenue (larger is better) under mixed MNL model II.

In this setting, we use the same parameter setup as in Setting 3, with $\mu$ fixed at $0.5$. The distance between the two subgroups' parameters $\theta^\star$ is controlled by a parameter $\delta$.

As $\delta$ increases, model misspecification becomes more severe and performance degrades. In this setting, LCB-MLE-v2 outperforms LCB-MLE, which outperforms PASTA. This suggests that stronger conservativeness may improve performance under this type of misspecification.

Q4(b): Extensions the analysis framework to other settings with similar structure.

Yes, our results can be extended to other settings. One promising direction is the joint assortment and pricing framework considered in [R1, R2], where actions include both assortment selection and item pricing $p$. In this model, the final choice outcome can still be viewed as a sample from a linear MNL model incorporating both utility parameters and prices. This suggests that our Theorem 1, particularly the confidence bound construction, can also apply.

However, this extension poses computational challenges, as optimizing over both assortments and prices increases the overall complexity. Combining this with UCB/LCB-based algorithm design, as discussed in [R1, R2], may introduce further complexity and warrants future investigation.

[R1] Miao, Sentao, and Xiuli Chao. "Dynamic joint assortment and pricing optimization with demand learning." Manufacturing & Service Operations Management 23.2 (2021): 525-545.

[R2] Erginbas, Yigit Efe, Thomas Courtade, and Kannan Ramchandran. "Online Assortment and Price Optimization Under Contextual Choice Models." The 28th International Conference on Artificial Intelligence and Statistics.

Thank you for raising these important empirical concerns and suggestion on introducing formal definition of $\kappa$ in abstract and introduction!

We will add a brief definition of $\kappa$ to improve clarity in the revised version.

Regarding the practical applications, we acknowledge that our work has limitations in terms of direct applicability to real-world systems such as recommendation engines. A key assumption in our setting is the presence of a known linear feature representation of items, where the only unknown is the linear interaction parameter $\theta^\star$. This contrasts with the broader literature on recommendation systems, where representation learning plays a central role, and the optimal recommendations are often learned jointly with the representations—typically through end-to-end models such as deep neural networks, as the reviewer mentioned.

This fundamental difference limits the direct applicability of our algorithm and theoretical results to the types of problems addressed in modern recommendation systems. In particular, the challenge of learning feature representations from data is central in those systems but falls beyond the scope of our work, which focuses on the linear MNL bandit setting with known features. We view integrating feature learning into this framework as an important and promising direction for future research, which could potentially start with neural network–based MNL bandit formulations, such as the recent work [R1]—but this is beyond the scope of the present study.

Finally, although our emphasis is primarily theoretical, we have included several synthetic experiments that we hope will be of interest to reviewers. These include:

• evaluating how the burn-in condition affects the confidence interval in Theorem 1, discussed in our response to reviewer nFhi;

• comparing our method with the PASTA algorithm, a benchmark from prior work on offline linear MNL models, discussed in our response to reviewer LNHW;

• assessing the robustness of our method under model misspecification, discussed in our response to reviewer LNHW.

We hope these additional experiments can provide several empirical supports for our theoretical work.

[R1] Bae, Seoungbin, and Dabeen Lee. "Neural Logistic Bandits." arXiv preprint arXiv:2505.02069 (2025).

Thank you for your valuable questions and suggestions! We greatly appreciate your feedback and provide our point-by-point responses below.

Q1. Empirical comparison of CI results.

When comparing our confidence interval results with those in [44, 3, 35], our bounds are consistently tighter in the sense that the confidence radius is smaller, due to a $\sqrt{d}$-factor improvement. However, this comes at the potential cost of requiring an additional burn-in condition and a conditional independence assumption.

In the following simulation, we compare our confidence bounds with those in [44] under varying burn-in constants to illustrate the potential failure of our bounds when the burn-in condition is violated. We hope this illustration can help understand the underlying trade-off between CI tightness and risk of violation. Below, we first present the results and discussion, followed by the experimental setup.

• Result and Comments:

In the table below, we compare the CI ratio, defined as

for confidence interval results derived in our Theorem 1 and [44]. The CI ratio measures how tightly the theoretical confidence bound captures the actual estimation error. A smaller CI ratio indicates a lower likelihood of violating the theoretical CI guarantee.

We make the test under different burn-in constants:

Theoretically, our CI result in Theorem 1 requires $\zeta \lesssim 1/\sqrt{d}$ to holds and the CI result in [44] have no restriction on $\zeta$.

We observe that as $\zeta$ increases, our CI ratio in Theorem 1 also increases, indicating a higher likelihood of violating the theoretical bound. In contrast, the CI ratio in [44] remains stable as $\zeta$ grows, which aligns with the differing theoretical requirements of the two confidence bounds.

• Experiment Setup - Feature Set and Parameter: For a given $d,K$(W.L.O.G. suppose $d$ is even) and $\beta >0$, we construct the item-associated feature map set with $N = d$ as the following:

• Type-1 Items: The first d-1 features $x_i$ for $i\leq d-1$ are given by the canonical basis $x\_i = e\_{i}$.

• Type-2 Items The last feature $x\_{d}$ is given by $x\_{i} = (1,1,...,1)/\sqrt{d}$.

• Underlying Parameter $\theta^\star$ Given radius $W > 0,$ the $\theta^\star$ is set as $\theta^\star = (W,W,...,W)/\sqrt{d}.$

• Experiment Setup - Assortment Sets: With above construction of feature sets, we construct two types of assortments as the following:

• Type-1 Assortment: A single-item assortment containing only the type-2 item $S_0 = \{ d \}$ as a single-item set that only contains item $d$.

• Type-2 Assortments: Denote $m = \lceil d/K \rceil$, then for every $1\leq k\leq m,$ we set the $k$-th type-2 assortment as $S\_k:= [ (m-1)K + 1, (m-1)K + 2, ..., \min ( mK, d ) ]$

• Observed assortment sets. With above types of assortment sets. Given any number $n_1,n_2$, the observed assortment sets(and corresponding features and choices generated by linear MNL model with $X,\theta^\star$ above) is set as $n_1$ copies of $\{S_1,..., S_m\}$ and $n_2$ copies of $S_0.$

With above construction, we can fix the value of $n_1, n_2$ and moving $W$ to generate different environments with different level of burn-in constants $\zeta$. In particular, under our construction $\zeta$ is increasing as $W$ increases, as we shown in the table below:

This explains how we obtain environments to generate the results presented in table 1. Specfically, we select $d = 6, K = 3$ and $n1 = n2 = 500$ in the above experiment.

Q2. Technical comparison with [31].

Thank you for raising this suggestion and question! We would acknowledge that our analysis follows the same overall framework in generalizing Theorem 1 of [31]. However, the detailed calculations require new arguments that explore the geometric landscape and self-concordant properties of $K$-MNL losses, which is a central topic in recent theoretical studies on MNL bandits.

More precisely, our main technical contribution lies in Lemma 6, where we carefully explore the curvature of the MNL loss to derive a confidence region that avoids dependencies on $K$ and $\kappa$. This improves previous arguments in [42]( the only prior work that considers $d$-free confidence bounds under the independence condition), and parallels the refinement technique in [36], which is developed for different purpose( to obtain sharp variance-dependent bounds).

Q3. Algorithmic details

-Initial length $n_0$ in Algorithm 2 Thank you for pointing out this issue! It should not be an input to Algorithm 2, and we will remove it in the revised version. We apologize for the confusion caused.

-Prior knowledge of $\kappa$ In general, we cannot assume a strong prior on $\kappa$. However, it is relatively reasonable to assume prior knowledge of an upper bound $W$ on the parameter norm, as is common in previous work. Given this, we can derive a conservative lower bound on $\kappa$ that scales as $\exp(-K W)$, which is sufficient to serve as an algorithm input.

-Computation Complexity. The elimination step of the algorithm 2 requires to search over the whole $\mathcal{A}_l$, whose complexity scales as $O(N^K)$ in the worst case.

Q4. Writing Suggestions and Typos.

Thank you so much for the suggestion and pointing out those typos! You are absolutely right on the problems in line 3, 8, 162, we will correct those problems in the revised version. We will also clarify the terms 'MLE', 'MNL' when they first appears to improve clarity.