Year: 2020

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 without accessing a generative model. We show that the sample complexity of exploration of our algorithm is bounded by Õ( SA 2(1−γ)7 ). This improves the previously best known result of Õ( SA 4(1−γ)8 ) in this setting achieved by delayed Q-learning (Strehl et al., 2006), and matches the lower bound in terms of as well as S and A up to logarithmic factors.

text: 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 without accessing a generative model. We show that the sample complexity of exploration of our algorithm is bounded by Õ( SA 2(1−γ)7 ). This improves the previously best known result of Õ( SA 4(1−γ)8 ) in this setting achieved by delayed Q-learning (Strehl et al., 2006), and matches the lower bound in terms of as well as S and A up to logarithmic factors.

heading: 1 INTRODUCTION
text: 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. A typical model in RL is Markov Decision Process (MDP). At each time step, the environment is in a 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-exploitation dilemma: whether to act to gain new information (explore) or to act consistently with past experience to maximize reward (exploit).
Theoretical analyses of reinforcement learning fall into two broad categories: those assuming a simulator (a.k.a. generative model), and those without a simulator. In the first category, the algorithm is allowed to query the outcome of any state action pair from an oracle. The emphasis is on the number of calls needed to estimate the Q value or to output a 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., 2018b). The current results have achieved near-optimal time and sample complexities (Sidford et al., 2018b;a).
∗These two authors contributed equally.
Without a simulator, there is a dichotomy between finite-horizon and infinite-horizon settings. In finite-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 near optimal. In this setting, extensive research in the past decade (Jin et al., 2018; Azar et al., 2017; Jaksch et al., 2010; Dann et al., 2017) has achieved great progress, and established nearly-tight bounds for both regret and sample complexity.
The infinite-horizon setting is a 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 a 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 Rmax (Brafman & Tennenholtz, 2003), MoRmax (Szita & Szepesvári, 2010) and UCRL-γ (Lattimore & Hutter, 2012). It is noteworthy that there still exists a considerable gap between the state-of-the-art algorithm and the theoretical lower bound (Lattimore & Hutter, 2012) regarding 1/(1− γ) factor. Though model-based algorithms have been proved to be sample efficient in various MDP settings, most state-of-the-art 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 on benchmarks such as Atari games and simulated robot control problems.
For infinite horizon MDPs without access to simulator, the best model-free algorithm has a sample complexity of exploration Õ( SA 4(1−γ)8 ), achieved by delayed Q-learning (Strehl et al., 2006). The authors provide a 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 a quadratic gap in 1/ 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 a result of delayed Q-learning algorithm itself, as well as the mathematical artifact in their analysis. To illustrate this, we construct a hard instance showing that Delayed Q-learning incurs Ω(1/ 3) sample complexity. This observation, as well as the success of the Q-learning with UCB algorithm (Jin et al., 2018) in proving a regret bound in finite-horizon settings, motivates us to incorporate a UCB-like exploration term into our algorithm.
In this work, we propose a Q-learning algorithm with UCB exploration policy. We show the sample complexity of exploration bound of our algorithm is Õ( SA 2(1−γ)7 ). This strictly improves the previous best known result due to Delayed Q-learning. It also matches the lower bound in the dependence on , S and A up to logarithmic factors.
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 error propagation structure in Q-learning. In particular, the analysis techniques developed in (Jin et al., 2018) do not directly apply here. We refer the readers to Section 3.2 for detailed explanations and a concrete example.
The rest of the paper is organized as follows. After introducing the notation used in the paper in Section 2, 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. In Section 4 we present some interesting properties beyond sample complexity bound. Finally, we conclude the paper in Section 5.

heading: 2 PRELIMINARY
text: We consider a Markov Decision Process defined by a five tuple 〈S,A, p, r, γ〉, where S is the state space,A is the action space, p(s′|s, a) is the transition function, r : S×A → [0, 1] is the deterministic
reward function, and 0 ≤ γ < 1 is the discount factor for rewards. Let S = |S| and A = |A| denote the number of states and the number of actions respectively.
Starting from a state s1, the agent interacts with the environment for infinite number of time steps. At each time step, the agent observes state st ∈ S, picks action at ∈ A, and receives reward rt; the system then transits to next state st+1.
Using the notations in Strehl et al. (2006), a policy πt refers to the non-stationary control policy of the algorithm since step t. We use V πt(s) to denote the value function under policy πt, which is defined as V πt(s) = E[ ∑∞ i=1 γ
i−1r(si, πt+i−1(si))|s1 = s]. We also use V ∗(s) = supπ V π(s) to denote the value function of the optimal policy. Accordingly, we define Qπt(s, a) = r(s, a) + E[ ∑∞ i=2 γ
i−1r(si, πt+i−1(si))|s1 = s, a1 = a] as the Q function under policy πt; Q∗(s, a) is the Q function under optimal policy π∗.
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); Strehl & Littman (2008). Definition 1. Sample complexity of Exploration of an algorithm ALG is defined as the number of time steps t such that the non-stationary policy πt at time t is not -optimal for current state st, i.e. V πt (st) < V ∗ (st)− .
Roughly speaking, this measure counts the number of mistakes along the whole trajectory. We use the following definition of PAC-MDP Strehl et al. (2006). Definition 2. An algorithm ALG is said to be PAC-MDP (Probably Approximately Correct in Markov Decision Processes) if, for any and δ, the sample complexity of ALG is less than some polynomial in the relevant quantities (S,A, 1/ , 1/δ, 1/(1− γ)), with probability at least 1− δ.
Finally, recall that Bellman equation is defined as the following:{ V πt(s) = Qπt (s, πt(s)) Qπt(s, a) := (rt + γPV πt+1) (s, a), { V ∗(s) = Q∗ (s, π∗(s)) Q∗(s, a) := (rt + γPV ∗) (s, a),
which is frequently used in our analysis. Here we denote [PV πt ] (s, a) := Es′∼p(·|s,a)V πt+1 (s′).

heading: 3 MAIN RESULTS
text: In this section, we present the UCB Q-learning algorithm and the sample complexity bound.

heading: 3.1 ALGORITHM
text: Algorithm 1 Infinite Q-learning with UCB Parameters: , γ, δ Initialize Q(s, a), Q̂(s, a)← 11−γ , N(s, a)← 0, 1 ←
24RM ln 11−γ
, H ← ln 1/((1−γ) 1)ln 1/γ .
Define ι(k) = ln(SA(k + 1)(k + 2)/δ), αk = H+1H+k . for t = 1, 2, ... do
5: Take action at ← arg maxa′ Q̂(st, a′) Receive reward rt and transit to st+1 N(st, at)← N(st, at) + 1 k ← N(st, at), bk ← c21−γ √ Hι(k) k . c2 is a constant and can be set to 4 √ 2
V̂ (st+1)← maxa∈A Q̂(st+1, a) 10: Q(st, at)← (1− αk)Q(st, at) + αk [ r(st, at) + bk + γV̂ (st+1) ] Q̂(st, at)← min(Q̂(st, at), Q(st, at))
end for
Here c2 = 4 √
2 is a constant. R = dln 3 (1−γ)/(1 − γ)e, while the choice of M can be found in Section. 3.3. (M = O (ln 1/((1− γ) ))). The learning rate is defined as αk = (H + 1)/(H + k). H is chosen as ln 1/((1−γ) 1)ln 1/γ , which satisfies H ≤ ln 1/((1−γ) 1) 1−γ .
Our UCB Q-learning algorithm (Algorithm 1) maintains an optimistic estimation of action value function Q(s, a) and its historical minimum value Q̂(s, a). Nt(s, a) denotes the number of times that (s, a) is experienced before time step t; τ(s, a, k) denotes the time step t at which (st, at) = (s, a) for the k-th time; if this state-action pair is not visited that many times, τ(s, a, k) = ∞. Qt(s, a) and Q̂t(s, a) denotes the Q and Q̂ value of (s, a) that the algorithm maintains when arriving at st respectively.

heading: 3.2 SAMPLE COMPLEXITY OF EXPLORATION
text: Our main result is the following sample complexity of exploration bound.
Theorem 1. For any > 0, δ > 0, 1/2 < γ < 1, with probability 1− δ, the sample complexity of exploration (i.e., the number of time steps t such that πt is not -optimal at st) of Algorithm 1 is at most
Õ
( SA ln 1/δ
2 (1− γ)7
) ,
where Õ suppresses logarithmic factors of 1/ , 1/(1− γ) 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 a high level description of the ideas of our 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 s1 (i.e. (V ∗ − V π)(s1)). However, in the infinite horizon setting, the agent may enter under-explored regions at 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 finitehorizon. Consider an MDP with a starting state s1 where the probability of leaving s1 is o(T−1). In this case, with high probability, it would take more than T timesteps to leave s1. Hence, guarantees about the learning in the first T timesteps or about the performance at s1 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 be directly applied to infinite horizon setting.
This calls for techniques for counting mistakes along the entire trajectory, such as those employed by Strehl et al. (2006). In particular, we need to establish convenient sufficient conditions for being -optimal at timestep t and state st, i.e. V ∗(st) − V πt(st) ≤ . Then, bounding the number of violations of such conditions gives a bound on sample complexity.
Another technical reason why the proof in Jin et al. (2018) cannot be directly applied to our problem is the following: In finite horizon settings, Jin et al. (2018) decomposed the learning error at episode k and time h as errors from a set of consecutive episodes before k at time h+ 1 using a clever design of learning rate. However, in the infinite horizon setting, this property does not hold. Suppose at time t the agent is at state st and takes action at. Then the learning error at t only depends on those previous time steps such that the agent encountered the same state as st and took the same action as at. Thus the learning error at time t cannot be decomposed as errors from a 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.
Now we give a brief road map of the proof of Theorem 1. Our first goal is to establish a sufficient condition so that πt learned at step t is -optimal for state st. As an intermediate step we show that a sufficient condition for V ∗(st)− V πt(st) ≤ is that V ∗(st′)−Q∗(st′ , at′) is small for a few time steps t′ within an interval [t, t+R] for a carefully chosen R (Condition 1). Then we show the desired sufficient condition (Condition 2) implies Condition 1. We then bound the total number of bad time steps on which V ∗(st)−Q∗(st, at) is large for the whole MDP; this implies a bound on the number of violations of Condition 2. This in turn relies on a key technical lemma (Lemma 2).
The remaining part of this section is organized as follows. We establish the sufficient condition for -optimality in Section 3.3. The key lemma is presented in Section 3.4. Finally we prove Theorem 1 in Section 3.5.

heading: 3.3 SUFFICIENT CONDITION FOR -OPTIMALITY
text: In this section, we establish a sufficient condition (Condition 2) for -optimality at time step t.
For a fixed st, let TRAJ(R) be the set of length-R trajectories starting from st. Our goal is to give a sufficient condition so that πt, the policy learned at step t, is -optimal. For any 2 > 0, define R := dln 1 2(1−γ)/(1− γ)e. Denote V ∗(st)−Q∗(st, at) by ∆t. We have
V ∗(st)− V πt(st) =V ∗(st)−Q∗(st, at) +Q∗(st, at)− V πt(st) =V ∗(st)−Q∗(st, at) + γP (V ∗ − V πt) (st, πt(st))
=V ∗(st)−Q∗(st, at) + γ ∑ st+1 p (st+1|st, πt(st)) · [V ∗(st+1)−Q∗(st+1, at+1)] +
γ ∑
st+1,st+2
p (st+2|st+1, πt+1(st+1)) · p (st+1|st, πt(st)) [V ∗(st+2)−Q∗(st+2, at+2)]
. . .
≤ 2 + ∑ traj∈
TRAJ(R)
p(traj) · R−1∑ j=0 γj∆t+j  , (1) where the last inequality holds because γ R
1−γ ≤ 2, which follows from the definition of R.
For any fixed trajectory of length R starting from st, consider the sequence (∆t′)t≤t′<t+R. Let X (i) t be the i-th largest item of (∆t′)t≤t′<t+R. Rearranging Eq. (1), we obtain
V ∗(st)− V πt(st) ≤ 2 + Etraj [ R∑ i=1 γi−1X (i) t ] . (2)
We first prove that Condition 1 implies -optimality at time step t when 2 = /3. Condition 1. Let ξi := 12i+2 2 ( ln 11−γ )−1 . For all 0 ≤ i ≤ blog2Rc,
E[X (2i) t ] ≤ ξi. (3)
Claim 1. If Condition 1 is satisfied at time step t, the policy πt is -optimal at state st, i.e. V ∗(st)− V πt(st) ≤ .
Proof. Note that X(i)t is monotonically decreasing with respect to i. Therefore, E[X (i) t ] ≤ E[X (2blog2 ic) t ]. Eq. (3) implies that for 1/2 < γ < 1,
E [ R∑ i=1 γi−1X (i) t ] = R∑ i=1 γi−1E[X (i) t ] ≤ R∑ i=1 γi−1E[X (2blog2 ic) t ]
≤ R∑ i=1 γi−12−blog2 ic−2 2 ( ln 1 1− γ )−1 ≤ R∑ i=1 γi−1 i 2 ( ln 1 1− γ )−1 ≤ 2 2,
where the last inequality follows from the fact that ∑∞ i=1 γi−1 i = 1 γ ln 1 1−γ and γ > 1/2.
Combining with Eq. 2, we have, V ∗(st)− V πt(st) ≤ 2 + E [∑R i=1 γ i−1X (i) t ] ≤ 3 2 = .
Next we show that given i, t, Condition 2 implies Eq. (3). Condition 2. Define L = blog2Rc. Let M = max { d2 log2 1ξL(1−γ)e, 10 } , and ηj = ξiM · 2 j−1. For all 2 ≤ j ≤M , ηj Pr[X(2 i) t > ηj−1] ≤ ξi M .
Claim 2. Given i, t, Eq. (3) holds if Condition 2 is satisfied.
Proof. The reason behind the choice of M is to ensure that ηM > 1/(1 − γ) 1. It follows that, assuming Condition 2 holds, for 1 ≤ j ≤M ,
E [ X (2i) t ] = ∫ 1/(1−γ) 0 Pr [ X (2i) t > x ] dx ≤ η1 + M∑ j=2 ηj Pr[X (2i) t > ηj−1] ≤ ξi.
Therefore, if a time step t is not 2-optimal, there exists 0 ≤ i < blog2Rc and 2 ≤ j ≤M such that
ηj Pr[X (2i) t > ηj−1] > ξi M . (4)
Now, the sample complexity can be bounded by the number of (t, i, j) 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 t such that Pr[X(2 i) t > ηj−1] > ξi Mηj , we count the number of time steps that X (2i) t > ηj−1. Lemma 1 provides an upper bound of the number of such t.

heading: 3.4 KEY LEMMAS
text: In this section, we present two key lemmas. Lemma 1 bounds the number of sub-optimal actions, which in turn, bounds the sample complexity of our algorithm. Lemma 2 bounds the weighted sum of learning error, i.e. (Q̂t −Q∗)(s, a), with the sum and maximum of weights. Then, we show that Lemma 1 follows from Lemma 2.
Lemma 1. For fixed t and η > 0, let B(t)η be the event that V ∗(st)−Q∗(st, at) > η1−γ in step t. If η > 2 1, then with probability at least 1− δ/2,
t=∞∑ t=1 I [ B(t)η ] ≤ SA lnSA ln 1/δ η2(1− γ)3 · polylog ( 1 1 , 1 1− γ ) , (5)
where I[·] is the indicator function.
Before presenting Lemma 2, we define a class of sequence that occurs in the proof.
Definition 3. A sequence (wt)t≥1 is said to be a (C,w)-sequence for C,w > 0, if 0 ≤ wt ≤ w for all t ≥ 1, and ∑ t≥1 wt ≤ C.
Lemma 2. For every (C,w)-sequence (wt)t≥1, with probability 1− δ/2, the following holds:
∑ t≥1 wt(Q̂t −Q∗)(st, at) ≤ C 1 1− γ +O
(√ wSAC`(C)
(1− γ)2.5 + wSA lnC (1− γ)3 ln
1
(1− γ) 1
) .
where `(C) = ι(C) ln 1(1−γ) 1 is a log-factor.
Proof of Lemma 2 is quite technical, and is therefore deferred to supplementary materials.
1 ηM > 1/(1−γ) can be verified by combining inequalities ξi ·2M/2 ≥ 1/(1−γ) and 2M/2−1 > (M +1) for large enough M .
Now, we briefly explain how to prove Lemma 1 with Lemma 2. (Full proof can be found in supplementary materials.) Note that since Q̂t ≥ Q∗ and at = arg maxa Q̂t(st, a),
V ∗(st)−Q∗(st, at) ≤ Q̂t(st, at)−Q∗(st, at). We now consider a set J = {t : V ∗(st) − Q∗(st, at) > η(1 − γ)−1}, and consider the (|J |, 1)- weight sequence defined by wt = I [t ∈ J ]. We can now apply Lemma 2 to weighted sum∑
t≥1 wt [V ∗(st)−Q∗(st, at)] . On the one hand, this quantity is obviously at least |J |η(1− γ)−1. On the other hand, by lemma 2, it is upper bounded by the weighted sum of (Q̂−Q∗)(st, at). Thus we get
|J |η(1− γ)−1 ≤ C 1 1− γ +O (√ SA|J |`(|J |) (1− γ)2.5 + wSA ln |J | (1− γ)3 ln 1 (1− γ) 1 ) .
Now focus on the dependence on |J |. The left-hand-side has linear dependence on |J |, whereas the left-hand-side has a Õ (√ |J | )
dependence. This allows us to solve out an upper bound on |J | with quadratic dependence on 1/η.

heading: 3.5 PROOF FOR THEOREM 1
text: We prove the theorem by stitching Lemma 1 and Condition 2.
Proof. (Proof for Theorem 1) By lemma 1, for any 2 ≤ j ≤M , ∑∞ t=1 I [V ∗(st)−Q∗(st, at) > ηj−1] ≤ C, where
C = SA lnSA ln 1/δ
η2j−1(1− γ)5 · P̃ . (6)
Here P̃ is a shorthand for polylog (
1 1 , 11−γ
) .
Let At = I[X (2i) t ≥ ηj−1] be a Bernoulli random variable, and {Ft}t≥1 be the filtration generated by random variables {(sτ , aτ ) : 1 ≤ τ ≤ t}. Since At is Ft+R−measurable, for any 0 ≤ k < R, {Ak+tR − E[Ak+tR | Fk+tR]}t≥0 is a martingale difference sequence. For now, consider a fixed 0 ≤ k < R. By Azuma-Hoeffiding inequality, after T = O ( C 2i · Mηj ξi ln(RML) )
time steps (if it happens that many times) with
Pr [ X
(2i) k+tR ≥ ηj−1 ] = E[Ak+tR] >
ξi Mηj , (7)
we have ∑ tAk+tR ≥ C/2i with probability at least 1− δ/(2MRL).
On the other hand, if Ak+tR happens, within [k + tR, k + tR + R − 1], there must be at least 2i time steps at which V ∗(st) − Q∗(st, at) > ηj−1. The latter event happens at most C times, and [k + tR, k + tR + R − 1] are disjoint. Therefore, ∑∞ t=0Ak+tR ≤ C/2i. 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− δ/(2ML), there are at most RT time steps where Pr [ X (2i) t ≥ ηj−1 ] > ξi/(Mηj). Thus, the number of sub-optimal steps is bounded by,
∞∑ t=1 I[V ∗(st)− V πt(st) > ]
≤ ∞∑ t=1 L∑ i=0 M∑ j=2 I [ ηj Pr[X (2i) t > ηj−1] > ξi M ] = L∑ i=0 M∑ j=2 ∞∑ t=1 I [ Pr[X (2i) t > ηj−1] > ξi ηjM ] ≤ L∑ i=0 M∑ j=2 SAMR ln 1/δ lnSA ηjξi · 2i(1− γ)5 P̃ ≤ L∑ i=0 SA · 2i+4 lnSA ln 1/δ 22(1− γ)6 P̃ (By definition of ξi and ηj)
≤ SAR lnSA ln 1/δ 22(1− γ)6 P̃ ≤ SA lnSA ln 1/δ 22(1− γ)7 P̃ . (By definition of R)
It should be stressed that throughout the lines, P̃ is a shorthand for an asymptotic expression, instead of an exact value. Our final choice of 2 and 1 are 2 = 3 , and 1 =
24RM ln 11−γ
. It is not hard
to see that ln 1/ 1 = poly(ln 1 , ln 1 1−γ ). This immediately implies that with probability 1− δ, the number of time steps such that (V ∗ − V π) (st) > is
Õ ( SA ln 1/δ
2(1− γ)7
) ,
where hidden factors are poly(ln 1 , ln 1 1−γ , lnSA).

heading: 4 DISCUSSION
text: In this section, we discuss the implication of our results, and present some interesting properties of our algorithm beyond its sample complexity bound.

heading: 4.1 COMPARISON WITH PREVIOUS RESULTS
text: Lower bound To the best of our knowledge, the current best lower bound for worst-case sample complexity is Ω ( SA 2(1−γ)3 ln 1/δ )
due to Lattimore & Hutter (2012). The gap between our results and this lower bound lies only in the dependence on 1/(1−γ) and logarithmic terms of SA, 1/(1−γ) and 1/ .
Model-free algorithms Previously, the best sample complexity bound for a model-free algorithm is Õ ( SA
4(1−γ)8
) (suppressing all logarithmic terms), achieved by Delayed Q-learning Strehl et al.
(2006). Our results improve this upper bound by a factor of 1 2(1−γ) , and closes the quadratic gap in 1/ between Delayed Q-learning’s result and the lower bound. In fact, the following theorem shows that UCB Q-learning can indeed outperform Delayed Q-learning. Theorem 2. There exists a family of MDPs with constant S and A, in which with probability 1− δ, Delayed Q-learning incurs sample complexity of exploration of Ω ( −3
ln(1/δ)
) , assuming that
ln(1/δ) < −2.
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 Õ ( SA
2(1−γ)6
) claimed by Szita & Szepesvári
(2010), which is (1− γ) smaller than our upper bound. From the space complexity point of view, our algorithm is much more memory-efficient. Our algorithm stores O(SA) values, whereas the algorithm in Szita & Szepesvári (2010) needs Ω(S2A) memory to store the transition model.

heading: 4.2 EXTENSION TO OTHER SETTINGS
text: Due to length limits, detailed discussion in this section is deferred to supplementary materials. Finite horizon MDP The sample complexity of exploration bounds of UCB Q-learning implies Õ ( −2 ) PAC sample complexity and a Õ ( T 1/2 ) regret bound in finite horizon MDPs. That is, our algorithm implies a PAC algorithm for finite horizon MDPs. We are not aware of reductions of the opposite direction (from finite horizon sample complexity to infinite horizon sample complexity of exploration). Regret The reason why our results can imply an Õ( √ T ) regret is that, after choosing 1, it follows from the argument of Theorem 1 that with probability 1− δ, for all 2 > Õ( 1/(1− γ)), the number of 2-suboptimal steps is bounded by
O ( SA lnSA ln 1/δ
22(1− γ)7 polylog
( 1
1 ,
1
1− γ
)) .
In contrast, Delayed Q-learning Strehl et al. (2006) can only give an upper bound on 1-suboptimal steps after setting parameter 1.

heading: 5 CONCLUSION
text: Infinite-horizon MDP with discounted reward is a setting that is 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 Õ( SA 4(1−γ)8 ), due to Delayed Q-learning Strehl et al. (2006). In this paper, we propose a variant of Q-learning that incorporates upper confidence bound, and show that it has a sample complexity of Õ( SA 2(1−γ)7 ). This matches the best lower bound except in dependence on 1/(1− γ) and logarithmic factors.

heading: 6 ACKNOWLEDGEMENTS
text: The authors thank Chi Jin and Chongjie 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.

heading: A PROOF OF LEMMA 1
text: Lemma 1. For fixed t and η > 0, let B(t)η be the event that V ∗(st)−Q∗(st, at) > η1−γ in step t. If η > 2 1, then with probability at least 1− δ/2,
t=∞∑ t=1 I [ B(t)η ] ≤ SA lnSA ln 1/δ η2(1− γ)3 · polylog ( 1 1 , 1 1− γ ) , (8)
where I[·] is the indicator function.
Proof. When η > 1 the lemma holds trivially. Now consider the case that η ≤ 1. Let I = {t : V ∗(st)−Q∗(st, at) > η1−γ }. By lemma 2, with probability 1− δ,
η|I| 1− γ ≤ ∑ t∈I (V ∗(st)−Q∗(st, at)) ≤ ∑ t∈I [( Q̂t −Q∗ ) (st, at) ] ≤ |I| 1
1− γ +O
( 1 (1− γ)5/2 √ SA|I|`(|I|) + SA (1− γ)3 ln |I| ln 1 1(1− γ) )
≤ |I| 1 1− γ +O ln 1 1(1− γ) ·  √ SA|I| ln SA|I|δ (1− γ)5/2 + SA ln |I| (1− γ)3  ≤ |I| 1
1− γ +O
(√ ln 1
δ ln
1
1(1− γ) · (√ SA|I| lnSA|I| (1− γ)5/2 + SA ln |I| (1− γ)3 ))
Suppose that |I| = SAk 2
η2(1−γ)3 lnSA, for some k > 1. Then it follows that for some constant C1,
η|I| 1− γ = k2SA lnSA (1− γ)4η ≤ 2(η − 1)|I| 1− γ
≤ C1 √ ln 1
δ ln
1
1(1− γ)
(√ SA|I| ln (SA|I|)
(1− γ)5/2 + SA ln |I| (1− γ)3
)
≤ C1 √ ln 1
δ ln
1
1(1− γ)
( SAk η(1− γ)4 √ lnSA · (lnSA+ ln |I|) + SA ln |I| (1− γ)3 ) .
Therefore
k2 ln(SA) ≤ C1 √ ln 1
δ ln
1
1(1− γ) (k (lnSA+ ln |I|) + η(1− γ) ln |I|)
≤ kC1 √ ln 1
δ ln
1
1(1− γ) · (lnSA+ 2 ln |I|)
≤ kC1 √ ln 1
δ ln
1 1(1− γ) · ( 3 lnSA+ 4 ln k + 6 ln 1 η(1− γ) ) ≤ 6kC1 √ ln 1
δ ln2
1
1(1− γ) (lnSA+ ln ek) .
Let C ′ = max{2, 6C1 √
ln 1δ ln 2 1 1(1−γ)}. Then
k ≤ C ′(2 + ln k). (9)
If k ≥ 10C ′ lnC ′, then
k − C ′ (2 + ln k) ≥ 8C ′ lnC ′ − (2 + ln 10)C ′
≥ 4C ′ (2 lnC ′ − 4) ≥ 0,
which means violation of (9). Therefore, since C ′ ≥ 2
k ≤ 10C ′ lnC ′ ≤ 360C21 max{ln 4 1
1(1− γ) , 20 ln 2}. (10)
It immediately follows that
|I| = SAk 2
η2(1− γ)3 lnSA (11)
≤ SA lnSA η2(1− γ)5 · ln 1 δ · O ( ln8 1 1(1− γ) ) . (12)

heading: B PROOF OF LEMMA 2
text: Lemma 2. For every (C,w)-sequence (wt)t≥1, with probability 1− δ/2, the following holds:
∑ t≥1 wt(Q̂t −Q∗)(st, at) ≤ C 1 1− γ +O
(√ wSAC`(C)
(1− γ)2.5 + wSA lnC (1− γ)3 ln
1
(1− γ) 1
) .
where `(C) = ι(C) ln 1(1−γ) 1 is a log-factor.
Fact 1. (1) The following statement holds throughout the algorithm,
Q̂p+1(s, a) ≤ Qp+1(s, a).
(2) For any p, there exists p′ ≤ p such that
Q̂p+1(s, a) ≥ Qp′+1(s, a).
Proof. Both properties are results of the update rule at line 11 of Algorithm 1.
Before proving lemma 2, we will prove two auxiliary lemmas.
Lemma 3. The following properties hold for αit :
1. √
1 t ≤ ∑t i=1 α i t √ 1 i ≤ 2 √ 1 t for every t ≥ 1, c > 0.
2. maxi∈[t] αit ≤ 2Ht and ∑t i=1(α i t) 2 ≤ 2Ht for every t ≥ 1.
3. ∑∞ t=i α i t = 1 + 1/H, for every i ≥ 1.
4. √
ι(t) t ≤ ∑t i=1 α i t √ ι(i) i ≤ 2 √ ι(t) t where ι(t) = ln(c(t+1)(t+2)), for every t ≥ 1, c ≥ 1.
Proof. Recall that
αt = H + 1
H + t , α0t = t∏ j=1 (1− αj), αit = αi t∏ j=i+1 (1− αj).
Properties 1-3 are proven by Jin et al. (2018). Now we prove the last property.
On the one hand, t∑ i=1 αit
√ ι(i)
i ≤ t∑ i=1 αit
√ ι(t) i ≤ 2 √ ι(t) t ,
where the last inequality follows from property 1.
The left-hand side is proven by induction on t. For the base case, when t = 1, αtt = 1. For t ≥ 2, we have αit = (1− αt)αit−1 for 1 ≤ i ≤ t− 1. It follows that
t∑ i=1 αit
√ ι(i)
i = αt
√ ι(t)
t + (1− αt) t−1∑ i=1 αit−1
√ ι(i)
i ≥ αt
√ ι(t)
t + (1− αt) √ ι(t− 1) t− 1 .
Since function f(t) = ι(t)/t is monotonically decreasing for t ≥ 1, c ≥ 1, we have
αt
√ ι(t)
t + (1− αt) √ ι(t− 1) t− 1 ≥ αt √ ι(t) t + (1− αt) √ ι(t) t ≥ √ ι(t) t .
Lemma 4. With probability at least 1− δ/2, for all p ≥ 0 and (s, a)-pair,
0 ≤ (Qp −Q∗)(s, a) ≤ α0t
1− γ + t∑ i=1 γαit(V̂ti − V ∗)(sti+1) + βt, (13)
0 ≤ (Q̂p −Q∗)(s, a), (14) where t = Np(s, a), ti = τ(s, a, i) and βt = c3 √ Hι(t)/((1− γ)2t).
Proof. Recall that
α0t = t∏ j=1 (1− αj), αit = αi t∏ j=i+1 (1− αj).
From the update rule, it can be seen that our algorithm maintains the following Q(s, a):
Qp(s, a) = α 0 t
1
1− γ + t∑ i=1 αit [ r(s, a) + bi + γV̂ti(sti+1) ] .
Bellman optimality equation gives:
Q∗(s, a) = r(s, a) + γPV ∗(s, a) = α0tQ∗(s, a) + t∑ i=1 αit [r(s, a) + γPV ∗(s, a)] .
Subtracting the two equations gives
(Qp −Q∗)(s, a) = α0t ( 1
1− γ −Q∗(s, a)) + t∑ i=1 αit [bi + γ (Vti − V ∗) (sti+1) + γ (V ∗(sti+1)− PV ∗(s, a))] .
The identity above holds for arbitrary p, s and a. Now fix s ∈ S, a ∈ A and p ∈ N. Let t = Np(s, a), ti = τ(s, a, i). The t = 0 case is trivial; we assume t ≥ 1 below. Now consider an arbitrary fixed k. Define
∆i = ( αik · I[ti <∞] · ( PV ∗ − P̂tiV ∗ ) (s, a) ) Let Fi be the σ-Field generated by random variables (s1, a1, ..., sti , ati). It can be seen that E [∆i|Fi] = 0, while ∆i is measurable in Fi+1. Also, since 0 ≤ V ∗(s, a) ≤ 11−γ , |∆i| ≤ 2 1−γ . Therefore, ∆i is a martingale difference sequence; by the Azuma-Hoeffding inequality,
Pr [∣∣∣∣∣ k∑ i=1 ∆i ∣∣∣∣∣ > η ] ≤ 2 exp { − η 2 8 (1− γ)−2 ∑k i=1(α i k) 2 } . (15)
By choosing η, we can show that with probability 1− δ/ [SA(k + 1)(k + 2)],
∣∣∣∣∣ k∑ i=1 ∆i ∣∣∣∣∣ ≤ 2 √ 2 1− γ · √√√√ k∑ i=1 (αik) 2 · ln 2(k + 1)(k + 2)SA δ ≤ c2 1− γ √ Hι(k) k . (16)
Here c2 = 4 √
2, ι(k) = ln (k+1)(k+2)SAδ . By a union bound for all k, this holds for arbitrary k > 0, arbitrary s ∈ S, a ∈ A simultaneously with probability
1− ∑
s′∈S,a′∈A ∞∑ k=1
δ 2SA(k + 1)(k + 2) = 1− δ 2 .
Therefore, we conclude that (16) holds for the random variable t = Np(s, a) and for all p, with probability 1− δ/2 as well.
Proof of the right hand side of (13): We also know that (bk = c21−γ √ Hι(k) k )
c2 1− γ
√ Hι(k)
k ≤ k∑ i=1 αikbi ≤ 2c2 1− γ
√ Hι(k)
k .
It is implied by (16) that
(Qp −Q∗)(s, a) ≤ α0t
1− γ + γ ∣∣∣∣∣ t∑ i=1 ∆i ∣∣∣∣∣+ t∑ i=1 αit [ γ(V̂ti − V ∗)(xti+1) + bi ] ≤ α 0 t
1− γ + 3c2 1− γ
√ Hι(t)
t + t∑ i=1 γαit(V̂ ti − V ∗)(xti+1)
(Property 4 of lemma 3)
≤ α 0 t
1− γ + t∑ i=1 γαit(V̂ ti − V ∗)(xti+1) + βt.
Note that βt = c3(1− γ)−1 √ Hι(t)/t; c3 = 3c2 = 12 √ 2.
Proof of the left hand side of (13): Now, we assume that event that (16) holds. We assert that Qp ≥ Q∗ for all (s, a) and p ≤ p′. This assertion is obviously true when p′ = 0. Then
(Qp −Q∗)(s, a) ≥ −γ ∣∣∣∣∣ t∑ i=1 ∆i ∣∣∣∣∣+ t∑ i=1 αit [ γ(V̂ti − V ∗)(xti+1) + bi ] ≥
t∑ i=1 αitbi − γ ∣∣∣∣∣ t∑ i=1 ∆i ∣∣∣∣∣ ≥ 0. Therefore the assertion holds for p′ + 1 as well. By induction, it holds for all p.
We now see that (13) holds for probability 1− δ/2 for all p, s, a. Since Q̂p(s, a) is always greater than Qp′(s, a) for some p′ ≤ p, we know that Q̂p(s, a) ≥ Qp′(s, a) ≥ Q∗(s, a), thus proving (14).
We now give a proof for lemma 2. Recall the definition for a (C,w)-sequence. A sequence (wt)t≥1 is said to be a (C,w)-sequence for C,w > 0, if 0 ≤ wt ≤ w for all t ≥ 1, and ∑ t≥1 wt ≤ C.
Proof. Let nt = Nt(st, at) for simplicity; we have∑ t≥1 wt(Q̂t −Q∗)(st, at)
≤ ∑ t≥1 wt(Qt −Q∗)(st, at)
≤ ∑ t≥1 wt
[ α0nt
1− γ + βnt + γ nt∑ i=1 αint ( V̂τ(st,at,i) − V ∗ ) (sτ(st,at,i)+1) ] (17)
The last inequality is due to lemma 4. Note that α0nt = I[nt = 0], the first term in the summation can be bounded by, ∑
t≥1
wt α0nt 1− γ ≤ SAw 1− γ . (18)
For the second term, define u(s, a) = suptNt(s, a). 2 It follows that,
∑ t≥1 wtβnt = ∑ s,a u(s,a)∑ i=1 wτ(s,a,i)βi
≤ ∑ s,a (1− γ)−1c3 Cs,a/w∑ i=1
√ Hι(i)
i w (19)
≤ 2 ∑ s,a (1− γ)−1c3 √ ι(C)HCs,aw (20)
≤ 2c3(1− γ)−1 √ wSAHCι(C). (21)
Where Cs,a = ∑ t≥1,(st,at)=(s,a) wt. Inequality (19) follows from rearrangement inequality, since ι(x)/x is monotonically decreasing. Inequality (21) follows from Jensen’s inequality.
For the third term of the summation, we have∑ t≥1 wt nt∑ i=1 αint ( V̂τ(st,at,i) − V ∗ ) (sτ(st,at,i)+1)
≤ ∑ t′≥1 ( V̂t′ − V ∗ ) (st′+1)  ∞∑ t=t′+1
(st,at)=(s ′ t,a ′ t)
αnt′nt wt  . (22) (23)
Define
w′t′+1 =  ∞∑ t=t′+1
(st,at)=(s ′ t,a ′ t)
αnt′nt wt  . We claim that w′t+1 is a (C, (1 + 1 H )w)-sequence. We now prove this claim. By lemma 3, for any t′ ≥ 0,
w′t′+1 ≤ w ∞∑
j=nt′
α nt′ j = (1 + 1/H)w.
2u(s, a) could be infinity when (s, a) is visited for infinite number of times.
By ∑i j=0 α j i = 1, we have ∑ t′≥1 w ′ t′+1 ≤ ∑ t≥1 wt ≤ C. This proves the assertion. It follows from (22) that ∑ t≥1 w′t+1 ( V̂t − V ∗ ) (st+1)
= ∑ t≥1 w′t+1 ( V̂t+1 − V ∗ ) (st+1) + ∑ t≥1 w′t+1 ( V̂t − V̂t+1 ) (st+1) (24)
≤ ∑ t≥1 w′t+1 ( V̂t+1 − V ∗ ) (st+1) + ∑ t≥1 w′t+1 ( 2αnt+1 1 1− γ ) (25)
≤ ∑ t≥1 w′t+1 ( V̂t+1 − V ∗ ) (st+1) +O ( wSAH 1− γ lnC ) (26)
≤ ∑ t≥1 w′t+1 ( Q̂t+1 −Q∗ ) (st+1, at+1) +O ( wSAH 1− γ lnC ) (27)
Inequality (25) comes from the update rule of our algorithm. Inequality (26) comes from the fact that αt = (H + 1)/(H + t) ≤ H/t and Jensen’s Inequality. More specifically, let C ′s,a =∑ t≥1,(st,at=s,a w ′ t+1, w ′ = w(1 + 1/H). Then
∑ t≥1 w′t+1αnt+1 ≤ ∑ s,a C′s,a/w ′∑ n=1 w′ H n ≤ ∑ s,a Hw′ ln(C ′s,a/w) ≤ 2SAHw lnC.
Putting (18), (21) and (27) together, we have,
∑ t≥1 wt(Q̂t −Q∗)(st, at)
≤ 2c3 √ wSAHCι(C)
1− γ +O
( wSAH
1− γ lnC
) + γ ∑ t≥1 w′t+1 ( Q̂t+1 −Q∗ ) (st+1, at+1). (28)
Observe that the third term is another weighted sum with the same form as (17). Therefore, we can unroll this term repetitively with changing weight sequences.Suppose that our original weight sequence is also denoted by {w(0)t }t≥1, while {w (k) t }t≥1 denotes the weight sequence after unrolling for k times. Let w(k) be w · (1 + 1/H)k. Then we can see that {w(k)t }t≥1 is a (C,w(k))-sequence. Suppose that we unroll for H times. Then∑
t≥1
wt(Q̂t −Q∗)(st, at)
≤ 2c3
√ w(H)SAHCι(C)
(1− γ)2 +O
( w(H)SAH
(1− γ)2 lnC
) + γH ∑ t≥1 w (H) t ( Q̂t −Q∗ ) (st, at)
≤ 2c3
√ w(H)SAHCι(C)
(1− γ)2 +O
( w(H)SAH
(1− γ)2 lnC
) + γH C
1− γ .
We set H = ln 1/((1−γ) 1)ln 1/γ ≤ ln 1/((1−γ) 1) 1−γ . It follows that w (H) = (1 + 1/H)Hw(0) ≤ ew(0), and that γH C1−γ ≤ C 1. Also, let `(C) = ι(C) ln((1− γ) −1 −11 ). Therefore,
∑ t≥1 wt(Q̂t −Q∗)(st, at) ≤ C 1 1− γ +O
(√ wSAC`(C)
(1− γ)2.5 +
wSA
(1− γ)3 lnC ln
1
(1− γ) 1
) . (29)

heading: C EXTENSION TO OTHER SETTINGS
text: First we define a mapping from a finite horizon MDP to an infinite horizon MDP so that our algorithm can be applied. For an arbitrary finite horizon MDPM = (S,A,H, rh(s, a), ph(s′ | s, a)) where H is the length of episode, the corresponding infinite horizon MDP M̄ = (S̄, Ā, γ, r̄(s̄, ā), p̄(s̄′ | s̄, ā)) is defined as,
• S̄ = S ×H, Ā = A; • γ = (1− 1/H); • for a state s at step h, let s̄s,h be the corresponding state. For any action a and next state s′, define r̄(s̄s,h, a) = γH−h+1rh(s, a) and p̄(s̄s′,h+1 | s̄s,h, a) = ph(s′ | s, h). And for h = H , set r̄(s̄s,h, a) = 0 and p̄(s̄s′,1 | s̄s,h, a) = I[s′ = s1] for a fixed starting state s1.
Let V̄t be the value function in M̄ at time t and V kh the value function inM at episode k, step h. It follows that V̄ ∗(s̄s1,1) = γH 1−γH V ∗ 1 (s1). And the policy mapping is defined as πh(s) = π̄(s̄s,h) for policy π̄ in M̄. Value functions in MDPM and M̄ are closely related in a sense that, any -optimal policy π̄ of M̄ corresponding to an ( /γH)-optimal policy π inM (see section C.1 for proof). Note that here γH = (1− 1/H)H = O(1) is a constant.
For any > 0, by running our algorithm on M̄ for Õ( 3SAH 9
2 ) time steps, the starting state s1 is visited at least Õ( 3SAH 8
2 ) times, and at most 1/3 of them are not -optimal. If we select the policy uniformly randomly from the policy πtH+1 for 0 ≤ t < T/H , with probability at least 2/3 we can get an -optimal policy. Therefore the PAC sample complexity is Õ ( −2 ) after hiding S,A,H terms.
On the other hand, we want to show that for any K episodes,
Regret(T ) = T/H∑ k=1 [ V ∗(s1)− V k1 (s1) ] ∝ T 1/2.
The reason why our algorithm can have a better reduction from regret to PAC is that, after choosing 1, it follows from the argument of theorem 1 that for all 2 > Õ( 1/(1 − γ)), the number of 2-suboptimal steps is bounded by
O ( SA lnSA ln 1/δ
22(1− γ)7 polylog
( 1
1 ,
1
1− γ )) with probability 1−δ. In contrast, delayed Q-learning can only give an upper bound on 1-suboptimal steps after setting parameter 1.
Formally, let Xk = V ∗(s1)− V k1 (s1) be the regret of k-th episode. For any T , set = √ SA/T and
2 = Õ( 1/(1− γ)). Let M = dlog2 1 2(1−γ)e. It follows that,
Regret(T ) ≤ T 2 + M∑ i=1 (∣∣k : {Xk ≥ 2 · 2i−1}∣∣) 2 · 2i ≤ Õ ( T 2 +
M∑ i=1 SA ln 1/δ 2 · 2i−2 ) ≤ Õ (√ SAT ln 1/δ
) with probability 1− δ. Note that the Õ notation hides the poly (1/(1− γ), log 1/ 1) which is, by our reduction, poly (H, log T, logS, logA).
C.1 CONNECTION BETWEEN VALUE FUNCTIONS
Recall that our MDP mapping from M = (S,A,H, rh(s, a), ph(s′ | s, a)) to M̄ = (S̄, Ā, γ, r̄(s̄, ā), p̄(s̄′ | s̄, ā)) is defined as,
• S̄ = S ×H, Ā = A; • γ = (1− 1/H); • for a state s at step h, let s̄s,h be the corresponding state. For any action a and next state s′,
define r̄(s̄s,h, a) = γH−h+1rh(s, a) and p̄(s̄s′,h+1 | s̄s,h, a) = ph(s, h). And for h = H , set r̄(s̄s,h, a) = 0 and p̄(s̄s′,1 | s̄s,h, a) = I[s′ = s1] for a fixed starting state s1.
For a trajectory {(s̄s1,1, ā1), (s̄s2,2, ā2), · · · } in M̄, let {(s1, a1), (s2, a2), · · · } be the corresponding trajectory inM. Note thatM has a unique fixed starting state s1, which means that stH+1 = s1 for all t ≥ 0. Denote the corresponding policy of π̄t as πt (may be non-stationary), then we have
V̄ π̄ t (s̄s1,1) = E [ r̄(s̄s1,1, ā1) + γr̄(s̄s2,2, ā2) + · · ·+ γH−1r̄(s̄sH−1,H−1, āH−1) + γH V̄ πt+H−1(s̄sH+1,1) ] = γHE [ r1(s1, a1) + r2(s2, a2) + · · ·+ rH−1(sH−1, aH−1) + V̄ πt+H (s̄sH+1,1)
] = γHV π t
(s1) + γ H V̄ πt+H (s̄s1,1).
Then for a stationary policy π̄, we can conclude V̄ π̄(s̄s1,1) = γH 1−γH V π(s1). Since the optimal policy π̄∗ is stationary, we have V̄ ∗(s̄s1,1) = γH 1−γH V ∗(s1).
By definition, π̄ is -optimal at time step t means that
V̄ π̄ t (s̄s1,1) ≥ V̄ ∗(s̄s1,1)− . It follows that
γHV π t
(s1) + γ H V̄ πt+H (s̄s1,1) = V̄ π̄(s̄s1,1) ≥ V̄ ∗(s̄s1,1)− , hence
γHV π t (s1) ≥ (1− γH)V̄ ∗(s̄s1,1) + γH(V̄ ∗(s̄s1,1)− V̄ πt+H (s̄s1,1))− ≥ (1− γH)V̄ ∗(s̄s1,1)− . Therefore we have
V π t (s1) ≥ 1− γH
γH V̄ ∗(s̄s1,1)− /γH = V ∗(s1)− /γH ,
which means that πt is an ( /γH)-optimal policy.

heading: D A HARD INSTANCE FOR DELAYED Q-LEARNING
text: In this section, we prove Theorem 2 regarding the performance of Delayed Q-learning. Theorem 2. There exists a family of MDPs with constant S and A, in which with probability 1− δ, Delayed Q-learning incurs sample complexity of exploration of Ω ( −3
ln(1/δ)
) , assuming that
ln(1/δ) < −2.
Proof. For each 0 < < 110 , consider the following MDP (see also Fig. 1): state space is S = {a, b, c} while action set isA = {x, y}; transition probabilities are P (b|a, y) = 1−10 , P (c|a, y) = 10 , P (b|a, x) = 1, P (a|b, ·) = P (a|c, ·) = 1. Rewards are all 1, except R(c, ·) = 0.
Assume that Delayed Q-learning is called for this MDP starting from state a, with discount γ > 12 and precision set as . 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 Q̂(a, y) is updated, the agent will always choose y in state a. Since Q(a, x)−Q(a, y) = 10 γ > for any policy, choosing y at state a implies that the timestep is not -optimal. In other words, sample complexity for exploration is at least the number of times the agent visits a before the first update of Q̂(a, y).
In the Delayed Q-learning algorithm, Q̂(·, ·) 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− γ)). According to the algorithm, this can only happen if c is visited m = Ω ( 1 2 ) times.
However, each time the agent visits a, there is less than 10 probability of transiting to c. Let t0 = m/(10 C), where C = 3 ln 1δ + 1. δ is chosen such that C ≤ m. In the first 2t0 timesteps, a will be visited t0 times. By Chernoff’s bound, with probability 1− δ, state c will be visited less than m times. In that case, Q̂(a, y) will not be updated in the first 2t0 timesteps. Therefore, with probability 1− δ, sample complexity of exploration is at least
t0 = Ω
( 1
3 (ln 1/δ)
) .
When ln(1/δ) < −2, it can be seen that C = 3 ln 1δ + 1 < 4 2 < m.

Review summaries:
In 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. 

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$.