Title: Q-LEARNING WITH UCB EXPLORATION IS SAMPLE EFFICIENT FOR INFINITE-HORIZON MDP

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. * These two authors contributed equally.

1. 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. 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) . 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 Õ( 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 Õ( 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.

2. PRELIMINARY:

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 s 1 , the agent interacts with the environment for infinite number of time steps. At each time step, the agent observes state s t ∈ S, picks action a t ∈ A, and receives reward r t ; the system then transits to next state s t+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-1 r(s i , π t+i-1 (s i ))|s 1 = 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-1 r(s i , π t+i-1 (s i ))|s 1 = s, a 1 = 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 s t , i.e. V πt (s t ) < V * (s t ) -.

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) := (r t + γPV πt+1 ) (s, a), V * (s) = Q * (s, π * (s)) Q * (s, a) := (r t + γPV * ) (s, a),

which is frequently used in our analysis. Here we denote [PV πt ] (s, a) := E s ∼p(•|s,a) V πt+1 (s ).

3. MAIN RESULTS:

In this section, we present the UCB Q-learning algorithm and the sample complexity bound.

3.1. ALGORITHM:

Algorithm 1 Infinite Q-learning with UCB Parameters: , γ, δ Initialize Q(s, a), Q(s, a) ← 1 1-γ , N (s, a) ← 0, 1 ← 24RM ln 1 1-γ , H ← ln 1/((1-γ) 1) ln 1/γ . Define ι(k) = ln(SA(k + 1)(k + 2)/δ), α k = H+1 H+k . for t = 1, 2, ... do 5: Take action a t ← arg max a Q(s t , a ) Receive reward r t and transit to s t+1 N (s t , a t ) ← N (s t , a t ) + 1 k ← N (s t , a t ), b k ← c2 1-γ Hι(k) k c 2 is a constant and can be set to 4 √ 2 V (s t+1 ) ← max a∈A Q(s t+1 , a) 10: Q(s t , a t ) ← (1 -α k )Q(s t , a t ) + α k r(s t , a t ) + b k + γ V (s t+1 ) Q(s t , a t ) ← min( Q(s t , a t ), Q(s t , a t )) end for Here c 2 = 4 √ 2 is a constant. R = ln 3 (1-γ) /(1 -γ)

, 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). N t (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 (s t , a t ) = (s, a) for the k-th time; if this state-action pair is not visited that many times, τ (s, a, k) = ∞. Q t (s, a) and Qt (s, a) denotes the Q and Q value of (s, a) that the algorithm maintains when arriving at s t respectively.

3.2. SAMPLE COMPLEXITY OF EXPLORATION:

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 s t ) of Algorithm 1 is at most

Õ SA ln 1/δ 2 (1 -γ) 7 ,

where Õ 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 s

1 (i.e. (V * -V π )(s 1 )).

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 s 1 where the probability of leaving s 1 is o(T -1 ). In this case, with high probability, it would take more than T timesteps to leave s 1 . Hence, guarantees about the learning in the first T timesteps or about the performance at s 1 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 s t , i.e. V * (s t ) -V πt (s t ) ≤ . 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 s t and takes action a t . Then the learning error at t only depends on those previous time steps such that the agent encountered the same state as s t and took the same action as a t . 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 s t . As an intermediate step we show that a sufficient condition for V * (s t ) -V πt (s t ) ≤ is that V * (s t ) -Q * (s t , a t ) 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 * (s t ) -Q * (s t , a t ) 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.

3.3. SUFFICIENT CONDITION FOR -OPTIMALITY:

In this section, we establish a sufficient condition (Condition 2) for -optimality at time step t.

For a fixed s t , let TRAJ(R) be the set of length-R trajectories starting from s t . 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 := ln

EQUATION

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 s t , 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

EQUATION

We first prove that Condition 1 implies -optimality at time step t when 2 = /3.

Condition 1. Let ξ i := 1 2 i+2 2 ln 1 1-γ -1 . For all 0 ≤ i ≤ log 2 R , E[X (2 i ) t ] ≤ ξ i . (3) Claim 1. If Condition 1 is satisfied at time step t, the policy π t is -optimal at state s t , i.e. V * (s t ) - V πt (s t ) ≤ . Proof. Note that X (i) t

is monotonically decreasing with respect to i. Therefore, E[X

(i) t ] ≤ E[X (2 log 2 i ) t ]. Eq. (3) implies that for 1/2 < γ < 1, E R i=1 γ i-1 X (i) t = R i=1 γ i-1 E[X (i) t ] ≤ R i=1 γ i-1 E[X (2 log 2 i ) t ] ≤ R i=1 γ i-1 2 -log 2 i -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 * (s t ) -V πt (s t ) ≤ 2 + E R i=1 γ i-1 X (i) t ≤ 3 2 = .

Next we show that given i, t, Condition 2 implies Eq. (3). γ) , 10 , and

Condition 2. Define L = log 2 R . Let M = max 2 log 2 1 ξ L (1-

η j = ξi M • 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 (2 i ) t = 1/(1-γ) 0 Pr X (2 i ) t > x dx ≤ η 1 + M j=2 η j Pr[X (2 i ) t > η j-1 ] ≤ ξ i .

Therefore, if a time step t is not 2 -optimal, there exists 0 ≤ i < log 2 R and 2 ≤ j ≤ M such that

EQUATION

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 (2 i ) t > η j-1

. Lemma 1 provides an upper bound of the number of such t.

3.4. KEY LEMMAS:

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. ( Qt -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)

EQUATION

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 (w t ) t≥1 is said to be a (C, w)-sequence for C, w > 0, if 0 ≤ w t ≤ w for all t ≥ 1, and t≥1 w t ≤ C.

Lemma 2. For every (C, w)-sequence (w t ) t≥1 , with probability 1 -δ/2, the following holds:

t≥1 w t ( Qt -Q * )(s t , a t ) ≤ C 1 1 -γ + O wSAC (C) (1 -γ) 2.5 + wSA ln C (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. Now, we briefly explain how to prove Lemma 1 with Lemma 2. (Full proof can be found in supplementary materials.) Note that since Qt ≥ Q * and a t = arg max a Qt (s t , a), V * (s t ) -Q * (s t , a t ) ≤ Qt (s t , a t ) -Q * (s t , a t ). We now consider a set J = {t : V * (s t ) -Q * (s t , a t ) > η(1 -γ) -1 }, and consider the (|J|, 1)weight sequence defined by w t = I [t ∈ J]. We can now apply Lemma 2 to weighted sum

t≥1 w t [V * (s t ) -Q * (s t , a t )

] . 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 * )(s t , a t ). 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 Õ |J| dependence. This allows us to solve out an upper bound on |J| with quadratic dependence on 1/η.

3.5. PROOF FOR THEOREM 1:

We prove the theorem by stitching Lemma 1 and Condition 2.

Proof. (Proof for Theorem 1)

By lemma 1, for any 2

EQUATION

Here P is a shorthand for polylog 1 1 , 1 1-γ .

Let A t = I[X (2 i ) t ≥ η j-1

] be a Bernoulli random variable, and {F t } t≥1 be the filtration generated by random variables {(s τ , a τ ) : 1 ≤ τ ≤ t}. Since A t is F t+R -measurable, for any 0 ≤ k < R, {A k+tR -E[A k+tR | F k+tR ]} t≥0 is a martingale difference sequence. For now, consider a fixed 0 ≤ k < R. By Azuma-Hoeffiding inequality, after

T = O C 2 i • M ηj

ξi ln(RM L) time steps (if it happens that many times) with Pr X

EQUATION

we have t A k+tR ≥ C/2 i with probability at least 1 -δ/(2M RL).

On the other hand, if A k+tR happens, within [k + tR, k + tR + R -1], there must be at least 2 i time steps at which V * (s t ) -Q * (s t , a t ) > η j-1 . The latter event happens at most C times, and

[k + tR, k + tR + R -1] are disjoint. Therefore, ∞ t=0 A k+tR ≤ C/2 i .

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 -δ/(2M L), there are at most RT time steps where Pr X

(2 i ) t ≥ η j-1 > ξ i /(M η j ).

Thus, the number of sub-optimal steps is bounded by,

∞ t=1 I[V * (s t ) -V πt (s t ) > ] ≤ ∞ t=1 L i=0 M j=2 I η j Pr[X (2 i ) t > η j-1 ] > ξ i M = L i=0 M j=2 ∞ t=1 I Pr[X (2 i ) t > η j-1 ] > ξ i η j M ≤ L i=0 M j=2 SAM R ln 1/δ ln SA η j ξ i • 2 i (1 -γ) 5 P ≤ L i=0 SA • 2 i+4 ln SA ln 1/δ 2 2 (1 -γ) 6

P (By definition of ξ i and η j )

≤ SAR ln SA ln 1/δ 2 2 (1 -γ) 6 P ≤ SA ln SA ln 1/δ 2 2 (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 1 1-γ

. 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 π ) (s t ) > is Õ SA ln 1/δ 2 (1 -γ) 7 ,

where hidden factors are poly(ln 1 , ln 1 1-γ , ln 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 Ω 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 Õ 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 Õ 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 Ω(S 2 A) memory to store the transition model.

4.2. EXTENSION TO OTHER SETTINGS:

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 Õ -2 PAC sample complexity and a Õ 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 Õ( √ T ) regret is that, after choosing 1 , it follows from the argument of Theorem 1 that with probability 1 -δ, for all 2 > Õ( 1 /(1 -γ)), the number of 2 -suboptimal steps is bounded by

O SA ln SA ln 1/δ 2 2 (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 .

5. CONCLUSION:

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 Õ( 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 Õ( SA 2 (1-γ) 7 ). This matches the best lower bound except in dependence on 1/(1 -γ) and logarithmic factors. A PROOF OF LEMMA 1

Lemma 1. For fixed t and η > 0, let

EQUATION

where I[•] is the indicator function.

Proof. When η > 1 the lemma holds trivially. Now consider the case that η ≤ 1.

Let I = {t : V * (s t ) -Q * (s t , a t ) > η 1-γ }. By lemma 2, with probability 1 -δ, η|I| 1 -γ ≤ t∈I (V * (s t ) -Q * (s t , a t )) ≤ t∈I Qt -Q * (s t , a t ) ≤ |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| ln SA|I| (1 -γ) 5/2 + SA ln |I| (1 -γ) 3 Suppose that |I| = SAk 2 η 2 (1-γ) 3 ln SA, for some k > 1. Then it follows that for some constant C 1 , η|I| 1 -γ = k 2 SA ln SA (1 -γ) 4 η ≤ 2 (η -1 )|I| 1 -γ ≤ C 1 ln 1 δ ln 1 1 (1 -γ) SA|I| ln (SA|I|) (1 -γ) 5/2 + SA ln |I| (1 -γ) 3 ≤ C 1 ln 1 δ ln 1 1 (1 -γ) SAk η(1 -γ) 4 ln SA • (ln SA + ln |I|) + SA ln |I| (1 -γ) 3 . Therefore k 2 ln(SA) ≤ C 1 ln 1 δ ln 1 1 (1 -γ) (k (ln SA + ln |I|) + η(1 -γ) ln |I|) ≤ kC 1 ln 1 δ ln 1 1 (1 -γ) • (ln SA + 2 ln |I|) ≤ kC 1 ln 1 δ ln 1 1 (1 -γ) • 3 ln SA + 4 ln k + 6 ln 1 η(1 -γ) ≤ 6kC 1 ln 1 δ ln 2 1 1 (1 -γ) (ln SA + ln ek) . Let C = max{2, 6C 1 ln 1 δ ln 2 1 1(1-γ) }. Then k ≤ C (2 + ln k). (9) If k ≥ 10C ln C , then k -C (2 + ln k) ≥ 8C ln C -(2 + ln 10)C ≥ 4C (2 ln C -4) ≥ 0,

which means violation of (9). Therefore, since

C ≥ 2 k ≤ 10C ln C ≤ 360C 2 1 max{ln 4 1 1 (1 -γ)

, 20 ln 2}.

It immediately follows that

EQUATION

B PROOF OF LEMMA 2

Lemma 2. For every (C, w)-sequence (w t ) t≥1 , with probability 1 -δ/2, the following holds:

t≥1 w t ( Qt -Q * )(s t , a t ) ≤ C 1 1 -γ + O wSAC (C) (1 -γ) 2.5 + wSA ln C (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,

Qp+1 (s, a) ≤ Q p+1 (s, a).

(2) For any p, there exists p ≤ p such that Qp+1 (s, a) ≥ Q p +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 α i t :

1.

1 t ≤ t i=1 α i t 1 i ≤ 2 1 t for every t ≥ 1, c > 0. 2. max i∈[t] α i t ≤ 2H t and t i=1 (α i t ) 2 ≤ 2H t 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 , α 0 t = t j=1 (1 -α j ), α i t = α 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 α i t ι(i) i ≤ t i=1 α i t ι(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, α t t = 1. For t ≥ 2, we have

α i t = (1 -α t )α i t-1 for 1 ≤ i ≤ t -1. It follows that t i=1 α i t ι(i) i = α t ι(t) t + (1 -α t ) t-1 i=1 α i t-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,

EQUATION

EQUATION

where t = N p (s, a), t i = τ (s, a, i) and β t = c 3 Hι(t)/((1 -γ) 2 t).

Proof. Recall that

α 0 t = t j=1 (1 -α j ), α i t = α i t j=i+1

(1 -α j ).

From the update rule, it can be seen that our algorithm maintains the following Q(s, a):

Q p (s, a) = α 0 t 1 1 -γ + t i=1 α i t r(s, a) + b i + γ Vti (s ti+1 ) .

Bellman optimality equation gives:

Q * (s, a) = r(s, a) + γPV * (s, a) = α 0 t Q * (s, a) + t i=1 α i t [r(s, a) + γPV * (s, a)] .

Subtracting the two equations gives

(Q p -Q * )(s, a) = α 0 t ( 1 1 -γ -Q * (s, a)) + t i=1 α i t [b i + γ (V ti -V * ) (s ti+1 ) + γ (V * (s ti+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 = N p (s, a), t i = τ (s, a, i). The t = 0 case is trivial; we assume t ≥ 1 below. Now consider an arbitrary fixed k. Define

∆ i = α i k • I[t i < ∞] • PV * -Pti V * (s, a)

Let F i be the σ-Field generated by random variables (s 1 , a 1 , ..., s ti , a ti ). It can be seen that

E [∆ i |F i ] = 0, while ∆ i is measurable in F i+1 . Also, since 0 ≤ V * (s, a) ≤ 1 1-γ , |∆ i | ≤ 2 1-γ .

Therefore, ∆ i is a martingale difference sequence; by the Azuma-Hoeffding inequality,

EQUATION

)

By choosing η, we can show that with probability

EQUATION

)

Here

c 2 = 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 = N p (s, a) and for all p, with probability 1 -δ/2 as well.

Proof of the right hand side of ( 13): We also know that

(b k = c2 1-γ Hι(k) k ) c 2 1 -γ Hι(k) k ≤ k i=1 α i k b i ≤ 2c 2 1 -γ Hι(k) k .

It is implied by ( 16) that

(Q p -Q * )(s, a) ≤ α 0 t 1 -γ + γ t i=1 ∆ i + t i=1 α i t γ( Vti -V * )(x ti+1 ) + b i ≤ α 0 t 1 -γ + 3c 2 1 -γ Hι(t) t + t i=1 γα i t ( V ti -V * )(x ti+1 )

(Property 4 of lemma 3)

≤ α 0 t 1 -γ + t i=1 γα i t ( V ti -V * )(x ti+1 ) + β t . Note that β t = c 3 (1 -γ) -1 Hι(t)/t; c 3 = 3c 2 = 12 √ 2.

Proof of the left hand side of ( 13): Now, we assume that event that (16) holds. We assert that Q p ≥ Q * for all (s, a) and p ≤ p . This assertion is obviously true when p = 0. Then

(Q p -Q * )(s, a) ≥ -γ t i=1 ∆ i + t i=1 α i t γ( Vti -V * )(x ti+1 ) + b i ≥ t i=1 α i t b i -γ 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 Qp (s, a) is always greater than Q p (s, a) for some p ≤ p, we know that Qp (s, a) ≥ Q p (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 (w t ) t≥1 is said to be a (C, w)-sequence for C, w > 0, if 0 ≤ w t ≤ w for all t ≥ 1, and t≥1 w t ≤ C.

Proof. Let n t = N t (s t , a t ) for simplicity; we have

EQUATION

The last inequality is due to lemma 4. Note that α 0 nt = I[n t = 0], the first term in the summation can be bounded by,

EQUATION

)

For the second term, define u(s, a) = sup t N t (s, a).2 It follows that,

EQUATION

≤ 2 s,a

(1 -γ) -1 c 3 ι(C)HC s,a w (20)

EQUATION

Where C s,a = t≥1,(st,at)=(s,a) w t . 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

EQUATION

Define

w t +1 =     ∞ t=t +1 (st,at)=(s t ,a t ) α n t nt w t     .

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, Hw ln(C s,a /w) ≤ 2SAHw ln C.

w t +1 ≤ w ∞ j=n t α n t j By i j=0 α j i = 1,

EQUATION

Putting ( 18), ( 21) and ( 27) together, we have,

EQUATION

)

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 w t ( Qt -Q * )(s t , a t ) ≤ 2c 3 w (H) SAHCι(C) (1 -γ) 2 + O w (H) SAH (1 -γ) 2 ln C + γ H t≥1 w (H) t Qt -Q * (s t , a t ) ≤ 2c 3 w (H) SAHCι(C) (1 -γ) 2 + O w (H) SAH (1 -γ) 2 ln C + γ 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) H w (0) ≤ ew (0) , and that γ H C 1-γ ≤ C 1 . Also, let (C) = ι(C) ln((1 -γ) -1 -1 1 ). Therefore,

EQUATION

• S = S × H, Ā = A;

• γ = (1 -1/H);

• for a state s at step h, let ss,h be the corresponding state. For any action a and next state s , define r(s s,h , a) = γ H-h+1 r h (s, a) and p(s s ,h+1 | ss,h , a) = p h (s, h). And for h = H, set r(s s,h , a) = 0 and p(s s ,1 | ss,h , a) = I[s = s 1 ] for a fixed starting state s 1 .

For a trajectory {(s s1,1 , ā1 ), (s s2,2 , ā2 ), • • • } in M, let {(s 1 , a 1 ), (s 2 , a 2 ), • • • } be the corresponding trajectory in M. Note that M has a unique fixed starting state s 1 , which means that s tH+1 = s 1 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 , ā1 ) + γ r(s s2,2 , ā2 ) + • • • + γ H-1 r(s s H-1 ,H-1 , āH-1 ) + γ H V π t+H-1 (s s H+1 ,1 )

= γ H E r 1 (s 1 , a 1 ) + r 2 (s 2 , a 2 ) + • • • + r H-1 (s H-1 , a H-1 ) + V π t+H (s s H+1 ,1 )

= γ H V π t (s 1 ) + γ H V π t+H (s s1,1 ).

Then for a stationary policy π, we can conclude V π (s s1,1 ) = γ H 1-γ H V π (s 1 ). Since the optimal policy π * is stationary, we have V * (s s1,1 ) = γ H 1-γ H V * (s 1 ). By definition, π is -optimal at time step t means that V πt (s s1,1 ) ≥ V * (s s1,1 ) -.

It follows that:

γ H V π t (s 1 ) + γ H V π t+H (s s1,1 ) = V π (s s1,1 ) ≥ V * (s s1,1 ) -, hence γ H V π t (s 1 ) ≥ (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 (s 1 ) ≥ 1 -γ H γ H V * (s s1,1 ) -/γ H = V * (s 1 ) -/γ H , which means that π t is an ( /γ H )-optimal policy.

D A HARD INSTANCE FOR DELAYED Q-LEARNING:

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 < < 1 10 , consider the following MDP (see also Fig. 1 ): state space is S = {a, b, c} while action set is A = {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.

:

ηM > 1/(1 -γ) can be verified by combining inequalities ξi •

M/2 ≥ 1/(1 -γ) and 2 M/2-1 > (M + 1) for large enough M .

u(s, a) could be infinity when (s, a) is visited for infinite number of times.

Figures and Tables:

Figure 1: The MDP family. Actions are denoted by arrows. Actions with red color have reward 1, and reward 0 otherwise.

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-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, 2018b.

Table content: <table><tr><td>Alexander L Strehl and Michael L Littman. An analysis of model-based interval estimation for</td></tr><tr><td>markov decision processes. Journal of Computer and System Sciences, 74(8):1309-1331, 2008.</td></tr><tr><td>Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. Pac model-</td></tr><tr><td>free reinforcement learning. In Proceedings of the 23rd international conference on Machine</td></tr><tr><td>learning, pp. 881-888. ACM, 2006.</td></tr><tr><td>István Szita and Csaba Szepesvári. Model-based reinforcement learning with nearly tight exploration</td></tr><tr><td>complexity bounds. In Proceedings of the 27th International Conference on Machine Learning</td></tr><tr><td>(ICML-10), pp. 1031-1038, 2010.</td></tr></table>

we have t ≥1 w t +1 ≤ t≥1 w t ≤ C. This proves the assertion. It follows from (22) that

Table content: <table><tr><td>t≥1</td></tr></table>

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 =

Table content: <table><tr><td>s,a</td><td>C s,a /w n=1</td><td>w</td><td>H n</td><td>≤</td><td>s,a</td></tr></table>

Peer review (iclr2020):
This paper extends Jin et al. (2018)*s idea to infinite horizon and improves the best known sample complexity to . The derivation is similar to Jin*s paper except a very careful selection on the pseudo-horizon length , where is given in finite horizon and work as the decaying rate for , but for infinite horizon when we need to decide how to pick . Theoretical 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. Novelty: 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 is with leaving probability less than . In this case, the latter rewards counted for will multiply by 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 , which is definitely related to 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. Minor issue: In algorithm box I didn*t see which occurs a lot in the derivation. Maybe change and in the way align to the derivation? Overall 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.