Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regret
Authors: Jiawei Huang
Li Zhao
Tao Qin
Wei Chen
Nan Jiang
Tie-Yan Liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement Learning
Regret Minimization

Abstract: We propose a new learning framework that captures the tiered structure of many real-world user-interaction applications, where the users can be divided into two groups based on their different tolerance on exploration risks and should be treated separately. In this setting, we simultaneously maintain two policies $\pi^{\text{O}}$ and $\pi^{\text{E}}$: $\pi^{\text{O}}$ (``O'' for ``online'') interacts with more risk-tolerant users from the first tier and minimizes regret by balancing exploration and exploitation as usual, while $\pi^{\text{E}}$ (``E'' for ``exploit'') exclusively focuses on exploitation for risk-averse users from the second tier utilizing the data collected so far. An important question is whether such a separation yields advantages over the standard online setting (i.e., $\pi^{\text{E}}=\pi^{\text{O}}$) for the risk-averse users. 
We individually consider the gap-independent vs.~gap-dependent settings. For the former, we prove that the separation is indeed not beneficial from a minimax perspective. For the latter, we show that if choosing Pessimistic Value Iteration as the exploitation algorithm to produce $\pi^{\text{E}}$, we can achieve a constant regret for risk-averse users independent of the number of episodes $K$, which is in sharp contrast to the $\Omega(\log K)$ regret for any online RL algorithms in the same setting, while the regret of $\pi^{\text{O}}$ (almost) maintains its online regret optimality and does not need to compromise for the success of $\pi^{\text{E}}$.

Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regret
Jiawei Huang' Li Zhao? Tao Qin Wei Chen?
Nan Jiang' Tie-Yan Liu?
Department of Computer Science, University of Illinois at Trrbana-hhappige (jiaweih, nanjiang @illinois. Microsoft Research Asia {lizo, taoqin, weic, tyliu: e com
Abstract
We propose a new learning framework that captures the tiered structure of many real-world lise-interaction applications, where the users be divided into two groups based on their different tolerance on exploration risks and should be treated separately. In this setting, simultaneously maintain two policies x and n²: x0 ("O" for "online") interacts with more risk-tolerant users from the first tier and minimizes regret by balancing exploration and exploitation usual, while x ("E" for "exploit") exclusively focuses on exploitation for risk-averse users from the sec- ond tier utilizing the data collected so far. An important question is whether such a separation yields advantages over the standard online setting (i.e., -= = 7 for the risk-averse users. We individually consider the gap-independent vs. gap-dependent settings. For the former, we prove that the separation is indeed not beneficial from minimax perspective. For the latter, we show that if choosing Pessimistic Value Iteration as the exploitation algorithm to produce n², we can achieve constant regret for risk-averse users independent of the number of episodes K, which is sharp contrast to the 2(log K) regret for any online RI. algorithms in the same setting, while the regret of o (almost) maintains its online regret optimality and does not need to compromise for the success of F.
Introduction
Reinforcement learning (RL) has been applied many real-world user-interaction applications to provide users with better services, such as recommendation systems [Afsar et al. 2021] and medical treatment (Yu et al. 2021 Lipsky and Sharp 2001). In those scenarios, the users take the role of the environments and the interaction strategies (e.g. recommendation or medical treatment) correspond to the agents in RL. In the theoretical study of such problems, most of the existing literature adopts the online interaction protocol, where in each episode & E [K], the learning agent executes policy т to interact with users (i.e. environments), receives new data to update the policy, and moves next episode. While this formulation treats each user equivalently when optimizing the regret, many scenarios have special "Tiered Structure users can be divided into multiple groups depending on their different preference and tolerance about the risk that results from the necessary exploration improve the policy, and such grouping is available to the learner in advance so it would be better to treat them separately. As concrete example, in medical treatment, after a new treatment plan comes out, some courageous patients or paid volunteers (denoted as GO; "O" for "Online") may prefer given the potential risks, while some conservative patients (denoted as G "E" for "Exploit") may tend to reccive mature and well-tested plans, even if the new one is promising be more effective.
the
Work done during the internship at Microsoft Research Asia. 2 We consider the cases with two tiers this paper.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Normal Online RL Formulation
Tiered Online RL Formulation (Ours)
Agant
Users
Agent
Users
Eny
Env
Alg
Rs Alg
E
User E GP
Eny
#
Alg
Figure 1: Comparison between the standard setting and our tiered RL setting (#Tiers 2), where use red and blue to color users from different groups. The main difference is that, in the standard setting (LHS), the learner does not distinguish users from different groups and treats them equivalently with a single policy тı produced by algorithm Alg, while our setting (RHS), we leverage the tier information and interact with different groups with different policies n. and T
As another example, companies offering recommendation services may recruit paid testers or use bonus to attract customers (Gº) interact with the system shoulder the majority of the exploration risk during policy improvement, which may result in better service (low regret) for the remaining customers (G+). Moreover, many online platforms have free service open for everyone (G"), while some users are willing to pay for enhanced service (G If we follow the traditional online setting and treat the users in these groups equivalently, then in expectation each group will suffer the same regret and risk. In contrast, we leverage the group information by using policies with different risk levels to interact with different groups, it is potentially possible transfer some exploration risks from users in G to Go while the additional risks suffered by G will be compensated in other forms (such as payment, the users' inherent motivation, or the free service itself).
To make our objective more clear, we abstract the problem setting into Frw. and compare it with the standard online setting in Fig. where we use Alg and Alg" to denote the two algorithms producing policies - and 7 to interact with users in G and G respectively. To enable theoretical analyses, do adopt few simplification assumptions while still modelling the core challenges in the aforementioned scenarios: firstly, at each iteration of Frw. [ the algorithms will interact with and collect one trajectory from each group, which assumes that users from two groups will come to seek for service in pair with the same frequency. In practice, usually, the users come in random order and the frequencies from different groups are not the same; see Appx. B for why our abstraction is still a valid surrogate and how our results can be generalized. Secondly, for convenience, we only use the samples generated from GO, because Alg is expected to best exploit the available information and not encouraged to perform intelligent exploration. Nonethe- less, results hold with minor modifications if also chooses to trajectories from G Thirdly, we assume that the dynamics and rewards during the interactions with users in different groups are all the same (i.e. Env Envo E) It is possible that the users in different tiers can behave differently, and we leave the relaxation of such an assumption to future work.
Framework 1: The Tiered RL Framework
Input: En and Env Note that Env Eny
2 Initialize D2 + O.
for k = 1,2, K do
o. + Ale (D+); + - Algh(De).
T interacts with customerrs/sseer/paainnsss Go (i.e. Eny"), and collect data 70
Th interacts with customerss/user//patienn in G (i.e. Env²), and collect data Tk
D = DA U (-2). ). // We do not consider to use o in this paper.
8 end
Similar to the online setting, we use the expected pseudo-regret to measure the performance of the algorithm, which is formalized Def. 2.T The key problem we would like to investigate provable benefits of leveraging the tiered structure Frw. comparing with the standard online setting:

---

Is it possible for Regret(Alg") to be strictly lower than any online learning algorithms in certain scenarios, while keeping Regret Alg") near-optimal?
Note that we still expect regret of Alg to enjoy near-optimal regret guarantees, which is reasonable requirement as the experience of users in G also matters in many of our motivating applications. We regard the above problem formulation as our first contribution, which is mainly conceptual.
As our second contribution, Sec. shows that Alg" E has the same minimax gap-independent lower bound as online learning algorithms. This result reveals the difficulty to leverage tiered structure in standard tabular MDPs, and motivates to investigate the benefits under the gap-dependent setting, which is frequently considered in the Multi-Armed Bandit (MAB) [Lattimore and Szepesvári 2020 Rouyer and Seldin
2020] and RL literature [Xu et al. 2021 Simchowitz and Jamieson 2019
As our third contribution and our main technical results, Sec. 4 establishes provable benefits of Frw. [ by proposing a new algorithmic framework and showing Regret(Alg") is constant and independent of the number of episodes K, which is in sharp contrast with the S2(log K) regret lower bound for any algorithms in the standard online setting that do not leverage the tiered structure. Specifically, we use Pessimistic Value Iteration (PVT) as Alg for exploitation interact with G while Alg can be arbitrary online algorithms with near-optimal regret. Concretely, we first study stochastic MABs as warm-up, where we choose Alg" E to be LCB (Lower Confidence Bonus), degenerated version of PVI in bandits, and choose UCB (Upper Confidence Bonus) as Alg O for concrete case study. We prove that Alg can achieve constant pseudo-regret ŌlE (A 1 1) 3
with A being the number of actions and A 's being the gaps with A 2 2 AA-1 2
A = O, while Alg is near-optimal due to the regret guarantee of UCB. After that, Sec. 4.2 extends the success of PVI to tabular MDPs, and establishes results that apply to a wide range of online algorithms Alg with near-optimal regret. Although the benefits of pessimism have been widely recognized in offline RL [Tin et al., 202T], to knowledge, we are the first study PVI in gap- dependent online setting. We also contribute several novel techniques for overcoming the difficulties in achieving constant regret, and defer their summary to Sec. 4.2 Moreover, in Appx H we report experiment results to demostrate the advantage of leveraging tiered structure as predicted by theory.
Closest Related Work Due to space limit, we only discuss the closest related work here and defer the rest to Appx. A To our knowledge, there is no previous works on leveraging tiered structure in MDPs. In the bandit setting, there is line of related works studying decoupling exploration and exploitation [Avner et al.) 2012, Rouyer and Seldin 2020), where [Rouyer and Seldin (020) studied "best of both worlds" methods and reported similar constant regret. First, in stochastic bandits, there are many cases when our result is tighter than theirs, (see a detailed comparison in Sec. [ and more importantly, our methods can naturally extend to RL (i.e., MDPs), whereas a similar extension of their techniques can run into serious difficulties: they relied on importance sampling to provide unbiased off-policy estimation for policy value, which incurs the infamous "curse of horizon", a.k.a., a sample complexity exponential in the planning horizon // in long-horizon RL (see examples in Sec. in [Liu et al. 2018)). Our approach overcomes this difficulty by developing pessimism- based learning framework. which is fundamentally different from their approach and requires several novel techniques in the analyses. Second, they did not provide any guarantee for the regret of exploration algorithm, whereas in our results the regret of Alg can be near-optimal, which we believe is also important as the experience of users in Go also matters in many of our motivating applications. Third, their bandit results require a unique best arm, whereas we allow the optimal arms/policies to be non-unique, which can cause non-trivial difficulties in the analyses we will discuss in Sec. 4.2.3
2 Preliminary and Problem formulation
Stochastic Multi-Armed Bandits (MABs) The MAB model consists of a set of arms A = 21, .... A}. When sampling an arm A, the agent observes random variable r; E [0. 1]. We use 14; = E[r]] to denote the mean value for arm for each i E A. We allow the optimal arms to be non-unique. For simplicity of notation, we assume the arms are ordered such that μn S u2... S P..
Finite-Horizon Tabular Markov Decision Processes (MDPs) For the reinforcement learning (RI. setting, we consider the episodic tabular MDPs denoted by MS, A, H, P,r), where S is the finite
3

---

state space, A is the finite action space, H is the horizon length, and P = (PA and r {rr are the deeedeepndentt transition and reward functions, respectively. We assume all steps share the state and action space (i.e. S S2... = Su S, A A2... Ai A) while the transition and reward functions can be different. At the beginning of each episode, the environment will start from a fixed initial state 81 (w.loog.). Then, for each time step h E [H]] the agent selects an action d E A based on the current state Sh, receives the reward r. (5h; an), and observes the system transition to the next state 1 until 5 is reached. g.L.ogg. we assume the reward function is deterministic and our results can be easily extended to handle stochastic rewards.
A time- dene-deenndnt policy is specified as π [ T2, TH. with TA : : A(A) for all h E [H]. Here (AA) denotes the probability simplex over the action space. With a slight abuse of notation. when TT, is deterministic policy, we use :S + A to refer to a deterministic mapping. V (s) and
(s,6 a) denote the value function and Q-function at step h E [H], which are defined as: VA (8)
BIE#= The (sy, ote) 18 = 8, =], (% a) = EIE The ow)]|s 5,0% m|.
We use (-) max (.) and (;(-,)) max, (% to refer to the optimal state/action -taluev functions, and II (s,) == (an, at state 84- With an abuse of notation, we define IT" = ( VT' (s1) (s1)), ). i.e., the set of policies that maximize the total expected return. In this paper, when we say that the MDP has "unique optimal (deterministic) policy", it is up the occupancy measure, that is, all policies in IT" share the same state-action occupancy d" (sh, an) == Pr(S), = Sn, AA ag [Si h E [H]],s Sh E Sr, ag E An. In the following, we use |II 1 to refer to the case of unique optimal (deterministic) policy, where the cardinality of II* is counted up to the equivalence of occupancies. Besides, for any function V S IR, we denote Vs,, ax,) == PP (-Ien. .s)) [V (sh+1)].
(aaala"(aa""""" (*,,,, an) = V (sh)) to denote the collection of all optimal actions
$1, σ) for all
Gap-Dependent Setting We follow the standard formulation of gap-dependent setting in previous
bandits [Lattimore and Szepesvári [2020] and RL literature [Simchowitz w Jamieson 2019 Xu et al.
2021 Dann et al. 2021]. In bandits, the gap w.r.t. arm i is defined as A; = max Hij 14, Vi E [A,, and we assume that there exists a strictly positive value Amin such that, either A; = 0 or
A; 2 Amin- For tabular RL setting, we define An an) := V* V*(ss) Q* ax), vh E [ff], sp Sn, ag E AAs We use the same notation Amin to refer to the minimal gap in tabular setting and assume that either (s an)
(s),a)) Amin.
Performance Measure We use "seudo-Regre defined below to measure the performance of Alg and Alg". In the following, we will also use "exploitation regret" to refer to Regret (Alg"). Definition 2.1 (Pseudo- Regret). We define the regret of Alg" and Algf be:
Regret x (Alg") == Σ (/
Regret x (Alg") = Σ -
where Th and th are generated according to the procedure in Framework 7 and the expectation is taken over the randomness in data generation and algorithms.
3 Lower Bound of Regret(Alg") without Gap Assumption
In this section, we show that, in normal tabular RL setting, for arbitrary algorithm pair (Algo, AlgF). even if we do not constrain Alg to be near-optimal, the regret of Alg has the same minimax lower bound algorithms in online setting. We defer the formal statement and proof to Appendix C.
Theorem 3.1. [Lower Bound for Alg without Gap Assumption] There exist positive constants So, 8o such that, for arbitrary S 2 4, A 2 2, H 2 2, K Z 2/ SHASA and arbitrary algorithm pair
(Alg", .Alg"), there must exist a hard tabular MDP Mhard. ELAgg" Alg") A
V - V
do Vee&&SK,, where the expectation is taken over the randomness of algorithmms and MDP.
The theorem above is stating that, comparing with the regret lower bound for online algorithms Ō({H(5AК) in Theorem 9 of Domingues et al. [2021), the exploitation algorithm cannot reduce the dependence on any of parameters H, S, A, K in hard MDPs, even if we allow Alg sacrifice its performance to gather the best possible data for Alg.. Also, the lower bound would still hold

---

even if we allow both Alg" and Alg" to additionally use the data T generated by n². This negative result implies that without any further assumptions, the separation not beneficial from minimax optimality perspective, and we can simply choose both Alg and Alg be the same near-optimal online algorithm as without worrying about separating them.
However, in the next section, will show that, in tabular MDPs with strictly positive gaps, in contrast with the Sloog K) lower bound for online algorithms. we can have Alg such that its regret is constant and independent on the number of time horizon K, which reveals the fundamental differences between the pure online setting and the Tiered RL setting considered in this paper.
4 Pessimism in the Face of Uncertainty and Constant Regret
In this section, we consider the gap-dependem setting and contribute to identifying the possibility to achieve constant regret by using pessimistic algorithms for Alg". Intuitively. the main reason why PVI can lead to a constant regret is that the quality of the policy returned by PVI is positively correlated to the accumulation of optimal trajectories in the dataset D, which is directly connected with Regret(Alg' (Alg") As result, on the one hand, the regret minimization objective of Alg coincidentally aligns with the optimality constraint of Alg On the other hand, thanks the positive gap assumption, B will gradually converge to the optimal policy with high probability when Alg is PVI, so there will be no regret after that. In Sec. 4.I] we start with stochastic MAB as warm-up, and in Sec. 4.2
we extend our success to tabular RL setting, We defer the proofs in this section to Appendix
4.1 Up: Gap-Dependent Regret Bound for Stochastic Multi-Armed Bandits
Algorithm 2: UCC-EEpploation-LCCEEEXppoioaa
Initilize: a > 1; (1(1) + 0, (1(1) < O, ViEA; f(k) == + 16A7 + 1)2
for k = 1, 2, .... K" do
T arg max; (k) + 2a log f(k)
arg (b)
2a lug f(k) (k(
(k)
Interact with F and G by T and nh. and observe reward r(xT) and r(TT) respectively.
for i = 1,2, A do
N1 - 1) + (k) + 1 = d)
N.KK 7 + (b) N.(--1) (.+1))
+ r(T)) [=f==)]
end
end
Our main algorithm for bandit setting is shown in Alg where we consider the UCB algorithm [Lattimore and Szepesvári 2020) as Alg and choose the LCB Alg which flips the sign of the bonus term in UCB. We use (k) to denote the number of times that arm was pulled previous to step k; and use fú; to record the empirical average of arm i. Besides, we assume 1/N.(.) too N.(-) = O, which implies that at the first [A] steps the algorithm will pull each arm one by one. Moreover,
will show later, the choice of a 1 is crucial to avoiding dependence on K in Regret( AlgB) with our techniques. For Alg 2 we have the following guarantee:
Theorem 4.1. [Exploitation Regret] In Algorithm [ by choosing arbitrary a > there exists absolute constant c, such that, for arbitrary K 2 1, the pseduo-regret regret of Alg is upper bounded by:
Regret x (Alg") < =Ō( a-1 + Es
1) A; -2,,),,
A. where Au : 00 so A
Our result implies that by choosing PVI as Alg Algo near-optimal. Besides the advantages discussed in the related work paragraph in Sec. our guarantee is also more favorable in certain cases compared to the O Amm Ea.50 3, result in Rouyer and Seldin [2020]: while it is not easy to verify whether our guarantee dominates theirs, in many cases consider the following two representative cases: A = A₂ = A..AA- Amia (uniform gap) and
achieve constant regret while keeping
be strictly better (or at least no worse) than theirs. For example,
A = A₂ = = A > A = Amin (small last gap); our result achieves Ō and
Õ A min respectively, in contrast to their Ō ((-)) and Ō VA x
5

---

Proof Sketch: The proof consists of two novel technique lemmas with carefully chosen failure rate Ōg- r ((1/kBla)) so that the accumulative failure probability Σk= ò6 < +oe. The first one is Lem. 4.2 where we show that w.p. dg. LCB will not prefer i with A; as long as another better arm has been visited enough times in the dataset. The second step is to identify a key property of UCB algorithm as stated in Lem. 4.3 where we provide a high probability upper bound that (k) S k/λ if k 2 (A)A3)) for arbitrary À E [1, 44], and serves to indicate that the condition required by the success of LCB achievable as long as le is large enough P
Lemma 4.2. [Blessing of Pessimism] With the choice that f(k)) = 1 + 16 + for arbitrary
i with A; > 0, for the LCB algorithm in Alg 2 and arbitrary j sarisfying A < D. we have:
Pr (i T + DI < 4,) (2(K)
So log ((k)
S
A.
Lemma 4.3. [Property of UCBJ With the choice that [kk = 1 + 1644 + 1)2, there exists a
constant e, for arbitrary with A > and arbitrary X [1,4A], in UCB algorithm, we have: ad (r(N)(k) 2 () p20-1; Vk 2 e Ai log(1
aA
Amin
Directly combining the above two results, we can obtain an upper bound for Regret(Alg") of order O(A/Amiu) min), which is already independent of K. To achieve better dependence on Amin in the regret, conduct finer analysis. For each arm i with A, O, we separate all the arms including into two groups based on whether its gap exceeds A:/2: G. = [j= A, > A/2 and G_ = {j : A S 4:/2]. As a result of Lem. 4.2. we know that & will not prefer arm as long there exists
G. such that (K) 044 3) () Based on Lem. 4.3
know is true with high probability, as long as l 2 θ(A A, since at that time N((k) S k/A
holds for arbitrary / E Gl which directly implies that m Nk)k) 2 )) Then, combining Lem. 4.2, with high probability, the regret resulting from taken arm i cannot be higher than @(1 A, A; G(A- A, which results in a Õ(Σ,, >a A/ A/),) regret bound. As for the techniques leading to the further improvement in our final result, please refer to Lem. D. and the
proof of Thm. 4. in Appx.
4.2 Constant Regret of Alg in Tabular MDPs
In this section, we establish constant regret of Alg based on realistic conditions for Alg and Alg We highlight the key steps of our analysis and our technical contributions here.
First of all, in Sec 4.2.1 we propose the concrete PVI algorithm, and inspired by the clipping trick used for optimistic online algorithms (Simchowitz and Jamieson| 2019), we develop a high-probability gap-dependent upper bound for the sub-optimality of π which related the accumulation of the optimal trajectories in dataset DR- Secondly, in Sec. 4.2.2] we first introduce a general condition (Cond. 4.6) for the chocie of Alg based on which we quantify the accumulation of optimal trajectories in D3 with the regret of Alg and connect the exploration by Alg and the optimality of Alg.. We also supplement some details about how to relax such a condition and inherit the guarantees by the doubling-trick in Appx. G which may be of independent interest. In Sec. 4.2.3 i.e. the last part of analysis, we bring the above two steps together and complete the proof. However, there is an additional challenge when the tabular MDP has multiple deterministic optimal policies, which is possible when there are non-unique optimal actions at some states. We overcome this difficulty by Thm. 4.8 about policy coverage. To our knowledge, the only paper that runs into a similar challenge is [Papini et al. 2021] and they bypass the difficulty by assuming the uniqueness of optimal policy. Finally, Section 4.2.4 provide some interpretation and implications of our results.
4.2.1 Pessimistic Value Iteration as El and its Property
The full details of our algorithm for tiered RL setting is provided in Alg. B where we use PVI as A. Here we do not specify a concrete Bonus function, but provide general results for a range of
CComparing with results in Thm. 8.1 of [Lattiore and Szepesvári 2020 although our upper bounds of ((kk) is linear w.n.t k rather than log scale, we want to highlight that ours hold with high probability 0(1 k- -((e)) while [Lattimore and Szepesvári 2020 only upper bounded the expectation.

---

Algorithm 3: Tiered-RL. RL Algorithm with Pessimistic Value Iteration as Alg
Input: Episode number K; Confidence level Jo Bonus function (onus(;;))
for k = 1. 2.... do
[bx.1 2 for h H, H.H- 1,..., do
bx. Bonus (Dx. 64). //Compute bonus function for PVI.
for 84 Sn On E An do
(s,, an) - the number of times 8h; dh occurs in the dataset Da-
(8p on; 8h+1) - the number of times (8), an: 8h+1) occurs in the dataset Dg-
0, Ne.Mihh.nne) No. (86,066)
if NE,A an) = 0:
-
otherwise.
end
Qua(-:) t max + PR. Vaa41(;,-) bn,A(:-),0)-
10
(x,(() maN EA Qn)((.an) TR((( t arg max, (..a(.a).
11
12
end
13
T +- k " k22 :..::...EE..
PVL
PVL
// Step 2: Use Alg satisfying Cond. 4.6 compute x for G
The + (D&)-
15
16
// Step 3: Sample trajectories and collect new data
Interact with G and Go by o and mQ. and observe of and re. respectively.
DR+1 D2 U (TR).
end
qualified bonus functions satisfying Cond. 4.4 below. Cond. 4.4 can be satisfied by many bonus term considered in online literatures, and we briefly dicuss some examples in Appx. F.I
Condition 4.4 (Condition on Bonus Term for Alg²). We define the following event at iteration [[PRR, Vi,4+1 (Shy as)
[K] during the running of Alg. ERoous,K = (NE(MM)S aS E.A,,
where B₁ and B2 are parameters depending on S, A, H and A but independent of 8g, k. We assume that, Bonus function satisfies that, in Alg. 3 given arbitrary sequence k= with 5n, o2...., óR (0, 1/2), at arbitrary iteration k E [K]. we have Pr(Enomus.ht 2 8R-
FA V an)l < (2. an) n (bu.n an) S Bi (2
Next, we provide an upper bound for the sub-optimality gap of PVT with the clipping operator Clip[ærle] x T[x 2 s]. Previous upper bounds of PVT [e.g.. Theorem 4.4 of Ji et al. 2021 do not leverage the strictly positive gap and can be much looser when Nr.1 is large, and directly applying those results to our analysis would result in regret scaling with VK.
Theorem 4.5. By running Algorithm wiith confidence level dy, a function Bonus satisfying Condition 4.4 and dataset D = {TI,... .k. consisting of k complete trajectories generated by executing sequence of policies TI, Tk. on the event ERonus defined in Condition 4.4
ECUI |]-
(ii(s)
mW Vitk
( 2E,
Eclip
H. H,
(2g(22/5z) (8, an)
where n² can be an arbitrary optimal policy, Ecui where dmin := min Maine ES, d= (sh. an) subject to d= (sh, an.) > 0.
Amin 2H+2 |1 1 and Ecup = Amin if
25AH
[II*| >
4.2.2 Choice and Analysis of Alg
Next, we introduce general condition for Alg that the Alg can achieve O(log -rerett with high probability. is worth noting that many existing near-optimal online RL algorithms for gap- dependent settings may not directly satisfy the condition (Simchowitz I Jamieson 2019 Xu et al.
Note that do not require the knowledge of A, compute ba.

---

2021
Dann et al. 202 since they use a fixed confidence interval 8. In Appx. G we will introduce a more realistic abstraction of those algorithms in Cond. G.I and discuss in more details about how to close this gap with an algorithm framework inspired by the doubling trick.
Condition 4.6 (Condition on Alg') ). Alg" is algorithm which returns deterministic policies at each v iteration, and for arbitrary k 2 2, we have: Pr ( (Σx -V (s1) where C1, C2 are parameters only depending on S A, H and gap A and independent of k..
(s1)
> Ci+aC2 log k) S gm
Implication of Condition 4.6 for Alg Intuitively, low regret implies high accumulation of optimal trajectories in the dataset collected by Alg We formalize this intuition in Thm. 4.7 by establishing the relationship between the regret of Alg dd and Ei=1 d an) (the expectation of Nu.1). En Theorem 4.7. For an arbitrary sequence of deterministic policies Tı, T2, Th, there must exist sequence of deterministic optimal policies oं, T2. ..,, The such that vh E [1f,,88 E &Sn, an E Ani
k
k [ - (1)(-
an) 2
Σ d' (sh, an)
Amin
1==1
k=1
4.2.3 Main Results and Analysis
The main analysis is based on our discussion about the properties of Alg" and Alg in previous sub-sections. In the following, we first discuss the proof sketch for the case when [II*| = 1. The main idea is to show that the unique x' will be "well-covered" by dataset, where we say policy "' is "welll-overedd if for each (s) Sr x AA. with d= (sh,,a)) > 0, ( an) can strictly increase so that the RHS of [ in Thm. 4.5 will gradually decay to zero (e.g. (8),(8),, 4x) 2 Ök))). To show this, the key observation is that, with high probability, Ne,, (sh, ax) will not deviate too much from its expectation Σ3 d' (sh, an) (Lem. F.8). and can be lower bounded by d' on) Ologg)) = kdm (5h, clipping operator in Eq will take effects as long as k is large enough, and PVI will converge to the optimal policy with no regret. All that remains is to show the regret under failure events also at the constant level because we choose a gradually decreasing failure rate O A ), and
Olog k)) as result of Thm. 4.7 [177 As a result, the
lim EE ( < oo as long as >>> 1.
However, when ||I*| > the analysis becomes more challenging. The main difficulty is that, when the optimal policy is not unique, it is not obvious about the existence of "well-covered" x", since it not guarantee that how much similarity is shared by the sequence of policies Ti.-. especially when [I[*| is exponentially large (e.g. [IT*| = A)) We overcome this difficulty by proving the existence of "welllcovered" policy in the theorem stated below:
Theorem 4.8. [The existance of well-covered optimal policy] Given an arbitrary tabular MDP, and an arbitrury sequence of deterministic optimal policies पं, ... (T. may not equal to रテ for arbitrary < i < j S k when there are multiple deterministic optimal policies), there exists a (possibly stochastic) policy Tomeer such that wh E (H), V(hh, an) E Sr x An with d (Sh: an) >
k d' (Pn, an)
J - un); un), with Ce (1.-) = max {
(|Zn,diel + +1)H dTonee (.:)..
di (.:))
2 2
K=1
where Zh.do= = {(sh) an) E Sp x Ar E II' s.t. (r((s)) > 0, d= (SN) = 0}, and din, (Sh,ap) = min d= (sh: on) subject to d= (sn. an) > 0.
Here we provide some explanation to the above result. According to the definition, Zi is the set including the state-action pairs which can be covered by some deterministic policies but is not reachable by some other deterministic policies, and therefore [2i, < SA (or even |2i < S AA) Besides, di (sh, an) denotes the minimal occupancy over all possible deterministic optimal policies which can hit 8h, (h,, and therefore, is no less than dmii defined in Thm. 4.3 As result, we know there exists a "well-covered" Toovrr: since the accumulative density of its arbitrary reachable states can be lower bounded by (kk). Then, following a similar discussion as the case |IT*| = 1, we can finish the proof. We summarize our main result below.
8

---

Theorem 4.9. By running an Algorithm satisfying Condition 4.6 Alg" running Alg as Alg with bonus term function Bonus satisfying Condition 4.4 and dy = 1/k,, for some constant a 1, for arbitrary 2 the exploitation regret of Alg can be upper bounded by:
(i) When [I = 1 (unique optimal deterministic policy):
Regret k (Alg*) 00
Σ
Σ
C1 C2 log dt (8h: Gh. Amin
SAH(C1 + C2),
BiHl
log d= (8h Oh ) min
B2H
Amin
Amin
h=1
(ii) When [II*| 1
(oof>>(nonuuqquuu) (non-unique optimal deterministic policies):
Regretx (Agretx(Algg) 2 so
Σ
Σ
(2 log
SAH(CI + C2)
+ BISAH
log B2SAH dmii Amin
Amin
d (Sh: an Deiin
dman Amia
hml
F Sh: 020)
where क Tower and de (St, On) are introduced in Theorem 4.8
4.2.4 Interpretation of Results in Tabular RL
Recall our objective in Sec. D is to establish the benefits of leveraging the tiered structure by showing Regretx (Alg") is constant. This contrasts the lower bound of online algorithms that continuously increases with the episode number K, which corresponds to the regret suffered by users in G without leveraging the ticred structure, while Regret (Alg keeps Jopti-J as before. In Appx. we also provide some simulation results verification of our theoretical discovery.
One limitation of our results is that our bounds have additional dependence on d= (or even 1/d") compared to most of the regret bounds in the online setting, although similar dependence on log dm also appeared in few recent works [c.g., X in Thms. 8 and of Papini al. 2021]. Besides. according to the lower and upper bound of online RL in gap-dependent settings [Sinchowitz and Jamieson 2019). C + C2 in Cond. 4.6 have dependence on O(Ami)) which implies that in the regret bound in Thm. 4.9 the dependence on Amin would be O(Am2n). For the former, in Appx. C.2 we prove lower bound, showing that log d= 1 is unavoidable when Alg is allowed to behave adversarially without violating Cond. 4.6) for latter, we note that in the analysis MAB setting (.)) specifying the detailed behavior of Alg" can help tighten the bound. Therefore. we conjecture that our results can be improved by putting more constraints on the behavior of Alg which we leave to future work.
5 Conclusion
In this paper, we identify the tiered structure in many advantages of leveraging it by interacting with users from different groups with different strategies. Under the gap-dependent setting, we provide theoretical evidence of benefits by deriving constant regret for the exploitation policy while maintaining the optimality of the online learning policy.
applications and study the potential
As for the future work, propose several potentially interesting directions. (i) As we mentioned in Section 4.2.4 it is worth investigating the possibility of improving the regret bound of Alg" by considering more concrete choice of Alg or maybe other choices for Alg (ii) It would be interesting to relax our constraint on the optimality of Alg I by introducing the notion of budget C' as the tolerance on the sub-optimality of Alg As result, our setting and the decoupling exploration and exploitation setting can be regarded as special cases of a more general framework when and C' = oc. (iii) We assume that the users from different groups share the same transition and reward function, and would also be interesting to extend our results to more general settings, where the group ID serves as context and will affect the dynamics [Abbasi- Yadkori and Neu 2014 Modi et al. 2018 (iv) We only consider the setting with two tiers, and may be worth studying the possibility and potential benefits under the setting with multiple tiers.

---

Acknowledgements
JH's research activities on this work were conducted during his internship at MSRA. NJ's last involvement was in December 2021. NJ also acknowledges funding support from ARL Cooperative Agreement INT--I17-2- NSF IIS-21 IIS-2112471, NSF CAREER award, and Adobe Data Science Research Award. The authors thank Yuanying Cai for valuable discussion.
References
Yasin Abbasi- Yadkori and Gergely Neu. Online learning in mdps with side information. arXiv preprint arXiv:1406.68// 2014.
M Mehdi Afsar, Trafford Crump, and Behrouz Far. Reinforcement learning based recommender systems: A survey, arXiv preprint arXiv:2101.06266, 2021.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
Orly Avner, Shie Mannor, and Ohad Shamir. Decoupling exploration and exploitation in multi aelti-armed bandits. arXiv preprint 1205: 2012.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pages 263 272. PMLR, 2017.
Jacob Buckman, Carles Gelada, and Mare G Bellemare. The importance of pessimism in fixed-dataset policy optimization. arXiv preprint arXiv:2009.066 06799,, 2020.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning, 2017.
Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value- function gaps: Improved cetence-deeendent regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR, 2021.
Scott Fujimoto and Shixiang Shane Gu. A minimalist approach offline reinforcement learning. arXiv preprint wrXiv:2106.06860 2021.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171- 4180. PMLR, 2021.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. q-learning provably efficient? arXiv preprint arXiv:1807.03765. 2018
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. arXiv preprint arXiv:2006. 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives open problems, arXiv preprint wwx.i:2005.066433 2020.
10

---

Martin S Lipsky and Lisa K Sharp. From idea to market: the drug approval process. The Journal of the American Board of Family Practice, 14(5):362-30 -67, 2001.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off- off- policy estimation. Advances in Neural Information Processing Systems, 31, 2018.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. arXiv preprint arXiv:2007.08202 2020.
Aditya Modi, Nan Jiang, Satinder Singh, and Ambuj Tewari. Markov decision processes with contimuous side information. In Algorithmic Learning Theory, pages 597-618. PMLR, 2018.
Matteo Papini, Andrea Tirinzoni, Aldo Pacchiano, Marcello Restelli, Alessandro Lazaric, and Matteo
Pirotta. Reinforcement learning in linear mdps: Constant regret and representation selection. Advances in Neural Information Processing Systems, 34, 2021.
Chloé Rouyer and Yevgeny Seldin. Tsallis-inf for decoupled exploration and exploitation in multi- armed bandits. In Conference on Learning Theory, pages 3227-3249. PMIR, 2020.
Max Simchowitz and Kevin G Jamieson. Non-asymptotie gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32: 12:1153-1111 1162, 2019.
Aleksandrs Slivkins. Introduction multi-armed bandits. arXiv preprint arXiv:1904.07272. 2019.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. In International Conference on Learning Representations, 2022. URL
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. arXiv preprint 1rXiv:2/06.06922 2021.
Haike Xu, Tengyu Ma, and Simon S Du. Fine-grained sap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. arXiv preprint arXiv:2102.00 100.0462, 2021.
Kunhe Yang, Lin Yang, and Simon Du. Q-learning with logarithmic regret. In International
Conference on Artificial Intelligence and Statistics, pages 1576-1584. PMLR, 2021.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healtheare: A survey, ACM Computing Surveys (CSUR), 55(1): 2021.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. Advances in Neural Information Processing Systems,
2020.
Andrea Zanette and Emma Brunskill. Tighter
regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof's of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URI.)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report enror bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals. if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "xjL_YDd9r7F", "reviewer": "Reviewer_Tg34", "summary": "The paper proposes a new framework for the reinforcement learning problem (specifically, the MAB and finite-horizon tabular MDP) when the instances can be divided into two groups; one group which tolerates risky action selections for the sake of exploration, and another group for which the agent just focuses on maximizing the rewards. A goal is to achieve the near-optimal O(logT) regret for the first group while achieving a time-horizon-independent constant regret for the second group.\n\nUnder the assumption that the underlying distributions of the sate, action, and reward are identical for the two groups, and that the proportion of the number of instances in the first vs second group is constant and fixed, the authors provide a framework algorithm which achieves the goal with high probability.\n\nSpecifically, the core of these algorithms is to make action decisions according to the \"pessimism in the face of uncertainty\" principle for the second group. For the bandit problem, the authors propose a specific algorithm which employs the usual UCB algorithm for the first group and select the maximizer of the LCB (Lower confidence bound) for the second group.", "questions": "Questions\n\nIt would be good to have more details on the use of clipping operator. The authors use it in the algorithm but just refer the explanation to other papers", "limitations": "I did not find any discussion on societal impact .", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The authors provide detailed lower bound analysis for this problem. Specifically for the gap-independent case, the authors provide an example where it is impossible to do better than employing the near-optimal regret reinforcement learning algorithm to the whole instance sequence without making any distinction between the two groups.\n\n\n\n2. The authors derive the regret guarantee for the \"framework\" algorithm rather than just a specific algorithm. The framework requries to use a near-optimal regret reinforcement learning algorithm (that satisfies Condition 4.6) for the first group and then use the pessimism in the face of uncertaint principle (satisfying Condition 4.4) for the second group. As long as Conditions 4.6 and 4.4 are satisfied, the algorithm can be diversified according to the specific inner algorithms used. Hence the framework can apply to a wide range of problems with different kinds of reward functions.\n\n\n\n3. The regret guarantee hold without the assuming the uniqueness of the optimal policy.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WHHu5_Z7gf", "reviewer": "Reviewer_YYUn", "summary": "- They investigate a 2-tiered play structure in the stochastic bandit and MDPs, one of which is the \"exploiters\".  \n- Those two groups play the same instance simultaneously, and the exploiter group was shown to achieve a (gap-dependent) constant regret by using a conservative strategy (LCB) and exploit information from the other group (explorer). The regret of the explorer remains (near-)optimal.\n- Although there exists studies of decoupled exploration-exploitation in bandit settings, the differential is that it can be naturally extended to MDPs by using an algorithm (UCB/LCB) which does not use sample weights, resulting in high compatibility to the MDPs.  ", "questions": "- Are there concrete examples of exploiter groups who share a homogeneous model with explorers?", "limitations": "- Limited to the setting where two parties continue to play at the same time.  \n- Dividing into tiers and favoring one side (the exploiter group) would imply that there are differences that should be favored (e.g., they are wealthy, paying users). Such differences may have an impact on transitions and reward distributions, but they are using a homogeneous model. Therefore, it remains to be seen if there are specific examples that would have an impact in realistic problems.  \n- In that case, since the method only learns the data from the explorer group, the exploiter group might suffer a linear regret.  ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Originality: somewhat weak\n\t- The idea of decoupled exploration-exploitation was inherited from previous work. Since the previous work considers adversarial setting also, its method uses sample-weights, which has a risk of the \"curse of horizon\" when extended to MDPs. It is not a surprising idea to use UCB/LCB to avoid the problem.  \n- Quality: excellent\n\t- Their analysis is convincing since it proves the problem-dependent constant regret as well as the impossibility of the problem-independent constant regret.  \n- Clarity: good\n\t- This paper is well organized and reads naturally from a simple MAB setup to a table RL setup.  \n- Significance: good\n\t- It is a significant contribution that a constant regret can be achieved also in reinforcement learning by decoupling the explorers and the exploiters.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Rz9UXTOULf2", "reviewer": "Reviewer_e8u5", "summary": "This work focused on reinforcement learning and proposed a novel framework to utilize the tiered structure in applications. More specifically, the users are divided into two groups: a risk-tolerant group with the UCB-types algorithm and a risk-averse group with the LCB-types algorithm. With this structure, the author shows that there is nearly no advantage in the gap-independent instance but can improve the regret guarantee from log-T to constant in the gap-dependent instance. \n", "questions": "1. For both Algorithm 2 and Algorithm 3, only the data from online policy $\\pi^O$ are used to design the policy, and other data from policy $\\pi^E$ are ignored, which seems will deteriorate the algorithm performance. Is there some intuition behind it or just to protect the personal privacy of group E?\n\n2. For the Gap-dependent setting, the author mentions recent advances in regret guarantees for reinforcement learning. More recent advanced works have focused on using the function approximation techniques in MDPs. For instance, He et al. [2022] first obtained a logarithmic regret with the gap-dependent setting. Therefore, it is better if the author can mention them or have some discussion about them.\n\nHe J, Zhou D, Gu Q. Logarithmic regret for reinforcement learning with linear function approximation. ICML2021\n\n", "limitations": "This paper provides theoretical guarantees for learning linear bandit and linear mixture MDP. There is no negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. This work proposed a novel structure to utilize the tiered structure in applications and can improve the performance to constant regret guarantee with the gap-dependent instance.\n\n2. This work provides a theoretical lower bound for the gap-independent instance and shows that tiered can provide nearly no help in this case.\n\n3. This work first considers the pessimism algorithm in online reinforcement learning and combines it with the optimistic rule, which may be of independent interest.\n\nWeakness:\n\n1. The algorithms require the initial state to be fixed ($s_1$), which is much more restrictive than previous work in reinforcement learning.\n\n2. The intuition of introducing a tiered structure is not clear. For the tiered structure, the author mentions that users can be divided into multiple groups depending on their different preferences and tolerance of the risk that results from the necessary exploration to improve the policy. However, from the setting, there is no difference between these two groups in reward, transition, or regret. It is unclear what the critical difference between risk-tolerant and risk-averse people is. It is also unclear why we need to introduce the tiered structure and consider the two groups of people individually. A much more reasonable structure to represent different preferences and tolerance is introducing different rewards for different groups.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "366hMTHeNx", "reviewer": "Reviewer_fFex", "summary": "This paper formulated and studied the tiered RL problems where the uses are divided into two groups and treated separately. They showed that the constant and log K regret are achievable while keeping the online algorithm near-optimal for bandit and RL settings, respectively.", "questions": "1. I have a general question about the Tiered RL Framework. Under the assumption that $Env^O = Env^E,$ if the definition of regret is the same for both groups, why do different groups' risk tolerances matter? Is exploration still necessary if the $Alg^E$ can already achieve constant regret after certain timesteps/episodes? We are eventually looking for an algorithm that can give us lower regret. Then maybe it is also worth looking at how many samples are needed by collecting with the online algorithm such that a constant regret is achievable by using an exploitation algorithm.\n\n2. Since PVI and LCB are widely used in offline settings, can the authors clarify what the novel technical contributions of this paper are?\n", "limitations": "I don't think this paper has any potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. This paper is well written and organized, and the insights behind the main results are well presented. \n2. Both MAB and RL settings are considered in this paper. The regret bound is comparable with the best existing results.\n\n**Weakness**\n1. The model assumes the users from two groups share the same transition and reward function, there is still some gap between the model and reality.\n2. It would be great if the framework could model the total \"toleration budgets\" of different groups.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept