Cascading Contextual Assortment Bandits
Authors: Hyunjun Choi
Rajan Udwani
Min-hwan Oh
Venue: NeurIPS 2023 poster (2023)
Keywords: cascade bandit
assortment bandit
upper confidence bound
exploration and exploitation
combinatorial optimization
TL;DR: We propose UCB-type algorithm for cascading contextual assortment bandits with the sharpest regret upper bound.

Abstract: We present a new combinatorial bandit model, the \textit{cascading contextual assortment bandit}. This model serves as a generalization of both existing cascading bandits and assortment bandits, broadening their applicability in practice. For this model, we propose our first UCB bandit algorithm, UCB-CCA. We prove that this algorithm achieves a $T$-step regret upper-bound of $\tilde{\mathcal{O}}(\frac{1}{\kappa}d\sqrt{T})$, sharper than existing bounds for cascading contextual bandits by eliminating dependence on cascade length $K$. To improve the dependence on problem-dependent constant $\kappa$, we introduce our second algorithm, UCB-CCA+, which leverages a new Bernstein-type concentration result. This algorithm achieves $\tilde{\mathcal{O}}(d\sqrt{T})$ without dependence on $\kappa$ in the leading term. We substantiate our theoretical claims with numerical experiments, demonstrating the practical efficacy of our proposed methods.

Cascading Contextual Assortment Bandits
Hyun-jun Choi Seoul National University Seoul, South Korea nschj 1@snu. ac kr
Rajan Udwani UC Berkeley Berkeley, CA, USA rudwani@berkeleg edu
Min-hwan Oh
Seoul National University Seoul, South Korea minoh@snu ac kr
Abstract
We present new combinatorial bandit model, the cascading contextual assortment bandir. This model serves as generalization of both existing cascading bandits and assortment bandits, broadening their applicability practice. For this model, we propose our first UCB bandit algorithm, UCB-CCA. We prove that this algorithm achieves T -tspp regret upper-bound of dv sharper than existing bounds for cascading contextual bandits by eliminating dependence on cascade length K. To improve the dependence second algorithm, WCB-CCA+, which leverages a new Bernstein-type concentra- tion result. This algorithm achieves ((d/T) without dependence on k the leading term. We substantiate our theoretical claims with numerical experiments, demonstrating the practical efficacy of our proposed methods.
problem-dependen constant we introduce our
Introduction
Sequential interactions between users and recommender agent are often modeled as the multi-armed bandit problem of its variants [15]. In practice, user typically encounters multiple items per round of interaction rather than solitary item. Two popular models that capture this aspect are the also often known multinomial
cascading bandit (13] [4 18
and the assortment bandit 4
22
logistic bandits.
In the cascading bandit problem 13
the agent selects cascade of K items from a total N items each round. These selected items are sequentially presented one at time to user. If the user clicks the next item from the cascade. This process continues until either the user clicks on an item or all K items in the cascade have been presented without click. Once round ends, next round commences with a newly selected list of K items.
presented item, the cascading round ends. If not, the agent proceeds reveal
In the assortment bandit problem items all once, then receives user choice feedback on the assortment. user may opt for one of the M items presented choose none at all, concluding the round in either case. Both cascading and assortment bandit problems are significant combinatorial variations of the multi-armed bandit problem and have been extensively examined both theoretically and in practice.
22 2
the agent presents assortment of M
However, more commonly encountered scheme weal-world applications is generalization of these two settings, where a cascade of assortments is sequentially revealed in each round. This approach is evident in video streaming services, where assortments of recommended contents are revealed as users scroll through webpages or mobile applications. Similar experiences can also be found in various online retail services and search engines. To address this, we propose new interactive model, which we term cascading assortment bandits. In the cascading assortment bandits, the agent chooses cascade of assortments that consists of assortments with each assortment containing M items. The agent reveals one assortment at time in the cascade. The cascade concludes the user clicks on one of the items contained in a given assortment. not, the agent proceeds
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

= 6,
= K=S.M=
Scanned & not clicked
Seanned & not clicked
K 1,
Single item
Current scan
Current scom
Single assoriment
Not scanned
Not scunned
Multi-Ameed Bandit
Cascading Bandit
Assormment Bandit
Cascading Assortment Bandit
Figure 1: Comparisons between the cascading assortment bandit and the other combinatorial bandits. The cascading assortment bandit subsumes the multi-armas bandit (K = 1, 1), the cascading bandit (K M, 1), and the assortment bandit (K" 1, > 1).
to unveil the subsequent assortment in the cascade. This eycle continues until either an assortment receives click from the user or the agent depletes the pre-selected assortments.
The cascading assortment bandit problem is the strict generalization of both the cascading bandits model and the assortment bandits model. It also a generalization of the simple multi-armed bandit problem. That is, if K 1 and M = 1, the problem is the simple multi-armed bandit. If K >> 1 and M the problem corresponds the cascading bandit. If K 1 and M > 1, we recover the assortment bandit problem. The illustrations on comparisons between the cascading assortment bandit and the other combinatorial bandits are presented in Figure 1
In order to accommodate the generalization of the interactive model across items and assortments, also incorporate the feature information of items and parametrization of click model in the cascading assortment bandit model. Hence, we name the model as cascading contextual assortment bandit (see Section 2.2 for the formal definition of the problem setting) Under this newly proposed combinatorial bandit model, we posit the following question:
Can we design provably efficient algorithm for cascading contextual assortment bandits?
To address the question hand, we first have to overcome the technical challenges inherent in each special case of our problem setting: the cascading contextual bandit and the contextual assortment bandit. Firstly, in the cascading contextual bandit [I 25 suboptimal dependence on the cascade length, K. Intuitively, one would expect that as K increases in the cascading model, the regret should either diminish or at least remain constant; performance deterioration should not occur. However, all existing regret bounds for cascading contextual bandits 28 25 This finding is not just caunter-nttuiive, but also suboptimal (for further discussions, refer to Section2.4). As a result, (i) eradicating the suboptimal dependence cascade length K has been recognized
longstanding issue has been the
scale proportionally to K (18 29
17
open problem, even within the cascading
contextual bandit setting
Further, in the context of assortment bandits, there is widely recognized suboptimal dependence on the cooblem-specifin constant K, as demonstrated in the existing assortment bandit literature 9 22 23
This problem-specifi. constant (in Assumption 4.2 represents the curvature of the multinomial logit (MNL) function. Recent studies [24] 3 have demonstrated an improved dependence on K. albeit only multiplied by logarithmic factors. However, this improvement comes the expense of an increased dependence on the assortment size M, a conclusion that is both counter-intuitive and suboptimal. Thus, (ii) decreasing the dependence without escalating the dependence still poses an unresolved issue. While addressing either of the two challenges (i) and (ii) can be daunting individually, tackling both issues simultaneously poses even greater challenge in both our al algorithm design and regret analysis.
M
Note that a non-contextual version of the cascading assortment bandit is a special case of the cascading contextual assortment bandit with one-hot encoded feature vector for each item. Hence, when we aim to provide efficient algorithms for cascading contextual assortment bandit, also address the non-contextual cascading assortment bandit which not been studied previously.
A concurrent work 200 addresses this suboptimal dependence K under the linear model assumption. Our work tackles this challenge under the MNL model in general setting.

---

Table 1: Comparisons of algorithms for contextual cascade and assortment bandits as well for cascading contextual assortment bandits. N is the number of ground items, is a length of cascade, d is dimension of feature vectors and T is total rounds. is problem-depender parameter for the MNL. model. See Appendix A for more discussions.
Algorithm
Context
Cascade
Assortment
Click Model
Regret Bound
CombCascade
14
X
X
Ö(VKNT) (dVKT))
C2-UCB 18
O
O
X
Linear
EE-MNL 5
X
O
MNL
O(VNT)
TS-MNL 22
O
X
O
MNL
UCB- MNL [2X
O
X
O
MNL
((-dVT)
LinTS-Cascadee
28
O
X
Linear
O(A(2KVT)
CascadeWOFUL. 25
O
X
Linear
WWOT+dTTh
VAC²-UCB 2
O
O
X
Linear
O(dVT)
UCB-CCA (Algorithm)
O0
OO
MNL
UCB-CCA+ (Algorithm
MNL
O(dvT)
To this end, we design novel upper confidence bound (UCB) algorithms for contextual cascading assortment bandits, tackling both technical challenges. We show that our proposed algorithms achieve provable guarantees on regret performances overcoming the longstanding technical challenges. Our regret bounds show sharper results than those of the existing contextual cascading bandits or assortment bandits. We corroborate our theoretical claims through numerical experiments, thus ensuring that both our newly proposed bandit framework and the proposed algorithms establish provable efficiency and practical applicability.
Our main contributions are summarized follows.
We formulate general combinatorial bandit model, named cascading contextual assortment bandit that encompasses the existing cascading bandits and assortment bandits. This novel problem setting is observed in many practical applications.
We first propose a UCB bandit algorithm UCB-CCA for the cascading contextual assortment bandit and establish the T-step regret upper-bound of ((EdVT) (in Theorem 4.3). This regret bound is tighter than the existing bounds for cascading contextual bandits, where we not only remove the longstanding, unnecessary dependence on K but also establish the result without dependence on M.
While UCB-CCA is an efficient algorithm achieving both the statistical efficiency and practical performances (shown in Section Z). its regret bound includes dependence on the inverse of a mooblem-dependee constant K, which can be potentially large in the worst case. To improve the dependence on we propose our second algorithm UCB UCB-CCA+ which exploits new Bernstein-type concentration result, taking into account the effects of the local curvature of the MNL model. We prove that UCB OCB-CCA+ achieves (dvTT) without the dependence on in the leading term (only scaling with logarithmic factors), hence significantly improving the regret of UCB-CC CCA without increasing the other dependencies. Hence, we successfully solve the two technical challenges (i) and (ii) mentioned above.
As an independent contribution, we prove that a greedy algorithm for the cascading assort- ment optimization problem gives a 0.5 approximation of the optimal solution (discussed in Section g To our best knowledge, this is the first rigorous result showing the approximation guarantee even for the contextual cascading bandit problem, instead of simply assuming access an approximation optimization oracle.
We evaluate our proposed methods in numerical experiments and show that the practical performances support theoretical claims. Hence, our proposed algorithms along with our newly proposed bandit model establish provable efficiency and practical applicability.
3

---

2 Preliminaries
2.1 Notation
Define [n] as a set of positive integers from 1 n. Let |-] be the length of sequence or the cardinality of a set. For a vector E R we denote the f--norm of x as ||z||2 and the V-weighted norm of for a positive-definite matrix V as ||]|| = Vx Vv. The determinant and trace of a matrix V are (V) and (V), respectively. Amin (V) denotes the minimum eigenvalue of matrix V.
2.2 Cascading Contextual Assortment Bandit Problem
Consider [V]. a set of N items. Let A be set of candidate assortments of items with size M, i.e., A: {A S [N] |A| MJ. A cascade S is ordered sequence of K assortments chosen from A where all the items in these K assortments are distinct. Then, the set of feasible cascades can be defined as follows.
S = (AI, (= Ax) As E A for all k E [K], n I = =0}
At round I, feature vectors { E RR,, i [N]) for every item are revealed to the decision-making agent. Each feature vector Iµ may contain the contextual information of the user at round and the item i. After observing this contextual information, at round t, the agent recommends cascade to the user, where As E A represents the k-th assortment the cascade at round t. The user scans the assortments in S, one by one. If the items in A& do not attract the user, the user moves on to the next assortment A,,++-- The user stops at the O,-th assortment when the user is attracted by an item in the O,-th assortment and clicks the item.
S, =
After the user clicks on item, the agent observes a sequence of user choices y/ = (yHx) where a binary vector Yık = (yeKo, Jek1, Weaad) represents user choices on assortment Auk- Let Utkm
the m-th item im A& is clicked by the user, and frkm clicked on. For each assortment, there is an outside option. That is, there is a probability that the user may not click any of the items in Ack If the user does choose any items, y:ao 1 and Yrlem for all m E MM]. The user choice for each assortment is given by the multinomial logit (MNL) choice model [21] For this MNL model, there is an unknown time-invariant parameter 0" E Rdd, We define the true weight of item i in round as wi, x=,00. Also, we let the vector representation of the weights be defined as w = (w]))eE[N) for convenience.
for items that are not
Under this model, the user's click probability of the m-th item in Au and the probability of the outside option in Au is given respectively by
exp(wit...
Pe(iml Aek; w,) I+ I exp(wit) and Pe(iol Ack, w() I+ EJEA, exp(wiy)
where item io represents the outside option. The user choice yeu sampled from the multinomial distribution, Vtkk MNL(1, (pr(iml Ark, wf)) m where the argument indicates that yeu is a single-trial sample. Hence, Em= Uekm is always 1. Also, we denote measurement noise as Erkm : Utkm - (im Aca, w;) Since Ezkm is bounded in [0, 1], 6xkm is o*-sub-Gaussian with independent
o² 1/4. It important note that Erkm across items in the same assortment due to the substitution effect in the MNL model.
The expected reward function of combinatorial action Se based wt is given by
1s.
f(S,, wf) Σ
II p. ( w
Σ SEA,,
PillAAeks ())lA(kk,(()= w = - II
PoliolAaa wf).
k=1
The formulation above is also known as the cascade model with disjunctive objective, where the user stops at the first attractive item
[8
2.3 a-Approximation Oracle and a-Regret
The exact combinatorial optimization to compute an optimal cascade of assortments can be com- putationally expensive. Therefore, allow for approximate optimization. We assume that the

---

the gram ma- agent has access to an a-optimization oracle to compute a-approximation solution of the cascade optimization problem with a I For approximate optimization, we prove that greedy selection for the cascading assortment optimization problem gives 0.5 approximation of the optimal solution, which may be of independent interest (see Section
Formally, for a given an a-optimization oracle and weight parameter w, the oracle outputs an approximately optimal cascade 5* 0 (w) S satisfying f(S", w) 2 of((S', w) where S e arg maxses f(S, w) an optimal assortment without approximation. The instantaneous a-regret of cascade S₁ in round t is defined as R" (t, St) == B[af(S;; wf) f(S,, w2)] where S e arg maxşes fSS wf) is an true optimal assortment. Then, the goal of the agent is to minimize the cumulative o-regret defined as
T
Rd RT = Σ R St,
Σ Blaf(S), wt) f(S.. w/)]
2.4 Suboptimal Dependence Problem Dependent Parameters
In this subsection, we discuss the main technical challenges faced in the regret amalysis of our problem setting. In particular, the suboptimal dependence cascade length K has been long-standing open problem even in contextual cascading bandits.
2.4.1 Dependence on Length of Cascade K
The previous literature the contextual cascading bandits 18 regret in each round, utilizing the monotonicity and Lipschitz continuity of the expected reward problem would result in
17
26 25
bounds the instantaneous
function f. A simple adaptation of the previously known techniques the following upper bound for the instantaneous regret R (t. St) for S = (An, Ask))..AAk)..
K
(t, S
Σ Bellresllv AD AE
where Be is suitable confidence radius chosen by algorithm, and V is positive definite gram matrix. Then, the dependence on the length of cascade K and the assortment size M would appear in the regret bound after summing the right- hand side of Eq. over the time horizon and applying the Buuchy-Schwarz inequality. Because of this reason, even when M = 1, there still exists dependence on K which appears in the regret bounds of all previous contextual cascading bandits (see Table !I
To overcome this challenge, we present a new Lipschitz continuity the expected reward function to derive the regret bound independent of M and K by replacing the summation with the maximum over assortments and a cascade (see Section 4.3 for more details).
2.4.2 Dependence Worst-Case Scanning Probability
Analogous the existing algorithms for the contextual cascading bandits 18 26
trix V contains the rank-1 matrices of observed items accumulated up to round 4, i.e. V = Et= El EiEA, TriIT, + AI. However, there exists an out-of-control issue, that is, the sum- mation of the rank-1 matrices over O + to |S.| in Eq. is not included in the gram matrix V,, Note that this issue also arises cascading contextual assortment bandits. Adapting a technique used in the existing literature [18 to mitigates this issue, let pt.s, be the probability of examining all assortments in S, and p" min [T] minses Pt.s, be the worst-case probability of examining a cascade over all rounds and all feasible cascades. A simple adaptation of the existing methods would result in the following bound for the expected instantancous regret.
1 (0, = [SB) s Pt.s.
E. (1, 5.)
Rd (1,
S L E (L,S,) [((]]]
"
This concedes the dependence on p", which can be exponentially small the worst case. We overcome this challenge by designing algorithm that offers the assortment containing the most uncertain item as the first assortment in a cascade. We discuss this salient feature of the proposed algorithm in more detail in Section
5

---

Algorithm UCB-CCA
Input: confidence radius 3t and ridge penalty parameter À 2
1: for / ,,..,, do
2: Observe o for all E [N]
3: Compute Uei x 0,, + 3e- 2 |ullyy for all [N]
4: Compute candidate cascade S + (A()) = 0a (4))
5: Find optimistic exposure assortment index he in (1)
argmax ke
|
A if k=
6:
Optimistic exposure swap St +- (AcH) (E(K) where Alk =
Al1
if =
A'
otherwise
Offer S,, and observe feedback O2 and yt (ytR)RETO.)
8: Update V22 < V + Ee= Σie THST
9: Compute the regularized MLE 0g by solving Vo [4(() + 1 =
10: end for
3 Algorithm:
3.1 Upper Confidence Bounds and Confidence Set
UCB-CCA utilizes the upper confidence bounds (UCB) technique 66 16 to compute an optimistic
action based on optimistic estimates of each item's weight, V,i vT,O,- (6) v for
all i E [N]. The confidence radius 3e(6) is specified to maintain a high- gigh--robbbblityy confidence set (6) for the unknown parameter 0*, although the algorithm does not explicitly compute Co))).
C.(6) {0 Rd | 0llv, S 3.(6))
Setting proper confidence radius (8) can guarantee that H lies within the confidence set with probability 1 1- 8. On the event that 0* C (8)), the UCB weight serves as upper bound of a true weight w ;= x n for every item E [N]. We denote the UCB weight vector as = (uei)iE[M) for convenience.
3.2 Optimistic Exposure Swapping
A distinctive element of UCB-CCA is what we call optimistic exposure swapping, procedure crucial for eliminating dependence on the worst-case scanning probability, as elaborated in Section 2.4.2 This technique strategically positions the assortment containing the item with the highest uncertainty among the top items in the first slot the cascade assortments.
In each round f, the a-approximate oracle O (u,) outputs candidate cascade Sy determined by the UCB weights ug It is important to note that S is not immediately presented to the user. Instead, after St is derived using the optimization oracle O* (ux), the algorithm identifies the index k' of an assortment that includes the item with the largest [ares Ilv. in Sy
Subsequently, the algorithm swaps the positions: the assortment A/ is moved to the top of S,, becoming Ar and the initially top assortment A' Sy is relocated the h= position of S,, now A The positions of the other assortments remain the same, that is, Au Ai for all l E [K] {1, k*) } This procedure is viable as the expected reward is unaffected by the display order of assortments in the cascade, as shown Lemma
3.3 Regularized Maximum Likelihood Estimation
UCB-CCA computes a regularized maximum likelihood estimate of the unknown parameter 6*. The MM negative log-likelihood is given by (0) = - 1 --E'1 Dd, ΣM Vrkm log (im Ark, Wr), where
'While the swapping occurs between the first and the --tth positions for specificity, it is sufficient to place A'a- at the top position of St. The sequence of the remaining assortments is not critical.

---

2) = (W is a weight vector, and its element is whs x, For penalty parameter À 2 1, the ez-regularized MLE is given by
0. argmin (0) + +
X 21011
argmin 0
ΣΣΣ Σ
Urkm log pr (1m Ark; w+)
101
0
7=1 k=1
(2)
Regret Analysis of UCB-CCA
4.1 Regularity Condition
Assumption 4.1. ||>||e I for all round and items i E [M] and also ||6*|| S 1.
Assumption 4.2. There exists such that for all [7'] any assortment A, and any item i A, inføers Prii w)pp (toppp/ooo4 (iol w) 2 K, where (WN) and w, = =x
Discussion of Assumptions. Assumption 4.1 makes the regret bound independent on the scale of the feature vector and parameter. This is the standard assumption used the contextual bandit litera- ture I8 ]. Assumption 4.2 is the standard regularity assumption in the contextual assortment bandit literature B 27
adapted from the standard assumption for the link function in the generalized linear contextual bandit literature []6 to ensure that the Fisher information matrix is non-singular.
4.2 Regret Bound of UCB-CCA
Theorem 4.3 (a-regret upper bound of UCB UCB-CCA). Suppose Assumptions 4.7 and 4. hold, and we run UCB-CCA CCA for total T rounds with Br = 2x v dog (1 (KM + log A and with X 2 1, Then, the o-regret of UCB-CCA upper- aaper-bounded by
K
K+1
1
TKM dx
v K
2dTIn (1+ TKM Xd
Rº S
dog
1
+ 4 log T
K+
2k
Discussion of Theorem 4.3 Theorem establishes that UCB-CCA achieves a regret bound of Ö (T). Notably, this regret bound removes dependence on p" completely and removes polynomial dependence on K, achieving the best-known bound in contextual cascading bandits [18 251 20 a special case of our problem setting. Apart from the generalization we consider in this work, key distinction between our work and the previous contextual cascading bandit models lies in our adoption of the MNL model, as opposed to the linear model assumed by the existing literature. This model choice introduces a dependence on the parameter к. within the regret bound of UCB CCA, which is an aspect we address and refine in subsequent sections. essential to highlight that our work tackles more general problem yet achieves improved bounds concerning the key problem parameters previously considered suboptimal. The factor comprised of the length the cascade, K+], in Theorem 4.3 is also notable, which is bounded above by I regardless of the value of K. Consequently, the regret bound does not increase polynomially with K, ensuring scalability.
4.3 Proof Outline
In this subsection, we present the proof sketch of Theorem 4.3 One of the key components of the regret analysis that enables carving off the dependence on K the following lemma.
Lemma 4.4 (Maximal Lipschitz continuity). Suppose wa 2 wit for all E [N]. Then
K
K+1
f(S. ue) f(S,,
max max (uus w;;))
K
+1
A.ES, JE
Lemma 4.4 demonstrates that the difference between the reward functions under the UCB parameter and the true parameter is upper bounded by the maximal difference between the UCB and true parameters. This implies that the regret bound remains unaffected by increases in the cascade length K or the assortment size M.

---

Eliminating the dependence on p" is another key element of our analysis. To this end, we first show that the order of assortments in the cascade model with the disjunctive objective does not affect the expected reward. We formalize this property in the following lemma.
Lemma 4.5. Let Pt: be the probability that the user clicks on any item Ag- Given collection of assortments (A1..... .Ak) with probabilities {pI..... ,PK). their order of display does not matter. Further, for every permutation p: [K] + [K], we have
Σn P KE(K]
II 1 II (1 (pP-p)-- kE[K]
Σ kE[K]
PP
(2) II II 1(6))
k<c
kck
Consolidating these key results, proceed bound the cumulative regret. We begin by leveraging the monotonicity of the expected reward function and the definition the a-approximate optimization oracle to bound the cumulative regret.
T
Ra (T) < E
f(S,, u1) f(Se. wi)
S CKE
Σ
max max (ues whi) Ant ES, ii
< 2
Br
max max | AucSS. iEA
2C E
B1
max max kE Ac
||
(4)
The second inequality is from Lemma 4.4 letting Cк = (K/(K + +1)K The third inequality is given by the concentration of the UCB weights (see Lemma [B.5p. Note that the assortment including the item with the largest value of | is always examined by the user since it is included in the first assortment of S, by the optimistic exposure swapping technique as described in Section 3.2 Note that a change in the order of assortments incurred by the optimistic exposure swapping does not affect the expected reward which is shown in Lemma 4.5 Hence, for every round E [T], we obtain
max max Ask AE
max max | ke kE[O.] iEAx.
(5)
Therefore, the last equality in Eq. is given by 55 Then, we can apply the maximal version of elliptical potential lemma (see Lemma B.8) bound the cumulative regret.
Improved Dependence on K
While UCB-CCI achieves the regret bound of ( improving dependence on K, the bound includes the deeeedeeeepndentt constant k. This implies potential risk of the regret bound becoming large when & becomes very small. In order to circumvent this challenge, we propose new optimism in the face of uncertainty (OFU) algorithm, UCB-CCA+, which exhibits regret bound that is independent of λ in the leading term. The pseudocode of (CC-CCC+ is detailed Algorithm
5.1 Algorithm: UCB-CCA+
5.1.1 Confidence Set
UCB-CCA+ computes regularized MLE ô, following the same procedure described in Section Then, the algorithm constructs
3.3
confidence centered around Ó, utilizing Bernstein-type tail inequality for self-normalized martingales [11 3] Nevertheless, a simple adaptation of the previous approaches may incur increased dependence on M. Hence, a more intricate analysis and refined algorithmic strategy are imperative to effectively address this challenge.
First, we define gr (f) = -' EkE(Or) EiEA, Pr (i]AAk w7)xri + X,0 where w, = (ww)iE(M) and We 0. We also denote the partial derivative of Pe(i]Ack, w/) with respect whi as Pi(i) Ayk: w,) = ( w, wr) |Au,, w.). Additionally, we define the new design matrix con- taining local information, denoted as He(0) = Ei= EnEjo,) EiEA, pr (ilAn,, wy t.
and, for convenience, H, == Ei= Exelo,) EiEa,, (i(1) (i]AA Ark. w + deTa. Then, the algo- rithm constructs a confidence set as below:
(, == (0 Rd (0)) ge (0( (0) S (()))}
8

---

Algorithm 2 UCB-CCA+
Input: confidence radius >r and ridge penalty parameter À 2 1
1: for / ,,..,, do
2: Observe zi for all E [N]
3: Construct confience (8) as defined in Eq.
4: Compute candidate cascade (S; = [ 02)
= arg maxses, B,00E f(S, wz)
5: Find optimistic exposure assortments L and L (and their positions h and v) in St
Tr, if k =
L
if h 2
6: St kEIK) where Ark:
A/e
if
A/2
if h = v otherwise
A
7: Offer St and observe Ot, = (Yekk [E(]..]
8: Update H, f- Hi-1 + E0. EiEA, Ack w/ 22)
9: Update V₁ Vi-1 Ed. EiEAm THal
10: Compute the regularized MLE Or by solving Ve [() + 1011 =
11:
end for
where the confidence radius (5) is suitably specified to ensure that the true parameter 6* lies in the confidence set (6) with high probability. On the event 0* E (,))), The following lemma bounds the weighted f--norm of the difference between 0 and 0" Lemma 5.1. Suppose 8" E (8). Then, for any 0 E (8)) we have ||0 0*||i, S (r).
5.1.2 Doubly Optimistic Exposure Swapping
UCB-CCA+ still faces the challenge outlined in Section 2.4.2 The complication is exacerbated for UCB-CCA+ as the algorithm concurrently updates two gram matrices, H;, and Vg, which only contain the information of the observed items. Building upon the technique of optimistic exposure swapping detailed in Section 3.2 in each round OCB-CCA+ assigns the assortment L, containing the item with the largest uncertainty with respect to H among the top KM items to the first slot of cascade S, Similarly, the algorithm places L - with the item that has the largest uncertainty with respect to V in the second slot of Sr.
5.2 Regret Analysis of UCB-CCA+
Theorem 5.2 (Regret upper bound of UCB-CCA-H Suppose Assumptions
and 4.2 hold, and
UCB-CCA: for total T rounds with X 2 and (6))) == 3v/x,
log
D Katka///a/1222
2
log 2 with 8 t. Then, the regret of UCB UCB-CCA+ is upper-bounded by Vx.
2d
RT(T) s CCTT(0)) 2dTlog (1+
KMT dA
C2 (r())2do
KMT dA
1+
1
k
where C₁ = 36 and C2 216(1 Me).
Discussion of Theorem 5.2 Theorem 5.2 establishes the regret bound of (dvTT). The leading term of the regret bound Is independent of K. Although the second term exhibits dependence on k, the term only scales logarithmically in T", whose comparative effect diminishes as t increases compared to the leading term. Hence, the worst-case regret guarantee of UCB-CCA+ improves from that of UCB-CCA. The comprehensive proof of Theorem 5.2 is provided in the appendix.
6 Approximation Algorithm for Optimal Combinatorial Action
In this section, we show that computing the optimal cascade is, general, a weakly NP-hard problem and give (fast) polynomial time algorithm that the agent can to compute a 0.5-approximation to

---

the optimal cascade for any weight w. We assume that the MNL weights are given and consider the problem of finding the cascade that maximizes the expected reward. This is an optimization problem on selecting a sequence of K assortments with size M each from ground set of N items. The KYnKK ))) In fact, we establish the following hardness result.
number feasible cascades O ((M)
Lemma 6.1. For general M, the optimization problem is weakly NP-hard even for =
The hardness of our problem follows from the hardness result of 19 for related setting of unconstrained cascade optimization where the size of each assortment can be arbitrary. In light of this hardness, we turn attention finding fast approximation algorithms for the problem. While there has been a lot recent work on the unconstrained cascade optimization problem (see [99 12 I0] and the references therein), none of the previous algorithms apply to constrained setting (where the size of each assortment is M).
We consider the following greedy approach for the problem. Consider arbitrary weights at round I, iee. W/ = <[N]) given. We order the items [N] in decreasing order given weights and consider the following cascade of assortments.
D1 = {1,2, ..., M), D2 = {M + 1, M + 2.... 2M), , - +
KM)
We call these assortments "decreasing order assortments". Let OPT denote the value of the optimal solution to the problem. We establish that showing these assortments in any possible sequences gives good approximation to the problem.
Lemma 6.2. Let OPT denote the overall click probability in the optimal solution. The decreasing order assortments D Dk, shown in any order, have overall click probability at least 0.5 OPT.
We present the proof in Appendix We also show that our algorithm is optimal for M 1, which captures the classic cascade optimization problem.
Numerical Experiments
N=10, Me2, d=
N=15. K=z, M=2, 1=
20.0
20.0
Cascae
CambCascade
CRUCH
ChuCh
UCB-CCA
JCB-CCA
15.0
UCS-CCA
15.0
UCS-CCA
Cumueenve Segget
12.5
22.5
30.0
30.0
7.5
7.5
2.5
2.5
500
750
1000
1500
1750
2000
750
1000
1500
1750
2000
Round
Round
Figure 2: N 10, = 2, M and d=5.
Figure 3: 15, 2, M = and d=
In this section, we evaluate the performances of our proposed algorithms UCB-CCA and UCB- +CA+ in numerical experiments and compare their performances with the existing combinatorial bandit algorithms CombCascade and -CB. For simulations, we generate a random sample of the unknown iime-invariant parameter 6* from (/0 1) the beginning of the simulation. We sample N feature vectors from / (0, 1) in each round t. At each round f, the oracle computes sequence of assortments in decreasing order, forming cascade S, based on given Wy. We assess the cumulative regret of UCB-CCA, UCB-CCA+, CombCascade, and C3-UCB. Note that a user's choice for UCB-CCA and UCB-CCA+ is determined by the MNL logit choice model, whereas C3-UCB utilizes linear model and CombCascade is non-contextual model. Figure 2 and UCB-CCA+ significantly outperform C*-UCB and CombCascade. We also observe that UCB-CCA CCC+ shows slight performance advantage over VCB-CCA- although the difference is not statistically significant. While UCB-CCA+ has sharper worst-case regret guarantee, UCB-CCA can provide favorable practical performances, with simpler implementation and computational efficiency.
and Figure 3 indicate that both UCB-CCA
10

---

Acknowledgments and Disclosure of Funding
This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Ko- rea (SS))) (RS-2023-0022288 No. 0022RICIC10068555 No. 2022R1A4A 144100057911 No. 2021MS55D22010244755 and by Creative-Pioneerin Researchers Program through Seoul National University and by Naver.
References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Mare Abeille, Louis Faury, and Clément Calauzènes. Instance-wiss minimax-optimat algorithmss for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 3691 1699., PMLR, 2021.
[3] Priyank Agrawal, Theja Tulabandhula, and Vashist Avadhanula. A tractable online learning algorithm for the multinomial logit contextual bandit. European Journal of Operational Research, 2023.
[4] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mnl- bandit. In Conference on Learning Theory, pages 76-78. PMLR, 2017.
[5] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Mnl-handit: A dynamic learning approach to assortment selection. Operations Research, (755):1453-1485 2019.
[6] Peter Auer. Using confidence bounds for exploitation-exxploaaaioo tradc-offs. Journal of Machine Learning Research, 34N44):397-422, 2002.
[7] Xi Chen, Yining Wang, and Yuan Zhou. Dynamic assortment optimization with changing contextual information. Journal of machine learning research, 2020.
[8] Wang Chi Cheung and David Simchi-Levi. Assortment optimization under unknown multinomial logit choice models. arXiv preprint urXiv:1704.0011 2017.
[9] Wang Chi Cheung and David Simchi-Levi. Thompson sampling for online personalized assortment optimization problems with multinomial logit choice models. Available SSRN 3075658, 2017.
[10] Elaheh Fata, Will Ma, and David Simchi-Levi. Multi-stage and multi-customer assortment optimization with inventory constraints. arXiv preprint arXiv:1908. 09808. 2019.
[11] Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq, Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pages 3052-3060, PMLR, 2020.
[12] Pin Gao, Yuhang Ma, Ningyuan Chen, Guillermo Gallego, Anran Li, Paat Rusmevichientong, and Huseyin Topaloglu. Assortment optimization and pricing under the multinomial logit model with impatient customers: Sequential recommendation and selection. Operations research, 1905)115091533, 2021.
[13] Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning rank in the cascade model. In International conference on machine learning, pages 767-776. PMLR, 2015.
[14] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Combinatorial cascading bandits. Advances in Neural Information Processing Systems, 28, 2015.
[15] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[16] Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference Machine Learning, pages 2071-2080. PMLR, 2017.
[17] Shuai Li and Shengyu Zhang. Online clustering of contextual cascading bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[18] Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In International conference on machine learning, pages 1245-1221001 1253. PMLR, 2016.
[19] Nan Liu, Yuhang Ma, and Huseyin Topaloglu. Assortment optimization under the multinomial logit model with sequential offerings. INFORMS Journal Computing. 32(3):835-88 2020.

---

[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-22593. PMLR, 2023.
[21] Daniel McFadden. Modeling the choice of residential location. Transportation Research Record, (673), 1978.
[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, volume 35, pages 9205-9213, 2021.
[24] Noemie Perivier and Vineet Goyal. Dynamic pricing and assortment under contextual mnl demand. Advances Neural Information Processing Systems, 35:3461-3473 2022.
[25] Daniel Vial, Sujay Sanghavi. Sanjay Shakkottai, and R Srikant. Minimax regret for cascading bandits. arXiv preprint arXiv:2203. 12577, 2022.
[26] Kun Wang. Conservative contextual combinatorial cascading bandit. IREE Access, 9:151434-151443, 2021.
[27] Xue Wang, Mike Mingcheng Wei, and Tao Yao. Online assortment optimization with high-dimensional data, Available at SSRN 3521843, 2019.
[28] Zixin Zhong, Wang Chi Chueng, and Vincent YF Tan. Thompson sampling algorithms for cascading bandils. The Journal of Machine Learning Research, 22(1),9915-9980, 2021.
[29] Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton. Cascading bandits large-scale recommendation problems. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, 2016.
12


Reviews:
[{"review_id": "z0NRJX3yVA", "reviewer": "Reviewer_nP45", "summary": "This paper introduces the cascading contextual assortment bandit problem and provides a UCB type algorithm. This problem is motivated by online content recommendation systems. They develop a UCB algorithm that is applicable to this problem setting, and prove that their algorithm improves upon existing regret bound rates in the cascading and assortment bandit problems respectively. ", "questions": "- It is not clear to me that Assumption 2.3 as written will ever hold. Do you really need to take an infinum over all $\\theta \\in \\mathbb{R}^d$? Based on my understanding, this means that if you take $\\theta = \\lambda \\cdot x_i$ you can make $w_i = x_i^\\top \\theta$ arbitrarily small or large with the choice of $\\lambda$. Then, based on the model from line 127, it seems you could make $p_t(i_m | A_{tk}, w)$ arbitrarily small. Can you explain there any reasonable settings where Assumption 2.3 will hold? If there are, please have a discussion of this and also more information about how to interpret Assumption 2.3.\n- You say below assumption 2.2 that the regret bound is $c$ times larger if you allow the norm of $x_i$ and $\\theta^\\star$ respectively to be bounded below $c$. Is \\emph{knowledge} of $c$ needed by the algorithm? In other words, does your algorithm currently implicitly take advantage of knowledge that you assume that $x_i$ and $\\theta^\\star$ are bounded by $1$? If so, this would severely limit the practical applicability of the approach. If this is the case, this limitation should be discussed. If it is not, it should also be mentioned when discussing scaling by $c$.\n- Could you a sentence or two (or more) about how you suggest to choose ridge penalty $\\lambda$?", "limitations": "- I would like the authors to address the questions / limitations I list in the weaknesses section.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Based on the authors' discussion, the scaling rate of their regret bounds is both sharper and more interpretable/intuitive than that in existing literature. It seems their regret bound improves upon those both in the assortment and cascading bandit literatures respectively.\n- The authors have a nice discussion about why we expect the regret to decrease with $K$ and then show how their result shows this type of dependence. Additionally, their result and discussion of how their regret bound scales with $\\kappa$ in a way that is not worsening its dependency on $M$ seems nice.\n- The overall writing and presentation in the paper pretty good. I think the table 1 is quite useful and Figure 1 was very helpful for understanding the problem.\n", "weaknesses": "- In the evaluation, it was not clear to me why you only compared to C^3-UCB and not the other methods listed in table 1. While the algorithm has these regret guarantees, its not entirely clear if the algorithm really performs well in practice from the simulations in the evaluation section.\n- Only applicable to environments in which the probability that a user clicks is determined by a generalized linear model. Additionally, the feature vector $x_{ti}$ captures both contextual information on the user and the item. It's not clear how this kind of vector could be chosen in practice.\n- There is not a real related works section in the main paper. I see there is one in the Appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time to review our paper and for your valuable feedback. Here are our responses to each comment and question:\n\n**Numerical Evaluations**\n\n- First of all, since our problem setting and proposed model, the cascading assortment bandit, are novel, there are not existing methods proposed exactly under this new model. Hence, we can only report to comparing against special cases. While both assortment bandits and cascading bandits are special cases of our model, assortment bandits do not possess cascading effect for which removing the suboptimal dependence on the cascade length is one of the main objectives. Hence, we aim to compare with cascading bandit algorithms to see the effect. Among the contextual cascading bandit algorithms, C$^3$-UCB is one of very few algorithms whose implementation exist. In this rebuttal (see the pdf file attached to the global rebuttal), we have included a comparison with another related method, CombCascade in [12], and we plan to incorporate further comparisons with other methods in a revision. We would be happy to include more results in the list. We appreciate your feedback in making our paper more persuasive to readers through additional experimental performance comparisons. But also, as this is the first theoretical work proposing the new cascading assortment bandit, the new provably efficient algorithms, and their improved regret bounds removing suboptimal dependence that existed even in less general cases, we respectfully request that it be mainly assessed based on its theoretical merit.\n\n\n*\"Only applicable to environments in which the probability...\"*\n\n- All parametric models for clicks in the bandit framework (whether it is a linear, logistic, or MNL model, along with their combinatorial adaptation, such as cascading, assortment, semi-bandit, etc.) have their own modeling assumption on click probability. Regret bounds are mostly derived under the realizability of each modeling assumption. Hence, we do not necessarily agree with the comment that \"applicability to environments\" with modeling assumptions should be considered a weakness. Rather, as we show in our paper, our proposed model encompasses two of the prominent existing combinatorial bandit instances, cascading bandits (K > 1, M=1) and assortment bandits (K=1, M>1), as well as single-action selection bandits (K=1, M=1), such as logistic bandits and multi-armed bandits with binary feedback. Under this more general model, we show even tighter and stronger regret bounds!\n\n\n*\"the feature vector $x_{ti}$ captures both contextual information on the user and the item...\"*\n\n- Suppose the user at round $t$ is characterized by a feature vector $u_t$ and the item $i$ has a feature vector $v_{ti}$ (note that we can allow item feature to vary over time), then we can use context feature vector as $x_{ti} = \\text{vec}(u_t v_{ti}^{\\top})$, the vectorized outer-product of $u_t$ and $v_{ti}$, as the combined feature vector of item $i$ at round $t$. This is a common technique also used in [16, 18, 19]. If a user's information is not accessible (for example, due to privacy issues), then one can use item-dependent features only, say $x_{ti}=v_{ti}$.\n\n\n\n**Related Works Section**\n\n- Due to the limited space in the main text, we defer the \"Related works\" section to the appendix. We are more than happy to moving the \"Related works\" to the main text in the revisied version.\n\n\n\n**Questions**\n\n**Q1 on Assumption 2.3**: It is a very good question. First of all, Assumption 2.3 is the standard regularity assumption in the MNL contextual bandit literature [5, 6, 18, 19, 20, 23]. Since true $\\theta^*$ is assumed to be $\\|\\theta^*\\| \\leq 1$ (in Assumption 2.2), we can only consider $\\theta \\in \\mathbb{R}^d$ with $\\|\\theta\\| \\leq 1$ for Assumption 2.3 (hence modification in the subscript). Since $\\|x_i\\| \\leq 1$ for all $i$, $x_i^\\top \\theta$ is bounded by $-1 \\leq x_i^\\top \\theta \\leq 1$ for all $i$. Hence, the probability $p_t(i | A_{tk}, w)$ cannot be arbitrarily small. Now, one practical implication of this assumption is that under any choice model we can possibly consider, we consider items that provide utilies to users (items that has aleast some probilities to be clicked).\n\n**Q2 on Assumption 2.2**: The boundness assumption is also a standard assumption in almost all parametric bandit literature [1,3,5,14,16,18,19,20,23] that includes linear, logistic, GLM, and MNL bandits. However, in practice and also in theory, you do not have to tune $c$ seperately. Since all the unknown hyperparameters can be combined $c' := c \\cdot \\frac{1}{\\kappa} \\cdot \\sigma$ and tuned as a whole (where $\\sigma$ is sub-gaussian parameter which is assumed in almost all parametric bandits; note that in MNL bandits, it is known that $\\sigma = \\frac{1}{2}$ but in general parametric bandits, $\\sigma$ is not known). If this were to be considered hinderance, then the same argument should be made about linUCB and linTS as well as almost all existing parametric bandit algorithms.\n\n**Q3 on Choosing $\\lambda$**: If $\\lambda$ can be any value between 1 and $d$, then the regret bound would not change the leading factor. Hence, a common choice of $\\lambda$ is $\\lambda = 1$ or $\\lambda = d$.\n"}, {"review_id": "JQCcCDIjSc", "reviewer": "Reviewer_anEU", "summary": "This paper studies a new combinatorial bandit problem that generalizes the existing cascading and assortment bandits. The authors first propose a UCB-based algorithm, UCB-CCA, that achieves a tighter regret bound than existing bounds for cascading contextual bandits by eliminating the dependence on cascade length $K$. They also introduce an improved algorithm, UCB-CCA+, and use a Bernstein-type concentration to prove a regret bound without $\\kappa^{-1}$ dependence, where $\\kappa$ is a problem-dependent constant in the regret bound of UCB-CCA. Numerical experiments validate the effectiveness of the proposed algorithms.", "questions": "Typo: line 207: In round (at every round) $t$", "limitations": "See Weaknesses.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1) This paper is the first to study the combination of contextual cascading and assortment bandits. This new problem is well-motivated by real-world applications in recommender systems.\n2) One of the main technical contributions is the new Lipschitz continuity of the expected reward function for contextual cascading assortment bandits in Lemma 4.2, which helps prove the regret bound of UCB-CCA is independent of $K$ and $M$. (However, I have a question about the proof of this Lipschitz continuity; see below.)\n3) The proposed UCB-CCA+ algorithm achieves an improved regret bound than that of UCB-CCA, solving the two technical challenges (dependence on cascade length and $\\kappa$) faced by contextual cascading and assortment bandits simultaneously.", "weaknesses": "1) For contextual combinatorial bandits, there is a recent result [A] that provides a regret bound independent of the cascade length $K$ using a variance adaptive algorithm. Moreover, its regret bound can get rid of $p^*$, which raises a concern that whether the optimistic exposure swapping in Section 3.3 is necessary or whether the $p^*$ issue can be resolved by a more involved analysis.\n2) The Lipschitz continuity in Lemma 4.2 is a key component of the analysis. However, the proof in line 402-405 is unclear to me. I would appreciate it if the authors could add more details about the proof; a simple example of the non-contextual cascading bandit can also be helpful.\n3) Although UCB-CCA+ achieves a good regret bound, there is no discussion on the lower bound of contextual assortment combinatorial bandits: would it be similar to that of the contextual combinatorial bandits or contextual assortment bandits?\n\n[A] 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, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time to review our paper and for your valuable feedback. Here are our responses to each comment and question:\n\n**Comparison with [A]**\n\n*  Thank you for introducing [A]. We are more than happy to compare our work with [A].\n*  First of all, we would like to point out the NeurIPS policy on \"recent work\" which states, *\"What is the policy on comparisons to recent work? Papers appearing less than two months before the submission deadline are generally considered concurrent to NeurIPS submissions. Authors are not expected to compare to work that appeared only a month or two before the deadline.\"*\n(https://neurips.cc/Conferences/2023/PaperInformation/NeurIPS-FAQ#:~:text=are%20generally%20considered%20concurrent%20to,or%20two%20before%20the%20deadline.)\n- [A] was published in ICML in July 2023, and its first arXiv version was posted on March 30th, 2023, which was about a month and a half before the NeurIPS submission deadline. Hence, we are not obliged to compare [A] with our work by the policy. Nevertheless, we are more than willing to offer a comparison.\n\n* Upon reviewing [A], we observed that there are significant technical differences in the analysis between our work and [A]. To elaborate the distinction, writing the expected reward function as $\\sum_{i=1}^{K}p_{i}^{\\mu, S}(\\bar\\mu_{i} - \\mu_{i})$ in [A], where $p_{i}^{\\mu, S} = \\prod_{j=1}^{i-1}\\mu_{j}$, allows them to remove $p^\\star$. Then, the difference $\\bar\\mu_{i} - \\mu_{i}$ is represented as a weighted norm of the feature vector, $||x_{i}||_{V_t^{-1}}$. To square a weighted norm of the feature vector, the Cauchy-Schwarz inequality can be applied and a dependency on $K$ arises. That is, the regret bound in Theorem 1 of [A] is independent of $p^\\star$, but dependent on $K$. Improving upon the $K$-dependent regret bound, [A] shows that contextual cascading bandits satisfy triggering probability and variance modulated (TPVM) condition by Lemma 19 in [B] and eventually carves off the $K$ dependence. \n* On the other hand, in our work, to simultaneously eliminate dependencies on both $p^\\star$ and $K$, we utilize the mean-value theorem combined with the swapping technique. We observe that the techinques used in both works are unique. Also, we would like to clearly highlight that our model is based on MNL choice model (and considers cascades of assortments) whereas [A] is based on much simpler linear click model.\n\n**Lipschitz continuity in Lemma 4.2**\n\n* By the mean value theorem, \\begin{align*}\n        f(S_t , u_t ) - f(S_t , w_t^* ) = \\nabla_\\theta f(S_t ,\\bar w)(\\theta_t - \\theta^* )\n        = \\left\\lbrace \\prod_{A_{t \\dot{k}}\\in S_t } p_t (i_0 |A_{t \\dot{k}}, \\bar w) \\right\\rbrace \\sum_{A_{tk}\\in S_t } \\sum_{i \\in A_ {tk}} p_t (i|A_{tk}, \\bar w) x_{ti}^\\top (\\theta_t - \\theta^* ) \n        \\end{align*}\n* For a convenience, let $\\sum_{i\\in A_ {tk}}p_{t}(i|A_{tk}, \\bar{w}) := P_{tk}$. Then, we can simplify $\\lbrace \\prod_{A_{t\\dot{k}}\\in S_{t}} p_{t}(i_{0}|A_{t\\dot{k}}, \\bar{w}) \\rbrace \\sum_{A_{tk}\\in S_{t}} \\sum_{i\\in A_ {tk}}p_{t}(i|A_{tk}, \\bar{w})$ as follows: $\\prod_{\\dot{k}\\in[K]}(1 -P_{t\\dot{k}})\\sum_{k\\in[K]}P_{tk}$. \n* We can see that this expression is maximized as $\\left(\\frac{K}{K+1}\\right)^{K+1}$ when $P_{tk}=\\frac{1}{K+1}$ for all $k\\in[K]$, since $0 < P_{tk} < 1$.\n    \n**On Lower Bounds**\n- Thank you for your questions on possible lower bounds. For logistic bandits ($K=1, M=1)$ which is a special case of our problem setting, [C] established a regret bound as $\\Omega(d\\sqrt{T})$. Also, [5] proved that a regret lower bound for assortment MNL bandits ($K=1, M\\geq1$) is $\\Omega(d\\sqrt{T})$. Thus, our regret upper bound matches with these lower bounds in terms of time horizon $T$ and dimensionality $d$ in these special cases.\n- Lastly, for non-contextual cascade bandits, [21] derived a regret lower bound of $\\Omega(\\sqrt{LT})$ where $L$ is the total number of items, which does not depend on the cascade length $K$. Hence, the $K$-indepedence in the regret upper bound in our result appears to be sound and tight in terms of $K$.\n- For general contextual cascading assortment bandits ($K>1, M>1), to our knowledge, proving a regret lower bound remains an open problem. We will include these discussions on lower bounds in a revised version of our paper.\n\n---\n\n**References**\n\n[A] 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, 2023.\n\n[B] Xutong Liu, Jinhang Zuo, Siwei Wang, Carlee Joe-Wong, John Lui, and Wei Chen. \"Batch-size independent regret bounds for combinatorial semi-bandits with probabilistically triggered arms or independent arms.\"\" Advances in Neural Information Processing Systems, 35:14904–14916, 2022.\n\n[C] Marc Abeille, Louis Faury, and Clément Calauzènes. \"Instance-wise minimax-optimal algorithms for logistic bandits.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021."}, {"review_id": "gmWTQwxJDi", "reviewer": "Reviewer_tk8N", "summary": "This paper studies the Cascading Contextual MNL bandits problem. Two effective algorithms UCB-CCA and UCB-CCA+ are proposed. Compared to existing cascading bandits and MNL bandits, the regrets of the two algorithms have some better dependence on the length of cascades and \\kappa. Numerical simulations demonstrate the effectiveness of the proposed algorithms.", "questions": "Q1. For UCB-CCA+, as \\kappa is removed in the regret, does it mean that we only need the assumption that the Fisher information matrix is invertible?", "limitations": "The authors discuss the limitations of their work in Appendix.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. Combining cascading bandits and MNL bandits is interesting and can find real applications.\n\nS2. The proposed UCB-CCA algorithm has a regret independent of K, the length of cascades.\n\nS3. The results of numerical simulations are good.", "weaknesses": "W1. This paper focuses on removing the dependence on K and \\kappa. It seems to me that improving the dependence on d may be more helpful than removing the dependence on K, since in practice K could be a small constant and the dimension of contextual vectors could be large. Note that [18] has an algorithm for MNL contextual bandits that has a \\sqrt{dT} regret.\n\nW2. In theorem 5.2, the dependence on \\kappa is removed by increasing T. Such a treatment explicitly assumes that T is much larger than 1/\\kappa, which makes some sense in practice. However, I am not sure if this practical assumption is appropriate in the theoretical analysis of regret. \n\nW3. In the numerical simulations, the authors report the cumulative regrets of algorithms. What about the curves of revenues of algorithms? Since all algorithms adopted in experiments have sublinear regrets, the cumulative regret is actually an insignificant term compared to the revenue. I wonder if the difference between the proposed algorithms and the baseline is still as large as reported in Fig 2 when reporting the curves of cumulative revenues.\n\nW4. The submission file and the full version (Supplementary Material) are inconsistent with each other in some parts. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time to review our paper and for your valuable feedback. Here are our responses to each comment and question:\n\n\n**improving dependence on $d$?**\n\n- We believe that you are referring to $\\tilde{\\mathcal{O}}(\\sqrt{dT})$ regret in Theorem 4 of [19]. Then, please note that the regret bound in Theorem 4 of [19] contains $\\log(TN)$ dependence. That is, if the total number of items is very large, such that $N>\\exp(d)$, then the regret bound would eventually be even worse than $\\tilde{\\mathcal{O}}(d\\sqrt{T})$.\n- Note that in both logistic [A] and MNL bandits [5] which are both special cases of the cascading contextual assortment bandits, the regret lower bound is of $\\Omega(d\\sqrt{T})$. Hence, this suggest that $\\mathcal{O}(d)$ dependence cannot be improved for arm-independent bounds. Note that our regret upper bounds in Theorem 4.1 and Theorem 5.2 are in the regime of arm-independent bounds. Hence, we do not see why this has to be considered a weakness.\n\n**$T$ and $1/\\kappa$**\n\n- First of all, note that Theorem 5.2 holds true for all values of $T$, regardless of whether $T$ is larger than $1/\\kappa$ or not. Hence, there is **no necessity for the assumption of $T \\gg 1/\\kappa$ at all** in order for Theorem 5.2 to hold. It is just that depending on the relationship between $T$ and $1/\\kappa$, the leading term may be different. \n- Now, suppose $T$ is small enough such that the second term in Theorem 5.2 becomes dominant as you stated. Then, the total regret would be $\\mathcal{O}(\\frac{1}{\\kappa} d^2 \\log T)$ which in this case has $\\frac{1}{\\kappa}$ dependence but  is logarithmic in $T$, and we have already assumed that $T$ is small if the second term were to be a learning term. So, for small $T$, $\\log T$ becomes even smaller. Hence, such a case is not a concern, both theoretically and practically. Hence for sufficiently large $T$, the regret is $\\mathcal{O}(d \\sqrt{T})$ and small enough $T$, $\\mathcal{O}(\\frac{1}{\\kappa} d^2 \\log T)$.\n\n\n**Plotting curves of revenues?**\n\n- Considering that the definition of regret is the cumulative difference between the expected reward of the optimal action and the expected reward of the action chosen by the agent, conceptually and for numerical purposes, we do not see any difference between comparsion based on regret and comparsion based on revenue. Given that standard metric in the bandit literature by default is regret, we do not see why this has to be considered a weakness. We would be more than happy to include plots in terms of revenue if required.\n\n\n**Supplementary Material**\n\n- When the supplementary material was submitted, the entire manuscript was uploaded which included the main text for convenient reading that includes the proofs and hyperlinks within the document. The uploaded supplementary material includes minor revisions in the main text.\n\n#### Questions\n\n**Q1: Assumption on the Fisher information matrix only?**\n\n* We still need Assumptions 2.2 and 2.3. What we claim is that $\\kappa$ in Assumption 2.3 no longer depends on the leading term of our regret upper bound.\n\n\nWe trust that our responses have sufficiently addressed your questions and alleviated any concerns. Should you need any clarification, we are more than happy to address them during the discussion period.\n\n---\n\n**References**\n\n[A] Marc Abeille, Louis Faury, and Clément Calauzènes. \"Instance-wise minimax-optimal algorithms for logistic bandits.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021"}, {"review_id": "lV2WYwwOVN", "reviewer": "Reviewer_Q2NZ", "summary": "This paper studies a new contextual combinatorial multi-armed bandit model, which generalizes the contextual cascading bandits and assortment bandits.  For the offline problem when item parameters are known, the authors propose a 0.5-approximate solution. For the online problem where parameters are not known a priori, the authors first propose a UCB algorithm, called UCB-CCA, which yields a regret bound of $\\tilde{O}(\\kappa^{-1}d\\sqrt{T})$ regret bound. To remove the unsatisfying $\\kappa$ which may be relevant to the cascade length $K$, the authors further leverage Bernstein-type concentration and propose a new algorithm UCB-CCA+, which removes the $\\kappa^{-1}$ dependence and achieves regret bounds that are independent of $K$. Finally, the authors conduct experiments to show the practical efficacy of the proposed methods.", "questions": "Please comment point 1,2,3 in the above weakness part.", "limitations": "The authors adequately addressed the limitations and there are no potential negative societal impact of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Overall, I feel this is a decent work that is suitable to put in the combinatorial MAB literature.\n\n1. From the model perspective, the model is new and general, which covers contextual cascading bandits and MNL bandits as degenerate cases.\n2. For the results, Table 1 gives a clear comparison with existing works and this paper gives the first regret bound for this new model. Interestingly, when the \n3. For the analysis, this paper not only is grounded by existing works from MNL bandit, but also gives some new techniques \n4. For the writing, it is clear and intuitive supported by intuitive figures and tables.", "weaknesses": "Overall, I do not have major concerns, yet I have some minor comments, which I hope to get some clarification to validate my understanding.\n\n1. In line 8 of Algorithm UCB-CCA+, the algorithm uses the true parameter $w_t^*$ which is unknown, is it a typo?\n2. In line 4 of Algorithm UCB-CCA+, it is a combinatorial optimization problem over a confidence radius $B_t(\\delta)$, it is NP-hard in general? Is any computational-efficient method for this?\n3. I cannot find the lower bound result for the current problem. Is the current result matches the lower bound?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time to review our paper and for your valuable feedback. Here are our responses to each comment and question:\n\n\n**Typo in Algorithm UCB-CCA+**\n\n* Yes, it is a typo. Thank you very much for catching it. It should be corrected to $\\theta_t$.\n\n**Combinatorial Optimization in UCB-CCA+**\n\n- Thank you for your question. Yes, finding the optiaml cascade is weakly-NP hard as we show in Lemma D.1 in the appendix. To this end, in Appendix D, we prove that a greedy selection for the cascading assortment optimization problem gives a 0.5 approximation of the optimal solution. We believe such approximation optimization guarantee is very rarely shown in combinatorial bandit literature. We believe that this result serves an independent contribution.\n\n**On Lower Bounds**\n- Thank you for your questions on possible lower bounds. For logistic bandits ($K=1, M=1)$ which is a special case of our problem setting, [A] established a regret bound as $\\Omega(d\\sqrt{T})$. Also, [5] proved that a regret lower bound for assortment MNL bandits ($K=1, M\\geq1$) is $\\Omega(d\\sqrt{T})$. Thus, our regret upper bound matches with these lower bounds in terms of time horizon $T$ and dimensionality $d$ in these special cases.\n- Lastly, for non-contextual cascade bandits, [21] derived a regret lower bound of $\\Omega(\\sqrt{LT})$ where $L$ is the total number of items, which does not depend on the cascade length $K$. Hence, the $K$-indepedence in the regret upper bound in our result appears to be sound and tight in terms of $K$.\n- For general contextual cascading assortment bandits ($K>1, M>1), to our knowledge, proving a regret lower bound remains an open problem. We will include these discussions on lower bounds in a revised version of our paper.\n\n\n---\n\n**References**\n\n[A] Marc Abeille, Louis Faury, and Clément Calauzènes. \"Instance-wise minimax-optimal algorithms for logistic bandits.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021."}, {"review_id": "39IIJHSZ1Q", "reviewer": "Reviewer_jQVq", "summary": "This paper studies the contextual cascading assortment bandit problem, and proposes low regret algorithms for this problem.", "questions": "1. The first claim the paper makes is that they are able to remove the dependence on K in the cascading bandit problem by using a swapping technique. However, I believe this depends on the specific loss function used, therefore this claim is not entirely accurate. Specifically, the swapping technique only holds when the order does not matter, but this does not generally hold for cascading bandits. \n2. The second claim is the regret removes $\\kappa$ term. However, the regret definition is different from assortment bandits, therefore is this claim really accurate? \n3. In section 2.4, is the description talking about the cascading bandit problem or cascading assortment bandit problem?", "limitations": "The author did not address limitations.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. This paper studies a novel problem by combining ideas from assortment bandits and cascading bandits. \n\t2. The paper introduces some new algorithmic ideas.", "weaknesses": "It seems to me the optimal cascading assortment should obey some structural properties, i.e., should similar items appear in the same assortment? Should different items appear in the same assortment? Should we pair desirable items together? Or should we pair high-weight and low-weight items together for an ‘anchoring effect’? It will be interesting to hear insights on this. \n\nThe writing contains noticeable grammatical errors and typos\n\nThe reward function in this work seems to greatly simplify the problem and removes the difficulty in prior work. See questions section below. \n\n---------------\nUpdate. Some issues in writing include:  \n1. several sentences in paragraph from line 215-227\n2. line 272, the $Ht^{-1}$ I assume should be subscript. \n3. Not writing out the constant in line 268 and 278 is strange.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time to review our paper and for your valuable feedback. We truly hope that we can resolve any doubts and misunderstandings of our result if there are any. Here are our responses to each comment and question.\n\n**Structural Properties of Optimal Cascading Assortment?**\n\n- The model is clearly defined in Section 2.2. Other than the MNL choice model structure stated in lines 127-128 and cascading interaction model, we do not impose any other structure on optimal assortment. With all due respect, we do not see why this has to be considered as a weakness.\n\n**\"The reward function in this work seems to greatly simplify the problem and removes the difficulty in prior work\"**\n\n- No, it does not. We strongly disagree with the comment. As we show in our paper, our proposed model encompasses two of the prominent existing combinatorial bandit instances, cascading bandits (K > 1, M=1) and assortment bandits (K=1, M>1), as well as single-action selection bandits (K=1, M=1), such as logistic bandits and multi-armed bandits with binary feedback. We propose a more general and more complicated model that is more challenging for regret analysis than the existing combinatorial parametric bandits. On top of that, we show even tighter and stronger regret bounds, overcoming the longstanding sub-optimal dependence!\n\n \n**Questions**\n\n**Q1: Swapping Technique and Dependence on $K$?**\n\n- You have stated that the swapping technique we propose has limitations in eliminating the dependency on $K$. Unfortunately, that is not correct. The swapping technique is intended to remove the worst-case scanning probability, denoted as $p^*$. The swapping technique has no relations to removing $K$ at all.\n- Now, we will show why dependence on $p^*$ appears and how we can mitigate this. See Section 4.2.1 in [16]. For contextual cascading bandits (with no assortments), the authors in [16] show that the regret at round $t$ is upper bounded as follows:\n    \\begin{equation} \\mathcal{R}^\\alpha (t, S_t ) \\le 2B \\sum_{i \\in S_ t } \\beta_t (\\delta) \\|x_{ti}\\|_{V_t^{-1}}. \\end{equation}    \n- Since $V_t$ contains only information of observed base arms, $i \\in \\lbrack O_\\tau \\rbrack: \\forall \\tau\\in \\lbrack t\\rbrack$, there is out of control issue in summation. [16] copes with this issue by a resorting to the case that $O_{t} = |A_{tk}|$ using the worst-case scanning probability $p^*$ as below, which then results in $\\frac{1}{p^*}$ dependence in the final regret bound in [16].\n    \\begin{align}\n        \\mathbb{E} \\lbrack \\mathcal{R}^\\alpha (t, S_t ) \\rbrack\n        \\le \\frac{1}{p^\\star} \\mathbb{E} \\lbrack \\mathcal{R}^\\alpha (t, S_t ) \\mathbb{1} \\lbrace O_t =|S_t | \\rbrace \\rbrack \n        \\le \\frac{2B}{p^\\star} \\mathbb{E} \\lbrack \\sum_{i \\in \\lbrack O_t \\rbrack } \\beta_t (\\delta) \\|x_{ti}\\|_{V_t^{-1}} \\rbrack.\n\t\\end{align}\n- However, in our case, the instantaneous regret at round $t$ is upper bounded as follows: \n\\begin{equation*}\n\\mathcal{R}^\\alpha (t, S_t ) \\le f(S_t , u_t ) - f(S_t , w_t^\\star) \\le 2\\Big( \\frac{K}{K+1}\\Big)^{K+1} \\max_{i \\in S_t } \\beta_t (\\delta) ||x_{ti}||_{V_t^{-1}}$.\n\\end{equation*}\n- As we mentioned in section 4.1 (line 242-244), the assortment with the largest item with respect to $\\|x_{ti}\\|_{V_t^{-1}}$ is always examined since it is in the first position of $S_t$ by our proposed swapping technique. \n- Due to the max operator and swapping technique, we can obtain the below inequality: \n\\begin{equation*}\n\\mathcal{R}^\\alpha (t, S_t ) \\le 2\\Big( \\frac{K}{K+1}\\Big)^{K+1} \\max_{i \\in \\lbrack O_t \\rbrack} \\beta_t (\\delta)\\|x_{ti}\\|_{V_t^{-1}}.\n\\end{equation*} Thus, $p^\\star$ does not appear in our regret analysis.\n\n* The swapping technique is applied utilizing the structure of cacading model, where change in the order of assortments within the cascade does not affect the expected reward. Such a invariance is one of the key characteristics of the cascade model widely studied in the many existing previous literature [11, 12, 15, 21, 24].\n\n**Q2: \"the regret definition is different from assortment bandits, therefore is this claim really accurate?\"\"**\n\n- First, we would like to clarify the premise of your question that \"the regret definition is different from assortment bandits.\" If you are referring to the use of  $\\alpha$-approximate regret in our work (and in most cascading bandit literature) and the regret using exact optimization in assortment bandits, then we can set $\\alpha = 1$, which is the regret using an exact optimization without approximation. Hence, regrets in our setting and assortment bandits (without cascade) are comparable when $K = 1$ which is a special case of our problem setting. Therefore, the claim is accurate.\n- Note that due to the complexity of computing the exact optimal solution in combinatorial optimization in general, it is very standard to use $\\alpha$-approximate regret, denoted as $\\mathcal{R}^{\\alpha}$, in the wide range of combinatorial bandit literatures [7, 16, 22, 25, A, B]. To this end, in Appendix D, we even prove that an approximation solution using greedy algorithm for the cascading assortment optimization problem gives a 0.5 approximation of the optimal solution, which we believe is an independent contribution.\n\n**Q3: Is Section 2.4 about Cascading bandit problem or Cascading assortment bandit?**\n\n* The notions of $\\alpha$-approximation oracle and $\\alpha$-regret apply to our problem setting, cascading assortment bandit problem, which also includes both cascading bandits and assortment bandits. This is a very common notion in cascading and combiantorial bandit literature as seen in [7, 16, 22, 25, A, B] and many more. \n\n---\n\n**References**\n\n[A] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. ICML, pp.151–159. PMLR, 2013.\n\n[B] Andi Nika, Sepehr Elahi, and Cem Tekin. Contextual combinatorial volatile multi-armed bandit with adaptive discretization. AISTATS, pp.1486–1496. PMLR, 2020."}]

Author rebuttal:
We would like to express our sincere gratitude for your overall positive feedback and recognizing the significance of our contributions. We introduce a novel combinatorial bandit model, *the cascading contextual assortment bandit*, which generalizes two of the prominent existing combinatorial bandits, cascading and assortment bandits and also generalizes single-action selection bandits. Not only do we generalize these bandit problem settings, but also we tackle longstanding open problem with suboptimal dependence on the cascade length. Hence, we take on a more general and more difficult problem and propose provably efficient algorithms and salient features and improved analysis. We strongly believe that the new model, the algorithms, the regret analysis, and the approximate optimization guarantees that we provide in this paper offer meaningful contributions to the community.

Incorporating the review of Reviewer nP45, we have also included an additional comparison to the CombCascade in [12] and intend to include more comparisons with additional methods in a revised version. For this experiment, we set (1) the total number of items $N=10$, the length of the cascade $K=2$, the size of the assortment $M=2$, the dimension (for the feature vector and parameter) $d=5$ (see Figure 6) and (2) $N=15, K=2, M=2, d=10$ (see Figure 7). You can see the results in the attached pdf file. Our proposed algorithm UCB-CCA and UCB-CCA+ perform better than C$^3$-UCB in [16] and CombCascade in [12]. 

Meta-review: The paper is a study on the mixture model that combines cascading bandits and assortment bandits together in a contextual bandit environment. The problem is reasonably motivated. The authors provide algorithms and theoretical analysis of their regret bounds.  All reviewers are positive in general to the paper (with scores 7, 6, 6, 5, 5), and the issues raised by reviewers have mostly been addressed by the authors rebuttal. Reviewer anEU did point out a recent ICML'23 paper that partially overlaps with the current submission. That paper can be viewed as a concurrent paper with the current one, and as the authors explained, two studies use quite different approaches, so the overlapping result does not post a serious issue here. 

Given the overall positive support to the paper by all five reviewers, I recommend acceptance to the paper. I encourage the authors to provide a comprehensive revision to the paper to address all the comments, especially a detailed comparison with the concurrent and partially overlapping paper pointed out by a reviewer.
Decision: Accept (poster)