Minimax Regret for Cascading Bandits
Authors: Daniel Vial
sujay sanghavi
Sanjay Shakkottai
R. Srikant
Venue: NeurIPS 2022 Accept (2022)
Keywords: online learning-to-rank
cascading bandits
linear stochastic bandits

Abstract: Cascading bandits is a natural and popular model that frames the task of learning to rank from Bernoulli click feedback in a bandit setting. For the case of unstructured rewards, we prove matching upper and lower bounds for the problem-independent (i.e., gap-free) regret, both of which strictly improve the best known. A key observation is that the hard instances of this problem are those with small mean rewards, i.e., the small click-through rates that are most relevant in practice. Based on this, and the fact that small mean implies small variance for Bernoullis, our key technical result shows that variance-aware confidence sets derived from the Bernstein and Chernoff bounds lead to optimal algorithms (up to log terms), whereas Hoeffding-based algorithms suffer order-wise suboptimal regret. This sharply contrasts with the standard (non-cascading) bandit setting, where the variance-aware algorithms only improve constants. In light of this and as an additional contribution, we propose a variance-aware algorithm for the structured case of linear rewards and show its regret strictly improves the state-of-the-art.

Minimax Regret for Cascading Bandits
Daniel Vial UT Austin UTUC arialoo rrial@utexas.co edu
Sujay Sanghavi UT Austin & Amazon
sanghavi ieaaiimaalaa...a.eeee .utexat.eee..m
Sanjay Shakkottai UT Austin sanjay. www.sshikottaaauteaasscco
R. Srikant UICC rsrikant@illinois edu
Abstract
Cascading bandits is natural and popular model that frames the task of learning to rank from Bernoulli click feedback bandit setting. For the case of unstructured rewards. prove matching upper and lower bounds for the wobbee--independee (i.e., gap-free) regret, both of which strictly improve the best known. A key observation is that the hard instances of this problem are those with small mean rewards, i.e., the small click throuhh rates that are most relevant in practice, Based on this, and the fact that small mean implies small variance for Bernoullis, our key technical result shows that variance-aware confidence sets derived from the Bernstein and Chernoff bounds lead to optimal algorithms (up to log terms), whereas Hoeffding-
algorithms suffer order-wise suboptimal regret. This sharply contrasts with the standard casccaacad bandit setting, where the variance-aware algorithms only improve constants. In light of this and as an additional contribution, we propose variance-awar algorithm for the structured case of linear rewards and show its regret strictly improves the state-of-the-art.
Introduction
The cascading click model describes users interacting with ranked lists, such as search results or online advertisements [Craswell et al., 2008]. In this model, there is set of items [T. (1...., I.). The user given a list of items A (a.,..., ag) sequentially examines the list, and clicks on the first attractive item (if any). If click occurs, the user leaves without examining the subsequent items. It is assumed that the e-th item has an attraction probability w(e) (which we also call the mean reward), and that the random (Bernoulli) clicks are conditionally independent given A.
Cascading bandits, introduced concurrently by Kveton et al. [2015a] and Combes al. [2015], are sequential learning version of the model where the mean rewards (L are initially unknown. At each round [n]. the learner chooses an action, which in the basic click model, the user scans the list and clicks on the first attractive item (if any). Thus, if the Cy-th item is clicked, the learner knows that the user was not attracted to {a [a- but was attracted to a²c However, the learner receives no feedback on the items (a C=++ that the user did not examine before leaving. The objective for the learner is to choose the sequence {A, to maximize the expected number of clicks, or equivalently, minimize the regret defined in (1).
list of items A, = "aj.....aj. a, As
This work provides problem-independen (i.e., gap-free) regret bounds for cascading bandits that strictly improve the state-of-the-an minimax-optimg regret bounds (up to log terms). Our key insight is that, compared to the standard bandit problem, the reward variance plays outsized role in the gap-free analysis. In partieular, show that for cascading bandits, the worst-case problem instances are those with low mean rewards-
the case of unstructured rewards, our results provide the first
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Problem-in indeem--ndeeeddent upper bounds and minimax lower bounds for cascading bandits with L total items, K recommended items, horizon n. and feature dimension d. The tabular columns assume unstructured mean reward. The linear column assumes reward is linear in unit- features and does not suppress any L dependencies in the (-) notation. See Appendix A for other related work.
Tabular case
Linear case
Paper
Upper bound
Lower bound
Upper bound Ö(Vnde
Zong et al. [2016]
none ÖVVILK Ö(vLLK))
none
Wang and Chen [2017]
none*
none
Lattimore et al. [2018]
none
none
Li and Zhang [2018]
none
none
(VvndK K)d
Zhong et al. [2021]
Ö(VLLK)
My MynL/KK)
Ö(V Ö(Vnd3 nd' K minfd, log L})
Kveton et al. [2022]
O(VnLK) Ö(VLL) (Thm 2) ((VnL)t (Thm 1) Ö(ynd(d + K))$ (Thm 4)
none
none
Ours
"These papers contain minimax lower bounds but for click models that are distinct from cascading bandits. 'hhee bounds assume L large compared to K and n large compared to L and K.
This bound holds for Bayesian notion of regret and includes dependence on the prior not shown above. These bounds assume n is large compared to and K to suppress some additive o(vn) terms.
namely, (ie) S 1/K, where the variance w(e) w(e)) is also small. We emphasize that these worst-case instances are not pathological; rather, they model the low click-through rates that prevail in practice [Richardson et al., 2007]. Further, we argue that adapting to low variance is crucial to cope with the worst-case instances. Put differently, algorithms should be variance-aware, i.e., more exploitative when the variance is small. We provide the intuition behind this key insight in Section 1.2 and show how to formalize it with proof sketch in Section 5.
More specifically, our first goal is to establish upper bounds the problem-independene regret (i.e., the maximum over te) for cascading bandit algorithms, as well as minimax lower bounds (i.e., the infimum over algorithms of their existing such bounds ÖVvLLK) and ? VnL/K), respectively. What is surprising is that, not only is there a gap between the bounds, but they increase and decrease in K, respectively. In other words, the following fundamental question is unresolved: as K grows, does the problem become harder (as suggested by the upper bound) or easier (as suggested by the lower bound)?
regret). As shown in Table 1, the tightest
As discussed by Zhong et al. [2021], this question lacks obvious answer. On the one hand, larger K means that the learner needs to identify more good items, which hints at a harder problem. On the other hand, the learner receives more feedback K grows, which intuitively makes the problem easier As we show later, variance-aware algorithms are the key to resolving this tradeoff.
In addition to this basic version of the model hereafter, the tabular case, where no structure is assumed for the mean rewards- we are also interested in the linear case, where w(e) = (ő(e), 0) for
some known feature map [L] + Rdd and unknown parameter vector E Rd. A second goal of this work is to apply our insights from the tabular case to the lincar one, in hopes of improving the best known upper bound Ö( D(Vnd2K /ndddK K) (see Table 1).
1.1 Main contributions
Tabular case. First, we show no algorithm can achieve ol o(vnL) regret uniformly across w assuming L large compared to K and is large compared L (see Theorem 1). Next, we consider three algorithms: CascadeXL-
CascadeUCB. V,, and CascadeUCB1 (the first and third are due to new). All three rank the L items using upper confidence
Kveton et al. [2015a]: CascadeUCB-Y bounds (UCBs) and choose A, as the K highest ranked items. They differ in the choice of UCB. As the names suggest, CascadeKL- and CascadeUCB-V use KL-UCB [Garivier and Cappé, 2011, Maillard et al., 2011 1, Cappé et al., 2013] and UCB-V [Audibert et al., 2009], respectively. Both are variance-aware,
the sense that their respective UCBs are derived from the Chernoff and Bernstein inequalities. We show that both algorithms have near-optimal regret Ö VVL) for any t (see Theorem 2). In contrast, CascadeUCB1 relies on the Hoeffing-style UCB1 [Auer et al., 2002], and we show that it suffers suboptimal regret Q( nLK) on some w (see Theorem 3).

---

In summary, we prove (i) the minimax regret is O (V)L)) for cascading bandits, (ii) the variance-awar algorithms CascadeKL-UCB and CascadeUCB-V are minimax minimax-optimal up log terms, and (iii) the variance-unaware algorithm CascadeUCB1 is decidely suboptimal. Moreover, note from Table 1 that we strictly improve both the upper and lower bounds for this problem.
Discussion. There are two surprising aspects to these results. First, the minimax bound é nL)LL) shows that (in a worst-case sense) the number of recommended items K plays no role.' i In other words, the aforementioned tradeoff (identifying more good items but receiving more feedback) is perfectly balanced when the correct algorithm (e.g., CascadeRL-UCB) is employed.
The second (and arguably more surprising aspect is that CacadeKL-UCB and CascadeUCB-Y are optimal but CascadeUCB1 is not. This stands in contrast to the standard L-armed bandit problem, where the analogous algorithms KL-UCB, UCB-V, and UCB1 all achieve the minimax regret @(vL)), and the main advantage of the former two is only to improve the constants in the gap-dependent bounds. We discuss the intuition behind this contrast in Section 1.2.
Linear case. Motivated by these findings, we also propose a variance-aware algorithm for the linear case called CascadeWOFUL.. CascadeWOFUL proceeds in two steps. First, we use the Hoeffding- style UCBs of Abbasi- Yadkori et al. [201 1] to upper bound the mean rewards T(e), and thus the Bernoulli variances (1e) - =(e)), with high probability. Second, we use these Hoeffding UCBs as proxies for the true variances in the WOFUL algorithm of Zhou et al. [2021]. which computes variance-weighted estimate of 0 that enjoys Bernstein-style concentration. In Theorem 4, we show the regret of CascadeWOFUL is Ō( O(vnd) /nd(d + K)) for large n, which improves existing bounds by a factor of at least /min d, K} (see Table 1).
1.2 Why do variance-aware algorithms succeed but variance-unawar algorithms fail?
To answer this question, focus on the tabular case and contrast the standard L-armed bandit setting with the cascading one. We first recall how the Ö(VnL) bound for L-armed bandits is derived. For simplicity, we restrict to instances with ((1 = and m(2) =
w(L) = p A for some p E (0, 1) and A E (0. p). In this case, UCB1 plays each of the L - suboptimal items 1/ times, up to constants and log factors [Auer et al., 2002]. Each such play costs regret A, for a total regret that scales as T./. A. Alternttivly,, regret can simply be bounded by An, since the n plays incur most A regret each. Combining the bounds gives min [,,A, A, An). The worst case occurs when the two bounds are equal, i.e., when A = /L/n, which implies vnL regret.
In contrast, UCB-V plays each suboptimal item 0² / times (in an order sense), where o² S is the variance of the Bernouli(p - A) reward [Audibert et al., 2009]. Therefore, the argument of the previous paragraph shows that regret grows as min(Lp/A An). Here the worst case occurs when is non-vanishing and A = / L/ni, which gives the same regret scaling as UCB1, A similar argument holds for KL-UCB, because the number of plays grows as 1/d(p- P) [Cappé et al., 2013] and one can show d(p A. p) = ?(A² /p) (see Claim in Appendix G).
The analysis is more complicated for cascading bandits, because regret is nonlinear in the mean rewards and the amount of feedback is random. To oversimplify things, we draw an analogy with w K) p and w(K 1) case, CascadeUCBI similarly plays the L K suboptimal items 1/4 times each, which costs L/A A regret when L >>>>> K. However, can no longer bound regret by An, because the total number of plays depends on the random number of items the user examines at each round, which is roughly min K} (the mean of Geometric(p) random variable, truncated the maximum K). Thus, the An bound inflates to An min(1/p, K}. which gives min minnL/AA, A, An min K}} regret. For p S 1/K and A /L. (nK), J. this yields the best known bound vnLK. We emphasize that, unlike the previous paragraph, the worst case here occurs when p (i.e., the click-through rate) is small.
the above and assume w11
(L)) = p A. In this
On the other hand, the analogous bound for CascadeUCB-V and CascadeKL-UCB scales as min A, An min(1/p. /p, KJJ. Crucially, the factor of p in the first term which arises due the variance-aware nature of the algorithms - offsets the factor /ppin in the second term. Thus, in the hard
'The Ô()) notation hides log K terms, but they can be bounded by log while retaining Ó(Vnl.) regret.
WOFFUL stands for weighted optimism in the face of uncertainty for linear bandits.
3

---

case S 1/K, the bound becomes min(L/(AK), AnK]. Here the worst case is A (L/(n which yields the minimax regret VnI. that we establish in Theorems and 2.
Preliminaries
In this section, precisely formulate problem. A cascading bandit instance is defined by the triple (L, K, w), where L E N is the total number of items, K E [L] = {1...., L} the number of items the learner displays to the user at each round, and
[0, 1] is the vector of attraction probabilities. We define a sequential game as follows, At each round / E [n]] the learner chooses an action A, (af,... .......aa))..
kj): ). where a [Z] and a * af. when k + k' (i.e., A, an ordered list of K distinct items). The user sequentially examines this list, clicks on the first item that attracts them, and stops examining items after clicking. Mathematically, we denote the first attractive item by C, Ik E [K] w, 1}. where we(e) ~ Bernoulli (e)) for each e [4]. If no item is for all we set C. oc. Note the learner only observes the realizations [min (C,, K...
clicked, i.e., if (
corresponding to the items that the user examined, i.e., (af )
We denote by H, = - (A.) U (w. k E [min (C., K}}} the history of actions and observations before time t. We let P.()) P(-174 U (A,)) and E.[]] = E HH U [At]] denote conditional probability and expectation given the history and current action. In the cascading bandit model, is assumed that the feedback (wr (w(aa))) ) (i.e., the presence or absence of clicks) is
conditionally independent given H. and A.. Therefore, the conditional click probability is
K
Pc < 10 - (w, -0)
= 1-0==--Pppp
= =
II m(a))).
Mappings from He to A, are called policies. Let II be the set of all policies. Given an instance E [0, 1)-, policy II, and horizon n. E N, the expected number of clicks is
K (1- (1-
Es,00 Σ (C, < x0) = Exr,an EP.(C, < <00)
= E Σ
(1-w(a)))
k=1
where is the indicator function. Let A (ai....,a8 oxk be any action A (aI,.... ak) that maximizes the click probability 1- -I (1 w(ax)). Our goal is to minimize regret, which the
expected difference in the number of clicks between and the policy that always plays A", i.e.
K a w(ai)
aI--Ila-00 (((0(())) o
K
(r,
17,
A=1
3
Results for the tabular case
We can now state our tabular results (the proof's are discussed in Section 5). First, we have minimax lower bound showing algorithm can achieve of / VnL) uniformly over the mean rewards w.
Theorem Suppose N A L/K E (4, (........) and n 2 L. Then for any policy n E II, there exists mean reward vector i E [0, 112h such that (n) = ((vnL).
The proof of Theorem I essentially reduction to Lattimore et al. [2018]'s lower bound for the so-called document-based click model. Their proof and ours both use the assumption L/K to simplify the analysis, which involves partitioning the L items into K subsets of size L/K each. When L/K & N, one of the subsets will have fewer items, which makes the analysis more cumbersome; however, this does not fundamentally alter either result.
Remark 1.
Remark The theorem also requires L Z 4K, which is not very restrictive since L > K in typical applications. However, this ussumption does eliminate an interesting analytical regime, namely, when K - T.. We conjecture the minimax lower bound is Z2 l2( (n([ K)) in this case, since any algorithm obtains zero regret when K L and there are no suboptimal items.
Our notation mostly follows Kveton et al. [2015a], but we clarify that their definition of He includes Ar.

---

We next consider the algorithms CascadeKL-UCB and CascadeUCB1 from Kveton et al. [2015a]. along with a new one called CascadeUCB-VV All follow a similar template, which is given in Algorithm 1. This is a natural generalization of upper confidence bound (UCB) algorithms from the standard T-armed bandit setting. At each round [n], it computes UCBs (z(e) in a manner to be specified shortly, then chooses A, as the K items with the highest UCBs (in order of UCB). After observing the click feedback Ct, the algorithm increments the number observations Ty(e) and updates the empirical mean (e) for each item that the user examined.
Algorithm 1: General UCB algorithm for tabular cascading bandits
Initialize number of observations (e) 0 and empirical mean wo(e) 0 for each E [Z]
for |= 1....... , do
Compute Uz(e) for each [T] (by (2), (3), and (4) for CascadeKL.UUBB, CascadeUCB-V, and CascadeUCB1, respectively)
for k = 1, K do
Let a = arg max
Uz(e) be the item with the k-th highest UCB
Play A₁ (aj. ..... a and observe C, inf [K] we(af)) = 1} (where inf 0 20)
Let (e) = T (e) for each e [4]
for k ..... min C, K} do
e + a (e) - (e(e) +1, (T, + (T (Tr-1 (ol I(C, (T))
For CascadeKL-UCB, the UCBs (e)e) are computed as follows:
U,(e) = max(u E [0, 1] WT, ((. u) = log([(0))T.-1(ee))
(2)
where [()) (log 8) and d(p, q) p plog(p//) 11 log
is the relative entropy between Bernoullis with means p. q E [0. 1]. The set in (2) a confidence interval for w(e), which is derived from the Chernoff bound. For CascadeUCB-VV the UCBs are instead given by
(.(c) = WT WT. +
+ 6log(t) (og)))/T)G (T)(())()(())
(3)
where v, (e) w. (e) (e)) is the empirical variance from observations of item This UCB derived from the coarser but crucially, still variance-aware Bernstein inequality. Finally, for CascadeUCB1, the UCBs are derived from the Hoeffing bound and computed as follows:
U+(e) = W (T) + CrTT.-(e)): where Ct,s = / 1.5 log(1)/s.
We now show the variance- UCBs are nearly optimal, while CascadeUCB1 is suboptimal. Theorem 2. Suppose is CascadeXL-UCB CascadeUCB- V, i.e., the policy from Algorithm with the UCBs given by (2) or (3). Then (n) Ö(vnL) for any w E 10,
Remark 3.
The reader may wonder why proposed CascadeUCB- since the CascadeKL-UCB minimax regret. The main reason
demonstrate that variance- awareness alone (no additional information encoded by KL-UCB) is enough to achieve the optimal regret, which helps motivate our linear algorithm. Furthermore, we show empirically in Section that, while CascadeUCB is inferior to CascadeKL -UCC in terms of regret, its closed form nature leads to quicker computation, while still improving the regret of CascadeUCB1.
bound enough to establish
800K, and CascadeUCB1, i.e., the policy from Algorithm/ I with the UCBs given by (4). Then R,,a(()) ((VnLK)) for some T E [0, 1)..
Theorem 3. Suppose n. 2 max [LK, 49K*),
Remark 4. The assumed bounds on and simplify the calculations and can improved (see Remark 9 in Appendix J). The main point of Theorem 3 is to show that, unlike the variance-aware algorithms, CascadeUCBi cannot satisfy the conclusion of Theorem 2 for choices of a and L.
4 Results for the linear case
In light of the previous section, we seek a variance-aware algorithm for the linear case. Our method is based on the WOFUL algorithm of Zhou et al. [2021], which was designed for the standard linear
5

---

bandit setting (the case K = 1). In this section, we review WOFUL, discuss how to overcome its limitations in the cascading setting, explain our CascadeWOFUL algorithm, and bound its regret.
Existing algorithm. In Section 4.3 of their work, Zhou et al. [2021] consider the following problem.
As above, there is set of items [T.] a known feature map & [T]] - Rd, and unknown parameter vector 0 E IR Successive plays of E [L] give i.i.d. rewards with mean w(e) (Ø(e), 0) and variance upper bounded by o². Thus, at each round E [r]. the learner chooses a' E [L] and receives
random reward Ft- (ó(a'). )) + '7,, where E[n |a"] 0 and B[y S oa. For this setting, the authors proposed the WDFUL algorithm, which is based on the (unweighted) OFUL algorithm [Abbasi-Yadkorí Yadkori et al., 2011] I]. At each round E [m)] WOFUL chooses the item
a' arg max ((((c). 0.) + +all()))la7))
(5)
cE[L]
where a > O is an exploration parameter, ||>||| = Vx Bæ the norm induced by a positive definite matrix B, and 0g is the regularized and weightd least-squares estimate given by
- Σ
where
A. I+ Σ o(aa oaa'
(6)
To gain some intuition, we assume momentarily that d= and Φ(e) is the e-th standard basis vector, ie., the vector with 1 in the e-th coordinate and 0 elsewhere. In this case, can easily calculate
Exett- [=s]tt-)ja==e Ts/o? 1 Te-1()
(o(c), 0.)
V T1+TI-I(0P) (c)
Therefore, for large Te) (large enough that 1 Te))o/) R (c-1(c)/or
we have
Esclt-1]aa' Te-1(e)
o² Te-
(é(e), 0.) + alll(e))la,
Similar to UCB-V (3), the right side of this equation is the empirical mean plus an exploration bonus that grows with the variance upper bound of and decays in Tc). Hence, the term inside the Bernstein-style UCB. The analysis of this UCB relies
arg max in (5) can be interpreted novel concentration inequality for vector-valued martingales [Zhou et al., 2021, Theorem 2], which a Bernstein analogue of the Hoeffding-stp bound due to Yadkori et al. [2011].
Limitations. The fact that WOFUL (roughly) generalizes UCB-V promising. However, computing (6) requires knowledge of the variance upper bounds o². and nontrivial bounds on the variance are rarely available in practice. We sidestep this issue with three simple observations: (i) cascading bandits only involve Bernoulli rewards, (ii) for Bernoulli rewards, variances are upper bounded by means, and (iii) these means can be learned efficiently since they are linearly- parrrly-paaametiieed... This suggests the following algorithm: first, compute Hoeffding-stye UCBs; second, treat these UCBs as upper bounds for the true means, and thus the true variances, WOFUL.
Proposed algorithm. Algorithm 2 formalizes this approach. It contains three steps. First, step 1 defines Hoeffding-style UCBs U. in Abbasi- Yadkori et al. [2011]. Next, step 2 uses U2, an upper bound for the variance and computes the Bemstein-stylee UCBs U,,B as in WOFUL. Finally, step 3 chooses A, as the K items with the highest U, analogous to Algorithm 1.
Two technical clarifications are order. First, observe that in step I, we clip the variance bound U below by 1/K. We do to ensure that At,B (which inverts U..H) remains bounded. Additionally, we note the choice 1/K is precisely motivated by Section 1.2, which shows this is a critical threshold for the small thick-through rate. Second, A,, uses the regularizer KI. This is to ensure that the regularizer is large enough compared to the summands ((at) T/ (...,,(())) (a.)) which scale K in the worst case where the variance upper bound U,.H(af) is clipped to 1/K.
Remark 5. Zong et al. [2016] proposed WOFUL-style cascading algorithm called Cascadel inUCB (see Appendix C), but they set the variance upper bound to fixed 0² > 0. fact, they remark "ideally, o² should be the variance of the observation noises." which CascadeWOFUL essentially learns.
Remark 6. Appendix contains an improved version of CascadeWOFUL. is more efficient (for example, the inverses are Uteratively updated via Cherman--orrrsson guarantee as Algorithm 2, and includes some tweaks that improve performance in practice. The tradeoff is that Algorithm 2 is simpler to explain, which is why we prefer it for the main text.
satisfies the same theoretical

---

Algorithm 2: CascadeWOFUL for linear cascading bandits
Input:
exploration parameters {or,H [Ot,H for f = 1....,M do
Step 1: Define the (clipped) Hoeffding-style UCBs
(. max
{ (0()), 0,, +(,ul)(())) 1/K where
(-1 mi,in(C,.k) K}
(aa)), A, = =1+ [-1 min(C,,K)
01,11
Σ Σ
Σ
o(a))o(a))
Step 2: Define the Bernstein-style UCBs
UL (o(-), 0r.B) tr. where
1-1 min(C,, w.(())
t-1 min(C., K)
((ag)
01,B A, Σ
(a,) ALB A KT
Σ Σ
U. (a
Step 3: Let a arg max (aa) A-1 (e) be the item with the k-th highest UCB,
play A, = (af, ) observe C, inf E [K] wr(af)) = 1} (as in Algorithm 1)
Regret bound. We now state our main result for the linear case. Here Ba(M) {x E R2d | I M) denotes the Euclidean ball of radius M >> 0 in R
Theorem 4. Suppose w E (0,1]4 &: [7]] + Ba(1), and 0 E Ba((1) satisfy vi(e) = (o(e), 0) for all E [L]. Let π be the policy of Algorithm 2 with inputs at v /loo((1 +tK/d) + log(n) +
and 0t,B /llgg tK/d) log(ne K) 4vK log(n K) + VK. Then
a (n) = Ô (min| V Vnd(d++ + K) + n a (d+ + K)} K v max K} min min(d,KKu KJ1/8))
Note this bound is completely independent of the number of items L. For large (typically the case of interest), it becomes (( + K)), which improves the best known bound of Ó K) [Li and Zhang, 2018]. The theorem also establishes Ö(vn max(d, K) min(d, KJ KJ1/5) regret uniformly in (i.e., without additive o( o()i) terms which may dominate for small n)), which improves the best known uniform-n bound of ((vnd)) [Zong et al., 2016]. See Table for more details.
5 Overview of the analysis
We next discuss the key ideas behind our proofs. The details are deferred to Appendices E-J.
Theorem 2 proof. For simplicity, assume the arms are ordered by their means, i.c., ((1 > w(L). Under this assumption, the optimal action is [K]. We call those items optimal and [L] [K] suboptimal. We let & be the "bad event" that the empirical and true means differ substantially at time t. & its complement, Ge,e". the event that suboptimal e > K was chosen in favor of optimal
e* K and subsequently examined by the user, and Ae,e- w(e") w(e) the reward gap. Then as in Appendix A. of Kveton et al. [2015a], we "linearize" " regret as follows:
Rx, ne (n) S
ΣΣ Σ
Dep 1(E,, Geet
+ ΣΣ P(E))
KEne>Ke'sh
SSn
The second term is small due to concentration. For the first term, define A w(K) (K) L/n and
assume n > L (so A & w( (K)) For each e > K, let (c(e) fe" S K A I A} be the
"Our results hold with minor modification if Φ [4] - (a( and E Ma(Ma) for general M1, M2 However, as prior work, the modified algorithm needs to know an upper bound on M2. 'The full proof addresses the cases L and w(K) (here implicitly assume the latter to invert A).
7

---

optimal items with small gap relative to e and Ka(e) = [K] \ (C((e) the other optimal items. Then
Σ A I(E,, D Go,et
I(G +
Σ
"SK
(C)
e"ERa(e)
Therefore, we can upper bound the first term in (7) by
A ΣΣ E SEED Σ I(Grot .)
+B
EE E ISne>k ctERa(e)
D 1 Gest
(8)
ISn
<>>e'EKale
For the first term in (8), the inner double summation the number of favor of e* E KC (e), and subsequently examined by the user, at round t. Denote this number by O Recall w(e*) 2 xi (K) (by the assumed ordering) and A < (K),, , so for e" E (e)e),, we have
that were chosen in
v(e) = T - -r.et 2 x(e")
2 W K) - A 전 T(K).
Hence, O, is bounded by the number of items with (ee) z () that the user examined. Since the user stops examining at the first attractive item, this number is dominated by a (cometric((((K))
random variable. Therefore, the first term in (8) is Ó (An/((K)) - ((vL)).
The second term in (8) accounts for choosing instead of e* when Ae. > A and the empirical means are concentrated. Building upon the intuition of Section 1.2, we exploit the variance-awareness of KL-UCB and UCB-V V (and use w(e) w(K) by the assumed ordering) to bound this term by ((Lx(c)( (at0((11((e)))))))))) AA) S ((Lū(K) /))A). Thus, by choice of A, this term is Ö(VnI,
well.
Theorem 4 proof. We decompose regret similar to (7) and (8), though with different choices of &, and A. To bound PPE,), we use the aforementioned result of Abbasi-Yadkon et al. [201]] 1] to show that the Hoeffding UCBs Ut. upper bound the variances with high probability, then prove
guarantee for the least-squares estimate Oz,8 using the Bernstein-style bound from Zhou et al. [2021]. We bound the first term (8) using the exact same logic as the tabular case. The second term has a more complicated analysis, but (as in the tabular case) it amounts to bounding the number of times that items far from optimal are chosen when 0,, is well-concentrated. For this, we adapt techniques from the standard linear bandit setting (the case =
1) to general K E [L].
Theorem proof. We let Hi = (A,, w. (a))),,... ...., W. (ak)] be the entire history before time I, which includes unobserved rewards w. (a > C.. We also let II' be the policies that map Hi
to A, Note He C Hy, so IT C TT' For any x E IT' and v E [0, 1)4, we define
n K
R², = Es
ΣΣ
- - ((a(a))
where of arg max (( (e). Then lower bound linearization analogous (7) shows that for any p [0, 1] and E 10, [. (n) 2 (1 p) K' (n), which implies
inf sup R (n) 2 inf sup Tell 1)0
R 2 (1 p) 1k inf sup R² (n). (10)
zell' we(0.,]
Hell' me(o.)]
If we choose p 1, the inf sup at right the minimax regret for the document-based model that was analyzed by Lattimore et al. [2018] (see Remark 1), but this makes (10) vacuous. On the other hand, by choosing p = O(1/K) (again, the small click-through rate Section 1.2), so that the term (I (k- in (10) is ((1), we can modify their analysis to prove Theorem 1.
Theorem proof. We linearize the regret similar the proof of Theorem then define a problem instance reminiscent of Section 1.2 and (roughly) follow the intuition for UCB1 therein.
6 Experiments
Before closing, we conduct experiments on both synthetic and real data. Some details regarding experimental setup are deferred to Appendix C. Code is available in the supplementary material.
'In fact, the proofs of Theorems 2 and 4 both rely on more general gap- free regret decomposition for cascading bandits (Lemmal I in Appendix F), which our knowledge is novel and may be of independent interest.
8

---

CascadeUCB1
CascadeUCB-V
CascadeKL-UCB
1.2 1e4
10
10*
0 10
1.2
1e4
K= 10
0.9
Runtime
0.9
Re9n
0.6
0.6
0.3
10a
0.3
0.0
10
0.0
6
8
10
12
14
16
6
10 K
12 14 16
0.0
0.2
0.4
0.6
0.8 1.0
1e5
CascadeLinUCB
CascadeWOFUL
1.8
1e3 (n. d = 10)
1e3 (n, K) = (10', 10)
1.2 1e3
d-k K-KK-10 10
Regret
1.2
Regret
1.2
0.9
0.66
0.6
0.6
0.3
0.0
0.0
0.0
8
12
16
10
14 16
0.2 0.6 0.8
d
le5
Figure 1: Results for synthetic data (tabular on top, linear on bottom, 7. = 100 in both)
CascadeLinUCB
CascadeWOFUL
CascadeLinUCB
CascadeWOFUL
2.4
1e4
(d = (20.4)
3.6
1e4
per genre, (1. 4)
1.8
2.7
Regres
1.22
0.6
0.9
0.0
0.0
0.2
0.8 1.0
Action Adverturee tion
0.0
Children's dind's'ss
Comedy
Documen tary
Crime
Drama anntasy Film- Noir
Musical Romang thrille Western
War
1e6
Figure 2: Results for MovieLens data [Harper and Konstan, 2015]
Synthetic data. We let L 100 and K E (2i) For each K, sample w(e) uniformly in L3K } for S K and in [0, 3k for > K. Note this yields positive gap with the small click-through rate of Section 1.2. The top left plot in Figure 1 shows the regret at 10 for the tabular albums of Section 3 (the shaded regions are the standard deviations across five trials). As predicted by Theorems 2 and 3, the CascadeUCB1 curve grows with K, while the variance-aware curves do not. The top middle plot shows the time spent computing UCBs for the same experiment, which confirms the behavior mentioned in Remark 3. For the linear case, we vary d (2i)=_2- generate the same w, then compute unit-norm vectors and Φfe) satisfying w(e) = (d(e), 0) (see Appendix C). We compare CascadeWOFUL to CascadeLinUCB [Zong al., 2016], which Li and Zhang [2018] showed has the best existing regret guarantee. As suggested by Theorem 4, the left and middle plots on the bottom of Figure show that our algorithm's 's regret has superior dependence on K and d. The rightmost plots show that regret is sublinear in n for the median values K = d = 10.
Real data. We replicate the first experiment from Zong al. [2016] on the MovieLens- 1M dataset (grouplens. org/ htgg/aaasets//m wwtps//ovveeee////eeeeeeeeeeesee /mm/, which contains user ratings for R 4000 movies. Next, we divide
In brief, the setup is as follows. First, use their default choices d 20 and K the ratings into train and test sets based on the user who provided the rating. From the training data and rank-d SVD approximation, we learn feature mapping é from movies to the probability that uniformly random training user rated the movie more than three stars. Finally, we run the algorithms as above, except at round t [n]. we sample a uniformly random user J; from the test set and define (r(a = W (Jr, ), where W (j. a) = 1 [user] rated movie a more than 3 stars). In other words, instead of the independent Bernoulli clicks of Section 2, we observe the actual feedback of user J We point the reader to Section 4 of Zong et al. [2016] and Appendix C for further details. The left plot of Figure 2 shows that CascadeWOFUL outperforms CascadeLinUCB across n, eventually incurring less than 66% of the regret. In addition to this setup from Zong et al. [2016], we reran the experiment while restricting the set of items to movies of a particular genre, for each of 18 genres the dataset. This is intended to model platforms like Netflix that recommend movies in various categories. The right plot shows that CascadeWOFUL is superior for all genres; for some genres (e.g., fantasy) its regret is about half of CascadeLinUCB's Moreover, experiments indicate that CascadeWOFUL

---

improves CascadeLinUCE more dramatically for genres with smaller tick-through rates (see Figure and surrounding discussion in Appendix C), which reinforces key message of this paper.
7 Conclusion
In this work, we proved matching upper and lower bounds for the problem-independent regret of tabular cascading bandits and an upper bound for the linear case, all of which improve the best known. Our results suggest some interesting future directions, such proving minimax lower bounds for the linear case and revisiting Thompson sampling for cascading bandits [Zhong et al., 2021] in light of insight; Appendix D for details. Finally, note the paper is theoretical and has no immediate societal impact. Nevertheless, we urge caution for the negative impacts that could arise in practice. For example, our MovieLens experiments involved training on a subset of users, which could cause poor recommendations for demographics underrepresented in the training set.
variance-
Acknowledgments and Disclosure of Funding
This work partially supported by ONR Grant N00014-19-1-2566 NSF TRIPODS Grant 1934932, NSF Grants CCF 22-07547, CCF 19-34986, CNS 21-06801, 2019844, 21 2112471, 2107037, the Machine Learning Lab (MLL) at UT Austin, and the Wireless Networking and Communications Group (WNCG) Industrial Affiliates Program. We thank Advait Parulekar for helpful discussions.
References
Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Jean- Audibert, Rémi Munos, and Csaba Szepesvári. Exploration-explootatio tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):186--100, 2009.
Peter Auer, Nicolo Cesa Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235 256, 2002.
Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Machine Learning, 5(1):1-122, 2012.
Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback-leible upper confidence bounds for optimal sequential allocation. The Annals of Statistics, pages 1516-1541, 2013.
Wang Chi Cheung, Vincent Tan, and Zixin Zhong. A thompson sampling algorithm for cascading bandits. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 438-447. PMLR, 2019,
Aleksandr Chuklin, lya Markov, and Maarten de Rijke. Click Models for Web Search. Morgan & Claypool Publishers, 2015.
Richard Combes, Stefan Magureanu, Alexandre Proutiere, and Cyrille Laroche. Learning to rank: Regret lower bounds and efficient algorithms. In Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 231-244, 2015.
Nick Craswell, Onno Zoeter, Michael Taylor, and Bill Ramsey. An experimental comparison of click position-bias models. In Proceedings of the 2008 international conference on web search and data mining, pages 87-94, 2008
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. Conference on Learning Theory, pages 2137-2143, 2008
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
10

---

Aurélien Garivier and Olivier Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376. JMLR Workshop and Conference Proceedings, 2011.
Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. Acm Iransactions on interactive intelligent systems (lis), 5(4):1-19, 2015.
Gaurush Hiranandani, Harvineet Singh, Prakhar Gupta, Iftikhar Ahamath Burhanuddin, Zheng Wen, and Branislav Kveton. Cascading linear submodular bandits: Accounting for position bias and diversity in online learning to rank. In Uncertainty in Artificial Intelligence, pages 722-732. PMLR, 2020.
Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning to rank in the cascade model. In International Conference Machine Learning, pages 767-776. PMLR, 2015a.
Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Combinatorial cascading bandits. Advances in Neural Information Processing Systems, 28, 2015b.
Branislav Kveton, Ofer Meshi, Zhen Qin, and Masrour Zoghi. On the value of prior in online learning to rank. In The 25th International Conference on Artificial Intelligence and Statistics, 2022.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Tor Lattimore, Branislav Kveton, Shuai Li, and Csaba Szepesvari. Toprank: A practical algorithm for online stochastic ranking. Advances in Neural Information Processing Systems, 31, 2018
Chang Li and Maarten De Rijke. Cascading non-stationary bandits: online learning to rank in the non-stationary cascade model. Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 2859-2865, 2019.
Shuai Li and Shengyu Zhang. Online clustering of contextual cascading bandits. In Proceedings of the AAAI Conference Artificial Intelligence, 2018.
Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading
bandits. In International conference machine learning, pages 1245-1253, PMLR, 2016.
Shuai Li, Tor Lattimore, and Csaba Szepesvári. Online learning to rank with features. In International Conference Machine Learning, pages 3856-3865. PMLR, 2019.
Xutong Liu, Jinhang Zuo, Siwei Wang, Carlee Joe- nee-Wng, John Lui, and Wei Chen. Batch-size independent regret bounds for combinatorial independent arms. arXiv preprint arXiv: 14837, 2022.
with probabilistically triggered arms
Odalric-Ambryn Maillard, Rémi Munos, and Gilles Stoltz. A finite-time analysis of multi-armed bandits problems with kullback-leibler divergences. In Proceedings of the 24th annual Conference On Learning Theory, pages 497-514. JMLR Workshop and Conference Proceedings, 1.
Matthew Richardson, Ewa Dominowska, and Robert Ragno. Predicting clicks: estimating the click- through rate for new ads. In Proceedings of the 16th international conference World Wide Web. pages 521 2007.
Lingda Wang, Huozhi Zhou, Bingcong Li, Lav R Varshney, and Zhizhen Zhao. Near-optimal algorithms for piecewise-stational cascading bandits. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3365-3369, IEEE, 2021.
Qinshi Wang and Wei Chen. Improving regret bounds for combinatorial semi- bandits with probabilis- tically triggered arms and applications. Advances in Neural Information Processing Systems, 30, 2017.
Zixin Zhong, Wang Chi Chueng, and Vincent YF Tan. Thompson sampling algorithms for cascading bandits. Journal of Machine Learning Research, 22:1-66, 2021.

---

Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory. pages 4532 4576. PMLR, 2021.
Masrour Zoghi, Tomas Tunys, Mohammad Ghavamzadeh, Branislav Kveton, Csaba Szepesvari, and Zheng Wen. Online learning to rank in stochastic click models. In International Conference on Machine Learning, pages 4199-4208. PMLR, 2017.
Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton. Cascading bandits for large-scale recommendation problems. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, pages 835-844, 2016.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The claims are accurate. Furthermore, provide references to the formal results alongside each claim stated in the introduction.
(b) Did you describe the limitations of your work? [Yes] The main limitation is that our lower bounds (Theorems and 3) require some additional assumptions. These are stated clearly in the theorem statements and discussed in Remarks I and 4.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Section 7 addresses societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] As mentioned above, the assumptions are clearly stated in the theorem statements.
(b) Did you include complete proofs of all theoretical results? [Yes] Section 1.2 discusses the high-level intuition behind our proofs, Section contains a more detailed proof sketch, and the appendices include complete proofs.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] Complete code to recreate all plots is available in the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The experimental setup is discussed detail Appendix C, and other training details can be found in the code.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] All plots include error bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]] The experiments were run over several hours on laptop, so no significant resources were used. Nevertheless, Appendix C mentions the approximate runtime needed to recreate the figures.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We only used the MovieLens dataset, which we cited and also provided a link to.
(b) Did you mention the license of the assets? [Yes] The link to the MovieLens dataset contains README with license information.
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
12

---

5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "sM4MPI5aFh", "reviewer": "Reviewer_HkuS", "summary": "The cascading-bandits problem considers a scenario where the agent aims to choose K out of L items, and each item corresponds to an independent Bernoulli random variable. In each iteration, the agent chooses an ordered list of K items, and the underlying variable is revealed in the same order until a 1 is observed. So the overall reward and regret for each action can be written in terms of the product of the probabilities of getting 0 for the K chosen actions. \n\nIn prior works, the best known upper bound for the optimal regret given n iterations is increasing in K. The best known lower bound is decreasing in K, leaving an otherwise gap. This work completely resolves this problem for $K\\leq L/4$.  ", "questions": "Theorem 1 is stated only for the discrete case of L/K being an integer. As far as I understand, this should imply the same lower bound for any $L/K\\geq 4$ (within a constant factor), or even $L/K\\geq C$ for general $C>1$. Is there any reason that the integer constraint is imposed in the theorem statement?", "limitations": "--", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of this work is the complete resolution of cascading bandits, at least for $K\\leq L/4$. Besides the results, the techniques/algorithms proposed in this work are also interesting. Note that when the reward function is linear (i.e., being the sum of expected values for the K items), the minimax regret is known. Cascading bandits have a non-linear regret function, and I imagined the solution of cascading bandits would be something that handles the non-linearity through sophisticated analysis. The presented algorithm uses KL divergence, which is surprisingly clean. \n\nPerhaps one limitation of this work is that the lower bound only holds for $L/K\\geq C$ with a constant $C>1$, leaving the minimax regret for the $K\\rightarrow L$ regime open. The minimax regret in that regime is known to follow a different rule, and it would be of interest whether the proposed solution or techniques can provide optimal bounds in that regime as well.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TLSxcoim_aV", "reviewer": "Reviewer_hXD7", "summary": "This work studied the regret minimization in cascading bandits. It closed the gap for the upper and lower bounds on the regret in the tabular setting by developing a variance-aware UCB-based algorithm. It also studied the linear setting and evaluated the algorithms with numerical experiments. ", "questions": "1. What are the key analytical challenges? These should be described in greater detail in Section 5. The current analytical framework in Section 5 looks quite standard for most cascading bandit algorithms.\n2. Is it possible to also provide a lower bound in the linear setting? This may further complete the analysis in cascading bandits.\n3. As shown in previous works such as Zhong et al. [2021], Thompson sampling algorithms can also be applied in cascading bandits, why don't the authors compare them in numerical experiments?\n", "limitations": "I don't see any issue regarding societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This work is easy to follow and the claims are generally sound. It improved the existing upper and lower bounds and closed the gap in the tabular setting. It also discussed why involving variance in the design of the algorithm can help. The numerical experiments compared different UCB-type algorithms.\n\nWeaknesses: The key difference between the analysis in this work and previous work should be better elaborated, and more experiments are appreciated. See the \"Questions\" part for more details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Kw89jcJRGX", "reviewer": "Reviewer_GvNk", "summary": "This paper revisits the cascading bandits problem where the decision maker must choose an ordered list of $K$ distinct items (from a universe of $L \\geqslant K$ items) at each round $t\\in\\left\\lbrace 1,...,n \\right\\rbrace$ to display to users arriving sequentially. Each item in the universe has a latent attraction probability; users are homogeneous, scan the ordered list displayed to them in a fixed order (left-to-right), and click on the first item that attracts them (subsequent items are left unexamined). The decision maker only observes Bernoulli feedback (governed by the underlying attraction probabilities) for the items that were examined (including the one that was ultimately clicked upon). Note that a user may potentially scan through an entire list of $K$ items and click on none; this would be denoted by a $K$-dimensional vector of all $0$'s. The goal of the decision maker is to maximize the total number of clicks (in expectation) over $n$ rounds.\n\nFor the aforementioned problem, the authors study the regret minimization problem where the learner competes against an oracle that always plays an action (an ordered list of $K$ distinct items) that maximizes the click probability.\n\nThe paper proposes matching problem-independent (worst-case) upper and lower bounds (the former based on a UCB approach) for the tabular version of the problem described above. For the linear setting, the authors propose an upper bound (again, using a UCB-based approach) that improves upon the current best known.", "questions": "For the tabular case, the bounds match in $n$ and $L$ (up to log factors). Would it be possible to capture explicitly dependencies also w.r.t. $K$?", "limitations": "Appears to be well-addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written with a clear technical exposition. The observation that variance-aware algorithms lead to bounds that are order-wise better in this setting than their counterparts relying on fixed variance proxies is an interesting one in light of known results for the standard MAB setting.\n\nI did not evaluate the technical details very rigorously, but proof sketches and arguments appear correct. I reckon this paper makes sound theoretical contributions to this area and would therefore vote for an accept.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "C2EEQjC1Pcc", "reviewer": "Reviewer_mQJt", "summary": "This paper studies the cascading bandits in both tabular and linear cases. The paper's main contribution is to find out that the hardest problem instances (where means are small) also yield small variance, meaning that the estimation for these instances is naturally more accurate. Based on this observation, the authors use variance-aware algorithms to give improved regret bounds, reducing the $K$-related factors. Specifically, for the tabular case, the authors show that the previous Cascade-KL and Cascade-V algorithms can achieve the improved regret upper bound by a factor of $O(K)$, compared with previous works. The authors also show that the newly proposed bounds are optimal up to log terms, using their newly proposed lower bounds. For the linear case, the authors propose the CascadeWOFUL algorithm and use the mean to replace the unknown variance. The regret bound of CascadeWOFUL improves the existing results by a factor of $O(\\sqrt{K\\min(d,K)})$. Finally, the experiments show that the proposed algorithms achieve superior performance compared to baselines.", "questions": "Please justify the questions proposed in the weakness part.", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength.\n\n1. The current paper makes solid contributions to the cascading bandits and combinatorial multi-armed bandits literature. For the tabular case, both upper and lower bounds strictly improve the existing works. For the linear case, the derived upper bound also significantly improves the existing works.\n\n2. The presentation is very clear, and I enjoy the flow of showing their results. The intuition of the algorithm design and the proof is quite clear and easy to follow. Both the novelty and the challenge of the problem are properly illustrated.\n\n3. Beyond the theoretical analysis, the authors also give promising empirical results, which adds more practical value to their work.\n\nWeakness.\n1. I wonder what the gap-dependent regret bound is. I believe the distribution-dependent regret bound is harder to derive, since the gap-independent regret bound can be derived by optimizing the gap $\\Delta$ using the distribution-dependent bound. Can the gap-dependent bound be easily shown using the current paper’s analysis?\n\n2. In appendix A, the authors claim Li and Zhang [2018] requires additional assumptions. In fact, the additional assumptions (cluster regularity, user uniformness and item regularity) are to deal with the varying $\\theta$. If $\\theta$ are the same, they are not needed to give the result of Corollary 3. So I think the authors could double-check their claim.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept