Cascading Reinforcement Learning
Authors: Yihan Du
R. Srikant
Wei Chen
Venue: ICLR 2024 spotlight (2024)
Keywords: reinforcement learning
cascading bandits
combinatorial action space
computational and sample efficiency
Primary area: reinforcement learning

Abstract: Cascading bandits have gained popularity in recent years due to their applicability to recommendation systems and online advertising. In the cascading bandit model, at each timestep, an agent recommends an ordered subset of items (called an item list) from a pool of items, each associated with an unknown attraction probability. Then, the user examines the list, and clicks the first attractive item (if any), and after that, the agent receives a reward. The goal of the agent is to maximize the expected cumulative reward. However, the prior literature on cascading bandits ignores the influences of user states (e.g., historical behaviors) on recommendations and the change of states as the session proceeds. Motivated by this fact, we propose a generalized cascading RL framework, which considers the impact of user states and state transition into decisions. In cascading RL, we need to select items not only with  large attraction probabilities but also leading to good successor states. This imposes a huge computational challenge due to the combinatorial action space. To tackle this challenge, we delve into the properties of value functions, and design an oracle BestPerm to efficiently find the optimal item list. Equipped with BestPerm, we develop two algorithms CascadingVI and CascadingBPI, which are both computationally-efficient and sample-efficient, and provide near-optimal regret and sample complexity guarantees. Furthermore, we present experiments to show the improved computational and sample efficiencies of our algorithms compared to straightforward adaptations of existing RL algorithms in practice.

Published as a conference paper at ICLR 2024
CASCADING REINFORCEMENT LEARNING
Yihan Du
R. Srikant"
Electrical and Computer Engineering University of Illinois AtranaaChaappln
Electrical and Computer Engineering
University of Illinois Lirbana-Champaa
Urbana, IL 61801, USA
Urbana, IL 61801, USA
"ihandu@illinoke
rsrikant 2entttilllinnn eillinois..... edu
Wei Chen
Microsoft Research Beijing 100080, China weicêmicrosoff com
ABSTRACT
Cascading bandits have gained popularity in recent years due to their applicability to recommendation systems and online advertising. In the cascading bandit model, at each timestep, an agent recommends an ordered subset of items (called an item list) from pool of items, each associated with an unknown attraction probability. Then, the user examines the list, and clicks the first attractive item (if any), and after that, the agent receives a reward. The goal the agent is to maximize the expected cumulative reward. However, the prior literature cascading bandits ignores the influences user states (c.g., historical behaviors) on recommendations and the change of states the session proceeds. Motivated by this fact, we propose generalized cascading RI. framework, which considers the impact of user states and state transition into decisions. In cascading RL., we need to select items not only with large attraction probabilities but also leading to good successor states. This imposes a huge computational challenge due to the combinatorial action space. To tackle this challenge, we delve into the properties of value functions, and design an oracle BestPerm to efficiently find the optimal item list. Equipped with BestPerm, we develop two algorithms CasCadingVI and Cascading8PI, which are both computation--effiiies and sample-efficient, and provide near-optimal regret and sample complexity guarantees. Furthermore, present experiments to show the improved computational and sample efficiencies of our algorithms compared to straightforward adaptations of existing RL algorithms in practice.
INTRODUCTION
In recent years, model called cascading bandits (Kveton et al., 2015; Combes al., 2015; Li et al., 2016; Vial et al., 2022) has received extensive attention in the online learning community, and found various applications such as recommendation systems (Mary al., 2015) and online advertising (Tang et al., 2013). In this model, an agent is given a ground set of items, each with an unknown attraction probability. At each timestep. the agent recommends an ordered list of items examines the items one by one, where the probability that each item attracts the user is equal to its attraction probability. Then, the user clicks the first attractive item (if any). and skips the following items. If an item is clicked in the list, the agent receives a reward; if no item is clicked, the agent receives no reward. The objective of the agent to maximize the expected cumulative reward.
user, and the user
While the cascading bandit model has been extensively studied, it neglects the influences of user states ge. users' past behaviors) on recommendations, and the fact that states can transition as users take actions. For example, in personalized video recommendation, the recommendation system usually suggests a list of videos according to the characteristics and viewing records of users. the user clicks a video, the environment of the system can transition to next state that stores the
"ooresponniig authors.

---

Published as a conference paper at ICLR 2024
user's latest behavior and interest. Next, the recommendation system will suggest videos of a similar type as what the user watched before to improve the click- thrck-thoogghhhh rate. While contextual cascading bandits (Li et al., 2016; Zong et al., 2016) can also be used to formulate users' historical behaviors as part of contexts, cascading RI. is more suitable for long-term reward maximization, since it considers potential rewards from future states. For instance, maximize the long-term reward, the recommendation system may recommend videos TV series, since users may keep watching subsequent videos of the same TV series once they get attracted to one of them.
To model such state-dependent behavior, we propose a novel framework called cascading rein- forcement learning (RL), which generalizes the conventional cascading bandit model depict the influence of user states on recommendations and the transition of states in realistic applications. In this framework, there is a pool of N items and space of states. Each state-item pair has an unknown attraction probability, an underlying transition distribution and deterministic reward. In each episode (e.g., a session in recommendation systems), at each step, the agent first observes the current state (e.g., the user's past behavior in the session), and recommends list of at most S N items. Then, the user goes over the list one by one, and clicks the first interesting item. After that, the agent receives a reward, and transitions no item in the list interests the user, the agent receives zero reward, and transitions to a next state according to the current state and virtual item a Here we say that the user clicks a 1 if item is clicked. We define a policy as a mapping from the space of states and the current step to the space of item lists, and the optimal policy as the policy that maximizes the expected cumulative reward.
next state according to the current state and clicked item.
Our work distinguishes itself from prior cascading bandit studies (Kveton et al., 2015; Vial et al., 2022) on its unique computational challenge. In prior cascading bandit studies, there no state, and they only need to select m items with the highest attraction probabilities, which does not involve computational difficulty. In contrast, in cascading RL, states also matter, and we need to balance between the maximization of the attraction probabilities of chosen items and the optimization of the expected reward obtained from future states. This poses a great computational difficulty in the planning of the optimal policy under a combinatorial action space. Moreover, the combinatorial action space also brings a challenge on sample efficiency, i.c., how to avoid a dependency on the exponential number of actions in sample complexity.
To handle these challenges, we conduct a fine-grained analysis on the properties of value functions, and design efficient oracle BestPerm to find the optimal item list, based novel dynamic programming for combinatorial optimization. Furthermore, we design sample-efficient algorithms CascadingVI and CascadingBPI, which employ oracle BestPerm to only maintain the estimates for items and avoid enumerating over item lists. Finally, we also conduct experiments demonstrate the superiority of our algorithms over naive adaptations of classic RI. algorithms in computation and sampling.
cmmputation-efffcieet and
The contributions of this work are summarized as follows.
We propose the cascading RL framework, which generalizes the traditional cascading bandit model to formulate the influence of user states (e.g., historical behaviors) on recommen- dations and the change of states through time. This framework can be applied to various real-world scenarios, e.g., personalized recommendation systems and online advertising.
To tackle the computational challenge of cascading RL, we leverage the properties of value functions to develop novel oracle BestPerm, which uses carefully-designed dynamic programming to efficiently find the optimal item list under combinatorial action spaces.
For the regret minimization objective, with oracle BestPerm, we design an efficient algo- rithm Cas CagV. and establish a Ö(H (LHHHSH HSNK) regret, which matches known lower bound for the general episodic RL setting up to Ö(VH). Here is the number of states, H/ is the length of each episode, and K is the number of episodes. Note that the regret depends only on the number of items N, instead of the exponential number of item lists.
For the best policy identification objective, we devise a computation and sample efficient algorithm CascadingBPI, and provide Ō ((HSNN) sample complexity. CascadingBPI is optimal up to factor of Ö(H) when < H1 3z, where is accuracy parameter.
2

---

Published as a conference paper at ICLR 2024
2 RELATED WORK
Cascading bandits. Kveton et al. (2015) and Combes et al. (2015) concurrently introduce the cascading bandit model, and design algorithms based on upper confidence bounds. Cheung et al. (2019) and Zhong et al. (2021) propose Thompson Sampling-type (Thompson, 1933) algorithms. Vial et al. (2022) develop algorithms equipped with variance-aware confidence intervals, and achieve near-optimal regret bounds. In these cascading bandit studies, there is state (context), and the order of selected items does not matter. Thus, they only need to select m items with the maximum attraction probabilities. Li et al. (2016); Zong et al. (2016) and Li & Zhang (2018) study linear contextual cascading bandits. In (Zong et al., 2016; Li & Zhang, 2018), the attraction probabilities depend on contexts, and the order of selected items still does not matter. Hence, they need to select m items with the maximum attraction probabilities in the current context. Li et al. (2016) consider position discount factors, where the order of selected items is important.
Different from the above studies, our cascading RL formulation further considers state transition, and the attraction probabilities and rewards depend on states. Thus, we need to put the items that induce higher expected future 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 future reward.
Provably efficient RL. In recent years, there have been number of studies on provably efficient RL, e-g. (Jaksch et al., 2010; Dann & Brunskill, 2015; Azar et al., 2017; Jin et al., 2018; Zanette & Brunskill, 2019). However, none of the above studies tackle the challenge of combinatorial action space and the computation and sample efficiency issues it brings. In contrast, we have to directly face this challenge when we generalize cascading bandits to the RL framework to better formulate the state transition in real- world recommendation and advertising applications, and we provide satisfactory solutions with near optimal computation and sample efficiency.
3 PROBLEM FORMULATION
We consider an episodic cascading Markov decision process (MDP) M(S, M(S,AFroul A AA, m, q.P, H). Here S is the space of states. Agmand := {ai...., .a......a... a_} is the ground set of items, where a1...... an are regular items and a_ is virtual item. Item a_ is put at the end of each item list by default, which represents that no item in the list is clicked. An action (i.e., item list) A is a permutation which consists of least one and at most S N regular items and the item an the end. AA is the collection of all actions. We use "action" and "item list" interchangeably throughout the paper. For any A A and i E []A[], let A(i) denote the i-th item in A, and we have A(IAA) = aa1.
For any (s, a) E S x Aground, q(s,a) E [o, 1] denotes the attraction probability, which gives the probability that item a is clicked in state 8; r(s,a) a) E [0, 1] is the deterministic reward of clicking item a in state s; p(-|s, a) E As is the transition distribution, so that for any s' E S. p(s'|s, a) gives the probability of transitioning to state s' if item a is clicked in state s. For any s E S. we define ((8, a1) := 1 and r(s, a1) := O (because if no regular item is clicked, the agent must click an and receives zero reward). Transition probability p(-|s, a.)) allows to formulate interesting transition scenarios that could happen when none of the recommended items is clicked. One of such scenarios is that the session ends with no more reward, which is modeled by letting p(so|s, a = 1 where so is a special absorbing state that always induces zero reward.
H is the length of each episode. In addition, we define a deterministic policy π = { : + Aheejr) as a collection of H mappings from the state space to the action space, so that (s) gives what item list to choose in state at step h.
The cascading RL game is as follows. In each episode k. an agent first chooses policy x², and starts from a fixed initial state s := $1. At each step h E [H], the agent first observes the current state s (e.g., stored historical behaviors of the user), and then selects an item list A = x xs())) according to her policy. After that, the environment (user) browses the selected item list one by one following the order given in AK.- When the user browses the i-th item A& (i E [[ [). there is a probability of q(5), (t) that the user is attracted by the item and clicks it. This attraction and clicking event is independent among all items. Once an item (a(1) is clicked, the agent observes which item is clicked and receives reward r(s), A); skipping the subsequent items {A} (1)isggaag)) and the
system transitions next state s/+11 ~ p(1 At()). On the other hand, if regular item in Al
3

---

Published as a conference paper at ICLR 2024
is clicked, i.e., say that T_ is clicked, then the agent receives zero reward and transitions to next state s ~ p(-1s% a1). After step H, this episode ends and the agent enters the next episode.
For any k > 0 and & E [H]] we use A to denote the index of the clicked item in A and A A if no regular item is clicked. In our cascading RL model, the agent only observes the attraction of items (A) (i.e., items (4) are not clicked and item A (i) is clicked), and the state . the system transitions into based on the unknown p(1|s A (1x,))). Whether the user would click any item in (A) is unobserved.
For any policy n. h E [H] and E S, we define value function VÆ S + [0, HI] the expected cumulative reward that can be obtained under policy x, starting from state $ at step h, till the end of
the episode. Formally, V (s) (s) := E..p. 1E r Ay (Iw) ss,,, = s). Similarly, for any policy
π. h E [H] and (s, A) E S x A, we define Q-value function Q7 S A + [0, Hj as the expected cumulative reward received under policy π, starting from (s, AA at step h, till the end of the episode, ie., Q7 (s, A) p.. ~ r(s,, Arr (In-))
s, As, A}. Since S, A and H are finite, there exists a deterministic optimal policy H' which always gives the maximum value V (s) for all E S and h E [H] (Sutton & Barto, 2018). The Bellman equation and Bellman optimality equation for cascading RL can be stated as follows.
= | -I:4)-EII
g(s (())) a(s, A(i) (r(s.A(i) ((())))) - p(1ss, A(1)) Viitt))
i=1 j=1
(s) = (s,
(8+ = 0,
Vs E [H].
IAI i-1
(s, = ΣI (1- (1-9(1, A61)) ((s)) (r(s, + +(-(s, A()))Ti))) Viit): i-1 j=1
(1)
(b(( = max Q7 A),
(5) = 0, Vs E V A, vh [M].
Here [T (1- 9(s A(i)) is the probability that item A(i) is clicked, which captures the cascading feature. r(s, A(i)) + p(11s, A(i)) Vi++ 1 is the expected cumulative reward received from step l onward if item A(i) is clicked at step h. Q7 A) is the summation of the expected cumulative reward over each item in A. In this work, we focus on the tabular setting where S is not too large. This practical in category recommendation, the vidcos are categorized into multiple types, and the recommendation system can suggest videos according to the types of the latest one or two videos that the user just watched.
recommendation applications. For example, in video
We investigate two popular objectives in RL, i.e., regret minimization and best policy identification. In the regret minimization setting, the agent plays K episodes with the goal of minimizing the regret R(K) = Σk= parameter 10 and an accuracy parameter s, the agent aims identify an s-optimal policy # which satisties V/* (s1) 2 Vi (81) - e with probability at least - ö, using as few episodes as possible. Here the performance is measured by the number of episodes used, i.e., sample complexity.
k= (s1) - VT (s1). In the best policy identification setting, given a confidence
4 AN EFFICIENT ORACLE FOR CASCADING RL
In the framework of model-based RL,, it typically assumed that one has estimates (possibly including exploration bonuses) of the model, and then planning problem is solved to compute the value functions. In our problem, this would correspond to solving the maximization in Eq. (1), Different from planning in classic RL (Jaksch et al., 2010; Azar et al., 2017; Sutton & Barto, 2018), 8), in cascading RL, a naive implementation of this maximization will incur exponential computation complexity due to the fact that we have to consider all A A.
To tackle this computational difficulty, we note that each backward recursion step in Eq. (1) involves the solution combinatorial optimization of the following form: For any ordered subset of A ground
4

---

Published as a conference paper at ICLR 2024
denoted by A, Agronnd R and A Aumund + R,
|A i-1
[A, u, w) = (I- ((()))))((( AEA
max
(2)
i=1==
Here I(A, u, w) corresponds to (s; A), al ((((i)) represents g(s, A(i), and w(A(i) stands for r(s, A(i)) A())s,((i)) A(i)) Vh+ We have u(ai) 1 to match with ((s =
4.1 CRUCIAL PROPERTIES OF PROBLEM (2)
Before introducing efficient oracle solve problem Eq. (2), first exhibit several nice properties of this optimization problem, which serve as the foundation of our oracle design.
For any subset of items X C AAground let Perm(X) denote the collection of permutations of the items in X, and DesW (X) E Perm(X) denote the permutation where items are sorted in descending order of For convenience of analysis, here we treat a an ordinary item oI,...,ay a. and Tp can appear in any position in the permutations in Perm(X).
Lemma 1.
The weighted cascading reward function f(A, u, w) satisfies the following properties:
(i) For any u, w and X S AAground we have
ux) =
u.)
max f(A, u, W).
AEPem(X)
(ii) For any u, and disjoint X, C Agrondd \ {ai) such that w(a) > wla for any E X,X, we have
f((DesW(X), u, w) S ((Des(XXUX),
w)).
Furthermore, for any u, w and disjoint X, X' C A \ {{a] such that w(a) > w(al).oo any X, and w(a) w(a1) for any a E X', we have
f((Des((X,X) a1), u. w) S f(Dees a,), w.)
Property (i) can be proved by leveraging the continued product structure in f(A, w) and a similar analysis as the interchange argument (Bertsekas & Castanon, 1999; Ross, 2014). Property (ii) follows from property (i) and the fact that w(a.) = 1. The detailed proofs are presented in Appendix B.
Remark. Property (i) exhibits that when fixing subset of Aground the best order of this subset is to rank items in descending order of w. Then, the best permutation selection problem in Eq. (2) can be reduced to best subset selection problem.
Then, natural question is what items and how many items should the best subset (permutation) include? Property (ii) gives an answer we should include the items with weights above w (a_). and discard the items with weights below w(al). The intuition behind is follows: If permutation does not include the items in X' such that w(a) > w(a1) for any E X', this is equivalent to putting X' behind a.,, since u(a_) = 1. Then, according property (i), we can arrange the items in X' in front of a (i.e., include them) to obtain a better permutation. Similarly, if a permutation includes the items X' such that w(a) w(a1) for any a E X', from property (i), can also obtain better permutation by putting X' behind ai, i.e., discarding them.
4.2 ORACLE BestPerm
Making use of the properties of [(A, u, w), we develop an efficient oracle BestPerm to solve problem Eq. (2), based carefully-designed dynamic programming to find the optimal item subset.
Algorithm presents the pseudo-code oracle BestPerm. Given attraction probabilities u and weights we first sort the items in Agound in descending order of w, and denote the sorted sequence by 01..... a,,, a_. (..41...... an. Here J denotes the number of items with weights above w(ay). J = 0, i.c. i_ has the highest weight, since the solution must contain at least one item, we choose the best single item as the solution (lines 3-4). If constraint and is the best permutation (lines 6-7). If J >> m, to meet the cardinality constraint,
S m, (a),... a,) satisfies the cardinality

---

Published as a conference paper at ICLR 2024
Algorithm 1: BestPerm: find argmax.e.A. f(A, w) and max f'A, u, w)
Input: Agrund A.8rounnd + [0, 11, A R.
Sort the items in Aground in descending order of and denote the sorted sequence by
ay...., O.J; 11,00,0000 o, Here denotes the number of items with weights above w(a ):
if J 0 then
argmax (E (ul(a))) (u(a)w(() + (1 u(a)) }}: Select the best single item
Shest + (a'). phest t u(a')w(a') = (1 (l(())))((a)
< J 4 m then
Shest f (a1..... a.):
Simply output (a1...... a.)
Fbest E i=l 11 (1- u(a;))u(())) + 11, (1 u(e,))m((a1:
if
J. then
[[] + (a.);
Select m best items from (a1...., a.)
F[J[[1] u(a,) (((a)))(aa))))))) + w(a)))
For any E Sli - and 0 - w(a i):
11
For any i [J] and -i+l m. F 00;
13
for i = - 1,J
2.....Idd
14
for k = 1,2, .... min(mn) min(m, do
15
if F [
(1=) 1]
then
Sti +[( Fli [[[
16
else
S - (a., SIi
1));
18
F[ikk] - u(a))u((a) - (1 u(a)) )) Fli +]]k 1]:
Sbest 4- [m]] pbest +- F[]][m]:
29
return pbbest Sbest,
21
need select m best items from (a1..... a.)) which maximize the objective value, i.e.,
max
f(aaj,..., a'm): u, w)
(a a()).....a.)
Eq. (3) is a challenging combinatorial optimization problem, and costs exponential computation com- plexity if one performs naive exhaustive search. To solve Eq. (3), we resort to dynamic programming. For any E [J] and & [min(mn Jn J 1}}, let ST]][]] and F[i][k] denote the optimal solution and optimal value of the problem ( of fA, w), have
f((a']..... ag),, u, w). Utilizing the structure
[[]][1] = u(a))w(ar) + (1 m(a)))u(a1);
F[][0]] = w(a
15i5J, 1 1I m,
F[] -0,
F[] = max
u(a;)w((a)) + (1 u(a) 1]jk 1]}, ISiSJ-1, < min (m, J - -
The idea of this dynamic programming is as follows. Consider that we want to select best items from ...)). If we put a; into solution, we need to further select A: best items from (0i+1.... ). In this case, we have [k]] u(a:)w((a, + =u(a)))F(a [] k 1]: Otherwise, we do not put 0; into the solution, we are just selecting lo best items from (a,+1:--. a.)), and then F[]]k]] Fl [[[k]. After computing this dynamic programming, output [[]][m]] and [[][m]] as the optimal solution and optimal value of Eq. (2) (lines 9-20), Below we formally state the correctness of BestPerm.
Lemma 2 (Correctness of Oracle BestPerm). Given any Aground [0, 1] and w Aground RR the permutation Sheat returned by algorithm BestPerm satisfies
f(Shee u. w) max (AA u, w).
AEA
BestPerm achieves O(Nm + N (og(N) computation complexity. This is dramatically better than the computation complexity of the naive exhaustive search, which is O(IA)) O(N)).

---

Published as a conference paper at ICLR 2024
Algorithm 2: CascadingVI
Input: 8, 8' := 17. L == log( KHSN ) For any k > 0 and E S, qt (s, a1) (s,a1) ==
and V (s) = V 1 == 0. Initialize n n' a) = n'' a) = 0 for any
(8.0) 1) E S x A.
for k = 1 ..... K do
for h = H, l,,.., do
for s S do for a E Agrend {aj] do
(*,)( + m ((aa)))) + n=.90,o] 1};
5L
(Fa(s,
4th (s) t (", a) + b4-9(s, a). (s, t (5, - (s,a):
for Agroadd do
BaPV (s. a) f
Var Nar
(+)))
8
(s,aa)
2V Srnhh (( h+s (0') 2 (69))1L
(t H):
SHL
(..F(
wh (s, (s, + (118,)) TVL + BA (s,a);
(s),, (s) <- BestPermm 18round (x, +), (s,
10
(x) t min(V/ HJ. A' + (s);
11
(I(s) + maxx_ !A' IT [1 (", ('))) (s, (()
11
(+(ss, L bhv (s, A())) 0):
for h 1,2..... do
Observe the current state s Take action A - n (s i 1; while é I m do
I/ Take policy n² and observe the trajectory
14
16
Observe if (1) is clicked or not. Update n² (s), (i) and (sh. (1) clicked then
17
18
Receive reward rs At)) and transition next state
$/41 p(115 (1)):
I&hh < Update n (s (i)) and g* (-1s A5()))
20
break while;
// Skip subsequent items
else
23
1+1:
24
m 1 then
Transition next state shit1 p(-1sh)aa); Update (s a.) and (-1sh, al);
No item was clicked
26
5 REGRET MINIMIZATION FOR CASCADING RL
In this section, we study cascading RI. with the regret minimization objective. Building upon oracle BestPerm, we propose an efficient algorithm CascadingVI, which is both computation and sample efficient and has a regret bound that nearly matches the lower bound.
5.1 ALGORITHM CascadingVI
Algorithm 2 describes CascadingVI. In each episode k, we construct the exploration bonus for the attraction probability bht and the exploration bonus for the expected future reward by.PV. Then, we calculate the optimistic attraction probability q² (s, a) and weight w a). by adding exploration bonuses for q(s, a) and p(-|s, a) V individually (lines 6 and 9). Here the weight x² (s, a) represents an optimistic estimate of the expected cumulative reward that can be obtained if item a is clicked in state Then, utilizing the monotonicity property of f(A, u, w) with respect the attraction
7

---

Published as a conference paper at ICLR 2024
probability u and weight w, invoke oracle BestPerm with q" (s.-) and ū (s. -) to efficiently compute the optimistic value function V (s) and its associated greedy policy (s) (line 10).
After obtaining policy n², we play episode k with n (lines 14-26). At each step E [H], we first observe the current state 5% and select the item list A = (s). Then, the environment (user) examines the items in AK and clicks the first attractive item. Once an item (i) is clicked, the agent receives a reward and transitions to sh+2 p-11s A (1)) skipping the subsequent items. If no item in A is clicked, the agent receives zero reward and transitions +h+1 p(-1s a ). In line 17, we increment the number of attraction observations n ( (i)) by 1, and update the empirical attraction probability q² (s (f). ) In lines 20 and 26, we increment the number of transition observations n (s A (or n (sh. a.)) by 1, and update the empirical transition distribution p (-1sh, (i)) (or 1º (-1sh, a1)) by incrementing the number of transitions to $/41 by 1 and keeping the number of transitions to other states unchanged.
If one naively applies classical RL algorithms (Azar al., 2012: Zanette & Brunskill, 2019) by treating each A E AA as an ordinary action, one will suffer dependency on |A| in the results. By contrast, CascadingVI only maintains the estimates of attraction and transition probabilities for each (s, a), and employs oracle BestPerm to directly compute (s), without enumerating over A E A. Therefore, CascadingVI avoids the dependency on |A| in computation and statistical complexities.
5.2 THEORETICAL GUARANTEE OF ALGORITIM CascadingVI
In regret analysis, we need to tackle several challenges: (i) how to guarantee the optimism of the output value by oracle BestPerm with the optimistic estimated inputs, and (ii) how to achieve the optimal regret bound when the problem degenerates to cascading bandits (Kveton et al., 2015; Vial et al., 2022). To handle these challenges, we prove the monotonicity property of f(A, u, w) with respect to the attraction probability u and weight w, leveraging the fact that the items in the optimal permutation are ranked in descending order of w. This monotonicity property ensures the optimism of the value function (s). ). In addition, we employ the variance-awareness of the exploration bonus (s, a). scaling as (s) q²t (s, a)). to save a factor of /m in the regret bound. This enables result match the optimal result for eascading bandits (Vial et al., 2022) in the degenerated case.
Theorem (Regret Upper Bound). With probability at least 1 8, the regret of algorithm CascadingVI is bounded by
Ô (HVHSNK
From Theorem 1, we see that the regret of CascadingVI depends only on the number of items N, instead of the number of item lists |A| O(NT)). This demonstrates the efficiency of our estimation scheme and exploration bonus design. When our problem degenerates to cascading bandits, i.e., S H 1, regret bound matches the optimal result for cascading bandits (Vial et al., 2022).
Lower bound and optimality. Recall from (Jaksch et al., 2010; Osband & Van Roy, 2016) that the lower bound for classic RL is 2(H KS Since cascading RL reduces to classic RL when q(s.a) a) 1 for any (s, a) E S x Aground (i.e., the user always clicks the first item), the lower bound Q(H /SHK) also holds for cascading RI.
Our regret bound matches the lower bound up factor of /Hl when ignoring logarithmic factors. Regarding this gap, one possibility is that it comes from our upper bound analysis. Specifically, we add exploration bonuses for q and p T individually, which leads a term (g+bb%9) V p -p V) in regret decomposition. Here the term b (Ø Db p TV) = O(Hb leads a Ö(HHKK)
regret, which causes the extra / H gap. A straightforward idea to avoid this is to regard 9 and p as an integrated transition distribution of A), and construct overall exploration bonus for (s, A). However, this strategy forces us to maintain the estimates for all A E AA and will incur a dependency on |A] in computation and statistical complexities. Another possibility behind the gap /H is that is needed in a tight lower bound for any polynomial-time algorithm for cascading RL. Therefore, how to close the gap / H while maintaining the computational efficiency remains open for future work.
8

---

Published as a conference paper at ICLR 2024
Cascadinge LOBS 20c Crecaliyeernes 9h Adadit 2000e o0.
Esscesngit 22
Cacoadigge 2700995 Eacasiggi 5205 d0s
Gaacediggh Orede Aeepti 33214
Cessalty/-russ Adaeht 80339
Adappin 93235 99,
The kurber of Canseess
The number Calodrex
Figure 1: Experiments for cascading RL on real-world data.
6 BEST POLICY IDENTIFICATION FOR CASCADING RL
Now we urrn to cascading RL with best policy identification. We propose an efficient algorithm CascadingBPI to find s-optimal policy. Here we mainly introduce the idea of CascadingBPI, and defer the detailed pseudo-code and description to Appendix D.1 due to space limit.
In CascadingBPI, we optimistically estimate q a) and p(- s, VV and add exploration bonuses for them individually. Then, we call the oracle BestPerm to compute the optimistic value function and hypothesized optimal policy. Furthermore, we construct an estimation error to bound the deviation between the optimistic value function and true value function. If this estimation error shrinks within e, we simply output the hypothesized optimal policy; Otherwise, we play an episode with this policy. In the following, we provide the sample complexity of CascadingBPI.
Theorem 2. With probability at least ó, algorithm CascadingBPI returns E-optimal policy, and the number of episodes used is bounded by Ō H log(}) +
H² HHSSN (log (3) + S)), where
5²
EVE
Ó() hides logarithmic factors with respect to N, H. S and
Theorem 2 reveals that the sample complexity of Cascading8PI is polynomial in problem parameters N, H, S and and independent of |.|. Regarding the optimality, since cascading RL reduces to classic RL when q(s, a) = 1 for all (s, a) E S x Arrund, existing lower bound for classic best policy identification Q H* log(s)) (Dann & Brunskill, 2015) also applies here. This corroborates that sa
CascadingBPI near-optimal up to factor of when & < 52
EXPERIMENTS
In this section, we present experimental results on a real-world dataset MovieLens (Harper & Konstan, 2015), which contains millions of ratings for movies by users. We set 0.005, K 100000, H 3, m 3, S 20, N E {10, 15, 20, 25} and |A| E {820, 2955, 7240, 14425]. We defer the detailed setup and more results Appendix A.
We compare our algorithm CascadingVI with three baselines, i.e., CascadingVI-OIre -Orrcle,, CascadingVI-Bonus and AdaptVI. Specifically, CascadingVI-Oraace replaces the efficient ora- ele BestPerm by naive exhaustive search. CascadingVI-Bomn ration bonus /4 by a variance-unaware bonus. AdaptVI adapts the classie RL algorithm (Zanette & Brunskill, 2019) to the combinatorial action space, which maintains the estimates for all (s, A). As shown in Figure 1, our algorithm CascadingVI achieves the lowest regret and a fast running time. CascadingVI-Drace much higher running time, which demonstrates the power of our oracle BestPerm computation. CascadingVI ViniinnnVV--uuus- attains similar running time as Cascadingll IgVI, but has worse regret. This corroborates the effectiveness of our variance-awan ciency. Vd suffers very high regret and running time, since it learns the information of all permutations independently and its statistical and computational complexities depend on [A].
replaces the variance-
explo-
has comparative regret performance to CascadingVI, but suffers
exploration bonus enhancing sample effi-
CONCLUSION
In this work, we formulate cascading RL framework, which generalizes the cascading bandit model to characterize the impacts of user states and state transition in applications such as recommendation systems. We design novel oracle BestPerm
efficiently identify the optimal item list under combinatorial action spaces. Building upon this oracle, we develop efficient algorithms Cas CascadingVI and CascadingBPI with near-optimal regret and sample complexity guarantees.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
The work of Yihan Du and R. Srikant is supported part by AFOSR Grant FA9550-24-1-0002, ONR Grant 10-0144991-2566, and NSF Grants CNS 23-12714, CNS 21-06801, CCF 19-34986, and CCF 22-07547.
REFERENCES
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen. On the sample complexity of reinforcement learning with generative model. In International Conference Machine Learning, 2012.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference Machine Learning, pp. 263-272. PMLR.
2017.
Dimitri P Bertsekas and David A Castanon. Rollout algorithms for stochastic scheduling problems. Journal of Heuristicx, 5:89-108, 1999.
Wang Chi Cheung, Vincent Tan, and Zixin Zhong. A thompson sampling algorithm for cascading bandits. In International Conference on Artificial Intelligence and Statistics, pp. 438 447. PMLR, 2019.
Richard Combes, Stefan Magureanu, Alexandre Proutiere, and Cyrille Laroche. Learning to rank: Re- gret lower bounds and efficient algorithms. In Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pp. 231-244, 2015.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed- hhrd-horizon reinforcement learning. Advances in Neural Information Processing Systems, pp. 2818-2826. 2015.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: uniform PAC bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pp. 5717-5727, 2017.
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems, 5(4):1-19,201
Thomas Jaksch, Ronald Ortner, and Peter Auer. Ncar-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? In Advances Neural Information Processing Systems, pp. 4868-4878, 2018.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In International Conference on Algorithmic Learning Theory, pp. 865-891. PMLR, 2021.
Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning to rank in the cascade model. In International Conference on Machine Learning, pp. 767-776.
PMLR, 2015.
Shuai Li and Shengyu Zhang. Online clustering of contextual cascading bandits, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In International Conference on Machine Learning, pp. 1245-1253, PMLR, 2016.
Jérémie Mary, Romaric Gaudel, and Philippe Preux. Bandits and recommender systems. In Machine Learning, Optimization, and Big Data: First International Workshop. MOD 2015, Taormina, Sicily, Italy, July 21-23, 2015, Revised Selected Papers 1, pp. 325-336. Springer, 2015.
Pierre Ménard, Omar Darwiche Domingues. Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In Interna- fional Conference Machine Learning, pp. 7599-7608. PMLR, 2021.
10

---

Published as a conference paper at ICLR 2024
Ian Osband and Benjamin Van Roy. On lower bounds for regret in reinforcement learning. arXiv preprint arXiv:1608.0277: 2016.
Sheldon M Ross, Introduction to stochastic dynamic programming. Academic press, 2014.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Liang Tang, Romer Rosales, Ajit Singh, and Deepak Agarwal. Automatic ad format selection via contextual bandits. In Proceedings of the ACM International Conference on Information & Knowledge Management, pp. 1587-1594, 2013.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-299) 1933.
Daniel Vial, Sujay Sanghavi, Sanjay Shakkottai, and R Srikant. Minimax regret for cascading bandits. In Advances Neural Information Processing Systems, volume 35, pp. 29126-299 121388.,, 2022.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo Weinberger. Inequalities for the (1 deviation of the empirical distribution. Hewlett-Packard Labs, Tech. Rep, 2003.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference Machine Learning, pp. 7304-7312. PMLR, 2019.
Zixin Zhong, Wang Chi Chueng, and Vincent YF Tan. Thompson sampling algorithms for cascading bandits. Journal of Machine Learning Research, 22(1):9915-9988) 2021.
Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton. Cascading bandits for sarge-scale recommendation problems. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pp. 835-844, AUAI Press, 2016.

---

Published as a conference paper at ICLR 2024
Reward
Sp
a E {ay (in- ayl: w.p. 0.9 (a, -y 0y-m) (a w.p.
E ayy w.p. 0.1
(ag ... ag-m) U(a)) w.p. 0.9
h=1
$1
$2
53
H
$2(H 1)-1
52(H
1)
Reward
Reward
Figure 2: The constructed cascading MDP synthetic data.
The Eppicees (a) Regret minimization, N =
(b) Regret minimization, N
(c) Best policy identification
Figure 3: Experiments for cascading RL synthetic data.
APPENDIX
A MORE EXPERIMENTS
In this section, describe the setup for the experiments real-world data (Figure 1), and present more experimental results on synthetic data (Figure 3).
A.I EXPERIMENTAL SETUP WITH REAL-WORLD DATA
In our experiments in Figure 1, we consider the real- wolld dataset MovieLens (Harper & Konstan, 2015), which is also used in prior cascading bandit works (Zong et al., 2016; Vial et al., 2022). This dataset contains 25 million ratings on a 5-star scale for 62000 movies by 162000 users. We regard item. For each user-movie pair, we scale the rating to
each user state, and each movie [0, and regard it as the attraction probability. The reward each user-movie pair is set to 1. For each user-movie pair which has rating no lower than 4.5 stars, set the transition probability 0.9 to this state (user) itself as 0.9, and that to other states (users) as 8-I- For each user-movie pair which has rating lower than 4.5 stars, set the transition probability to all states (users) as 1. We use subset of data from MovieLens, and set 5 0.005, K 100000, = 3, m 3, S= 20, N (10, 15, 20, 25) and [A| Σm= m!! (820, 2955, 7240, 14425).
12

---

Published as a conference paper at ICLR 2024
A.2 EXPERIMENTS ON SYNTHETIC DATA
For synthetic data, we consider cascading MDP with H layers, S = 2H 1 states and N items as shown in Figure 2: There is only an initial state sg in the first layer. For any S < H, there are good state 82(h-1) and bad state 82(h-1) in layer h. The reward function depends only states. All good states induce reward 1, and all bad states and the initial state give reward 0. The attraction probability for all state-item pairs is 2 Denote Aground {01,.... aN ). For any h [H], under good item a E faN-m+1.--.
aN }. the transition probabilities from each state layer to the good state and the bad state in layer h are 0.9 and 0.1, respectively. On the contrary, under bad item E {a....., aN-m) } U {a J. the transition probabilities from each state in layer h to the good state and the bad state in layer policy is to select good items (aN-m+1, mm aN) in all states.
are 0.1 and 0.9, respectively. Therefore, in this MDP, an optimal
We 8 0.005, H 5, S 9 and m runs. In the regret minimization setting, we let N E {4.8) and K = 10000, and show the average cumulative regrets and average running times (in the legend) across runs. the best policy identification setting, we set c 0.5 and N E {4, 5, 6, 7.8), and plot the average sample complexities and average running times across runs with 95% confidence intervals.
Each algorithm performed for 20 independent
Under the regret minimization objective, we compare our algorithm CascadingVI with AdaptVI. From Figures 3(a) and 3(b), one can see that CascadingVI achieves significantly lower regret and running time than AdaptVI, and this advantage becomes more clear N increases. This result demonstrates the efficiency of our computation oracle and estimation scheme.
Regarding the best policy identification objective, we compare our algorithm CascadingBPI with AdaptBPI, I, an adaptation of a classic best policy identification algorithm in (Ménard et al., 2021) to combinatorial actions. In Figure 3(c), N increases, the sample complexity and running time of AdaptBPI increase exponentially fast. By contrast, CascadingBPI has much lower sample complexity and running time, and enjoys mild growth rate as N increases. This matches our theoretical result that the sample and computation complexities of CascadingBPI are polynomial in N.
B PROOFS FOR ORACLE BestPerm
In this section, we present the proofs for oracle BestPerm.
First, we introduce two important lemmas which are used in the proof of Lemma 1.
Lemma 3 (Interchange by Descending Weights). For any Agromd + 10, 1}, A + IR and (a1...., ag, Og+1...., an) such that (a), ......... 0,41, .,.1, ag................... .., an), we have
n and w(ae) < w(ae+1), denoting A'
f(A, u, w) < f(A', w.)
Proof of Lemma 3. This proof uses similar idea the interchange argument (Bertsekas & Castanon, 1999; Ross, 2014). We have
f(A, w, w) ,(A', u. w)
t-1
II u(a))) (u(ar)w(as) + (1 =(a=))((a=)))(((++)))
(1 u(a;)) (u(a)=)))(0411) + (1 u((+:))u(aa)u(aa)))
I u m(a)))
/=1
(1 u(a))) u(ar)u(ae+1) (w((r) w(a++1))
13

---

Published as a conference paper at ICLR 2024
O.
Lemma 4 (Items behind Tp Do Not Matter). For any ordered subsets of fai......a J. A and A', such that A n A' 9, have
([A,aI,A)); [((A,a J,
Proof. Since u(a_) 1, we have
f((A, a1, A1), u, w)
|A| i-1
|A] II j=1
1 (1
(1 (1- m(A(i))) (il)aaaaaaa alal))((a)
i=1 1=1
IAI
i-1
(1
II (1-u(A'(1))) " u(A(()))((A(())
E=1
j=1
M
|
= Σ
1 1- ((AA))))((())))(((()))
II (1 m(A(i)) u(al)vo(a))
=1
= a()
Now prove Lemma 1.
For any X C Agrund, let Perm(X) denote the collection of permutations of the items X, and (X) E Perm(X) denote the permutation where items are sorted in descending order of
Proof of Lemma 1. First, we prove property (i) by contradiction.
Suppose that the best permutation A argmax AePmmx f(A, u, w) does not rank items in descending order of w. other words, there exist some ae, ae+1 such that we can write A (ai,..., (s+1,..., ((x)) and w(ae)= < w(a++1).
Then, using Lemma 3, we have that A' (a1..... a6+1, at...., x ) satisfies f(A', u, w) 2 f(A", u, w), which contradicts the supposition. Given any permutation in Perm(X), we can repeat- edly perform Lemma 3 to obtain better permutation bubble sort, until all items are ranked in descending order of w. Therefore, we obtain property (i).
Next, we prove property (ii).
For any u, w and disjoint X, C Aground \ {aj} such that w(a) > w(a_) for any a E X, we have
F(Dess(XX) (1 w) (2) (DDesW(X).
((D)ss(XUX)))a))) w),
Here in the right-hand side of equality (a), X' can be in any order, and inequality (b) uses property (i).
Furthermore, for any u, w and disjoint X, X' C Agmand {ri} such that w(a) > w(a1) for any E X, and w(a) < w(a1) for any E X', we have
((Desw(XX, X'), (a))),), w) (((Des((X) (eW))))))
[((Des(XX)) w),
where inequality (c) is due to property (i).
Next, we prove Lemma 2.
14

---

Published as a conference paper at ICLR 2024
Proof of Lemma 2. From Lemma (i), have that when fixing subset of A the best order of this subset is to rank items in descending order w. Thus, the problem of finding the best permutation in Eq. (2) reduces to finding the best subset, and then can just sort items in this subset by descending w to obtain the solution.
We sort the items in Aground in descending order of w, and denote the sorted sequence by aj.-..,a,, L, aJ+1---.,, ON- Here J denotes the number of items with weights above a1.
According to Lemma 1 (ii), we have that the best permutation only consists of items in d1..... a.- In other words, we should discard 0.+t,...., aN.
Case (i). If S S m, (ai...., .......))))))..........)) satisfies the cardinality constraint and the best permutation.
Case (ii). Otherwise, if J one regular item the solution.
have select single best item satisfy that there is least
Why do not select more items? We prove that including more items gives permutation by contradiction. Without loss of generality, consider a permutation with an additional item, i.e., (a, a', a where a, a' Agrouudy \ {ai) } and w(a), w(aa) w(a Using Lemma have f((a,d' al)ddaa),,,e))) u, w) f((a, a', =((aa, (1,, u, w).
In this case, the best permutation is the best single item argmax
a((a,a)), u,
Case (iii). If J > m. the problem reduces selecting m best items from ....... a.. For any i E [J] and & E [min[m, max of ((a.....)) f((a))..... u, w). From the structure of f(A, u, w), we have the follow- ing dynamic programming:
1}), let [[] denote the optimal value of the problem
[[J][1] u(a, u(a))w(aa) + u(a)))w((1),
F|] = w(a1),
1 J
F[][A] -0,
F[ max [F]++][A)]
u(a:)ur(a) (1 u(a.)) Fli 1][K- 1]), ISisJ- 1 < J
Then, F[]][m] gives the objective value of the best permutation.
Combining the above analysis, we have that BestPerm returns the best permutation, i.e.. f(Shest u. w, AaxAcA f(A, u, w).
C PROOFS FOR CASCADING RL WITH REGRET MINIMIZATION
In this section, we provide the proofs for cascading RL with the regret minimization objective.
C.I VALUE DIFFERENCE LEMMA FOR CASCADING MDP
We first give the value difference lemma for cascading MDP, which is useful for regret decomposition.
Lemma 5 (Cascading Value Difference Lemma), For any two cascading MDPs M'(S, Agrond A, m. H, ,'r)) and M"(S, Aground A,m, H, ,",,"", the difference in values under the same policy w satisfies
H
AA ΣI
(s) ( (s)
Σ
E
Eq
pM
d' (s.)) Ar(i)) (s. A(())
-
|d 1-1
Σ
d" A.G))) (s, (
15

---

Published as a conference paper at ICLR 2024
1A.
Σ
d'(s,,
A 1-1
T A1 A.(1)
Viti sn = An ma(SN)
Proof of Lemma 5. Let A == (s). We have
(i
|AI i-1
Σ - (s, (FM
TV771)
A 1-1
EI (s. (r((s)((i) + + p" ((s)) T V
A
|4|
Σ - (0
Σ
(1
==
=
A
100 Vi+1
d", (T (V/71 V4
A 1
A i-1
Σ II (s.
Σ
II -1 (1- (3))
A
Σ
II
(1 (10-o(.AA0)MM(s.A)000((...0..
[ (0010"/(ssA0""0"0000000000000
E
V4+1
+ Byg s/' [V (8++1) - (1)))))) = [e i-1 (00
=Ra"' x". Σ
All
Σ1
(s,, (406AAA)))))AAAAAA0))00000000000
(s,, (1
A 1-
E - A1o.AAA0)0000/AsA000000000000 v/5 s, A, = (sN)
16

---

Published as a conference paper at ICLR 2024
C.2 REGRET UPPER BOUND FOR ALGORITHM CascadingVI
Below we prove the regret upper bound for algorithm CascadingVI.
C.2.1 CONCENTRATION
For any > 0, 8 E S and a E A \\ {a let ( a) denote the number of times that the attraction of (s, a) observed up to episode In addition, for any k 0, s S and a A let ns a) denote the number of times that the transition of (s, a) is observed up to episode k.
Let event
9h (s, ()ssa)))oog n),4(8,0)
KHSA 8'
5 5 n
KHSA 8
8:= -s.aa) a(s,a)) 22
(
KHSA log 8'
(ss ("(s,))) V((s,a)(1 ((8,a))
521
n. a)
Vk E [K], ((s ES Broundd (ai3)
Lemma 6 (Concentration of Attractive Probability). It holds that
Pr 2 - 48'
Proof of Lemma 6. Using Bernstern's 's inequality and union bound over (s. E [KH, A E [K]
and (8.0) a) E S Aground we have that with probability 22',
g(s. a) ((s a)) log KHSA
log
KHSA 5'
(s a) a(s,a)) = 2
(4)
(s.
Moreover, applying Lemma I in (Zanette & Brunskill, 2019), we have that with probability 1 - 28',
log KHSA 8'
V a) 00 - - -((s.a)(1-qss.a)) s 2
(5)
n
Combining Eqs. (4) and (5), we obtain this lemma.
Let event
Fi= |10 p(-1,,a)) (p((lss))) Vi- $2/ Varg<p (V"+)(8')) log (KHSA)
H log n p (s,
KHSA
(s,
p( (o6lss,)(111 p(s' ((8 a)) log nA a)
KHSA
log
KHSA 8'
- s
n RP R a)
2S log
KHSA o' nt (s,
a1)) pp(-ss,)) s
(8)
Vk [K], [ V(s a) E ground
Lemma (Concentration of Transition Probability). holds that Pr [r -
Proof of Lemma 7. According to Bernstein's inequality and union bound over (s a) [KH) E [K] E [H] and (s, E x Agmand we obtain Eqs. (6) and (7). In addition. Eq. (8) follows from (Weissman et al., 2003) and Eq. (55) in (Zanette & Brunskill, 2019).
17

---

Published as a conference paper at ICLR 2024
Let event
KHSAA log
G :-
V Var (V"+z(5'))
Var (Vitz
S 2H1
6' ()
Ak E [K] 4A E V(s.a) E x Agrund
(9)
Lemma 8 (Concentration of Variance). It holds that
Pr 9 2 28'.
Furthermore, assume event Fng
Eng G holds. Then, for any [K], h E [H] and (s, a) E S Agrund if V.k (iti(1s)) 2 Vi++i(') 2 (s') for any E S, we have
Var (V
(5') (s') log KHSA
(b*())),)) p(-1s, a)) Vitt1 22
())
Bunpe [Viiti(s)) V viti(ss))²
log (KSAA)
5H log KHSA
+ 2
n).((s,a)
n p a)
Proof of Lemma 8. According Eq. (53) in (Zanette & Brunskill, 2019), we have
Pr 9 2 1 28'.
Moreover, assume event F ng holds. Then, for any E [K], h E [H] and (8,a) E x A h441 (5)) 2 (s') 2 v for any s' E S, we have
Vargnng (V / Varg (Vi+1 (+))
Varg (V& (s'))
( Varggaau (Vin+ (5'))
Varampps (Viti(s'))
- Vara'mp (Vrtz(5'))
( R Se [ Vh+ -
log (KHSA) 8 nAPP a)
+ 2H
(10)
where inequality (a) comes from Eqs. (48)-(52) (Zanette Brunskill, 2019). Plugging Eq. (10) into Eq. (6), we have
Var (V.h ( (s')) log (KHSA
(5+ ((1)))))pp((s a)) T Vn+tl S $2
- p(-1s,
(s,
Ernnpt (Vitt ub (
log KHHAA
5H log (KHSA) n P a)
+ 2
())
For any 1: > 0, h E i [m] and as) S x (AArouud \ {ait), let obserue.0 (s, a) denote the probability that the attraction of (x, a) is observed in the i-th position at step h of episode k. Let observe.q
Uk.
Ug
(s,a) a) = >m Uk,
oheerve. a) = DMI Dm observee (s, a) and us
U
obeerve (s, a).
For any & > 0, h [M]. i [m + and (s, E S Aground let observe,P a) denote the probability that the transition of (s, a) is observed (i.e., (s,a) is clicked) in the i-th posi-
18

---

Published as a conference paper at ICLR 2024
tion at step h of episode k. Let observe, (s, a) = Ei=t mm+1 pbserve.Pss, a) and Us k,,
observe. (s.
E Di=1 observe.P
Vi, (8, (8,a).
Lemma 9, For any > and h E [H,, we have
Σ
observe.
h
(s,a)E5x Awmand) (oo)
Proof.
For any k > 0, E [I]] 8 E S and A A, let (a,n(s, A) denote the probability that (s, A) visited at step hi in episode k.
It holds that
Σ
observe. (s,a)g(s,a)
k,
(s,0)ESx x A {
m observe, obaerve: (5.a)g(s.a)
Σ
(s,0)ESx Apound
(al]
m
i-1 II (L (ss ((M)
Σ
WkA (s, A)
(s,a)ESx Amonnd
{ai]
AEA A(1)=a
Σ
Pr[(s, is clicked in the i-th position at step h of episode k.]
(e.0) Awondd
}
Σ
Pr((s, a) is clicked at step l of episode k]
<1.
Let event
HSA 8'
:= n (s,
2
Uk
obserne, (s, a) - H log
2
vk ((s S (Asmand {ai));
HSA
n as)
a)
2
Σ
UK!
(haerve:P(ssaa)
H log
.k ((s,)) E A ground
k'ck
Lemma 10. holds that
Pr [C] 2 1 28'
Proof of Lemma 10. This lemma can be obtained by Lemma F.4 in (Dann al., 2017).
C.2.2 VISITATION
For any l: > O, we define the following two sets:
HSN
B = (s) E S x gronnd (ail)
Σ
observe, (s, 2
H log
+ H J.
8
HSN 8'
B (s) E
ground
observe k
(s, (( H log
H
B and Be stand for the sets of state-item pairs whose attraction and transition are sufficiently observed in expectation up to episode k. respectively.
19

---

Published as a conference paper at ICLR 2024
Lemma 11 (Sufficient Visitation). Assume that event K. holds. Then, if (s, E Bb we have
n ( a) 2
1
observe.g
(s, (s,a).
k
If (s,0) E Bg, we have
n R (8,
observe.p
(8, a).
Kich
Proof of Lemma 11. If (8,0) E Bg. we have
HSA 8'
(s, a) 2 2
Σ
UK
observe.g
(s,a) 1 log
kick
Σ
k
observe.
(s,
Σ Wec
Uk
a (8,a)
H log
HSA
8'
kich
observeeg (s,, a) H
Uk
Mick
Σ
observe. (s, +
observe (8, a)
Uk'
Mick
Σ
observe,
(s,
kick
where inequality (a) is due to the definition of B
By similar analysis, we can also obtain the second inequality in this lemma.
Lemma 12 (Minimal Regret). It holds that
HSN
observe,g
(s, SHHSAlgg
UKA
(s
K
HSN 8'
Σ>
Σ
observe.p (s. & &8HSAlog k
Jimn h= (5,a) BY
Proof of Lemma 12. We have
K
K
H
observe:
(s,0)
Σ
ΣΣ
abserve.g
(s) (o,,a)(((s,))) ((s,a) & B.
kkh
(
(e.0)ESx x Apwnn) {ait
k= h=1
K
Σ
observer
(s. as) ((s,a) $ B
(x,0)ESx. Awoudd fai A=
A=1
Σ
4H log
HSN 8'
+ 4H
(sammS).Apmmdl Apond) Hai
HSN 8'
4HSAlog
+ 4HSA
HSN 8'
< SHSAlog
where inequality (a) uses the definition of B
The second inequality in this lemma can be obtained by applying similar analysis.
20

---

Published as a conference paper at ICLR 2024
Lemma 13 (Visitation Ratio). It holds that
K
(8,
(s.00) 1 &o (KH),
Ru Ruml (S
K
H
observe..Pe khh (s,
- 85A (KH).
k= ==1=11 (B
Proof of Lemma 13. We have
K
H
observe.g
(8,
K
U g
UR
(s,
n (s,,a
h= (s
k= (s,a)E
K
abserve,
(s,a) ((8, a) E Bi
n (s,
k= (e,a) A
Hai
K
Uk observei
(8, I [((5aa E B observe (8, uk
4
Σ
Evsc
(s.a) Apont {ai] km
8SA log (KH),
where inequality (a) comes from Lemma 13 in (Zanette & Brunskill, 2019).
Using similar analysis, we can also obtain the second inequality in this lemma.
C.2.3 OPTIMISM AND PESSIMISM
Let L : ::og KHSA) For any k > 0, h E [H] and s S, define
6 (s, a) = min 2 (* (5,)))
a))
5L
a 1 Va Aground \ {aLl,
bc (8, =0;
Exiaga (V)+ L Lotr( L
Var (8"= n).P(,,)) a)
BADV (s, mimi 2/
+21
nk.
5HL
+ (s,
H. Va E Agronnd
For any 4: > 0, E [H] E and A E A, we define
i-1
(%(,, A) min
EI[ (()))
==
(r(s, A(i) + 1 (-18, A(i)) T/A + bB (s. A(i))) H
(((s)) = argmax Øh (s. A),
AEA
(i)( = (h(s, (()))
V (s) = O,
21

---

Published as a conference paper at ICLR 2024
[AI
A) max II (0
+ (-1s, A(1) (1))) - Bhioy (s. ((i)) of.
(s)) 2% (s, (s)), vh (s) = O.
We first prove the monotonicity of J. which will be used in the proof of optimism.
Lemma 14 (Monotonicity of f). For any A = (aI..... an. aT) E A. w Agrand + R and ú, Aground + [0, 1] such that 1 S n S m, w(a1) 2 2 w(an) 2 w(a1) and ū(a) 2 u(a)for
any E A, we have
f(A, u. w) 2 f(A, w.
Proof of Lemma 14. In the following, we make the convention an+1 aO and prove [(aa....., ak), w) 2 f((a).... (2),, w) for k = 1,2, 1 by induction.
Then, suffices to prove that for k 1,2, ..,, n 1.
1-1
& 1-1
EI (1 (ls))(()))()a)u(
Σ II u(()))((asw(aa)
2 (1 mai)) )) (1 ū(an (()==)))(((aa)) u(ax))w(ax)
+1 u(a1)) ... a (aa 2())===))(((((())) - ((a===))((1 ((a)))aa))
(a((1) u(a1))(1 u(a))) ... (1 u(ax))w((xx)
(11)
since the right-hand side of the above equation is nonnegative.
First, for 1, we have
a(a1)w(a1) u(a1)w((s (ū(a1) uu(1)) w(a1);
and thus Eq. (11) holds.
Then, for any S & n, supposing that Eq. (11) holds for we prove that it also holds for k
k+1-1
k+1 i-1
EI u(a, (()))))(())
Σ II (1
u(as)))(as)uo(a))
=1
==
1-1
& i-1
ΣI[ (1 u(a,))a(a,))ut
EII u(a,)))(a))wa(a))
2
i=1 ==
=1
+ +(1- ((a))) ... (1-
...
Term
(12)
Here, we have
Term D (1 ... ((l=
(1 ū(a1)) ... a(ax)) ((a)))))((+))))(a
+ (1 ū(a1)) ... ((a))))((++)))()))
(1 u(a1)) ... (ll--(aa)((aaaaa) ((4))))((=+)))((())))
(1 ū(ar)) ... u(ax)) (ū((x+1) u((k+1)) w(ax+1)
+ [1 [11-a(0)) ... ú((x)) - (1- u(a1)) ... (1 - u(aw)) (((x+1)((0++)))
-(1-w(a))
= (1 ū(a1)) ... -1- --m(ax)) (a(a++1) - u(ax+1)) w((++1)
+ (1 ū(ai)) ... u(ax))
22

---

Published as a conference paper at ICLR 2024
(1 a(a1)) .. (1 ((1 u(ax))
+ (1 u(ai)) .. u(ax-1)(1 - u(((a)))
(1 u(ai)) ... (1 u(ax)) u(ax+1)w((xx11)
(1 a(ai))
............ ...
u(ax)) (ū(ax+1) - u(ax+1))))))))))))))))(())))(v w(ax+1)
+ (1 m(a1)).......)...))))))))))) ..................... 1(a (u(a)) -(ax))(())))))) (00)
+ (1 ((.))))..... ū(a=-1) - (1 u(())) (1 u(ax=1)))
(1 u(ax)) ((a=)))((
(1 (..)))....( (1 u((x)) (ū((x+1) u(ax+1)) w(ax+1)
+ (1 u(a1)).... ... i(ak=1)(u(ax)
(ax+1)
(1 u(a1)) ...(1 ū(ak=2)
a((x=11))( 1) u((a)))((++)))0(a))
(u(a1) - ū(ai (1-()))((a(aa)))) ... 11-1111lljpp ((
(13)
Plugging Eq. (13) and the induction hypothesis into Eq. (12), have
k+1--1
k+1i-1
E EI {(a)))((a))((a)
EII =(aa))((a))a())
2 (1 - i(ai)) ... ū((x)) (a((x+1) - u((x+1)) w((a+1)
+ - ū(ai)) ...
a(a; (l ())(((s))))))) u(a=)) (u(ax)) u u(ax+1)w(aa)))
+(1 - ū(a1)) ... =((x=2)((((a-=1)
u(ax)) (waxx) - u(ax+))u((a+2))
+...
+ (m(ai) - - u(o))
u(ax))
(((x))))(((a)))))))))))))))))( w(ax) u(as-1a)aaaaaa
2 (1 - (.loi)))....iii
... (1- -(xx
+ (1 ū(a1)) ... ((1-((a)))(((a)) u(ax))(( ((ax+1))ww(ax=)
+ (1 u(a1)) ... (1 ū(a 2) (ū((x=))) u(ax ul u(ax))(1 - u((x+)))w(ar44)
+ (ū(a1) - u((n)))) (1 u(a2)) ... - u1ax))(1 (()(+))))()
Therefore, Eq. (11) holds for + 1, and we complete the proof.
Now we prove the optimism of (s) and pessimism of Vi (s). Lemma 15 (Optimism and Pessimism). Assume that event E E n holds. Then, for any & E [K]. E [H] and s E S.
(x) 2 Vi(() (s).
In addition, for any k E [K], h E [M] and (s, S Agound it holds that
Vargrape
log (s,
(KHAA 6
(-1s,)) p(-1s, a)) Vi+1 2
log ( Edinge (Vity(6') (8)))))))
KHHAA 6'
5H log KHSA
+ +
(s
n p (8, a)
Proof of Lemma 15. We prove this lemma by induction.
For any le E [K] and S. it holds that V (
V++ Vb (#+1(s) (5) 0.
23

---

Published as a conference paper at ICLR 2024
First, prove optimism. For any & E [K] and h [H] if (s) = H. then (s) 2 (5)
trivially holds. Otherwise, supposing V 1 2 (s') 2 Vh+ (s') for any s' S, we have
V (s) - (h()) 2 A*)
(s)
= Σ I (T) (10 (1000 V
I 1-1
+ +b (8, A" A1))
ΣII (10 -I (1 Vi
+ P (s. A (1) (0))
i-
- ( r(s.AA TVi+z
EI j=1
al r(s, A(()) + A'()) T
A*)
(s).
Here A" argmax A (1 g(8, A()))m) A()))(((s, A()) + T
Inequality (a) uses the induction hypothesis. Inequality (b) applies the second statement of Lemma 8 with the induction hypothesis. Inequality (c) follows from Lemma 14 and the fact that the optimal permutation A satisfies that the items in A are ranked in descending order of w(a) == r(s,a) a)-1s;a) Vi++
Next, we prove pessimism. For any [K] and E [M]] if (s) O, then (i(ss S (s) trivially holds. Otherwise, supposing / (8') 2 (s') 2 Vh+1 (s') for any s' S, we have
|4| ا-ع
(s, = I
1=
(1(ss kh+ -bPP (APV(ss A(i))
+
M 1-1
ΣI
(s, (4)) A())
==1==1
(r(s, A(1) (1 A(1) Vi+1 BA A())))
g(s ((i))) A(1) (r(s, A(i) p(11s, A(i)) A(i)) (V
Q (s, A),
where inequality (a) uses the induction hypothesis.
Then, we have
(+) = - xx())) s (()) < @7(s, = Vs))s),
which completes the proof of the first statement.
Combining the first statement and Lemma 8, we obtain the second statement.
24

---

Published as a conference paper at ICLR 2024
C.2.4 SECOND ORDER TERM
Lemma 16 (Gap between Optimism and Pessimism). For any k 0, h E [H]] and S,
41-1i-1
66H
(5) - vh())
Σ
B
Σ
(1- (st, Ar(i)))
Vn Ae(i))
t=h
i-
20HLVS
Σ
II (s As))) A+ii)
8h 8, 3
(s,
Proof of Lemma 16. Let A' = (s). Recall that
1A i-1
(s)
(1 (()) A()))
=1
(r(s, (10) ((1)) T + Bhev (()))
and
A i-1
(+) 2
(1 - (1-
F=1
(r(s,
V BRDV (s, A'(1))
Then, we have
A4 1-1
-
-
Σ (1- ((,-"(s,,A(i))) (20(s.)(0))
=1
A(i)
26 A())) (fsss V bR. A(()))
(s, (0'(1s,
Vi+1 bhoV (,, bbo
EII
(1. (1 T
- A'ii) T Vh+ + 28 (s. (s,
A
i-1
- ())
5L
-6H
(s, 2v
(s)
n (
j=1
[ 11
(2/)
Varg-ap (Vi (8)) L
II
o (())))((sAA
n (8, A'ii)
==
Egnggh (Vir)(')) - 2b 2h+1(61))
L
5HL n (s, A'(i))
+21
(8, A()))
[A 1-11
=1
(1s, - -(l,)) (V/.1- VVh1--V4 Vi+i)) -Vh+1)
( A'()) (V vhrt))
==
25

---

Published as a conference paper at ICLR 2024
-
Σ I -1 (s,A'() (2
/ n).9(s,a)
a(s, ((,
9L n)
Z6H
W| 1-1 (1- A(1))
18HL
(s..(ss,A(i)) A'(i))
2HvSL
(s
Vn A'(1)
[I (Vi+1- vh+t)
=1
M1-1
66HVL
Σ
I (1-7(a,
(s A'())
i-1
20HLVS
(1-
(s,
II (LAAA (Vi+i vh+t)
==
AI--;
66HVL
Σ II of (sc. A,OI)) (nt Ac(i))
t=h
1=1
[d 1-1
20HLVS
( (0))))(ss A())
8h = 8, π
Vn ((()))
where inequality (a) is due to Eq. (8).
Lemma (Cumulative Gap between Optimism and Pessimism). holds that
K H
Σ
observe.P
(8, p(-1s,)) (Vi+1 VD+11 S 1152192(m 5
Uhh
1= h=1 (sa)ESxAmma Awound
Proof of Lemma 17. For any l: > 0, h [H] and S, let (s))(s) denote the probability that state is visited at step h in episode k.
We have
K
H
ΣΣ
Σ
abserve.P khh
(s, ((-a)))(-ls,a)) (Vitz vh+t))
Am Aml
A
K
H
Σ
observe. Uk
18, a) Σ ((s'(s, (1it - k
k= h= (Ma))SSx Anound
3'ES
K
Σ
Σ
- kh+)(6/)2 P (s', (viL
Uk
k= h= (xx))Exx Agound s'ES
K
Σ
(k')+ (V2t1(6)) - Vb Vhh (5')
kml hmll NES
K H
b (
- (8h+1) 27
Ban
Am hml
26

---

Published as a conference paper at ICLR 2024
K
H
(sN) - v((ON))
21
B Ban
A=
h=1
K
H
66H VL
Σ Es
Σ
9" (st, Ac(i))
Vntialoss Ac(i))
==1
Ad 1-1
1)
(s, (()))(())())) (,(1)
20HLVS
5h = 8, x4
V (st, Ac(i))
K
H
H
66H VL
E wat
Σ
Σ
II (1- ((s,..)) Vnhig(oe, Ar(i))
I=1
Ad
20HLVS
= = m 1)
EII ((8 Acl))))((s Ac(i))
VnhiP (Se, Ac(i))
j1
(9)
H
K H
E
E
Σ
H
E (inAint
(
[Al--16-1
Σ
II
(1
66H
(st. Arli))
i=1
2 V Scc Ar(i))
20HLVS
Σ II
q(s (
s,
(
H
A1-18
4356H
<2 1)H
E
Σ I (86, A,O)))
( A1)
1=1
Ad 1
400
EI
(1
a(s ((H, A((1)
n² B. (s,, (i))
K
H
(s, a) 4356H² T. (s, a)
-2(m + 2)
Σ
observe,
k
k=1h=1
(x,O) (AAD)SX(AAMaa (Auoud) +)
400H3
obseevee (8,0)
UKA
(s.
(5.a)E5x Armend
(0)
HSN 8'
))
2m + 1)H2. (8SN SHSN log
(4866H""4
<152192(m + S
Here inequality (a) uses Lemma 16. Inequalities (b) and (d) are due to the Schwwaz incquality. Inequality (c) comes from Jensen's 's inequality. Incquality (c) follows from Lemmas 12 and 13. 0
C.2.5 PROOF OF THEOREM
Proof of Theorem I. Recall that 8' := 1 148' =
6 14.
Combining Lemmas 6-10, we have Pr|E FriEnnngnk 2
In the following, assume that event E n Fng O K. holds, and then prove the regret upper bound.
K
R(K) Σ
(VT (o1))
K
< Σ
(s+)) - (str
k=
27

---

Published as a conference paper at ICLR 2024
K
AA i-1
E
(1
(sh. (00 An(1))
Ax
i-1
Σ
II (shh A00
A
g (,()))) An(1) (16h,,, An(i)) V/+1 + BA (oh, An)))))
A
(sh, Au (())))(((,,AAA()))(((()))))))))) An()) Th+t1 (V)
5=
K H E
AA 1-1
2
Σ
II (1
Ax)))
kml Aml
==1
EII (sa, An(i))) (I(Sn, (n)) + (. An))))
(1om,, An(1)) vht B Ax))))
i-1i-1
EI (sh, An As0 An(i)) Vh+t
K H
AC0 An()))
j=1
M
i-1
(sh, (s)))((((nn An(1)) (100,, An(ii) T + B An(i))
AAA i-1
p(11sh, An (1)) T/t + 4H
II g(sh, Ax An(i))
K
H
|
E
6H Σ
((sh, (s. An
A
(0n, An())))((nn An(i))( (Sh, An(())
EI Aln) (Hsh,, - An())) Vi+ta
Adk-1
EI ((sn, AnG)))((ss An()) (1s), (A) - Vitti)
1=1==1
K
E
6H
observe. (s,
(A) ((1))
Σ
observe Tki,i
(s,a)b+ (s, (s,a)
observe U.hs
(8,a) (6* (1,,,) p(-1s,a)) Vi+
Amm
28

---

Published as a conference paper at ICLR 2024
observe. kk,ha
(s, (s, (1*,))) - p(11s,a) (Vh+1 - Viri)
(x
K
H
Σ
observe, R G ( (3,4)6*:(s5c))
k= h= (8
obbserve.p
(s, (s,a)bk.vVss (s,a)
(s pbserve.P "kh
(s, a) (ft -((1,a) Vi+1
observe
P (s, a) (p* (118,a) - p() T (Vit2 Viita)
+ k.
6H
khh
observe 4 (8, (), = 3H
OdserveiP(ss
1= 1 h= (5.0)g
R= Am (5.0)
Σ
6H observe,g (s,a)(+((ssa))
k.
(e
K Σ
ΣE
observe.
(s, (),,)bbiiV( (5,a)
(s
observee khh
(s, a) (p (11s,a) - p(-18,))) -((1,a))p((1)))))
Vi+i
(s, a) (p (-1s.a) p()ss,)) (V/+1 Vitta) SNH k
observe.
(14)
where inequality (a) due to that for any and E S, (8, = 0, and inequality (b) uses Lemma 12.
bound the four terms on the right-hand side the above inequality as follows.
(i) Term 1:
H
6H
UgA
observeill
(s.
(s)))
k= 1=1 (e
K H
(s (),
5L ( a)
6H
observe.4 khh
2
(
1=1 h=1 (B
K
((s a(s,a))L (s,
9L n a)
6H
observe,g kk
2
Jm
Juml
(
K ΣΣ
observa.g (8,
12HVL
Σ
obeervee ( (s,
Uhh (
(M.))BB
k=1 (c.))
VL VKH VSSNlog (KH)
< ASHL.KHSN.
where inequality (a) is due to Lemma
(ii) Term 2:
Σ
observe. (s, (s),)) (s)
Uk
1= h=l (s
29

---

Published as a conference paper at ICLR 2024
Var gaph (+4)
L E
observe, (8, (,, (2V
(8, ())
(s,0)EB
(hi (Vitz(0') - 1/ (31)
Beingge
L
5HI. ps a)
+
(),)(s,a)
K
H
(8,a) (8, RRh (s,
observee
K
H
$2VT.
Σ
observe-P (8, a) Var rarh h+ (14)
==1k1l
(
k=1k=1 (s
K
H
observe.P (etnerve.P(ssa)) (8,
+ 2VT..
UkAh ())
1=11
(s
K
H
(s, as)-)p(-)). (V)t)(0)--Vttn - khhh
observe.
A= (8.0)EBB
K
ΣΣ
Σ
alserve-P U
(8.00((((1..)))((((B1_) a() ( (
V (0))
- P (8,
1=1=1
(
K H
55H
Σ
kkd
(s)
1= (S
S2VL. V 8SN log log (KH) HVKH
+ +VVL. VSN log (KH) 11121922 + 1)
VH 111HHSSNN2 / (m + 1)HL) 5HL 8SN log (KH)
SSHLWKHSN - 3428H ((m 1)HST.
(iii) Term 3:
K
Σ
abserve.p kkh
(s, a) (f*())a, p()1,,a)) Vi+t
11 (
K H
Var (Vi+)(s')) (s, a)
-2
observe
(s, (s k
Am Aml (
K
observe.P (s, UR (s,
HL
1= 1=1 (s,a)EB
K
observe. (s,a) kk ())
H ΣΣ
<2VT.
observe. (s, /a (Vizi (8))
Ukh
k=
(L
k= h=1n=1(s.ajEBB
observe (s, k
nk.P(s,,) a)
<2VL. 8SN log (KH)- HVKH HL 8SN log (KH)
S8HLVKHSN + 8HSNL2.
30

---

Published as a conference paper at ICLR 2024
(iv) Term 4:
observe,p k
(s. a) (1' p(-1s,aa) _ (Vi+i Vi+t)
1= Amm Rf
(a)
K
H
observe.p 1 (s, a) E k,h
p(6'11,, a) - w))L
[V/+a(6') - vx++
(s)
1= 1=1 (
HL
(s,
p(
L
observe, K
(8,a) E
k= h= (B
observe.P (s) Rkk (.,
1= (s,a)B
K H
s)
observe, UKh
(s,a)
nt. (V (V/42(8") (8)))
k= h= (s
observe. (8, kh (
HL
Σ
(B
p(-1s,)T (V/i1 Vi+t)
ST.
obeerve k
(s.
(s,
k= 1=11 (B
K 11
PobsereeP (s, RR (8,
+ +HL
Σ
k= k= (B,))BB)
K
H
observe k,ds (s,
SVSL
(s.
A= 1=11 (B
K
H
Σ
observe. kKh
(8,a) p(-1s,)) T)T (Vht1 - Viit1)²
k=1
(B
Pb (s,
k
HL
(s,
(L,))BB
SVSL. V8SN log (KH) / 112112 + S + HL 8SN log (KH)
NI (m + 11HH 8HSNL2
$1112H 52 NT.2 (m 1) where inequality (a) follows from Eq. (7).
Plugging the above four terms into Eq. (14), we obtain
R(K) 48HL + 8HL SHLVKHSN KHSN 3428H /22H
KHHL &HHSNI2 1112H 11 +
=Ö(UKKHSN)
31

---

Published as a conference paper at ICLR 2024
D ALGORITHM AND PROOFS FOR CASCADING RL WITH BEST POLICY IDENTIFICATION
In this section, we present algorithm CascadingBPI and proofs for cascading RI. with the best policy identification objective.
D.1 ALGORITHM CascadingBPI
Algorithm 3: CascadingBPI
Input: E, 8, 8' $ For any E (0, 1) and > 0, L (K, == log( HSN log(8e(n + 1))
and [KK n) log( MSN x
(0og(8((n-.) 1)). For any k > 0 and S,
(s = -s a1) = and V (1) = V (s) == 0. Initialize
12 (s, a) = =n'-P(s,a) a) == 0 for any (s.a) E S A.
for k =
do
for h = -I........
do
for s E do for a E Agroand {ai } do
1}: (s, + (s) + (s, a). (8, g" (s, (s.
(s,(s,))) min(41 (1 (8'.
(i.((s,a)
(s,aa
for a E Aground do
P (s, t min(4y
Var / (VL, (ha(()
160 M] (k.((aaa)
+
2 (1s, T 1h H):
(s,a) - (8, + i a) h+1 + BAP (s,u);
T
(s),, (s) BestPerm Agound _ +), (s,-)))
(s) < mVn H). A' (s);
(x(s) + max i= I1 (1- Aii)) (s. +
(())((((sss) +
(*((),AA())) V - (s, 0):
(s) + min ( 14
(s,
13
(') PV (s, + A G ()+))) H);
(x)) <e then L return *
14
15
// Estimation error small enough
for h 1,2, ........ H do
Observe the current state */: Take action A = क (s) t- i while é I m do Observe if (t) is clicked or not. Update n² ( (1) and A (i) clicked then
// Take policy x and observe the trajectory
17
19
20
21
Receive reward r(sk, At)) and transition next state
sh+1 ~ pl-1st (i)):
Ie < Update n² ( (1) and 5* (-1s), A3(1));
23
break while;
// Skip subsequent items
else
26
1+
27
i m + then
28
Transition next state stit p(-lsshaa); Update (s an) and (-1st;
No item was clicked
29
32

---

Published as a conference paper at ICLR 2024
Algorithm 3 gives the pseudo-code of CascadingBPI. Similar to CascadingVI, in each episode, estimates the attraction and transition for each item independently. and calculates the optimistic attrac- tion probability (s, a) and weight (s, a) using exploration bonuses. Here wt (s, a) represents the optimistic cumulative reward that can be received ítem a clicked in state 8. Then, we call the oracle BestPerm compute the maximum optimistic value V% and its greedy poliey * (s). Furthermore, we build estimation error (s) which upper bounds the difference between (y)(s and Vi (s) with high confidence. If G (s) shrinks within the accuracy parameter e, we output the policy x². Otherwise, we play episode with policy n², and update the estimates attraction and transition for the clicked item and the items prior it.
Employing the efficient oracle BestPerm, CascadingBP) only maintains the estimated attraction and transition probabilities for each a E Agroand, instead of calculating 0% (s, A) for each A A as in naive adaption of existing RL algorithms (Kaufmann et al., 2021; Ménard et al., 2021). Therefore, CascadingBPI achieves a superior computation cost that only depends on N, rather than [A].
D.2 SAMPLE COMPLEXITY FOR ALGORITHM CascadingBPI
In the following, we prove the sample complexity for algorithm CascadingBPI.
D.2.1 CONCENTRATION
For any x E (0,1) and n > 0, let L(K,n) = log( HSN + Slog(8e(( + 1)) and I. [M( =
log( HSN + log(Se(n + 1)).
Let event
(s, - [(s SAp (1s -M(s00(10(s.0))1(011 ((8
15L"
L
()
(s.(ss
-f ()) - Vg((s)) - ((s,a))
(-(8kk)
S $41 (
(15)
Vk 0, vh [I, ESx A )
Lemma 18 (Concentration of Attractive Probability). It holds that Pr [r 2 1 45'
Proof of Lemma 18. Using a similar analysis as that for Lemma and a union bound over 1...., 0C, have that event L holds with probability 48'.
Let event
L(8',
M
KL (p* (11s,)))lp((1sssa)) -
(s,
Varsow (Vinn(')) L- (8),k)
(8', (8),)) (s, a)
(1*())))) - a)) (((1s))))
Vi+t1 22
(8,
Vk 0, vh E [MI as, E x Aground
Lemma 19 (Concentration of Transition Probability). It holds that
[M[M] 2 1 - 35'. Furthermore, if event L e M holds, we have that for any 0. h E [H] and (s, a) E S x Agmand
Var moth (V (V++ (s')) L (8' 1(H
(p (1)s,a)) p(-1s,a)) T Vitll S4V
()
(s,
33

---

Published as a conference paper at ICLR 2024
2 +
H 0 (1,,a)T (Vit1 -Kitt)
Proof of Lemma 19. Following Lemma 3 in (Ménard et al., 2021), we have Pr [M[M] 2 38'
Using Eq. (22) and (23) in Lemma 22, have
L' (" 1 a)
Var (Vi+1 (+')
L. (8' ls) ()
(0) k=)
2Vrr.'pp (V/41 (6))
+
(), a))
(8 k) (s,
L L* k) (s
/Varg' (V/+2(01)
+ (1s,o)) (V
-Vit1)
2H k) (s, a)
18)
/Varg/ (Vh+) (8) k))
1 (1 (V/+, vh+ta)
(8',)
(s,
+
(s)
2H K) (s)
(8) (s
+ 11 0 a) (vh+1 - -hhtt) + 6H L(8,K)
221 Var.- (V (s'))
p
where inequality (a) uses the induction hypothesis of Lemma 15. Thus, we have
(D*()1s, - -p(-ls,a)) Vi- <4 Varg'=B* (Vhtz (0()',k)
(s,
+ / - (-1s,a) (Vi4=1 - -Vita) +
15H 15'22 k (8, a)
D.2.2 OPTIMISM AND ESTIMATION ERROR
For any to > 0, h [H] and S, define
(1,)() = min { {1V
gh (s. (1 (),,
18'' k:) (s,
(s)
Va E A fail.
(49(s,
Vara (V (V") (8) 15H
bePV BAPV(s,,)) (s, = min {
nt.p(s,a)
(s,
+ 7 p* (+1s,aTT (Vitz - -Vi+ta) H. j. Va e A ground
34

---

Published as a conference paper at ICLR 2024
For any & > h E [H] E S and A A, we define
IAI i-1
(h( = min
EI - (s.A6)))((
==
(r(s, A(i) + (1s, A(1))VV/++ b (0, (c.)),
(6) = argmax (h, A),
AEA
(s) = (s))),
V V#+1 (s) O,
IAI 1-1
2 (s, A) = max
==
A(0) A(1) - -b (8, A(i)) of.
(s) = (s, (s)))
V H+1 (8) = O,
Gh A) Σ II (1 (s, A(i))) 6H min {
(-1
{&v
gh ())))))(11 ((),,
n*.(s,))
;=1
(6' k)
+ (x, (min {8)
Varginpt (Vit (8')) L (* k)
n a)
(s,
30'2L(8', k)
11 (-1s,,, ( G 2H + (+1s,)) Gh++1 (
()
Gh(ss = (s.
G5) = O.
Lemma 20 (Optimism). Assume that event C n M holds. Then, for any k > 0, E [H] and s E S,
(s) 2 (s). (x)
Proof of Lemma 20. By similar analysis that for Lemma 15 with different definitions of (s, a), b. (s, a) and Lemmas 18, 19, we obtain this lemma.
Lemma 21 (Estimation Error). Assume that event K. n C holds. Then, with probability at least 1 - 8, for any k > 0, h E [H] and s S,
Vi(()) min min (s), VA (s)) s G+)
Proof of Lemma 21. For any k 0 and
S. it trivially holds that V
m (//++((3))) (s), V (s)} < (s).
For any k > 0, h E [H] and (s. A) E S A. if (s A) H. then it trivially holds that @h (s, A) - m h+ (s. A), Q (s, A)] s G (8, A).
Otherwise, supposing (s) min (8), V (8)) < 1 we first prove (8 A)
(s, G (s. @h(ss, A) 27 A)
35

---

Published as a conference paper at ICLR 2024
A 1-1
EI (1 - (01 + (s,
(r(s, A()) A(1) + A()))
A i-1
Σ -1- (s)
+ Tv++1 BB. (s, As))
=1
| 1-1
II (s, (6210 (B000 (s,Aa((
+ +g (s, A(i)) (26
(7/-1- 1 -k+t)))
Wh-11
EI
/ A(i))) (5H1 A(1)) A(i)) (2///V (s, ( (H))) A(i))TGh++)) k
= (s, A)-
Now, we prove (%) A) - Q (s, A) s A).
2h A) Q% As
A 1-1
(1 +100
((s (s,
(1 -
(T(s.A(i)) A(i) + +1-1,s A(i)) ( vati
1=1
A
(s. (HHb*((s
+s, (
+ (-|s A()) T A()) (ioTTttt))
M
- ((, 6116 (()) + (s,
(s, (())
(-1s, (V/41 -Vita + A(i) - p(1|s, A(i))) T Vitti
+ (p(-1s A(1) - -00 (11s, ((1)) (Vi+2 - vitt vitt))
(16)
In addition, for any (s,a) E S x Aground, we have (p(-)s,a) (-1s, (Viti V
Vars (Viti
n+ V (8')) A.)' noti (8,
L k) p (s, a)
L(8',k)
2Va (V"ta(0")- vitt((")) + 4H2 4H2 kk)
3 k) (s,
/
(s,
n k.p (8,
36

---

Published as a conference paper at ICLR 2024
((),k)
(2H1)(((s,,aT (Vitz v
4HPT((0)
3 k)
$2
+
(s,
(0'k)
4HL(0,))
3HL(8'
22
H (11,,a) (Viit1 vitt1) +
(),)(s,a)
(s,
(s.0)
+ 11H2L(8.1)
H (+)s,a)
(Viti-Vitt) -
(17)
(s
Plugging Eq. (17) into Eq. (16), we have
(5, A)
Q% A)
|4| i-1
(1) - a))
15
Σ (1 7t (s.
6H
4V (4)
(t.
(s,
Vargi (s')) k8)
((1) 11
(),
15H2L(88 k))
+ H (1s,a))
(v -
a)
Vargrpp (V (69) (=)
38L(8.,) k)
+ ++1s,,, (vit1 Vitti) +
n)
2 + H (11s,)) (Viti -viti) +
1182I((88K))
(),as
II (1 5" (s, (s,)( 6H (AV (1) (ts n),
(OL((4))
15L
9 a)
Vargsmpp (5)) k8)
+ (s, A(i)) 6V
(s,
L9 ks) (s) + (1+ H 4 8" (-1s, chirl)
( ))
By the clipping bound in Eq. (16), we have
(s, A) Q (s. A)
M 1-
(1 o A(M)) 6H min { gh a)( - (*, (8)
15L (0', k:) (s. a)
1
())0)))))
=1
+ g (s. A(t)) min {ov Vargrage (Vitz(s")) I*(8',
29 k)
(
(s,
4 O0 (+13,u) T G 2H + 10 (1),, Ghit1)
(11,,a)(Gh++1)
+
Sth+1($, A).
Then, we have
min( V min (v)))))ss), Vi² (s)) = xf(s, -mn))))nn(())))))))) m+)))) Q (s,
S (((,,(((()))
= c{(s),
37

---

Published as a conference paper at ICLR 2024
which completes the proof.
D.2.3 PROOF OF THEOREM? 2
Proof of Theorem 2. Recall that 8' : 3. From Lemmas 10, 18 and 19, we have Pr[K n En > 78' = 11-6 8. Below we assume that event IC Cn M holds, and then prove the correctness and sample complexity.
First, we prove the correctness. Using Lemma 20 and 21, we have that the output policy n K+1 satisfies that
(i((s)) 1/ (s1) S 1)*+((s)) x (51) (s1)
(s1) Se.
which indicates that policy nKK
++1 is e-optimal.
Next, we prove sample complexity.
For any k > 0, h E
[H], E S and A A.
|A i-1
Gh (((3) - n).9 a)
L=),
15 k) (5, a)
(5, <
II (L (G))) 6H (1
+ (s, A()) (8V Vargenge (V (V)+2(8')) (8,
30 .b) (8,(8, A(i))
n A(i))
(+ (1+
H 4) 8 (+|s, A(i)) G
+
| (-1
(5, a) - (s, (8), k)
90HLL R) (s,
Σ (1 g(s A(ii)) 24H1
(8,
Var (Vi,,(()) (=(,',k)
L0H'L (k) (s A(i)
+
+g(0, A(i)) 6V
( A(i))
+ (1+ H
((is
Σ gls, A(i))) / a(s,a)(1 g(8, (()
M 1-1
186HL nt.99,, a)
(s,
=1
Varsrppa
L (+(
30H2 Rk) n^P(s,
+ g(s ((1) @V
nhr A(i))
4 H p( A(i))
G + (1+ 4 #) A(i)) - p(-1s A(i)) 0h+1)
+
(18)
where inequality (a) comes from Eq. (15). Using Eq. (21) in Lemma 22, we have
2 2ar up (hh+a('')) K(5,k)
2HL(6, k)
(p*(-1s, - p(-1s, A(1)) Gh S
+
nh.(ss, A(i))
P (s, A(i))
H p(|1s, A(i) A(1))TGH G 2H²
2HT(5,k)
nltP(s,AAii)
P A(i)
(H,
T H p(1s,, A(i)) Gh+1
(19)
ntt A(1))
38

---

Published as a conference paper at ICLR 2024
According to Eqs. (22) and (23) in Lemma 22, we have
(
/arg (V (V)+)((")) =
/ar (V (5')) + ())
(H2
Varrgmop (Viti (0') + p-),( (vh+ - Vitii) + P (8,0))
Varggw (V (5') + 4Hp(-1s,a) (v/4, vh+t)) + 4H ((6
a).
4HHI(
Varg/np Vitt26')) + /4Hp(-1s,a) aT + a) 1
Then,
Var sipp (Vh+z (8') L (8 k)
/ (V (s') ())
(s,aa)
(s,
4112 1 1( T+ 2HL(8', k) (t,
Var (V (5') (*),,k))))))) ())
GHPI(6, k) (),(s,
52
+
+ T Gh+1
(20)
Plugging Eqs. (19) and (20) into Eq. (18), we obtain
IAI t-1
24H g(s,a) g(s, (8),
186HLL
G A) S
Σ II g(s.
A(i)))
(s)
5=
+ g(ss, A(i)) (1OV
Vars'>p (V (yti(s')) (8' k)
42H2L(8, k) nt a)
+
H p(-(s. T
8
() a)
4 L(0 + (1+
p(-1s, A(i) T
(t A(i))
H
+ 1+
H
4
(5 A(i)) GG + nA A(i))
3112 k)
A 1-1
/ (((s,)((1 g(s, a)) I (5',k)
(8', k) (s.a))
$ EII (1 g(s, A())))
(s,
j=
Vars'op (Viti (s')) ())
87 k)
+ 00, A(i)) 16
())
h A(i)
+ (1
17) H p(-1s, A(i)) p(()s,A(0))
dhz1) A(1))((h+1)
Unfolding the above inequality over h = 1,2,...
H, we have
(86 g(s, (85
cf(s1) S
observe, RkA (s.a)Exx Apmont)
Σ
(s,
24H
n).9(s,a)
n a)
H
Var (Vrti (8') (=)))'
Σ
observe Ukhh
a)
17 17
(F,)())))
1= (mmd)
39

---

Published as a conference paper at ICLR 2024
87e LT L ( a)
H
g(s, - g(s, L))
<24H
observe.g a k
(s,0)
(5.0(s, a)
A=1 A
Aponnd {
H
kk)
+ 186H
Σ
abserve.g k.h
(8, a)
nh (s.a) a)
A=l (s,a)eSx x sacull((o1)
+ 16
Σ
observe, P (s, a) aat up h+t (8'))
1=1
H
observe.p kkhh
(s, (s,
Am (s,))Sxx Apound
H
H²
+ 87c
17
Σ
abserve. k
(s,
(s, a, nF.P (s,
h=1 (x,a)ESx Apund
a(8,a)(1 g(s, a)) (8 (8,
<24H
Σ
observe ( (s.08V k
1=1 (s,a)ESx XAsond)
11
(s, a) k8)
+ 186H
1 k.A
abserve.q
(s,( a)
h=1 (s,a)ESx x A [T1]
observe. (s, a) T, (8' k)
16e 17 HVH
Σ Σ
khh
P
(s
H
L(8 k)
+ "7 H²
Σ
cbserve. 2 (s.0)
0) n1 p.
kkh
h=1 (s.))EXxAmm
Let K denote the number of episodes that algorithm CascadingBPI plays. According to the stopping rule of algorithm CascadingBPI, we have that for any h & K,
E < G (s1).
Summing the above inequality over k = 1, K, dividing (s, a) by sets By and Bg, and using the clipping construction of Gs, A). we obtain
K
H
((s, ((s,a)(1 - (8),
Ke 244
Σ
(8, (3,4a) ukh
abserve.g
(s.
k=1h=1
(s.a)EBB
k5) (s,a) t (s, a)
+ 1861
observe.q k
k= (8,0)BB
k8),
+ 16c 17 H
observe. (s, a) (s. kk
Rm
A=
H
L(8' k)
+ 87c 27 22
observe. FRA
(s. a) n (s,
(3.))ER)
40

---

Published as a conference paper at ICLR 2024
K
K
H
UR
observe.g
(8,
observe.F kkh
(8, a)2
R=1 h=1 (s
k= h=1 (8
K
H1
K
observe.g
(s, (8,,)
S24H
ΣΣ Σ
obaerve k
(8, (8,8)
(8,9
k= h= (s,a)EBy
k=1h=1 (o,0)BB
L' kk) (8, a) n n (8,
+ 186/
k
observe.
A= 1= (s
H
+ 16e 17 HVKK
UAA
observe.p
(s, (s
h=1
(B
L(8', k)) observe.P (s.a)
HSN
+87e 17 2
+ 2
(s
8'
(s.0)EBB
Z96H / KHSA log (KH) (' 1488/54 log (KH) (6 K) + 64e KHSA log (KH) (8 K) 696e 17 SA log (K H) L(8', K)
HSN
+ +64H2SAlog log
8
HSN
$160e HOCHH K
log
log (KH) + (8g +1))
HSN 8'
KHSN 8'
(8eHSN(K
+ 27
log
log
+ Slgg
8'
where inequality (a) uses Lemma 9.
Thus, we have
160e 17 H HSA
HSN
<
log
log (KH) + log (8 + +1))
2248 H2SA
HSN
KHSN 8'
SeHSN((K +
log
log
Slog²
8
Using Lemma 23 with
+
SeHSN
A
log
HSN 8'
B B=
160e 17 HVHSA
D 2248. 17 HAAA and E S, we have
HASA A 2
HSN
H2SA
H2VHSA EVE
HSN
K K+150
log
log
+ S C2
where
HHSN 86
HSN
+ ))
C 0
log
(log
Therefore, we obtain Theorem 2.
E TECHNICAL LEMMAS
In this section, we present useful technical lemmas.
Lemma 22 (Lemmas 10, 11, 12 in (Ménard et al., 2021)). Let and p2 be two distributions on S such that KL(p1.P2) a. Let f and be two functions defined on S such that for any S.
41

---

Published as a conference paper at ICLR 2024
0 S g(s) I b. Then,
2
1e1 - 1/ S v 2Var (J)a - - ba,
(21)
3
Varp2 (f) S Var,, (f) + ab²a, Varp1 (f) S 2a (f) + 4b'a,
(22)
Varp (f) 2ar (9) 2b ob.pil. g)-
(23)
Lemma 23. Let A. B,C. D. E and be positive scalars such that S B < E and a e. Ifr 2 2 satisfies
TS C (Alog (AT) + Blog² (aT)) + D (A (aT) + Elog" (aT)),
then
T S (A B) C7 + (D+2VDCC) E) +1
where
8 C = - log (1la² (A+ B) (C D)).
42


Reviews:
[{"review_id": "aw3vggyMlB", "reviewer": "Reviewer_z4b8", "summary": "This paper studies cascading reinforcement learning, which is a natural extension of cascading bandits to the episodic reinforcement learning setting. In particular, this paper has\n\n- proposed the cascading reinforcement learning framework;\n\n- developed a computationally efficient algorithm to solve the \"cascading MDPs\" (i.e. the cascading reinforcement learning problems with known models). The key ideas are summarized in the BestPerm algorithm (Algorithm 1). \n\n- developed a learning algorithm for the cumulative regret minimization setting, which is referred to as CascadingVI (Algorithm 2). A regret bound is also established (Theorem 1). This paper has also discussed the tightness of this regret bound.\n\n- also developed a learning algorithm for the best policy identification setting, which is referred to as CascadingBPI. A sample complexity bound is established (Theorem 2). This paper has also discussed the tightness of this regret bound.\n\n- demonstrated preliminary experiment results (Section 7).", "questions": "Please address the weaknesses above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "In general, I think this paper is a strong theoretical paper, for the following reasons:\n\n- This paper studies a natural extension of a well-studied problem. Moreover, as summarized above, the contributions of this paper are clear.\n\n- The main results of this paper, summarized in Section 4 (efficient oracle), Section 5 (regret minimization), and Section 6 (best policy identification), are interesting and non-trivial. In particular, the regret bound in Theorem 1 and the sample complexity bound in Theorem 2 are non-trivial. Moreover, this paper has also discussed the tightness of these two bounds by comparing with existing lower bounds. Both bounds are near-optimal.\n\n- The paper is well-written in general, and is easy to read.", "weaknesses": "- I am wondering if the developed algorithms are useful for practical recommendation problems. The reason is that, this paper considers a tabular setting, thus the developed regret bound and the sample complexity bound depend on the number of states $S$. However, my understanding is that for most practical recommendation problems, $S$ will be exponentially large. Might the authors identify a setting where $S$ is not too large and hence the proposed algorithms are practical?\n\n- Currently the experiment results are very limited. In particular, this paper has only demonstrated experiment results in small-scale synthetic problems. I think experiment results on large-scale practical problems will further strengthen this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7Gq6bsuFV2", "reviewer": "Reviewer_MkFu", "summary": "The paper presents a new framework for reinforcement learning (RL) called cascading RL, which builds upon the concept of cascading bandits but incorporates state information into the decision-making process. This framework is aimed at applications such as personalized recommendation systems and online advertising, where cascading items are displayed to users one by one.\n\nKey challenges addressed include computational difficulty due to the combinatorial nature of actions and ensuring sample efficiency without relying on the exponential number of potential actions. To overcome these, the authors developed an efficient oracle called BestPerm, which uses dynamic programming to optimize item selection. They also introduced two RL algorithms: CascadingVI for regret minimization and CascadingBPI for sample complexity, both of which utilize BestPerm to achieve polynomial regret and sample complexity.\n\nCascadingVI achieves near-optimal regret matching a known lower bound. CascadingBPI offers efficient computation and sample complexity, reaching near-optimal performance.\n\nIn summary, the paper contributes a new cascading RL framework that efficiently handles the computational and sample complexity challenges of stateful item selection, supported by theoretical guarantees and demonstrated effectiveness through experiments.", "questions": "Where does the gap $\\sqrt{H}$ appear? Can you elaborate on this? Any possible direction to carve off this given that the tabular RL methods with a single action can achieve minimax optimality?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- As far as I know, this would be the first theory RL work with cascading actions. The formulation is sound.\n- The paper proposes an efficient optimization oracle for cascading RL, providing its correctness (it would be better to show it in the main text rather than the appendix).\n- Although it is not groundbreaking, the paper provides both regret analysis and sample complexity analysis.", "weaknesses": "- It seems that the techniques used for regret analysis and sample complexity are largely borrowed from the previous literature. I wonder if there are sufficient technical challenges once you know how to solve Problem (2).\n- The readability of the algorithms can be improved. e.g., Update rule of $\\bar{q}^k$ and $\\underbar{q}^k$ in Line 6 of Algorithm 2, Line break in Line 8 of Algorithm 2, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w9HBg6gDzc", "reviewer": "Reviewer_Rma4", "summary": "This paper proposes an extension of the cascading bandits framework to a more general reinforcement learning framework. The authors thereby attempt to model user sessions or historical user behavior and their impact on the click behavior and payoff.  While the action space (i.e., combination of items) is combinatorial, the feedback is item-wise so that attraction and transition probabilities can be estimated efficiently. This allows the authors to design algorithms with non-trivial regret and sample complexity guarantees. In particular, the authors rely on monotonicity properties to design an efficient oracle. Finally, the authors support their theoretical findings through experiments which support the efficiency of the proposed algorithms.", "questions": "- Could you further explain why contextual approaches are insufficient and what the merit of the RL formulation is in contrast to contextual bandits or recommendation approaches based on context trees? In the RL framework it is important what states the user transitions to, as some states may have the potential to yield higher rewards than others. Do you think that this is realistic in practice?  \n\n- It would be great if you could go into a bit more detail in your related work section and more clearly highlight the differences to prior models. For example, in contrast to the classical cascading bandits, the order of items also matters in your case as you usually would like the item with largest reward in state s to be clicked. \n\nMinor things: \n- In the 4th contribution, I found the statement about \"$\\varepsilon$ sufficiently large\" slightly confusing. It only becomes clearer later in Theorem 2 when the full bound is stated. Maybe there is a way to state this less conusingly in the introduction.  \n- Typo in the 3rd paragraph of Section 7: \"Regarding the best policy identification objective\" instead of \"Regarding the regret minimization objective\".", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Firstly, I think that the studied problem is interesting and the presentation of the paper clear. \n- The extension of the cascading bandit model to an RL formulation is highly non-trivial and the paper contains novel contributions including the RL formulation itself and an interesting algorithm design which relies on properties of the value function. \n- The authors do a good job explaining their algorithms and provide intuition for their results.  \n- The necessity of adopting standard RL algorithms to the proposed cascading model is highlighted in the paper several times and the authors thereby provide proper justification for the proposed algorithms.", "weaknesses": "- I am not fully convinced of the practicality of this model. Firstly, historical user behavior can be modeled as part of the context in contextual bandit frameworks. Moreover, \"artificially\" creating states appears fairly cumbersome compared to the contextual bandit structure and it is also not entirely clear how such states would be defined in practice. However, I could be convinced otherwise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IWhak2vAW3", "reviewer": "Reviewer_6goX", "summary": "The paper tackles the Cascading Bandits problem over a Markov Decision Process, where time is divided into episode of fixed length $H$, and the attractiveness of items (which determined the expected state transitions and rewards) is dependent on a state at the current step in the episode. At each step in the episode, the system gets to observe the current state and proposed a ranked list of items and the environment provides a click on one of the items according to the cascading click model. For this problem, the paper provides a method for computing the optimal offline strategy when all distributions are known and an introduces the CascadingVI algorithm along with a regret bound of $O(H\\sqrt{HSNK})$, where $H$ is the episode length, $S$ is the number of states, $K$ the number of episodes and $N$ is the number of individual items available to rank. The performance of the proposed algorithm is compared numerically with a baseline algorithm produced by adapting an existing algorithm to the combinatorial space, referred to here as AdaptRM.", "questions": "On line 8 in Algorithm 2, what is the complexity of computing $E_{s'\\sim p^k}[ .... ]$? \n\nRegarding BestPerm, to me it feels like the biggest hurdle is the computational complexity of computing the value functions $w$, which BestPerm assumes is an input. How does your proposed algorithm navigate this difficulty? \n\nI would also like to see more intuition regarding the exploration bonus $b^{k, pV}(s, a)$, in particular: how is the optimism of $\\overline{V}^k_h(s)$ connected to the uncertainty in the estimates of state transition probabilities $p$? The algorithm is already fairly convoluted and it is hard to see how we can construct optimistic estimates of the value functions in light of estimation noise in the state transition probabilities. I believe it is very valuable to clearly articulate such insights in the main body of the paper.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- generalizes the cascading bandit problem to MDPs\n- provides numerical experiments, even though, in my opinion the baseline is too weak\n- provides theoretical guarantees and proofs of correctness\n- generally well written, despite the convoluted algorithms I could navigate my way around the paper.", "weaknesses": "- The significance of the contribution is not substantial enough to justify acceptance into the venue in my opinion. One of the main contributions is providing an algorithm that does not scale in complexity (both sample or computational) with the space of all possible rankings. I believe we have well-known recipes for how such algorithms can be formulated since the papers on Cascading Bandits from 2015 (Kveton et. al, Combes et al.). Providing a solution scaling with the number of items is expected in my opinion and not a surprising contribution (we know that estimating individual CTRs is enough to construct optimal rankings, we don't need to keep statistics on each individual ranking). This also leads me to believe the baseline used in the numerical experiments is weak. \n- The contribution related to the generalization to MDPs is not opening a significant amount of new doors. In my opinion, this generalization does not provide further theoretical insights and has limited additional practical relevance.\n- The experimental section use a setting that is too simplistic (very few items and states) and a weak baseline, in my opinion, thus not being representative enough of what we can expect from this algorithm in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)