Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
Authors: Jiafan He
Dongruo Zhou
Quanquan Gu
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
discounted MDP
Bernstein inequality

Abstract:  We study the reinforcement learning problem for discounted Markov Decision Processes (MDPs) under the tabular setting. We propose a model-based algorithm named UCBVI-$\gamma$, which is based on the \emph{optimism in the face of uncertainty principle} and the Bernstein-type bonus. We show that UCBVI-$\gamma$ achieves an $\tilde{O}\big({\sqrt{SAT}}/{(1-\gamma)^{1.5}}\big)$ regret, where $S$ is the number of states, $A$ is the number of actions, $\gamma$ is the discount factor and $T$ is the number of steps. In addition,  we construct a class of hard MDPs and show that for any algorithm, the expected regret is at least $\tilde{\Omega}\big({\sqrt{SAT}}/{(1-\gamma)^{1.5}}\big)$. Our upper bound matches the minimax lower bound up to logarithmic factors, which suggests that UCBVI-$\gamma$ is nearly minimax optimal for discounted MDPs.

Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
Jiafan He
Dongruo Zhou
Department of Computer Science University of California, Los Angeles
Department of Computer Science University of California, Los Angeles CA 90095, USA drzhou@cs ucla.edll edu
CA 90095, USA j jiafanhe19@ucla.ede
Quanquan Gu
Department of Computer Science University of California, Los Angeles CA 90095, USA qguêcs ucla. edu
Abstract
We study the reinforcement learning problem for discounted Markov Decision Processes (MDPs) under the tabular setting. We propose a model-based algorithm named UCBVI-7 which is based on the optimism principle and the Bernstein-type bonus. We show that UCBVI-? achieves an O(VSAT/C - 2--5) regret, where S is the number of states, A is the number actions, 7 is the discount factor and T is the number of steps. In addition, we construct a class of hard MDPs and show that for any algorithm, the expected regret is least Ω (SSTT/// (1 - 2)5)) Our upper bound matches the minimax lower bound to logarithmic factors, which suggests that UCBVI-y is nearly minimax optimal for discounted MDPs.
the face of uncertainty
Introduction
The goal of reinforcement learning (RL) is designing algorithms to learn the optimal policy through interactions with the unknown dynamic environment. Markov decision process (MDPs) plays central role in reinforcement learning due their ability to describe the time-independent state transition property. More specifically, the discounted MDP is one of the standard MDPs in reinforcement learning describe sequential tasks without interruption restart. For discounted MDPs, with generative model [12], several algorithms with near-optimal sample complexity have been proposed. More specifically, Azar al. [3] proposed an Empirical QVI algorithm which achieves the optimal sample complexity to find the optimal value function. Sidford et al. [22] proposed sublinear randomized value iteration algorithm that achieves near-optimal sample complexity to find the optimal policy, and Sidford et al. [23] further improved it to reach the optimal sample complexity. Since generative model is powerful oracle that allows the algorithm to query the reward function and the next state for any state-action pair (s. a), it is natural to ask whether there exist online RI. algorithms (without generative model) that achieve optimality.
To measure an online RL algorithm, a widely used notion is regret, which is defined as the summation of sub-optimality gaps over time steps. The regret is firstly introduced for episodic and infinite- horizon average-reward MDPs and later extended to discounted MDPs by [15, 30, 35, 35]. Liu and Su [15] proposed a double Q-learning algorithm with the UCB exploration (Double Q-learning).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

regret, where S is the number of states, A is the number of actions, Y is the discount factor and is the number of steps. While Double Q-learning enjoys a standard VT /rggrett,, it still does not match the lower bound proved [15] in terms of the dependence on S, A and 1/(1 - 7). Recently, Zhou et al. [34] proposed a UCLK* algorithm for discounted MDPs under the linear mixture MDP assumption and achieved O(dvT/(1 2))1.) regret, where d is the dimension of the feature mapping. However, directly applying their algorithm to our setting would yield an O(S2AvT/( -7)".b) regret', which is even worse that of double Q-learning [15] in terms of the dependence on S. A.
which enjoys ((VSAT/(1-))
In this paper, we aim to close this gap by designing a practical algorithm with a nearly optimal regret. In particular, we propose model-based algorithm named UCBVI-a for discounted MDPs without using the generative model. At the core of our algorithm is to use a "refined" Bernstein-type bonus and the law of total variance [3, 4]. which together can provide tighter upper confidence bound (UCB). Our contributions are summarized as follows:
We propose a model-based algorithm UCBVI-a to learn the optimal value function under the discounted MDP setting. We show that the regret of UCBVI-y in first T steps is upper bounded by Ó(VSAT/(L - ..5) Our regret bound strictly improves the best existing regret Ö(VSAT/(1 - (1-7//11----- in [15] by a factor of (1 -)
We also prove a lower bound of the regret by constructing a class of hard-to-learn discounted MDPs, which can be regarded as chain of the hard MDPs considered in [15]. We show that for any algorithm, its regret in the first T steps can not be lower than Ω / S.V/AA//// (1 1-55 the constructed MDP. This lower bound also strictly improves the lower bound Ωi ((vSAT/(C))) - -)
(1 - 7)2-) proved by [15].
The nearly matching upper and the lower bounds together suggest that the proposed UCBVI-
algorithm is munimax-optimal up to logarithmic factors.
We compare the regret of UCBVI-? with previous online algorithms for learning discounted MDPs in Table 1.
Notation For any positive integer n, we denote by [n] the set (I....,m]. n. For any two numbers a and b, we denote by a V b as the shorthand for max(a, 6). For two sequences {an} and }b, we write an = O(b,)) if there exists an absolute constant C' such that an S Cbn, and we write an (2(b,)) if there exists an absolute constant C' such that an 2 Cbn. We use Ō() and f2(-) to further hide the logarithmic factors.
2 Related Work
Model-free Algorithms for Discounted MDPs. A large amount of reinforcement learning algo- rithms like Q-learning can be regarded as model-free algorithms. These algorithms directly learn the action-value function by updating the values of each -tatenaction pair. Kearns and Singh [13]
firstly proposed a phased Q-Learning which learns an e-optimal policy with (SSA//((11)
sample complexity for 1/(11 - 7). Later on, Strehl et al. [25] proposed a belly----eeaningg algorithm, which achieves Ō(SA/((1 - (0/((((1)))c*)) sample complexity of exploration. Wang [29]
proposed a randomized primal-dual -ual method algorithm, which improves the sample complexity to
O(SA/((1 - -)) f < 1/(1 7) under the ergodicity assumption. Later, Sidford et al. [23]
proposed sublinear randomized value iteration algorithm and achieved D(SAA((1-7) complexity for S 1. Sidford et al. [22] further improved the empirical QVI algorithm and proposed variance-reduced QVI algorithm, which improves the sample complexity to O(SA/(( - ))) for S 1. Wainwright [28] proposed a variance-reduced Q-learning algorithm, which is an extension of the Q-learning algorithm and achieves Õ(SA/(1 - 2)) sample complexity. In addition, Dong
sample
I Linear mixture MDP assumes that there exists a feature mapping (bs'|s,, a) Rd and vector 0 e Rd such that (P(8"'s,, a) = (<0(')ss (s, a), 0). It can verified that any MDP automatically linear mixture MDP with a A dimeeniiona feature mapping [2, 35].
"The regret definition in [15] differs from our detinition by a factor of (1 - --- Here we translate their regret from their definition to our definition for a fair comparison. A detailed comparison can be found in Appendix.
2

---

Table 1: Comparison of RL algorithms for discounted MDPs in terms of sample complexity and regret. Note that the regret bounds for all the compared algorithms except Double Q-learning [15] are derived from their sample complexity results. See Appendix A.1 for more details.
Algorithm
Sample complexity
Regret
Delay-Q-learning
SA (1 (1-7)8++
A
[25]
(1-1)0/5
Q-learning with UCB
0
SA
/1/3/1/27//3
[9]
(1-ン)TE
(I-2)873
UCB- UCB-multistage [33]
SA
g1/3 A//////
Model-free
(1-7)oibe
(1-7)18766
UCBB-uultitaage-adv [33]
SA
(1-7)
(1-1)4/3
Double Q-learnng
N/A
VSAT
[15]
(1-7)218
(1
R-max
S
91/2 ///2///1///4
[5]
(1 (1-7)
(1-1)7/1
MoRmax
δ
SA
gata g1/a/t/3r2/3
[27]
(1-
(1-3)778
Model-based
UCRL
S
5a/3 A 133-2/33
[14]
(1 (1-7)00²
(1-1)473
UCBVI-
N/A
VSAT δ
(Our work)
(1->)1+
SA ñ
Ω
VSAT (1-7)
Lower bound
N/A
[1-))
[14]
(Our work)
2. holds when S 1/poly(S, A,
et al. [9] proposed an infinite Q-learning with UCB and improved the sample complexity of explo- ration to (1))A(((1)))2)) Zhang et al. [33] proposed a UCB -CC--ittitttge algorithm which attains - the D(SA/(117)888)) 2)) sample complexity of exploration, and proposed a UCB-multistage- algorithm which attains a better sample complexity O(SA/((1 -(1)
in the high accuracy regime. Recently, Liu and Su [15] focused on regret minimization for the infinite-horfe horizon discounted MDP and showed the connection between regret and sample complexity of exploration. Liu and Su [15] proposed a Double Q-Learning algorithm, which achieves (/(VSAT// (1 2)555) regret within T steps. Furthermore, Liu and Su [15] constructed a series of hard MDPs and showed that the expected regret for any algorithm is lower bounder by (/V/SAT/// - 7) + VAT/ - -.3..) There still exists a 1/(1 - -gap between the upper and lower regret bounds. In contrast to the aforementioned model-free algorithms, our proposed algorithm is model-based.
Model-based Algorithms for Discounted MDP. Our UCBVI- falls into the category of model- based reinforcement learning algorithms. Model-based algorithms maintain a model of the envi- ronment and update it based the observed data. They will form the policy based the learnt model. More specifically, to learn the cooptiall value function, Azar et al. [3] proposed an empirical QVI algorithm which achieves Ó(SA/((1 - -))) sample complexity. Azar et al. [3] proposed an empirical QVI algorithm which improves the sample complexity Ó(SA/((1 - ())) for (1/1(17)55 Szita and Szepesvári [27] proposed MoRmax algorithm, which achieves
O(SA/((1-)) -)) sample complexity. Later, Lattimore and Hutter [14] proposed a UCRL algo- rithm, which achieves (S A/((1 - -3)3 sample complexity in general and Ö(S A/((1 - 3)2) sample complexity with a strong assumption on the state transition. Recently, Agarwal et al. [i]
proposed a refined analysis for the empirical QVI algorithm which achieves ((SA/((1 - 3)))
sample complexity when e < 1/v1 7.
Upper and Lower Bounds for Episodic MDPs. There a line of work which aims at proving sample complexity or regret for episodic MDPs (MDPs which consist of restarting episodes) [7, 18,
3

---

4. 19, 11, 8, 24, 21, 31, 32, 17, 20]. Compared with the episodic MDP, discounted MDPs involve only one infinite-horizon sample trajectory, suggesting that any two states or actions on the trajectory are dependent. Such a dependence makes the learning of discounted MDPs more challenging.
3 Preliminaries
We consider mnfiiit-hhoizon discounted Markov Decision Processes (MDP) which are defined by a tuple (S, A. r. IP). Here S is the state space with [] = S.A A is the action space with |A| = A, y (0. is the discount factor, r: S x A - [0, 1] is the reward function, PP'''ss, a) is the transition probability function, which denotes the probability that state s transfers to state with action a. For simplicity, we assume the reward function is deterministic and known. A non-stationary policies is a collection of function { where each function म, : {S x A] x S - A maps 8) action. For any non-stationary policy n, we denote Te(s) = (s; $1, a1.... St-1, for simplicity. We define the action-value function and value
history {#1: 01, St-1, 1
function at step as follows:
8
Q7 =
? r (s att))
813..1 =,
V.*(() (s) = E
Σ x (s 04:1) 81
where ac+i = (544() and 66+1+1 ~ (51411
In addition, denote the optimal
action-value function and the optimal value function as (s) = sup, Q7 (s. a) and (*) sup, V (s) respectively. Note that the optimal action-value function and the optimal value function are independent of the step f. For simplicity, for any function V : S - Rt we denote [PV] a)
Ex (s'). According to the definition of the value function, we have the following non- stationary Bellman equation and Bellman optimality equation for non-stationary policy and optimal policy n":
Q7 r(s,a) a) + (s), (s, = r(s,a) + (spV"
(3.1)
4
Main Results
4.1
Algorithm
In this subsection, we propose the Upper Confidence Bound Value Iteration- (UCBVI-?) algorithm, which is illustrated in Algorithm 1. The algorithm framework of UCBVI-y follows the UCBVI algorithm proposed in Azar et al. [4], which can be regarded as the counterpart of UCBVI-a in the episodic MDP setting.
UCBVI-> model-based algorithm that maintains an empirical measure Fr, at each step At the beginning of the t-th iteration, UCBVI-y takes action based on the greedy policy induced by Qr(s,, a) and transits to the next state $t+1. After receiving the next state St+1, UCBVI-> computes the empirical transition probability function IP, (s'ss,,, a) in (4.1). Based on empirical transition probability function (s' a). UCBVI-~ updates Q441 (s, a) by performing one-step value iteration on (2,s, a) with an additional upper confidence bound (UCB) term UCB, a) defined in (4.3). Here the UCB bonus term is used to measure the uncertainty of the expectation of the value function Vs(s).
Unlike previous work, which adapts Hoeffding-tyre type bonus [15], our UCBVI-> uses Bernstein- type bonus which brings tighter upper bound by accessing the variance of V.(s), denoted by Var,:~e(-l.e.a) (s'). However, since the probability transition TP(||s, a) is unknown, it is impossible to calculate the exact variance of V.. Instead, UCBVI- estimates the variance by considering the variance of V; over the empirical probability transition function Pr(-Is, a) defined in 14. Therefore, the final UCB bonus term (4.3) can be regarded as a standard Bernstein-tyre bonus on the empirical measure P. (r(-|s, a) with an additional error term.
Compared with UCBVI algorithm in Azar al. [4], the action- action-value function Qe(s, a) in UCBVI- is updated in a forward way from step to step T with the initial value Qı a) = 1/(1->) 7) for all
8 E S, a E A, while UCBVI updates its action-value function a backward way from QI H to Q., with initial value (t, a) = O. Compared with UCRL in Lattimore and Hutter [14], UCBVI- does not need to call an additional extended value iteration sub-procedure [10, 26), which is not easy to implement even with infinite computation [14].

---

Algorithm Upper Confidence Value-iteration UCBVI-y
Receive state 81 and set initial value function (s) 1/(1 -/(1-)), No(s, No(s, a,) No(s) t 0 for all E S, E A, E
2: for step t 1.... do
3: Let (-) & argmax Qe(:,a), take action as + (s and receive next state S141
P(-ss,, az)
4: Set Ne(x) +- Nr-1(s), Ni(8,a) N2-1(8, and Ne(s,a,8) + Ne-1 8') for all
8 SES,a E A, ES
5: Update (1(8)) t- N((8)) + 1, (1 + ae) + and (1 (1,
Ni at, 8141)+ +1
6: For all s 8, E A, set
Pr(s'(s,a) = Ni(s,a,s))
(4.1)
Nr(s,a)
7: Update new value function Q1+1 and (s+ by + [P. )
Q++1(s, a) min (Q:(s,a), r(s,a) +
Vi-(()) max (s,
(4.2)
where
SU Va (Vi(s'))
8U/(1-))
UCB)(8,a)= =
V1
Ni(s, 0) VI
S. Pi('ls,)) (100
(4.3)
N1(s,a)
and B,(s') (M
8: end for
Computational complexity In each step f, Algorithm needs to first compute the empirical transition P, and update the value function V++1 by one-step value iteration, which will cost O(S² A) time complexity for each update. However, the number of updates can reduced by using the "batch" update scheme adapted in [10, 7] and in this case Algorithm only needs to update the value function V++1 when the number of visits Nr(s, a) doubles. With this update scheme, the number of updates is upper bounded by O(S A log 7') and the total cost for updating the value function is O(S3 A² log T). In addition, the Algorithm still needs to choose the action with respect to the value function V22 and it costs (AAT) time complexity. Thus. the total computation complexity of the "batch" version of Algorithm is O(AT + $3 A² log
4.2 Regret Analysis
In this subsection, we provide the regret bound of UCBVI-?. We first give the formal definition of the regret for the discounted MDP setting.
Definition 4.1. For a given non-stationary policy æ, we define the regret Regret(T)) as follow:
Regret(T) Σ (7
The same regret has been used in prior work [30, 35, 34] discounted MDPs. It is related the "sample complexity of exploration" [12, 14, 9]. For more details about the connection between the regret and the sample complexity, please refer Appendix A.
Remark 4.2, Without the use of generative model [12], an agent may enter bad states at the first few steps discounted MDPs there is no "restarting" mechanism as in episodic MDPs that can prevent the agent from being stuck in those bad states. Due to this limitation, both the regret and the sample complexity of exploration guarantees are not sufficient to ensure good policy being learned. We think this is the fundamental limitation in the online learning of discounted MDPs.
5

---

With Definition 4.1, we introduce our main theorem, which gives an upper bound on the regret for UCBVI-
Theorem 4.3. Let U log(40SAAT log T -))))) If we set 3 5 in UCBVI-% then with probability least 1 8, the regret of UCBVI-y in Algorithm is bounded by
7525 13.
G0UvSAT AvTU
Regret(T)
(1 (1-7)3.5
(1 7)1.5
(1 (1-7)2²
Remark 4.4. Notice that when T = 5255 A2/(1 7) and SA = (111(1(11)) - -)), the regret is
bounded by (1VSAT(1-7)44) In addition, since Regret(T) I T/(1 ->) holds for any T, we have E [eggrtt) = O(V/ATT(C (LL 7). + T6/1 - 7). When choosing å = 1/T, we have B|Regret =
We also provide regret lower bound, which suggests that our UCBVI-y nearly minimax optimal. Theorem 4.5. Suppose 2 30 and T 2 100SAL/(L 7)², then for any algorithm, there exists an MDP such that
VSAT E[Regret(T)] 10000(1 71.33
4VSTT. (1 (1-7)1.5 71-
85
where L log
-1-/)/11)))))))))) log
Remark 4.6. When large enough and A = (1). Theorem 4.5 suggests that the lower bound of regret is STVVS//T//T (11 1.G). It can be seen that the regret of UCBVI-y in Theorem 4.3 matches this lower bound up to logarithmic factors. Therefore, UCBVI-y nearly minimax optimal.
Proof of the Main Results
In this section, we provide the proofs of Theorems 4.3 and 4.5. The missing proofs are deferred to the appendix.
5.1 Proof of Theorem 4.3
1og2 In this subsection, we prove Theorem 4.3, For simplicity, let 8' = (1 - (1--))2/(807)) ( log T). then
U log(SAT2 /8"). We first present the following key lemma, which shows that the optimal value functions V and Q" can be upper bounded by the estimated functions Vú and Q with high probability:
we Lemma 5.1. With probability at least 1 - 64Tölog 1 - ()), for all t [T] S, A. we have Qr(s, a) 2 (s, Vi(s) 2 (s).
Equipped with Lemma 5.1, we can decompose the regret of UCBVI-y as follows:
Regret(1 (T) [V((s.) - (st) = (Q((), - Q7 (st.
Regret' (T)
where the inequality holds due to Lemma 5.1. Therefore, suffices to bound Regret' (T). We have
Regret' (T) <
((()) + ( ax) CyUCB,-1(ss.))
t=
r(81, - -
(1IP CUUCB. (C,,--ii at) -
where the inequality holds due to the update rule (4.2) and the Bellman equation Q (St. 01)
r(st, az) + (PV v4 [st, az). We further have
Σ (PP Vo- [3s,, ar) (+r, - -PPVV

---

(V221(800+1 -
+
7 - (sr)
T
T
+
7(P P) az)
+
CyU,
I
(s - (V VA (s(+1)
(5.1)
In the above decomposition, term / controls the estimation error between the value functions V and V terms 12 and 13 measure the estimation error between the transition probability function and the estimated transition probability function Pr-1, term I4 comes from the exploration bonus in Algorithm and term Is accounts for the randomness the stochastic transition process, which can be controlled by the third term O OVVTU/U /(1 7) in Theorem 4.3.
In the remaining of the proof, it suffices to bound terms I to Is separately.
First, J can be regarded as the difference between the estimated V and the value function V of policy т, and it can bounded by the following lemma.
Lemma 5.2. For the term 4t We have 41 S ?Regret' (I) + (2S + 2)7/1 -y
Next, 12 can be regarded as the "correction" term between the estimated V2-1 and the optimal value function V*h It can bounded by the following lemma.
Lemma 5.3. With probability least 1 6478log T/(1 -7) - -38, we have
"rPAAClo(SS/// log(3T)
log))
12 S (1-7)) (T) (2TClog(1/8)
(1-7)²
In addition, I3 can be regarded as the error between the empirical probability distribution P.-1 and the true transition probability P.. Note that V* is fixed value function that does not have any randomness. Therefore, T3 can be bounded through the standard concentration inequalities, and its upper bound is presented in the following lemma.
Lemma 5.4. With probability least
28
5/(1 (1) have
AS 1a < 1-7 UV2SA
5T
29U
2Regret' (T) +
V2TU
+
1-y
3(1 - 713
7)2
Furthermore, 14 can be regarded as the summation of the UCB terms, which is also the dominating term of the total regret. It can be bounded by the following lemma. Lemma 5.5. With probability least 1
46 5/(1 ()), we have
5T
12SU 3(1 ((1-2)) 7)3 + 2Regret' (T)
29U
I < (1 (1-7)2.5 + UV8SA
1-
(1- 7)
Finally, I5 is the summation of a martingale difference sequence. By with probability at least 8, we have
inequality,
2T log
Is S
(5.2)
1-7
Substituting the upper bounds of terms /1 to Is from Lemma 5.2 to Lemma 5.5, as well as (5.2), into (5.1), and taking a union bound let all the events introduced in Lemma 5.2 Lemma 5.5 and (5.2) hold, we have with probability at least 1 20TU25/(1 7)2 the following inequality holds:
A6
54U SAT
SAT
2V2TU
SARegret (T)
- Regret' (T)
12U
(1 215
11
1 1-7
1 ?
(5.3)

---

Using the fact that 2 S a <a+bvI+ I 1.la + 4b², (5.3) can be further bounded as follows
(Tg - Regret (T)
7525 A
600 VSAT
AVTU
7/3.5
(1 7)1.
(1 11-99 (1-
This completes our proof.
Proof Theorem 4.5
+
$1,0
11,1
$2,0
$2,1
1-7
85.1
85.0
85-1,1
85-1.0
Figure 1: A class of hard-to-learn MDPs considered in Theorem 4.5. The MDP can be regarded as combination of two-state MDPs, each of which is an MDP illustrated on the top-left corner. In addition, the i-th two-state MDP has the a. -th action its optimal action. The blue arrows represent the optimal actions in different states.
((1 7)/K 1/4/
In this subsection, provide the proof of Theorem 4.5. The proof of the lower bound is based on constructing class of hard MDPs. Specifically, the state space consists 2S states {si,o= $1,1 ke(s) and the action space contains actions. The reward function r satisfies that r(s,,o, a) = 0 and r(st,1,0 for any A, [S]. The probability transition function IP is defined as follows.
A(1 7)
P(s a) = -1-1 - a===;
24 V
(((L,,)S,,1, %
K
1 A(1 - 7)
P(sL.o/s,,0,) a) =7 7 La=o;
(P($5+11055,1111 =1 %
24
K
where we assume 85+1.0 = 81,0 for simplicity and at is the optimal action for state 81.0- The MDP illustrated in Figure which can be regarded as S copies of the "single" two-state MDP arranged in a circle. The two-state MDP is the same as that proposed has two states and one "optimal" action at satisfied (P( $5,0, a²) 1 + Compared with the MDP instance in [10], both instances use copies of a single MDP. However, unlike MDP in [10] which only has one "optimal" action among all S.A actions, our MDP which has in total S "optimal" actions, which makes it harder to analyze.
[15]. Each of the two-state MDP
Now we begin to prove our lower bound. Let [:] denote the expectation conditioned on one fixed selection of a'
az)). We introduce a shorthand notation E to denote [+[ 1/AS Earess Ex [:]. Here E" is the average value of expectation over the randomness from MDP defined by different optimal actions. From now on, aim lower bound E* [Regret(T)), since once E* (Reegret(T)) is lower bounded, E [[Regret(T)) can be lower bounded by selecting ai....,d a' which maximizes E E(Regret(T)). We set T 10SK in the following proof. Based the definition of E", we have the following lemma.
Lemma 5.6. The expectated regret EE EE' ["eegrett))) can be lower bounded follows:
T
r(st, oz)
Ex [*egrett 2 E
V*(8t)
1
(1 7)
8

---

which is Regret-" defined in [15]. When an agent visits the state set 18,00.8,11 for the i-th time, we denote the state in {85.0. $j,1 } it visited as j, and the following action selected by the agent as A Let 7 be the number of steps for the agent staying in (83.0, 83,1) } in the total 7 steps. Then the regret can be further decomposed as follows:
By Lemma 5.6, it suffices to lower bound
r(st,)
T
r(sr,
8
T3
r(X,,t, An (X,,)
(s))
11 + 1 + 13
1
1-7
1=1
where
8
K
r(X Ajai)
1 Σ
E
(X,,)
1-?
j=1
8
(xX,,1AA,.)) 1-7
1/2
Σ E
Σ V'(X,,))
T3>> > K PP > K],
J=1
i=K+1
13
S Σ f=1
E
Σ
K
V*(X,))
r(X Asae)
Tj K k]
[T K].
1-7
1=1,+1
Note that / essentially represents the regret over S two-state MDPs in their first K steps, and it can be lower bounded through the following lemma.
Lemma 5.7. K 2 10SA/(1 - -) then for each j E [S], we have
K
VAK
1
E*
Σ (1 - (x)))
2304 V
This lemma shows that the expected regret of first K steps on states 85.0 and 8311 is at least ((VAK/(1 (1//(111)))) 21-5) 1/(1 7)). Therefore by Lemma 5.7, have
8
K
r(X,,,, Agú))
VSAT 2304 10(1 7)15
S
1
Σ 1=1
E
Σ (x
(5.4)
1-y
(1 (1-7)2²
To bound I2, we need the following lemma.
Lemma 5.8. With probability least 1 -2ST5 log T/(1 7), for each j E (S) and K +1 SIST,
we have
r(xi,, Aja)
21 10g(g(11// log/ T
4
Σ vX) k=
1-7
(1-7)1.3
(1 - 7)2
Lemma 5.8 gives crude lower bound of Iz- summation over all states, we have
Taking expectation over Lemma 5.8 and taking
9 E"
(
2T, log( (10)) log)
(1 (1- )
4 T₁> K PTT > K
1
1.55
j=1
8
T
2STölog T (1-7)2
1-7
j=1
9
V 2T, log (1/0) log (1 - 1.5
4$
2.2T log T
Σ
E
(1 71-
(1 7)
1=1
3
21E* (Ty) log
1og(1110 (1/5) log
4S
252T2 log T 71-7)3
(1 1.5
(1 11-79 7)2
1=1

---

/2ST 1og(1/6) log
45
2
(5.5)
(1 (1.5)1.5
(1- (1 -1)
where the first inequality holds due Lemma 5.8, the second inequality holds since 22T5 T/(1 -2) I 1 and E[-X|Y]P(Y) 2 B[-X] when X 2 0, the third inequality holds due to Jensen's inequality and the fact that vI a concave function, and the last inequality holds due to Jensen's 's incquality and the fact that Σ}=1
=j=1 E [T]] = T.
J To bound 13. we need the following lemma,
which suggests that when is large enough, T; > K happens with high probability:
Lemma 5.9. When K 2 10Alog(1/0)(1 7)*, with probability at least 256, for all E (S). we have T; > K.
Notice that the difference of transition probability between the optimal action and suboptimal actions VA(1 - 7) /24K In this case, when T' is large enough, Ta is close T/S 10K. Thus I3 can be lower bounded as follows:
8 Σ ==1
K
ST5
12
PT
<
K 2
(5.6)
5(1 (1)
where the first inequality holds due to 0 S r (x 1 A4.)) S and the second incquality holds due we can verify that the requirements
to Lemma 5.9. Finally, setting 6 = ( (1- of K' in Lemma 5.7 and Lemma 5.9 hold when T satisfies T > 100S.AL(( () and L log 1,00$$22/(1) 7)) log T. Therefore, substituting 5 = 11/44572 - 7) log 7) into (5.5)
and (5.6), and combining (5.4), (5.5), (5.6) and Lemma 5.6, we have
VSA E [[Regret 10000(1 - 7211 (1 (1-7)15
4VSTL
88
71-
which completes the proof of Theorem 4.5.
6 Conclusions and Future Work
We proposed UCBVI-?, online RL algorithm for discounted tabular MDPs. We show that the regret of UCBVI-y can be upper bounded by Ö(VSAT/(L - 7)5- and we prove matching lower bound on the expected regret ((VSSAAA (IVVAAT/(/ (1-7)--5) There still gap between the upper and lower bounds when T < 5 A3 (11 7) SSA(L y)*}. and we leave it as an open problem for future work.
Acknowledgments and Disclosure of Funding
We thank Csaba Szepesvári for a valuable suggestion on improving the presentation of the proof. We thank the anonymous reviewers for their helpful comments. JH, DZ and QG are partially supported by the National Science Foundation CAREER Award 1906169, 19S41994183. BIGDATA IIS- 1855099 and AWS Machine Learning Research Award. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
[1] AGARWAL, A., KAKADE, S. and YANG, L. F. (2019). Model-based reinforcement learning with a generative model is minimax optimal. arXiv preprint 1906v:1906.030
[2] AYOUB, A., JIA, Z., SZEPESVARI, C., WANG, M. and YANG, L. F. (2020). Model-based reinforcement learning with value-targeted regression. arXiv preprint arXiv:2006.01107.
[3] AZAR, M. G., MUNOS, R. and KAPPEN, H. J. (2013), Minimax pac bounds on the sample complexity of reinforcement learning with generative model. Machine learning 91 325-349.
[4] AZAR, M. G., OSBAND, and MUNOS, R. (2017). Minimax regret bounds for reinforcement learning, In Proceedings of the 34th International Conference on Machine Learning- Volume 70. JMLR. org.
[5] BRAFMAN, R. I. and TENNENHOLTZ, M. (2002). R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research 3 213-231
10

---

[6]
N. and LUGOSI, G. (2006). Prediction, learning, and games. Cambridge university press.
[7] DANN, C. and BRUNSKILL, E. (2015), Sample complexity of episodic fixed-horizon reinforce- ment learning, In Advances in Neural Information Processing Systems.
[8] DANN, C., LI, L.,, WEI, W. and BRUNSKILL, E. (2019). Policy certificates: Towards account- able reinforcement learning. In International Conference on Machine Learning. PMLR.
(9] DONG, K., WANG, Y., CHEN, X. and WANG, L. (2019). Q-learning with ucb exploration is sample efficient for infinite-horizon mdp. arXiv preprint arXiv: 1901.0931
[10] JAKSCH, T., ORTNER, R. and AUER, (2010). Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research 11 1563-1600.
[11] JIN, C., ALLEN-ZHU, Z., BUBECK, S. and JORDAN, M. I. (2018). Is q-learning provably efficient? In Advances Neural Information Processing Systems.
[12] KAKADE, S. M. ET AL. (2003). On the sample complexity of reinforcement learning. Ph.D. thesis, University of London London, England.
[13] KEARNS, M. J. and SINGH, S. P. (1999). Finite-sample convergence rates for q-learning and indirect algorithms. In Advances in neural information processing systems.
[14] LATTIMORE, T. and HUTTER, M. (2012). Pac bounds for discounted mdps. In International Conference Algorithmic Learning Theory. Springer.
[15] LIU, S. and SU, H. (2020). Regret bounds for discounted mdps.
[16] MAURER, A. and PONTIL, M. (2009). Empirical bernstein bounds and sample variance penalization. arXiv preprint arX7v:0907.3740.
[17] NEU, G. and PIKE-BURKE, C. (2020). A unifying view of optimism in episodic reinforcement learning. arXiv preprint arXiv:2007.0189/
[18] OSBAND, I. and VAN ROY, B. (2016). On lower bounds for regret in reinforcement learning. arXiv preprint arXhv:1608.0273:
[19] OSBAND, and VAN ROY, B. (2017). Why is posterior sampling better than optimism for reinforcement learning? In International Conference on Machine Learning.
[20] PACCHIANO, A., BALL, P., PARKER-HOLDER, J., CHOROMANSKI, K. and ROBERTS, S. (2020). On optimism in model-based reinforcement learning. arXiv preprint arXiv:2006. 1991
[21] Russo, D. (2019). Worst-case regret bounds for exploration via randomized value functions. In Advances Neural Information Processing Systems.
[22] SIDFORD, A., WANG, M., WU, X., YANG, L. F. and YE, Y. (2018). Near-optimal time and sample complexities for for solving discounted markov decision process with generative model. arXiv preprint 1Xxx:1806.00499
[23] SIDFORD, A., WANG, M., WU, X. and YE, Y. (2018). Variance reduced value iteration and faster algorithms for solving markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithmss. SIAM.
[24] SIMCHOWITZ, M. and JAMIESON, K. G. (2019). Non-asymptotic gap-dependent regret bounds for tabular mdps. In Advances Neural Information Processing Systems.
[25] STREHL, A. L.. LI, L., WIEWIORA, E.,, LANGFORD, J. and LITTMAN, M. L. (2006). Pac model-free reinforcement learning. In Proceedings of the 23rd international conference on Machine learning.
[26] STREHI., A. I. and LITTMAN, M. I.. (2008). An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences 74 1331-1331.

---

[27] SZITA, I, and SZEPESVÁRI C. (2010). Model-basee reinforcement learning with nearly tight exploration complexity bounds.
[28] WAINWRIGHT, M. J. (2019). Variance-reduced q-learning minimax optimal. arXiv preprint arXiv:1906.04697.
[29] WANG, M. (2017). Randomized linear programming solves the discounted markov decision problem in nearly-linear running time. arXiv preprint orXiv:/704.. (eee:010448000 01860.
[30] YANG, K., YANG, L. and Du, (2021). Q-learning with logarithmic regret 1576 15844
[31] ZANETTE, A. and BRUNSKILL, E. (2019). Tighter moblem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. arXiv preprint arXiv:1901.002100
[32] ZHANG, Z., ZHOU, Y. and J1, X. (2020). Almost optimal model-free reinforcement learning via reference-advantag decomposition. arXiv preprint arXiv:2004. 10019.
[33] ZHANG, Z., ZHOU, Y. and J1, X. (2020), Model-free reinforcement learning: from clipped pseudo-regret to sample complexity. arXiv preprint arXiv:2006.03866
[34] ZHOU, D., GU, Q. and SZEPESVARI, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In COLT.
[35] ZHOU, D., HE, J. and GU, Q. (2021). Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning. PMLR.
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] We discuss the limitations and potential future works in Section 6
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work provides a theoretical analysis discounted MDPs, and there is no potential negative social impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofss of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
12

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "nSIY3tXrUBv", "reviewer": "Reviewer_bvo4", "summary": "This paper closes the gap betewwn upper and lower bounds for regret of tabular discounted MDPs. In particular, it proposes UCBVI-$\\gamma$ algorithm that achieves regret of $\\widetilde{O}\\left(\\frac{\\sqrt{SAT}}{(1-\\gamma)^{1.5}}\\right)$ and constructs a class of hard MDPs such that any algorithm will have expected regret at least $\\widetilde{\\Omega}\\left(\\frac{\\sqrt{SAT}}{(1-\\gamma)^{1.5}}\\right)$.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Overall, although the techniques used do not seem to be very novel, I consider the results of this paper as a significant progress on tabular disconted MDPs. Meanwhile, the writing of this paper is also clear and easy to follow.\n\nQuestions:\n- On page 9, how you show that $$\\mathbb{E}\\left[\\sum_{i=K+1}^{T_j}V^*(X_{j, i})-\\frac{r(X_{j, i}, A_{j, i})}{1-\\gamma}\\mid T_j>K\\right]\\geq -T,$$ or more specifically, $V^*(X_{j, i})-\\frac{r(X_{j, i}, A_{j, i})}{1-\\gamma}\\geq -1$?\n\n---\n\nGood paper. Score remains the same after rebuttal.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitation of their work in Section 6 by pointing out the requirement on $T$ for their algorithm to be nearly optimal. The potential negative social impact is not addressed, which is not so needed for a purely theoretical analysis on tabular MDPs.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "gebPzvGSDM", "reviewer": "Reviewer_2f6X", "summary": "The authors study the problem of learning a discounted tabular-MDP. They adopt a notion of regret that is closely related to policy identification problem.\n\nThe authors make two main contributions:\n1. They show how to adapt UCBVI to discounted MDP. This lead to an algorithm called UCBVI-\\gamma algorithm. This model-based algorithm uses OFU principle by computing Bernstein-type bonus for empirical Q-function. The policy of the algorithm is updated every time step (online algorithm).  The author prove that its regret is upper bounded by \\tilde{O}(\\sqrt{SAT}/(1-\\gamma)^1.5) where \\gamma is the discount factor.\n\n2. The authors also derive a minimax lower bound for the problem that essentially match the upper bound of the algorithm {\\Omega}(\\sqrt{SAT}/(1-\\gamma)^1.5). This shows that their algorithm is minimax-optimal.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "In summary, I found that the main result is strong but the paper is a bit incremental. I find the result strong because compared to previous work, the paper closes the gap between the lower and upper bound for discounted MDPs (more precisely, the the order of the two bounds provided are the same up to logarithmic factors and [huge] constants). That being said, the algorithm to obtain the upper bound is essentially a variant of UCBVI. I found the counter-example for the lower bound more original.\n\nThe definition of the regret seems adapted for disconted MDP. It is the sum over time steps of the differences between the optimal expected return of an optimal policy and the expected return of the computed policy, both at current states. As indicated it is closely related to policy identification but only for those states. I am wondering if it make sense as those states might not be representative of the whole MDP. Would it make sense to restart the MDP from time to time (for instance after a geometrically distributed time?).\n\nAlso, there is no numerical simulations comparing the algorithm with other existing algorithms and no detail about algorithm's computational complexity.  My guess is that it is probably because, in practice, the proposed algorithm is not efficient: despite having order-optimal regret, the hidden constant in the O(.) are just huge. Hence, this algorithm has mostly a theoretical interest but not really a practical interest.\n\nThe sketches of proof for both theorems are convincing. The exposition of the paper is clear and the obtained result is nearly minimax optimal for tabular discounted MDPs. The literature review is well described.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors could comment on the practical use of the algorithm (numerical complexity and performance compared to related work).\n\nApart from the regret proof, is there a big difference with UCB-VI? It seems to be that UCBVI-\\gamma does not use episode. Is it the main difference?\n\nThe regret definition impliees that only the visited states will be well identified. Would an episodic approach with restart be more appropriate here?\n", "review_text": "", "extra_scores": {"ethical_concerns": "NA.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6GjInPm6fJF", "reviewer": "Reviewer_QtQ3", "summary": "This work studies the problem of learning stochastic discounted infinite-horizon Markov Decision Processes (MDPs) with unknown transition. The authors propose an algorithm UCBVI-gamma based on recent advances in episodic MDPs (e.g. Azar et al., 2017; Jin et al., 2018; Zanette and Brunskill, 2019) and specifically the Bernstein-type exploration bonus. Besides, the authors provide a lower bound which indicates that UCBVI-gamma matches the minimax lower bound up to logarithmic factors. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "1. Contribution\n\nIn this work, the authors propose the model-based algorithm UCBVI-gamma which achieves O(sqrt(SAT)/ (1-gamma)^1.5) regret, which matches the lower bound on the expected regret O(sqrt(SAT)/(1-gamma)^1.5). This is the first algorithm that matches the lower bound. The algorithm design is inspired from UCBVI-BF of Azar et al. (2017), which adopts a specific Bernstein-type exploration bonus. \n\nOn the other hand, although based on the hard two-state instance of Liu and Su (2020), the proof of the lower bound in Theorem 4.4 is novel and inspiring.  \n\n2. Weaknesses\n\nThe proving techniques and algorithm design of the upper bound are quite similar to that of previous works such as Azar et al. (2017) for UCBVI-BF. I am willing to reconsider my score if the authors could emphasize their own technical contributions in the proof of the upper bound. \n\nBesides, the third term in Theorem 4.2 and the decomposition of Eq (5.1) would benefit from more high-level explanations.\n\n3. Writing Issues\n\nline 262-336, the format of reference seems incorrect. It should not be numbered. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is pure theoretical and does not have any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "17"}, "extra_text": {}}, {"review_id": "1B96KY7uaYB", "reviewer": "Reviewer_3A7m", "summary": "This paper proposes a new model-based algorithm for tabular MDPs, and proves a upper bound and a lower bound on regret. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Pros:\nThe newly proposed algorithm enriches the collection of model-based algorithms. The power of $T$ in the upper bound on regret is decreased to 0.5 by this paper.\n\nCons: \nIn Section 6, it says \"There is still a gap between the upper and lower bounds when $T\\leq\\max\\{S^3A/(1-\\gamma)^4,SA/(1-\\gamma)\\}$.\" But Theorem 4.2 and Theorem 4.4 respectively require $T\\geq S^3A^2/(1-\\gamma)^4$ and $T\\geq SA/(1-\\gamma)^4$. Hence only when $T\\geq S^3A^2/(1-\\gamma)^4$, the upper bound matches the lower bound. In this case, where does $T\\leq\\max\\{S^3A/(1-\\gamma)^4,SA/(1-\\gamma)\\}$ in Section 6 come from? Furthermore, how restrictive is this condition on $T$? There seems no discussion about this in the paper.\n\nI've read the authors' response and updated my score accordingly. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper focuses on theoretical analysis. It's expected that the paper does not have direct negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the sample complexity of tabular (finite state/action) reinforcement learning in the infinite-horizon discounted setting, which is a fundamental problem in reinforcement learning theory. The main contribution is to provide improved upper and lower bounds on the optimal sample complexity (w.r.t, the dependence on the horizon parameter (1-gamma)^(-1)) which resolve the optimal sample complexity. The reviewers found these results to be interesting and technically non-trivial and recommend acceptance, but the authors are encouraged to take their suggestions into account and update the paper to better emphasize what the key analysis ideas and why they are novel.
Decision: Accept (Poster)