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. 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Õ( . 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. In this section, we discuss the implication of our results, and present some interesting properties of our algorithm beyond its sample complexity bound. 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Õ( -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Õ( . 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 B (t) η be the event that V * (s t ) − Q * (s t , a t ) > η 1−γ in step t. If η > 2 1 , then with probability at least 1 − δ/2, where I[·] is the indicator function. Proof. When η > 1 the lemma holds trivially. Now consider the case that η ≤ 1. By lemma 2, with probability 1 − δ, Suppose that |I| = SAk 2 η 2 (1−γ) 3 ln SA, for some k > 1. Then it follows that for some constant If k ≥ 10C ln C , then which means violation of (9). Therefore, since C ≥ 2 , 20 ln 2}. It immediately follows that B PROOF OF LEMMA 2 Lemma 2. For every (C, w)-sequence (w t ) t≥1 , with probability 1 − δ/2, the following holds: where (C) = ι(C) ln is a log-factor. (2) For any p, there exists p ≤ p such that 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 : t where ι(t) = ln(c(t+1)(t+2)), for every t ≥ 1, c ≥ 1. Proof. Recall that (1 − α j ). Properties 1-3 are proven by Jin et al. (2018) . Now we prove the last property. On the one hand, 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, α Since function f (t) = ι(t)/t is monotonically decreasing for t ≥ 1, c ≥ 1, we have Lemma 4. With probability at least 1 − δ/2, for all p ≥ 0 and (s, a)-pair, where t = N p (s, a), t i = τ (s, a, i) and β t = c 3 Hι(t)/((1 − γ) 2 t). Proof. Recall that (1 − α j ). From the update rule, it can be seen that our algorithm maintains the following Q(s, a): Bellman optimality equation gives: Subtracting the two equations gives 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 Let F i be the σ-Field generated by random variables (s 1 , a 1 , ..., s ti , a ti ). It can be seen that 1−γ . Therefore, ∆ i is a martingale difference sequence; by the Azuma-Hoeffding inequality, By choosing η, we can show that with probability 1 − δ/ [SA(k + 1)(k + 2)], Here . By a union bound for all k, this holds for arbitrary k > 0, arbitrary s ∈ S, a ∈ A simultaneously with probability 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 ( It is implied by (16) that (Property 4 of lemma 3) 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 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. SinceQ p (s, a) is always greater than Q p (s, a) for some p ≤ p, we know thatQ p (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 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, For the second term, define u(s, a) = sup t N t (s, a). 2 It follows that, 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 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,
We adapt Q-learning with UCB-exploration bonus to infinite-horizon MDP with discounted rewards without accessing a generative model, and improves the previously best known result. This paper considered a Q-learning algorithm with UCB exploration policy for infinite-horizon MDP.