True Impact of Cascade Length in Contextual Cascading Bandits
Authors: Hyunjun Choi
Joongkyu Lee
Min-hwan Oh
Venue: NeurIPS 2025 poster ()
Keywords: contextual bandit
cascading bandit
upper confidence bound
online leaning
Primary area: theory
TL;DR: We show that in contextual cascading bandits, regret vanishes as the cascade length grows, with nearly matching upper and lower bounds.

Abstract: We revisit the contextual cascading bandit, where a learning agent recommends an ordered list (\emph{cascade}) of items, and a user scans the list sequentially, stopping at the first attractive item. Although cascading bandits underpin various applications including recommender systems and search engines, the role of the cascade length $K$ in shaping regret has remained unclear. Contrary to prior results that regret grows with $K$, we prove that regret actually \emph{decreases} once $K$ is large enough.
Leveraging this insight, we design a new upper-confidence-bound algorithm built on online mirror descent that attains the sharpest known regret upper bound, $\tilde{\mathcal{O}}\bigl(\min \lbrace K\bar{p}^{K-1}, 1 \rbrace d \sqrt{T}\bigr)$ for contextual cascading bandits. To complement this new regret upper bound, we provide a nearly matching lower bound of $\Omega \bigl(\min \lbrace K\underline{p}^{K-1}, 1 \rbrace d \sqrt{T}\bigr)$, where $0 \leq \underline{p} \leq \bar{p} < 1$. Together, these results fully characterize how regret truly scales with $K$, thereby closing the theoretical gap for contextual cascading bandits.
Finally, comprehensive experiments validate our theoretical results and show the effectiveness of our proposed method.

True Impact of Cascade Length in Contextual Cascading Bandits
Hyun-jun Choi Seoul National University nschj 1@snu. ac.kr
Joongkyu Lee Seoul National University jklee07170snu.ac. kc.
Min-hwan Oh
Seoul National University minoh@snu, ac kr
Abstract
We revisit the contextual cascading bandit, where a learning agent recommends ordered list (cascade) of items, and at the first attractive item. Although cascading bandits underpin various applica- tions including recommender systems and search engines, the role of the cascade length K in shaping regret has remained unclear. Contrary to prior results that regret grows with K, we prove that regret actually decreases enough. Leveraging this insight, we design a new upper-confiidence-ooiie rithm built on online mirror descent that attains the sharpest known regret upper bound, Ô Omiin
the list sequentially, stopping
K is large algo-
K KFk-1_ I)dvT) for contextual cascading bandits. To comple- ment this new regret upper bound, we provide nearly matching lower bound of 9 ([min((K)) Kp 1)dvT). where 0 S < 1. Together, these results fully characterize how regret truly scales with K, thereby closing the theoretical gap for contextual cascading bandits. Finally, comprehensive experiments validate our theoretical results and show the effectiveness of our proposed method.
Introduction
Cascading bandits have broad applications online recommender systems, search engines, and social media. In this model, each round, the agent selects an ordered list (a cascade) of K items from a ground set to click it skip to the next. The round stops the first click or when all K items have been examined without any click. Therefore, the agent receives the partial click feedback only for the observed items in the given cascade. Cascading bandits have been extensively studied from the non-contextual multi-armed formulation [I] 26 to contextual variants incorporating item (and user) features [19 18 28 26 20 (11. providing widely used framework for modeling sequential user interactions with multiple items.
items. The user examines each item in order and decides whether
In contextual cascading bandits, the effect of the cascade length K the regret bound remains theoretically unclear. While previous studies suggest that the regret either scales polynomially or logarithmically with K (see T.) this contradicts the intuition that longer cascade provides more opportunities to collect feedback and may therefore reduce regret. The gap between theory and intuition regarding how the cascade length affects the regret has been recognized [28] 20 and recent studies 21 have narrowed this gap, though it has yet to be fully resolved.
Li et al. 19 first introduced the contextual cascading bandits and derived regret upper bound that scales as O(VK) by exploiting the Lipschitz continuity of the expected reward. Recent studies have further refined the dependence of regret on the cascade length by analyzing different click feedhack models. Liu et al. 20 considered the case where the click feedback follows linear model, whereas Choi et and Liu et [21] focused on the logistic model. These three works investigated common structural property that the gradient of the expected reward function can be expressed as
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Comparisons of algorithms for cascading bandit. N is the number of ground arms, K is a cascade length, d is a dimension of context vectors and T is total rounds. Here, 0 $ $ p 1 (See Definition 5.2 and K E (0, 1/4] (See Assumption 5.3
Algorithm Puper
Model
Bound
Dependence
CascadeKL-UCE
(Non conteeelx)
o ((N - K) Pez(s-A1 Al
log
Decreasing
Lower Bound
II
(Non-contextual)
9 2((N K) DNLG A315)) Ing
Decreasing
C²-UCB 19
Linear
OldyKTlog log
Increasing
LinIS-Cascade 23
Linear
Increasing
CascadeWOFUL 20
Lincar
O + JTT
Increasing
VAC*-UCB [0)
Lincar
OldyTlog(kT))
Increusing
UCB-CCA 7
Logistic
O1AdyTlog(KT)
Incrensing
UCB-CCA+
Logistic
O(dvTlog(KTT)
Increusing
CLogUcB 21
Logistic
old/ (ogg(K))) Vidy/Tloo(AT
Increasing
VA VA-CLogUCB 4
Logistic
Increusing
EVA- CLogUCC
A1
Logistic
OldyTlog(KT))
Increusing
UCB-CLB (this work, Theorem 5.6
Logistic
[iiu [K 1.l."""..dolooooo. (JdyTTog(AT)) Q min (Kpp"1_1ddv7
Decreasing large K
Lower Bound (this work. Theorem 5.7
Logistic
Decreasing for lurge K
These non-contextual results are gap-dependent regret bounds under symmetric instance, where each optimal item has a click probability p and each suboptimal item has p - A for some E (0,p). (pll)) denotes the Btl/bacck-Libblc (KL) divergence between two Bernoulli distributions with means and q.
** Although present our main results for the logistic model model-reflccctng the hinary "click" feedback observed in practice-the analysis also carries over to the linear model, hence our results are comparable to existing linear model results, well logistic model results.
a product of non-click probabilities. Specifically, Choi et al. 7 combined this property with the optimistic exposure swapping technique, which places the most uncertain item first in the cascade, while Liu et al. [20] and Liu et al. [21] leveraged the triggering probability equivalence technique, which links the probability that an item is observed to the random event of that item being observed. These approaches yielded tighter regret bounds of order Odv' log( KT)), demonstrating that the regret no longer grows polynomially with the cascade length but still grows logarithmically.
On the other hand, the con-contextual cascading bandit literature characterization of how the cascade length affects regret. Kveton al. established gap-dependent upper and lower bounds, explicitly scaling with the difference between total number of arms and cascade length (N K). Under a symmetric instance, where each optimal item has click probability
provides a more explicit
and each suboptimal item has A for some A E (0, O(N - K) Dper log I') regret upper bound is shown, along with matching lower bound (up to logarithmic factors of A) of Q((N K)) (p-Alpp log T). These results indicate that the regret decreases as increases (i.e., as K approaches N). Yet, a direct translation of these bounds to contextual cascading bandits is unclear, since regret bounds typically exhibit explicit dependence on N in contextual settings.
A(++log(/AA)
In this paper, we address this long-standing open question in the contextual cascading bandits:
What is the true impact of the cascade length on the regret bound?
We show that the regret bound of contextual cascading bandits shrinks zero for sufficiently large cascade length. Our analysis begins with the contextual logistic cascading bandits where the binary click feedback follows logistic model. Within this framework, we propose new UCB algorithm with an online mirror descent method effectively exploiting the cascading structure and integrating the optimistic exposure swapping technique proposed by Choi et al. [7]. To establish its thcoreti- cal guarantee, we derive the tightest known regret upper bound for contextual cascading bandits, Ó(min ([min(KF*<1 K 1} dvT), overcoming the technical challenges inherent to the cascade structure. Unlike previous results 7 21 that scale (ddTT), our bound introduces the multiplicative factor

---

Kp* revealing that the regret can decrease with larger cascade length. This result is further supported by matching problem-dependent regret lower bound, which confirms the correct K- scalability of our upper bound. To the best of our knowledge, this is the first lower bound analysis for contextual cascading bandits. Finally, the proposed analysis is directly applicable to the contextual cascading linear bandits, where the regret bound O(min [Kp ( 1) dyT)) remains valid, demon- strating that the K term captures intrinsic property of the cascade structure rather than peculiarity the feedback model.
Our main contributions are summarized as follows.
We propose UCB algorithm for cascading logistic bandits and establish the Ttse regret upper bound Omin (KpK-1, 1 dv/)) where 0 S p < 1 (Theorem 5.6
To our best knowledge, this regret upper bound is the tightest bound among all the existing regret bounds for contextual cascading bandits. In contrast previous studies that suggest the bound increases with K, our finding demonstrates that the regret bound decreases with sufficiently large K.
By leveraging online mirror descent for parameter estimation in cascading logistic bandits, our algorithm achieves constant per-round computational and storage costs, independent of T, thereby ensuring computational efficiency.
We also derive N-independent lower bound the regret in cascading logistic bandits dvT) (in Theorem 5.7). where 0 S p S < 1. To the best of our knowledge, this is the first derivation of lower bound in contextual cascading bandits.
Q(min { K K-1 1
We show that the regret bound derived in the logistic setting also holds in the linear model under mild assumptions, highlighting the generality of our theoretical results.
Inefficient Dependence on Cascade Length
In contextual cascading bandits, the true impact of cascade length on the regret bound still remains unresolved to this day. As summarized in Table [] all existing regret upper bounds for contextual
7 21] are either ((KvVT) or ÖddVT) However, simple these existing results. We conduct experiments to observe how cumulative regret evolves with varying cascade length K. This experi- ment is based on the MovieLens 1OOK datase and we defer the experimental details to Section 6 We gradually increase K, with all other conditions held constant across bandit instances. As shown in Figure [ our result presents counterexample: cumulative regret decreases as K increases for all existing methods. Hence, the previous theoretical claim that regret either worsens or remains unaffected by increasing K not supported by experimental results.
cascading bandits 19 28
26
20
experiments cast doubt on the implication of K dependence
UCB-CCA, N=1682, d=25
CLogUCB, N=1682, d=25
VA-CLogUCB, N=1682, d=25
300
Curulaaive Regret
Cumullstive stive Regret
Curulaative Repret
150
200
4.00
4000
5000 5000
10000
2000
4000
8000
10000
4000 8000 8000 Round
Round
Figure 1: Cumulative regret over time for UCB-CCA (7). CLogUCB 21 and VA- VA-CLOBUCB 21 with N 1682, d = 25, and varying cascade lengths K E (1,2,3,4). In all methods, increasing the cascade length leads to a clear reduction in cumulative regret?".
Furthermore, the claim that regret grows with is also counterintuitive. By definition, regret the difference hetween the expected reward of the optimal cascade and that of the cascade selected by the
Still, these results retain a logarithmic dependency on K. Available at httttpps://rooplerrrt http:////oooppppoooo/////aaaaaap

---

agent. In cascading bandits, the expected reward of a cascade is generally defined as the probability that least one arm in the cascade yields positive feedback When all other conditions are kept constant, increasing the cascade length provides the agent with more opportunities to receive positive feedback. This leads the expected reward of the selected cascade to increase. For the same reason, the expected reward of the optimal cascade also increases as the cascade length increases.
Our intuition and experiments suggest that prior claims about how cascade length affects regret are incomplete and possibly loose. Surprisingly, explicit discussion of this issue is scarce in the literature. We therefore establish a rigorous, refined regret bound that reveals how cascade length fundamentally influences regret in cascading bandits.
3 Preliminaries
3.1 Notation
Define [n] as the set of positive integers from to n. Let |-| be the length of a sequence or the cardinality of a set. For a vector x E RR, we denote the f2-norm of x as ||||| and the V-weighted norm of æ for positive-definite matrix V as | = vx Vx. The determinant and trace of matrix V are (V) and (Vace(V), respectively. Amin denotes the minimum eigenvalue of a matrix V. La E gaxd is an identity matrix.
3.2 Problem Setting
We begin by outlining the structure of the contextual cascading bandit, followed by an extension that parameterizes the Bernoull feedback using logistic function.
The contextual cascading bandit framework models the interaction between a learning agent and the environment as follows: given a set I that consists of total arms, the agent offers list of K distinct arms to the environment, which refer as a cascade. The set of all possible cascades is denoted by II := ((k)) f1,.... ig E I, it * im for any k * m}. At each round t, the environment reveals a contextual feature vector Ft.; Rdd for each arm E I, collectively denoted by X, == { hezz- Based on the history H, and the revealed feature vectors X the agent selects a cascade C. = (fe1, .., ix) II, where iek is the k-th arm in C.. For any arm is E Cr. we define Ut E 1) the binary feedback provided by the environment to the agent, where I indicates positive feedback (i.e., click). Starting from the first arm 4n the agent sequentially observes feedback for each arm in C.. Upon receiving feedback Vt,a 1, the round immediately terminates, halting further observations for remaining arms 4 k 4nk- Let k == min (fm E [K] yt.sem 1) U {K + 1)), which denotes the position of the first clicked item in round f, or K + if no click occurs. We define the list of observed arms in round t as k < min K)).
O = (iek
The reward of agent who chooses cascade C, in round t defined as if at least one arm in C. yields feedback of 1; otherwise, the reward is O. Formally, this can be expressed as:
re(C,))
max De, V Vt, seC,
II (1 st.)). sEC,
sEC,
This type of reward structure is referred to as a disjunctive model 12 19, in which the agent receives reward if any arm within the cascade provides positive feedback. This model is well suited to recommender systems, where success is achieved if at least one recommended item satisfies the user.
Building on the framework described above, we study the cascading logistic bandil, which integrates a logistic parametric model to account for the Bernoulli feedback. Since the logistic model is better suited to handle binary feedback than the linear model, it has gained attention in recent cascading bandit literature 7 (2)) Specifically, given the history H. == (X,, C,, O,, Yr rr U(X,, Ct). the feedback Vt, for all i I are modeled as mutually independent Bernoulli random variables. Let σ1 = / + exp(=)) and (2(2) = 1 1- (2). The conditional expectation of yr, is parameterized using a logistic function [yc. [H.] = 0 (x) where 0" E Rd is an unknown
TThis is commonly referred to cascading bandits with a disjunctive objective.

---

time-in inveriivrrinn parameter. The expected reward of C₁ is then given by:
((r)(Ci) Hi] =
II (1 - a1 (x, f(C,,)))
SEC,
The optimal action O E argmaxcen fc 8*) in round is defined as the cascade that maximizes the expected reward. The objective is to maximize the cumulative expected reward over T rounds by efficiently learning the unknown parameter 0* To evaluate the performance of an online learning bandit algorithm, the regret, defined the gap between the expected cumulative reward of the optimal cascade C and that achieved by the algorithm's selection C, over 'T' rounds, is used. The formal definition of regret as follows:
T -
T E -
R(T) = E Σ -n(C))-r(Ci
(CC)
(2)
where the last equality is from the law of total expectation and the definition of the expected reward.
4 Algorithm
In this section, we introduce our algorithm, Upper Confidence Bound for Cascading Logistic Bandits (UCB-CLB), leveraging the widely used UCB technique 4 [1 to find optimistic action based on a well-established confidence set. The pseudocode of UCB- UCBBCLB is presented in Algorithm T UCB CCBB-LB consists of three key components.
First, it constructs a confidence set using parameter estimates obtained via online mirror descent (OMD), detailed in Section The use of OMD provides computationally and memory-efficiett alternative to maximum likelihood estimation (MLE), which has been adopted in logistic bandits [3) To the best of our knowledge, UCB-CIA is the first algorithm to incorporate OMD in the cascading bandit setting. Second, Section 4.2 explains how UCB-CLB efficiently selects a cascade by ensuring optimism through
exploration bonus. Rather than solving combinatorial optimization over (x) arms to find the cascade that maximize the estimated rewards, UCB-CLI CLB reduces this process to a simpler top- K arm selection procedure. Finally, Section 4.3 discusses the incorporation of optimistic exposure swapping. originally proposed by Choi al. 7 adapted to our problem setting. This technique aims to mitigate an issue arising from unobserved feedback, by strategically placing arms with higher uncertainty in the cascade.
Our main design goal is to develop a eascading bandit algorithm whose regret decreases for sufficiently large cascade length K. Since our setting assumes logistic model, we leverage insights from prior work S 2 on contextual logistic bandits, where the leading term of the regret is known to be independent of mooblem-dependerr factor K, formally defined in Assumption 5.3 To achieve both goals, our algorithm incorporates two key components: DO-SWAP for cascade restructuring and online parameter estimation via OMD.
4.1 Efficient Online Parameter Estimation
In the existing literature on logistic and multinomial logistic bandits 8 2 10 15 the maximum likelihood estimation (MLE) approach has been the common method for parameter estimation. To reduce computational and memory overhead. recent studies 9
have proposed online parameter estimation methods based on algorithms such as online Newton step and online mirror descent (OMD). Building on these advances (27 13 14), we adopt an OMD-based estimator tailored to the cascading bandit setting. This adaptation achieves constant computational complexity per round, providing substantial computational efficiency over MLE-based approaches.
27
13
The parameter is updated for each observation iez E O.. Let 0z,1 == Og and He, == He, where
H H Σ Σ
(1 Or (r Tri + Xla-
r= kE
Then, for k E [[Or]], we update the parameter 0,,411 using an online mirror descent 24 as follows:
- 10 0,, 12., (0, Vlyn (u.i))) o = =0 gd 10 < 1}. (3)
0, argmin PE0
2n
5

---

Algorithm 1 UCB-CLB
Algorithm DO-SWAP
Input: penalty X, radius 3r, step size 17. Initialize 01 E θ, H1 -Pd-
Input: cascade Ct, parameter lz. gram ma-
trix H,.
for to 1,..., T do
Find i, and i by (q.
Compute {u4,i 2T, 0t Be | n. her-
Swap the positions of in and i
if 1 * then
Select C₁ E argmaxcen fc) by (5.
Swap the positions of in and i!") end if
C + DO- DO-SWAP(CC, 0r, He).
Play Ct and receive feedback tuple (O,, Yi). 02,1 < Oz, Hr, t- H, for L...., 1001 do
Output: swapped cascade (%) ,46 1(a)
......
He,k f- He, + n/1 (x. lk Pe, T Thi Update 01,k41 by (3.
Hi,k+1 + H + ōg (2(22 0o, De 2 Time"
end for
O.+1 < 0110,111 Het1 + 0.1+1
end for
where Hr, H2 + (1 BI, Da Pia Here, for arm in round t under parameter the loss is defined as (0) == (o.) Ker = y log (xT, and its gradient is given by (0), (a (= 31,)) Fe.s.
To efficiently solve the optimization problem in Eq. 3
we perform a single projected gradient step.
02K+1 = O2, ,, V Veiin (0c,,), 02,0+11 E argmin |0 0 02,441 Br,a"
de0
Next, we update the gram matrix as follows:
H He, ( (e Fiate
This process is repeated in every round, ensuring the parameters and gram matrices are consistently updated for all observed arms.
The optimization problem in Eq. requires a computational cost of only O(Kd²), which is com- pletely independent of the round I. Since we update the parameter K times per round, the total computational cost is O(K2d') For storage costs, the estimator does not need to store all historical data because both He,k and He, can be updated incrementally, requiring only O(d2) storage.
4.2 Efficient Optimistic Expected Reward
We leverage the UCB technique to compute optimistic action based estimates of each arm. We compute our optimistic estimate ve, for all E [T) and E I as follows:
= T, 0: + Se II
(4)
where 3. 2 0 represents a confidence radius, with its specific value being provided in Section (.2 to ensure the necessary statistical guarantees. We define fc(CC) be the optimistic expected reward of the cascade C/ in round based on u,,;
M(0)= II oo(uu,))
(5)
SEC
Then, the agent identifies the cascade that maximizes T, in each round. As ao()) is monotonically decreasing function, maximizing ft simplifies selecting the top-K arms with the highest optimistic estimates Uz from E I.
Remark 1 (Comparison to Liu et al. 21 rithms introduced by Liu al. (1)) namely VA-CLogUCB and EVA- EVA-CLOgUCB. Similar to our approach, both algorithms adopt bonus-based method to induce exploration. However, our algorithm offers key
We compare our method, UCB-CLB, with the UCB algo-

---

advantages in terms of computational efficiency beyond statistical efficiency. Unlike VA-CLogUCE and EVA-CLogUCB, which rely on MLE, UCB-CLI CLB leverages online parameter estimation, signifi- cantly reducing computational and storage costs. Furthermore, VA- VA-CLogUCB requires a non-convex projection, which could NP-hard, to ensure statistical guarantees. -LLoUCBB eliminates this non-convex optimization process by introducing a burn-in stage of (loo T') rounds to construct convex vonlinearity-restrice region. However, EVA-CLA -LLLUCBBC requires an additional assumption that feature vectors remain time-invariant. Thus, our UCB-CIA -CLB applies to more general settings.
4.3 Doubly Optimistic Exposure Swapping
In this section, we introduce the doubly optimistic exposure swapping (DO-SWAP), which is technique that provides an alternative approach for handling unobserved feedback. We summarize the process of DO-SWAP in Algorithm [ In cascading bandits, there exists critical challenge that the learning agent cannot access feedback information for all arms in Ct. but only for the arms in O₁, i.e., the observed arms. Consequently, the Gram matrix H, is constructed solely from the feature information of the observed arms-whoss number may be strictly smaller than the cascade length-and is used construct the confidence set. As result, there is an issue where the leftover sum (from |O, to [Cx)) becomes out of control [19]. To address this issue, we exploit the doubly optimistic exposure swapping technique first introduced Choi et al.
DO-SWAP follows the following process. After finding C E argmaxcen f((C), the agent swaps in and it2, the first and second arms in Ct, with v and ( respectively, where
argmax σ1 (z) || ( argmax || H,
iEC.
rEC,
As side note, when efth 1 it suffices for the agent to swap 2(t) with the first positioned arm 4,,1 E C. Since the arm in the first position always observed (&, E O,), the following inequality holds and effectively avoids the aforementioned out-of-control issue:
Σ 201 (1(, || ll, K max ò (x) | = Ko (x 1,t
(r 0e)
:EC.
IEC.
Additionally, considering that the arm with the largest || in Cs is placed in the second position, the following equation holds:
Σ
| li,
K max
|| K 1,
.EC.
H
iEC.
A detailed discussion on how DO-SWAP affects the regret analysis is included in Appendix C.1
Regret Analysis
5.1
Regularity Condition
Before presenting our main theoretical results, we first introduce the regularity assumptions. Assumption 5.1.
|| < 1 for all round t and arms i E I. and also ||@*|| || < 1.
Assumption 5.1 ensures that the regret bound is independent of the scale of the feature vector and parameter, which standard assumption commonly adopted in the contextual bandit literature [I] 19 (2). Under Assumption 5.] we define the following constant related to the feedback probabilities:
Definition 5.2. Under Assumption
5.1
we define the following constants
==
sup (o(xT()))
P ::=
inf co(x') 0*).
La 1
2:||
These two constants play a critical role in expressing the true scaling of regret as the cascade length K becomes sufficiently large. (See Theorem 5.6 Theorem 5.7) Assumption 5.3. There exists i I and all round f.
such that ming.jje]ss1 01 (x.,, ( (0l ) 2 K. for every arm
The problem-dependent factor typically appears in the combinatorial logistic bandit literature 6 22 2X] and is adapted from standard link-function conditions the generalized linear contextual bandit literature [[7].. Note that smaller indicates larger deviation from the linear model.
7

---

5.2 Confidence Set
In this section, we aim to establish theoretically grounded confidence set for the parameter estimate f.k which plays a crucial role in constructing the upper confidence bound in our algorithm. Since
we update the parameter fe.k and the hessian matrix H for every and & E
[0,]] we can directly
apply the online confidence bounds previously studied in the recent work 27
13
14
Proposition 5.4 (Online parameter confidence set, Zhang and Sugiyama 27 Lee and Oh 13 14).
Let E (0, 1J. and denote the assoriment size as M. Under Assumption
5. set the step size
log 2 + 2 and penalty parameter X = 84v2dn. For each update time t [2'] we define the following confidence set with (6) ((vdlog
(6) = (0 < θ ||0 A1 S B(()))
Then, we have IP (Vt 1,0 E C())) 2 1 8.
Applying this result our problem setting, each assortment in our contains single item (since the agent receives binary feedback), Hence, our problem setting is special case with M = 1. Up round i, the algorithm performs one parameter update per observation, resulting in a total of Ex= 1 updates. Hence, we obtain the following result:
Corollary 5.5. Under the same setting with Proposition 5.4 for all t E [T] and E [[Orl]. with probability at least 6. we have Hr C(,k(0), where
Cr, (0) = - 0 110r - 0 H., S (0) =(val))(((())
5.3 Regret Upper Bound
Theorem 5.6 (Regret of UCB UCB-CLB). Suppose d 2 K. Set the step size 3 log 2 + 2 and penalty max (84v2dn, K.. Let 8 (0, 1]. With probability at least 1 8, and under Assumptions 5.1
and 5.3
CCB-CLBec ensures
R(T) = Ö min Kp KpK -d--
Kp K-
Kp K
d2 ,dVT - K
2)
df
Discussion of Theorem 5.6 This theorem highlights the interesting impact of cascade length K on regret, providing new insights. The dominant term of the regret upper bound in Theorem scales as Ó min KpK-1, 1,1 dV)), which exhibits a plateau-ther seateaa--the-ddereaasin behavior with respect to the cascade length K. To interpret this behavior, consider the term KpK-1, Since K is positive integer, Kp* is monotonically decreasing in when p S e-!. For larger values p (c.g., e < < 1), this term first increases from K and then eventually decreases, achieving its maximum Tog(1/p) However, the regret bound depends on the truncated quantity min K, 1}. Because of this truncation, the overall regret bound is non-increasing in K: it remains flat for small K and decreases once K becomes sufficiently large. This offers an intuitive understanding of how an increasing cascade length positively affects regret performance under such conditions. The proof of Theorem i.6 provided in Appendix C.T
K =
Remark 2 (Applicability to Linear Models). A regret bound of Ómin (KPK-1 1)dvT) can also be derived for the cascading linear bandits. The full derivation is provided Appendix Existing cascading linear bandit algorithms 19
18 26 combined with a swapping technique similar to DO-SWAP. In particular, the arm maximizing the confidence width || where V, = -==1 Eieo, Ir.a + XI is placed in the first position of the cascade. Deriving this bound in the linear setting requires assumption that p 1; that is, the probability of receiving positive feedback is assumed to be less than 1. This is because in the linear model, the feedback probability is defined xr,,0" [0, 1] in [19 26). The assumption of p being less than is often considered mild in practice- that is, every arm considered as candidates has least a (even very) small positive probability of being clicked.
20 can attain a regret bound of Ó
when
5.4 Regret Lower Bound
Theorem 5.7 (Regret lower bound of contextual cascading bandits). Let d be divisible by 4, and suppose that Assumption 5.7 holds. Suppose T 2 C dl for some constant C' > 0. Then, for any
8

---

policy R, there exists problem instance such that the worst-case expected regrer of π is lower bounded as follows:
sup Eg [T)) 2 min (Kpk-1, ,11 dvT).
The key observation is that the dominant term in our upper bound in Theorem 5.6 matches the lower bound up to logarithmic factors, lower-order terms and gap of p and p. indicating that the UCB-CLA achieves near optimal regret upper bound. The proof of Theorem 5.7 is deferred to Appendix D
Remark 3 (Comparison to Kveton et al. [T]). The lower bound for non-contexuall cascading bandits established by Kveton al. [11 in Theorem is QQ((N KK K)p² 1)))-)),, ignoring constant factors. In the non-contcxtual setting, regret necessarily depends on the total number of arms NN, whereas in the contextual setting, both upper and lower bounds of regret scale with the feature dimension d, not N. Hence, there is a need for an N N-independent lower bound for contextual cascading bandits. To this end, Theorem 5.7 provides the first N N-independent lower bound for contextual cascading bandits.
Numerical Study
In this section, we empirically evaluate the performance of our proposed algorithm, UCB-CLB, and compare it against three UCB-based baselines- UCB- CCB-CCA 77, CLogUCB (2T, and VA-CLogUCB [21] in the contextual cascading logistic bandit setting. We conduct simulated experi- ments with a real-world dataset: MovieLens 100K dataset. We transformed the dataset into a binary feedback setting, assigning label of 1 to ratings of 4 or 5, and 0 to ratings of 1, 2 or 3. To construct feature representations, we applied truncated SVD extracting 5-dimensional embeddings for 943 users and 1682 movies. For each user t and movie i, we computed the feature vector Jz, IR225 by taking the outer product of their embeddings and vectorizing the result. We choose the random unknown parameter 0* E RR2 In the online setting, user is sampled uniformly at random in each round t, and the agent selects an optimal movie from all 1682 movies (N 1682). Additional experimental details are provided in Appendix G To evaluate the effect of cascade length, we compare cumulative regret under two settings, K = 5 and = 10, with all other parameters held constant. The running time is reported here only for K 10.
N-1682, K-5 d-25
N 1682, K-10, d=25
N=1682, K-10, d-25
Cuogl-CS CD
CLogi WA-LossKC LER-CCA
Clogl CS
Cumulstive Regret
150
Cumulativ Regret
400
CLD
300
200
300
2000
4000
6000 8300
10000
2000
4000
6.00
8000
10000
2000
4,000
6000 8300
10000
Round (4)
Round (1)
Round (4)
Figure 2: Cumulative regret for varying cascade lengths (K 5, 10) and cumulative running time for K = 10 with N 1682 and d = 25. Error bars indicate standard error, and all results are averaged over 5 random seeds.
Cumulative Regret Comparison. Figure 2 (left two plots) presents cumulative regret curves for different algorithms under = 5 and K 10. Among the logistic methods, our UCB-CLB and UCB-CCA achieve better regret than CLogUCB and VA- VA-CLogUCB for both settings. We attribute this to the small x (Assumption 5.3) this experiments, which weakens the performance !-dependent methods (UCB-CCA CLogUCB). Furthermore, as the cascade length K increases, all algorithms exhibit lower cumulative regret, which is consistent with our theoretical findings.
Computational Efficiency. Unlike MLE-based methods (UCB-CCA, CLogUCB and VA- VA-CLogUCB), which incur high per-round computational costs due to solving complex optimization problems, our UCB-CI CLB avoids this issue and is highly scalable in large-scale cascading bandit settings. As shown in the rightmost plot of Figure the running time ML.E-based methods grows exponentially with T. In contrast, UCB-CLB remains computationally efficient, exhibiting runtime that scales linearly.

---

7 Conclusion
In this paper, we revisit the contextual cascading bandit problem and resolve the long-standing question of how the cascade length K affects regret. We first empirically show that, unlike prior theoretical results that regret grows with K, the regret actually decreases once becomes sufficiently large. Motivated by this observation, we propose UCB-CLB, an OMD-based UCB algorithm that achieves the tightest known regret bound of (min {Ka*~1 1,, } dv dv/T), and nearly matching lower bound. Our findings provide new theoretical and empirical insights into how longer cascades can enhance statistical efficiency in contextual cascading bandits.
Acknowledgements
This work supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2022-NR071833 1837153,, RS-2023-00222663, RS- 2S42002--0406908, and RS-2025 (225-22440044) by Institute of Information & communications Technology Planning & Evaluation (ITP)) grant funded by the Korea government (MSIT) (No. AS-2025-02263754) and by AI-Bio Research Grant through Scoul National University.
References
[1] Yasin Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Marc Abeille, Louis Faury, and Clément Calauzènes. Instance-wise minimax-optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 3691-3699. PMLR, 2021.
[3] Sanae Amani and Christos Thrampoulidis. Ucb-based algorithms for multinomial logistic regression bandits. Advances in Neural Information Processing Systems, 34:2913-2924, 2021.
[4] Peter Auer. Using confidence bounds for exploitation-exxllrraioo trade-offs.Journall of Machine Learning Research, 3(Nov):397-422 2002.
[5] Xi Chen, Yining Wang, and Yuan Zhou Dynamic assortment optimization with changing contextual information. Journal of machine learning research, 21(216):144) 2020.
[6] Wang Chi Cheung and David Simchi- Assortment optimization under unknown multino- mial logit choice models. arXiv preprint arXiv:1704.0011: 2017.
[7] Hyunjum Choi, Rajan Udwani, and Min-hwan Oh. Cascading contextual assortment bandits. Advances in Neural Information Processing Systems, 36, 2023.
[8] Louis Faury, Mare Abeille, Clément Calauzênes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference Machine Learning, pages 3052-3060. PMLR, 2020.
[9] Louis Faury, Mare Abeille, Kwang-Sung Jun, and Clément Calauzènes. Jointly efficient and optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 546-580, PMLR, 2022.
[10] Kwang-Sung Jun, Lalit Jain, Blake Mason, and Houssam Nassif. Improved confidence bounds for the linear logistic model and applications to bandits. In International Conference Machine Learning, pages 5148-5155 5157. PMLR, 2021.
[11] Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning to rank in the cascade model. In International conference on machine learning, pages 767-776. PMLR, 2015.
[12] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Combinatorial cascading bandits. Advances in Neural Information Processing Systems, 28, 2015.
10

---

[13] Joongkyu Lee and Min-hwan Oh. Nearly minimax optimal regret for multinomial logistic bandit. Advances in Neural Information Processing Systems, 37:109003-109065 2024.
[14] Joongkyu Lee and Min-hwan Oh. Improved online confidence bounds for multinomial logistic bandits. In Forty-second International Conference Machine Learning, 2025.
[15] Junghyun Lee, Se- Young Yun, and Kwang-Sung Jun. Improved regret bounds of (multinomial logistic bandits via sonrettto-coffidncc--eee conversion. In International Conference on Artificial Intelligence and Statistics, pages 4474 4482. PMLR, 2024.
[16] Junghyun Lee, Se- Young Yun, and Kwang-Sung Jun. A unified confidence sequence for generalized linear models, with applications to bandits. Advances in Neural Information Processing Systems, 37:124640-124685, 2024.
[17] Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR, 2017.
[18] Shuai Li and Shengyu Zhang. Online clustering of contextual cascading bandits. In Proceedings of the AAAI Conference Artificial Intelligence, 2018.
[19] Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In International conference on machine learning, pages 1245-1253. PMLR, 2016.
[20] Xutong Liu, Jinhang Zuo, Siwei Wang, John CS Lui, Mohammad Hajiesmaili, Adam Wierman, and Wei Chen. Contextual combinatorial bandits with probabilistically triggered arms. In International Conference on Machine Learning, pages 22559-22599 PMLR, 2023.
[21] Xutong Liu, Xiangxiang Dai, Xuchuang Wang, Mohammad Hajiesmaili, and John Lui. Combi- natorial logistic bandits. arXiv preprint arXiv:2410. 170755 2024.
[22] Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
[23] Min-hwan Oh and Garud Iyengar. Multinomial logit contextual bandits: Provable optimality and practicality. In Proceedings of the AAAI conference on artificial intelligence, pages 9205-9213, 2021.
[24] Francesco Orabona. modern introduction to online learning. arXiv preprint arXiv:1912.1322 2019.
[25] Lijing Qin, Shouyuan Chen, and Xiaoyan Zhu. Contextual combinatorial bandit and its appli- cation on diversified online recommendation. Proceedings of the 2014 SIAM International Conference Data Mining, pages 461-469. SIAM, 2014.
[26] Daniel Vial, Sujay Sanghavi, Sanjay Shakkottai, and R Srikant. Minimax regret for cascading bandits. Advances in Neural Information Processing Systems, 35:29126-291131 2022.
[27] Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit:
Improved regret and constant computation cost, Advances Neural Information Processing Systems, 36, 2024.
[28] Zixin Zhong, Wang Chi Chueng, and Vincent YF Tan. Thompson sampling algorithms for cascading bandits. The Journal of Machine Learning Research, 22(1):9915-99) 59800, 2021.

---

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: The abstract and introduction clearly state that the regret decreases when is sufficiently large. This claim is theoretically supported by Theorems 5.6 and 6.1, and empirically validated by the experiments.
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 the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: In Section 5.3, discuss the limitation that the linear model requires the probability of positive feedback to be bounded away from zero. However, we argue that this is a mild assumption in practice, as such events are rare in real-world scenarios.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play 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
12

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results are stated with explicit assumptions. Complete proofs are in the supplementary material, with intuitions provided in the main paper.
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 or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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 information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We describe all experimental settings in supplementary materials (See Ap- pendix G
and provide code for full reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a 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 new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
13

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We use public data and provide anonymized code and instructions for repro- ducibility.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc)
jublic/guuiee//CddSuubiii wwtaimiisssooooioiooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: for more details.
//ipps.ccpullic/giddee http://bbll.caiiieee/ooooouutiia
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information 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: The main paper provides a summary all experimental settings, and full details including data processing and material (See Appendix G).
are provided in the supplementary
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the
the paper to 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, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars in all plots indicate the standard error (SE), as stated in the main text.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
14

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).
It should be clear whether the error bar is the standard deviation 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 error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
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 to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details about compute resources, including hardware specifications and run- time, are provided in the supplementary material (See Appendix G
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't fidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We comply with the NeurIPS Code of Ethics and identify no ethical concerns in our work.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make 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: [Yes]
Justification: The paper discusses potential benefits for personalization and risks such as bias and privacy concerns, despite being primarily theoretical (See Appendix I]).
Guidelines:
15

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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 train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used 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 (c.g., gated release 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 ML).
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: Our paper does not involve any data or models that pose risk of misuse.
Guidelines:
The answer NA means that the paper poses no 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. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We used the MovieLens 100K dataset, which is publicly available for non- commercial use. We have cited the dataset and its source appropriately in the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
16

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, papprrsi thcode. com/datasets vatasets.paperssi
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.
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: [Yes]
Justification:
We will release the full code with documentation to support reproducibility.
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 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We did not use crowdsourcing or human subjects in this work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 to the NeurlPS Code of Ethics, 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 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:
We did involve human subjects crowdsourced data in our research.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
17

---

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 NeurIPS 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We used LLMs only for writing and editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy ottupp/s/eeerroosccc///ooeerrrrs for what should or should not be described.
18

---

A Notations
We provide the notations used throughout the appendix. The total number of rounds is denoted by T, the total number arms by N, the cascade length by K, and the dimension of the feature vectors by d. The logistic function (2) and its complement (0(2) are defined follows:
exp(=)
01 (2) = 1+ exp(z)
and 0o(2) = + exp(=)
(2).
for any E R. The first and second derivatives of (2) with respect to given by
01 (1(2) = oa (=)))11(2))
81 (1)=) == (z(2))1 (=) (2)).
Also, === EI Eio, F, Ala-
Table 2 provides summary of the symbols and their descriptions used throughout this section.
Table 2: Symbols
Symbol
Description
I
set of all N arms
II
set of all possible cascades cascade chosen by our algorithm in round a list of observed arm in round k-th arm in C2 in round t feature vector for arm given at round t feedback for arm given at round
C.
O
Vr,i
0))
1 - Iliec oo (0(x expected reward of the cascade C' at round
(0)
Eve(o.1) Hy = y} log (,, loss function at round
(0,,(())
(z,,),,)) yr, the first derivatives of (0, with respect 0
(0),,(0)
ō 0 the second derivatives of (0) with respect to regularization parameter
A
1
step size parameter
(e,
(Vdllog(LK) confidence radius at round / (3, = Br,1)
0c 3.(5) ot, lla optimistic estimate for arm at round t,
J((C)
1 Ilic ao(u,) (4,)), optimistic expected reward of the cascade C round
B Exploration Bonus
Lemma B.1. Let Og be the online estimate as defined in Equation 3 Let (8) be confidence set with a confidence radius B,(5) in Corollary 5.5) Define u4,; := ,r + 3,( || il Then,
under the event [vt 2 1 E (5)) for all E [T and i I, the following holds:
0 I U4,i TT,00' 28,(6) ||
Proof of Lemma B.1
We begin by bounding the estimation error as follows:
TT 0:
x. o
[0, 0y)l
SN1 JVB (B) ||reslller
|| 1|0, ml
19

---

where inequality (i) comes from Hölder's inequality and inequality (ii) is obtained by applying
Corollary 5.5 Thus, the following inequality holds:
0 s 2 + (,(0) ||
21,00 ueii -,, 23,((0) |a
Lemma B.2. For any given E 11, the following holds:
f((C,8) - f((C).
Proof of Lemma B.2 Recall that f((C,0") == - ILec ou(x,,, 0*) for any given E II. Due to the fact that (=(2) is monotonically decreasing function of a E lR and a,, I Uz for all i E C by Lemma B.I we directly obtain the desired result.
C Regret Upper Bound of UCB-CLB
C.1 Proof of Theorem 5.6
The proofs of all lemmas stated in this section establish Theorem 5.6 are deferred Appendix C.2
Theorem 5.6 Suppose d 2 K. Set the step size 1)
1 log 2 + 2 and penalty parameter X
max(84 2dm, K). Ler Let (0, 1}. Then, under Assumption 5.1 UCB-CLB CLB ensures
R(T) δ min { KKK KKKKIddT -d--dddT- KpK-1
d²
Kpk d d²
d²
Ki 1)
+
kp
with probability at least 1 1 5.
Proof of Theorem 5.6 We provide the detailed proof the regret upper bound stated in 5.6 To this
end, we separately analyze the two regimes that dominate the minimum term: (i) the K dependenn regime leading to Ö(K K-IVT + KjK-1s da K K -k - and (ii) the K-independent regime
kp
yielding Ó(dVT+ 2) The combination of these results establishes the upper bound in Theorem 5.6
In the following, assume the good event Eg (vt TT] and vk [|O,1],0* C2 (6) to hold, which happens with probability at least 1 - 8 according to Corollary 5.5 Recall that the optimistic expected reward for the cascade C (i.,..., (ii....,kk)) in round is defined f{(C)
1 - Iiee, (o(ue,) where ūz 0e (6) || for all E I. Also, recall that C. (ir,,...,$e the cascade selected by UCB- CLB in round
Deriving R(T)= = Ō(KKK d/T KRK-1 de + Kpk-
Now, we bound the regret R(T) as follows:
T f((C))
R(T)
E
f((Ci, (*) - f((C,,0))
<
E
Σ
f(l))) f(())))))
(1)
E
[((C))- - (((C))-((C,,,)))))
=E
II
co(
II cn(u).)
sEC.
iEC.
K
E
colotee 0*) (ar (un,s)) ai 01 0n))
II m=k+1
oo rul
1m
Ec 1=1
T'
E
II
,o(xT,0') (ui()))) (I(TTT0)))
iEC, jECA(f
(iv)
K-LE
( - (1(
< p
iEC.
20

---

where inequality (i) is obtained by applying Lemma B.2,
inequality (ii) holds due to the definition
of C == argmaxcen f((C), inequality (iii) follows from the fact that oo(-) is monotonically decreasing function and Lemma B.1 which guarantees " 2 2,,00" for all rounds t and arm i, and inequality (iv) holds by the definition of p in Definition 5.2 Notably, the product term in Equation (7) plays critical role in deriving the desired result, showing that the regret upper bound vanishes as the cascade length K becomes sufficiently large.
Then, we decompose the prediction error in Equation 7 using second-order Taylor expansion, a standard technique widely employed in the logistic bandit literature [2]. This yields:
R(T)
01(2(,)) d1 (x, (ue, 1 =T,00)
E
(we. 0/
2
IEC,
(
T
(0)
$ K
28,(0)01
FEC
(1) S 2p K- (5)
xk (8) E
σ1 (z) Σ Σ
||
|
H
(8)
5
VEC.
iEC,
where 2t,4 is a convex combination of ue, and me,s- The above inequality (i) is due to the fact that a()) < 0.1 and from Lemma B.1 which states ue, - 0,, s (6) | for all t E [2]] and i e I, and inequality (ii) holds since (6) is monotonically increasing with respect to t.
To control the first term on the right-hand side of Equation (8), we decompose the first summation term as follows:
Σ E (z
|
1=1 iEC.
δn (x) || H.
(òn (0 (x) |
IEC
1= IEC.
T
d1 (1 |
20, -x ||
4
IEC
IEC
1
Σ
0,) |
110 0ell 10,,,112,
iEC,
IEC.
(11)
T
3r(
in (xT | + Σ iEC
| F H
(9)
IECs
where inequality (i) is obtained by applying Lemma C.2 inequality (ii) holds by applying Hölder's
inequality, and inequality (iii) holds by applying Corollary 5.5 and the fact that 3c(6) is monotonic increasing with respect to t.
Plugging Equation
9 into Equation
{8
yields the following:
R(T) S -1 (5)E
IEC.
7 -0 3
(8)L
Σ
(10)
[=1 IEC.
Before diving into bounding Equation 10 we first discuss the challenge in theoretical analysis of contextual cascading bandits and the swapping technique to address it. The general strategy for completing the proof is to utilize the elliptical potential lemma Abbasi-Yade Yadkori et al. [. a standard
21

---

lemma in the contextual bandit literature. However, it is challenging to directly apply the existing elliptical potential lemma in the contextual cascading bandit setting. As seen in Equation (TO), we need to bound the term that accumulates all arms in Cr, while the Gram matrix H; only accumulates the feature information of the observed arms. As a result, there is an issue in which the leftover sum (from [O,] + 1 to (C,) becomes out of control [9]. This limitation arises from the fact that the agent receives feedback only for the observed arms Oz, making difficult to control the contribution of unobserved arms in the regret analysis. To address this issue, we exploit the optimistic exposure swapping technique first introduced Choi et al. 77.
Let C22 E argmaxcen (C). The expected reward fi(C, 8*). as defined in Equation ( invariant under permutations of the arms in the cascade. Exploiting this property. the doubly optimistic exposure swapping technique rearranges the cascade C₁ by placing the two selected arms at the top, yielding a new cascade Ct without affecting the expected reward 77. Let x,") and 2, be the arms in C22 with the highest values of (x, 0c) [ and || H respectively. We construct the cascade C2 by placing these arms in the first and second positions. followed by the remaining arms in Cf:: C. := (i) 24 || (C) \ (((1) (2) }). where A B denotes the concatenation of two lists A and B. We denote the k-th arm in C lek- As side note, it is possible for the arm that should be placed in the first position to be the same as the arm that should be placed in the second position. In such cases, the arm placed in the first position. This does not impact the regret upper bound derived in this section. For ease of analysis, we henceforth assume that the two arms are distinct.
Since the arm in the first position is always observed (ie1 E Or), the following inequality holds and effectively avoids the aforementioned out-of-control issue:
Σ 81 (17, | n-- = K max d (ZT, || | = Kōi 0t) || In. (11)
iECr
iEC
Additionally, considering that the arm with the largest || in C2 is placed in the second position, the following equation holds:
nr- = K max
|
lia. = K Te I 1
(12)
REC,
IEC
Applying Equation
II and Equation
12 to Equation
10 we obtain the following result:
R(T) S 2K
(T)
tn (1T 0c) I| Ilx,"
T
7 Kp (0)))
+ 10
Σ
| H.
(13)
Now, we first focus the first summation term the right-hand side of Equation (3). Still, directly applying the elliptical potential lemma [1] to the above equation is challenging due to a dependency mismatch: the weight term dr (xI,.,, 6.) depends on the parameter fg, while the Gram matrix H, is computed using the parameter (0..++1rejtt-) -rtt))),,,,,,, I]- To address this issue, we adopt the decomposition technique inspired by Lee et al. [16) whose work focuses generalized linear bandits, and we adapt it to cascading bandits. Specifically, define an intermediary parameter ò as:
0, argmin ôn (x 0)-
8ECT,_(6)
Note that in (xT,,, 0*), (Z 02,)) 2 a (IT.a, 0.) under the good event &, and by applying Corol- lary 5.5
Using this intermediary parameter O,, decompose the summation term on the right-hand side of Equation (13) as follows:
on (a 0c) Ilaess 19,7"
Σ di (oT 0.) Ilatsa H. +
Σ
à ( 0,) - 62(2,,,, 0.)) 1 (e,,nlla, (14)
m=1
22

---

For the second term on the right-hand side of Equation (4). the following result holds:
T
0 (0 0:) (1 ie la,
T
T 22 (0: - 8.) |10eballe,
1=1
1VB
0+ 0.1 He -11sr.a lla."
110- 0 11 + +110- - -0.2lla. + +110,2 - -0.11- 0.111e) I 1226""
1V3
110: - 0- + 110 - 0121 He, + =110.2 8el [
( (()
T
| 1e.."
4
1=1
(vi) (,3r,(())
Σ
4
(vil) 3,3 k (0)
1+ TT) dd
2d
(15)
4
where inequality (i) is obtained by applying Lemma inequality, inequality (iii) is derived using the triangle inequality, inequality (iv) holds since H, < H2,2, inequality (v) follows from Corollary along with the monotonicity of Be, with respect to and k, inequality (vi) is valid due to H, KV. (V; - Eieo, Tr, T + Ala), and finally, (vii) results from Lemma F2 with the identification n, |Oo|, 21, 2t,i and Ze Vy.
C.2 2
inequality (ii) follows from Hölder's
To handle the first term on the right-hand side of Equation (14), we establish the following bound:
T
T
Σ δi (= 0.) | H.
V 0i (x 0+)
δ (1 0c.2) || laa
t=
T
T
Σ
rn (ITTin 0*),
Σ
òn (x 02.2) I1 Il
Σ ri (xTTie 0222) I1seaa li21"
T
Σ Vol (e2)aeeaa)) I!-
(iv)
2d log (1+
T
1
(16)
dA
where inequality (i) is valid due to dn (= 8*), &n (IT 02,2) 2 81 (1 0c), inequality (ii) results from the Cauchy-Sehwarz inequality, inequality (iii) is due to the fact that 0.(-) S 1. and inequality
(iv) follows from Lemma F22 with = =1Orl, 21, Vol(aT... oc 1,, and Z. = Hi-
Plugging Equation
15 and Equation (16 into Equation
14 we have:
k R dog
T
df log
T'
Σ oi (ZT 0,) | AA, <
1
+
1 + db
(17)
2
dY
2
23

---

Substituting Equation 17 into Equation
13 this yields the following bound:
T dr log (1+
R(T) S -2Kp 1orp0))1100 sT(0)/
dA
T
+ 133kK-1 3r (r))))))) (8r
1+
dd
T
+ KBpK-1B7 10
7
11
(18)
To complete the regret bound, it remains to bound the last term on the right-hand side of Equation 18 which involves the cumulative weighted norm of the sccond-position features. Unlike the first position, the arm in the second position is not always observed. To address this issue, we present the following lemma. The proof of Lemma i. deferred to Appendix C.2.1
Lemma C.I. Recall from Definition 5.2 that p denotes the lower bound of oo(x 0*) for any E X. Suppose Cg is constructed under the doubly optimistic swapping technique placing the arm with the largest | 1, in the second position of C Then, we have the following inequality:
T
1 H
<
E
1(002 23 11 1
Applying Lemma
to Equation
18
we obtain the following bound:
E
Σ
H
p
'E
1 110 2 23 |1ar, 1i2
(i))
T
(ps)
-E
1[10 2 2}
|| V.
2T
(px)
l2d log
1
(19)
dA
where inequality is obtained by applying Lemma C.I
inequality (ii) holds since He 2 RV, and O.), 2τ Lx and Z. V.
inequality (iii) follows from Lemma F.3 with the identification
Finally, combining Equation (19) with Equation
(88) yields the claimed result:
T
R(T) < - By(o) df log 1+
dx
+ 3KpK 1 - (r
1 dd
21'
+ Ky k- -pxx)=x))>))))}>))))) (px)) (8) log
1
5
θ K dvT + -1 d2
+ K KpK-11 d22
Kp
Deriving R(T) Ö(dV +
L
Now, we bound the regret R(T) as follows:
R(7) = E
T
1((;,00)~ -e
(1)
E
T
J((;))
((C,or)))))))))
(8)
T
E
- - o(())
=E
oo(xIT00)-
II
coluu.d
LEC,
sEC.
E
Σ
c0(x (
- 01 - 0*))
II
oo um
(20)
Esg EC, 1=1
m=k+
24

---

We define an intermediary parameter 01,; as follows:
O ==
argmin
01 o1
[T,
This ensures that the gram matrix H, satisfies the following lower bound:
[-
H. = Σ Σ 01 + Py =: L..
The following inequality chain bound the deviation between the true gradient term o 0*) and d1 (1,T,b0..).
òi à
-x )
(
$ d B..)) +
4 T,, - -6..)l
1
(x
l0,,llle 110 - bl.ille.
(T)
|
(21)
where inequality (i) is from Lemma C.2 inequality (ii) is obtained by applying the Cauchy-Schwar inequality, and inequality (iii) is due to Lemma B.1
Building on the gradient-deviatee bound above, we derive the following inequality to control the difference between the UCB estimate and the true expected click probability as follows:
(u,,)) 01 (1)
(1(.))
=0((x,,00)) (u., - xx)
(ue, x2
2
(0(
223((0)) || ||,
|
5
(
7
< 23r(
| 1 H
10
7,37,x
(d)
$ (8)( || +
10
where inequality (i) obtained by applying Lemma B.1 inequality (ii) is by Equation (21)
Define Çr. == (5) (x., || and Er,s
799
| Then, we can bound
10
Equation 20 as follows:
K II m=k-1
R(T)
S
E
oo 0*) (Grin ELine)
ool (om
laz Ec 1=1
T
1=-1
< E
col Se
II
a To 0r)
1=1 EC, I=1
m=k-1
Temm
+E
II
ao col 0 Ee,
I=1 ELLEC, Iml
Term
25

---

We first bound the Term 1 as follows:
(i)
T
k-1
Tmm co(=ts 0 (ot 0M)
Term
Σ
au Se
ou
Vor(whiu 8² (000 8*)
1=1
1=1
m co( 01) Shite
K II
E
Σ Ec, m=k+1
0o (f 00) (1r 0+)
01 ( (1)00( 0*)
I1 00( on( S2
II oo o0(
E
on (1 8t 100 84)
AwEC
iEC,
IHei co( 80) O
S E
0n (2 (") 0+)
Ec
(i1)
I co(x Gr
Σ Σ Liml teEEC
(22)
01 ( 0+ (00 0-)
where inequality (i) follows from the fact that (2) I vo(2) for E (0,1) and by mul- tiplying and dividing each summand for d, Ct with the corresponding / (xT 0) and
y (1 0) co( 0*), inequality (ii) is due the Cauchy-Schward inequality, and inequal- ity (iii) is obtained by applying the Cauchy-Schwanl inequality and Jensen's inequality. Each term in summation Equation (22) bounded the following inequality
GLE
(8)( ( 0r.in) | 11 I2,
01 8t ( 8*)
01 (o)o Q-)
457 (enin)) 11 122
01 (1 0 100( 0-)
(o)6 0z)ān (T deicee 11 1,,"
(23)
where inequality (i) is due to the definition of the intermediary parameter 0 Substituting Equation (23) into Equation (22) yields the following bound, and the remaining step is to apply the triggering probability equivalence (TPE) technique of Liu et al. [20 21]:
Term 1 2.3((0)V
E
Σ
oo TT 0*) ( dern Sitt
lez EC. 1=1
=33r(8VVT
E
E
ao( 0*) He an (IT desse Iloreeu 1l
-33r(0VVT
E
E [[iiir E O.) Hi) ā (al)i(( (w.TA drii Ilaeette l2.-
E.
=33((OVT.
E
Σ KLEC.
Him Ortō (r Ieresalll..
-33r(0VVT.
E
Σ
in (1. ||
IEO,
26

---

Next, we bound the Term 2 as follows:
k-1
Term
I2
co( 0*) (Crais))
E
E
o0 T 07) He Settek
E
E [Tffce E Oif Hel Ee,dex
Hii Or)erii
txEC,
E
IEO:
7 7
T
E
| 1
10
1=1.E0,
Thus, we have:
7
T
R(T) 28T(O)VT
E
Σ
on
0r.))
E
| |
10
t=
SEO,
TK
7,7 (0)
TK 1+
2BTT
2d
1+
+
2dlog
dA
10x
dA
= (dVT
Combining the bounds for Term and Term 2 and applying Lemma unified regret bound claimed in Theorem 5.6
F.4 and Lemma
F.7
yield the
C.2 Proof of Lemmas for Theorem 5.6
C.2.1 Proof of Lemma C.1
Lemma C.1 Recall from Definition 5.2 that p denotes the lower bound of oo(x 8*) for any X. Suppose is constructed under the doubly optimistic swapping technique placing the arm with the largest | H,," in the second position of Ct. The following inequality holds:
T
E
| AA."
S
E
Σ
1(00 2 2 || 11
Proof. By the law of total expectation, we have:
E
1 H,
Σ E
| H..
Now we introduce some definitions related to the probability of observing a specific arm, which used exclusively in this proof. Let Pt,c, be the probability of the second-positin being observed in round t. Also, let pz minigesT mingen Pr.c,- When C, is fixed, Pr,c, is the probability that O 2, and thus
of C,
(10.122 Ci) =
Pac.
27

---

Then we have:
E
E
|1e H1g
E
E
| 1H E
1
1 1[0,11 2 2) c
M/
Prcc,
E
|
n1. Pr,C.
{|0i| 2 2) Hr
E
E [ 2 2} | 11
Hol
E
Σ 1 110 2) 10 lHA
Σ
f1111 2 23 F 1811""
where the last inequality follows from Definition 5.2
C.2.2 Proof of Lemmas for Lemma
Lemma C.2. Given x E R for any 01,02 E Rd.
1 1 [ - -0)-
ò ( 01) 5 01
Proof. We start from Lemma E.3 of Lee et al. 16 (restated in Lemma F:5
61(x (z 02) s 10,(0 T 01) 01(11' (r 02)
(z)(2 T(0 02)
x T (0: - 02)l $ 4
D Regret Lower Bound
In this section, provide the proof of Theorem 5.7 To begin with, construct a hard instance, inspired by Chen et al. [3), Lee and Oh 13
D.1 Adversarial Construction and Bayes Risk
Let E (0, 1/dvd) be a small positive constant, be specified later. For each subset V S [d], we define the parameter By Rd follows: [0vl, = for all j E and [0y], for all j & V. Next, we define the parameter set:
θ = (0v : E V4/43 = (0v V S [4] |V = d/4),
where V&3 represents the collection of all subsets [d] whose size is k. Let d be divisible by
Let context vectors remain invariant across all rounds t. For each U Vaya, we construct K identical context vectors zy as follows:
[mul, = 1/Vd for j E U; [æyl; = for j & U.
Note that since there are K identical context vectors, the total number of arms is N = K (2/))
For any V,U E Vaja, the boundedness assumption (Assumption 5.I D.D is satisfied as follows:
[|6vl12 s Vde² 11, || 1/d
28

---

Moreover, the worst-case expected regret of any policy x can be lower bounded by the "average"
regret over a uniform prior over è as follows:
T
sup E (T)( =
sup Eg
-(C",0)-(CC,))
==1
T
max Byy By
Σ
[(C",0v) --(C,,
Σ
0v)
(24)
Va/1 VEVa/4
This simplifies the problem of lower bounding the worst-case regret of any policy the task of lower bounding the Bayes risk for the constructed parameter set.
D.2 Main Proof Theorem 5.7
Proof of Theorem 5.7 For any sequence of cascades { produced by policy x. we denote an alternative sequence {CT)T= that results in lower regret under the parameterization.
Let ZU....., ,Uxx be the distinct feature vectors contained in cascades Cr where U......, UKK
Va/4- Denote U.- argmaxyeeU......ua 2. fv, where By is the underlying parameter.
Then, leveraging the properties of the cascading structure and the non-decreasing nature of the sigmoid function d1, we make the following observation:
Proposition D.1. For all V E Va/4, we have
T
E
Σ
-(CC,, 2 min Kg [Kg-11, 11 E Σ
- ( 0v)
for logistic bandits
Proof of Proposition D.I
T
E
Σ f(C", 00) f(C,,0v)
T
K
oal co( - (1 1 1I-Ioom ool Io Bv))
K
E
1=1
k=1
1=1
T
K
oo ool 8v) (o1(zT0v) - o1 (x 0v)) (oo(zTor)) k-#
E,,
[=1
k=
2 K 1--Eg E
(a (o(TT)y)) 0, (x
(p inf, op (x (xT)r))
2 Kp K- 'E Σ (oi(TTor)) - - o
0v) 2 a. (xt 0v))
Note that, by definition, we have
p= inf (x (x = ev eova/4 2
(E> 0)
This directly implies that KpK-1 < 1 for all K > 1. Therefore, we can conclude that
Es(c - f(C,, 0v) 2 min K-1,1111 13 Ey Σ
(o)(xTor) (1)
B
t=1
t=1
This completes the proof.
29

---

Hence, it is sufficient to establish lower bound on the regret for logistic bandits. To this end, we introduce the following proposition.
Proposition D.2 (Regret lower bound for MNL bandits, an intermediate result of Theorem in Lee and [3) Denote M as the maximum assortment size in MNL bandits. Let d be divisible by Suppose T 2 C. d' / for some constant C >> O. Then, in the uniform reward setting, for any policy æ, there exists a worst-case problem instance with N = ((M 24) items such that the worst-case expected regret of lower bounded as follows:
VM
Σ
Eg
[RAAL [ (T)]
=
dvT)
Pafsl VEVAja
M +1
By applying Proposition D.2 with the assortment size set to 1, i... M 1, obtain
sup E [R)(T)) Ω (min (Kp*-1 dvT).
which concludes the proof of Theorem 5.7
E
Tighter Regret Analysis for Cascading Linear Bandits
E.1
Problem Formulation
Apart from the linear feedback model described below, the overall problem formulation remains
identical to the cascading logistic bandits setting presented in Section 3 Each arm i E I has an associated Bernoulli feedback yt, E 1) at round L. Given history Hr, we assume that the feedbacks (ve are conditionally independent and satisfy the linear model:
E Elya.
H4] = 2T,
where E [dd is an unknown time-invariant parameter under the assumption that ||=,,<l| S 1, Vt [T], E Z and ||0"||2 < as stated in Assumption 5.1
We further assume that the expected feedback strictly positive for all and i, i.e., xT, > O, which excludes the case where the probability of receiving positive feedback is exactly zero. This condition excludes only those context vectors lying on the hyperplane orthogonal to 0", which forms measure-zero subset in d This mild assumption that holds almost surely when the contexts are drawn from any continuous or non-degenerate distribution. In practical recommendation settings, each item typically has non-zero probability of receiving positive feedback from users. Hence, the assumption is commonly satisfied in real-world applications, as every item in the recommendation pool is expected have least minimal relevance to some users.
In Appendix reuse on
we overload the notation σ (2) to denote the identity function, i.e., 01(2) == 2. Also, 1 σ (z) for consistency. Additionally, we overload the notations and p from Definition 5.2 while noting that their interpretation differs under the linear model. Specifically, since
(o(2) 2, and thus /- suP]|=]]s1 x. (²r) and p inf [I x: TT)). Under the linear
model (a)(2) (2) 2), the expected reward is defined follows:
f((C,,0") 1 II (1 01 (1
II (1 x TT)0) IEC,
(25)
iEC.
30

---

E.2 Algorithm for Cascading Linear Bandits
Algorithm UCB-CLimg
Algorithm OE-SWAP-L
Input: penalty X, radius 7t- Initialize 01 E e, V1 Ald. for 1 = 1,..., T do
Input: cascade C = (i...... ik) gram
matrix Vz.
Find it E arggaaxecc || lleellll
Compute {ui, (z)
= or t || f y hez.
Swap the positions of i and z(1)
Select C₁2 E argmaxcen fi(C) by 5
Output: swapped cascade (76 )...).
C. f D--SPP dc, He).
Play C, and receive feedback tuple (O,, V,).
Update 0, by Equation (26)
Vi+1 +- Vi + Eieo, Z1,10,,.
end for
In this section, we present the UCB-type algorithm for Cascading Linear Bandits (UCB-CLinB), which combines UCB-type exploration with a linear reward model and optimistic exposure swapping technique introduced by Choi al. The pseudocode is shown Algorithm 3 and consists of three core steps.
First, it estimates the unknown parameter 8* using & (-rrgularized least-squares regression based on observed arm nee-bec pairs, constructing a confidence set based on the confidence ellipsoid result from Abbasi- Yadkori al. M. (See Appendix E.2.I) Second, using this estimate and confidence set, we defines an upper confidence bound on the expected feedback each arm and selects a cascade that maximizes the optimístic expected reward (See Appendix (E.2.)). Finally, apply the optimistic exposure swapping technique (See Appendix E.2.3). originally introduced by Choi al. [7] to deal with the partial feedback in cascading bandits. This strategy promotes the arm with highest uncertainty to the top position in the cascade, While conceptually similar to DO-SWAP used in cascading logistic bandits, this technique differs in the criterion for selecting which arm swap, reflecting the structure of the linear reward model.
E.2.1 Parameter Estimation & Confidence Set for Cascading Linear Bandits
To estimate the unknown parameter 6", we use ridge regression on data collected at each round f, {(T+,i ((,t,,,+a))an v+a)) ae0. Leveraging the collected data, we obtain an lz-regularized least squares estimate of 8" with regularization parameter À >
0. (x, X1 + AT) Y,YY,
(26)
where X₂ is the (E4=1 (0+)) x d matrix whose are 2T,i and Y, is column vector with entries Fr,s, for i [0,],T 1]. Let
[-1 V = Σ Σ Rr,eT + AI. T=,
(27)
Note that V2 E Rd is symmetric positive definite matrix. We apply Lemma F.1 the confidence ellipsoid result in Theorem 2 of Abbasi- Yadkori et al. [1] which provides a confidence bound for the lg-regularized least squares estimate in the linear model. This yields Corollary E.]] which establishes that the true parameter 0* lies in the confidence set c(2) (8) with high probability under the cascading linear bandit setting.
Corollary E.1. For all t [T]. with probability least 1 - 8. we have 0* Cc (8), where
c ch (0) = (0 E θ 110, 0 0lv. S 7e(5)).
Here, (6) O( O(Vdlog(tK))
31

---

E.2.2 Optimistic Expected Reward for Cascading Linear Bandits
Now, we define an upper confidence bound for the expected feedback of any arm i
( min [2 + [ |
(28)
Then, define (C) be the optimistic expected reward of the cascade C' in round based on (4).
4,
A (C) =
II oo ( IEC
(29)
Then, the agent identifies the cascade that maximizes f( in each round. To ensure that the above exploration bonus approach remains effective, it is crucial to guarantee that (C) is indeed optimistic relative to the true expected reward fi (*). This requirement is addressed and formalized in Lemma E.2 and Lemma E.3 demonstrating that effectively explore.
maintains the necessary optimism to
Lemma E.2. Let 0, be the lz-regularized least squares estimate as defined in Equation 26)
Let c (5) be a confidence set with confidence radius ((((5) in Corollary E.1 Define (2
minf27,,0 + (((6) I 1 for [T] and i E I. Then, under the event fvt 2 1, 0"
c, (6)}, the following holds for all t E [T] and E I:
(4) M 2.5 - 0 < 22%((0][=xslll==
Proof of Lemma
F.2
We begin by bounding the estimation error as follows:
0c x zT_00- 0
[0, -80
i1)
|.ralll, 100. 0-
7((6) | lle.
where inequality (i) follows from Hölder's inequality and incquality (ii) is obtained by applying 0 2 O, the following inequality holds:
Corollary E.1 Since
0 S 0r + 76() |,r,,lll,- - =-,.0' ui
(1) - xT.00 r < (5) ||
Lemma E.3. For any given C E II, the following holds:
Jx 0-) - (C).
Proof of Lemma
E.3 Due to the fact that o0(2) = - 1- is monotonically decreasing function of
z E IR and TT,
(1) for E i E C by Lemma E.2 we directly obtain the desired result. D
E.2.3 Optimistic Exposure Swapping for Cascading Linear Bandits
We describe Optimistic Exposure SWAPping for cascading Linear bandits (OE- (WA-SL) which is technique handling unobserved feedback in cascading linear bandits and first introduced by Choi et al.
Z7 The overall procedure OE-SWAP-L summarized in Algorithm 4 At each round t, the agent
employing OE-SWAP-L identifies single arm i( E argmax,ec || | from the given cascade
C. and swaps it with the first-position arm in C.
32

---

E.3
Proof of Theorem E.4
Theorem provides the regret upper bound for UCB-CLinB. demonstrates that UCB-CLinB achieves regret order O(KKK-AVVT) Notably, this bound exhibits the same dependence on the cascade length K and the constant p as in the logistic setting, This highlights that the factor Kp*-1 originally derived in the analysis of cascading logistic bandits, also naturally arises in the linear case.
Theorem E.4. Set the penalty parameter X 2 K. Let E (0, 1.. Then, under Assumption 5.1 with probability least 6,
ensures
R(T) Ô min 1Kp-11_ ,1, 11dVT)
Proof. In the following, we assume the good event (Ai T occurs with probability at least -5 according to Corollary E.1
and 0" E (6) hold, which
Deriving R(T) = Ō(Kpk=-Kdd
The derivation of the regret upper bound up to Equation 7 in Appendix C.1 remains identical for both logistic and linear reward models. We then bound the cumulative regret R(T) follows:
R(T) Σ fe(Ct, -(((C,))))))))))))
E
-
-.(CC.
S (C)) fe(Ce,0))
=E
ao 00)
II
co(u(())
iEC;
iEC,
E
II (' (a1 (w( σ (J 0*)
II To Ue
in EC,
m=k+1
<
II
To
- -0 (xTT{/0))
(30)
Aml iEC
$ <
Σ [=1 LEC
where inequality is obtained by applying Lemma E.3 This is because the steps rely only on the structure of the expected reward in the cascade model and do not yet involve any assumptions specific to the nonlinearity of the logistic model. Since (=) in this section, we have:
T
R(T) S pK K-
E
(ut (1) - xTT
SEC,
T
① 2p 'I
7e(6) || ||
FEC.
(1)
$ 2p x (6))E
| |x
VEC+
< 2Kp 1
| llv
(Iv)
S 2KT (6)
VT Σ |
(iv)
(1+
T
5 2K 2kpk<117700)
177(0))
2dT log
dA
-((Kk--dVT)
33

---

where inequality (i) is derived by Lemma E.2 inequality (ii) is due to the fact that (6 is mono- tonically increasing with respect to t, inequality (ii)) comes from OE-SWAP-L, inequality (iv) results from the Bouchy-Schwarz inequality, and inequality (iv) is obtained by applying Lemma F2 with the Friin and Z V4.
identification n4 1Or,, 2t.k
Deriving R(T)= (T
Starting from Equation
30
we rederive the regret bound as follows:
R(T)
E
II
00) - -
ieC jECA(()
T
k-
co( )²) (uiine - I 2hi 07)
< IE
1=1
Tkm
oo T 8*) He 1 (utta Ixira 84)
E Elffie Oi} Hil (u x 04))
E
E
lif E Ord (ut - ( 04)
1= MnEC,
(uiia - -iiis 0+)
ieE
T 1+
= ++ =
T dd
22 2dT
where the equalities employ the TPE technique introduced by Liu et al. 120 21,, and the final inequality follows from Lemma E.2 the monotonicity of (o)) and the application Lemma F4 and Lemma F.7
F Auxiliary Lemmas
Lemma F.1. For any S S t and 1 < & n, K, ||2,,1122 S 1. For some X 0, let
Z: = Ei=l E 27,22T + Ala Then,
d
det(Zi) S x -r
nr
d
In particular, since n, S K for all T E [t], we have the simplified bound
det(Zz) s (x+ (t 1)K d
d
Proof. We observe that Z, 2 kk= 2T,1:2T,A. + Ala can be rewritten in a form analogous to E, TT + ALa as stated in Lemma 10 of Abbasi- Yadkori et al. (restated in Lemma F.7) by interpreting the index as ranging over Σ(=1 |n+ instances. Hence, Lemma 10 of Abbasi- Yadkori al. [T] can be directly applied by treating each pair (r, k) independent index.
Lemma F.2. Suppose n, E [K] for all t. Lel (o be sequence in Rd such that
|| < 1 and define Z, = Et11 Ehn, Rr, + Ala where X 2 1. Then, we have that
|| 1 S 2dlog (1+
T dA
34

---

Proof. We follow the proof of Lemma 11 of Abbasi- Yadkori et al. M. Since A 2 1 and || S for all and the following holds:
1/ 12
|| 122,2112
| 2,+
S
S
S 1.
Amin (ze)
Amin (ATa)
Using that S 2log(1 1 + 2) for any 2 E [0,1], 1], we have:
T
log
11 1
T
< log
II
1 + ||20,11 2-
1=1
I log
II
1+ | [1+112111))
(31)
where Z, = E 27,12,,1 Ald 3 Zz. Also, the following holds:
(et( det (Z,-1 + 2,124,1)
@ del (2-1)) 1) del [I + (2 2x,1 (1,11=,,)))((-17 (2(2/ (2((12=(117]) 2x,)T)
(1)
2 det 2,-1)
(1+ ||2,,1 11,2112,11 2,
(m0)
f-1
det Ala)
II
1 + | 112 12211)
(32)
r=1
where inequality (i) is by the fact that V + = --
for a symmetric
positive definite matrix V. inequality (ii) due to Lemma F.6 and inequality (iii) is by repeatedly applying inequality (ii). Then, by applying Equation 32 to Equation (31), we have:
|| 11, S log det(ZT+1)
del
(
T
< 2d
1
dd
where inequality (i) is obtained by applying Lemma
F7
Lemma F.3. Suppose n, E [K] for all t. Let (es, be sequence in Rd such that
xll & 1, and define Z, = Σt En= 2y 2T,2TT + NTa where X 2 Then, we obtain
27 (1+
Σ (m. 2 2) ||2,, s 2d 2d
dh
Proof. We follow the proof of Lemma 11 of Abbasi- Yadkori et al. for all and k, the following holds:
[1. Since 2 and || S
1
||
Z l22
1 11
< 1.
Amin
Amin (Xla)
35

---

Let T = f [T] h 2 2}. Using that 2 S
2 log(( + 2) for any E [0, 1], we have:
T
Σ 1m 2 2) |,, 12; -
Σ
log
+ [[ 2 2} ||
$ Σ log (1+ || (2,1
IET
I log II
(1 | 12.1
KET
log
II
11+ 2 (2,1)
(33)
IET
where 2, = -=ETTT 2T,27,2 Ald 3 Zz Also, the following holds:
(el(2)) 2 del()Ta) II
(1+ || 12.112111))
(34)
TET.
r<t
where Equation (34 follows from applying the same determinant update steps in Equation Then, by substituting Equation (34) into Equation
33
we have:
det (ZT(+)+)))))
fm, 2 2} Σ
|
22,1 s log det(Ala)
T
2d log
1
where inequality (i) is obtained by applying Lemma F.7
Lemma F.4 (Lemma 4.2 of Qin et al. most K, and define
25
For all I 1,2,..., ,, let S. S [N] be a subsel of size
VR Ma
t=1 iES;
If 2 K and |æ,, S for all t and i, then
ΣΣ
|o. v S log (et - 2 2og deet((())))
(=1 lES.
Lemma F.5 (Lemma E.3 from Lee et al. [6).. Given æ E Rd, for any 0, 02 E Rd
Jō (x 01) (1 02) S | 01) σ (1 T 02)1.
Lemma E66 (Lemma A.3 from Li et al. (19), Let Fdx1 1 1 S Then we have
det
I+
1+
Lemma E.7 (Lemma 10 from Abbasi-Yadkori et al.
Suppose Iı, X2, .., Zn E Rdd and for any
1 < i n, | I 1. Let
VT Σ 1=1
W + AI for some X 0.
Then, we have
dot(Vn) < () d)
36

---

6000 G Numerical Study Details
G.2 Experiments on Simulated Data with MovieLens 100K
Dataset. We use the Movielenns 100K dataset, which contains 100, 000 ratings (on a 1-5 scale) from 943 users for 1, 682 movies. Since the ratings are not binary, we convert them into binary labels by assigning feedback for ratings 2 4 and 0 for ratings S 3. After preprocessing. the dataset contains 55, 375 interactions across 943 users and 1, 682 movies.
Feature extraction. Let M E R 1682 to obtain M UEVT, We treat UΣ E 9433 as the user as the movie feature matrix. Let u, E R denote the t-th row vector US, and eú E R denote the i-th column vector of VT For each user-movie pair (4, i), we construct the 25-dimensional context vector J4, vec(u, & vs), where @ denotes the outer product.
denote the user-movie rating matrix after binarization. We
apply truncated SVD with rank feature matrix and V E R5x 1682 1662
Online evaluation. We empirically evaluate the performance of our proposed algorithm, UCB-CLB, and compare it with three baselines; UCB-CCA [7]. CLogUCB [21]. and VA-CLogUCB [21] At each round [T]. we sample a user uniformly random from the 943 users, and the agent selects movie from a pool of N 1682 candidates. Because the norm of 6* is large (e.g., ||0 ll2 2 5), the condition number is small. To evaluate the effect of the cascade length K, we report the cumulative regret under two settings, K = 5 and K = 10, while keeping all other parameters fixed.
N=1682, K=5, d=25
N=1682, K= 10, d=25
600
ClogUCe
CLogUCB
Time [seconds)
500
JCB-CCA
CLogUCB
Time (seconds)
400
UCB-CCA
VA-CLogUCB
400
UCB-CLB
300
UCB-CLB
300
200
200
100
100
0
01
2000
4000
8000
10000
2000
4000
6000
8000
10000
Round (c)
Round (t)
Figure 3: Cumulative running time for varying cascade lengths (K 5, 10) with N = 1642 and
d = 25. Error bars indicate standard error, and all results are averaged over over 5 random seeds.
We evaluate the computational efficiency of the algorithms by plotting the cumulative running time (in seconds) over 10000 rounds for two cascade lengths, K == and K 10, with N 1682 and d = 25. As shown in the figures, UCB-CLI -LBB consistently maintains significantly lower computational cost compared to UCB-CCA, CLogUCB and VA- CLogUCB across different values of K. This efficiency reflects the algorithmic design of linear reward structure and an efficient swapping strategy, and employs OMD updates with a per- round cost independent of t. In contrast, UCB-CCA, CLogUCB and VA-CLogUCB rely MLE updates, whose computational cost increases with each round. Overall, the results demonstrate that UCB-CLB achieves strong computational efficiency without sacrificing performance.
which avoids costly recomputation by leveraging the
Computational resources. All experiments were conducted on server equipped with an Intel Xeon R Gold 6526R CPU (16 cores, 2.8GHz, 37.5MB cache, 3UPI, 195W).
H
Limitations
While our work revisits contextual cascading bandits under both logistic and linear reward models, these modeling choices come with certain limitations. First, we assume that the feedback for each arm follows either logistic or linear function of its context. More flexible models could be explored in future work. Second, we adopt the assumption that the feedback from different arms within a cascade is independent, which may not always hold in practice. Finally, in the linear feedback setting, we additionally assume that the expected feedback strictly greater than zero for all arms and rounds, to ensure that the regret decreases for sufficiently large cascade lengths. While this assumption is mild
37

---

in practice, it may not always be satisfied. Nevertheless. we believe that this work offers significant contributions by revisiting the contextual cascading bandit framework and providing improved regret analysis with carefully designed algorithms.
I Broader Impacts
This work revisits contextual cascading bandits with improved theoretical guarantees under logistic and linear models, which can directly support real- cal-world applications such as personalized recommen- dation, content ranking, and interactive decision- making. In these real-world applications, users are often exposed long sequences of items sometimes tens hundreds nundreds-beefrre making decision. Our algorithms are designed to remain robust and practically effective even in long-sequence settings with partial feedback, which are common in real-world recommendation scenarios. Nevertheless, such systems should be deployed with care, as they may reinforce biases or reduce content diversity,
38


Reviews:
[{"review_id": "1Ch62CjgGT", "reviewer": "Reviewer_C937", "summary": "This paper considers contextual cascading bandits where an agent select ordered lists of $K$ arms from $N$ total arms, receiving sequential feedback until a criterion is met. \n\nThe authors propose UCB with online mirror descent for cascading logistic bandits, which requires only $O(1)$ per-round computation, independent of $T$. \n\nThis work is the first to prove that longer cascades can improve performance", "questions": "Q1. In the description of Algorithm 2 on page 5, there is no explanation on how to choose $i_t^{(1)}$ and $i_t^{(2)}$.\n\nQ2. When $K$ is not large enough, how can you argue that your regret bound is the tightest compared to previous results (on Page 2)?", "limitations": "Yes", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- With the help of OMD subroutine, the proposed algorithm is computationally efficient.\n- The first to prove that longer cascades can improve performance\n- Provides first lower bound derivation for contextual cascading bandits\n\nWeaknesses:\n- There is still s gap between the upper and lower bound. It would be better if the authors discuss more on how to close the gap in the future.\n\n- The regret bound increases when $K$ is relatively small, especially when $\\bar p$ is large.", "was_revised": true, "final_justification": "The authors addressed most of my concerns. I will keep my score.", "rebuttal": "Thank you for your time to review our paper and for your valuable feedback. Here are our responses to each comment and question:\n\n**1. Gap between the Upper-Lower Bound Gap**\n\nAs the reviewer pointed out, closing the gap between the current upper and lower bounds—i.e., matching $\\bar{p}$ and $\\underline{p}$—is indeed an important direction for future research. At present, we do not yet know how to achieve minimax optimality in this regime. One potential approach is to pursue instance-dependent regret bounds, as done by Abeille et al. (2021). For example, by defining $p^\\star = \\sigma_0((x^\\star)^\\top \\theta^\\star)$, where $x^\\star$ is an optimal arm, one could try to derive $p^\\star$-dependent regret bounds instead of relying on worst-case probabilities ($\\bar{p}$ and $\\underline{p}$). While promising, this line of work is beyond the current scope and we leave it for future work. We thank the reviewer for this valuable and constructive suggestion.\n\n**2. Discussion of Regret Bound for Small $K$ and Large $\\bar{p}$**\n\nEven though our regret bound may increase in the small-$K$ regime with particularly large $\\bar{p}$, we emphasize that this is the **first regret bound** to explicitly capture and improve with increasing $K$, with the explicit dependence on both $K$ and $\\bar{p}$. We believe this constitutes a significant and meaningful contribution to the community. \nThis theoretical result is NOT just an artifact of the loose analysis. That is because we establish the same scale of lower bound (modulo the difference between $\\bar{p}$ and $\\underline{p}$), which further supports our theoretical findings and implications. That is, it may be possible in the worst-case scenario for the small-$K$ regime with particularly large $\\bar{p}$, the regret may initially increase with $K$ but eventually decrease as $K$ becomes sufficiently large although such scenarios may not appear in practice. \nWe sincerely believe that this finding should NOT be considered as weakness. It is rather the nature of the problem that our work presents for the first time as the true scaling.\n\nFurthermore, we would like to highlight that in the bandit literature, it is common for different regret bounds to coexist, with each being tighter under different conditions. For example, in linear bandits, two widely recognized optimal regret bounds are: (1) $\\tilde{\\mathcal{O}}(d\\sqrt{T})$, and (2) $\\tilde{\\mathcal{O}}(\\sqrt{dT \\log N})$, which additionally depends on the number of arms $N$. When the number of arms is relatively small (e.g., $N = \\mathcal{O}(e^d)$), the bound $\\tilde{\\mathcal{O}}(\\sqrt{dT \\log N})$ is tighter. Conversely, when $N$ is large, $\\tilde{\\mathcal{O}}(d\\sqrt{T})$ becomes the better guarantee.\n\nIn the same spirit, our newly established bounds become much tighter than existing bounds for cascading contextual bandits, as $K$ increases, and optimal in the large-$K$ regime. We will incorporate this clarification into the final revision.\n\nAdditionally, we conduct an experiment to demonstrate the robustness of our algorithm to the value of $\\bar{p}$ in practice. Importantly, the actual performance depends on the no-click probabilities $\\sigma_0(x_{t,i}^\\top \\theta^\\star)$ for items in the selected set $C_t$ (i.e., $i \\in C_t$), rather than on the worst-case value $\\bar{p} = \\sup_x \\sigma_0(x^\\top \\theta^\\star)$ used in the regret analysis. As a result, the realized regret does NOT typically scale with $\\bar{p}$—the worst-case analysis can be overly conservative.\n\nThe following table illustrates that **even when $\\bar{p}$ is large, the observed cumulative regret decreases monotonically as $K$ increases**, highlighting the practical stability of our method.\n\n| $K$  | $\\bar{p} = 0.37$          | $\\bar{p} = 0.74$          | $\\bar{p} = 0.95$          |\n|---:|-------------------:|-------------------:|-------------------:|\n| $2$  | $1.712 × 10^{1}$        | $1.884 × 10^{1}$        | $2.103 × 10^{1}$        |\n| $4$  | $3.965 × 10^{-1}$       | $4.833 × 10^{-1}$       | $5.183 × 10^{-1}$       |\n| $6$  | $1.089 × 10^{-2}$       | $1.322 × 10^{-2}$       | $2.942 × 10^{-2}$       |\n| $8$  | $4.042 × 10^{-4}$       | $4.928 × 10^{-4}$       | $1.147 × 10^{-3}$       |\n| $10$ | $1.992 × 10^{-5}$       | $2.409 × 10^{-5}$       | $4.615 × 10^{-5}$       |\n\n**3. Selection Rule for $i_t^{\\scriptscriptstyle (1)}$ and $i_t^{\\scriptscriptstyle (2)}$**\n\nThank you for pointing out this omission. The exact rule for choosing the two swap arms is stated on page 7, line 226:\n\\begin{equation}\ni_t^{\\scriptscriptstyle  (1)} = \\arg\\max_{i\\in C_t}\n\\dot\\sigma_1 \\bigl(x_{t,i}^{\\top}\\theta_t\\bigr)\n\\lVert x_{t,i}\\rVert_{H_t^{-1}}, \\quad\ni_t^{\\scriptscriptstyle (2)} = \\arg\\max_{i\\in C_t}\n\\lVert x_{t,i}\\rVert_{H_t^{-1}}.\n\\end{equation}\nTo make this clear in the final version, we will (i) assign an explicit equation number to the formula above, and (ii) add a reference to the equation directly inside Algorithm 2 (page 5).\nWe appreciate your careful reading and for helping us improve the clarity."}, {"review_id": "kdprbA06tP", "reviewer": "Reviewer_Rqrd", "summary": "This paper addresses a long-standing and misunderstood problem in the field of recommendation systems: how the length of a recommended list (the cascade length.", "questions": "1. In the experiment, the K values are only 5, 10. Could the authors try a larger K, such as 50, 100? Also, it would be interesting and convincing if they could plot the curve between the regret and a range of K to validate their theories.\n\n2. For \\bar p in the bound, \\bar p is small when all the arms in the space has a relatively high logit. It seems a little strict since there may exist x such that x^T\\theta is very small. In this case, the bound only decreases when K is sufficienlty large. Could the authors disscuss more about the limitations of their result?", "limitations": "no", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThey propose a new Upper Confidence Bound (UCB) algorithm for cascading logistic bandits. It uses Online Mirror Descent (OMD) for parameter estimation, which makes it computationally efficient and scalable, with per-round costs that are independent of the total time horizon. Specifically, they novelly achieve the decreasing for large K regret bound compared to others.\n\nWeaknesses:\n1. They assume a lower bound for the vairances. This assumptions are not so standard. Could the authors discuss about this assumption, why do they need it and could their analysis degrade to deterministic settings where variances are zero?", "was_revised": true, "final_justification": "The authors solve my questions, so I will raise my score accordingly.", "rebuttal": "We appreciate your thoughtful feedback on our work. Below, we provide detailed responses to each comment and question.\n\n**1. Variance Lower-Bound Assumption**\n\nBefore addressing the reviewer’s concern, we would first like to clarify the intended meaning of “variance” in the review. We assume the reviewer is referring to the parameter $\\kappa$. In that case, we strongly believe that the **existence of a non-zero $\\kappa$ should NOT be viewed as a weakness** of our paper, since $\\kappa$ is always non-zero as long as the features and parameter vectors are bounded. In the logistic bandit literature, it is standard practice to \\textit{define} $\\kappa$ explicitly—rather than \\textit{assume} it—based on problem parameters (e.g., Equation (2) of Faury et al., 2020 [1]). Therefore, we believe it is more appropriate to formally define $\\kappa$ rather than assume its non-zeroness. For clarity, we will revise Assumption 5.3 to be a Definition in our final version.\n\nTo further elaborate on $\\kappa$: this parameter captures the **degree of non-linearity** of the sigmoid function. Specifically, $\\kappa$ becomes smaller when the agent selects actions across a wider range of the sigmoid. As such, $\\kappa$ quantifies the difficulty of learning induced by the non-linearity of the logistic model. This dependence is not unique to our work—it has been unavoidable in much of the existing literature (Faury et al., 2020, 2021, 2022; Lee and Oh, 2024, 2025; Vial et al., 2022; Liu et al., 2024), whether it appears in the leading term or non-leading constants of the regret bounds.\n\nIn response to the reviewer’s question regarding the deterministic choice setting: such a setting corresponds to a degenerate case where each item is either (a) always clicked or (b) never clicked. Neither case is interesting from a learning or decision-making perspective. In case (a), the learner could simply select any $K$ items at random and incur zero regret, since every selected item leads to a click. In case (b), the learner also incurs zero regret, regardless of the selection, as the optimal reward is itself zero. Thus, the deterministic setting is uninformative and trivial in terms of both exploration and regret analysis.\n\n[1] Faury, Louis, et al. \"Improved optimistic algorithms for logistic bandits.\" International Conference on Machine Learning. PMLR, 2020.\n\n**2. Additional Experiments: larger $K$**\n\nIn accordance with this year’s NeurIPS rebuttal guidelines, we are not permitted to include plots; thus, we present the results in tabular form below. $R(t)$ denotes the cumulative regret up to round $t$, whereas $R(t)/t$ is the average regret at round $t$. \nWe report $R(t)/t$ to check whether cumulative regret is sublinear.\n\nAs per reviewer's request, we have conducted additional MovieLens benchmark experiments with larger $K = 50, 100$ to evaluate the robustness of our method. Consistent with our theoretical findings, the **regret decreases as $K$ increases**, demonstrating that our method scales favorably with the cascade length. The scale difference is enormous: for every round in the table, $R(t)$ at $K = 100$ is roughly $10^{15} \\sim 10^{16}$ times smaller than at $K = 50$.\n\n\n|  $K$   |  $t$   |     $R(t)$      |   $R(t) / t$   |\n|----:|-----:|--------------:|-------------:|\n| $50$  | $1000$ | $6.09 × 10^{-17}$ | $6.09 × 10^{-20}$ |\n| $50$  | $2000$ | $9.49 × 10^{-17}$ | $4.74 × 10^{-20}$ |\n| $50$  | $3000$ | $13.04 × 10^{-17}$| $4.35 × 10^{-20}$ |\n| $50$  | $4000$ | $15.29 × 10^{-17}$| $3.82 × 10^{-20}$ |\n| $50$  | $5000$ | $17.54 × 10^{-17}$| $3.51 × 10^{-20}$ |\n\n|  $K$   |  $t$   |     $R(t)$      |   $R(t) / t$   |\n|-----|-----|-----|-----|\n| $100$ | $1000$ | $0.88 × 10^{-32}$ | $8.80 × 10^{-36}$ |\n| $100$ | $2000$ | $1.59 × 10^{-32}$ | $7.96 × 10^{-36}$ |\n| $100$ | $3000$ | $2.14 × 10^{-32}$ | $7.14 × 10^{-36}$ |\n| $100$ | $4000$ | $2.50 × 10^{-32}$ | $6.26 × 10^{-36}$ |\n| $100$ | $5000$ | $2.88 × 10^{-32}$ | $5.75 × 10^{-36}$ |\n\n**3. Large $\\bar{p}$ Case**\n\nEven though our regret bound may increase in the small-$K$ regime with particularly large $\\bar{p}$, we emphasize that this is the **first regret bound** to explicitly capture and improve with increasing $K$, with the explicit dependence on both $K$ and $\\bar{p}$. We believe this constitutes a significant and meaningful contribution to the community. \nThis theoretical result is NOT just an artifact of the loose analysis. That is because we establish the same scale of lower bound (modulo the difference between $\\bar{p}$ and $\\underline{p}$), which further supports our theoretical findings and implications. That is, it may be possible in the worst-case scenario for the small-$K$ regime with particularly large $\\bar{p}$, the regret may initially increase with $K$ but eventually decrease as $K$ becomes sufficiently large although such scenarios may not appear in practice. \nWe sincerely believe that this finding should NOT be considered as weakness. it is rather the nature of the problem that our work presents for the first time as the true scaling.\n\nFurthermore, we would like to highlight that in the bandit literature, it is common for different regret bounds to coexist, with each being tighter under different conditions. For example, in linear bandits, two widely recognized optimal regret bounds are: (1) $\\tilde{\\mathcal{O}}(d\\sqrt{T})$, and (2) $\\tilde{\\mathcal{O}}(\\sqrt{dT \\log N})$, which additionally depends on the number of arms $N$. When the number of arms is relatively small (e.g., $N = \\mathcal{O}(e^d)$), the bound $\\tilde{\\mathcal{O}}(\\sqrt{dT \\log N})$ is tighter. Conversely, when $N$ is large, $\\tilde{\\mathcal{O}}(d\\sqrt{T})$ becomes the better guarantee.\n\nIn the same spirit, our newly established bounds are optimal in the small-$\\bar{p}$ regime, while for large $\\bar{p}$, the existing bound of $\\tilde{\\mathcal{O}}(d\\sqrt{T})$ remains optimal. We will incorporate this clarification into the final revision.\n\nAdditionally, we conduct an experiment to demonstrate the robustness of our algorithm to the value of $\\bar{p}$ in practice. Importantly, the actual performance depends on the no-click probabilities $\\sigma_0(x_{t,i}^\\top \\theta^\\star)$ for items in the selected set $C_t$ (i.e., $i \\in C_t$), rather than on the worst-case value $\\bar{p} = \\sup_x \\sigma_0(x^\\top \\theta^\\star)$ used in the regret analysis. As a result, the realized regret does NOT typically scale with $\\bar{p}$—the worst-case analysis can be overly conservative.\n\nThe following table illustrates that \\textbf{even when $\\bar{p}$ is large, the observed regret decreases monotonically as $K$ increases}, highlighting the practical stability of our method.\n\n| $K$  | $\\bar{p} = 0.37$          | $\\bar{p} = 0.74$          | $\\bar{p} = 0.95$          |\n|---:|-------------------:|-------------------:|-------------------:|\n| $2$  | $1.712 × 10^{1}$        | $1.884 × 10^{1}$        | $2.103 × 10^{1}$        |\n| $4$  | $3.965 × 10^{-1}$       | $4.833 × 10^{-1}$       | $5.183 × 10^{-1}$       |\n| $6$  | $1.089 × 10^{-2}$       | $1.322 × 10^{-2}$       | $2.942 × 10^{-2}$       |\n| $8$  | $4.042 × 10^{-4}$       | $4.928 × 10^{-4}$       | $1.147 × 10^{-3}$       |\n| $10$ | $1.992 × 10^{-5}$       | $2.409 × 10^{-5}$       | $4.615 × 10^{-5}$       |"}, {"review_id": "ZTqFWvj7hU", "reviewer": "Reviewer_3rPH", "summary": "This paper investigates the role of the cascade length $K$ in contextual cascading bandits—a learning framework relevant to search and recommendation systems. Contrary to previous works suggesting that regret increases with $K$, the authors theoretically and empirically demonstrate that regret can decrease as $K$ grows large. They propose a novel UCB-based algorithm, UCB-CLB, which uses Online Mirror Descent (OMD) for efficient parameter estimation, achieving a regret upper bound of $\\tilde{O}(K^{\\bar{p}} d \\sqrt{T})$ that diminishes with increasing $K$. They also provide the first matching lower bound in the contextual setting, resolving a long-standing open problem about the impact of cascade length.", "questions": "1. **Clarification on $p$ vs $\\bar{p}$**: Can the authors comment on how large the gap between $p$ and $\\bar{p}$ might be in practice, and whether it's observable in experiments?\n2. **OMD vs MLE Trade-offs**: Could the authors elaborate on potential limitations of OMD versus MLE, especially in terms of statistical efficiency in low-noise regimes?\n3. **Impact of Arm Pool Size $N$**: Even though the bounds are independent of $N$, does increasing $N$ affect empirical performance (e.g., convergence speed)?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "#### **Strengths**\n\n* The paper challenges and overturns a widely held belief in cascading bandits literature—that regret necessarily increases with cascade length. This is an important and surprising contribution.\n* The UCB-CLB algorithm leverages OMD for parameter estimation, significantly improving computational efficiency compared to MLE-based approaches.\n* The paper provides both upper and lower bounds that match up to logarithmic factors, a rare accomplishment in bandit theory.\n* UCB-CLB is shown to be scalable and effective on real-world datasets like MovieLens, and avoids non-convex optimization bottlenecks.\n*  The paper is generally well-organized, with a thorough theoretical exposition, detailed algorithms, and compelling empirical results.\n\n#### **Weaknesses**\n\n* Some results rely on regularity conditions such as bounded features and logistic noise parameters, which may not hold in all real-world deployments.\n* While the MovieLens experiments are convincing, broader validation across datasets or task domains would strengthen the claims.\n* The lower bound uses a slightly different constant $p$ than the upper bound's $\\bar{p}$, though the authors do acknowledge and justify this.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work. We sincerely appreciate your constructive feedback and provide our detailed responses below.\n\n**1. Discussion of Regularity Conditions**\n\nCould you kindly clarify what is meant by the \"logistic noise parameters\"? We assume this refers either to $\\theta^\\star$ or to the curvature parameter $\\kappa$. Accordingly, we will address the boundedness of the three relevant quantities: the feature vector $x$, the true parameter $\\theta^\\star$, and the curvature parameter $\\kappa$.\nBelow, we explicitly show that these boundedness assumptions are made for convenience and can be easily relaxed or reformulated as definitions. Therefore, we believe they should \\textbf{not be viewed as weaknesses} of our work.\n\n**1) Boundedness assumption on $x$ and $\\theta^\\star$ (Assumption 5.1):**\nWe would like to clarify that this assumption is made purely for convenience and cleaner presentation. If $x$ and $\\theta^\\star$ are bounded by a general constant $S$ (rather than 1), the regret bound simply scales with $\\text{poly}(S)$. For example, if $\\Vert x \\Vert_{2} \\le 1$ and $ \\Vert \\theta^{\\star} \\Vert_2 \\leq S$, the regret becomes $\\tilde{\\mathcal{O}} \\left( S^{3/2} K \\bar{p}^{K-1} d \\sqrt{T} \\right)$, since the confidence parameter scales as $\\beta_{t,k}(\\delta) = \\tilde{\\mathcal{O}}(S^{3/2} \\sqrt{d})$.\n\n**2) Discussion about $\\kappa$ (Assumption 5.3):**\nWe would like to highlight that $\\kappa$ is always non-zero as long as the features and parameter vectors are bounded. In the logistic bandit literature, it is standard practice to _define_ $\\kappa$ explicitly—rather than _assume_ it—based on problem parameters (e.g., Equation (2) of Faury et al., 2020 [1]). Therefore, we believe it is more appropriate to formally define $\\kappa$ rather than assume its non-zeroness. For clarity, we will revise Assumption 5.3 to be a Definition in our final version.\n\n[1] Faury, Louis, et al. \"Improved optimistic algorithms for logistic bandits.\" International Conference on Machine Learning. PMLR, 2020.\n\n**2, Additional Experiments: KuaiRand Pure Click Datasets [2]**\nAs the current NeurIPS rebuttal guidelines prohibit the inclusion of figures, we instead present the results in the table below. \n$R(t)$ denotes the cumulative regret up to round $t$, whereas $R(t)/t$ is the average regret at round $t$. \nWe report $R(t)/t$ to check whether cumulative regret is sublinear.\nFollowing the reviewer’s suggestion, we ran additional experiments with cascade lengths $K = 10$ on the KuaiRand-Pure dataset.\n\nKuaiRand-Pure is a real-world recommendation benchmark derived from the short-video platform Kuaishou; it contains anonymised user–item interaction logs with click indicators, which we adopt as the binary reward signal for our bandit task.\nConsistent with our theoretical findings, the regret decreases as $K$ increases, confirming that our method scales favourably with longer cascades and remains robust across datasets.\n\n(i) UCB-CLB with K=5\n| $t$    | $R(t)$  | $R(t)/t$   |\n|:------:|:--------:|:-----------:|\n| $1000$ | $13.15$  | $0.013$     |\n| $2000$ | $16.14$  | $0.008$     |\n| $3000$ | $18.57$  | $0.006$     |\n| $4000$ | $20.48$  | $0.005$     |\n| $5000$ | $21.96$  | $0.004$     |\n\n(ii) UCB-CLB with K=10 \n| $t$    | $R(t)$ | $R(t)/t$             |\n|:------:|:------:|:--------------------:|\n| $1000$ | $0.92$ | $9.19 \\times 10^{-4}$ |\n| $2000$ | $1.06$ | $5.31 \\times 10^{-4}$ |\n| $3000$ | $1.15$ | $3.84 \\times 10^{-4}$ |\n| $4000$ | $1.20$ | $3.00 \\times 10^{-4}$ |\n| $5000$ | $1.24$ | $2.47 \\times 10^{-4}$ |\n\n[2] Gao, Chongming, et al. \"Kuairand: An unbiased sequential recommendation dataset with randomly exposed videos.\" Proceedings of the 31st ACM international conference on information & knowledge management. 2022.\n\n**3, Clarification on $\\underline{p}$ vs $\\bar{p}$**\n\nWhile our upper and lower bounds differ due to the gap between $\\bar{p}$ and $\\underline{p}$, these quantities are often overly conservative in practice. As a result, the realized regret typically lies between the two—**significantly lower than the upper bound and higher than the lower bound**—indicating that our algorithm is **robust** to the worst-case values of $\\bar{p}$ and $\\underline{p}$. To illustrate this, we provide a table below comparing the theoretical upper bound, theoretical lower bound, and the actual cumulative regret observed in an experiment with $\\bar{p} = 0.8$ and $\\underline{p} = 0.1$.\nIn the table:\n\n- \"Upper Bound\" refers to the \\textit{theoretical} regret upper bound,\n- \"Lower Bound\" refers to the \\textit{theoretical} regret lower bound, and\n- \"Cum. Regret\" refers to the cumulative regret actually _incurred_ by our algorithm on the MovieLens 100K dataset.\n\n|                | $K=4$       | $K=6$       | $K=8$       | $K=10$      |\n|----------------|---------------|---------------|---------------|---------------|\n| Upper Bound    | $1619.09$   | $1554.32$   | $1326.36$   | $1061.08$   |\n| Cum. Regret    | **$18.36$** | **$5.15$**  | **$1.39$**  | **$0.36$**  |\n| Lower Bound    | $3.16 \\times 10^{0}$   | $4.74 \\times 10^{-2}$   | $6.32 \\times 10^{-4}$   | $7.91 \\times 10^{-6}$   |\n\nCurrently, we do not yet know how to close the gap between $\\bar{p}$ and $\\underline{p}$ to achieve minimax optimality. One promising direction is to pursue instance-dependent regret bounds, as in Abeille et al. (2021). For example, by defining $p^\\star = \\sigma_0((x^\\star)^\\top \\theta^\\star)$, where $x^\\star$ is an optimal arm, one could derive $p^\\star$-dependent regret bounds instead of relying on worst-case quantities like $\\bar{p}$ and $\\underline{p}$. While this is a meaningful direction, it falls outside the scope of the present work, and we leave it for future research. We thank the reviewer for this valuable and constructive suggestion. Moreover, note that our algorithm does not need to observe or know $\\bar{p}$ or $\\underline{p}$ at any point. \n\n**4. OMD vs. MLE Trade-offs in Low-noise Regimes**\n\nIt remains _unclear_ which method—OMD or MLE—is preferable. In a low-noise regime, click feedback is almost deterministic. Under the logistic model this means the parameter norm $S$ must be large (i.e., $\\\\| \\theta\\\\|_2 \\leq S$), reflecting a strong signal or a wide parameter space.\n\nRecall that when $\\\\|\\theta^\\star\\\\|_2 \\leq S$, our regret bound (that uses OMD) scales as $\\tilde{\\mathcal{O}}\\left(S^{3/2} K \\bar{p}^{K-1} d \\sqrt{T} \\right)$, which deteriorates as $S$ increases. In contrast, for MLE-based approaches, $S$-free regret bounds have been established in the GLM bandit literature (e.g., Lee et al., 2024 [3]). This suggests that a similar $S$-free regret might be achievable in our setting by adopting MLE and applying similar techniques. Alternatively, an \\textit{adaptive warm-up} strategy, as proposed by Lee and Oh [4], could also eliminate the dependence on $S$. \n\nBecause both MLE and carefully tuned OMD variants can avoid explicit $S$ dependence, deciding which approach is superior—even in low-noise scenarios—remains unresolved. Further work is required to pin down their precise statistical and computational trade-offs.\n\n\n[3] Lee, Junghyun, Se-Young Yun, and Kwang-Sung Jun. \"A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits.\" Advances in Neural Information Processing Systems 37 (2024): 124640-124685.\n\n[4] Lee, Joongkyu, and Min-hwan Oh. \"Improved Online Confidence Bounds for Multinomial Logistic Bandits.\" Forty-second International Conference on Machine Learning.\n\n**5. Impact of Arm Pool Size $N$**\n\nOur regret bound—and the algorithm in practice—is $N$-independent; to substantiate this, we conduct additional experiments.\nUsing the MovieLens-100K benchmark with cascade length $K=5$, we vary the arm pool from $N=2000, 2500, 3000$ movies while keeping the same optimal arm across all settings to ensure a fair comparison. \nThe resulting cumulative-regret, $R(t)$ is reported in the table below. \n\nAcross all horizons the largest gap between any two $R(t)$ is $0.009$ (at $t=5000$), which is approximately $1\\%$ of the regret scale in those rows. Thus, even when $N$ increases from $2000$ to $3000$, the regret remains almost unchanged, supporting our theoretical results that regret does not depend on $N$.\n\n|          |  $N=2000$  | $N=2500$ | $N=3000$ |\n|----------|------------|----------|----------|\n| $t$      | $R(t)$     | $R(t)$   | $R(t)$   |\n| $1000$   | 0.0233     | 0.0245   | 0.0307   |\n| $2000$   | 0.0356     | 0.0342   | 0.0409   |\n| $3000$   | 0.0432     | 0.0421   | 0.0492   |\n| $4000$   | 0.0506     | 0.0510   | 0.0581   |\n| $5000$   | 0.0593     | 0.0612   | 0.0683   |"}, {"review_id": "0TsJvkcH3B", "reviewer": "Reviewer_LwJ1", "summary": "The cascading bandit problem is widely used in recommendation systems, search engines, and online advertising. In this model, an agent selects an ordered list (cascade) of length $ K $ from $ N $ options (arms), and users sequentially browse the list, stopping at the first appealing item. Traditional studies suggest that regret—defined as the difference in expected rewards between the optimal and selected cascades—increases or remains constant with larger $ K $. However, this contradicts the intuition that longer cascades offer more feedback opportunities, potentially reducing regret. The paper challenges this view, proving that in contextual cascading bandits, regret decreases when $ K $ is sufficiently large.", "questions": "1. The UCB-CLB algorithm leverages Online Mirror Descent (OMD) and DO-SWAP techniques to enhance computational efficiency and optimize regret. Can this approach effectively extend to dynamic environments, such as those with time-varying contextual features?\n\n2. The paper introduces the combination of OMD and DO-SWAP as a novel proof technique to address the sequential feedback characteristics of cascading bandits. What new challenges might this integration introduce?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. The paper challenges existing research on the impact of cascade length $ K $ on regret in contextual cascading bandits, demonstrating that regret decreases when $ K $ is sufficiently large. Specifically, the authors propose a new regret upper bound of $\\mathcal{O}(K \\bar{p}^{K-1} d \\sqrt{T})$, where $\\bar{p}$ is the upper bound of the feedback probability, $d$ is the dimension of the context vector, and $T$ is the total number of rounds. This bound shows that regret diminishes with increasing $K$ due to the exponential decay of $\\bar{p}^{K-1}$ ($\\bar{p} < 1$).\n\n2. Additionally, the authors derive a matching lower bound of $\\Omega(K \\underline{p}^{K-1} d \\sqrt{T})$, where $\\underline{p}$ is the lower bound of the feedback probability. Together, these bounds fully characterize the true trend of regret with respect to $K$, addressing a theoretical gap in contextual cascading bandits.\n\n3. The paper introduces UCB-CLB (Upper Confidence Bound for Cascading Logistic Bandits), an algorithm based on Upper Confidence Bound (UCB) that integrates Online Mirror Descent (OMD) and a cascade restructuring technique (DO-SWAP). Operating under a logistic model, UCB-CLB achieves efficient parameter estimation and cascade selection. By avoiding the high computational cost of traditional maximum likelihood estimation (MLE), UCB-CLB significantly improves efficiency while maintaining theoretically optimal regret bounds. The DO-SWAP technique optimizes the exploration-exploitation trade-off by prioritizing items with higher uncertainty in the cascade.\n\n\n**Weaknesses**\n\n1. The theoretical results rely on specific assumptions, such as Assumption 5.1 (bounded norms of feature vectors and parameters) and Assumption 5.3 (a positive lower bound $\\kappa$ in the logistic model). These assumptions may not always hold in practice. For instance, a small $\\kappa$ (indicating significant deviation from a linear model) could impact algorithm performance, despite claims that UCB-CLB remains effective in such cases. However, the paper does not thoroughly explore how violations of these assumptions affect performance, potentially limiting the generalizability of its theoretical findings.\n\n2. The analysis depends on $\\bar{p} \\leq 1/e \\approx 0.37$, where the regret upper bound decreases monotonically with increasing $K$. When $\\bar{p} > 1/e$, regret may initially increase before decreasing (as $K \\bar{p}^{K-1}$ peaks at $K = \\frac{1}{\\log(1/\\bar{p})}$). The paper does not adequately address the implications of $\\bar{p} > 1/e$ in practical high-feedback-probability scenarios, which may restrict the applicability of its theoretical results.\n\n3. Experiments only test cascade lengths $K = 5$ and $K = 10$, without exploring a broader range of $K$ values.\n\n4. The UCB-CLB algorithm relies on the DO-SWAP technique to restructure cascades, prioritizing items with higher uncertainty. While effective, this increases algorithmic complexity, potentially introducing additional computational overhead or implementation challenges in practice. The paper does not provide a detailed analysis of DO-SWAP’s computational costs or potential failure cases across different scenarios.", "was_revised": true, "final_justification": "The response from the authors resolves my concerns. I will maintain my positive rating.", "rebuttal": "We sincerely thank the reviewer for the thoughtful and detailed comments on our work. \nYour feedback has greatly helped us refine and strengthen the paper.\n\n**1. Discussion of Regularity Conditions**\n\nFirstly, Assumption 5.1 is without loss of generality: any raw feature vector can be rescaled to lie inside the unit ball before learning, and relaxing the parameter norm bound to $S$ merely multiplies the theoretical regret by $S^{3/2}$ factor.\n\nSecondly, we strongly believe that the **existence of a non-zero $\\kappa$ should NOT be viewed as a weakness** of our paper, since $\\kappa$ is always non-zero as long as the features and parameter vectors are bounded. In the logistic bandit literature, it is standard practice to _define_ $\\kappa$ explicitly—rather than _assume_ it—based on problem parameters (e.g., Equation (2) of Faury et al., 2020 [1]). Therefore, we believe it is more appropriate to formally define $\\kappa$ rather than assume its non-zeroness. For clarity, we will revise Assumption 5.3 to be a Definition in our final version.\n\nLastly, we conduct additional experiments on the MovieLens-$100K$ benchmark: reducing $\\kappa$ from $0.1$ to $0.01$ leads to no noticeable change in cumulative or average regret (see the below table). $R(t)$ denotes the cumulative regret up to round $t$, whereas $R(t)/t$ is the average regret at round $t$. \nWe report $R(t)/t$ to check whether cumulative regret is sublinear.\n\n| $\\kappa$ | $t$     | $R(t)$   | $R(t)/t$             |\n|----------|---------|----------|-----------------------|\n| $0.1$      |$2000$    | $10.97$    | $5.40 \\times 10^{-3}$ |\n|          | $4000$    | $15.80$    | $3.90 \\times 10^{-3}$ |\n|          | $6000$    | $19.83$    | $3.30 \\times 10^{-3}$ |\n|          | $8000$    | $23.84$    | $2.90 \\times 10^{-3}$ |\n|          | $10000$   | $27.28$    | $2.70 \\times 10^{-3}$ |\n\n| $\\kappa$ | $t$     | $R(t)$   | $R(t)/t$             |\n|----------|---------|----------|-----------------------|\n| $0.01$     | $2000$   | $12.66$    | $6.30 \\times 10^{-3}$ |\n|          | $4000$    | $18.46$    | $4.60 \\times 10^{-3}$ |\n|          | $6000$    | $22.94$    | $3.80 \\times 10^{-3}$ |\n|          | $8000$    | $26.94$    | $3.30 \\times 10^{-3}$ |\n|          | $10000$   | $30.54$    | $3.00 \\times 10^{-3}$ |\n\n**2. Discussion of $\\bar{p}$**\n\nWe first clarify meaning of _large_ $\\bar{p}$. Recall that \\bar p is defined as an upper bound on the non-click probability:\n$\n\\bar{p} = \\sup_{x}\\sigma_0(x^{\\top}\\theta^\\*).\n$\nConsequently, a large $\\bar{p}$ corresponds to a high–_negative_-feedback scenario.\n\nEven though our regret bound may increase in the small-$K$ regime with particularly large $\\bar{p}$, we emphasize that this is the **first regret bound** to explicitly capture and improve with increasing $K$, with the explicit dependence on both $K$ and $\\bar{p}$. We believe this constitutes a significant and meaningful contribution to the community. \nThis theoretical result is NOT just an artifact of the loose analysis. That is because we establish the same scale of lower bound (modulo the difference between $\\bar{p}$ and $\\underline{p}$), which further supports our theoretical findings and implications. That is, it may be possible in the worst-case scenario for the small-$K$ regime with particularly large $\\bar{p}$, the regret may initially increase with $K$ but eventually decrease as $K$ becomes sufficiently large although such scenarios may not appear in practice. \nWe sincerely believe that this finding should NOT be considered as weakness. It is rather the nature of the problem that our work presents for the first time as the true scaling.\n\nFurthermore, we would like to highlight that in the larger bandit literature, it is common for different regret bounds to coexist, with each being tighter under different conditions. For example, in linear bandits, two widely recognized optimal regret bounds are: (1) $\\tilde{\\mathcal{O}}(d\\sqrt{T})$, and (2) $\\tilde{\\mathcal{O}}(\\sqrt{dT \\log N})$, which additionally depends on the number of arms $N$. When the number of arms is relatively small (e.g., $N = \\mathcal{O}(e^d)$), the bound $\\tilde{\\mathcal{O}}(\\sqrt{dT \\log N})$ is tighter. Conversely, when $N$ is large, $\\tilde{\\mathcal{O}}(d\\sqrt{T})$ becomes the better guarantee.\n\nHence, it is not just a matter of which bound is tighter but rather what this work focuses is **what is the true scale of the regret in cascading contextual bandit problem** supported by both upper and lower bounds.\n\n\n**3. Additional Experiments with larger $K$**\n\nFollowing your suggestion, we run the MovieLens-$100K$ experiment with $K = 50$ and $K = 100$. \nAs the Table 6 shows, cumulative regret remains sub-linear (indicated by the steadily falling the average regret $R(t)/t$). Crucially, the overall scale of the regret $R(t)$ diminishes as $K$ increases, exactly reflecting our theoretical claim that regret decreases once the cascade length is long.\n\n| $K$  | $t$   | $R(t)$                | $R(t)/t$               |\n|------|-------|------------------------|-------------------------|\n| $50$   | $1000$  | $6.09 \\times 10^{-17}$ | $6.09 \\times 10^{-20}$  |\n|      | $2000$  | $9.49 \\times 10^{-17}$ | $4.74 \\times 10^{-20}$  |\n|      | $3000$  | $13.04 \\times 10^{-17}$| $4.35 \\times 10^{-20}$  |\n|      | $4000$  | $15.29 \\times 10^{-17}$| $3.82 \\times 10^{-20}$  |\n|      | $5000$  | $17.54 \\times 10^{-17}$| $3.51 \\times 10^{-20}$  |\n\n| $K$  | $t$   | $R(t)$                | $R(t)/t$               |\n|------|-------|------------------------|-------------------------|\n| $100$  | $1000$  | $0.88 \\times 10^{-32}$ | $8.80 \\times 10^{-36}$  |\n|      | $2000$  | $1.59 \\times 10^{-32}$ | $7.96 \\times 10^{-36}$  |\n|      | $3000$  | $2.14 \\times 10^{-32}$ | $7.14 \\times 10^{-36}$  |\n|      | $4000$  | $2.50 \\times 10^{-32}$ | $6.26 \\times 10^{-36}$  |\n|      | $5000$  | $2.88 \\times 10^{-32}$ | $5.75 \\times 10^{-36}$  |\n\n**4. Time–Complexity of DO-SWAP**\n\nContrary to your concern, the DO-SWAP subroutine imposes neither significant computational overhead nor implementation difficulty. With a single partial sort that runs in $O(K)$ time, our agent selects the two most uncertain arms within the length-$K$ cascade $C_t$. Our MovieLens-100K experiment with K=5 (See the table below) supports this claim, showing that DO-SWAP consistently consumes only $\\approx 0.7 \\%$ of total cumulative runtime even as the round $t$ grows.\n\n[Table Instruction]\n- \"Total\": is the mean cumulative runtime of the full algorithm,  \n- \"DO-SWAP\": is the mean cumulative time spent in the DO-SWAP sub-routine, \n- \"Ratio\": is the share of DO-SWAP within the total time.\n| $t$   | Total       | DO-SWAP     | Ratio  |\n|-------|-------------|-------------|--------|\n| $1000$  | $1.825$     | $0.012$     | $0.7$% |\n| $2000$  | $3.446$     | $0.024$     | $0.7$% |\n| $3000$  | $4.910$     | $0.035$     | $0.7$% |\n| $4000$  | $6.309$     | $0.045$     | $0.7$% |\n| $5000$  | $7.687$     | $0.056$     | $0.7$% |\n\n**5. Applicability to Time-Varying Contextual Features**\n\nWe would like to clarify that our current framework **already supports time-varying contextual features**. \nSection 3.2 (Problem Setting) explicitly models the environment using time-varying contextual features, confirming that our theoretical analysis already accommodates such dynamics. \n\nAccordingly, the OMD + DO-SWAP algorithm is naturally applicable to dynamic environments where contextual features change over time. \nIn our MovieLens-100K experiment, the agent observes time-varying features $x_{t,i}$ at every round $t$: a new user $u_t$ arrives, and the agent chooses among $1,642$ movies $i$. \nAs reported in Section 7 (Numerical Study), UCB-CLB with DO-SWAP achieves sub-linear regret under this setting, showing in practice that the algorithm still performs well even as the contexts change over time. \n\n**6. Integrating OMD and DO-SWAP Introduces No Additional Challenges**\n\nOMD is used for parameter estimation, while DO-SWAP handles the cascading selection process. These two components operate **independently** of each other. For example, one could substitute OMD with an alternative estimator such as MLE, and DO-SWAP would remain fully functional without modification."}]

Author rebuttal:

Meta-review: This paper investigates the role of the cascade length $K$ in contextual cascading bandits. Contrary to previous works suggesting that regret increases with $K$, the authors theoretically and empirically demonstrate that the regret can decrease as $K$ grows large. They propose a novel UCB-based algorithm, UCB-CLB, which utilizes Online Mirror Descent (OMD) for efficient parameter estimation, achieving a regret upper bound that can diminish with $K$. They also provide an almost matching lower bound. Experiment results on a real-world dataset are also demonstrated.

As the reviewers have pointed out, this paper has made several major contributions. To the best of our knowledge, this is the first paper proving that a longer cascade length can improve the performance of a contextual cascading bandit. This is important and surprising. Moreover, the proposed algorithm leverages OMD for parameter estimation, which significantly improves computational efficiency compared to more standard MLE-based approaches. Overall, the paper is well-written.

All reviewers are on the acceptance side for this paper. After reading the paper, the reviews, and the discussions, I agree with the reviewers and recommend accepting this paper.
Decision: Accept (poster)