Online Learning of Delayed Choices
Authors: Recep Yusuf Bekci
Venue: NeurIPS 2024 poster (2024)
Keywords: choice models
multinomial logit
delayed feedback
Primary area: online_learning

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.

Online Learning of Delayed Choices
Recep Yusuf Bekci University of Waterloo Waterloo, Canada recep. wewp:ebbkciiaeaeeee bereppbbekciuuuttrloooo.oo ca
Abstract
Choice models are essential for understanding decision- making processes in do- mains like online advertising, product recommendations, and assortment optimiza- tion. The Multinomial Logit (MNL) model particularly versatile in selecting products or advertisements for display. However, challenges arise with unknown MNL parametees and delayed feedback, requiring sellers to learn eustomers' 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 threshold for considering feedback is imposed by business requirements. Our algorithm demonstrates ((VNT) regret, with matching lower bound up logarithmic term. Furthermore, we extend our analysis to environments with non-thresholded delays, achieving a ((VNT) regret. To validate our approach, we conduct experiments that confirm the effectiveness of our algorithm.
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 consumers to maximize engagement and revenue. However, the task of optimizing what content or products are shown customer during their browsing session complex due 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-makin problems, fall short in scenarios where a subset of alternatives must be presented, and the customer's s choice among these influences future decisions.
Multinomial choice (MNL) models have emerged as powerful tools for capturing and predicting consumer behavior among finite of alternatives. These models estimate the utilities of different options and the probabilities of their selection. However, when the MNL parameters are unknown and historical data is available-as is often the case with newly introduced products advertise- ments-the learning process becomes even more challenging. This complexity is further exacerbated when the feedback on decisions 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 e-commerce environments often take hours even days make decisions, highlighted by Vernade et al. (220) and CCapelle 20144.. 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.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 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 handle potentially censored delayed feedback effectively.
In contrast, non- non-thresee 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, 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 comprehensive regret analysis for both DEMBA and PA-DEMBA, demonstrating an O(VNT) regret bound and 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 this paper is organized as follows. In Section 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 In Section 7 conduct experiments to demonstrate the effecttieneess of our proposed algorithms. Finally, Section concludes the paper and outlines potential directions for future research.
presented in Section 6
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, Joulami et al. [2013] studied online learning scenarios with stochastic delayed feedback. Their work laid the foundation for understanding how delays impact learning performance. Similarly, Chapeele [2014) examined delayed conversions in display advertising, highlighting the practical challenges faced in real-world applications. Further, Vernade et al. (0077] 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 anony- mous feedback, which adds another layer of complexity by considering multiple types of delays. Zhou et al. [2099] extended this exploration to generalized linear contextual bandits with delayed feedback. Vernade et al. [2020] investigated linear bandits with stochastic thresholded delays. Ad- ditionally, 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 con-stochastic bandits, further enriching the literature on delayed feedback mechanisms, Tang et al.) [2024] studied delayed multi-armed bandits (MAB) with rewerd-de delays in clinical trials, while Lancewicki et al.
2021 explored both peeeddddeeendent and inwred-indeeendent delay settings. Flaspohler et al.
2021 investigated delayed learning in weather forecasting, and Grover et al. [2088 addressed the
best arm identification problem with delayed feedback. (Thune et al. 2019) examined non-stochastic
MABs with unrestricted delays, and
al. [0166] considered cooperation between

---

different agents in delayed settings. Tang et al. [021 explored scenarios where past actions impact future arm rewards, and Yang et al. 2024] addressed general sequential decision-mane 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 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 simultancously. present 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 al. [017]] developed Thompson sampling algorithm
for learning MNL parameters for assortment optimization, while [Agraaal et al. [2019] proposed
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 multiple pulls, which is a generalization of the dueling bandits problem. Other notable works include Wang et al. (20188 and Chen et al. [202]]. who worked on dynamic assortment allocation under uncapacitated MNL models, and Perivier and Goyal 20222 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 (PADDEMA) algorithm for mon-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.
3 Problem Setup
We consider 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 potentially be shown the customer. The set of products selected in given round is called an assortment, denoted as S₁ for round t, where S; C fl....... .N and |S,] < 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 choice a, among the options: (i) rejecting the browsing options provided (a: = 0). (ii) browsing and purchasing/selectnng an option (a: = i, E SD), and (iii) browsing but not purchasing/selecting
option (a, Od). If option is chosen, the seller earns a reward ri, with r: E [0, 1] for E [N] and ro = Fod O.
Customer choice probabilities are determined by the Multinomial Logit (MNL) model as follows:
e {0,00d)
P(a: S 5)
Uy Un Eees
otherwise,
where v; denotes the (unknown) attraction parameter of option i. Without loss of generality we assume that attraction parameters are normalized such that vi = 1. In parallel with the real applications, we also assume that not browsing is the most common choice, i.c. 2, Up.
3

---

It is important to note that not purchasing/selectnng is different from tracking conversions. Specifically, the customer browses the given assortment, we can track the customer decides not 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 = O, the seller receives this choice immediately. Otherwise, the customer's 's choice revealed the seller after a delay d, N. de is sampled from unknown distribution fa and independent from dr. Moreover, delays longer than a certain threshold μ is censored or ignored by the seller in the learning process. This threshold is based on the seller's operational requirements. We later extend our solution to the patient learner setting without threshold, i.c. μ oc.
We define aif as the demand for option at time L. We have
1 ifa==
ai.e = (o. otherwise.
We also define Ca,a, E {0, }} as the censoring variable of product i at period / that is sold at period 8. The censoring variable determined
Ci,s,t = T(d, St - 8 and d, S 14)-
We define the feedback observed by the seller oi E {0, 1) and Oi,et Ci,s, The expected fraction of observed feedback denoted as 1/ : EE= fa(s).
The sequence of events at round t can be summarized as follows:
1. The seller selects an assortment St.
2. The customer interacts with the medium(view the page encounter with the pop-up) and makes a decision at-
3. The environment returns a reward r., i [AV, and samples a delay de-
4. Rewards of certain previous actions and/or if the customer rejected to browse revealed to the seller as aj
The expected reward of the seller given assortment S and attraction parameter is given by
R(S:v)= = Σ T4 1+ uod + Ejes
2
iES
The goal of the seller is to sequentially learn customer preferences and find policy to minimize cumulative expected regret, defined as:
Reg(T, m) Σ ((S R(ST:0),))
where S* arg ma (I.....)) M).SSIK R(S; 2nv) maximizes the expected reward of the clairvoyant and {vod, U1, ......, UN is the ground truth attraction parameter set.
4 Delayed MNL Bandit (DEMBA) Algorithm
In this section, we introduce the Delayed MNL Bandit (DEMBA) algorithm. DEMBA leverages an epoch-based learning method, where epochs explicitly defined by immediate no-purchase decisions. Specifically, when a no-purchase decision made by the customer, the current epoch is closed, and 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- 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 until epoch r is denoted as Üi, and can be calculated
rend
where 7 the current epoch and tand the last period of epoch
We count how many times a particular product is offered in the assortment until epoch J using the set (i) which is the epochs during which is offered, i.e. Ei) {e S T : E S.). Then, we estimate attraction parameters by
0g.r
(E)()
0gr is a biased estimator due to delay and thresholding, i.e. E[ + v, We consider this bias in our estimation and build our concentration around Uy. We state our concentration result in the following lemma.
Lemma 4.1 With probability at least O(N-2T-)) for every epoch {L....} and option i E {Od, I...., N J. we have
10,r - Uu S Dir.
where A,,-
(486, + +1) log(NT)
48 log NT) (x]
[X]
Sketch of the proof. Note that or a biased estimator and defined
gend
U1.T
E, (i)
[E)
where [E) is the total number of epochs during which product is shown to the customer and send
E sm1 Oi.a.enna is the total observed sales of product of 0d or is the total observed delayed no selections.
We analyze the concentration around Uy:
#=1 Og,n
10 ub
F, (i)
Σen send
aijaT(dds S (1) Σ gend
==tend -+1 u+1 0i S gend s)
(i)
and Een Cs as,oI(ds 11) +E
lend
#= u+1 Gi,s (I(ds S gend - 5) - IIdd S 11)
Ex)
E (d, < u1) [+)(
ee u+1 0i,0 I(de s 14)
+
(1)
[+(1)]
where 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.
5

---

For the first term in the decomposition
we have
gend
rond
E 04,s 0i, [(d 11)
04,5 Td,s
S 111
1/p
== 0i,s
==1 02,5
2/
E1(1
[i)l
Ei)
E, (i)
==1
as.o
$ 14)
4/ Dx Fu
as,a
+
1/4
> ==
1//2
E (i)l
E (i)
E (i)
(a)
gnd
gend
I[d, S pc)
e= 04,5
U/
+
0/
(2)
E (i)
Ex]
We bound the first term (a) using Hoeffding's 's inequality:
(oT(NNT [E)
(a) S
(3)
For part (b), we make use of the Chernoff bound from Theorem A.1 and handle two cases based
on (v, + 1) v. [B]] The detailed proof is provided in Appendix A. The result can be
Glog(NT)
summarized as follows:
480,, (NT (T(1))
48 A8log(N7)
U1 S
2
(+)
N2T
Combining the bounds for both terms, we establish the concentration result stated Lemma 4.1
Using the concentration result for the attraction parameters, we construct upper confidence bounds for each product each epoch:
Usrr = 0i,7 + Ai,r.
and for the delayed no-purchase option, we construct lower confidence bound:
Cnd.r God.r Aod,T
where
(480,r (NT)) [i)]
48 log(NT) +
A
[1]
We use the optimistic parameter estimations to construct an optimistic revenue function
R(S;)= ri VES
(5:; 2 2od,r + Ejes
Ci.7
Our algorithm DEMBA suggests the assortment according to the optimistic revenue function R(S; 6) and updates parameters according to feedback received with delay. The pseudocode of DEMBA is given Algorithm
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; i). For this step, polynomial-time solutions with O(N2) complexity are available, as demonstrated by |usmeviichietong et al. (2100] and Davis et al. [013). Updating observed preferences či, involves summing over previous observations, with complexity of (1 fend)). The process of updating sets (i) and estimations úi,r and the confidence bounds adds O(N) operations per epoch. Given that S and S T, the overall computational complexity across all rounds T is O + 22

---

Algorithm Delayed MNL Bandit (DEMBA)
Initialize:
0;
while < do
Compute S, arg (l..s R(S;0);
Offer assortment Sr;
Receive feedback;
if 0₁ = then (immediate reject]
ügr = - Oi,s
send
Vi E [od];
Fr (1) :feST:iES
E [N] U (od);
0G. = Ri.T
[
[E+(0)
UGr UG,r + Dir
vi [N]:
Lnd,r = Bud.r Dod,7
T
end if
++1
end while
Regret Analysis
Our main result is given in the following theorem.
Theorem 5.1 Let π DEMBA be the policy produced by Algorithm
using
Dir
(488, (NT)
48 logiNTY+H Then, π DEEMBA satisfies [E-()]
[6(0)]
Reg(T, n DEMBA)
<(1 + p)) log(T) - K 73T (og(T) + 48K log(T)()og((TT) + 73 NT (NT(
48 log? (NT).
The bound can be further simplified to Ô (VNT) by omitting logarithmic terms.
Sketch of the proof. The proof of Theoremm 5.] consists of several steps. First, the definition of the optimistic revenue function R(S; 8) and show that it provides an upper bound on the true revenue function R(S; v..) This is achieved by leveraging Lemma/B. 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:
Σ (R(S( (B) R(S,; -
Reg(T, x)
where H, is the duration of epoch r. Given that the epoch duration follows 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 and one that occurs with low probability (event E,):
E|AR,] = [AR,I(E,-)) + ARTI(EF
We bound the contribution of the low-probability event by (N 1)P((T 1), which is small due our concentration results.
For the hiobabrrobbbiiity event, we show that the difference between the optimistic and true revenues we can then bound the regret for each epoch:
bounded by A.r. Applying Lemma B.I
E|RR] < (N + 1)P(ETT +
1 + Uy Bod + Suys (R(S,; R(S ())
JES,
Summing over all epochs and using the properties of the epoch duration, we show that the total regret is bounded by Ö(VNT). D

---

The full detailed proof is provided in Appendix B.
Next, we provide lower bound result for the regret in the following theorem:
Theorem 5.2 For any policy n, suppose K N//4, 1, and d/a E (0, 1). There exists a universal constant c > 0 such that
TN 1//
Reg TT) 2 emmin
T.
The proof of Theorem 5.2 deferred to Appendix C. This theorem establishes lower bound on the regret, showing that no policy can achieve a better regret rate than D2 ((VNT).
The effect of the threshold μ in the upper bound appears only in logarithmic terms, suggesting that the regret increases with larger p.. In contrast, in the lower bound, thy appears in the square root and the denominator, indicating that the regret decreases with larger It is important to note that p 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.
Remark 5.3
Non-Thresholded Setting: The Patient Learner
In this section, we modify our algorithm for environments that do not apply threshold for delays. We refer to the seller in this setting as the patien! learner. The patient learner 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 OON-O(N-2 we have
480 r (NT(N
48 (NT)
E [[d,]
6E [d,] (NT(
10rr vsl S
[x(T)]
[T)
[E(T)]
[E(TT]
The proof deferred to the Appendix. According to Lemma Air r to
6.1 we modify Algorithm by changing
480,,- log(NT)
48 18log( (TT
E [d.]
6E [d,] log(NT)
+
[E((T)
[E((T)
[T]
[E(T)
We then state the regret result of the modified algorithm:
Theorem 6.2 Let PAt BA be the policy produced by Algorithm using Åi,, T PA-DEMMA satisfies
Reg(T, N P < (Tg((T) + K log log((T)) NT)
(K+ + 1) E. [d.)
GE (d.)) log (NT) 72 NT NT (NT).
the non-thresholded setting, the term with by disappears since lim Up This implies that the regret in this setting does not depend on th providing potentially lighter bound compared to the thresholded case. However, new terms involving E (de) are introduced. Asymptotically, both the thresholded and non threshoedddd regret bounds simplify to Ö(VNT), with the differences primarily reflected in the constants, and both bounds approach the lower bound.
Remark 6.3
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, focus the expectation of the delay, and further improvements based on skewness are left for future work. The asymptotic regret bound remains O O(VNT), independent of skewness.

---

500
300
EXP you
EXP pos
250
200
EXP yox 7
Cummlalieen Baggeet
2200
EXP
EXP
Cammlntve
DEMBA
Camalatte
DEMBA
150
DEMBA
200
150
1000
5000
10000
15000
20000
5000
10000 Rounds
15000
20000
5000
10000
15000
20000
Rounds
Rounds
400
EXP you
Stggre
EXP pdl6
Cunulativv ionuaalive Regret
220
RXP
EXP your
EXP 3
300
EXP
EXP
200
EXP ymu
Cumulation
DEMBA
200
DEMBA
150
DEMBA
200
1.00
5000
10000
15000
20000
4000
8000
12000
16000
20000
5000
10000
13000
20000
Rounds
Rounds
Rounds
Figure 1: Simulation results of DEMBA algorithm with benchmarks. Top row: geometric delays. Bottom row: uniform delays. Left: E[d,] = 500, μ = 100; Middle E[d,] = 100, μ = 100; Right: [[d,] 100, μ 500. Results are averaged over 100 independent runs.
7 Experiments
We conducted two sets of experiments to evaluate the performance our algorithms. Our benchmark sxplore-then-explot (EXP) algorithm, which explores by offering random assortments until 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 comparisons.
We used N = 10, K 4 and = for all i E (I....,NN)
N). The attraction parameters were set as:
(0.25 te if i (1,2,9,, 0.25 otherwise,
V;
where e represents the contrast between products. With this setting the optimal assortment is (1, 10].
In the first 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 th values: E[d.] 500, / 100; R [d.]]
100, μ 100; and E[d,] 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 all settings. Learning becomes more difficult as b 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 v p 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 R[d.]] = 100 and μ = 100 for the first experiment and [Edd]] 100 for the second experiment. The results shown in Figure 2 On the left-hand side, we observe that when the number of rounds 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.

---

120
0.00
EXP pai
Cumulative Regret
100
0015
Cum Degret
200
EXP yoT
PA-DEMBA
150
100
40
50-
2500
5000
7500
10000
12500 Rounds
15000
17500
20000
2500
5000
7500
10000
12500
15000
17500
20000
Rounds
Figure 2: Left: Performance change of DEMBA algorithm with different contrast levels. Right: PA- DEMBA and benchmarks with non-thresholded delays. Results are averaged over 100 independent runs.
Comalative Begret
250
EXP gos
Camuulation Raggee
EXP To
CamullaSve Reggee
EXP TUM
200
goa
200
EXP go3
EXP
400
EXP 2
150
DEMBA
150
DEMBA
DEMBA
MNL Bandi:
50
5000
10000
15000
20000
5000
10000
15000
20000
5000
10000 Rounds
15000
20000
Rounds
Rounds
Figure 3: Comparison with MNL-Bandit. Left: no delay; Middle R[d.] 50; Right: E[d.] 100.
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 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.] 50 and R[d.] 100. We observed that when there is no delay, the performance of MNL-Bandit and DEMBA almost identical. However, as the delay increases, the performance of MNL--Bandit deteriorates, clearly indicating that it fails to handle delayed feedback.
8 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 improvement regret by considering the delay distribution via d).. This would require learning the delay distribution itself, adding more complexity. Moreover, it could be interesting 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.
Acknowledgments
I would like thank the anonymous referees for their valuable feedback, which has helped to improve this paper.
10

---

References
A. Agarwal, N. Johnson, and S. Agarwal. Choice bandits. Advances in neural information pweiiiiooooooooosee processing systems, 33:18399-18410, 2020.
S. Agrawal, V. Avadhanula, V. Goyal, and A. Zeevi. Thompson sampling for the mnl-bandit. In Conference on Learning Theory, pages 76-78. PMLR, 2017.
S. Agrawal, V. Avadhanula, V. Goyal, and Zeevi. Mnl-bandit: dynamic learning approach to assortment selection. Operations Research, 1753))1453-1445 2019.
P. Auer, N. Cesa-Bianchi and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
J. Blanchet, R. Xu, and Z. Zhou. delay-adaptive learning in generalized linear contextual bandits. Mathematics of Operations Research, 49(1):326-345 2024.
N. Gesa-Bianchi, C. Gentile, Y. Mansour, and A. Minora. Delay and cooperation in nonstochastic bandits. In Conference on Learning Theory, pages 605-622. PMLR, 2016.
N. Gesa-Bianchi T. Cesari, R. Colomboni, C. Gentile, and Y. Mansour. Nonstochastie bandits with composite anonymous feedback. The Journal of Machine Learning Research, 23():12713- 2022.
O. Chapelle. Modeling delayed feedback in display advertising. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1097-1105, 2014.
X. Chen and Y. Wang. A note tight lower bound for capacitated mnl-bandit assortment selection models. Operations Research Letters, 46(5):334-55 537, 2018.
X. Chen, Y. Wang, and Y. Zhou, Optimal policy for dynamic assortment planning under multinomial logit models. Mathematics of Operations Research, 46(4):1639-1633 2021.
J. Davis, G. Gallego, and H. Topaloglu. Assortment planning under the multinomial logit model with totally unimodular constraint structures. 2013.
K. Dong, Y. Li, Q. Zhang, and Zhou. Multinomial logit bandit with low switching cost. In International Conference on Machine Learning, pages 2607-2615, PMLR, 2020.
G. E. Flaspohler, F. Orabona, J. Cohen, S. Mouatadid, M. Oprescu, P. Orenstein, and L. Mackey, Online learning with optimism and delay. In International Conference on Machine Learning, pages 3363-3373, PMLR, 2021.
M. A. Gael, C. Vernade, A. Carpentier, and M. Valko. Stochastic bandits with arm-dependent delays. In International Conference on Machine Learning, pages 3348-3356. PMLR, 2020.
A. Grover, T. Markov, P. Attia, N. Jin, N. Perkins, B. Cheong, M. Chen, Yang, S. Harris, W. Chueh, et al. Best arm identification in multi-armed bandits with delayed feedback. In International Conference on Artificial Intelligence and Statistics, pages 833-842. PMLR, 2018.
B. Howson, C. Pike-Burke. and S. Filippi. Delayed feedback in generalised linear bandits revisited. In International Conference on Artificial Intelligence and Statistics, pages 6095-6119, PMLR, 2023.
P. Joulani, A. Gyorgy, and C. Szepesvári. Online learning under delayed feedback. In International Conference on Machine Learning, pages 1453-1461. PMLR, 2013.
Lancewicki, S. Segal, T. Koren, and Mansour, Stochastic multi-armed bandits with unrestricted delay distributions. In International Conference Machine Learning, pages 9978. PMLR, 2021.
T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
M. Mitzenmacher and F. Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
11

---

N. Perivier and V. Goyal. Dynamic pricing and assortment under contextual mnl demand. Advances in Neural Information Processing Systems, 35:3461-3474, 2022.
C. Pike-Burke, S. Agrawal, C. Szepesvari, and Grunewalder. Bandits with delayed, aggregated anonymous feedback. In International Conference on Machine Learning, pages 4105-4113, PMLR, 2018.
Rusmevichientong, Z.-J. M. Shen, and D. B. Shmoys. Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations research, (866):666611680 2010.
W. Tang, C.-J Ho, and Y. Liu, Bandit learning with delayed impact of actions. Advances in Neural Information Processing Systems, 34:26804-26817, 2021.
Y. Tang, Wang, and 7.. Zheng. Stochastic multi-armed bandits with strongly reward-dependent delays. In International Conference on Artificial Intelligence and Statistics, pages 3043-3051. PMLR, 2024.
T. S. Thune, N. Cesa-Bianchi, and Y. Seldin. Nonstochastic multiarmed bandits with unrestricted delays. Advances in Neural Information Processing Systems, 32, 2019.
C. Vernade, O. Cappé, and V. Perchet. Stochastic bandit models for delayed conversions. arXiv preprint urXiv:1706.09) 091000996666600 2017.
C. Vernade, A. Carpentier, T. Lattimore, G. Zappella, B. Ermis, and M. Brueckner. Linear bandits with stochastic delayed feedback. In International Conference on Machine Learning, pages 9712-9721 PMLR, 2020.
Y. Wang, X. Chen, and Y. Zhou. Near-optimal policies for dynamic multinomial logit assortment selection models. Advances in neural information processing systems, 31, 2018.
Y. Yang. H. Zhong. Wu, B. Liu, L. Wang, and S. Du. A reduction based framework for sequential decision making with delayed feedback. Advances in Neural Information Processing Systems, 36, 2024.
Z. Zhou, R. Xu, and J. Blanchet. Learning in generalized linear contextual bandits with stochastic delays. Advances in Neural Information Processing Systems, 32, 2019.
12

---

A Proof of Lemma 4.1
We begin by providing an instrumental theorem that will be useful establish concentration results.
Theorem A.1 (Theorem 5 of Agrawal et al. 2019]) Consider n ii.d. geometric random variables X1...., Xn with parameter p. i.e. for any
P(X; = m) (1 p Vm = 10.1,2.... b
and let μ E(;) 1- p and X 1 n Ei=1 Xz. For any Ç > we have
npc?
P(X > (1 + (1 S exp
2(1 () n)2 )
We now provide the proof of Lemma 4.1 that is crucial for subsequent analysis. Proof of Lemma 4.1 Note that 0g,r is a biased estimator and defined as
ES
Ui.r
Oi,a,ennd
EE, (i)
|E(11]
where (E) is the total number of epochs that product is shown the customer and Σ the total observed sales of product Od or is the total observed delayed no selections.
Let be the current period, i.e. = rend + 1. We have
r-1
s=1 01,8,--1 2/
10,rr Vu
Er)
\- Ti. S 11)++ + E.-L 0i, St- 888) 8)
[1,(
Σ di. I(d 11) + Ex-t-p ai,e
(I(ds S 1 - 8) - I(dds S 14)
[i)
1-1 E di,al(ds S 11)
+ Ex 0i I(d, S 1))
(5)
[E)
Ex(1)
where 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 have
t-1 ag T(ds I 11)
1-1
1=
ai I(d, < 11
1/ === Oi,s
=== ais
E, (1)
Ex (i)
(x)
E, (1)
Σ
as.aI(cd AIde S 11)
3/
1==1 0i,8
2//u Σ'=1 -=
Oi,e
<
+
Ex (i)
Er (i)
E, (i)
(a)
(b)
I(d, S 1))
> -= 04.a
1/4 +
(6)
EE(())
Fr (i)
We have
(NT)
(a) S
(1)
by Hoeffding's 's inequality.
13

---

For part (b), we make use of the Chernoff bound from Theorem A.1
in two cases according to
<= (m: + 1) (Nog(NT) E.]
Case 15 5 L. We have from Theorem A.1
2'
Σ s=1 Oi,s
1
IP
14 544
E (i)
N2T2
-=1 Oi,5
IP
< -5p
E (i)
N272
M Oi,s
60, log log((N))
2
> (us + V
For [i)(
U/
N2T2
Therefore, we have
ai,s
24v; (NT)
P
U/ > V
(8)
E, (T)
(1)
NºT2
We shall generalize the result at two cases for substituting vs with oG, in the concentration radius and upper bounding the new bound utilizing v.
For 0g,7, we have
1 1
P( vs -65
N2T2
hence,
1
P(20,rr Sv²) S
N2T2
Combining this with
g we get.
Σ ===1 Gi,s
480; log log(NT)
IP
04 >
(9)
E
(i)
Ex
N2T2'
For upper bounding 9 using 24 we have
P(ú,r U1 > v:5) 1 S N2T2
hence
32%
TP( 01,)) 5 N2T2
Therefore, conclude
P
s=1
1-1
ai,8
U4
72v, log( NT)
[+)i
N272
(10)
Case <>> 4: We have 2ç²
1.4 Let C'
=222. We have by Theorem A.1
Σ ==1 ai.s
Ex (1)
p
Vi
> C'v
S exp
E (1)l
2(1 (1)(1 v.)
(F)
S exp
6(1 + 0z)
14

---

substituting the value of 5' we get
- 0g,s (i)
48 log NT)
P
==
1 N272
(1I)
E,
Ei)
Combining and and applying union bound we have
Σ
48 (NT(NT)
48 (ogg((TT))
4
IP
===1
21
[E)
E+(1)
[+)
N²T
Additionally, combining
10
and 11
and applying union bound we have
Σ
4-1
di,s
72v; Mog(NT)
48 (og((N)
P
U/
(12)
E+(1)
(+(
(+)
ai,s
480,,- log(NT)
48 log((N)
P
Us S
21
(13)
E
(i)
(i)
(+)
NºT
We can bound the second element of (T)
Σ(-1 Ls=t-p 01,0
T(d, S 5n))
(14)
(i)
[i)l
Combining
7
12 and (4) gives the result.
B Proof of Theorem 5.1
We begin with establishing key result that will instrumental in our main proof.
Lemma B.1 Let S represent the optimal assortment when the MNL parameters are given by Also, let Sy denote the assortment applied by the policy at epoch v. For any parameter set w distinct from v the following hold.
Uf for all E II...,,,, and ond 2 wod, then R(S" w) 2 R(S":v).
ii. If S w; for all i E I,...,N, and oud wod then R(S,:w) R(S,;u) S (w:-)) 14voa ++voa+Eeess+ Eyese vi"
Proof of Lemma B. Note that the proof of Part i. mostly resembles Lemma A.3 Agrawal et al. 2019), and we write the whole proof here for being self-contained.
Proof of Part Let vd be identical to e except for the jth element, which is increased wy. We aim show that for any S*, if vy is increased to wj, then R(S*;u²) > R(S*:)) This suffices to prove R(S"; w) 2 u)
Define := E Yy F34 and V := 1+ Eissyy U/. If there exists a S* such that ry R(S*), removing product from the assortment yields higher expected revenue, contradicting the optimality of S* Therefore, we have
rú 2 R(S";v)
Eies+ Tet:
1+ Eiesi 14
Eiesnry Fill +ry0
1+ Eiesh ve t
T Ttys
V D
15

---

for all j E S". Rearranging terms, we get
V 2 T.
(15)
To have v() ;() we need show that
T ry
T + ry
N + V-
+ Wj
which is equivalent to Rearranging terms, we get
Toy + rryW;; 2 Twy + r3 ug.
ryV( - n1)) 2 Twm - 0z),
which holds thanks to 15
Moreover, the case for = Od holds trivially which concludes our proof.
Proof of Part ii. We have
R(S,:w) - R(S+;u)
Σ Vod
Σjes, w/
+ Uld EyEs. 8j
iES.
Σ vES.
U
ri + vod + LjES. W/
Ti + uod + Ejes. Wj
iES.
Eies. ri(wi: - Us)
1 + Vod + EjEs. W/)
Eies, (wi U/)
< 1 vod + Djes. 41
where the second inequality follows from S 1, V
Now, we provide the proof of Theorem 5.1
Proof of Theorem
5.7 We have
R(S,;O,) Z R(S"; 0,) 2 ;(S";,),.)
(16)
where the first inequality holds thanks to the definition of S, and the second inequality follows from Lemma B.I with probability at least -NN-IT IT-
We have
Reg(T, E
HL (pp) - R(S+:(w)))
where H, is the duration of epoch and |H,, Geom( 14.hy Eees, wany' then E| Sz] = 1 + Vod + Ejes, thu Since Sr is determined by the history of policy(Fr-1). 1). we have E| F,-1l= = 1 + V/ Vod + Ejes, d/n Therefore the regret is equal to
Reg(T, T) =
E [| (R(S' - ((Sr;t Fr-il
and by the law of total expectations
Reg(T, (og(TTT)) = E
1 + Vod Σ tiwes (R(S")0a)) - R(S,:
jES-
16

---

Let the epoch based regret be AR,, we can write it as
AR, = 1 1uooo + Σd Uays (R(S": - R(Sr;
JES+
then the regret can be written in the form of We define event &, for all as
7
(T, σ) = E
AR
N
E, = U (
-
Ar) u (lonwos _od,1 Ar). Unuis
The event & is low probability event. We will analyze the regret according to the event separately:
B| E [A, AR,,I(EF_,))
We have ARt S N + 1 and hence
E
E|AR,] s (N + 1)(+())))))++B (E(,,
We have by 16 that
( 1+ Σ
B[AR (N + 1))((E-1)) +
(R.(S-: (())
jES,
Then, by Lemma B.1 we have
1 + Uod +
Σ
(R(S):04) - R(S+; (n)) (
jES,
+ toy +
Σ
Wulss
(R(S)iVt) - ((StiVnn)
jES.
Eies, T2Ü
ΣiEs, 1/U,T
+ Vod Vod +
Σ
Uullss
+ Vou + Ejes, Tj 1 + Dod + EjEs, B3
jES,
EiEs, PeUliit
Eies, rith
+ + Vod + Ejes, fi
+ Wyylod Ejes, V/n
Eies, ryU;r (102,((1pm - Coa) + 2nd + Ejes, T,) + Uyuoos + Ejes, 0i))
Eies, ri(Uier - v/4ls)
+ Vod
Σ
Whelisg
1 Vod + Ejes, Ui
JES,
K K(WnVod - -ood)
Eies, (04.r - v3
+ dyy +
Σ Duyi
(1 +
Lod Lond + Ejes, 13) (1 + Wyyood + Ejes, 0;)
1 thy EEES, Tj
jES,
K( K(thyood 2na)
Eies. (Ui, - (b(
1 + woy +
Σ Mulls
+ + dlyubd Exes, Du
Vod + Ejes, Duuli
JES,
K (2// Vod - 2od) + E (uer
17

---

Let E, be the number of periods that the product is offered. Then, the regret can be written as
Reg(T, T) s E
(N + 1))(E,)))) + KAdd, +
Σ A
EES
N+1
(72vnd + 1) (oT((NT)
48K (log((() + p))
E
K
NT2
T
(726; + log((T)
48 log((N)) + 1 +
(i)
E, (i)
EES,
N E,ggET
s (T)(T) + / 737 log( + 48K (NT) + μ4) + 73E
Σ
+ 48 4ologg (NT) + μ (Tg(
N
< (T) + K 73T (NT) + 48K (T) + +1) 73
Σ
V
48 log (NT) + μ log()),
where the third inequality holds due to 7 s T, F4 S T and the fourth inequality holds due to Jensen's 's inequality.
Since, EN B T, we conclude
Reg(T, a) (Tg(T)) K / 73T 48K (og(())) + n))
+ 73 NT (NT) + 48 log? (NT) + /a (T)
C Proof of Theorem 5.2
Before giving the proof of Theorem 5.2 its proof.
first give an instrumental Lemma in the main proof and
Lemma C.1 Let and Q be categorical distributions with Pp = = Ps and Po = = q: where Pt = 9: for all i == = Also. let the selected option be observed with bias d. The Sellback-Leibles divergence between and Q, denoted by (K Q), given by
DKL (1)())))
Q)
Σ
96
2=0
Proof of Lemma
C.1
We have
(vala te)
(P 1Q)=]
Σ
() + tc)
1=0
(9: + t
gi
1=0
di
where the inequality follows since log(1 + x) S for any x >
and the last equality holds since
EL 4 =0.
18

---

Proof of Theorem 5.2 We set 1 for all i E [N]. Let S be a subset of N with |S] K. For
attraction parameters. we set Uo 1, Vod arbitrary in [0, 11, o (1 + +e/K K for E S and v; 1/K
otherwise.
We denote all subsets of product set [M] of size K as Sk- We have
R(S) = R(S") 1+E
SESK
vod +
We employ the neighboring argument for assortment sets as described in Chen and Wang 2018 For any arbitrary assortment St, we have
1 (1- R(S.) + Vod + (1 5)E'
where ò a measure of discrepancy from the optimal set S, i.c. ô := 8,5s| Then, we have
K
R(S*) - R(S.) = 1
1 1 (1 -1e
2 + vod +E 2 + vod + (1 8)E
8E + devod
(2 vod + {2 + vod + (1 - (1e5
5r (1 vod)
For any arbitrary subset S. of |St| s K, we can find S, SK such that S. S. We define
N = -T 1(i St). We have
max SESK
Es (R(S) R(S.)]
(17)
max SESK
Es
R(S) R($:)
(18)
T
Es
R(S) - R{S:)
(19)
SK
SESK t=1
2
Ess
N
E
(20)
16
K
SESK iES
Eg
T
(21)
16
SK
K
SESK
ES
Let s(i)
all subsets [N] of size K 1 that do not include We have
1
Σ
Σ
Es
No
Σ
Σ
Eg
N
K|Sk|
K|SK
SESK iES
im
SESguES
Σ
Σ
Es
No
(22)
KJSK
S'ESK-1
We define probability measures and Q through parameterizations S' and S' fi} respec- tively. We denote Total Variation(TV) distance between two probability measures as TV(P.Q) = sup (P(A) - Q(A) and Kullback-Leible (KL) divergence as Dx Q). We have 0 S N; <T
19

---

and
T
Ep[ - |o[ -
Σ
P(N: =) Q(N, =)
1=0
T
Σ
P(N; =) Q(N
/=0
- T (P(
V 2 D
ST V
(23)
where the last inequality follows from Pinsker's Inequality.
We use
23 in
22
and get
Σ Es
N
KSK
SESK
LES
Es NM
+T
V2
DKu(Ps' || Psu(t))
(24)
S
For the first element of
24
we have
Σ
Σ
Es
N
1
Σ
Σ
Eg
N
(25)
K SK
K
K|Sk|
5'ES
S'ESk-1 i&S'
N
1
Esg
N
(26)
K|SK|
S'ESK-1 1=1
|SK-1| TK
(27)
K|Sk
TK
(28)
N
K
+1
T
(29)
3
where the last inequality follows from K < N/4. For the second element of (24). we have that
T
Σ
DKL(Ps
|| Psum))
(30)
K|Sk
S'Es(a
T|SK-1
N
1 DKL |l Psu()))
<
K|Sk|
Σ
S
max
V
2
(31)
T
N
/ DKILPPs Psu(g)
Σ
max
(32)
N K
S'E
max T S'ESK-1
Σ DEL || Psru())
(33)
V
2(N - 2NN-22K-
K+
where the first inequality is due Hölder's inequality and the second inequality follows from Jansen's inequality.
20

---

We have ( (-15. || (- = 0 for & St. For analyzing i E St, we define K'
| S K, = |S, S $ K and a = 1 + vod + K'
K
We have
1 a Je/K a (J + 1)e/K
Ppo - -o0ool=
+ K(a² + aJeeK K + + +(
K
1
Pod doal = vod
a Je/K
a + (J + D)/K
Vode
K(a² + aJe/K + a(J + 1)c/ K + J(J 1)e2K33)
Bude K
1
1
lpy 1 5 s
K
a a Je/K a (J + (J()+))eKK
c+c²
(² + aJe/K + aa +
2c
for 1 ر $ N and i;;
K2
and
1
1
1
Ip: - 2i 1
-
+ Kat Je/K
K
a
+ Je/K
a (J+ 1)e/K
6
5
+
K2
K
2c
$
K'
We also have
1
40
2
2 7'
a (J 1)
3+c
1/2
and
1+6
1 1
9 K(a+ (J + 1)e/K)
2
2 4K'
4K
Using these with Lemma
we get
4
40
4K J 4
4K 462
DKr (Ps((.))))
|| Psuua (-1$)) S 1//
+
K2
K2
K4
K2
802
16e
16e7
$ 1/4
+
K²
K2
K
40
K
21

---

Integrating this into
33 we obtain
max S'ESK-1
1
Σ
DRI(Ps) || Ps.u())
(34)
2(N K 11
iES'
40
<
max S'ESK-1
T
Esy [N:]
(35)
2(N
K + 1)
K
igS!
40 2
N
T
Σ
Eg [Nd]
(36)
2(N - K + 1)
K
40 e2
S
TK.
(37)
2(N K +)
K
For the final bound, we have
max SESK
Es (R(S)
R(S.)
1=1
Es
Σ
(38)
16
SK
K
SESX iES
T
40
2
16
T
3
T
V
2(N
K
+
K
TK
(39)
(40)
where follows from 21
388
339
follows from
29 and 37
Setting min N/ T, 0.53 gives the final bound.
D Proof of Theorem 6.2
We 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 XI.... Xn be independent Poisson trials such that PX;;- 1) pt- Let X
-i=1 X, Then, for 5 < 1:
P(X 2 (1 5) S exp( exp(-E(X)55/3)
Proof of Lemma 6.
We have
10 1/1
-== 0i,a,t-1 1
ET(T)
Σ 1-1
== Ti,,T(ds
S t 2-
[E((T]
Σ 01,9
E1-1
I(d > 1- 5)
[T(T)
Σt-1 I(ds > t 6-9) 8)
+
(41)
[a(TT)
[2(TT]
22

---

The derivation of the bound for the first element of (41 parallels that of Lemma 4.1 thus, we omit the analysis, yielding
1==1 Gi
,8 log(NT
48 log (NT)
S
(42)
[T(
[T)
[T(T)
with probability at least
NºT.
For the second element of (41) we first bound the expected number of unobserved feedback until time t. We have
7-1 Σ
1- P(d, > t s-
t-1 p(d-- > >
E
I(d, > t- - 8)
Σ
PPd1 n)
P(d1 mm)
n=0 m=n+=
m-1
Σ
P(d1 = m) =
Σ
m P(d1 =m)
m n=
m=0
E(de].
(43)
Then, have
Σ I(d, > t 8)
Σ I(dd > -t-s s)
(44)
Ei(T)
[Bx(T]
(1 + 5)E
t-1 I(d, 1 - ss
(45)
[E((T)
(1 + 8)E [d.]
(46)
[T)
E [d,]
6E dd (T))
(47)
E.(T)
[E)
where the first inequality follows by Theorem D.1 with probability at least 1 1 by setting
6 NN) and the second inequality follows from 43
Combining 42 and gives the result.
Proof of Theorem 6.2
We will proceed similarly to the proof of Theorem 5.1 but we provide complete proof here for clarity and completeness.
We have
((S+; 2 ((S"; 2 R(S*vv),
(48)
where the first inequality holds thanks to the definition of S, and the second inequality follows from Lemma B.I with probability at least - ((N-TT-1)
Similar to the proof of Theorem
5.1
we can write
Reg (T π)
E
Σ
+ vod
Eoz oi (R(S*;u) - R(S+:U))
jES,
And defining the epoch based regret be ART, we can write it as
AR,
1 vod +
Σ 4
-
jES-
23

---

which will lead to We define event &, for all as
Reg(T, =E
ART
& U 01.r Uil
u Lod,rl Ar).
Conditioning on the event and by 488 we can write
B & (N + 1)) +
1+ vod + Σ /)
JESr
Then, by Lemma B.1
we have
Σ (R(S+:0+)-R(S)))) R(S-:0) -((F_))
1 una +
jESr
1 Gnd +
Σ
(R(SF;ot)- - R((S:))
jEST
EiEs, TiUlr
Eies, T/Ul.
1 Vud Σ Di
1+ Uod End + Ejes, Ty 1 Vod + Ejes, T
jESt
Eies. 12Ui,
Eies, rill + Vid + Ejes, n3)
+ + vod + Ejes, Uj
Eies. reUi (Vod Una)
Eies, Pi(Ui,r - U.)
+ 0od Σ
Di
(1 Lidd + Ejes, T;) (1 (1+ + Vod + Ejes, TT))
1 vod Ejes, 11
JES,
K(vod Bod) Ejes, 11) + Und + Ejes, V.))
Eies, (De,r - 11)
Σ Dj
1 vod +
(1 + +od Eod
+ vod Exes, T7
JESt
K(und- - 2od)
+ Eies, Eis,,(oir -14) + vid Ejes, D/
Σ Dj
+ vod +
1 vud + Eyes, Vi
JESt
K (Vod 2oa) + Σ (Uer vs.)).
24

---

Let E, be the number of periods that the product is offered. Then, the regret can be written as
(Tg(T, T) = E
(N + 1))(E,1))) + Kdd +
Σ A..7) ΣA.))
iES
++
480;,r (NT)
48K (og(NT)
KR [d.]
6E [d,] log (NT)
I E
K NT
[E(1)
[+]
[g(T)
[E((T)
480,, log(NT)
48 48 (NT)
E [d
6E [d,] log(NT)
[E)
E,, (i)
[E((T]
IES.
< ITg + K
48T log(NT)
+ K + [d.] + 6E d log (NTT)
72E
03 Er (NT
(48 E(d.)
6E d. log 2 (NT)
< "log(T)) + K V 487 log( (T)) + (K + 1)(48 + E [d.] + 6E [d.)) log (NVT)
N
72
Σ
EE (NT)
i=1
where the third inequality holds due to F < T, E, - T and the fourth inequality holds due to Jensen's s inequality.
Since, EN
& E[E S T, we conclude
Reg(T, T) (T) + K 48T 48T (o)(TT) + (K 1) + [E] + 6E [d.)) log (NT)
+ 72v NT (NT)
E Experimental Details
We numerically evaluate our algorithms over 100 independently generated problem instances, with error bars representing standard errors both Figure I and Figure 2
The simulations were conducted on a server equipped with 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.
25

---

NeurIPS Paper Checklist
1. Claims
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
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 not discussed in the paper.
The authors are encouraged to create 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
26

---

Justification: [NA]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The scripts for all experiments is provided.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
27

---

Answer: [Yes]
Justification: The necessary information is provided in the Experiments section and in the appendix as well as the scripts for experiments are provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm ec/
public/guides/ htwps///ooooduabsssssoooooooo
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/ppp wwwppcclccgguiecuceccccceooooope Detggudddse/oeSubbiiiinn httSSSabmiiiioooiiiiiiooooii for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Error bars are reported and represent standard errors.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
28

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 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 range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
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 compute required for each of the individual experimental runs well 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:p/pw....aeoooooo/oooooooaaa
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed. The main application of the presented work theoretical for sequential decision making.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.
29

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [NA]
Justification: the paper does not use existing assets.
Guidelines:
The answer NA means that the paper does 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
30

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "xbK19B64fu", "reviewer": "Reviewer_9pwP", "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).\n\nThe 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.\nThe 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.", "questions": "See above.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper considers online learning of discrete choice models in a general setting with delayed feedback. The setup is broadly applicable.", "weaknesses": "- 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)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and constructive feedback on our paper. We appreciate your recognition of the strengths of our work and the detailed suggestions for improvement.\n\nFollowing your suggestion, we will expand the related work section in our revised manuscript to include a more comprehensive discussion of how our contributions differ from other available online learning methods with MNL choice models and other delayed learning settings. We also performed additional experiments to compare our algorithm with the literature.\n\nIn particular, Agrawal et al. rely on unbiased estimations of attraction value i.e. $v_i$). However, in our setting with delayed feedback, we only observe biased samples which requires a different approach for estimation. We develop a concentration inequality in Lemma 1 that accounts for not-yet-observed choices. Without considering not-yet-observed choices, the high probability bounds would be invalid. Moreover, we performed additional experiments comparing our algorithm (DEMBA) with MNL-Bandit (Agrawal et al.) and we will include them in our revised manuscript. We have also uploaded a file with these figures.  We have three figures, we start with no delay and increase the delay in our second and third figure. We observe that when there is no delay the performance of MNL-Bandit and DEMBA are almost identical. However, as we increase the amount of the delay the performance of MNL-Bandit deteriorates, clearly indicating that it fails to answer delayed feedback.\n\nThe challenges in our problem are similar to those in other online learning settings with delays in the higher level: dealing with the uncertainty due to not-yet-observed rewards. For UCB-based solutions, correcting bias due to delays is a common approach in the delayed bandit literature with stochastic delays. However, existing solutions for other bandit algorithms are not applicable to our problem due to the unique nature of assortment feedback in discrete choice models. Particularly, in MAB settings with delayed feedback, the primary concern is updating estimates of arm rewards. In our discrete choice model, we must maintain and update an assortment of items, creating a more complex interaction between choices and feedback. The expected reward structure is determined by an assortment of items, and we consider the bias at the item level. Delayed feedback affects both item value estimation and the assortment composition offered at each time step. Therefore, we developed a novel concentration inequality and used it to construct upper and lower confidence bounds of item attraction values that results in optimistic assortments.\n\nOnce again, we thank you for your valuable feedback and for helping us improve our paper. We hope these clarifications adequately address your concerns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XreYUyHfT4", "reviewer": "Reviewer_KQSR", "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.\n\nPros:\n\n- 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.\n\n- 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.\n\nCons and questions:\n\n- 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?\n\n- 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.", "questions": "Please see my comments above.", "limitations": "Please see my comments above.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Please see my comments above.", "weaknesses": "Please see my comments above.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First of all, we would like to extend our sincere thanks for your detailed review and for the insightful comments.\n\n> 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 . 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  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?\n\nTaking the skewness of the delay distribution into account can improve the regret upper bound, especially in the non-thresholded setting, although it will not change the asymptotic bound. However, this consideration is important in practice, as it can lead to tighter regret bounds under certain conditions. This would involve using Bernstein-type inequality, assumptions on tail characteristics(e.g. sub-exponential tails) or Gaussian assumption with known or unknown variance. \n\nIn our revised manuscript, we will add a remark to explain that in practice, variations in the delay distribution with certain assumptions can be favorable. Specifically, for distributions with fast decay rates, such as Gaussian distributions, we can expect a better regret performance compared to long-tail distributions. \n\nRegarding the improvement mentioned in Remark 5.3 (reducing the $\\mu$ factor in our upper bound), our current analysis does not admit improvement by incorporating the skewness of the delay distribution because currently we are using $\\mu$ directly to bound one term in our analysis. We leave improving it as a future research direction.\n\n> 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.\n\nWe agree and performed additional experiments comparing our algorithm (DEMBA) with MNL-Bandit (Agrawal et al.) and we will include them in our revised manuscript. We have also uploaded a file with these figures. We have three figures, we start with no delay and increase the delay in our second and third figure. We observe that when there is no delay, the performance of MNL-Bandit and DEMBA are almost identical. However, as we increase the amount of the delay the performance of MNL-Bandit deteriorates, clearly indicating that it fails to answer delayed feedback. \n\nOnce again, we appreciate your insightful comments, which have significantly contributed to the enhancement of our manuscript. We hope these clarifications adequately address your concerns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JmXmqK9C3V", "reviewer": "Reviewer_dJHq", "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.", "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": "The authors have addressed the limitations of this work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The studied problem of delayed feedback in bandits, while not new, is interesting in the case where the seller can offer a slate of items to the customer at every round. \n\n- The paper is well-written and easy to follow.\n\n- The theoretical regret guarantee is provided with matching lower bound. These results and the numerical experiments provided a complete set of result for this setting.\n\n- The proof-sketch provided offers good intuition to help understand the analysis and the result.", "weaknesses": "- The analysis did not attempt to learn the unknown delay distribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and for your positive evaluation of our work. We appreciate your recognition of the strengths of our paper and your constructive feedback.\n\n> Does the problem setup change dramatically when the reward for each item in the assortment is 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 yield higher reward (or lower cost of browsing), does the current analysis still hold?\n\nIn our current setting, we use the multinomial logit model which assumes that the consumer choice behavior is solely affected by the subset of products being offered. We can extend this model by considering the choice probabilities, and therefore the expected reward of a product, is dependent to its position. We can define $\\gamma_k$ as the visibility coefficient of the product in position $k$. We can also assume that $\\gamma_k$ for each position is known to the learner. Indeed, $\\gamma_k$ can be estimated from historical data. Then, the attraction parameter will be multiplied by the visibility parameter to calculate the expected reward, i.e., $r_i \\frac{\\gamma_{k(i)} v_i}{\\sum_{j \\in S} \\gamma_{k(j)} v_j}$. \n\n\nOur analysis holds for this setting if we make an additional assumption that the customer viewed the whole assortment. Without this assumption, we cannot calculate choice probability by $\\frac{\\gamma_{k(i)} v_i}{\\sum_{j \\in S} \\gamma_{k(j)} v_j}$ and we would need a different model for this case. In scenarios where customers may not view the entire assortment, our current model would require significant modifications to accommodate partial visibility. While other approaches such as cascading bandits (e.g., Combes et al., Craswell et al., Kveton et al.) explicitly model sequential item examination, integrating such models into our framework would be an interesting direction for future research rather than a direct solution within our current setup. With our whole-assortment viewing assumption and by using an appropriate argmax oracle (e.g., the work of Abeliuk et al. provides an efficient algorithm), we can cover the position-dependent scenario within our framework.\n\nWe appreciate your insightful question and the opportunity to address it.\n\n\n\nA. Abeliuk, G. Berbeglia, M. Cebrian, and P. Van Hentenryck. Assortment optimization under a multinomial logit model with position bias and social influence. In 4OR, 14:57-75, 2016.\n\nR. Combes, S. Magureanu, A. Proutière, and C. Laroche. Learning to rank: Regret lower bounds and efficient algorithms. In Proc. of the 2015 ACM SIGMETRICS Int. Conf. on Measurement and Modeling of Computer Systems, 2015.\n\nN. Craswell, O. Zoeter, M. Taylor, and B. Ramsey. An experimental comparison of click position-bias models. In Proc. of the Int. Conf. on Web Search and Data Mining. ACM, 2008.\n\nB. Kveton, C. Szepesvári, Z. Wen, and A. Ashkan. Cascading bandits : Learning to rank in the cascade model. In Proc. of the 32nd Int. Conf. on Machine Learning, 2015.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vFtezJskR3", "reviewer": "Reviewer_rHM8", "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.", "questions": "The reviewer would like the authors to address the reported weaknesses, and to respond to the following questions:\n\nQ1) Can the authors provide a formal proof of the first passage of the proof of Lemma 4.1 at line 184:\n$$\\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) |},$$\nas 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).\n\nQ2) Can the authors clarify how the epochs are defined?\n\nQ3) Why have the authors not considered any of the algorithms reported in Section 2 in the experimental evaluation of the proposed algorithms?", "limitations": "No limitations", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "The paper is clear and well-written. A deep analysis of related works is provided by the authors, clearly stating what gap in the literature the work aims to fill.\nThe work combines existing ideas to propose a solution to a problem that might have some significance to some members of the NeurIPS community.", "weaknesses": "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:\n$$\no_{i,s,t} = c_{i,s,t} a_{i,t},\n$$\nwhereas in the proof sketch of Lemma 4.1 it is used as $o_{i,s,t} = c_{i,s,t} a_{i,s}$.\nBoth 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.\nIn 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.\n\nW2) 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.\n\nW3) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First of all, we would like to extend our sincere thanks for your comments. We have taken due diligence to address the concerns raised and we believe your suggestions have greatly helped us in improving our manuscript.\n\n> W1) The definition of the \"feedback observed by the seller\", $o_{i,s,t}$ is inconsistent and seems also incorrect.\n\nThank you for identifying this typo. We have updated line 148 as $o_{i,s,t} = c_{i,s,t} a_{i,s}$. We will explain the potential issue of multiple counting in the discussion of Q1.\n\n> 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.\n\nWe can write the condition containing the logical AND as  \n$$\n\\mathbb{I}(d_s \\le t-s \\text{ and } d_s \\le \\mu) = \\mathbb{I}(d_s \\le \\min(t-s, \\mu)).\n$$\nIn line 188, we split the expression based on the periods where the minimum attains a particular value. Therefore, our analysis is valid. We will add an explanation to make this step clear in our revised manuscript.\n\n> W3) The observation that \"each alternative can act as a substitute or competitor 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.\n\nWe agree that the multinomial logit (MNL) model has limitations. While the MNL model does not explicitly make attraction parameters dependent on the proposed set, the relative nature of the choice probabilities ensures that each item’s selection probability is influenced by the presence or absence of other items in the assortment. This captures a form of substitution effect. We acknowledge that more complex substitution dynamics could be modeled by making attraction parameters assortment-dependent. However, our current formulation offers a balance between capturing essential substitution behavior and maintaining model tractability. Exploring more nuanced substitution dynamics could indeed be an interesting direction for future research.\n\n> Q1) Can the authors provide a formal proof of the first passage of the proof of Lemma 4.1 at line 184:\n$$\n\\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) |},\n$$\nas 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).\n\nConsidering your comment in W1, we have refined our approach for representing the total observation count to avoid potential multiple counting. Hence, we modified the definition of $\\tilde{v}\\_{i, \\tau}$ as \n$$\n\\tilde{v}\\_{i, \\tau} = \\sum\\_{s=1}^{t^{end}\\_\\tau} o_{i,s, t^{end}\\_\\tau}\n$$ \nand we can compute $\\hat{v}\\_{i, \\tau}$ directly as \n$$\n\\hat{v}\\_{i, \\tau} = \\frac{\\tilde{v}\\_{i, \\tau}}{| E\\_{\\tau} (i) |} = \\frac{\\sum\\_{s=1}^{t^{end}\\_\\tau} o_{i,s, t^{end}\\_\\tau}}{| E\\_{\\tau} (i) |}.\n$$\n\nBy this representation, we avoid any possible double counting and simplify the step asked in Q1.\n\n> Q2) Can the authors clarify how the epochs are defined?\n\nEpochs are defined by immediate no-purchase decisions. When an immediate no-purchase decision occurs, it closes an epoch and starts a new one. In line 164\\&165, we mention that epochs are based on immediate no-purchase outcomes, however, we agree that this expression is not clear enough. We will make this definition explicit in our revised manuscript.\n\n> Q3) Why have the authors not considered any of the algorithms reported in Section 2 in the experimental evaluation of the proposed algorithms?\n\nInitially, we did not consider any algorithms from the literature in our experiments since our algorithm is the first one that considers delays and does not have a competitor in this regard. However, following your suggestion, we performed additional experiments comparing our algorithm (DEMBA) with MNL-Bandit (Agrawal et al.) and included them in the revised manuscript. We have also uploaded a file with these figures. We have three figures: starting with no delay and increasing the delay in the second and third figures. We observe that when there is no delay, the performance of MNL-Bandit and DEMBA are almost identical. However, as we increase the delay, the performance of MNL-Bandit deteriorates, clearly indicating that it fails to address delayed feedback effectively, whereas DEMBA continues to perform well.\n\nOnce again, we would like to convey our sincere thanks for your thorough reading and your valuable feedback. We also hope that our revised version addresses all your comments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "C70ZlBW4ml", "reviewer": "Reviewer_3Qos", "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.", "questions": "Questions:\n1) What is $\\mathcal{S}$ in algorithm 1? The set of all assortments of size at most K?\n2) $K$ is not mentioned in the upper bounds. They hold for all K?\n3) What is the tradeoff between DEMBA and PA-DEMBA? The guarantees mentioned in Theorems 5.1 and 6.2 are identical.\n4) 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.\n\nSuggestions:\n1) The guarantees written in Theorems 5.1, 6.2 are identical. Consider showing the factors who make a difference between the results. \n2) 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?\n3) 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})$\".\n\nTypos:\n1) line 181: \"at least at least\".\n2) Theorem 5.1: Add \"Then\" before \"$\\pi^{DEMBA}$\".", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) Assuming that results are correct, the paper gives a first solution to a question that seems natural in the domain of online advertising.\n2) The bounds are fairly tight.\n3) The paper includes an extensive literature review.\n4) The authors conducted experiments to support their theoretical findings.", "weaknesses": "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.\n2) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First of all, we would like to extend our sincere thanks for your detailed review and constructive feedback. We have carefully considered your comments and have addressed them as follows:\n\n> W1) 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.\n\nWe appreciate your feedback regarding the presentation of the results. You are correct that the current use of $\\tilde{O}$ notation may obscure the differences between the guarantees of DEMBA and PA-DEMBA. To address this, we will revise the manuscript to include all relevant factors in our regret bounds. This change will highlight the differences more clearly and provide a better understanding of the improvements that can be achieved with each algorithm.\n\n> W2) 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 helped the reader to conjecture if the same techniques may be used to solve other variations of the problem.\n\nRegarding the generalizability of our setup, we acknowledge that our work is indeed focused on the specific problem of delayed learning in the multinomial logit model. This specificity allows us to provide detailed analysis and guarantees for this particular setting, which is important in areas such as online advertising and recommendation systems. However, we believe that some of our techniques, particularly those dealing with delayed feedback, could potentially be adapted to other choice models or learning scenarios with delayed information. Future work could explore extending our approach to other discrete choice models or investigating how our methods for handling delay could be applied in different online learning contexts. While our current focus is on providing a thorough solution for the multinomial logit model with delayed feedback, we agree that exploring broader applications could be a valuable direction for future research.\n\n> Q1) What is $\\mathcal{S}$ in algorithm 1? The set of all assortments of size at most \\(K\\)?\n\n$\\mathcal{S}$ represents the set of all assortments of size at most K. We will make this clearer in the revised manuscript.\n\n> Q2) $K$ is not mentioned in the upper bounds. Do they hold for all \\(K\\)?\n> Q3) What is the tradeoff between DEMBA and PA-DEMBA? The guarantees mentioned in Theorems 5.1 and 6.2 are identical.\n\n$K$ and the difference between DEMBA and PA-DEMBA appear in logarithmic terms of our regret bounds, in the revised manuscript we will include logarithmic terms to clarify the distinctions between the algorithms.\n\n> Q4) In line 288, I am not sure how you reached the conclusion that \"Our lower bound suggests 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 a lower bound can suggest an improvement to the upper bound. For example, $\\Omega(1)$ is also a valid lower bound.\n\nThe key point we were aiming to make is that our lower bound and upper bound do not match in terms of threshold terms $\\psi_\\mu$ and $\\mu$ and this suggest a possible improvement on handling delay and/or threshold mechanism in our analysis. This distinction will also be clearer when we explicitly include the logarithmic terms in our regret guarantees in the revised manuscript.\n\n> S1) The guarantees written in Theorems 5.1, 6.2 are identical. Consider showing the factors who make a difference between the results.\n\nWe agree with your suggestion. In the revised manuscript, we will explicitly detail the factors that differentiate the results, including constants and other relevant terms.\n\n> S2) I think that the introduction lacks justifications or examples. For example, in line 23, you write \"fall short in scenarios....\". Why? Is there a line of work showing this?\n\nWe will modify this sentence with an example to illustrate that classical multi-armed bandit (MAB) models are not suitable for our setting. Specifically, MAB models require selecting one arm at each round, while in our case, we need to select multiple products (arms) to form an assortment. Moreover, adding or subtracting a product from the assortment affects the probabilities of selection for other products, which introduces a complexity not captured by traditional MAB models. This stochastic reward process and the impact of assortment changes on future decisions are better captured by our discrete choice model using the multinomial logit (MNL) framework. We will provide relevant justifications and examples to illustrate these points.\n\n> S3) 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 logarithmic 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})$\"\n\nThank you for pointing out this typo. We will correct this and use $\\Omega$ while calling our lower bound.\n\n> Typos\n\nWe will correct the repetition of “at least” and we will add “Then” before “$\\pi^{DEMBA}$\" as suggested.\n\nWe appreciate your feedback and believe these revisions will significantly improve the manuscript. Thank you for the opportunity to address these issues.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We deeply appreciate the reviewers’ thoughtful and comprehensive comments and feedback. As per the suggestions of the review team, we’ve performed an additional experiment and are sharing the results in this file.

Meta-review: 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.
Decision: Accept (poster)