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

In this work, we consider the data-driven assortment optimization problem under the linear multinomial logit (MNL) choice model. We first establish an improved confidence region for the maximum-likelihood-estimator (MLE) of the d-dimensional linear MNL likelihood function that removes the explicit dependency on a problem-dependent parameter κ -1 in previous result [42], which scales exponentially with the radius of the parameter set. Building on the confidence region result, we investigate the data-driven assortment optimization problem in both offline and online settings. In the offline setting, the previously best-known result scales as O d κn S ⋆ , where n S ⋆ denote the number of times that optimal assortment S ⋆ is observed [26]. We propose a new pessimistic-based algorithm that, under a burn-in condition, removes the dependency on d, κ -1 in the leading order bound and works under a more relaxed coverage condition, without requiring the exact observation of S ⋆ . In the online setting, we propose the first algorithm to achieve O( √ dT ) regret without a multiplicative dependency on κ -1 . In both settings, our results nearly achieve the corresponding lower bound when reduced to the canonical N -item MNL problem, demonstrating their optimality.

† The κ ′ notation in [26] defined in a different way as those in other works, but the still suffers from the exponential dependency on ∥θ ⋆ ∥ in the worst case.

‡ When consider the canonical N -item setting with xi = ei, d = N, the Ω( √ N T ) result in [17] implies this result. * We leave the related algorithm design and proof to Appendix E.4 due to space limitation.

Based on the sharp confidence region result, we then consider the offline assortment optimization problem, where the seller can access to a dataset D = i k , S k n k=1 and aim to find the assortment that maximize the revenue. In this setting, we provide an pessimistic-based algorithm and show that under a basic coverage number of each items, it can achieve the sub-optimality gap that scales with O( i∈S

) ) in the leading-order term. Notably, we can show that p

for n i := n k=1 1i ∈ S k , thus it suffices for each i ∈ S ⋆ to be covered by S k sufficiently many times in order to ensure that ∥x i ∥ H -1 D (θ ⋆ ) becomes small. In contrast, the best-known result for linear MNL model prior to ours, presented in [26], scales as O d κn S ⋆ , where n S ⋆ := n k=1 1S ⋆ = S k . This result has an additional d-dependency and a multiplicative κ -1 -dependency compared to ours. More importantly, their approach requires the optimal assortment S ⋆ to be exactly observed sufficiently many times, which imposes a restrictive coverage requirement on D. Finally, we show that, when reduced to the canonical N -item setting with uniform item-wise rewards, our result matches the Ω max i K/n i lower bound recently developed in [29]. This demonstrates that the proposed item-wise coverage measure,

, is an appropriate metric for sample complexity in the offline setting.

Improved Regret for Online Assortment Optimization. In the online assortment optimization setting, where the seller starts without prior knowledge but can interact with arriving customers over T rounds, we design an algorithm based on the SupCB framework [8] that achieves a regret of O( √ dT log N + κ -1 d). This result improves upon the previous regret bound of O(κ -1 √ dT log N ) in [42] by reducing the dependency on κ -1 . Our result also improves the O(d [44,35] on the dependency of d when N = o(2 d ). Especially, our result is nearly optimal in the sense that it nearly matches the Ω( √ dT ) lower bound in [17] when reduced to the canonical N -item setting .