Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
Authors: Yuanhao Wang
Kefan Dong
Xiaoyu Chen
Liwei Wang
Venue:  (2020)
Keywords: theory
reinforcement learning
sample complexity

Abstract: A fundamental question in reinforcement learning is whether model-free algorithms are sample efficient. Recently,  Jin et al. (2018) proposed a Q-learning algorithm with UCB exploration policy, and proved it has nearly optimal regret bound for finite-horizon episodic MDP. In this paper, we adapt Q-learning with UCB-exploration bonus to infinite-horizon MDP with discounted rewards \emph{without} accessing a generative model. We show that the \textit{sample complexity of exploration} of our algorithm is bounded by $\tilde{O}({\frac{SA}{\epsilon^2(1-\gamma)^7}})$. This improves the previously best known result of $\tilde{O}({\frac{SA}{\epsilon^4(1-\gamma)^8}})$ in this setting achieved by delayed Q-learning (Strehlet al., 2006),, and matches the lower bound in terms of $\epsilon$ as well as $S$ and $A$ up to logarithmic factors.

Published as a conference paper at ICLR 2020
Q --EARNNING WITH UCB EXPLORATION IS SAMPLE EFFICIENT FOR SFFINIEE-HORIZA MDP
Kefan Dong', Yuanhao Wang" Institute for Interdisciplinary Information Sciences, Tsinghua University (dkf16, 6, yuanhao-16) 16] @ma i 1s. tssinguua........ edu cn
Xiaoyu Chen
Key Laboratory of Machine Perception, MOE, School of EECS, Peking University cxy300ple .er.ppkk..du..cmmmmmmmmom .cd.ccn
Liwei Wang
Key Laboratory of Machine Perception, MOE, School of EECS Center for Data Science, Peking University wanglw@cis. pku. edu.er.
ABSTRACT
A fundamental question in reinforcement learning is whether model-free algo- rithms are sample efficient. Recently, Jin et al.) (2018) proposed Q-learning algorithm with UCB exploration policy, and proved it has nearly optimal regret bound for finite-horizon episodic MDP. In this paper, we adapt Q-learning with UCB-exploration bonus to infinite-horizon MDP with discounted rewards without accessing a generative model. show that the sample complexity of exploration our algorithm is bounded by Ō ((1111))> This improves the previously best
known result Ó(Z(-))))) in this setting achieved by delayed Q-learning (Strehl et al., (006), and matches the lower bound in terms of as well as and A up to logarithmic factors.
INTRODUCTION
The goal of reinforcement learning (RL) is to construct efficient algorithms that learn and plan in sequential decision making tasks when the underlying system dynamics are unknown. typical model in RI. is Markov Decision Process (MDP). At each time step, the environment is in state s. The agent takes an action a, obtain a reward r, and then the environment transits to another state. In reinforcement learning, the transition probability distribution is unknown. The algorithm needs to learn the transition dynamics of MDP, while aiming to maximize the cumulative reward. This poses the exploration-exploitaaio dilemma: whether to act to gain new information (explore) to act consistently with past experience to maximize reward (exploit).
Theoretical analyses of reinforcement learning fall into broad categories: those assuming simulator (a.k.a. generative model), and those without simulator. In the first category, the algorithm is allowed query the outcome of any state action pair from oracle. The emphasis is the number of calls needed to estimate the Q value or to output near-optimal policy. There has been extensive research in literature following this line of research, the majority of which focuses on discounted infinite horizon MDPs (Azar et al. 2011 Even-Dar & Mansour, 2003, Sidford et al. 20186). The current results have achieved near-optimal time and sample complexities (Sidford et 201 8b a)
"These authors contributed equally.

---

Published as a conference paper at ICLR 2020
Without simulator, there is dichotomy between haite-horizon settings, there are straightforward definitions for both regret and sample complexity; the latter is defined as the number of samples needed before the policy becomes
and infinite-horizon settings. In
optimal. In this setting, extensive research in the past decade (Jin et al. 2018: Azar et al.] 2017 7 Jaksch et al. (0100) Dann al. (017) has achieved great progress, and established nearly-tight bounds for both regret and sample complexity.
The shrinite-horizon setting is very different matter. First of all, the performance measure cannot be a straightforward extension of the sample complexity defined above (See Strehl & Littman (2008) for detailed discussion). Instead, the measure of sample efficiency we adopt is the so-called sample complexity of exploration (Kakade et al. 2003), which is also widely-accepted definition. This measure counts the number of times that the algorithm "makes mistakes" along the whole trajectory.
See also (Strehl& & Littman 2008) for further discussions regarding this issue.
Several model based algorithms have been proposed for infinite horizon MDP, for example R- max (Brafman & Tennenholtz 2003), MoRmax (Szita & Szepesvári 2010) and UCRL-y (Lattimore) Hutter 2012). is noteworthy that there still exists a considerable gap between the state-of-the-art
algorithm and the theoretical lower bound (Lttimooe & Hutter 2012) regarding 1/(1 7) factor.
Though model-based algorithms have been proved to be sample efficient various MDP settings, most state-of-ther of-tt--rrt RL algorithms are developed in the model-free paradigm (Schulman et al. 2015
Mnih et al. 2013] 2016). Model-free algorithms are more flexible and require less space, which have achieved remarkable performance benchmarks such as Atari games and simulated robot control problems.
For infinite horizon MDPs without access to simulator, the best model-free algorithm has sample complexity of exploration Ö $4 ((rri_))>)) achieved by delayed Q-learning (Strehl et al. 2006). The authors provide novel strategy of argument when proving the upper bound for the sample complexity of exploration, namely identifying a sufficient condition for optimality, and then bound the number of times that this condition is violated.
However, the results of Delayed Q-learning still leave quadratic gap in 1/ce from the best-known lower bound. This is partly because the updates in Q-value are made in an over-conservative way. In fact, the loose sample complexity bound is result of delayed Q-learning algorithm itself, as well as the mathematical artifact in their analysis. To illustrate this, we construct hard instance showing that Delayed Q-learning incurs ((1/e5) sample complexity. This observation, as well as the success of the Q-learning with UCB algorithm (Jin et al., 2018) in proving regret bound in finite-horizon settings, motivates to incorporate UCB-like exploration term into our algorithm.
In this work, we propose a Q-learning algorithm complexity of exploration bound of our algorithm is (><パー>)>> ). This strictly improves the previous best known result due to Delayed Q-learning. It also matches the lower bound in the dependence on and A up to logarithmic factors.
with UCB exploration policy. We show the sample
We point out here that the infinite-horizon setting cannot be solved by reducing to finite-horizon setting. There are key technical differences between these two settings: the definition of sample complexity of exploration, time-invariant policies and the eтror propagation structure in Q-learning. In particular, the analysis techniques developed in (Tin al., (018)) do not directly apply here. We refer the readers to Section 3.2 for detailed explanations and concrete example.
The rest of the paper is organized as follows. After introducing the notation used in the paper in Section [ we describe our infinite Q-learning with UCB algorithm in Section 3 We then state our main theoretical results, which are in the form of PAC sample complexity bounds. Section 4 we present some interesting properties beyond sample complexity bound. Finally, we conclude the paper Section 5
2 PRELIMINARY
We consider a Markov Decision Process defined by a five tuple (S.A,,. where S is the state space, AA is the action space, p(s'|s, (s, a) is the transition function, r: SSx - [0, the deterministic
2

---

Published as a conference paper at ICLR 2020
reward function, and y is the discount factor for rewards. Let S |S| and A |A|| denote the number of states and the number actions respectively.
Starting from state $1, the agent interacts with the environment for infinite number of time steps. At each time step, the agent observes state s, E S, picks action a, A, and receives reward ry; the system then transits to next state 81+-1-
Using the notations in Strehl et al. (2006), a policy тe refers to the non-stationary control policy of the algorithm since step We use (=((s) to denote the value function under policy Te, which is defined as V* (s) = E - ((8, T (1:+s=1(())){)))
s]. We also use V*(s) = sup, V*(()) to denote the value function of the optimal policy. Accordingly, we define QT (s. a) r(8, a)
E| r me+i-1 1 ( [s{ = = al as the Q function under policy Te; (s, a) is the Q
function under optimal policy x².
We use the sample complexity of exploration defined in Kakade et al. (2003) to measure the learning efficiency of our algorithm. This sample complexity definition has been widely used in previous works Strehl et al. (2006); Lattimore & Hutter 2012); Sttehl & Littman (2008).
Definition 1. Sample complexity of Exploration of algorithm ACG is defined as the number of time steps such that the non-stationary policy ne at time t is not c-optimal for current state 8t, Lee. VTe (st) V* (
Roughly speaking, this measure counts the number of mistakes along the whole trajectory. We use the following definition of PAC-MDP Strehl al. (2006).
Definition 2. An algorithm ALG is said to be PAC-MDP (Probably Approximately Correct in Markov Decision Processes) if. for any and 6, the sample complexity of ACG is less than some polynomial in the relevant quantities (S, A, 1/e, 1/8, 1/(1 - 7)), with probability least 6.
Finally, recall that Bellman equation is defined as the following:
{ (T* Q. (s, (s)) @T == (r+ + yPP (s,a),
{
V*(s) Q" (s, (s(s = (rt + +
which is frequently used in our analysis. Here we denote [PV*[] (s, == (s V (s').
3
MAIN RESULTS
In this section, we present the UCB Q-learning algorithm and the sample complexity bound.
3.1
ALGORITHM
Algorithm Infinite Q-learning with UCB
Parameters: c, Y,
Initialize ((s. a), Q(s, a) 1 N(s,a) +- 0,
24RM In r. H
In 1n1/((1-)))
1-7 In1/7
Define (k) = In(SA(k + 1)(k + ax = H+1
H44"
for = do
5: Take action 0e +- arg max Q(sr,a)) a²)
Receive reward r, and transit 8,41 N a.) + (st, or) +1
k k- N(st,, by - 1 1 Hi(k) -
C2 is constant and can be set 4v2
((++1) m (()=)11))
a(s,, t (1 ax ax))(ssr ar) + an a() + by (s(+1))
10:
Q(s), t min((((s), ax), a().
end for
Here 02 4v2 a constant. IIn /11 7)1, while the choice of M can be found in (M = O (In (In1/((1 - )))))) The learning rate is defined as = (Hl + 1)/(H + k). 1n11((1-))s)) which satisfies H < la ((())))))
Section. 3.3
H is chosen
In 1/7
3

---

Published as a conference paper at ICLR 2020
Our UCB Q-learning algorithm (Algorithm 1) maintains optimistic estimation of action value function Q(s, a) and its historical minimum value (s, (s, a) denotes the number of times that (s, a) is experienced before time step i; 7(8, a, k) denotes the time step at which (8t, a+) = (8, a) for the k--th time; if this state-action pair is not visited that many times, 7(s, a, k) = xc. (s(s, a)
and (s a) denotes the Q and Q value of (s, that the algorithm maintains when arriving at st respectively.
3.2 SAMPLE COMPLEXITY OF EXPLORATION
Our main result is the following sample complexity of exploration bound.
Theorem 1. For any > 0, 8 > 0, 1/2 < < 1, with probability 1 1-6 8. the sample complexity of exploration (i.e., the number of time steps such that we is not e-optimal se) of Algorithu is at most
SAIn 1/0
21 711)))²
where Ô suppresses logarithmic factors of 1/c, 1/(1-11 and SA.
We first point out the obstacles for proving the theorem and reasons why the techniques in Jin et al.) (2018) do not directly apply here. We then give high level description of the ideas of approach.
One important issue is caused by the difference in the definition of sample complexity for finite and infinite horizon MDP. In finite horizon settings, sample complexity (and regret) is determined in the first T timesteps, and only measures the performance at the initial state 81 (i.e. (V* - (si())) )). However, in the infinite horizon setting, the agent may enter under-explored regions any time period, and sample complexity of exploration characterizes the performance at all states the agent enters.
The following example clearly illustrates the key difference between infinite-horizon and finite- horizon. Consider an MDP with a starting state $1 where the probability of leaving 81 is o). In this case, with high probability, it would take more than T timesteps to leave $1 Hence, guarantees about the learning the first T timesteps or about the performance at 8 imply almost nothing about the number of mistakes the algorithm would make in the rest of the MDP (i.e. the sample complexity of exploration of the algorithm). As a result, the analysis for finite horizon MDPs cannot directly applied to infinite horizon setting.
This calls for techniques for counting mistakes along the entire trajectory, such as those employed by Sttrhl et al. (2006). In particular, we need to establish convenient sufficient conditions for being e-optimal at timestep t and state 8t, i.e. (*,s,) - V* (st) < e. Then, bounding the number of violations of such conditions gives bound sample complexity.
2018)) cannot be directly applied to our problem is the following: In finite horizon settings. Jin et al. 2018 decomposed the learning error episode k and time h as errors from a set of consecutive episodes before k at time h + using a clever design of learning rate. However, time the agent is at state 8, and takes action Gr. Then the learning error at t only depends on those previous time steps such that the agent encountered the same state 8 and took the same action as a, Thus the learning eтror at time f cannot be decomposed as errors from set of consecutive time steps before t. but errors from a set of non-consecutive time steps without any structure. Therefore, we have to control the sum of learning errors over an unstructured set of time steps. This makes the analysis more challenging.
Another technical reason why the proof in Jin et al.
the infinite horizon setting, this property does not hold. Suppose at
Now we give brief road map of the proof of Theorem 1 Our first goal is to establish a sufficient condition so that गe learned at step / is e-optimal for state 8t. As an intermediate step we show that a (x"(""p, (xx))ar)) is small for few time steps within an interval [t. + R] for a carefully chosen R (Condition I). Then we show the desired
sufficient condition for V* V*(s.) V= (sx) < is that V*(sz)
sufficient condition (Condition 2 implies Condition []] We then bound the total number of bad time
steps on which (s,) Q* 0,) is large for the whole MDP; this implies a bound on the number of violations of Condition 2 This in turn relies on key technical lemma (Lemma
4

---

Published as a conference paper at ICLR 2020
The remaining part of this section is organized as follows. We establish the sufficient condition for e-optimality in Section 3.3 The key lemma is presented in Section 3.4 Finally we prove Theorem !
in Section 3.5
3.3
SUFFICIENT CONDITION FOR C-OPTIMALITY
In this section, we establish sufficient condition (Condition 2 for c-optimality at time step
For fixed 8;, let TRAJ R) the set of length- trajectories starting from 8t. Our goal to give sufficient condition that Tr, the policy learned step t. is e-optimal. For any e2 0, define R [In / 7)]. Denote V*(ss) - Q" (st, at) by A,. We have
(*(s)) (st)
=V*(s)) (8t) - Q* at) + (s) 0z) - (se)
=V*(st - Q'(8), at) + (V' - V**) (x(;
-V*((s) Q* a4) + Σ (88411106, (V ($1+1) 01st)11
Σ
p (8442)841,, (x1 p0 (V
(8142) - (1442)
Bc+1 1942
R-1 Σ
Sez +
Σ p(traj)-
Acts
(1)
TrajE (RAI(R)
where the last inequality holds because 1 S E2, which follows from the definition of R.
For any fixed trajectory of length starting from 8t, consider the sequence (Ar) Let x( be the i-th largest item of (Ae )ige Rearranging Eq. we obtain
(*(s)) (st) S c2
Etras
(8)
first prove that Condition
Iimples e-optimality at time step when E2 = e/3.
Condition 1. Let & = 2 62 In -
For all 0 sis [logz RJ.
E SE
(3)
Claim 1. If Condition is satisfied at time step i, the policy ne is c-optimal at state 85, iee. V*(st) V S.c.
Proof. Note that X is monotonically decreasing with respect i. Therefore, E[x(0] <
E[x ")) J.. Eq. 3 implies that for 1/2 < 1,
R
R
x
(1)
<
x
1=1
i=1
R
R
7
- 2 Llog, {) 2
In
In
222
i
1-
where the last inequality follows from the fact that 500
1-1
In
and 1/2.
7
1-7
Combining with Eq. we have, V*(*)) - V (x(())) 5
E
- x(xx))
3 =
5

---

Published as a conference paper at ICLR 2020
Next show that given i, Condition implies Eq. (3)
Condition 2. Define L [log2 RJ. Let M max 2 (. 1, 10} and ny 12 -2
For all j S M, Ti Pr[ (2")
πΙ nn S M
Claim 2. Given i, Eq. holds if Condition is satisfied.
Proof. The reason behind the choice of M is to ensure that 7M assuming Condition holds, for S S M,
1/(1 7) |
It follows that,
1/(1->)
E
X (2')
Pr [((2)
(2')
dz S m +
Σ f=2
ny Pr[x, (2)
-
Therefore, a time step is not e2-optimal, there exists 0 i [log2 RJ and 2 2 M such that
My Pr[x m1 n &
Now, the sample complexity can be bounded by the number of (f, i, pairs that Eq. (4) is violated. Following the approach of Strehl et al. (2006). for a fixed (i,j)-pair, instead of directly counting the number of time steps such that Pr[x,"' 1/-1]
e we count the number of time steps that
May
x(22)
M--1- Lemma provides upper bound of the number of such t.
3.4
KEY LEMMAS
In this section, present two key lemmas. Lemma bounds the number of sub-optimal actions, which in turn, bounds the sample complexity of our algorithm. Lemma bounds the weighted sum of learning error, i.e. (Q: - Q*) a), with the sum and maximum of weights. Then, we show that T from Lemma
Lemma 1. For fixed and 1) > let ( be the event that V*((s) (st,,, > 1 step If > 26,, then with probability at least 1 - 6/2,
Σ1(B()
SAmSAhi 1/88
ppolylog
1 1
(5)
r1 7)3
6 1''1-7
where [[-] is the indicator function.
Before presenting Lemma we define a class of sequence that occurs in the proof.
Definition 3. sequence (w4)221 said to a (C, w) sequence for C, > 0, if0 we S w for
all 2 1, and Σ1z1 Wa < C.
Lemma 2. For every (C, u) -sequence (we))21, with probability - -/2,, the following holds:
Cei +0 1-7
VuSAACICC) wSAInC (1-7)23
Σ wy wx( (s), 121
(1 21- - (1-7)c
where E(C) ((C) In [া-クパ a log-factor.
Proof of Lemma 2 is quite technical, and is therefore deferred to supplementary materials.
7M 1/(1- -Y) can be verified by combining inequalities G M/2 2 1/(1 -r) and M/2-1 (M +1) for large enough M.

---

Published as a conference paper at ICLR 2020
Now, we briefly explain how prove Lemma with Lemma 2 (Full proof can be found in supplementary materials.) Note that since Q 2 Q" and az arg max, Qe(st,
(s:) (* at) _ Qr az)
(s).
We now consider a set J = [t: (s:) (*( az) > sn(1 -))- and consider the (|7), 1)- weight sequence defined by we = [ J/. We can now apply Lemma to weighted sum E W/ (V+(s)) Q (st, dz)]. On the one hand, this quantity is obviously at least [J|m -)-
On the other hand, by lemma 2 it is upper bounded by the weighted sum of (Q Q*) oz). Thus we get
(lm(1-7) Ca +0
[SAJ]R(()) (1-7)25
WSAIn J
In
(1- (1 7)
Now focus on the dependence on JJ. The left-hand-side has linear dependence on |J] whereas the left-hand-side has a Ô (v[J)
dependence. This allows us to solve out an upper bound on |J| with
quadratic dependence on 1/n.
3.5
PROOF FOR THEOREM
We prove the theorem by stitching Lemma I and Condition 2
Proof. (Proof for Theorem 1)
By lemma for any 2 s j s M, E [[( - (' n/511 S C, where
C SA In 5A 1/5 PP.
(6)
11 7)5
Here P is a shorthand for polylog
1 T
Let A, -[x 2 n1-1 be Bernoulli random variable, and (Felez1 be the filtration generated by random variables ((s,, ar) 1 S St. Since At is -reasuurrbbll.. for any 0 S k < R. {AR+ER E[Ax+en [Ften] h22 is martingale difference sequence. For now, consider fixed
0 S k < R. By Azuma-Hoeffice inequality, after T O
C Ma: In(RML)) time steps (if it E.
2
happens that many times) with
Pr (x EHR 2 1 E[A >
(2)
&
Mn,'
we have Ae+RR 2 C/2' with probability at least 1 8/(2MRL).
On the other hand, if ARteR happens, within [k + tR, k + tR + R - 1]. there must be at least 2' time steps at which V*
Q" (s), > 7T-1- The latter event happens most C' times, and [k + LR, k + LR + R are disjoint. Therefore, E ARteR S C/22.. This suggests that the event described by (7) happens at most T times for fixed i and j. Via a union bound on 0 << k < R, we can show that with probability 1 - 8/(2ML), there are at most RT time steps where Mij
Pr X
(/( Thus, the number of sub-optimal steps is bounded by,
TV (st)
V (st) > c)
L M
M
15 Pr(x 11
&
Pr(x(e))
& M M
M
1=0
f=2
1=1
M
SAMRI
SA 2 In SASAll 1/8 p
(By definition of & and m)z))
T 21 -7
((1-7)
1
1=0
SAR SAln
SA 1/5 P.
(By definition of R)
21-66
2 7)7
7

---

assuming that Published as a conference paper at ICLR 2020
It should be stressed that throughout the lines, P is shorthand for asymptotic expression, instead of an exact value. Our final choice of 62 and 61 are 62 = 3. and 61 24/2M -
not hard
to see that In 1/e1 poly(In 2, In )- This immediately implies that with probability - 8, the number of time steps such that (V* V*) (0t) i
S SA 1/6 e2 - 7)
δ
where hidden factors are poly(In ,, In I In SA).
4
DISCUSSION
In this section, we discuss the implication of our results, and present some interesting properties of our algorithm beyond its sample complexity bound.
4.1 COMPARISON WITH PREVIOUS RESULTS
Lower bound To the best of our knowledge, the current best lower bound for worst-case sample complexity is S2 and this lower bound lies only in the dependence on 1/(1 7) and logarithmic terms SA, 1/(1 and 1/c.
SA ?((17)} In 1/0) due to Lattimore & Hutter (012). The gap between our results
Model-free algorithms Previously, the best sample complexity bound for a model- free algorithm Ö
(1 (1- (suppressing all logarithmic terms), achieved by Delayed Q-learning Strehl al. (2006) Our results improve this upper bound by a factor of .ां and closes the quadratic gap in 1/c between Delayed Q-learning's s result and the lower bound. In fact, the following theorem shows that UCB Q-learning can indeed outperform Delayed Q-learning.
SA
Theorem 2. There exists a family of MDPs with constant and A, in which with probability 1 - 6, Delayed Q-learning incurs sample complexity of exploration of Q In(1/)) <
c-
[n(I/8]
The construction of this hard MDP family is given in the supplementary material.
Model-based algorithms For model-based algorithms, better sample complexity results in infinite horizon settings have been claimed Szita & Szepesvári (2010). To the best of our knowledge, the best
published result without further restrictions on MDPs is Ô 211-- claimed by Szita & Szepesvári
(2010), which is (1 (1->) smaller than our upper bound. From the space complexity point of view, our algorithm is much more memory-efficient. Our algorithm stores O(SAA) values, whereas the algorithm in Szita & Szepesvári (2010) needs (2S5 A) memory to store the transition model.
4.2 EXTENSION TO OTHER SETTINGS
Due to length limits, detailed discussion in this section is deferred supplementary materials.
Finite horizon MDP The sample complexity of exploration bounds UCB Q-learnig implies Ô (E PAC sample complexity and a O (T' regret bound finite horizon MDPs. That is, our algorithm implies a PAC algorithm for finite horizon MDPs. We not aware of reductions of the opposite direction (from finite horizon sample complexity to infinite horizon sample complexity of exploration).
Regret The reason why results can imply an Õ(VT) regret is that, after choosing c1, it follows from the argument of Theorem 1 that with probability 1 8, for all 62 > ( 7)), the number of ez-suboptimal steps is bounded by
SA In SA AAAAAmA 1/6
11 - 7) polylog ( (
8

---

Published as a conference paper at ICLR 2020
In contrast, Delayed Q-learning Strehl al. (2006) can only give an upper bound on suboottiaa steps after setting parameter 61.
CONCLUSION
Infinite-horizon MDP with discounted reward is a setting that arguably more difficult than other popular settings, such as finite-horizon MDP. Previously, the best sample complexity bound achieved by model-free reinforcement learning algorithms in this setting is ((7(11733))
). due to Delayed
Q-learning Strehl al. (2006). In this paper, we propose variant of Q-learning that incorporates 84 This matches the best lower bound except in dependence on 1/(1 -7) and logarithmic factors.
upper confidence bound, and show that it has sample complexity of Ō $4,5) ((20)))))
ACKNOWLEDGEMENTS
The authors thank Chi Jin and Chongjic Zhang for helpful discussions. This work is supported by National Basic Research Program of China (973 Program) (grant no. 2015CB352502), NSFC (61573026), BJNSF (L172037) and Beijing Acedemy of Artificial Intelligence.
REFERENCES
Mohammad Gheshlaghi Azar, Remi Munos, Mohammad Ghavamzadeh, and Hilbert Kappen. Speedy q-learning. In Advances in neural information processing systems, 2011.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. arXiv preprint arXiv: / 703.05449, 2017.
Ronen I. Brafman and Moshe Tennenholtz. R-max a general polynomial time algorithm for near-optimal reinforcement learning. J. Mach. Learn. Res., 3:213-231, March 2003. ISSN 1532-4435. doi: 10.1 (0.1162/152443336622083333 153244303752208377
URL
1162/
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pp. 5713-5723, 2017.
Eyal Even-Dar and Yishay Mansour. Learning rates for q-learning. Journal of Machine Learning Research, 5(Dec):1-25, 2003.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 1163))):563-16600 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. q-learning provably efficient? In Advances in Neural Information Processing Systems, pp. 4874-4874, 2018
Sham Machandranath Kakade al. On the sample complexity reinforcement learning. PhD thesis, University of London London, England, 2003.
Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. In International Conference on Algorithmic Learning Theory, pp. 320-334. Springer, 2012.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1rXiv:1312.5602, 2013.
Volodymyr Mnih, Adria Puigdomenech Badia, Mchdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver. and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International conference on machine learning, pp. 1928-1937, 2016.
John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pp. 1889-1897, 2015.

---

Published as a conference paper at ICLR 2020
Aaron Sidford, Mengdi Wang. Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems, pp. 5186-1165155 5196, 2018a.
Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 770-787, Society for Industrial and Applied Mathematics, 20188 8b.
Alexander L Strehl and Michael L Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309 1331, 2008.
Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. Pac model- free reinforcement learning. In Proceedings of the 23rd international conference on Machine learning, pp. 881-888. ACM, 2006.
István Szita and Csaba Szepesvári. Model- reinforcement learning with nearly tight exploration complexity bounds. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp. 1031-1038, 2010.
A PROOF OF LEMMA 1
Lemma 1, For fixed and 1 > O, let (1) be the event that V*(st) - Q" > - in step t. If
> 261, then with probability at least 1 - -//2.
Σ1(B(0)
SAmSAIn ppolyoog
1 1
(8)
r1 733
61 1-1
where [[1] is the indicator function.
Proof. When > 1 the lemma holds trivially. Now consider the case that 1) S 1.
Let {t: (*())) - (8( 3 By lemma ? with probability 6,
7/7|
Σ
(st) Q*(ss, S Σ [0 - Q-) (s),
1-7 1E!
| +0
SA In I| 61 - ()) x))
$
(1 71-7)5/2 VSAITRR((T))
1 1-7
(1 (1-7)3
SAA/ In SAIT
| +0
1
SA [4]
In
I 1-
c1(1-))
(1 (1-7)3/2
(1 (1-
< |7|
1 In
SAlm [T] (1 7)3
1 1-7
+
(
al (1(1-))
(1 (1-2)
+
SAA22 Suppose that |/| (1-
In SA, for some k > Then it follows that for some constant C₁,
7/ 7 12SAAn In SA
(17 G
22
1 7 (1 - (1
1-7
s sailng In
1
V In
SA [Z] (1-7)3
61 - 7)
(1 (5-2)
1
SAK
SA
sci In
ln
(1(1 74 V VISAA. (In SA + In [7]
( 7))
(1 (1-
10

---

Published as a conference paper at ICLR 2020
Therefore
1
A
In(AA)
CiV In
In
(In SA + + 7
0
e1 - 7)
In
SIn + +2nn
8
1 (1 7)
skCi
In
S 4mmk 6ln
E1 - 7)
771 - 7)
skkCi In 3 In
SAn + Inek).
6 71
Let C" = max(2, 601 / In } ln2 a(l-))) J. Then
k s
If 2 10C' In C", then
k: C- 8C C' - 12 10)C
In
2 4C (2 C' - 4) 20,
which means violation of (9) Therefore, since C"
1
< InC < <300C max (In
61 7)) 20 2}.
(10)
immediately follows that
SAK²
11
In SA
(11)
1) 7)3
SA In SA
In 8
O
In
(12)
1 - 7)3
61(1 - (1(1-
B PROOF OF LEMMA
Lemma 2. For every (C, sequuencee (w))221, with probability - 6/2, the following holds:
Cei
VUSSAC(CC)
+ wSAInC
Σ wy ww, (8t, 5 1- +0 (1-7)25
(1 - (1-
(1 - (1-7)c)
121
where E(C) ((C) In [I-7]e a log-factor.
Fact 1. (1) The following statement holds throughout the algorithm,
Qp+1(s,a) S Qpt
(2) For any there exists p' S such that
Qpti(s,a) 2 Qptr)(saa)
Proof. Both properties are results of the update rule line of Algorithm 1.
Before proving lemma will prove two auxiliary lemmas.
Lemma 3. The following properties hold for of
11

---

Published as a conference paper at ICLR 2020
1. V S at dtvt s //2 for every t 1, > 0.
2. maxiel| a - 2H and Σi= (a))² 1 2H for every 2 1.
3. EES of + + 1/H, for every i 2
d0 4. Mt Ei=ı of di) < 2
where (t)) -n((((+))(--2))forreeel 1,c 1.
Proof. Recall that
# H+( of II a5), of ai II (1 (1-aj) az).
j=i+1
Properties 1-3 are proven by Jin et al. 2018 Now we prove the last property. On the one hand,
Σ
(t)
S 2
t=1 i
t
where the last inequality follows from property 1.
The left-hand side is proven by induction on 1. For the base case, when / /= 1, = For / 2 2, we have a (1 as)aa_1 for Sist
follows that
((L) t (1 oz)
(1l)
cll - 1)
Σ
04
04
+ (1 -oi)
Since function
f(t) = (tt)/t is monotonically decreasing for 2 1, 2 1, we have
(t) + (1 V
l[t -
i(t)
((t) ((t)
at
2 as
+ (1 a1-aa) az)
1-1
Lemma 4. With probubility at least 8/2, all p 2 0 and (8, ap-iiir
0 0 (Q, (x), < +
raj(Ve - (*)( + Br,
(13)
1=1
0 (1p
(14)
where = T(s, a, and Br = ca (1(0)
Proof.
Recall that
II ( az), = II (1 oz). j=
From the update rule, it can be seen that our algorithm maintains the following Q(s,
Qp(s, a. - + Σ at (r( a) + by + (V,,
1=1
Bellman optimality equation gives:
Σ
Subtracting the two equations gives
(s) =ail 1 (s)
Σ
a lb + + (Ve, (86+1) + PP
==1
12

---

Published as a conference paper at ICLR 2020
The identity above holds for arbitrary p. and Now fix E S, A and N. Lett= (p a). t2 = T(s, a, 1). The = case is trivial; we assume t 2 below. Now consider an arbitrary fixed
Define
A = a (ab At. < oo)
Pov--Pr,1 (PV*-Pr,V*) (s, (s,
Let F. be the o-Field generated by random variables (81. Q1 84, 0t.). It can be seen that E [| = 0, while A; is measurable in F.+1. Also, since < (8, a) S - |A S -
Therefore, A; is a martingale difference sequence; by the Zzuma-Hoefdding inequality,
n7²
Pr
Σ 1=1
A
>
exp
(15)
8 - 7) E (a
By choosing we can show that with probability 1 1- 6/((AA(K + 1)(k + 2)
k
2/2
k
(o In 2(k + 1)(k + 2)5A
C2
Hu(k)
A
(16)
5
k
i=1
Here 02 -4v2, (k) = In (++))((++)5 By union bound for all kt this holds for arbitrary t: > 0.
8
arbitrary 8 E S, E simultaneously with probability
d'ES,e'AA 2SA 1)(A 22) = 11 8 2
1
Therefore, we conelude that (16) holds for the random variable Np a) and for all p. with probability 1 - 6/2 as well.
Proof of the right hand side of 13: We also know that (b,-
1-7 v
(1(())
Hi(k)
202
He(k)
a
5
1 ?
k
It is implied by (6) that
0
(Qp - (Q,=))
S
+
Σ
A
+ Σ
a
V (x)(++)) + bz
1-
i=1
1=1
a
302
Hi(t)
Σ
rai(V": (T)(
<
+
?
t
t=1
(Property 4 of lemma 3)
0
<
Σ -V'):
B
Note that 3r c3(1 71 Ht(tt/t;
c3 3c, 12v2.
Proof of the left hand side of (13): Now, we assume that event that (66) holds. We assert that Qp 2 Q for all (s, a) and p S p². This assertion obviously true when p' Then
(Qp - (s, 2 -
Σ A
a
hac (=) + +bb]
2 afh 7
A 20
1=1
Therefore the assertion holds for p' + as well. By induction, it holds for all p.
We now see that (13 holds for probability 5/2 for all p. 8, a. Since Qp a) always greater than Qpr (s, a) for some p' S p. we know that Q, a) 2 (s, 2 Q* a), thus proving (4
13

---

Published as a conference paper at ICLR 2020
We now give proof for lemma 2. Recall the definition for (C, sequeence A sequence (w))21
said to be a (C, w) -equeece for C, w > O, i S we I w for all t 2 1, and Ei21 wa - C.
Proof. Let = Ne(st, ar) for simplicity; we have
Σ we( (st, az)
Σ wo(Qr (5t, ai)
We
R4
Bag + Σ an (Vr(nnaeed) V*) (s:(n)
(17)
1=1
The last inequality is due to lemma 4. Note that a% be bounded by,
=Imm = 0]. the first term in the summation can
Σ wh
a
SAw
(18)
For the second term, define u(s,a) a) sup, Ni(s, a)
It follows that,
u(saa)
Σ
wc Sr.
=
Σ
w Wr(s,a,583
121
8,0
1=
Caa/ui
Hi(i)
< Σ (1 7)
W
(19)
8,0
E=1
< 2 Σ (1 - 7) 03
(CC)HCHH
(20)
8,0
5 20g 71-- -VSAHCCCO
(21)
Where Cs.a = (s, (s,a,)) Wh. Inequality 19 follows from rearrangement inequality, since (x) x is monotonically decreasing. Inequality
follows from Jensen's 's inequality.
For the third term summation, we have
Σ Wt one (Fressann -V*) (sr(s)
Vg - vv*) (st+4)
Tht Ons
Wt
(22)
1'1
t=t++] (().))=(((.a4)
(23)
Define
why+
On Wh:
We claim that wh+1 is (C, (1 + n ) sequencee We now prove this claim. By lemma
for any
t 2 0,
wh41 S
Σ a = 11H)/
"u( a) could be infinity when (s, is visited for infinite number of times.
14

---

Published as a conference paper at ICLR 2020
By Σ = of = 1, we have Erz1 w/44 S E1>1 we C. This proves the assertion. It follows from
(22 that
E D1/+1 (vi (V-vv-) (0++1)
Σ W/+1 (Vi+1 (1+t1-1)) (sc+1)+ + Σ t/47 (vi - (V++))+) ($1+1)
(24)
w/+1 (V+11 - - (81+1) +
Σ
W/+1
1 22
(25)
1-7)
121
121
wWAHH
Σ
W/+1 (Ve+1 1V+1--1)) (st+1) +0
In
(26)
1-
121
$ >Ewle (21
when (Q:+1- (00+1, 0(+1) +
(WSAH 11-7 In lnC)
(27)
Inequality 25 comes from the update rule of our algorithm. Inequality (26) comes from the
fact that a2 (H + 1)/(H + +t) &. H/t and Jensen's Inequality. More specifically, let Ca
Ex21o s.a W/41 w' w(1 1/H1.. Then
/aal" /w'
Σ
wi/+ 1 an
w
Σ
Hw'In(C,, Hw' In(C /w) S 2SAH
11
8,0
8,0
Putting 18].
21
and
27
together, we have,
Σ
wi(Qi (5)) oz)
121
V /WSAHC((C
WSAH
1-7 In C) + En'n wii (Qi+1- -0t) ($1+1, (28) 121
s 203
+0
1-7
Observe that the third term is another weighted sum with the same form 17 Therefore, we can unroll this term repetitively with changing weight sequences.Suppose that our original weight (0)
sequence is also denoted by {w, h221, while {wt (k) h22 denotes the weight sequence after unrolling
for i times. Let (k) be w- (1 + */ Then we can see that (*) 1621 a (C, seeuueee
Suppose that we unroll for H times. Then
Σ wr. (")(s,,
(W(H)SA (1 (1- In Inc) + 7
203
Σ
w
(H)
(o: - Q.) (s),
(1-
121
< 203
AHCC))
(w(H))SHH SAH
In lnc)
+ 1-
C
(1 (1-
(1 71-
We set H = In 1n
< In 1n(((()))))) 1- It follows that w1t (1 + #/ (0) S (ew(") and
1/7
that 7 11 C < Cc. Also, let ((C) ((C) In - Therefore,
1-7
Σ wr(Q. Q')
CaI +0 1 1-7
[VUSACECC) 71-7)225
WSA
In C
1
(29)
(1 (1-7)3
(1 7)
15

---

Published as a conference paper at ICLR 2020
C EXTENSION TO OTHER SETTINGS
First we define a mapping from a finite horizon MDP to an infinite horizon MDP so that our algorithm be applied. For an arbitrary finite horizon MDP .M (S, A. H. ra a) Pa (s' | s.))) where H is the length of episode, the corresponding infinite horizon MDP M = (S, A, 7(5, (). s, defined as,
S = = H, A;
-1-11/11 1/H);
for state s at step h, let Sash be the corresponding state. For any action and next state 8', define F(5.,n, a) = - - (n, a) and fe h+l Sa.h, a) - pp(s' 8, h). And for
h = H, set F( a) and (( 8a,h, a) 1ss = =1] for a fixed starting state 81.
Let V, be the value function in M time and V the value function in M at episode k. step h. It " follows that V 15 = -- (s1) And the policy mapping is defined as (T) = H (3a..) for policy i in M. Value functions in MDP M and M are closely related sense that, any c-optimal policy म of M corresponding to an (c/>") (e/7")-ooptimal )-optimal policy π in M (see section C.1 for proof). Note
that here 7 = 1/1) = (1) a constant.
For any > 0, by running our algorithm on M for Ö(2SAR) time steps, the starting state is visited at least Ō 3SAA times, and at most 1/3 them are not e-optimal. If we select the policy uniformly randomly from the policy x -1 for 0 < t < T/H, with probability at least 2/3 we can get an e-optimal policy. Therefore the PAC sample complexity is Ô (E-2) after hiding S, A, H terms.
On the other hand, we want to show that for any K episodes,
T/H
Regret((T) Σ -v x 122
The reason why our algorithm can have better reduction from regret to PAC is that, after choosing é1, it follows from the argument of theorem that for all e2 ((e1/(1 7)), the number of éz-suboptimal steps is bounded by An polylog 22
[ (1
61 1 (41-))
with probability 1 1- 5. In contrast, delayed Q-learning can only give an upper bound on ei-suboptimal steps after setting parameter E1.
Formally, let X₃ = V*(+1) - (81) be the regret of k-th episode. For any T, set /SA/T and = Ó(E//(1 - 7)). Let M [loga 62(1 [[] 1. It follows that,
M
(T) S T + Σ
(lk: (Xx 2 62 2'-11|/) 6
i=1
M
SAln1/8
Te2
2
< IS/
with probability 1-6. 5. Note that the Ô notation hides the poly (1/(1 - 7), log 1/e1) which is, by our reduction, poly (H, log T, log S, log A).
C.I CONNECTION BETWEEN VALUE FUNCTIONS
Recall that our MDP mapping from M = A, (ss, s,a)) to M = (S, A, F(8, (88 8, a)) is defined as,
16

---

Published as a conference paper at ICLR 2020
S S =
(1 1/H;;
for a state s at step h, let 8 be the corresponding state, For any action and next state s', define F(5s,h. a) ? H
-o-btrrrh (n (8, a) and p( A++1 8e, a) = Ps (s, h). And for H, set F(3 a) = 0 and p 1 h, a) = I[s = s1] for fixed starting state $1-
For trajectory 15 @1). 23 a2). in M, let {(s1, a1), (s2, a2). be the corresponding trajectory in .M. Note that M has unique fixed starting state $1, which means that $ = 31 for all t 2 0. Denote the corresponding policy of #² as x' (may be non-stationary), then we have
V (8er.)) E [F( a1) (5 (2)) +," - (550 ----1.0-11
+7" "V (5
= 7 "E [11(51, a1) + 72(2,, a2) + ........HH11 (5H-1((H-1, + V * (3em41.1)
= (51) , "V**** (5.1.1).
Then for stationary policy H, can conclude V (3.,.11) -- (T(ss). Since the optimal policy H
H* is stationary, we have 1) = 1- (s1)). By definition, म is c-optimal at time step f means that
v (s...) 2 (3 -
It follows that
H (51) + +1 Hpa (5...)) V (5.,,.11) (5 -G,
hence
" (81) (1- V ( + (V* (Rs.,1) (V*()))))) V. (8s1,)) - ( -c
Therefore we have
1 7 ( - V -Vh" - c/7
v (s1) 2 7Hl
which means that n² an (e/>") policy.
D A HARD INSTANCE FOR DELAYED Q-LEARNING
In this section, we prove Theorem regarding the performance of Delayed Q-learning.
Theorem 2. There exists family of MDPs with constant S and A, in which with probability
assuming that 1 6, Delayed Q- Q-learning incurs sample complexity of exploration of [n[1/8] (1/8)) < <
0, y
10c
y
w p. 10c
T,, y
Figure 1: The MDP family. Actions denoted by arrows. Actions with red color have reward 1, and reward 0 otherwise.
Proof. For each 0 {a, b, cf while action set is A 1 consider the following MDP (see also Fig. state space is S Lr,y]; transition probabilities are P(b a, - 10e, P(cla,y) 10c, P(bla, 2) 1, P(alb.)) P(alc, Rewards are all 1, except R(c, 0.
17

---

Published as a conference paper at ICLR 2020
Assume that Delayed Q-learning is called for this MDP starting from state a, with discount y 2 and precision set as e. Denote the Q value maintained by the algorithm by Q. Without loss of generality, assume that the initial tie-breaking favors action y when comparing Q(a, x) and Q(a, y). In that case, unless ((, y) is updated, the agent will always choose in state a. Since Q(a,z) Q(a, y) 10ey > e for any policy, choosing y at state implies that the timestep is not c-optimal. In other words, sample complexity for exploration is at least the number of times the agent visits before the first update of Q( y)-
In the Delayed Q-learning algorithm, ((:-)) are initialized to 1/(1 - -)). Therefore, Q(a y) could only be updated if max Q(c, -) is updated (and becomes smaller than 1/(1 7)). According the algorithm, this can only happen if is visited = 2 (+) times.
However, each time the agent visits a, there less than 10e probability of transiting to c. Let In the first 2tg timesteps.
to m/(1eCC), where C = 3m 1/2 1. 8 is chosen such that C' a will be visited tg times. By Chernoff's bound, with probability 1 - ō, state will visited less than m times. In that case, (a, y) will not be updated in the first 26 timesteps. Therefore, with probability 1 8, sample complexity of exploration is at least
= Ω (~ (In (1m
When In(1/6) < E²,
2, it can be seen that = 3 < 4 < m.
18


Reviews:
[{"review_id": "r1gUR9K1qr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nIn this paper, the authors extend the UCB Q-learning algorithm by Jin et al. (2018) to infinite horizon discounted MDPs, and prove a PAC bound of \\tilde{O}(SA/\\epsilon^2 (1-\\gamma)^7) for the resulting algorithm. This bound improves the one for delayed Q-learning by Strehl et al. (2006) and matches the lower-bound in terms of \\epsilon, S, and A. \n\n\nComments:\n- Overall, the paper is well-written and well-structured. Although most of the results are in the appendix, the authors have done a good job in what they reported in the paper and what they left for the appendix. \n- I personally think ICLR is not a good venue for this kind of papers. Places like COLT and journals are better because they allow the authors to report most of the results in the main paper, and give more time to the reviewers to go over all the proofs. \n- I did not have time to go over all the proofs in the appendix but I checked those in the paper. I did not find any error, but the math can be written more rigorously. \n- The algorithm is quite similar to the one by Jin et al. (2018), which is for finite-horizon problems. The authors discuss on Page 4 that why despite the similarity of the algorithms, the techniques in Jin et al. (2018) cannot be directly applied to their case. It would be good if the authors have a discussion on the novelty of the techniques used in their analysis, not only w.r.t. Jin et al. (2018), but w.r.t. other analysis of model free algorithms in infinite-horizon discounted problems. \n- What makes this work different than Jin et al. (2018), and is its novelty, is obtaining a PAC bound. The resulting regret bound is similar to the one in Jin et al. (2018), but the PAC bound is new. It would be good if the authors mention this on Page 4. This makes it more clear in which sense this work is different than that by Jin et al. (2018). \n- It is important to write in the statement of Condition 2 that \"i\" changes between 0 and \\log_2 R. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyxP6tXTtB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considered a Q-learning algorithm with UCB exploration policy for infinite-horizon MDP, and derived the sample complexity of exploration bound. The bound was shown to improve the existing results and matched the lower bound up to some log factors. The problem considered is interesting and challenging. However, I have a few major concerns.\n\n1. Assumptions: The Condition 2 is on the term $X_t^{(i)}$ which is the i-th largest item of the gap $\\Delta_t$ (the difference between the value function and the Q function fo the optimal policy). How to verify this condition in practice? Do you need this condition for all $t$? Does this condition depend on the choice of length $R$? The conditions are listed without any discussions.  \n\n2. Algorithm: The Algorithm depends on the choice of the parameter $R$. How to choose $R$ in practice?\n\n3. Writing: This paper is not well written. There are many typos and grammar errors. In addition, the key components Sections 3.3 and 3.4 are very hard to follow. For instance, in Section 3.3, the authors first introduced Condition 1 and then Condition 2, and then claimed that Condition 2 implied Condition 1. Similarly, in Section 3.4, Lemma 1 was introduced before Lemma 2. Then the authors claimed that Lemma 2 implies Lemma 1. If would be easier to follow if the authors only introduced the latter result, and then discuss the former result as a remark.  \n\n~~~~~~~~~~~~~~~~~~~~~~\nAfter rebuttal: Thanks the authors for addressing my questions. My first two major concerns have been nicely addressed. Therefore, I would like to increase my rating to 6.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlWhQI79B", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper adapts the UCB Q-learning method to the inifinite-horizon discounted MDP setting. With an analysis similar to that of Jin et al (2018), it shows that this algorithm achieves a PAC bound of (1-gamma)^-7 |S||A|/eps^2, improving previous best-known bound (Delayed Q-learning, Strehlet et al, 2006, (1-gamma)^-8 |S||A|/eps^4) for this case.\n\nEvaluation: As I see this paper a direct extension of that of Jin et al (2018), I am afraid I have to recommend a rejection. \n\nHere are some more detailed comments:\n\nSignificance: \nThis paper studies the RL problem for the infinite-horizon discounted MDP setting. This is an important setting in reinforcement learning. However, the bound is not optimal as the dependence of (1-gamma) is significantly larger than the lower bound. Moreover, both the algorithm and analysis are direct extensions of that of Jin et al, I do not see a huge technique improvement. \n\nTechnique Novelty:\nAs stated in the paper, the major difficulty is that the inf-horizon case does not have a set of \"consecutive episodes\". Therefore the \"learning error at time t cannot be decomposed as errors from a set of consecutive time\nsteps before t, but errors from a set of non-consecutive time steps without any structure.\" However, I do not see a major technological innovation is needed to get around this issue. As a result, the analysis and algorithm in this paper are very similar to that of Jin et al 2018, who nearly implicitly contain the results in this paper.\n\nFurthermore, I would think there is a (likely) very simple reduction from the inf-horizon to finite-horizon: break the inifinite horizon into episodes of length R = O((1-\\gamma)^-1 log(eps^-1)). Now, although the MDP does not restart, but it can be treated as restarting at a history-dependent initial state distribution at the beginning of every episode. So, an optimal finit-horizon algorithm in this setting is at most epsilon worse than the optimal inf-horizon algorithm, no matter where/when you start. With little to no modification, we can see that Jin et al work in this setting. Thus, we obtain an algorithm for the inf-horizon as well.\n\nA good match for this conference?\nAs this paper is an adaptation of a previously known Q-learning algorithm to a slightly different setting in RL, I do not see how it fits the \"learning representation\" paradigm. Of course, Q-function can be argued as a representation of the MDP model, but this Q-function itself is not a new concept in this paper.\n\n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1x2aR8Z9S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper extends Jin et al. (2018)'s idea to infinite horizon and improves the best known sample complexity to $\\tilde{O}(\\frac{SA}{\\epsilon^2 (1-\\gamma)^7})$. The derivation is similar to Jin's paper except a very careful selection on the pseudo-horizon length $H$, where $H$ is given in finite horizon and work as the decaying rate for $\\alpha_k$, but for infinite horizon when we need to decide how to pick $H$.\n\nTheoretical Soundness: I didn't check every step of the proof, but I the steps I check is correct and I can feel that the derivation is solid.\n\nNovelty: In section 3.2, the authors discuss the difference between finite case and infinite case. I don't agree with the example if the starting state $s_1$ is with leaving probability less than $T^{-1}$. In this case, the latter rewards counted for $V(s_1)$ will multiply by $\\gamma^t$ which is pretty small, and will not contribute too much on the error. But I do agree that the case of infinite horizon is different since we need to carefully decide the decaying rate of $\\alpha_k$, which is definitely related to $\\frac{1}{1-\\gamma}$ but we need to figure out the relation. I think that is the most difficult part of the whole proof and this is the main technical contribution for the paper.\n\nMinor issue: In algorithm box I didn't see $V^{\\pi_t}, \\hat{Q}_t$ which occurs a lot in the derivation. Maybe change $\\hat{V}$ and $\\hat{Q}$ in the way align to the derivation?\n\nOverall I think this paper is sufficient to get in the conference. But to be honest since I lack the background of PAC-RL, I would remain a conservative of weak accept and would like to hear more discussions from other reviewers and authors to finalize my decision.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors extended Q-learning with UCB exploration bonus by Jin et al. to infinite-horizon MDP with discounted rewards without accessing a generative model, and proved nearly optimal regret bound for finite-horizon episodic MDP. The authors also proved PAC-type sample complexity of exploration, which matches the lower bound up to logarithmic factors. Overall this is a solid theoretical reinforcement learning work.  After author response, we reached a unanimous agreement to accept this paper.
Decision: Accept (Poster)