Cascading Reinforcement Learning

Thank you very much for your time and effort in reviewing our paper! We have incorporated your comments in the revised version, and highlighted our revision in red font.

1. Contribution of our Generalization to Cascading MDPs

We emphasize that our generalization to cascading MDPs is very different from prior cascading bandit works [Kveton et al. 2015; Combes et al. 2015], since we face a unique challenge on how to efficiently compute the optimal permutation. To tackle this challenge, we make use of special properties of the objective function for cascading MDPs, and develop a novel and efficient oracle BestPerm using a dynamic programming approach for combinatorial optimization.

Specifically, prior cascading bandit works [Kveton et al. 2015; Combes et al. 2015] consider finding the optimal subset of items as follows:

$$\max_{A \in \mathcal{A}} \quad f(A) = \sum_{i=1}^{|A|} \prod_{j=1}^{i-1} \Big( 1-q(A(j)) \Big) q(A(i)) = 1- \prod_{i=1}^{|A|} \Big( 1-q(A(i)) \Big) . \quad Eq. (i)$$

This objective function only depends on the attraction probabilities of items $q(A(i))$. Thus, prior works only need to select $m$ items with the maximum attraction probabilities, which do not involve computational difficulty.

In contrast, our cascading MDP problem considers finding the optimal ordered subset of items as follows (for step $h=H,H-1,\dots,1$):

$$\max_{A \in \mathcal{A}} \quad Q^{*}_h(s,A)$$ $$\ \qquad = \sum_{i=1}^{|A|} \prod_{j=1}^{i-1} \Big( 1-q(s,A(j)) \Big) q(s,A(i)) \Big( r(s,A(i))+p(\cdot|s,A(i))^\top V^{*}_{h+1} \Big) .$$

Our objective function depends on both the attraction probabilities $q(s,A(i))$ and the expected future rewards $r(s,A(i))+p(\cdot|s,A(i))^\top V^{*}_{h+1}$.

This requires us to solve a combinatorial optimization problem for each $s \in \mathcal{S}$ as follows:

$$\max_{A \in \mathcal{A}} \quad f(A,q,w) = \sum_{i=1}^{|A|} \prod_{j=1}^{i-1} \Big( 1-q(A(j)) \Big) q(A(i)) w(A(i)) , \quad Eq. (ii)$$

where $q(a):=q(s,a)$ and $w(a):=r(s,a)+p(\cdot|s,a)^\top V^{*}_{h+1}$

(in the online RL process, we can have the estimates of $r(s,a)$, $p(s'|s,a)$ and $V^*_{h+1}(s')$). This optimization involves two attributes of items $q(a)$ and $w(a)$, instead of just depending on $q(a)$, which is far more challenging to efficiently compute than Eq. (i).

To overcome this computational difficulty, we first analyze the special properties of $f(A,q,w)$, including the fact that sorting items in descending order of $w(a)$ gives the optimal permutation (Section 4.1). Then, based on these properties, we design an efficient oracle BestPerm to solve Eq. (ii), building upon a novel dynamic programming approach for finding the best subset from sorted items (Section 4.2):

$$F[i][k] = \max \\{ F[i+1][k],\ q(a_i) w(a_i) +(1-u(a_i)) F[i+1][k-1] \\} ,\quad 1\leq i \leq J-1,\ 1 \leq k \leq \min\\{m,J-i+1\\} .$$

Here $F[i][k]:=\max_{(a'_1,\dots,a'_k) \subseteq (a_i,\dots,a_J)} f((a'_1,\dots,a'_k),q,w)$ denotes the optimal objective value that can be achieved by selecting $k$ items from items $a_i,\dots,a_J$ which are sorted in descending order of $w(a)$. Furthermore, we also provide rigorous analyses for the properties of $f(A,q,w)$ and the correctness of oracle BestPerm (Lemmas 1 and 2).

To sum up, our generalization to cascading MDPs has the following novelties: (1) This generalization introduces a significant computational challenge on how to efficiently find the optimal permutation. (2) To resolve this challenge, we analyze the special properties of the objective function for cascading MDPs, and design an efficient oracle BestPerm based on a novel dynamic programming. Rigorous proofs are provided for the properties of the objective function and the correctness of oracle BestPerm. (3) Building upon oracle BestPerm and the carefully-designed exploration bonuses for estimates, we develop provably computationally-efficient and sample-efficient algorithms for cascading RL.

2. Experiment

Following the reviewer's suggestion, we conduct experiments on a larger-scale real-world dataset MovieLens [Harper & Konstan 2015] (also used in prior works [Zong et al. 2016; Vial et al. 2022]) with more baselines. We present preliminary experimental results here (due to time limit), and will certainly include more results for larger numbers of states and items in our revision.

The MovieLens dataset contains 25 million ratings on a 5-star scale for 62000 movies by 162000 users. We regard each user as a state, and each movie as an item. For each user-movie pair, we scale the rating to [0,1] and regard it as the attraction probability. The reward of each user-movie pair is set to 1. For each user-movie pair which has a rating no lower than 4.5 stars, we set the transition probability to this state (user) itself as 0.9, and that to other states (users) as $\frac{0.9}{S-1}$. For each user-movie pair which has a rating lower than 4.5 stars, we set the transition probability to all states (users) as $\frac{1}{S}$. We use a subset of data from MovieLens, and set $\delta=0.005$, $K=100000$, $H=3$, $m=3$, $S=20$, $N \in \\{10,15,20,25,30,40\\}$ (the number of items) and $|\mathcal{A}|=\sum_{\tilde{m}=1}^{m} \binom{N}{\tilde{m}} \tilde{m}! \in \\{820,2955,7240,14425,25260,60880\\}$ (the number of item lists).

We compare our algorithm CascadingVI with three baselines, i.e., CascadingVI-Oracle, CascadingVI-Bonus and AdaptVI. Specifically, CascadingVI-Oracle is an ablated version of CascadingVI which replaces the efficient oracle BestPerm by a naive exhaustive search. CascadingVI-Bonus is an ablated variant of CascadingVI which replaces the variance-aware exploration bonus $b^{k,q}$ by a variance-unaware bonus. AdaptVI adapts the classic RL algorithm [Zanette & Brunskill 2019] to the combinatorial action space, which maintains the estimates for all $(s,A)$ rather than $(s,a)$. The following table shows the cumulative regrets and running times of these algorithms. (CascadingVI-Oracle, which does not use our efficient computational oracle, is slow and still running in some instances with large $N$. We will update its results once it finishes.)

As shown in the above table, our algorithm CascadingVI achieves the lowest regret and a fast running time. CascadingVI-Oracle has a comparative regret performance to CascadingVI, but suffers a much higher running time, which demonstrates the power of our oracle BestPerm in computation. CascadingVI-Bonus attains a similar running time as CascadingVI, but has a worse regret (CascadingVI-Bonus looks slightly faster because computing a variance-unaware exploration bonus is simpler). This corroborates the effectiveness of our variance-aware exploration bonus in enhancing sample efficiency. AdaptVI suffers a very high regret and running time, since it learns the information of all permutations independently and its statistical and computational complexities depend on $|\mathcal{A}|$.

We have also presented the figures of these experimental results in our revised version.

3. Replies to Questions

3.1 Computational Complexity of $\mathbb{E}_{s'\sim\tilde{p}^k}[\dots]$

The complexity of computing $\mathbb{E} (s'\sim\hat{p}^k) [( \bar{V}^k_{h+1}(s')-\underline{V}^k_{h+1}(s') )^2 ]$ in Algorithm 2 is $O(\mathcal{S})$. (In this response, we use $(s'\sim\hat{p}^k)$ to denote the subscript of $\mathbb{E}$ due to the formula display issue of OpenReview.)

3.2 Computation of the Value Function $w$

Algorithm CascadingVI performs optimistic value iteration by backward iteration for step $h=H,H-1,\dots,1$. At each step $h$, we already have the estimates $\hat{p}^k(s'|s,a)$ and $\bar{V}^k_{h+1}(s')$, and then we can compute the optimistic estimate for $w(s,a)$ as $\bar{w}^k(s,a) \leftarrow r(s,a)+\hat{p}^k(\cdot|s,a)^\top \bar{V}^k_{h+1}+ b^{k,pV}(s,a)$ (Line 10 of Algorithm 2). The complexity of computing $\bar{w}^k(s,a)$ is $O(\mathcal{S})$. After that, for each state $s \in \mathcal{S}$, we call oracle BestPerm with $\bar{w}^k(s,a)$ to efficiently calculate the optimal value and the optimal permutation, i.e., $\bar{V}^k_h(s),\ \pi^k_h(s) \leftarrow BestPerm(A^{ground}, \bar{q}^k(s,\cdot), \bar{w}^k(s,\cdot))$ (Line 11 of Algorithm 2).

Actually, the biggest computational difficulty of BestPerm is how to efficiently solve the combinatorial optimization Eq. (ii) in our Reply 1. BestPerm takes advantage of the special properties of the objective function for cascading MDPs, and adopts a novel dynamic programming approach to solve it (see our Reply 1).

3.3 Intuition of the Exploration Bonus $b^{k,pV}(s,a)$

Our construction of $b^{k,pV}(s,a)$ follows that in prior RL work [Zanette & Brunskill 2019], which guarantees the optimistic estimation for $p(\cdot|s,a)^{\top} V^*_{h+1}$. Below we describe the intuition behind $b^{k,pV}(s,a)$ (Lemmas 7-8 in Appendix C.2).

According to Bernstern's inequality, we have that with high probability,

$$| (\hat{p}^k(\cdot|s,a) - p(\cdot|s,a))^{\top} V^*_{h+1} | \leq 2 \sqrt{ \frac{Var_{s'\sim p}(V^*_{h+1}(s')) \log( \frac{KHSA}{\delta'} ) }{n^{k,p}(s,a)} } + \frac{H \log( \frac{KHSA}{\delta'} ) }{n^{k,p}(s,a)} . \quad Eq. (iii)$$

Hence, the right-hand side of Eq. (iii) is the Bernstern-type exploration bonus of $p(\cdot|s,a)^{\top} V^*_{h+1}$. However, the algorithm does not know the exact $Var_{s'\sim p}(V^*_{h+1}(s'))$, and thus we want to use the estimate of $Var_{s'\sim p}(V^*_{h+1}(s'))$ instead of itself.

Following the analysis in [Zanette & Brunskill 2019], we have that if $\bar{V}^k_{h+1}(s') \geq V^*_{h+1}(s') \geq \underline{V}^k_{h+1}(s')$ for any $s' \in \mathcal{S}$, then with high probability,

$$\sqrt{Var_{s'\sim p }(V^*_{h+1}(s'))} \leq \sqrt{Var_{s'\sim \hat{p}^k }(\bar{V}^k_{h+1}(s'))} + \sqrt{\mathbb{E} (s'\sim\hat{p}^k) [( \bar{V}^k_{h+1}(s')-\underline{V}^k_{h+1}(s') )^2 ]} + 2H \sqrt{\frac{ \log( \frac{KHSA}{\delta'}) }{n^{k,p}(s,a)}} .$$

Plugging the above inequality into Eq. (iii), we have that with high probability,

$$| (\hat{p}^k(\cdot|s,a) - p(\cdot|s,a))^{\top} V^*_{h+1} | \leq 2 \sqrt{ \frac{Var_{s'\sim \hat{p}^k} (\bar{V}^k_{h+1}(s')) \log( \frac{KHSA}{\delta'} ) }{n^{k,p}(s,a)} } + 2 \sqrt{ \frac{\mathbb{E} (s'\sim\hat{p}^k) [( \bar{V}^k_{h+1}(s')-\underline{V}^k_{h+1}(s') )^2 ] \log( \frac{KHSA}{\delta'} ) }{n^{k,p}(s,a)} } + \frac{5H \log( \frac{KHSA}{\delta'} ) }{n^{k,p}(s,a)} := b^{k,pV}(s,a) .$$

Thus, if $\bar{V}^k_{h+1}(s') \geq V^*_{h+1}(s') \geq \underline{V}^k_{h+1}(s')$ for any $s' \in \mathcal{S}$, then $\hat{p}^k(\cdot|s,a)^\top \bar{V}^k_{h+1}+ b^{k,pV}(s,a)$ is an optimistic estimate of $p(\cdot|s,a)^{\top} V^*_{h+1}$.

In the following, we discuss how to guarantee the optimism of $\bar{V}^k_{h+1}$, and the proof for pessimism is similar (Lemmas 14-15 in Appendix C.2).

First, we prove that $f(A,q,w)$ satisfies the monotonicity property, i.e., if $\bar{q} \geq q$ element-wise and the items in $A$ are ranked in descending order of $w$, then $f(A,\bar{q},w) \geq f(A,q,w)$.

Then, we prove the optimism of $\bar{V}^k_{h+1}$ by induction. For $h=H$, it trivially holds that $\bar{V}^k_{H+1} \geq V^*_{H+1}$ element-wise, and thus $\hat{p}^k(\cdot|s,a)^\top \bar{V}^k_{H+1}+ b^{k,pV}(s,a)$ is an optimistic estimate of $p(\cdot|s,a)^{\top} V^*_{H+1}$. Using the monotonicity property of $f(A,q,w)$, the fact that the items in the optimal permutation are ranked in descending order of weights, and the optimism of $\bar{w}^k(s,a) = r(s,a)+\hat{p}^k(\cdot|s,a)^\top \bar{V}^k_{H+1}+ b^{k,pV}(s,a)$, we can prove that the output value $\bar{V}^k_H$ of oracle BestPerm is an optimistic estimate of $V^*_{H}$. For $h=H-1,H-2,\dots,1$, by induction and similarly using the optimism of $\bar{V}^k_{h+1}$ and $\hat{p}^k(\cdot|s,a)^\top \bar{V}^k_{h+1}+ b^{k,pV}(s,a)$, we can prove that $\bar{V}^k_h$ is an optimistic estimate of $V^*_{h}$ for all $h \in [H]$.

We have added more explanation in Section 5.1 in our revision.

1. Contribution of our Generalization to Cascading MDPs

Thank you for the detailed response. Please allow to further articulate my point of view on why I believe this extension's significance is limited relative to what I believe is already known from the vanilla cascading bandits (and please correct me where I am missing something).

Dynamic programming is already an established method for computing optimal policies in an MDP. The proposed novelty here is the reduction of computation time for this algorithm by exploiting the cascading structure, i.e. the fact that "basic" actions are rankings (and hence the number of actual items in our ranking pool is much much smaller than that of actions). But in my opinion, it is already known that we don't need to evaluate every individual ranking, since it is sufficient to know the expected value of each individual item in this state (probability of click and expected future value) to construct the optimal ranking in a given state and avoid complexities in $O(|\mathcal{A}|)$. Therefore I am not convinced this result (expanding the setting to the RL setting and providing an oracle algorithm avoiding $O(|\mathcal{A}|)$ computational complexity) represents a sufficiently significant addition to the literature.

I have one other standing curiosity for which I wonder if you can provide any insights: Would a naive algorithm that simply takes the top $m$ items as sorted by $q(s, i) \times w(s, i)$ (the expected return of item $i$ weighted by its chance to be clicked when inspected) and further sorts these by $w(s, i)$ (items with the highest expected return at the top, regardless of their attractiveness) produces optimal rankings?

Any insights you can offer are appreciated (I am not expecting a proof, just wondering if you have any counter-example at hand or whether you've seen this fail in your experiments).

Thank you for giving us an opportunity to interact with you!

1. Significance of Our Contribution

Indeed it is already known that one only needs to evaluate each item, instead of each ranking, in classic cascading (combinatorial) bandits [Kveton et al. 2015]. However, the objective function in cascading bandits

$$\max_{A \in \mathcal{A}} \quad f(A,q) = \sum_{i=1}^{|A|} \prod_{j=1}^{i-1} \Big( 1-q(A(j)) \Big) q(A(i)) = 1- \prod_{i=1}^{|A|} \Big( 1-q(A(i)) \Big) . \quad Eq. (i)$$

only involves one attribute of items, i.e., the attraction probability $q(a)$. This objective function completely depends on $q(a)$, which is obvious to compute. They only need to select $m$ items with the maximum attraction probabilities $q(a)$.

However, when generalizing to RL, the objective function at each step $h$ is

$$\max_{A \in \mathcal{A}} f(A,q,w) := \sum_{i=1}^{|A|} \prod_{j=1}^{i-1} \Big( 1-q(A(j)) \Big) q(A(i)) w(A(i)) , \quad Eq. (ii)$$

which involves two attributes of items, i.e., the attraction probability $q(a)$ and the expected current and future reward $w(a)$ (here $w(a)=r(s,a)+p(\cdot|s,a)^\top V^*_{h+1}$ given the state $s$ and step $h$). Eq. (ii) itself is a complex combinatorial optimization problem even when one only evaluates the attributes of individual items and ignores the recursion over step $h$, and there is no obvious monotone rule with respect to $q(a)$, $w(a)$ or $q(a)*w(a)$.

To solve Eq. (ii), we design an efficient computational oracle BestPerm, using a novel dynamic programming rule based on the cascading feature of $q(a)$ and $w(a)$:

$$F[i][k] = \max \\{ F[i+1][k],\ q(a_i) w(a_i) +(1-q(a_i)) F[i+1][k-1] \\} ,\quad 1\leq i \leq J-1,\ 1 \leq k \leq \min\\{m,J-i+1\\} , \quad Eq. (iv)$$

where

$F[i][k]:=\max_{(a'_1,\dots,a'_k) \subseteq (a_i,\dots,a_J)} f((a'_1,\dots,a'_k),q,w)$

denotes the optimal objective value achieved by selecting $k$ items from items $a_i,\dots,a_J$ which are sorted in descending order of $w(a)$. The intuition behind our dynamic programming rule is that: for a sorted item sequence $a_i,a_{i+1},\dots,a_J$, if we do not select $a_{i}$, then the optimal objective value is equal to that achieved by selecting $k$ items from $a_{i+1},\dots,a_J$, i.e., $F[i+1][k]$. Otherwise, if we select $a_{i}$, then the optimal objective value is equal to $(1-q(a_i))$ multiplying the optimal value achieved by selecting $k-1$ items from $a_{i+1},\dots,a_J$, i.e., $(1-q(a_i)) F[i+1][k-1]$, due to the cascading feature of the objective function.

We note that the "dynamic programming" we mentioned in our contribution statements refers to the dynamic programming Eq. (iv) that we design to solve the combinatorial optimization Eq. (ii), which iterates over the indices of items $1\leq i \leq J-1$ and the number of selected items $1 \leq k \leq \min\\{m,J-i+1\\}$. We were not referring to the well-known MDP dynamic programming that iterates over step $h=H,H-1,\dots,1$.

In other words, our dynamic programming rule (Eq. (iv)) and oracle BestPerm provide an efficient computational solution to the combinatorial optimization Eq. (ii), which one needs to solve at each step $h$ in cascading RL even when only using the attributes of individual items. This is a significant contribution and novel to the combinatorial bandit/RL literature.

2. Counter-example for the Naive Algorithm

A naive algorithm that first sorts items by $q(a)*w(a)$ and further sorts them by $w(a)$ cannot find the optimal ranking.

Consider a counter-example as follows: There are 10 items $a_1,a_2,\dots,a_{10}$, and we want to find the optimal ranking with the maximum cardinality $m=3$. The attraction probabilities $q(a)$, weights $w(a)$ and their products $q(a)*w(a)$ of items are shown in the following table.

The naive algorithm the reviewer mentioned will output $(a_4,a_5,a_6)$, while our computational oracle BestPerm will output $(a_3,a_4,a_5)$ according to our dynamic programming rule Eq. (iv).

The objective values $f(A,q,w) := \sum_{i=1}^{|A|} \prod_{j=1}^{i-1} ( 1-q(A(j)) ) q(A(i)) w(A(i))$ of $(a_4,a_5,a_6)$ and $(a_3,a_4,a_5)$ are

$$f((a_4,a_5,a_6),q,w)=0.28+(1-0.4)*0.3$$ $$\qquad\qquad\qquad\qquad\qquad +(1-0.4)*(1-0.5)*0.3=0.55 ,$$ $$f((a_3,a_4,a_5),q,w)=0.24+(1-0.3)*0.28$$ $$\qquad\qquad\qquad\qquad\qquad +(1-0.3)*(1-0.4)*0.3=0.562 > f((a_4,a_5,a_6),q,w) .$$

This demonstrates that the output of the naive algorithm $(a_4,a_5,a_6)$ is not the optimal solution.

Thank you very much for your time in reviewing our paper and your positive comments! We have revised our paper according to your suggestions. Our revision is highlighted in orange font.

1. Merit of the RL Formulation Compared to Contextual Bandits

We agree with the reviewer that contextual bandits can also be used to formulate historical user behaviors as part of contexts. We think that RL is more suitable for long-term reward maximization, since it considers state transition and potential future rewards in decision making.

For example, consider a video recommendation scenario. The recommendation system encounters a user who is interested in funny videos and TV series. Given this context, contextual bandits mainly recommend videos which can maximize the reward in the current context. Hence, contextual bandits may recommend funny videos which usually give higher instantaneous utilities. In contrast, RL recommends videos which maximize the expected cumulative (long-term) reward, which also considers the potential rewards generated by future states. Thus, in this case, RL may recommend TV series videos. Although TV series videos may have lower instantaneous utilities, once the user is attracted to some of them, the user can enter a high-reward successor state, i.e., he/she is obsessed with it and keeps watching subsequent videos of this TV series. Therefore, using the RL formulation can obtain higher rewards in the long term.

2. Related Works

We detail the differences of our cascading RL model from prior works below.

[Kveton et al. 2015; Cheung et al. 2019; Zhong et al. 2021; Vial et al. 2022] study the cascading bandit model. In their model, there is no state (context), and the reward generated by each item (if clicked) is one. Thus, the order of selected items does not matter, and they only need to select $m$ items with the maximum attraction probabilities. [Zong et al. 2016; Li & Zhang 2018] consider the contextual cascading bandit problem. In their problem, the agent first observes the context (i.e., the feature vector of each item) at each timestep, and the attraction probability of each item is the inner-product of its feature vector and a global parameter. The order of selected items still does not matter, and they need to select $m$ items with the maximum attraction probabilities in the current context. [Li et al. 2016] investigate contextual cascading bandits with position discount factors and a general reward function. In their model, the order of selected items matters, and they assume to have access to an oracle that can output the optimal ordered subset of items for the general reward function.

Different from the above works, our cascading RL formulation further considers state transition, and the attraction probabilities and rewards of items depend on states. Thus, we need to put the items with higher rewards in the current state in the front. In addition, we require to both maximize the attraction probabilities of selected items, and optimize the potential rewards from future states. Furthermore, instead of assuming access to an oracle, we design an efficient oracle to find the optimal ordered subset of items.

3. Replies to Minor Things

Thank you for pointing out the unclear sentence and typo!

We have revised the statement in the fourth contribution to "CascadingBPI is optimal up to a factor of $\tilde{O}(H)$ when $\varepsilon < \frac{H}{S^2}$" to avoid confusion, and fixed the typo.

---

References:
[1] Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning to rank in the cascade model. ICML 2015.
[2] Wang Chi Cheung, Vincent Tan, and Zixin Zhong. A thompson sampling algorithm for cascading bandits. AISTATS 2019.
[3] Zixin Zhong, Wang Chi Chueng, and Vincent YF Tan. Thompson sampling algorithms for cascading bandits. JMLR 2021.
[4] Daniel Vial, Sujay Sanghavi, Sanjay Shakkottai, and R Srikant. Minimax regret for cascading bandits. NeurIPS 2022.
[5] Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton. Cascading bandits for large-scale recommendation problems. UAI 2016.
[6] Shuai Li and Shengyu Zhang. Online clustering of contextual cascading bandits. AAAI 2018.
[7] Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. ICML 2016.

Thank you very much for your time and effort in reviewing our paper! We have revised our paper according to your comments. Our revision is highlighted in orange font.

1. Presentation on the Correctness of Oracle BestPerm

Thank you for your helpful suggestion! We have moved the correctness guarantee of oracle BestPerm to the main text (Lemma 2) in our revision.

2. Technical Challenges

Below we elaborate the technical challenges and novelties in addition to the oracle for solving Problem Eq. (2).

• Even if we know how to solve Problem Eq. (2), in the online RL process, we only have the estimates of attraction probabilities, transition distributions and value functions. Then, how to guarantee the optimism of the output value by oracle BestPerm with optimistic estimated inputs is a crucial challenge. To handle this challenge, we prove the monotonicity property of the objective function for cascading RL by induction, leveraging the fact that the items in the optimal permutation are ranked in descending order of $w$ (Lemma 14). This monotonicity property guarantees the optimism of our estimation under the use of oracle BestPerm with optimistic estimates (Lemma 15).

• Since the objective function for cascading RL involves two attributes of items, i.e., attraction probabilities $q(s,a)$ and the expected future rewards $p(\cdot|s,a)^\top V^*_{h+1}$, how to construct exploration bonuses for them is an important step in algorithm design. We build the exploration bonuses for $q(s,a)$ and $p(\cdot|s,a)^\top V^*_{h+1}$ separately for $(s,a)$, rather than adding an overall exploration bonus for each $(s,A)$. This exploration bonus design enables us to achieve regret and sample complexity bounds that depend only on the number of items $N$, instead of the number of item lists $|\mathcal{A}|$.

• Another critical challenge is how to achieve the optimal regret bound when our problem degenerates to cascading bandits [Vial et al. 2022] given that cascading RL has a more complicated state-transition structure. To tackle this challenge, we use a variance-aware exploration bonus $b^{k,q}(s,a)=\sqrt{\frac{\hat{q}^k(s,a) (1-\hat{q}^k(s,a)) L}{n^{k,q}(s,a)}} + \frac{5 L}{n^{k,q}(s,a)}$, which can adaptively shrink when the attraction probability $q(s,a)$ is small. In regret analysis, when performing summation over $b^{k,q}(s,a)$, this variance-awareness saves a factor of $\sqrt{m}$, and enables our regret bound to match the optimal result in cascading bandits [Vial et al. 2022].

3. Readability

Thank you for your valuable suggestions! We have revised Algorithm 2 according to your comments to improve readability in our revision.

4. The Gap $\sqrt{H}$

The gap $\sqrt{H}$ appears because we construct the exploration bonuses for $q(s,a)$ and $p(\cdot|s,a)^\top V^*_{h+1}$ separately, which leads to an additional $\sqrt{H}$ factor when summing up $b^{k,q}(s,a)$ and $b^{k,pV}(s,a)$ in regret analysis.

Below we elaborate this in detail. In regret analysis, using value difference lemma, the regret decomposition contains the following term

$$\sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{E} \Bigg[ \sum_{i=1}^{|A_h|} \prod_{j=1}^{i-1} (1-q(s_h,A_h(j))) \bigg( \bar{q}^k(s_h,A_h(i)) \left( \hat{p}^k(\cdot|s_h,A_h(i))^\top \bar{V}^k_{h+1} + b^{k,pV}(s_h,A_h(i)) \right)- q(s_h,A_h(i)) p(\cdot|s_h,A_h(i))^\top \bar{V}^k_{h+1} \bigg) \Bigg]$$ $$= \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{E} \Bigg[ \sum_{i=1}^{|A_h|} \prod_{j=1}^{i-1} (1-q(s_h,A_h(j))) \bigg( \Big( q(s_h,A_h(i))+2b^{k,q}(s_h,A_h(i)) \Big) \Big( \hat{p}^k(\cdot|s_h,A_h(i))^\top \bar{V}^k_{h+1} + b^{k,pV}(s_h,A_h(i)) \Big) - q(s_h,A_h(i)) p(\cdot|s_h,A_h(i))^\top \bar{V}^k_{h+1} \bigg) \Bigg] \quad Eq. (i)$$ $$\leq \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{E} \Bigg[ \sum_{i=1}^{|A_h|} \prod_{j=1}^{i-1} (1-q(s_h,A_h(j))) \bigg( q(s_h,A_h(i)) \Big( \hat{p}^k(\cdot|s_h,A_h(i))^\top \bar{V}^k_{h+1} + b^{k,pV}(s_h,A_h(i)) - p(\cdot|s_h,A_h(i))^\top \bar{V}^k_{h+1} \Big) + 4Hb^{k,q}(s_h,A_h(i)) \bigg) \quad Eq. (ii) \Bigg]$$

Since we construct exploration bonuses for $q(s,a)$ and $p(\cdot|s,a)^\top V^*_{h+1}$ separately, in Eq. (i) above, the regret contains a product $(q+b^{k,q})(\hat{p}^\top \bar{V}+b^{k,pV}-p^\top V)$, while the regret for classic RL only contains the term $\hat{p}^\top \bar{V}+b^{k,pV}-p^\top V$. To handle this product, we bound it by $q(\hat{p}^\top \bar{V}+b^{k,pV}-p^\top V)+b^{k,q}(\hat{p}^\top \bar{V}+b^{k,pV}-p^\top V)=q(\hat{p}^\top \bar{V}+b^{k,pV}-p^\top V)+O(H b^{k,q})$. Here the $O(H b^{k,q})$ term directly leads to a $\tilde{O}(H\sqrt{HK})$ regret.

A straightforward idea to improve the $\sqrt{H}$ gap is to combine the attraction probability $q$ and transition distribution $p$ as an integrated transition distribution $\tilde{p}(s'|s,A)$ for each item list $A$, and construct an overall exploration bonus for $\tilde{p}(s'|s,A)$. However, this strategy forces us to maintain the exploration bonus for each $A \in \mathcal{A}$, which will incur an additional dependency on $\mathcal{A}$ in the regret bound and is computationally inefficient.

We think that a more fine-grained analysis for bounding $b^{k,q}(\hat{p}^\top \bar{V}+b^{k,pV}-p^\top V)$ or a more advancing bonus construction approach may be helpful to close the $\sqrt{H}$ gap. We plan to further investigate it in our future work.

---

Reference:
Daniel Vial, Sujay Sanghavi, Sanjay Shakkottai, and R Srikant. Minimax regret for cascading bandits. NeurIPS 2022.

Thank you very much for reviewing our paper and your positive comments! We have incorporated your suggestions in the revised version, and highlighted our revision in teal font.

1. The Scenario Where $S$ Is Not Too Large

Consider a video recommendation scenario where the videos are categorized into multiple types, e.g., news, education, entertainment and movies. Here each item is a video, and each action (item list) is a list of videos. We can define each state as the types of the last one or two videos that the user just watched, which represents the recent preference and focus of the user. Then, the recommendation system suggests a list of videos according to the recent viewing record of the user. After the user chooses a new video to watch, the environment transitions to a next state which represents the user's latest interest. In such scenarios, the number of states $S$ is polynomial in the number of types of videos, which is not too large. Therefore, our cascading RL formulation and algorithms are useful and practical for these applications.