Cascading Bandits: Optimizing Recommendation Frequency in Delayed Feedback Environments
Authors: Dairui Wang
Junyu Cao
Yan Zhang
Wei Qi
Venue: NeurIPS 2023 poster (2023)
Keywords: delayed feedback
recommender system
frequency control

Abstract: Delayed feedback is a critical problem in dynamic recommender systems. In practice, the feedback result often depends on the frequency of recommendation. Most existing online learning literature fails to consider optimization of the recommendation frequency, and regards the reward from each successfully recommended message to be equal. In this paper, we consider a novel cascading bandits setting, where individual messages from a selected list are sent to a user periodically. Whenever a user does not like a message, she may abandon the system with a probability positively correlated with the recommendation frequency.  A learning agent needs to learn both the underlying message attraction probabilities and users' abandonment probabilities through the randomly delayed feedback. We first show a dynamic programming solution to finding the optimal message sequence in deterministic scenarios, in which the reward is allowed to vary with different messages. Then we propose a polynomial time UCB-based offline learning algorithm, and discuss its performance by characterizing its regret bound. For the online setting, we propose a learning algorithm which allows adaptive content for a given user. Numerical experiment on AmEx dataset confirms the effectiveness of our algorithms.

Cascading Bandits: Optimizing Recommendation Frequency in Delayed Feedback Environments
Dairui Wang Tsinghua University
Junyu Cao"
The University of Texas at Austin junyu. www.mccombs..ccc..........o..... utexas.ee..........o edu
wdr230mails tsinghua. edu. en
Yan Zhang McGill University yan. zhang13@mail www.immgllll...................o
Wei Qi'
Tsinghua University qiw@tsinghua,
edw.. edu. cn
Abstract
Delayed feedback is a critical problem in dynamic recommender systems. In practice, the feedback result often depends on the frequency of recommendation. Most existing online learning literature fails to consider optimization the recom- mendation frequency, and regards the reward from each successfully recommended message as equal. In this paper, we consider a novel cascading bandits setting, where individual messages from selected list sent to user periodically. When- ever a user does not like a message, she may abandon the system with probability positively correlated with the recommendation frequency. A learning agent needs learn both the underlying message attraction probabilities and users' abandonment probabilities through the randomly delayed feedback. We first show dynamic programming solution to finding the optimal message sequence in deterministic scenarios, which the reward is allowed to vary with different messages. Then we propose polynomial time UCB- -esed offline learning algorithm, and discuss its performance by characterizing its regret bound. For the online setting, we propose a learning algorithm which allows adaptive content for a given user. Numerical experiment on AmEx dataset confirms the effectiveness of our algorithms.
Background
1.1 Introduction
Recommending dynamic content based on adaptive learning of user behavior is a critical task to online platforms. In marketing campaign, only 2% of web traffic converts on the first visi is important to re-target potential users with notifications such as ads, emails or app reminders to gain traction and awareness. The content for those notifications should be dynamic and adapted to user's behavior. Since the feedback may not be instant, campaign system still needs to provide campaigns to other while waiting. Mcanwhile, the frequency at which the notifications be judiciously managed, i.c., sending more messages may increase the odds click, but frequent messaging may also alienate and drive away users.
sent should also
Online learning for recommendation tasks has been extensively studied in the multi-armed bandit framework. In this setting, pulling certain arms in the bandit problem corresponds to selecting marketing messages for user. In particular, cascading bandit [13
20 25 which models
Cooresponding authors.
http:://eeaargteee..cc//bbiiibie www./hatt-----eerrreeeeeeeeee httpre//aeeabbb---eettrrreiianaa -nw---a--d-d----ddde how-does- ienss-it-oo -or
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

sending sequence of messages to individual users is a popular choice for analyzing sequential recommendations. However, existing settings in this field are often stylized and overlook certain characteristics that are prevalent in real-world scenarios. For instance, a common assumption is immediate user feedback, whereas in practice, it may take hours to months to receive responses. Additionally, bandit models typically disregard the variation in payback for each message, which limits the practical implications of the model for recommendations. Furthermore, the concept of "frequency" in message dissemination is absent in current cascading bandit literature, where an entire sequence of messages is sent to a user at once. Consequently, the content for a single user becomes non-adaptive, potentially missing out additional feedback from other users over an extended time span and foregoing potential benefits.
In this work, we propose and analyze a variant of cascading bandit with five notable differences from the existing literature. Firstly, whenever a user does not like a message, she may abandon the system and forgo receipt of future messages. Thus, the order of messages influences the reward in our
setting, which is in contrast to the existing work on cascading bandit such as [13 18
21
20 25
Secondly, instead of having the total number of messages in a sequence as a fixed parameter, this quantity is also a decision variable. In particular, we assume the abandonment probability may increase with the frequency at which messages are being disseminated. Thirdly, individual messages for each user are sent out with some time apart, as opposed to all at once. As we gather more feedback from some of the previous messages, the content for a user is dynamic and adaptive. Fourthly, the reward generated after a message is clicked varies with the type of it. Lastly, we also incorporate delayed feedback in our setting.
have the ability to update the remaining sequence, and thus
The analysis for this setting is particularly challenging. One source of complications comes from the interlaced timing of multiple events, i.e., users arrive at different time, messages for individual users are sent at different time, and their responses time is also random. Meanwhile, users' feedback also depends on multiple factors, including the choices of the content, their order, as well as the dissemination frequency.
The contribution of our work is fourfold. 1. We introduce a novel cascading bandit setting with delayed feedback, different reward and frequency control. 2. For the offline combinatorial problem with all known parameters. we characterize a polynomial-timg -imme algorithm which determines an optimal list with the appropriate dissemination frequency. 3. For the online setting where we need to learn both the message attraction probabilities and the abandonment probabilities, we propose a learning algorithm and characterized its regret bound. 4. We incorporate personalization by analyzing a contextual variant of the online problem which utilizes both content and user features.
The paper is organized as follows. We review the related literature in Section 1.2 In Section 2 we formally introduce the model and analyze the offline optimization problem with all known parameters. In Section 3 and Section 4 we study the online learning problem in the presence of delayed feedback for the non-contextual and contextual settings, respectively. We evaluate the performance of our algorithms with numerical experiments in Section Lastly, we discuss some limitations and research prospect of our work in Section 6
1.2 Related Work
The analysis on delayed feedback has started to receive increasing attention in recent years 22 16
23 In online learning. [8] considers fixed and known delay effect, and shows an additive penalty of the regret for the stochastic setting. [I] analyzes a more general setting and show that the regret increase is multiplicative in the adversarial setting and additive in the stochastic setting. They propose meta-algori that can adapt non-delay algorithms and develop a UCB algorithm for the bandit problem. [7] and [19 analyze the impact of delayed feedback in a Gaussian process bandit and an online Markov decision process respectively. Compared to the existing bandit literature, to the best of our knowledge, our work is the first to incorporate delay effects for the cascade model which involves a sequence of actions. Besides the uncertainty contributed by the random response time, the feedback also depends both the choice of the messages and the order in which they are being sent.
Our work shares some similarity with combinatorial bandits 3 5 4 as the learning agent needs to choose a set of messages. However, in our setting, the order of the messages also impacts the rewards. As highlighted in the introduction, our work extends the cascading bandits literature by including frequency control and delayed feedback. This setting can be potentially modeled as a reinforcement

---

learning problem, such as [24], which proposes an offline reinforcement learning framework to optimize sequential notification decisions. However, this approach significantly increases the learning complexity, making it difficult to analyze performance theoretically.
In the original cascading model [6], user who is presented with list of messages examines the content sequentially, until she clicks on the first attractive message. A common different assumption the dependent click model. In this model, a user may click on multiple messages and finally stop at the truly attractive one. It can be used in bandit settings 2 or generic click-models algorithms [9] 20 25], the attraction probabilities of messages are not known a priori. A learning agent selects list with fixed number of messages to incoming users, with the goal to maximize the total clicks over T time steps. User's i feedback to list is immediate. The agent then uses this information to learn the underlying attraction probabilities and updates their list for the next user. Although [10] provides a bound based on Thompson sampling for semi-bandit rewards and (20] provides a problem-independent bound for unstructured rewards, they do not consider the messages' difference theory. While 22 also considers user abandonment behavior in a cascading bandit setting, the abandonment probability is constant and the recommendation to single user is static, as opposed an adaptive sequence which is considered this work.
In cascading bandit [3 18
2 Problem Formulation
Assume there are N available messages, which we denote as X. We use S = ,..",, to denote list of messages, where S1 and Sm represent the first and the last message, respectively.
Let be the index function mapping the position in a list to message, i.e., x(i) = j if and only if S, = (i]. Define 0 as the inverse function of K, i... {(i) = j if and only Sj {i}.
Users will receive a list of messages periodically, Upon receiving a message, if a user finds attractive, she clicks on it. Otherwise, she may examine the next message with probability q(m) if the list has not run out, or she may leave with probability 1- 1m) The probability (m) depends on the total length of the list the message dissemination frequency, which we will elaborate next. For each message i, we use U; to denote its attraction probability which captures the relevance of its content to user, and use R2 to denote its return when user clicks it. We define (V1, uN) and R (R,, ... Rxx)
A user arrives at time f, where t= I,...., T. We assume that for every user, there is fixed time window D, during which selected messages will be disseminated Messages are sent sequentially at a fixed time interval with a dissemination frequency f(m) recommendation frequency fixed for every user, which allows us to easily capture the trade-off between the total number of messages that can be disseminated and the probability of abandonment. At every time step, a user receives at most one message. Define M as the maximum number of messages that can be sent during D. We assume q(m) is non-increasing function with m. The intuition is that when the frequency of re-targeting is higher, a user is more likely to he overwhelmed and is more prone to abandonment. We denote q = (q(1).... ... ((M)). The following example illustrates the interactions between users and messages at different time.
[m/D]. Here we keep the
Example 2.1. Figure shows 5 users that arrive at time 1,... ,5. Actions taken by users are color-coded, i.e., user clicks on a specific message (orange), has not clicked but remains active (green), and has abandoned the system (yellow). M.,t = denotes that message is sent at time step j. e.g., User 2 receives message 10 at t = 2 and message 9 at = 6. While the dissemination frequency is determined for a given user upon arrival, may be different across users, e.g., User and 5 receive messages at fixed interval of 4 and 6 time steps respectively.
For list with m messages, besides the first message which is guaranteed to be viewed, the probability that message i is being examined, denoted as wo (m)) depends on the outcomes of the earlier messages, i.., w:; (m) II j=1
(() ((1 *n(g) (m))) It is the probability that the user does not click on any messages shown before and still remains in the system. Let US, v, g(m)) denote the payoff that the learning agent receives from list of messages S, when the message attraction probabilities are
2D is known as the re- targgeeting window in the marketing literature. See https://www/ learn- Learn-nore/rene nore/retargeting
wdwowl....rlloooo http:://ww.aarrol.. com/
3

---

Fl
2 3
10
11
12
14
16
18
20
21
22
23
Ussr
M1
M20
M5
User
M1O
M9
MI8
M16
User
M12
User 5
M17
MS
M21
MII
Figure I: An illustrative example on user's interactions with the learning agent.
and abandonment probability is - gmm). The expected payoff is
V,, R,,5,, Σ (,(mm) R,v.
iEX
To determine a list of messages with appropriate dissemination frequency, the learning agent needs solve an optimization problem that maximizes EIU(S, v, R, (m)))] subject constraint that S; S, @ for i * j. indicating no duplicated messages in the list. We use S* to denote the optimal solution to the combinatorial optimization problem.
In the following result, we characterize the property the optimal list S'. We then propose an algorithm to identify S in the offline setting, i.e., when the message attraction probabilities and the probabilities q describing users' abandonment behavior are known.
Theorem 2.2. the optimal sequence S", the characteristic parameter of messages
RR
- v(1 (mm)
are sorted descending order.
Proof outline:
We prove the statement by contradiction. If S is not ordered by y, we generate another sequence S' by swapping pair of adjacent messages S. We can prove that the expected payoff of S' is higher than S, which is contradiction.
We include complete proof in the supplementary material. Note that while Theorem 2.2 provides necessary condition for S" it does not indicate that the messages with the highest should be selected. The structure of (S, v, R, (mm)) shows that each message in the list will only influence the contribution of all the messages after it on the total return. Therefore, we use a dynamic programming approach determine the list backwards.
Algorithm 1: Determine the optimal sequence S" with frequency control.
Input messages and their R:
for m MM do
Sort messages based on their in a descending order S' = (S1, , for m N do
W 1,1) m G(m 1, argmaxy
end
for le
m do
for
/ = 1-1:N. m -
W - 1,1) max (v. + (k)
10
G(k - 1,1) argmax - m
(v.R + (1 ())(m)
G(k, (
P2 + (k)))))((k))))
11
end
12
end
13
Output (00. 0), G(O,0).
end
15 Select the highest (0, 0) and record the corresponding m and G(0, 0)-
Algorithm describes the procedure of finding the optimal list S with frequency f(m*). Messages will be first sorted in descending order based on y. For any feasible m, selected the messages

---

backwards. The last message must be the one left with the highest expected return vR. We define
I-1
1(K, = Σ Un(()) Bu(s)
II (1 (a(o))a(m), k 551 s=k+1
(2.1)
b=++
the maximum weighted sum of the last (m k) messages' return, when the (k- 1)-th message be sent is restricted to be after the 1-th message in S G(k, 1) is to record the messages selected. The transition equation shows the influence of the (A: 1)-th message on the feasible place for the k-th messages in S". Therefore, GO 0) is the optimal m messages, and W (0. 0) means total return. The optimal list is the list with the highest expected return W W0,00 0) among the M candidates.
Learning with Delayed Feedback
In the previous section, we have explored the structure of the optimal list when v and q are both known. In this section, we to the online learning setting with delayed feedback. To differentiate the time stamps, we will use r to indicate the time when a user arrives (i.e., r = 1, , and use I indicate when messages are being sent. The first message for user r is sent instantaneously at t == r, and the subsequent messages are sent at the frequency determined by f(m).
A message sent time t is delayed if its feedback is received after Let denote the delayed duration. Throughout this analysis with delayed feedback, we assume that 0 S T S Tiaa with probability 1, i.e., the delay has finite support independent of the attraction probability. When the feedback is not received after Tmaz (e.g.. a user stops responding to messages), we assume the user has abandoned. Note that Tmaz is not related the attraction probability, nor does it imply feedback.
Define as the list of messages for user r, where the total message length m,, We use regret to measure the performance of a learning algorithm, where the regret for policy π is defined
(Tg(T) F.x Σ USS v, R(,)())))) US"", v, g(mm)))))
3.1 Learning Algorithm
As the messages are sent sequentially with some time apart, the learning agent may additional feedback to update the remaining messages. Thus, the content for a user can be dynamic. We will now present our UCB-based learning strategy achieve this.
We first define our unbiased estimator for u and q respectively. Let (t))) be the total number of feedback (i.e., sum of clicks and no-clicks) received for message by time f, and let ct denote the number of clicks for message by time t. Similarly, let (t) denote the total number of no-clicks from users with dissemination frequency f(m), and bm (t) denote the number abandoned users with frequency (m) by time I. Let (1) = Tm (1) bm(())
Define the estimator ūg = e; (t) and qu (m) = n., (t)/Tm(() (t),, which are both unbiased. Next, define the upper confidence bound for and q follows,
logt and qi UCB (m) qm())= + 2 logt Ti(tt)
UCB Ci
- + V
(3.1)
The following lemma proves the concentration bound for these estimators.
Lemma 3.1. For any t, we have P (UCB
logt T:())
UCB 2 11 2 for all i E X and < 1
P
d (CBB(m)
UCB (m)
logs Tm (t) {()) - <
< de
UCB (m) 2 for all S m S M.
Then propose Algorithm 2 for our learning task.
5

---

Algorithm 2: An online learning algorithm for cascading bandits with delayed feedback
Initialization: Set vUCB = 1 for all i E X, 9 BBB (m) = 1 for m = 1, M: = 1;
0,0
2 while 1 < <Too do for Any feedback for some message do Update B and BC (m) according to Equation end
3..1
for Any active user r with message scheduled to be sent at time do
UCB (m,))] according to Algorithm 1 Compute S arg maxş (S v RR, 9:
Send the first message in S S""(O"t user r; O, O, (e)) end
Compute (S', :m,) = arg maxs,m E|U(S, WCB R. qi-1 Offer Sf user and the dissemination frequency is set to f(m)); O2 S
L (m)) according to Algorithm |
12 end
We introduce the following notations. At time we consider not clicked on a message or abandoned, and there is a message scheduled to send to her at time I. Define m, the total number of messages selected for user r. where the corresponding abandonment probability is 1 - (m,)) and the frequency is [m,z). In the recommendation system, my is always fixed for single user and determined when she enters the system, but may vary for users entering the system at different times. Define O, as the set of messages that have already been sent to user r.
active where if she has
Algorithm 2 states that at time the learning agent first updates the UCB estimators for and q based on the available information. For the user that just arrived at time f, the agent determines a list St with frequency f (m,), and sends the first message St. Meanwhile, for an active user r who is scheduled to have the message sent at time I, the learning agent determines a new recommending list St with frequency (m,) (determined at time r), and then sends the first message in the list ("
3.2 Regret Analysis
Before presenting the regret bound for Algorithm 2 we want to highlight the challenges behind the analysis. Firstly, we allow dynamic content for active users who remain in the system. Secondly, the feedback of individual messages may be delayed for random amount of time and the frequency of the message dissemination across users could be different. User feedback depends on both the choice of content and the dissemination frequency, which further complicates the analysis. To address these challenges, develop novel proof technique analyze the regret.
Let S* denote the optimal strategy and S denote the sequence for user under strategy π. Without loss of generality, assume "n 2 72 2 ... 2 Yv. Define F, as the filtration regarding all the information before time t. We say E E, if message is sent to user r at time t.
Lemma 3.2 proves that with the higher attraction probabilities and the lower the abandonment probabilities, the expected payoff is higher. Lemma 3.3 estimates the upper bound regret of single recommendation under identical reward. Theorem 3.4 feedback exists.
3.4gives gives an upper bound of regret when delayed
Lemma 3.2. Assume S* is the optimal list of messages with length m². Under the condition that 0 UUBB and 0 < q(m²) S = (/CB(mm) we have
ESU y UCB RR
2 E|U((", v, v,R,)(m")),
Lemma 3.3. When all messages have identical reward, t E E, and any g' E (0, 1), we have
Ex [E[(UUK v, Ul (. UCB 2 v)]Fa
< Frx F ( UCB ver,.) 1(v UCB 2 v)]Fi-1 E
where Ex, is the tth message sent Theorem 3.4 (Performance bound for Algorithm 2. above by
time t.
The expected regret of Algorithm 2 is bounded
(T) S CN + M2) / T + C2N Ninax
for some constants C1 and Cz.

---

Proof Outline: First we note that
[S" v, R. {(m)))]] ES R, g(m,))
F. (S v, R, q(m))) US", v, R. q(m,))
+ E+ v, v, g(m,))))) US"", v, R. g(m.))]
(3.2)
Let Si denote the initial list for user r when she just arrives, i.c., Si the optimal sequence given v and - Note that this list may change at a later time when more information becomes available. Define events B Bu V8logt/T((t)
vs vitt o and Em,
(m)) ( Define H, Niex B Nismem Em,,- Firstly we could estimate the upper bound of E, v, R. q(m*)) - US v,, R. q(m,)))) by coupling, We can get
(m) /llott/Tm(t
E Ex [E(U(S)) v R. 9--1 (m,)) - v, R. (H. F11l
UCB P
SC2N + CBM² /T
Regarding the second part in Equation 3.2), we now bound the difference between E, (S(", R, q(m))]] and Ex[U(S", R, ))]. Note that S is an updated list that may differ from Sh, so we again use coupling to bound the difference. We couple the processes sending S and S", which both have the identical dissemination frequeney m,.
Summing over all time steps, we have ETH (S v, R. g(m.)) USS", V, ((m))) s CiylogT E Es E 21,0% T](--1] + DE ( where Jr Niex Bis With
some derivations, for each E X, we can bound the term
T
1 Till
Ex
Zie
S CsTmas + +CVT.
-
Applying Lemma
3.1 we have
E
1(H))
S CCNN++
Combining all the results above, we arrive at the desired result.
The complete proofs of Lemma 3.2 Lemma 3.3 and Theorem 3.4 are included in the supplementary material. If the delay effect is absent, we can show that the regret bound in Theorem 3.4 is reduced show that the increase in the regret contributed by
to (N + M2) T. In other words, the delayed feedback additive and linear in Tiaa in our setting. In this paper, we mainly focus on the instance-indeeendent regret, while is possible derive an instance-dependent result similarly following Theorem 2 and Theorem 4 in [13], combined with the technique that we have used here to deal with multiple interactions and the delayed feedback.
As special case of our proposed model, we can compare this result with the state-of the-thh-at art results of cascading bandits. [15] has derived lower bound as Ω ((VN MTT). Moreover, [[]] has shown the regret of O (VNT log T + N E[r]). Our setup is more complicated since there are more unknown parameters that need to be learned (probability abandonment), and the feedback is received in a delayed manner. The regret bound for our proposed algorithm (maxx(N M Nr). From the comparison to two special cases, duration.
see that regret is optimal in T well as the delay
Personalized Recommendation
In the previous section, we assume that all users share the identical preferences towards content and the abandonment behavior. To provide personalized recommendations which incorporate content and
7

---

user features, we propose a contextual variant of the learning algorithm which is motivated by [17 Note that in this section, we allow the message X to vary for different users, denoted as X,.
Define aa, as the features of message in X,, and X, as user's features. We assume the attraction probability of message is logit function of its content feature Wr,s, and user r's abandonment behavior can be described by a logit function of the user's features X,. Define the link function p(v) exp(y) exp(y)). That is,
1 P(abandon] X,, m) = ( exp(x =
and p(W,,))).
P(click on message i/W,,) exp(w,,,3)/(1 exp(w,,
Set Yr,- = if user r remains in the system after she does not click on the j"h message in a list, while yr, 0 if she abandons the system after viewing the jth message. Therefore, the maximum likelihood estimator Om at time t, dm,t. can be obtained as
1(m, = m) (Yrgx,a - log(1 + exaa))
ām,t arg max
[user examines the jth message but does not click by time t).
(4.1)
Similarly, let Yr = if user r clicks on the message j. and Y = O otherwise. The maximum likelihood estimator time can be obtained as
8, arg max
(Yn Wn - log + (mmmno99))
(user gives the feedback for the jth message by time t),
(4.2)
where feedback includes both clicks and no-elicks and K, the index function for user
Define the covariance matrices at time for two estimators Mm, = Et=i EØ= x, 1 examines the jth message but does click by time 1)1(m, Et= Ej= Wr,(() w' x(j) [user gives the feedback for the jth message by time t). We pro- pose the following contextual learning algorithm. In each step, after observing users' feedback, we update the maximum likelihood estimators for a'm and 3, respectively, followed by their upper confidence bound. We then these estimators determine the messages for the active users.
m). and V,
Algorithm 3: An online algorithm for contextual cascading bandits with delayed feedback
Input: Total time steps T, tuning parameter 7), and 72; t = 0; Initialize: Randomly choose frequency and messages send until time m,. Update V,, and Mm.ni while < T do
Update ām.t and B. by Equation 4.1 and Equation 4.2 +
Observe user's contexts x, and message contexts We.s Update
UCB (Wr.)) (CCB(w..))
W 3 (w..ell for all i, and
UCB (x:)) 11 (x/ 1211xe MMM)).)) for all m
for Any active user with message scheduled be sent at time do
Compute S" arg maxs (S, UUB R, R- UCB (m)) according Algorithm Send the first message in S" O" user O, O, (e): end
VCB V R, (CCB(() according to Algorithm Offer S to user and the dissemination frequency is set to (m:);; O, = S:;
Compute (S', m.) = arg maxs.m (SU
10
Update Mn,t and V;;
end
is also important to note that although Algorithm 2 and Algorithm are both based on the assumption that messages cannot be recommended repeatedly, they can be casily generalized. If

---

O, is not excluded from the candidate messages, the two algorithms can be applied the repeat- recommendation case. Moreover, if we want constrain the total number of repetitive displays of one message as B, we can create B copies of that message in the candidate set.
5 Numerical Experiment
In this section, we evaluate the performance of both the non- con-contextual and contextual algorithms based on the features of the real AmEx User Click datase which records over 463,000 recommen- dations of AmEx from July 2 to July 7 in 2017. The combination of "product" and "campaign_id" is regarded as messages in simulation.
Experiment I: Non-contextual setting. There are _N- = 25 available messages. The attraction probability v is uniformly generated from distribution [0, 0.5). and the return Rt uniformly generated from distribution [1, 3]. The maximum length of message list M is set to be 10. Based on estimations from the short lists in AmEx dataset, we set q(m) 1++xx(00033m) We set the re-targeting window
D 200 in all setrings. The response time r is uniformly generated from [0, 3] for each user. In addition to our proposed algorithm, we introduce several algorithms benchmarks: three different e-greedy algorithms and TS- IS-Cascade, which is a Thompson sampling algorithm for cascading bandits with Gaussian update
[25]
We observe the results of 100 independent simulations for 30,000 time steps. The results are shown in Fig where the shaded area represents the 95% confidence region. We find that the optimistic greedy and decaying e-greedy algorithms are difficult to find an optimal list. The average regret at T = 30,000 of our UCB algorithm is 550.14. 14, with 95% confidence interval of (454.71, 645.57), significantly better than the benchmarks.
Result:
Noncontextual Algorithms Performance Experiment
Contextual Algarithms Performance Experiment
2500
OptimistiGrredyy
ExplorethenCommit
Decaying Epslonrreecy
TS Castade
500
LinTs Cascade
Epsioonrredy
EpsilonSreecy
UCB
ContextualUCB
Regret
1500
Regres
300
1000
500
100
5000
10000
15000
20000
25000
30000
500
1000
1500
2000
2500
3000
Time
Time
Figure 2: Regrets of Algorithm
Figure 3: Regrets of Algorithm
Experiment II: Contextual setting. There are N = 25 available messages. The maximum length of message list M is set to be 20. User features are uniformly generated from [0, 5] x [0, 5] x [0,5], 5]. and message features are uniformly generated from [-6, 0j x [0, 1] x 00, 2] [-5,0] 0j. The coefficient related to the abandonment behavior, denoted as am. is uniformly generated
the range (four- dimensional including the intercept) -1.04 x [-0.064m, 0J x 1-0.08m, 0) x 1-0.16m, for 1.... 20, where 0m,1 is the intercept. An alternative coefficient &m is uniformly generated from -1.04 [-0.004m, 0] x [ 0.064m, 0) x 10.08m, 0] for
1.... 20. The coefficient related to message attraction is 3 = (0.05, 0.2, 0.1, 0.3, 0.4). where 3 is the intercept. Users' response time uniformly distributed
[0, We also implement several benchmark algorithms: two variants of algorithm, and Lin'L -CCCacade, which is linear
the <-greedy algorithm, the explore-then-comee
generalization of CT-Cascade 25
Result: We observe the results of 50 independent simulations for T 3,000 time steps. The result is shown in Fig 3 The average regret at T = 3,000 of Algorithm 3 is 293.94. 34,4, with a 95% confidence interval (273.85, 314.04), significantly better than the benchmark algorithms. In the early stage,

---

the contextual UCB algorithm also has good performance, showing faster convergence speed than benchmarks.
Experiment II: Comparison of UCB and contextual UCB. To compare the effect of Algorithm
2 and Algorithm [] make settings: (a): N 25, M 20 with user features and message features generated from the same distribution as in Experiment 2, but only generated once and then fixed. All other parameters are the same as Experiment (b): same as (a) but with N 100.
ContextualUCB vs UCB with Fixed Context Feature
1600
N-100,
ContextualUCB
1400
N-25, UCB
1200
N-25, ContextualUCB
1000
Regret
500
1000
1500
2000
2500
3000
Figure 4: Comparison of the UCB algorithms.
Result: We observe the results of 50 independent simulations for T 3,000 time steps. The result is shown in Fig The average regrets under the settings are 1451.95, 798.94, 441.90 and 280.73 from high to low, respectively. The contextual bandit UCB always work better than UCB algorithm in the same setting. Furthermore, the advantage of contextual algorithm becomes greater when there are more messages. This is because more messages will improve the estimation accuracy of a and B..
Conclusion
In this work, we considered cascading bandit problem with delayed feedback and flexible rewards. Based on the users' feedback, the learning agent needs policy to select list of messages and determine the frequency at which these messages are disseminated. We proposed a novel learning algorithm to effectively learn such a policy, and it is capable of recommending list that is dynamic to given user within polynomial time. Experiments proved the effectiveness and applicability of our algorithm compared to benchmark algorithms in novel cascading bandit problem.
For future work, it would be interesting to analyze the performance of alternative bandit algorithms, such as coompson-sampliing based algorithms for this setting. Additionally, considering that users' preferences may change over time, another avenue for future research would be to incorporate non-stationarity into user preferences.
Acknowledgments and Disclosure of Funding
Dairui Wang, Yan Zhang, and Wei Qi acknowledge the support from National Natural Science Foundation of China (Grants 72242106, 72188101).
References
[1] Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. In Advances in Neural Information Processing Systems, pages 873-881, 201
[2] Junyu Cao and Wei Sun. Dynamic learning of sequential choice bandit problem under marketing fatigue. The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19), 2019.
[3] Nicolo Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 1404-142, 2012.
10

---

[4] Wei Chen, Yajun Wang. Yang Yuan, and Qinshi Wang. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. The Journal of Machine Learning Research, 17(1):1746-1778 2016.
[5] Richard Combes, Mohammad Sadegh Talebi Mazraeh Shahi, Alexandre Proutiere, et al. Com- binatorial bandits revisited. In Advances in Neural Information Processing Systems, pages 2116-2122 2224,,2242222 2015.
[6] Nick Craswell, Onno Zoeter, Michael Taylor, and Bill Ramsey. An experimental comparison of click position-bias models. In Proceedings of the 2008 international conference on web search and data mining. pages 87-94. ACM, 2008.
[7] Thomas Desautels, Andreas Krause, and Joel W Burdick. Parallelizing exploration-exploitaaioo tradcoff's in gaussian process bandit optimization. The Journal of Machine Learning Research, 15(3333873,322, 2014.
[8] Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. Proceedings of the Confer- ence on Unceriainty in Artificial Intelligence (UAI), 2011.
[9]
Gauthier, Romaric Gaudel, and Elisa Fromont. UniRank: algorithms for online ranking. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pages 7279-7309, PMLR, 2022.
Unimodal bandit
[10] Alihan Huyuk and Cem Tekin. Analysis of thompson sampling for combinatorial multi-armed bandit with probabilistically triggered arms. In Proceedings of the Secony--ecood International Conference on Artificial Intelligence and Statistics, volume 89, pages
PMLR, 2019.
[11] Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Online learning under delayed feedback. In International Conference Machine Learning, pages 1453-1461, 2013.
[12] Sumeet Katariya, Branislav Kveton, Csaba Szepesvari, and Zheng Wen. DCM bandits: Learning to rank with multiple clicks. In Proceedings of The 33rd International Conference on Machine Learning, pages 1224-1224. PMLR, 2016.
[13] Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning to rank in the cascade model. International Conference on Machine Learning, pages 767-776. 2015.
[14] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Combinatorial cascading bandits. In Advances Neural Information Processing Systems, pages 1458, 2015.
[15] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial
In AISTATS, 2015.
[16] John Langford, Alexander Smola, and Martin Zinkevich. Slow learners are fast. arXiv preprint arXiv:0911.0491, 2009.
[17] Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 2071-2080. JMLR. org, 2017.
[18] Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In ICMI,, volume 16, pages 1245-1253, 2016
[19] Gergely Neu, Andras Antos, András György, and Csaba Szepesvári. Online markov decision processes under bandit feedback. In Advances in Neural Information Processing Systems, pages 1804-1812, 2010.
[20] Daniel Vial, Sujay Sanghavi, Sanjay Shakkottai, and R. Srikant. Minimax regret for cascading bandits. In Advances in Neural Information Processing Systems, volume 35, pages 29126 338 2022.
[21] Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-handits, arXiv preprint arXiv:1803.04623, 2018
11

---

[22] Marcelo J Weinberger and Erik Ordentlich. On delayed prediction of individual sequences. IEEE Transactions on Information Theory, 48(7):1959-1976, 2002.
[23] Jiaqi Yang and De-Chuan Zhan. Generalized delayed feedback model with post-click informa- tion in recommender systems. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 16192-26203. Curran Associates, Inc., 2022.
[24] Yiping Yuan, Ajith Muralidharan, Preetam Nandy, Miao Cheng, and Prakruthi Prabhakar. Offline Reinforcement Learning for Mobile Notifications. In Proceedings of the 31st ACM International Conference Information & Knowledge Management, pages 3614-3623, Atlanta
GA USA, October 2022. ACM.
[25] Zixin Zhong, Wang Chi Chueng, and Vincent YF Tan. Thompson sampling algorithms for cascading bandits. The Journal of Machine Learning Research, 22(():9915 15-9980, 2021.
12


Reviews:
[{"review_id": "wITDcpztAH", "reviewer": "Reviewer_GPGp", "summary": "The paper considers a bandit setting where the agent selects a list of messages to be sent one at a time in a time window of length $D$. For each message, the user may be attracted (and sent a reward) or not (in which case she may leave the system with a probability that depends on the frequency of the messages).\n\nThe authors propose an algorithm to identify the optimal sequence of messages (including their size) if the parameters are known, and use it to derive two UCB-like algorithms dedicated to this setting. The first algorithm treats the messages and users as independent entities, while the second is dedicated to the contextual setting, where the attraction probabilities depend on known characteristics of the messages and the abandonment probability depends on known characteristics of the user.\n\nThe regret of the first algorithm is theoretically bounded, and some experiments compare both algorithms and epsilon-greedy.", "questions": "Do you know how to derive an instance-dependent proof  (and a proof of the corresponding lower-bound) ?", "limitations": "There is no section dedicated to the limits of the proposed approach.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The main strengths of the paper are the proposed setting and the derivation of the optimal solution for this setting when the parameters are known.  \nRegarding the setting, the notion of delayed feedback is not new. However, (i) the sending of messages one at a time, (ii) the dependence of the abandonment probability on the message frequency, and (iii) the distinction between attraction and reward, are interesting from an application point of view.\n\nTwo UCB-like algorithms are proposed, but they are simple.\n\nSimilarly, the experiences are interesting but remain of little impact since the setting is new and there is no baseline apart from $\\epsilon$-greedy.", "weaknesses": "The theoretical analysis is limited to the worst-case regret and covers only the algorithm for independent arms.\n\nApart from this weakness,  I have a comment: The literature on click models includes a click model with probability of leaving the system: the *dependent click\nmodel*. This model is used in the bandit setting in \n\n> S. Katariya, B. Kveton, Cs. Szepesvári, and Z. Wen. DCM bandits: Learning to rank with multiple clicks. In Proceedings of the 33rd International Conference on Machine Learning, pages 1215–1224, 2016.\n\nor by generic click-models algorithms such as TopRank (cited in the appendix) or UniRank\n\n> Camille-Sovanneary GAUTHIER · Romaric Gaudel · Elisa Fromont. UniRank: Unimodal Bandit Algorithms for Online Ranking. ICML'22\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for commenting that our paper is technically solid. We answer your questions below:\n\n>Apart from this weakness, I have a comment: The literature on click models includes a click model with probability of leaving the system: the dependent click model. \n\nThanks for your comments on the references. We have added the two papers that you mentioned in the section of literature review in the revised paper.\n\n>Do you know how to derive an instance-dependent proof (and a proof of the corresponding lower-bound) ?\n\nRegarding the instance-dependent upper bound and lower bound, we can derive the result similarly following Theorem 2 and Theorem 4 in the paper [Cascading bandits: Learning to rank in the cascade model], combined with the technique that we have used in the paper to deal with multiple interactions and the delayed feedback. We have added the comment to the paper, but due to the space limit, we mainly focus on the instance-independent regret. \n\nCascading bandit is a special case of our proposed model. [Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits] has derived lower bound as $\\Omega(\\sqrt{NMT})$. Moreover, [Online Learning under Delayed Feedback] has shown the regret of $O(\\sqrt{NTlog T}+NE[\\tau])$. Our setup is more complicated since there are more unknown parameters that need to be learned (probability of abandonment), and the feedback is received in a delayed manner. The regret bound for our proposed algorithm is $O(\\max(N,M^2)\\sqrt{T}+N\\tau)$. From the comparison to two special cases, we can see that regret is optimal in $T$ as well as the delay duration. We have added this discussion in the revised paper.\n\nThank you very much for your helpful review! We hope we have addressed your concerns satisfactorily.\n"}, {"review_id": "dHy1xS1cZn", "reviewer": "Reviewer_TbT8", "summary": "This work introduces a new variant of cascading bandit that differs with the classical cascading bandit in the following ways: (1). the user might abandon the system with certain probability depending on the list length; (2). the list length is some variable to be optimized (even could be contextualized), instead of fixed in advance; and (3). the list could be adaptively updated as more user feedbacks coming in. This new variation is closer to real-world settings such as notification/personalized recommendation systems. \n\nThe paper proposes a dynamic programming approach for finding the optimal length and optimal list periodically and extend it to the contextualized setting where the relevance and abandon probability is a function of contextual features. Some simple synthetic experiments verify the effectiveness of the method compared with epsilon-greedy based approach.\n", "questions": "- Do we need to have a fixed list of messages? How the algorithms adapted to the new possible messages that arrive at different time-steps?\n\n- One thing confused me is that whether the learned list length $m$ is updated in each DP? or it is only computed and fixed on the first round? \n\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- The setting this paper studies, extending from classical cascading bandit, is closer to real-world applications. The modeling/assumptions are realistic and not deviate that much more from the use-cases. I do like the new formulation. \n\n- The paper provides theoretical understanding of the non-contextualized case, the dynamic programming approach is intuitive and interesting, the regret compared with the optimal list and list length is given. The paper further extends it to the non-contextualized case, allowing parametric form of the relevance and abandon probability. The method is solid and the analysis seems valid. \n\n- The paper is very well-written. It motivates the problem in a crystal clear way and thoroughly listed the difference compared with the previous approach. I enjoy reading the paper. ", "weaknesses": "- One thing i am concerned about is the computational feasibility of the method. It seems for each user, the exact DP is performed, which might be super expensive when the length list $m$ is large. Could the authors comment more on the computational aspect?\n\n- For the experiments, the author mentioned that the features is based on the real-world dataset, but the model parameters are being simulated. I am wondering how the real-world features help here? It seems to me closer to a fully synthetic set-up. Could the authors comment more on this aspect?\n\n- Following this, it seems the experiment is performed in a very small scale. In real-world scenarios, the number of available messages might be very large, and also the length of the list. Could the authors compare the proposed method in a larger scale experiments, preferably more real-world scenarios?\n\n- It seems there are also RL based approach for solving the notification problem [1], have the authors thought of this aspect and it would be great to add literature review on this aspect and discuss the pros/cons, even empirical comparison? \n\nRef: [1]: https://arxiv.org/abs/2202.03867", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your great comments! Please see our point-by-point response below.\n\n>One thing I am concerned about is the computational feasibility of the method. It seems for each user, the exact DP is performed, which might be super expensive when the length list $m$ is large. Could the authors comment more on the computational aspect?\n\nThank you for your comment. Instead of enumerating all possible lists, the computational complexity of our basic DP (Alg.1)  is polynomial in $m$. Consequently, Alg. 2 should also operate in polynomial time for each time step. Therefore, we believe that the computational feasibility is acceptable in practice. Even in scenarios where multiple users enter our system simultaneously, they will share the same optimal message sequence. Thus, this won't significantly increase the computational complexity when applied to a real recommender system. In addition, in numerical trials, we found the computational efficiency of our algorithm superior to many others which need to enumerate possible lists or combinations.\n\n> For the experiments, the author mentioned that the features are based on the real-world dataset, but the model parameters are being simulated. I am wondering how the real-world features help here? It seems to me closer to a fully synthetic set-up. Could the authors comment more on this aspect?\n\nThanks for your question. We estimate parameters from the real-world dataset. To be more specific, in our experiment, we first estimate $q(1)$ from the difference between the proportion of single recommendations and clicking actions of the first message among all records in the AmEx User Click dataset. Then we take the form of $q(m)=\\frac{1-\\exp(-km)}{1+\\exp(-km)}$. With respect to attraction probabilities, we find that real datasets often have a small v value (with a mean of 0.06 by K-S normality test, p = 0.033). Under this setup, our algorithm performs better than other benchmark algorithms. \n\n> Following this, it seems the experiment is performed in a very small scale. In real-world scenarios, the number of available messages might be very large, and also the length of the list. Could the authors compare the proposed method in a larger scale experiments, preferably more real-world scenarios?\n\nThank you very much for this constructive comment. The real dataset has about 75 messages in total. Based on your comment, we have run the experiment of 1000 messages and found out that our UCB-like algorithm has the ability to reduce regret by 22.71%, compared to the best baseline EpsilonGreedy. Therefore, the scale of our experiment is no less than realistic cases from an order-of-magnitude point of view. As discussed in our response to Weakness 1, our proposed algorithm has the potential of performing well when dealing with large-scale data. The performance of the experiments with large-scale data demonstrates the practical value of our proposed algorithm.\n\n> It seems there are also RL based approach for solving the notification problem [1], have the authors thought of this aspect and it would be great to add literature review on this aspect and discuss the pros/cons, even empirical comparison?\n\nThank you for pointing out the reference using the offline RL-based approach. We have added a brief discussion of RL related literature in the literature review. The problem that we studied can be potentially modeled as an RL problem, but the learning complexity would be much higher.\n\n> Do we need to have a fixed list of messages? How the algorithms adapted to the new possible messages that arrive at different time-steps?\n\nThanks for your insightful question. It is not necessary to have a fixed list of messages. Because the attraction probabilities of messages are estimated at each time step, we can always recompute the optimal sequence length and recommend the message with the highest UCB among all the messages available, without losing effectiveness when new messages show up. \n\n> One thing confused me is whether the learned list length $m$  is updated in each DP? or it is only computed and fixed on the first round?\n\nThanks to your comment, we added more description about the model setting to clarify that the list length $m$ is fixed for a single user and computed when a user enters the system, while $m$ is updated over time and might be different for users entering the system at different times. For each user, the learned list length is only computed and fixed during the first round. The algorithm can potentially be implemented in a way that the total number of messages sent to a single user is updated at each time step. However, if the frequency has changed during the recommendation process, it would be hard to evaluate the average frequency. Therefore, to ensure a straightforward and clear evaluation process, we fix the list length at the very beginning for each user.\n\nThank you very much for your helpful review! We hope we have addressed your concerns satisfactorily.\n\n"}, {"review_id": "hatB8tr6Ij", "reviewer": "Reviewer_MzDh", "summary": "This work studied a generalization setting of the cascading bandit model which has been explored in existing literature. In detail, beyond the existing cascade model, it allows delayed feedback from the user, different number of pulled arms at different time steps, and takes the action frequency into consideration.\nThis work provides and analyzed an algorithm for the setting with delayed feedback and proposed another one for the setting with personalized recommendation.\nNumerical experiments are presented to compare the performance of algorithms.\n\n\n\n====================\n\nI would like to keep the previous score after reading comments from other reviewers and the responses from authors.", "questions": "Major concerns are listed in the *Weakness* section, and some possible typos are as below:\n1. Line 26: 'multi-arm bandit' should be 'multi-armed bandit'\n2. Line 81: 'our work extends the cascading bandits literature include' should be 'our work extends the cascading bandits literature by including' \n3. Line 85: 'known a priori' should be 'known as a priori'", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper formulates a more realistic cascading bandit model. In detail, it generalized the existing model by taking delayed feedback, flexible length of recommendation list and action frequency into consideration.\n3. The motivation to study this novel setting is well explained and convincing.\n2. To help readers understand the formulation of the problem, Example 2.1 with Figure 1 provides a vivid instance.", "weaknesses": "1. The regret upper bound for Algorithm 2 is provided in Theorem 3.3, I think a detailed comparison to existing bounds should be provided here: \n    1. I guess Algorithm 2 also works for the traditional cascading bandit setting, how will the regret bound be in the traditional setting? Does it match the state-of-the-art bounds?\n    2. What is the corresponding lower bound in this novel setting? Are the upper/lower bounds tight?\n2. What is the key challenge to derive a bound for Algorithm 3 in the setting with personalized recommendation?\n3. In numerical experiments, Thompson sampling algorithms are not mentioned. I believe the authors should also compare Thompson sampling algorithms or explain the reason not to do so.\n4. The literature review does not seem to be complete. I think the author(s) may consider to mention the following works on cascading bandits:\n    1. Minimax Regret for Cascading Bandits https://proceedings.neurips.cc/paper_files/paper/2022/hash/bbb397739546de027bc81a2c2a8fb119-Abstract-Conference.html\n    1. Thompson Sampling Algorithms for Cascading Bandits\nhttps://jmlr.csail.mit.edu/papers/volume22/20-447/20-447.pdf\n    1. Analysis of Thompson sampling for combinatorial multiarmed bandit with probabilistically triggered arms\nhttps://proceedings.mlr.press/v89/huyuk19a.html", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to sincerely thank you for your effort in reviewing our paper.\n\n> The regret upper bound for Algorithm 2 is provided in Theorem 3.3, I think a detailed comparison to existing bounds should be provided here:\nI guess Algorithm 2 also works for the traditional cascading bandit setting, how will the regret bound be in the traditional setting? Does it match the state-of-the-art bounds?\nWhat is the corresponding lower bound in this novel setting? Are the upper/lower bounds tight?\n\nThanks for your question. Since the problem is built on a new model, typical ‘existing bounds’ do not exist. Following your suggestion, we compare our results with classical cascading bandits. Cascading bandit is a special case of our proposed model. [Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits] has derived lower bound as $\\Omega(\\sqrt{NMT})$. Moreover, [Online Learning under Delayed Feedback] has shown the regret of $O(\\sqrt{NTlog T}+N E[\\tau])$. Our setup is more complicated since there are more unknown parameters that need to be learned (probability of abandonment), and the feedback is received in a delayed manner. The regret bound for our proposed algorithm is $O(\\max(N,M^2)\\sqrt{T}+N\\tau)$. From the comparison, we can see that regret is optimal in $T$ as well as the delay duration. We have added this discussion in the revised paper.\n\n> What is the key challenge to derive a bound for Algorithm 3 in the setting with personalized recommendation?\n\nThank you for this thought-inspiring question. Firstly, the analysis of contextual cascading bandits with delayed feedback shared similar challenges with non-contextual cascading bandits: 1) We allow dynamic content for active users who are remaining in the system, resulting in multiple interactions; 2) The feedback of individual messages may be delayed for a random amount of time and the frequency of the message dissemination across users could be different. Moreover, user feedback depends on both the choice of content and the dissemination frequency. \n\nSecond, the contextual cascading bandits have additional challenges. In Algorithm 3, the parameters corresponding to clicking and leaving probability both need to be estimated, and their estimation error depends on several characteristics including $x$ and $w$. The parameters need to be estimated through supervised learning oracles for generalized linear function. In addition, because of the abandonment behavior, we can only observe partial feedback.\n\n> In numerical experiments, Thompson sampling algorithms are not mentioned. I believe the authors should also compare Thompson sampling algorithms or explain the reason not to do so.\n\nThank you for this very constructive suggestion. Following your comment, we additionally implemented two Thompson sampling-based algorithms for the standard setting (TS-Cascade) and personalized recommendation setting (LinTS-Cascade) in the second paper you mentioned. We compare the performance of our proposed algorithms and benchmarks including Thompson sampling algorithms with the same setting described in our paper, and the results are shown in the two figures in the attached PDF file. In the non-contextual setting, we run each algorithm independently for 100 times, and the average regret of TS-Cascade at T=30,000 is 1289.01, with a 95% confidence interval of (1098.93, 1479.07). Thus, UCB outperforms TS-Cascade in our experiments. In the contextual setting, we run each algorithm independently for 50 times, and the average regret of LinTS-Cascade at T=3,000 is 367.26, with a 95% confidence interval of (331.74, 402.79), which is also worse than ContextualUCB.\nMeanwhile, although our results indicate that our two UCB-like algorithms outperform these benchmarks, we would like to clarify that the focus of this paper is to formulate a more realistic and generalized cascading bandit model and propose appropriate algorithms to solve it, as you mentioned in the strengths section. \n\n> The literature review does not seem to be complete. I think the author(s) may consider to mention the following works on cascading bandits:\n\nThank you very much for pointing out these papers. We have added them in the section of literature review.\n\n> some possible typos are as below:\n   Line 26: 'multi-arm bandit' should be 'multi-armed bandit'\n   Line 81: 'our work extends the cascading bandits literature include' should be 'our work extends the cascading bandits literature by including'\n   Line 85: 'known a priori' should be 'known as a priori'\n\nThanks for your comments. We have fixed these typos.\n\nThank you very much for your helpful review! We hope we have addressed your concerns satisfactorily.\n"}, {"review_id": "FnjzaQSdSt", "reviewer": "Reviewer_RjMs", "summary": "This paper introduces several modifications to the cascading bandit setting to make it more suitable for settings where users can provide delayed feedback and abandon the system in response to receiving messages too frequently, such as online ad retargeting. It then provides an algorithm for solving the message queueing optimization problem given a fixed set of parameters describing the user/environment, then a UCB-style algorithm for learning the user/environment parameters while making decisions. It then provides regret bounds for its algorithm and provides experiments for the non-contextual and contextual setting.", "questions": "1) Should Algorithms 2 and 3 call Algorithm 1 with q^LCB instead of q^UCB? The optimism in the face of uncertainty heuristic is based on always using upper bounds on how good something is, and it seems that the upper bound on $\\gamma$ would be obtained using the lower bound on q instead of the upper bound. For example, in [1] the PrimalDualBwK Algorithm on page 23 uses the lower bound on resource consumption instead of the upper bound.\n2) How important is the restriction to a fixed message frequency for a given message queue length? It seems that most things will email me more at first and then less later.\n3) Is there also an assumption that the user delay is uncorrelated with the click probability? If so, it would be good to mention it since it seems plausible that users who ultimately click are likely to provide feedback sooner.", "limitations": "The limitation of potentially shifting user preferences was mentioned, though I would also re-iterate in the limitations section the uniform dissemination frequency mentioned earlier on in the paper.\n\nThis research seems to have similar societal impact to most other work on bandits applied to online advertising.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality/Significance: The authors propose a modification to cascading bandits which allows for delayed feedback and user abandonment, which make it substantially more applicable to several problems such as re-targeting in online advertising.\n\nQuality: The paper includes algorithms for the contextual and non-contextual cases, as well as a regret proof and experiments. Their proposed method is clearly supported by the evidence provided.\n\nClarity: Writing was generally clear.", "weaknesses": "1) The UCB heuristic seems to me like it may be mis-implemented in Algorithms 2 and 3, since it uses the UCB of q instead of the LCB. See question 1 for more details.\n2) The experiments don't compare to a normal cascading bandits baseline.\n3) If I understand correctly, each message can only be used once. While the setting is substantially more realistic than cascading bandits, this still seems like a restrictive assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your commenting that our writing is generally good. Please find our point-by-point responses below.\n\n> Should Algorithms 2 and 3 call Algorithm 1 with $q^{LCB}$ instead of $q^{UCB}$? The optimism in the face of uncertainty heuristic is based on always using upper bounds on how good something is, and it seems that the upper bound on $\\gamma$ would be obtained using the lower bound on q instead of the upper bound. For example, in [1] the PrimalDualBwK Algorithm on page 23 uses the lower bound on resource consumption instead of the upper bound.\n\nThank you for this comment. Following your comment, we have added discussion to Section 3.1 of our paper to clarify the intuition of upper bound. Note that $q(m)$ is the probability of examining the next message, so if we optimistically estimate the sequence, we should use the upper bound of the resuming probability. Also, Lemma 3.2 has proved this property rigorously.\n\n\n> The experiments don't compare to a normal cascading bandits baseline.\n\nThank you for this constructive comment. Following this comment, we have added experiments to compare our algorithm to two Thompson sampling-based algorithms: TS-Cascade for standard setting and LinTS-Cascade for personalized recommendation setting [2]. The two algorithms are proposed based on a normal cascading bandits model. We compare the performance of our proposed algorithms and baselines including Thompson sampling algorithms with the same setting described in our paper, and the results are shown in the two figures in the attached PDF file. In the experiments, our proposed UCB-like algorithms outperform the Thompson sampling-like algorithms, with the 57.32% reduction in regret by time T=30,000 for the non-contextual case in 100 independent runs and the 19.97% reduction in regret by time T=3,000 for the contextual case in 50 independent runs. Intuitively, our proposed algorithms are specialized to the modification setting in our paper, which is a generalization to the normal cascading bandits model. By contrast, the Thompson sampling-like algorithms are for the normal setting, and they don’t take the delayed feedback and user abandonment into consideration.\nRef: [2] Thompson Sampling Algorithms for Cascading Bandits https://jmlr.csail.mit.edu/papers/volume22/20-447/20-447.pdf\n\n> If I understand correctly, each message can only be used once. While the setting is substantially more realistic than cascading bandits, this still seems like a restrictive assumption.\n\n Thanks for your great comment. Our algorithm can also apply to the case where messages can be recommended repeatedly, with a modification of line 8 in Algorithm 2 or line 7 in Algorithm 3 that $O^r$ is not excluded from the candidate messages. Moreover, if we want to constrain the total number of repetitive displays of one message as $B$, we can create $B$ copies of that message in the candidate set.\n\n> How important is the restriction to a fixed message frequency for a given message queue length? It seems that most things will email me more at first and then less later.\n\nThanks for your question. A fixed message frequency for a given message queue length is a simplified assumption in our model. The purpose is to capture the tradeoff between the total number of messages that can be disseminated and the probability of abandonment. If the frequency has changed during the recommendation process, it would be hard to evaluate the impact of frequency. Therefore, to ensure a straightforward and clear evaluation process, we fix the frequency for each user. We have added a short discussion in the revised paper.\n\n> Is there also an assumption that the user delay is uncorrelated with the click probability? If so, it would be good to mention it since it seems plausible that users who ultimately click are likely to provide feedback sooner.\n\n\nThanks for your great comment. We do have such an assumption. We have added this assumption in the revised version of the paper.\n\nThank you very much for your helpful review! We hope we have addressed your concerns satisfactorily.\n\n\n"}]

Author rebuttal:
We thank all reviewers for their time and insightful comments to improve our paper. We appreciate the positive feedback. We provide clarifications below.

Meta-review: This paper studies a generalization of cascading bandit. In particular, it considers a setting that allows delayed feedback and different numbers of pulled arms at different time steps, and takes the action frequency into consideration. This paper proposes and analyzes algorithms for the considered problem, and demonstrates some experiment results.

Most reviewers recommend to accept this paper. After reading the paper, the reviews, and the rebuttals, I think the strengths of this paper outweigh its weaknesses, and recommend accepting this paper as a poster.
Decision: Accept (poster)