Online Learning of Delayed Choices

Authors: recep yusuf bekci
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 12:29:00

Abstract: Choice models are essential for understanding decision-making processes in domains like online advertising, product recommendations, and assortment optimization. The Multinomial Logit (MNL) model is particularly versatile in selecting products or advertisements for display. However, challenges arise with unknown MNL parameters and delayed feedback, requiring sellers to learn customers’ choice behavior and make dynamic decisions with biased knowledge due to delays. We address these challenges by developing an algorithm that handles delayed feedback, balancing exploration and exploitation using confidence bounds and optimism. We first consider a censored setting where a threshold for considering feedback is imposed by business requirements. Our algorithm demonstrates a $\tilde{O}(\sqrt{NT})$ regret, with a matching lower bound up to a logarithmic term. Furthermore, we extend our analysis to environments with non-thresholded delays, achieving a $\tilde{O}(\sqrt{NT})$ regret. To validate our approach, we conduct experiments that confirm the effectiveness of our algorithm.

Main paper: 
 introduction: 
 The ability to model and understand consumer choices between discrete alternatives is critical for various business applications, such as online advertising, product recommendations, and assortment optimization. Businesses need to present the most appealing set of options to consumers to maximize engagement and revenue. However, the task of optimizing what content or products are shown to a customer during their browsing session is complex due to the interplay between alternatives that customers face. Each alternative can act as a substitute or competitor to others, impacting the customer's final decision. Traditional multi-armed bandit (MAB) models, which are widely used for decision-making problems, fall short in scenarios where a subset of alternatives must be presented, and the customer's choice among these influences future decisions.Multinomial choice (MNL) models have emerged as powerful tools for capturing and predicting consumer behavior among a finite set of alternatives. These models estimate the utilities of different options and the probabilities of their selection. However, when the MNL parameters are unknown and no historical data is available-as is often the case with newly introduced products or advertisements-the learning process becomes even more challenging. This complexity is further exacerbated when the feedback on decisions is delayed, requiring the learner to dynamically adjust decisions based on limited and potentially biased information.One of the fundamental challenges in this setting is the delay in receiving feedback from customers. Unlike immediate responses in classical MAB problems, customers in e-commerce environments often take hours or even days to make decisions, as highlighted by Vernade et al. [2020] and Chapelle [2014] . This delay in feedback complicates the learning process, as it must adapt to new information that arrives sporadically and potentially long after the initial interaction.In this paper, we address the dual challenges of unknown MNL parameters and delayed feedback by developing algorithms that balances exploration and exploitation through the use of confidence bounds and the principle of optimism in the face of uncertainty. We focus on two settings in receiving delay: the thresholded and the non-thresholded settings.In thresholded settings, feedback is only considered if it is received within a predetermined time frame set by business requirements. This constraint ensures operational stability and efficiency by ignoring excessively delayed responses that may no longer be relevant. For these settings, we introduce the Delayed Multinomial Logit Bandit (DEMBA) algorithm, specifically designed to handle potentially censored delayed feedback effectively.In contrast, non-thresholded settings allow the learner to consider all feedback regardless of delay, potentially leading to better accuracy in decision making in long-term but at the cost of increased bias in the learning process. For such environments, we propose the Patient Delayed Multinomial Logit Bandit (PA-DEMBA) algorithm, which adapts its learning strategy to accommodate all feedback, irrespective of the delay.Contributions. Our main contributions are two novel bandit algorithms: we develop DEMBA, for thresholded feedback settings, and PA-DEMBA, an algorithm designed for non-thresholded feedback environments. Both algorithms effectively learn from delayed and censored choices using confidence intervals. We provide a comprehensive regret analysis for both DEMBA and PA-DEMBA, demonstrating an Õ( √ N T ) regret bound and a matching lower bound up to a logarithmic term. Additionally, through detailed computational experiments, we validate the performance and robustness of our algorithms in various scenarios.Organization. The remainder of this paper is organized as follows. In Section 2, we review the related work on choice modeling and delayed feedback in online learning. Section 3 details the problem formulation and the specific challenges addressed by our approach. Our main algorithm DEMBA is presented in Section 4. We analyze the regret bounds of this algorithm in Section 5, providing theoretical guarantees for its performance. PA-DEMBA algorithm for non-thresholded delays is presented in Section 6. In Section 7, we conduct experiments to demonstrate the effectiveness of our proposed algorithms. Finally, Section 8 concludes the paper and outlines potential directions for future research.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification: [NA] Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 Delayed feedback is a crucial aspect of online learning environments, especially in domains like online advertising and e-commerce, where decision making involves a consideration period, or in healthcare, where the effects of actions take time to manifest. Consequently, research interest in bandits with delayed feedback has surged in recent years.In their seminal work, Joulani et al. [2013] studied online learning scenarios with stochastic delayed feedback. Their work laid the foundation for understanding how delays impact learning performance. Similarly, Chapelle [2014] examined delayed conversions in display advertising, highlighting the practical challenges faced in real-world applications. Further, Vernade et al. [2017] focused on delays specifically in the context of delayed conversions, providing insights into handling delays with known distributions.Expanding on this, Pike-Burke et al. [2018] explored bandits with delayed, aggregated, and anonymous feedback, which adds another layer of complexity by considering multiple types of delays. Zhou et al. [2019] extended this exploration to generalized linear contextual bandits with delayed feedback. Vernade et al. [2020] investigated linear bandits with stochastic thresholded delays. Additionally, Gael et al. [2020] tackled multi-armed bandits with arm-dependent stochastic delays, focusing on the challenges of non-uniform delays across different choices. Moreover, Cesa-Bianchi et al. [2022] considered composite and anonymous delayed feedback within non-stochastic bandits, further enriching the literature on delayed feedback mechanisms. Tang et al. [2024] studied delayed multi-armed bandits (MAB) with reward-dependent delays in clinical trials, while Lancewicki et al. [2021] explored both reward-dependent and reward-independent delay settings. Flaspohler et al. [2021] investigated delayed learning in weather forecasting, and Grover et al. [2018] addressed the best arm identification problem with delayed feedback. Thune et al. [2019] examined non-stochastic MABs with unrestricted delays, and Cesa-Bianchi et al. [2016] considered cooperation between different agents in delayed settings. Tang et al. [2021] explored scenarios where past actions impact future arm rewards, and Yang et al. [2024] addressed general sequential decision-making problems with delayed feedback. Despite this rich body of work, the solutions developed for MABs do not directly apply to our setting, where assortment feedback in discrete choice models presents additional complexities. In particular, delayed feedback affects both item value estimation and assortment composition, making our problem significantly more challenging than those where only arm rewards are updated.When focusing specifically on generalized linear bandits with delays, we note key contributions such as Howson et al. [2023] and Blanchet et al. [2024] who explored generalized linear bandits with delayed feedback, demonstrating the efficacy of these models in more complex, non-linear settings. Multinomial bandits, which address decision making where multiple items are offered simultaneously, present a unique challenge due to the interactions between items. This complexity distinguishes our problem from other online learning models. Specifically, for generalized linear bandits, we note that when the assortment has more than one item, our problem cannot be addressed by solutions designed for generalized linear models due to the complexity of interactions among multiple choices which makes the action space more complicated.In terms of online learning with choice models, significant progress has been made in understanding and optimizing MNL parameters. Agrawal et al. [2017] developed a Thompson sampling algorithm for learning MNL parameters for assortment optimization, while Agrawal et al. [2019] proposed a UCB algorithm for the same purpose. Dong et al. [2020] adapted this problem by introducing switch costs, addressing practical constraints in dynamic environments. Further, Agarwal et al. [2020] studied the problem for best arm identification, extending the framework to multiple pulls, which is a generalization of the dueling bandits problem. Other notable works include Wang et al. [2018] and Chen et al. [2021] , who worked on dynamic assortment allocation under uncapacitated MNL models, and Perivier and Goyal [2022] , who investigated joint pricing and assortment optimization with MNL demand processes.To the best of our knowledge, our work is the first to address online learning of delayed choices in this context. Specifically, we propose the Delayed Multinomial Logit Bandit (DEMBA) algorithm for thresholded feedback settings and the Patient Delayed Multinomial Logit Bandit (PA-DEMBA) algorithm for non-thresholded settings. These algorithms effectively learn from delayed and censored choices using confidence intervals, providing robust solutions for dynamic and uncertain environments where feedback is not immediately available. Our approach not only advances the theoretical understanding of delayed feedback in online learning but also offers practical insights for applications in e-commerce and online advertising.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: [NA] Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
problem setup: 
 We consider a capacitated selection problem faced by a seller over T rounds. The items to be selected, referred to as products, can be new retail products or services such as advertisements. There are N products available to potentially be shown to the customer. The set of products selected in a given round is called an assortment, denoted as S t for round t, where S t ⊂ {1, . . . , N } and |S t | ≤ K.Here, K represents the capacity, indicating the maximum number of items the seller can show at any given time.Upon encountering the assortment, the customer makes a choice a t among the options: (i) rejecting the browsing options provided (a t = 0), (ii) browsing and purchasing/selecting an option (a t = i, i ∈ S t ), and (iii) browsing but not purchasing/selecting an option (a t = 0d). If option i is chosen, the seller earns a reward r i , with r i ∈ [0, 1] for i ∈ [N ] and r 0 = r 0d = 0.Customer choice probabilities are determined by the Multinomial Logit (MNL) model as follows:P(a t = i|S t = S) = vi v0+v 0d + j∈S vj if i ∈ S ∪ {0, 0d} 0 otherwise,where v i denotes the (unknown) attraction parameter of option i. Without loss of generality we assume that attraction parameters are normalized such that v 0 = 1. In parallel with the real applications, we also assume that not browsing is the most common choice, i.e. v i ≤ v 0 .It is important to note that not purchasing/selecting is different from tracking conversions. Specifically, if the customer browses the given assortment, we can track if the customer decides not to purchase, similar to choosing an option to purchase (e.g., by closing the pop-up or following specific behavioral click-through patterns).If the customer's choice is a t = 0, the seller receives this choice immediately. Otherwise, the customer's choice is revealed to the seller after a delay d t ∈ N. d t is sampled from a unknown distribution f d and independent from a t . Moreover, delays longer than a certain threshold µ is censored or ignored by the seller in the learning process. This threshold is set based on the seller's operational requirements. We later extend our solution to the patient learner setting without a threshold, i.e. µ → ∞.We define a i,t as the demand for option i at time t. We havea i,t = 1, if a t = i, 0, otherwise.We also define c i,s,t ∈ {0, 1} as the censoring variable of product i at period t that is sold at period s.The censoring variable is determined as:c i,s,t = I(d s ≤ t -s and d s ≤ µ).We define the feedback observed by the seller as o i,s,t ∈ {0, 1} and o i,s,t = c i,s,t a i,s . The expected fraction of observed feedback is denoted as ψ µ := µ s=0 f d (s). The sequence of events at round t can be summarized as follows:1. The seller selects an assortment S t . 2. The customer interacts with the medium(view the page or encounter with the pop-up) and makes a decision a t . 3. The environment returns a reward r i , i ∈ [N ], and samples a delay d t . 4. Rewards of certain previous actions and/or if the customer rejected to browse revealed to the seller as o i,s,t .The expected reward of the seller given assortment S and attraction parameter set v is given byR(S; v) = i∈S r i • v i 1 + v 0d + j∈S v j .The goal of the seller is to sequentially learn customer preferences and find a policy to minimize cumulative expected regret, defined as:Reg(T, π) = T t=1 R(S * ; ψ µ v) -R(S π t ; ψ µ v),where S * = arg max S⊂{1,...,N },|S|≤K R(S; ψ µ ) maximizes the expected reward of the clairvoyant and v = {v 0d , v 1 , . . . , v N } is the ground truth attraction parameter set.4 Delayed MNL Bandit (DEMBA) AlgorithmIn this section, we introduce the Delayed MNL Bandit (DEMBA) algorithm. DEMBA leverages an epoch-based learning method, where epochs are explicitly defined by immediate no-purchase decisions. Specifically, when a no-purchase decision is made by the customer, the current epoch is closed, and a new one begins. Throughout each epoch, customer selections are observed, and parameter updates occur upon encountering a no-purchase outcome.Our approach adopts the principle of optimism in the face of uncertainty [Auer et al., 2002] for parameter estimation, generating optimistic estimations using upper confidence bounds for product attraction parameters and a lower confidence bound for the no-purchase option. This results in an optimistic revenue function, guiding decision-making under uncertainty by balancing exploration and exploitation.We build our optimistic estimates on biased observations. The total observed preference given to product i until epoch τ is denoted as ṽi,τ and can be calculated as ṽi,τ =t end τ s=1 o i,s,t end τ ,where τ is the current epoch and t end τ is the last period of epoch τ .We count how many times a particular product i is offered in the assortment until epoch τ using the set E τ (i) which is the set of epochs during which i is offered, i.e. E τ (i) = {e ≤ τ : i ∈ S e }. Then, we estimate attraction parameters byvi,τ = ṽi,τ |E τ (i)| .vi,τ is a biased estimator due to delay and thresholding, i.e. E[v i,τ ] ̸ = v i . We consider this bias in our estimation and build our concentration around ψ µ v i . We state our concentration result in the following lemma.Lemma 4.1 With probability at least 1 -O(N -2 T -1 ), for every epoch τ ∈ {1, . . . } and option i ∈ {0d, 1, . . . , N }, we have|v i,τ -ψ µ v i | ≤ ∆ i,τ ,where∆ i,τ = (48vi,τ +1) log(N T ) |Eτ (i)| + 48 log(N T )+µ |Eτ (i)|.Sketch of the proof. Note that vi,τ is a biased estimator and defined asvi,τ = ṽi,τ |E τ (i)| = t end τ s=1 o i,s,t end τ |E τ (i)| ,where |E τ (i)| is the total number of epochs during which product i is shown to the customer andt end τ s=1 o i,s,t end τis the total observed sales of product i ̸ = 0d or is the total observed delayed no selections.We analyze the concentration around ψ µ v i :EQUATIONwhere the second equality follows from decomposing the observations into those before and after the threshold, the third equality rearranges the terms, and the last inequality uses the triangle inequality.For the first term in the decomposition (1), we haveEQUATIONWe bound the first term (a) using Hoeffding's inequality:EQUATION)For part (b), we make use of the Chernoff bound from Theorem A.1 and handle two cases basedon ζ = (v i + 1) 6 log(N T ) vi|Eτ (i)| .The detailed proof is provided in Appendix A. The result can be summarized as follows:EQUATIONCombining the bounds for both terms, we establish the concentration result stated in Lemma 4.1. □Using the concentration result for the attraction parameters, we construct upper confidence bounds for each product at each epoch:vi,τ = vi,τ + ∆ i,τ ,and for the delayed no-purchase option, we construct a lower confidence bound:v 0d,τ = v0d,τ -∆ 0d,τ ,where∆ i,τ = (48v i,τ + 1) log(N T ) |E τ (i)| + 48 log(N T ) + µ |E τ (i)| .We use the optimistic parameter estimations to construct an optimistic revenue functionR(S; v) = i∈S r i vi,τ 1 + v od,τ + j∈S vj,τ .Our algorithm DEMBA suggests the assortment according to the optimistic revenue function R(S; v) and updates parameters according to feedback received with delay. The pseudocode of DEMBA is given in Algorithm 1.Computational complexity. The computational complexity of the DEMBA algorithm involves several key components. The most intensive step is computing the assortment S τ by maximizing the revenue function R(S; v). For this step, polynomial-time solutions with O(N 2 ) complexity are available, as demonstrated by Rusmevichientong et al. [2010] and Davis et al. [2013] . Updating observed preferences ṽi,τ involves summing over previous observations, with a complexity of O(N (t start τ -t end τ )). The process of updating sets E τ (i) and estimations vi,τ and the confidence bounds adds O(N ) operations per epoch. Given that τ ≤ t and t ≤ T , the overall computational complexity across all roundsT is O(T N 2 + N T 2 ). Algorithm 1 Delayed MNL Bandit (DEMBA) Initialize: t = 0, τ = 0; while t < T do Compute S τ = arg max S⊂{1,...,N },|S|≤K R(S; v); Offer assortment S τ ; Receive feedback; if a t = 0 then {immediate reject} ṽi,τ = t end τ s=1 o i,s,t end τ ∀i ∈ [N ] ∪ {0d}; E τ (i) = {e ≤ τ : i ∈ S e } ∀i ∈ [N ] ∪ {0d}; vi,τ = ṽi,τ |Eτ (i)| ∀i ∈ [N ] ∪ {0d}; vi,τ = vi,τ + ∆ i,τ ∀i ∈ [N ]; v 0d,τ = v0d,τ -∆ i,τ τ = τ + 1 end if t = t + 1 end whileQuestion: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
regret analysis: 
 Our main result is given in the following theorem.Theorem 5.1 Let π DEM BA be the policy produced by Algorithm 1 using∆ i,τ = (48vi,τ +1) log(N T ) |Eτ (i)| + 48 log(N T )+µ |Eτ (i)| . Then, π DEM BA satisfies Reg(T, π DEM BA ) ≤(1 + µ) log(T ) + K 73T log(N T ) + 48K log(T )(log(N T ) + µ) + 73 N T log(N T ) + 48 log 2 (N T ).The bound can be further simplified to Õ √ N T by omitting logarithmic terms.Sketch of the proof. The proof of Theorem 5.1 consists of several steps. First, we use the definition of the optimistic revenue function R(S; v) and show that it provides an upper bound on the true revenue function R(S; ψ µ v). This is achieved by leveraging Lemma B.1, which ensures that the estimated attraction parameters are close to their true values with high probability.We start by expressing the regret in terms of the epochs:Reg(T, π) = E τ τ =1 |H τ | (R(S * ; ψ µ v) -R(S τ ; ψ µ v)) ,where H τ is the duration of epoch τ . Given that the epoch duration follows a geometric distribution, we simplify the expected regret using the law of total expectations.Next, we decompose the regret into two parts: one that occurs with high probability (event E C τ ) and one that occurs with low probability (event E τ ):E[∆R τ ] = E ∆R τ I(E τ -1 ) + ∆R τ I(E C τ -1) . We bound the contribution of the low-probability event by (N + 1)P(Eτ -1), which is small due to our concentration results.For the high-probability event, we show that the difference between the optimistic and true revenues is bounded by ∆ i,τ . Applying Lemma B.1, we can then bound the regret for each epoch:E[∆R τ ] ≤ (N + 1)P(Eτ -1) + E     1 + ψ µ v 0d + j∈Sτ ψ µ v j   (R(S τ ; vτ ) -R(S τ ; ψ µ v)) I(E C τ -1 )   .Summing over all epochs and using the properties of the epoch duration, we show that the total regret is bounded by Õ(√ N T ). □The full detailed proof is provided in Appendix B.Next, we provide a lower bound result for the regret in the following theorem:Theorem 5.2 For any policy π, suppose K ≤ N/4, T ≥ 1, and ψ µ ∈ (0, 1). There exists a universal constant c > 0 such that Reg(T, π) ≥ c min T, T N ψ µ .The proof of Theorem 5.2 is deferred to Appendix C. This theorem establishes a lower bound on the regret, showing that no policy can achieve a better regret rate than Ω( √ N T ).Remark 5.3 The effect of the threshold µ in the upper bound appears only in logarithmic terms, suggesting that the regret increases with larger µ. In contrast, in the lower bound, ψ µ appears in the square root and the denominator, indicating that the regret decreases with larger µ. It is important to note that µ is determined by business conditions and is typically fixed. We conjecture that the upper bound is not tight concerning µ, indicating potential areas for future improvement in the analysis.6 Non-Thresholded Setting: The Patient LearnerIn this section, we modify our algorithm for environments that do not apply a threshold for delays.We refer to the seller in this setting as the patient learner. The patient learner is assumed to have knowledge of the expected delay. This assumption is consistent with existing literature (see e.g. Joulani et al. [2013] , Blanchet et al. [2024] ).We build our concentration result as follows:Lemma 6.1 With probability at least 1 -O(N -2 T -1 ) we have |v i,τ -v i | ≤ 48v i,τ log(N T ) |E i (τ )| + 48 log(N T ) |E i (τ )| + E [d s ] |E i (τ )| + 6E [d s ] log(N T ) |E i (τ )| .The proof is deferred to the Appendix. According to Lemma 6.1, we modify Algorithm 1 by changing∆ i,τ to ∆i,τ = 48v i,τ log(N T ) |E i (τ )| + 48 log(N T ) |E i (τ )| + E [d s ] |E i (τ )| + 6E [d s ] log(N T ) |E i (τ )| .We then state the regret result of the modified algorithm: Theorem 6.2 Let π P A-DEM BA be the policy produced by Algorithm 1 using ∆i,τ . π P A-DEM BA satisfies Reg(T,π P A-DEM BA ) ≤ log(T ) + K 48T log(N T ) + (K + 1)(48 + E [d s ] + 6E [d s ]) log 2 (N T ) + 72 N T log(N T ).Remark 6.3 In the non-thresholded setting, the term with ψ µ disappears since lim µ→∞ ψ µ = 1. This implies that the regret in this setting does not depend on ψ µ , providing a potentially tighter bound compared to the thresholded case. However, new terms involving E [d s ] are introduced. Asymptotically, both the thresholded and non-thresholded regret bounds simplify to Õ( √ N T ), with the differences primarily reflected in the constants, and both bounds approach the lower bound. Remark 6.4 Incorporating the skewness or variance of the delay distribution can improve the regret upper bound in practice, particularly in the non-thresholded setting. For instance, distributions with faster decay rates, such as Gaussian distributions, may lead to better regret performance compared to long-tail distributions. This would involve using techniques like Bernstein-type inequalities or making assumptions about tail behavior (e.g., sub-exponential tails). However, in the current analysis, we focus on the expectation of the delay, and further improvements based on skewness are left for future work. The asymptotic regret bound remains O( √ N T ), independent of skewness.  
experiments: 
 We conducted two sets of experiments to evaluate the performance of our algorithms. Our benchmark is an explore-then-exploit (EXP) algorithm, which explores by offering random assortments until a pre-specified time and then offers the optimized assortment based on the collected data. We tuned the exploration duration of the EXP algorithm and used the three best-performing durations in our comparisons.We used N = 10, K = 4 and p i = 1 for all i ∈ {1, . . . , N }. The attraction parameters were set as:v i = 0.25 + ϵ if i ∈ {1, 2, 9, 10} 0.25 otherwise,where ϵ represents the contrast between products. With this setting the optimal assortment is {1, 2, 9, 10}.In the first set of experiments, we tested our algorithm in two different delay settings: geometrically distributed and uniformly distributed delays. We set ϵ = 0.05 and used three cases in each distribution with increasing ψ µ values: E[d s ] = 500, µ = 100; E[d s ] = 100, µ = 100; and E[d s ] = 100, µ = 500. The results of this experiment are shown in Figure 1 . We observed that the DEMBA algorithm learns effectively and performs better than our benchmarks in all settings. Learning becomes more difficult as ψ µ decreases due to increased censorship and information loss from thresholding. With uniform delays, the learning is more challenging due to the heavy tail of the distribution. The gaps between DEMBA and the benchmarks increase with higher ψ µ , suggesting better utilization of information by DEMBA.In our second set of experiments, we tested how the contrast parameter ϵ affects learning and how the PA-DEMBA algorithm performs. We used geometric delays with E[d s ] = 100 and µ = 100 for the first experiment and E[d s ] = 100 for the second experiment. The results are shown in Figure 2 . On the left-hand side, we observe that when the number of rounds is low (and thus the amount of learning is limited), lower contrast values lead to better results. As the number of rounds (and therefore the amount of learning) increases, as expected, higher contrast simplifies the learning problem, as indicated by lower regret curves. Furthermore, on ther right hand side, the PA-DEMBA algorithm demonstrated robust performance, effectively managing the challenges posed by the non-thresholded setting. Results are averaged over 100 independent runs.In our third set of experiments, we compare DEMBA algorithm and EXP benchmarks with MNL-Bandit algorihm from Agrawal et al. [2019] . While MNL-Bandit learns customer preferences similarly to DEMBA, it does not account for potential delays in the feedback. In this experiment, we considered µ = 500 and we applied a geometric delay distribution with no delay, E[d s ] = 50 and E[d s ] = 100. We observed that when there is no delay, the performance of MNL-Bandit and DEMBA is almost identical. However, as the delay increases, the performance of MNL-Bandit deteriorates, clearly indicating that it fails to handle delayed feedback. 
conclusion: 
 This work provides the first solution and analysis for delayed choice modeling and online assortment optimization. We introduced two novel algorithms, DEMBA for thresholded feedback settings and PA-DEMBA for non-thresholded settings, demonstrating their effectiveness through theoretical guarantees and comprehensive experiments. Our algorithms address the dual challenges of unknown Multinomial Logit (MNL) parameters and delayed feedback, achieving sub-linear regret bounds.Lastly, we discuss future work. Our lower bound suggest an improvement on regret by considering the delay distribution via ψ µ . This would require learning the delay distribution itself, adding more complexity. Moreover, it could be interesting to explore scenarios where no-purchase decisions are indistinguishable from delayed purchases, such as settings where tracking no purchases is not possible. Additionally, it would be worthwhile to consider multi-level choice settings where customer preferences and rewards are revealed to the seller in multiple stages with delays between each stage.A Proof of Lemma 4.1We begin by providing an instrumental theorem that will be useful to establish concentration results.Theorem A.1 (Theorem 5 of Agrawal et al. [2019] ) Consider n i.i.d. geometric random variables X 1 , . . . , X n with parameter p, i.e. for any iP(X i = m) = (1 -p) m p ∀m = {0, 1, 2, . . . },and let µ = E(X i ) = 1-p p ≤ 1 and X = 1 n n i=1 X i . For any ζ > 0, we haveP( X > (1 + ζ)µ) ≤ exp - nµζ 2 2(1 + ζ)(1 + µ) 2 .We now provide the proof of Lemma 4.1 that is crucial for our subsequent analysis.Proof of Lemma 4.1. Note that vi,τ is a biased estimator and defined asvi,τ = ṽi,τ |E τ (i)| = t end τ s=1 o i,s,t end τ |E τ (i)| ,where |E τ (i)| is the total number of epochs that product i is shown to the customer andt end τ s=1 o i,s,t end τis the total observed sales of product i ̸ = 0d or is the total observed delayed no selections.Let t be the current period, i.e. t = t end τ + 1. We haveEQUATIONwhere the second equality follows from the decomposition of old observations before the threshold and recent observations, the third equality is rearrangement of the values and the last inequality follows from triangle inequality.For the first element of (5), we havet-1 s=1 a i,s I(d s ≤ µ) |E τ (i)| -ψ µ v i = t-1 s=1 a i,s I(d s ≤ µ) |E τ (i)| - ψ µ t-1 s=1 a i,s |E τ (i)| + ψ µ t-1 s=1 a i,s |E τ (i)| -ψ µ v i ≤ t-1 s=1 a i,s I(d s ≤ µ) |E τ (i)| - ψ µ t-1 s=1 a i,s |E τ (i)| + ψ µ t-1 s=1 a i,s |E τ (i)| -ψ µ v i ≤ (a) t-1 s=1 I(d s ≤ µ) |E τ (i)| -ψ µ + (b) t-1 s=1 a i,s |E τ (i)| -v i (6)We haveEQUATIONby Hoeffding's inequality.For part (b), we make use of the Chernoff bound from Theorem A.1 in two cases according toζ = (v i + 1) 6 log(N T ) vi|Eτ (i)| .Case 1 ζ ≤ 1 2 : We have from Theorem A.1P t-1 s=1 a i,s |E τ (i)| -v i > ζv i ≤ 1 N 2 T 2 , P t-1 s=1 a i,s |E τ (i)| -v i < -ζv i ≤ 1 N 2 T 2 , P t-1 s=1 a i,s |E τ (i)| -v i > (v i + 1) 6v i log(N T ) |E τ (i)| ≤ 2 N 2 T 2 .Therefore, we haveEQUATION)We shall generalize the result at 8 in two cases for substituting v i with vi,τ in the concentration radius and upper bounding the new bound utilizing v i .For vi,τ , we haveP(v i,τ -v i < -v i 1 2 ) ≤ 1 N 2 T 2 , hence, P(2v i,τ ≤ v i ) ≤ 1 N 2 T 2 .Combining this with 8, we getEQUATION)For upper bounding 9 using v i , we haveP(v i,τ -v i > v i 1 2 ) ≤ 1 N 2 T 2 , hence P( 3v i 2 ≤ vi,τ ) ≤ 1 N 2 T 2 .Therefore, we concludeEQUATION) Case 2 ζ > 1 2 : We have 2ζ 2 ≥ 1 2 . Let ζ ′ = 2ζ 2 .We have by Theorem A.1P t-1 s=1 a i,s |E τ (i)| -v i > ζ ′ v i ≤ exp - |E τ (i)|v i ζ ′2 2(1 + ζ ′ )(1 + v i ) 2 ≤ exp - |E τ (i)|v i ζ ′ 6(1 + v i ) 2 ,substituting the value of ζ ′ , we getP t-1 s=1 a i,s |E τ (i)| -v i > 48 log(N T ) |E τ (i)| ≤ 1 N 2 T 2 .(11)Combining 9 and 11, and applying union bound we haveP t-1 s=1 a i,s |E τ (i)| -v i ≤ 48v i,τ log(N T ) |E τ (i)| + 48 log(N T ) |E τ (i)| ≥ 1 - 4 N 2 T .Additionally, combining 9, 10 and 11, and applying union bound we haveEQUATION)We can bound the second element of (1) asEQUATION)Combining ( 7), ( 12) and ( 14) gives the result.Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: Information provided in appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes]Justification: [NA] Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: the paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: B Proof of Theorem 5.1We begin with establishing a key result that will be instrumental in our main proof.Lemma B.1 Let S * represent the optimal assortment when the MNL parameters are given by v. Also, let S τ denote the assortment applied by the policy at epoch τ . For any parameter set w distinct from v the following hold.i. If v i ≤ w i for all i ∈ 1, . . . , N , and v 0d ≥ w 0d , then R(S * ; w) ≥ R(S * ; v).ii. If v i ≤ w i for all i ∈ 1, . . . , N , andv 0d = w 0d , then R(S τ ; w) -R(S τ ; v) ≤ i∈Se (wi-vi) 1+v 0d + j∈Se vj .Proof of Lemma B.1. Note that the proof of Part i. mostly resembles Lemma A.3 in Agrawal et al.[2019], and we write the whole proof here for being self-contained.Proof of Part i. Let v j be identical to v except for the j th element, which is increased to w j . We aim to show that for any j ∈ S * , if v j is increased to w j , then R(S * ; v j ) ≥ R(S * ; v). This suffices to prove R(S * ; w) ≥ R(S * ; v).Define T := i∈S * \j r i v i and V := 1 + i∈S * \j v i . If there exists a j ∈ S * such that r j < R(S * ), removing product j from the assortment yields higher expected revenue, contradicting the optimality of S * . Therefore, we haver j ≥ R(S * ; v) = i∈S * r i v i 1 + i∈S * v i = i∈S * \j r i v i + r j v j 1 + i∈S * \j v i + v j = T + r j v j V + v j .for all j ∈ S * . Rearranging terms, we getEQUATION)To have R(S * ; v j ) ≥ R(S * ; v), we need to show thatT + r j w j V + w j ≥ T + r j v j V + v j ,which is equivalent toT v j + r j V w j ≥ T w j + r j V v j .Rearranging terms, we getr j V (w j -v j ) ≥ T (w j -v j ),which holds thanks to (15). Moreover, the case for i = 0d holds trivially which concludes our proof.Proof of Part ii. We haveR(S τ ; w) -R(S τ ; v) = i∈Se r i w i 1 + v 0d + j∈Se w j - i∈Se r i v i 1 + v 0d + j∈Se v j ≤ i∈Se r i w i 1 + v 0d + j∈Se w j - i∈Se r i v i 1 + v 0d + j∈Se w j = i∈Se r i (w i -v i ) 1 + v 0d + j∈Se w j ≤ i∈Se (w i -v i ) 1 + v 0d + j∈Se v j ,where the second inequality follows fromr i ≤ 1, ∀i ∈ [N ].□ Now, we provide the proof of Theorem 5.1.Proof of Theorem 5.1. We haveEQUATIONwhere the first inequality holds thanks to the definition of S τ and the second inequality follows from Lemma B.1 with probability at least 1 -O(N -1 T -1 ).We haveReg(T, π) = E τ τ =1 |H τ | (R(S * ; ψ µ v) -R(S τ ; ψ µ v)) ,where H τ is the duration of epoch τ and|H τ | ∼ Geom( 1 1+ψµv 0d + j∈Sτ ψµvj ), then E[|H τ | | S τ ] = 1 + ψ µ v 0d + j∈Sτ ψ µ v j .Since S τ is determined by the history of policy(F τ -1 ), we haveE[|H τ | | F τ -1 ] = 1 + ψ µ v 0d + j∈Sτ ψ µ v j . Therefore the regret is equal to Reg(T, π) = E τ τ =1 E [|H τ | (R(S * ; ψ µ v) -R(S τ ; ψ µ v)) | F τ -1 ] ,and by the law of total expectationsReg(T, π) = E   τ τ =1   1 + ψ µ v 0d + j∈Sτ ψ µ v j   (R(S * ; ψ µ v) -R(S τ ; ψ µ v))   .Let the epoch based regret be ∆R τ , we can write it as∆R τ =   1 + ψ µ v 0d + j∈Sτ ψ µ v j   (R(S * ; ψ µ v) -R(S τ ; ψ µ v)) ,then the regret can be written in the form ofReg(T, π) = E τ τ =1 ∆R τ .We define event E, for all τ asE τ := N i=1 {|v i,τ -ψ µ v i | > ∆ τ } ∪ |ψ µ v 0d -v 0d,τ | > ∆ τ .The event E τ is a low probability event. We will analyze the regret according to the event separately:E[∆R τ ] = E ∆R τ I(E τ -1 ) + ∆R τ I(E C τ -1 ) .We have ∆R τ ≤ N + 1 and henceE[∆R τ ] ≤ (N + 1)P(E τ -1 ) + E ∆R τ I(E C τ -1 ) .We have by ( 16) thatE[∆R τ ] ≤ (N + 1)P(E τ -1 ) + E     1 + ψ µ v 0d + j∈Sτ ψ µ v j   (R τ (S τ ; vτ ) -R(S τ ; ψ µ v)) I(E C τ -1 )   .Then, by Lemma B.1 we have  1 + ψ µ v 0d + j∈Sτ ψ µ v j   R(S τ ; vτ ) -R(S τ ; ψ µ v) I(E C τ -1 ) ≤   1 + ψ µ v 0d + j∈Sτ ψ µ v j   R(S τ ; vτ ) -R(S τ ; ψ µ v) =   1 + ψ µ v 0d + j∈Sτ ψ µ v j   i∈Sτ r i vi,τ 1 + v 0d + j∈Sτ v j - i∈Sτ r i vi,τ 1 + ψ µ v 0d + j∈Sτ v j + i∈Sτ r i vi,τ 1 + ψ µ v 0d + j∈Sτ v j - i∈Sτ r i ψ µ v i 1 + ψ µ v 0d + j∈Sτ ψ µ v j ≤   1 + ψ µ v 0d + j∈Sτ ψ µ v j   i∈Sτ r i vi,τ (ψ µ v 0d -v 0d ) 1 + v 0d + j∈Sτ v j 1 + ψ µ v 0d + j∈Sτ v j + i∈Sτ r i (v i,τ -ψ µ v i ) 1 + ψ µ v 0d + j∈Sτ v j ≤   1 + ψ µ v 0d + j∈Sτ ψ µ v j   K(ψ µ v 0d -v 0d ) 1 + v 0d + j∈Sτ v j 1 + ψ µ v 0d + j∈Sτ v j + i∈Sτ (v i,τ -ψ µ v i ) 1 + ψ µ v 0d + j∈Sτ v j ≤   1 + ψ µ v 0d + j∈Sτ ψ µ v j   K(ψ µ v 0d -v 0d ) 1 + ψ µ v 0d + j∈Sτ ψ µ v j + i∈Sτ (v i,τ -ψ µ v i ) 1 + ψ µ v 0d + j∈Sτ ψ µ v j = K(ψ µ v 0d -v 0d ) + i∈Sτ (v i,τ -ψ µ v i,τ ).Let E i be the number of periods that the product i is offered. Then, the regret can be written asReg(T, π) ≤ E τ τ =1 (N + 1)P(E τ -1 ) + K∆ 0d,τ + i∈Sτ ∆ i,τ ≤ E τ τ =1 N + 1 N T 2 + K (72v 0d + 1) log(N T ) τ + 48K(log(N T ) + µ) τ + i∈Sτ (72v i + 1) log(N T ) |E τ (i)| + 48 log(N T ) + µ |E τ (i)| ≤ log(T ) + K 73T log(N T ) + 48K log(T )(log(N T ) + µ) + 73E N i=1 v i E i log(N T ) + 48 log 2 (N T ) + µ log(T ) ≤ log(T ) + K 73T log(N T ) + 48K log(T )(log(N T ) + µ) + 73 N i=1 v i E[E i ] log(N T ) + 48 log 2 (N T ) + µ log(T ),where the third inequality holds due to τ ≤ T , E i ≤ T and the fourth inequality holds due to Jensen's inequality.Since,N i=1 v i E[E i ] ≤ T , we conclude Reg(T, π) ≤ log(T ) + K 73T log(N T ) + 48K log(T )(log(N T ) + µ) + 73 N T log(N T ) + 48 log 2 (N T ) + µ log(T ). □ C Proof of Theorem 5.2Before giving the proof of Theorem 5.2, we first give an instrumental Lemma in the main proof and its proof.Lemma C.1 Let P and Q be categorical distributions with P P (X = i) = p i and P Q (X = i) = q i where p i = q i + ϵ i for all i = 1, . . . , I. Also, let the selected option be observed with bias ψ µ . The Kullback-Leibler divergence between P and Q, denoted by D KL (P ∥ Q), is given byD KL (P ∥ Q) = I i=0 ψ µ ϵ 2 i q i .Proof of Lemma C.1. We haveD KL (P ∥ Q) = I i=0 ψ µ (q i + ϵ i ) log ψ µ (q i + ϵ i ) ψ µ q i ≤ I i=0 ψ µ (q i + ϵ i ) ϵ i q i = I i=0 ψ µ ϵ 2 i q i ,where the inequality follows since log(1 + x) ≤ x for any x > -1 and the last equality holds sinceI i=0 ϵ i = 0. □ Proof of Theorem 5.2. We set p i = 1 for all i ∈ [N ]. Let S be a subset of N with |S| = K. For attraction parameters, we set v 0 = 1, v 0d arbitrary in [0, 1], v i = (1 + ϵ)/K for i ∈ S and v i = 1/K otherwise.We denote all subsets of product set [N ] of size K as S K . We havemax S∈S K R(S) = R(S * ) = 1 + ϵ 2 + v 0d + ϵ .We employ the neighboring argument for assortment sets as described in Chen and Wang [2018] . For any arbitrary assortment S t , we haveR(S t ) = 1 + (1 -δ)ϵ 2 + v 0d + (1 -δ)ϵ ,where δ is a measure of discrepancy from the optimal set S, i.e. δ := 1 -|St∩S| K . Then, we haveR(S * ) -R(S t ) = 1 + ϵ 2 + v 0d + ϵ - 1 + (1 -δ)ϵ 2 + v 0d + (1 -δ)ϵ = δϵ + δϵv 0d (2 + v 0d + ϵ)(2 + v 0d + (1 -δ)ϵ) ≥ δϵ (1 + v 0d ) 16 .For any arbitrary subsetEQUATION≥ maxEQUATIONEQUATIONEQUATIONK-1 be all subsets of [N ] of size K -1 that do not include i. We haveEQUATIONWe define probability measures P and Q through parameterizations S ′ and S ′ ∪ {i} respectively. We denote Total Variation(TV) distance between two probability measures as T V (P, Q) := sup A |P (A) -Q(A)| and Kullback-Leibler (KL) divergence as D KL (P ∥ Q). We have 0 ≤ Ñi ≤ T andEQUATIONwhere the last inequality follows from Pinsker's Inequality.We use ( 23) in ( 22) and we getEQUATIONFor the first element of (24), we haveEQUATIONwhere the last inequality follows from K ≤ N/4.For the second element of (24), we have thatEQUATIONEQUATION≤ maxEQUATIONwhere the first inequality is due to Hölder's inequality and the second inequality follows from Jansen's inequality.We haveD KL (P S ′ (•|S t ) ∥ P S ′ ∪{i} (•|S t )) = 0 for i / ∈ S t . For analyzing i ∈ S t , we define K ′ = |S t | ≤ K, J := |S t ∩ S ′ | ≤ K -1 and a = 1 + v 0d + K ′ K . We have |p 0 -q 0 | = 1 a + Jϵ/K - 1 a + (J + 1)ϵ/K = ϵ K(a 2 + aJϵ/K + a(J + 1)ϵ/K + J(J + 1)ϵ 2 /K 2 ) ≤ ϵ K ; |p 0d -q 0d | = v 0d 1 a + Jϵ/K - 1 a + (J + 1)ϵ/K = v 0d ϵ K(a 2 + aJϵ/K + a(J + 1)ϵ/K + J(J + 1)ϵ 2 /K 2 ) ≤ v 0d ϵ K ; |p j -q j | ≤ 1 + ϵ K 1 a + Jϵ/K - 1 a + (J + 1)ϵ/K = ϵ + ϵ 2 K 2 (a 2 + aJϵ/K + a(J + 1)ϵ/K + J(J + 1)ϵ 2 /K 2 ) ≤ 2ϵ K 2 for 1 ≤ j ≤ N and j ̸ = i;and|p i -q i | ≤ 1 K 1 a + Jϵ/K - 1 a + (J + 1)ϵ/K + ϵ K 1 a + Jϵ/K ≤ ϵ K 2 + ϵ K ≤ 2ϵ K .We also haveEQUATIONq j = 1 + ϵ K(a + (J + 1)ϵ/K) ≥ 1 + ϵ 4K ≥ 1 4K .Using these with Lemma C.1, we getD KL (P S ′ (•|S t ) ∥ P S ′ ∪{i} (•|S t )) ≤ ψ µ 4ϵ 2 K 2 + 4v 2 0d ϵ 2 K 2 + 4K • J • 4ϵ 2 K 4 + 4K • 4ϵ 2 K 2 ≤ ψ µ 8ϵ 2 K 2 + 16ϵ 2 1 K 2 + 16ϵ 2 1 K ≤ 40ψ µ ϵ 2 1 K .Integrating this into (33), we obtain maxEQUATION≤ maxEQUATIONFor the final bound, we haveEQUATIONwhere (38) follows from ( 21), (39) follows from ( 29) and (37).Setting ϵ 1 = min{ N/ψ µ T , 0.5} gives the final bound.□ D Proof of Theorem 6.2We first provide an instrumental theorem that we will use to establish concentration results.Theorem D.1 (Theorem 4.4 of Mitzenmacher and Upfal [2017] ) Let X 1 , . . . , X n be independent Poisson trials such that P(X i = 1) = p i . Let X = n i=1 X i . Then, for 0 < δ < 1:P(X ≥ (1 + δ)E[X]) ≤ exp(-E[X]δ 2 /3).Proof of Lemma 6.1.We haveEQUATION)The derivation of the bound for the first element of (41) parallels that of Lemma 4.1, thus, we omit the analysis, yieldingEQUATIONwith probability at least 1 -4 N 2 T . For the second element of (41), we first bound the expected number of unobserved feedback until time t. We haveEQUATIONThen, we haveEQUATIONEQUATIONwhere the first inequality follows by Theorem D.1 with probability at least 1 -1 N 2 T 2 by setting δ = 6 log(N T )and the second inequality follows from 43.Combining 42 and 47 gives the result.Proof of Theorem 6.2.We will proceed similarly to the proof of Theorem 5.1, but we provide a complete proof here for clarity and completeness.We haveEQUATIONwhere the first inequality holds thanks to the definition of S τ and the second inequality follows from Lemma B.1 with probability at least 1 -O(N -1 T -1 ).Similar to the proof of Theorem 5.1, we can writeReg(T, π) = E   τ τ =1   1 + v 0d + j∈Sτ v j   (R(S * ; v) -R(S τ ; v))   .And defining the epoch based regret be ∆R τ , we can write it as∆R τ =   1 + v 0d + j∈Sτ v j   (R(S * ; v) -R(S τ ; v)) , which will lead to Reg(T, π) = E τ τ =1 ∆R τ .We define event E, for all τ asE τ := N i=1 {|v i,τ -v i | > ∆ τ } ∪ |v 0d -v 0d,τ | > ∆ τ .Conditioning on the event and by ( 48), we can writeE[∆R τ ] ≤ (N + 1)P(E τ -1 ) + E     1 + v 0d + j∈Sτ v j   (R τ (S τ ; vτ ) -R(S τ ; v)) I(E C τ -1 )   .Then, by Lemma B.1 we have  1 + v 0d + j∈Sτ v j   R(S τ ; vτ ) -R(S τ ; v) I(E C τ -1 ) ≤   1 + v 0d + j∈Sτ v j   R(S τ ; vτ ) -R(S τ ; v) =   1 + v 0d + j∈Sτ v j   i∈Sτ r i vi,τ 1 + v 0d + j∈Sτ v j - i∈Sτ r i vi,τ 1 + v 0d + j∈Sτ v j + i∈Sτ r i vi,τ 1 + v 0d + j∈Sτ v j - i∈Sτ r i v i 1 + v 0d + j∈Sτ v j ≤   1 + v 0d + j∈Sτ v j   i∈Sτ r i vi,τ (v 0d -v 0d ) 1 + v 0d + j∈Sτ v j 1 + v 0d + j∈Sτ v j + i∈Sτ r i (v i,τ -v i ) 1 + v 0d + j∈Sτ v j ≤   1 + v 0d + j∈Sτ v j   K(v 0d -v 0d ) 1 + v 0d + j∈Sτ v j 1 + v 0d + j∈Sτ v j + i∈Sτ (v i,τ -v i ) 1 + v 0d + j∈Sτ v j ≤   1 + v 0d + j∈Sτ v j   K(v 0d -v 0d ) 1 + v 0d + j∈Sτ v j + i∈Sτ (v i,τ -v i ) 1 + v 0d + j∈Sτ v j = K(v 0d -v 0d ) + i∈Sτ (v i,τ -v i,τ ).Let E i be the number of periods that the product i is offered. Then, the regret can be written asReg(T, π) ≤ E τ τ =1 (N + 1)P(E τ -1 ) + K ∆0d,τ + i∈Sτ ∆i,τ ≤ E τ τ =1 N + 1 N T 2 + K 48v i,τ log(N T ) |E τ (i)| + 48K log(N T ) |E τ (i)| + KE [d s ] |E i (τ )| + 6E [d s ] log(N T ) |E i (τ )| + i∈Sτ 48v i,τ log(N T ) |E τ (i)| + 48 log(N T ) |E τ (i)| + E [d s ] |E i (τ )| + 6E [d s ] log(N T ) |E i (τ )| ≤ log(T ) + K 48T log(N T ) + K(48 + E [d s ] + 6E [d s ]) log 2 (N T ) + 72E N i=1 v i E i log(N T ) + (48 + E[d s ] + 6E [d s ]) log 2 (N T ) ≤ log(T ) + K 48T log(N T ) + (K + 1)(48 + E [d s ] + 6E [d s ]) log 2 (N T ) + 72 N i=1 v i E[E i ] log(N T ),where the third inequality holds due to τ ≤ T , E i ≤ T and the fourth inequality holds due to Jensen's inequality.Since,N i=1 v i E[E i ] ≤ T , we conclude Reg(T, π) ≤ log(T ) + K 48T log(N T ) + (K + 1)(48 + E [d s ] + 6E [d s ]) log 2 (N T ) + 72 N T log(N T ).We numerically evaluate our algorithms over 100 independently generated problem instances, with error bars representing standard errors in both Figure 1 and Figure 2 .The simulations were conducted on a server equipped with 4 Intel Xeon 6248 2.5GHz CPUs and 377 GB of RAM, running CentOS 7. The simulation code was developed in Python version 3.9.6.Justification: There is no societal impact of the work performed. The main application of the presented work is theoretical for sequential decision making.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: There was unanimity in the fact that the problem studied by the authors is of broad interest to the NeurIPS community. Some reservations were expressed during the reviewing period, but after the discussions, no reviewers lamented that the authors were not able to address their major criticisms convincingly.
	Given the broad appeal of the topic and the overall positive opinions of the reviewers (which I also share), I recommend acceptance (poster) under the condition that the authors commit to incorporating all requested clarifications in the revised version.

Reviews: review: paper_summary: paper_summary: The paper considers on online learning problem in the setting of discrete choice models with delayed feedback. The paper assumes a multinomial logit model where a decision maker has some (unknown) valuation v_i for item i. When presented with a menu S of choices, the agent chooses a single item from S such that the probability of selecting item i is proportional to v_i. In the online learning setup, at each time step t, the learner offers an assortment (menu) S_t and then agent chooses one item from the assortment. The paper considers a setup with delayed feedback, where the feedback regarding which item was chosen is delayed (according to an unknown distribution).

The paper considers two settings - (i) with censorship - where feedback delayed by more than some fixed deadline \mu is censored, and (ii) without censorship - where feedback can be delayed indefinitely (but expected delay is known to the learner). In both settings, the paper presents algorithms that obtain almost best possible regret \tilde O(NT) where N is the total number of items and T is the time horizon.
The algorithms are based on UCB and perform learning in epochs - i.e. offer the same assortment at all time steps throughout an epoch in order to reduce variance. An epoch is determined by times when the learner receives explicit negative feedback, i.e., the agent did not pick any item from the assortment.
strength_weakness: strength_weakness: - I found the comparison with prior work a bit lacking. Since I am not directly familiar with works in this area, I would have appreciated more details about how the paper differs from prior work. In particular, Online learning with MNL choice models (but no delayed feedback) admits UCB based algorithms [Agrawal et al]. How much does the current work differ from that work? What additional technical complications are introduced by delayed feedback? Are they different from the challenges introduced by delayed feedback in other online learning settings (say classic MAB)?
questions: questions: See above.
limitations: limitations: N/A
paper_summary: paper_summary: This paper works under the MNL bandit settings where the environment feedback is delayed, motivated by real-world application scenarios like e-commerce platforms, while balancing exploitation and exploration. For the two proposed algorithms, the authors provide corresponding theoretical analysis, resulting in regret upper and lower bounds. Experiments are also conducted to show the effectiveness.

Pros:

- The paper is generally well-organized with clear narratives and derivations. Indeed, delayed feedback is an important characteristic for modern recommender systems where users can remain neutral before disclosing their final preference towards recommendations.

- From my personal perspective, the theoretical analysis pipeline is novel, and the results look decent, with both the regret upper bound and lower bound presented.

Cons and questions:

- One question from my side is that for the current theoretical analysis, the regret bound mainly depends on the expectation of the delay, without modeling the skewness of the delay distribution $f_d$. In this case, I am wondering what the regret bound would look like if we take the skewness/variance of the distribution into account. For example, with $f_d$ being Gaussian, how will the variance interact with the final regret upper bound/lower bound? Is it possible to achieve a tighter regret bound when the distribution is decaying super fast compared to that of a long-tail distribution?

- Although the contribution of this paper mainly lies in the theoretical analysis perspective, it would be better if the authors could include more algorithms for comparison in their experiments. Some MNL bandit baselines from the related works section would be good.
strength_weakness: strength_weakness: Please see my comments above.
questions: questions: Please see my comments above.
limitations: limitations: Please see my comments above.
paper_summary: paper_summary: The authors studied the problem of learning with delated feedback under the Multinominal Logit model. Prior work in bandits with delayed feedback does not accommodate settings where multiple items can be offered simultaneously. The authors instead proposed two algorithms: DEMBA for thresholded setting where the seller discarded delay longer than a certain threshold, and PA-DEMBA when the threshold is infinity (when all delayed feedback are considered). Both algorithms achieve $O(\sqrt{NT})$ regret bound, and the authors provided matching lower bound up to a log term. Finally, the authors provided a set of numerical experiments to support their theoretical findings.
strength_weakness: strength_weakness: - The analysis did not attempt to learn the unknown delay distribution.
questions: questions: - Does the problem setup change dramatically when the reward for each item in the assortment are not drawn i.i.d. For example, if the position of the item is correlated with the reward such that items put first in the list yields higher reward (or lower cost of browsing), does the current analysis still hold?
limitations: limitations: The authors have addressed the limitations of this work.
paper_summary: paper_summary: The authors consider the setting in which a business is required to select a set of options to a customer in order to maximize the generated revenue. This task is challenging as the options presented to a customer may interact with each other and alter the choice of the customer, and the feedback on the choice of the customer could be received by the business after a considerable delay. This class of tasks can be addressed in literature using Multinomial choice (MNL) models. The authors aim to address two challenges that arise in this scenario, namely the unknown MNL parameters and the delayed feedback. The authors consider two settings, *threshold* and *non-threshold*, and propose two algorithms to address them, DEMBA and PA-DEMBA, respectively.
strength_weakness: strength_weakness: W1) The definition of the "feedback observed by the seller", $o_{i,s,t}$ is inconsistent and seems also incorrect. At line 148, it is defined as:
$$
o_{i,s,t} = c_{i,s,t} a_{i,t},
$$
whereas in the proof sketch of Lemma 4.1 it is used as $o_{i,s,t} = c_{i,s,t} a_{i,s}$.
Both definitions seem to be incorrect, as in the first case (i.e., with $a_{i,t}$), $o_{i,s,t}$ evaluates to 1 considering the option chosen by the consumer at round $t$ instead of round $s$, in which the product was sold.
In the second case (i.e., with $a_{i,s}$), this issue is solve however the definition of $c_{i,s,t}$ makes it so that $o_{i,s,t}$ would evaluate to 1 at every round $t \ge d_s + s$ (under the condition that $d_s \le \mu$), potentially causing a choice of the consumer to count more than once towards the estimation of the preference.

W2) The proof sketch of Lemma 4.1 at line 188 (and in the appendix) seems to contain an error, as the conditions of $c_{i,s,t}$, which in the definition are in a logical AND, are split using a summation, which seems to be incorrect, and could invalidate all the subsequent steps of the proof.

W3) The observation that "each alternative can act as a substitute or competitors to others, impacting the customer's final decision" stated in Section 1 would have been better represented in the problem formulation with attraction parameters that depend on the options in the proposed set. Indeed, the provided formulation of the customer choice probabilities works fine, but cannot comprehensively capture product substitution dynamics.
questions: questions: The reviewer would like the authors to address the reported weaknesses, and to respond to the following questions:

Q1) Can the authors provide a formal proof of the first passage of the proof of Lemma 4.1 at line 184:
$$\frac{ \sum_{\tau \in E_{\tau} (i) } \tilde{v}\_{i, \tau}}{| E_{\tau} (i) |} = \frac{\sum_{s=1}^{t_{\tau}^{end}} o_{i,s,t_{\tau}^{end}}}{| E_{\tau} (i) |},$$
as it is simply stated as a trivial definition however by applying the definition of $\tilde{v}_{i, \tau}$ it does not seem to be correct, considering also the remarks of W1).

Q2) Can the authors clarify how the epochs are defined?

Q3) Why have the authors not considered any of the algorithms reported in Section 2 in the experimental evaluation of the proposed algorithms?
limitations: limitations: No limitations
paper_summary: paper_summary: The paper studies a task of learning MNL parameters with delayed feedback. The authors study both the cases where feedback with extremely high delay is ignored or taken into account as well. They prove that for both settings the optimal regret is $\tilde{\Theta}(\sqrt{NT})$ where $T$ is the horizon and $N$ is the number of products. They also conducted experiments that support their theoretical findings.
strength_weakness: strength_weakness: 1) I think that the main results could have been better presented. In the current formulation, it seems like there is no difference between the guarantees of DEMBA and PA-DEMBA, which makes the reader wonder why do we need both of them. It also makes it hard to understand what improvements can we hope to achieve in future work.
2) The setup seems kind of specific to this problem. It could have been interesting to know if one can define it more generally, and still use the same or similar solutions. This could have help the reader to conjecture if the same techniques may be used to solve other variations of the problem.
questions: questions: Questions:
1) What is $\mathcal{S}$ in algorithm 1? The set of all assortments of size at most K?
2) $K$ is not mentioned in the upper bounds. They hold for all K?
3) What is the tradeoff between DEMBA and PA-DEMBA? The guarantees mentioned in Theorems 5.1 and 6.2 are identical.
4) In line 288, I am not sure how you reached the conclusion that "Our lower bound suggest an improvement on regret by considering the delay distribution via $\psi_\mu$." (there is also a typo here: suggest --> suggests). I don't understand how can a lower bound suggest an improvement to the upper bound. For example, $\Omega(1)$ is also a valid lower bound.

Suggestions:
1) The guarantees written in Theorems 5.1, 6.2 are identical. Consider showing the factors who make a difference between the results. 
2) I think that the introduction is a bit lack of justifications or examples. For example, in line 23, you write "fall short in scenarios....". Why? Is there a line of work showing this?
3) A minor suggestion: In line 237, it is not clear why to use $\tilde{O}(\cdot)$ in this context. First, the lower bound has no logarithm factors in it so there's no point in concealing them. Second, $O(\sqrt{NT})$ can also be O(1), which is not the point of the lower bound. Therefore, I suggest writing "...better regret than $\Omega(\sqrt{NT})$".

Typos:
1) line 181: "at least at least".
2) Theorem 5.1: Add "Then" before "$\pi^{DEMBA}$".
limitations: limitations: Yes.

Comments: title: Thank you for the response
comment: I would like to thank authors for your explanations. I will keep my current positive evaluation of your manuscript.
Thank you very much for addressing my comments and questions.