Journal of Machine Learning Research 5 (2003) 1-25 Submitted 4/02; Revised 9/02; Published 12/03

Learning Rates for Q-learning

Eyal Even-Dar evend@cs.tau.ac.il Yishay Mansour mansour@cs.tau.ac.il School of Computer Science Tel-Aviv University Tel-Aviv, 69978, Israel

Editor: Peter Bartlett

Abstract

In this paper we derive convergence rates for Q-learning. We show an interesting relationship between the convergence rate and the learning rate used in Q-learning. For a polynomial learning rate, one which is 1/t^{ω} at time t where ω ∈ (1/2,1), we show that the convergence rate is polynomial in 1/(1 − γ), where γ is the discount factor. In contrast we show that for a linear learning rate, one which is 1/t at time t, the convergence rate has an exponential dependence on 1/(1 − γ). In addition we show a simple example that proves this exponential behavior is inherent for linear learning rates. Keywords: Reinforcement Learning, Q-Learning, Stochastic Processes, Convergence Bounds, Learning Rates.

1. Introduction

In Reinforcement Learning, an agent wanders in an unknown environment and tries to maximize its long term return by performing actions and receiving rewards. The challenge is to understand how a current action will affect future rewards. A good way to model this task is with Markov Decision Processes (MDP), which have become the dominant approach in Reinforcement Learning (Sutton and Barto, 1998, Bertsekas and Tsitsiklis, 1996).

An MDP includes states (which abstract the environment), actions (which are the available actions to the agent), and for each state-action pair, a distribution of next states (the states reached after performing the action in the given state). In addition there is a reward function that assigns a stochastic reward for each state and action. The return combines a sequence of rewards into a single value that the agent tries to optimize. A discounted return has a parameter γ ∈ (0,1) where the reward received at step k is discounted by γ^{k}.

One of the challenges of Reinforcement Learning is when the MDP is not known, and we can only observe the trajectory of states, actions and rewards generated by the agent wandering in the MDP. There are two basic conceptual approaches to the learning problem. The first is model based, where we first reconstruct a model of the MDP, and then find an optimal policy for the approximate model. The second approach is implicit methods that update the information after each step, and based on this derive an estimate to the optimal policy. The most popular of those methods is Qlearning (Watkins, 1989).

Q-learning is an off-policy method that can be run on top of any strategy wandering in the MDP. It uses the information observed to approximate the optimal function, from which one can

\begin{matrix}c \\ ◯ \end{matrix} 2003 Eyal Even-Dar and Yishay Mansour.

Even-Dar and Mansour

construct the optimal policy. There are various proofs that Q-learning does converge to the optimal Q function, under very mild conditions (Bertsekas and Tsitsiklis, 1996, Tsitsiklis, 1994, Watkins and Dyan, 1992, Littman and Szepesvári, 1996, Jaakkola et al., 1994, Borkar and Meyn, 2000). The conditions have to do with the exploration policy and the learning rate. For the exploration one needs to require that each state action be performed infinitely often. The learning rate controls how fast we modify our estimates. One expects to start with a high learning rate, which allows fast changes, and lowers the learning rate as time progresses. The basic conditions are that the sum of the learning rates goes to infinity (so that any value could be reached) and that the sum of the squares of the learning rates is finite (which is required to show that the convergence is with probability one).

We build on the proof technique of Bertsekas and Tsitsiklis (1996), which is based on convergence of stochastic iterative algorithms, to derive convergence rates for Q-learning. We study two models of updating in Q-learning. The first is the synchronous model, where all state action pairs are updated simultaneously. The second is the asynchronous model, where at each step we update a single state action pair. We distinguish between two sets of learning rates. The most interesting outcome of our investigation is the relationship between the form of the learning rates and the rate of convergence. A linear learning rate is of the form 1/t at time t, and a polynomial learning rate, which is of the form 1/t^{ω}, where ω ∈ (1/2,1) is a parameter.

We show for synchronous models that for a polynomial learning rate the convergence rate is polynomial in 1/(1 − γ), while for a linear learning rate the convergence rate is exponential in 1/(1 − γ). We also describe an MDP that has exponential behavior for a linear learning rate. The lower bound simply shows that if the initial value is one and all the rewards are zero, it takes O((1/ϵ)^{1/(1−γ)}) updates, using a linear learning rate, until we reach a value of ϵ.

The different behavior might be explained by the asymptotic behavior of ∑_{t}α_{t}, one of the conditions that ensure that Q-learning converges from any initial value. In the case of a linear learning rate we have that ∑ _{t=1}^{T} α_{t} = O(ln(T)), whereas using polynomial learning rate it behaves as O(T^{1−ω} ). Therefore, using polynomial learning rate each value can be reached by polynomial number of steps and using linear learning rate each value requires exponential number of steps.

The convergence rate of Q-learning in a batch setting, where many samples are averaged for each update, was analyzed by Kearns and Singh (1999). A batch setting does not have a learning rate and has much of the flavor of model based techniques, since each update is an average of many samples. A run of a batch Q-learning is divided into phases, at the end of each phase an update is made. The update after each phase is reliable since it averages many samples.

The convergence of Q-learning with linear learning rate was studied by Szepesvari (1998) for special MDPs, where the next state distribution is the same for each state. (This setting is much closer to the PAC model, since there is no influence between the action performed and the states reached, and the states are i.i.d distributed). For this model Szepesvari (1998) shows a convergence rate, which is exponential in 1/(1 − γ). Beleznay et al. (1999) give an exponential lower bound in the number of the states for undiscounted return.

2. The Model

We define a Markov Decision process (MDP) as follows

Learning Rates for Q-learning

Definition 1 A Markov Decision process (MDP) M is a 4-tuple (S,U,P,R), where S is a set of the states, U is a set of actions (U(i) is the set of actions available at state i), P_{i,j}^{M}(a) is the transition probability from state i to state j when performing action a ∈ U(i) in state i, and R_{M}(s,a) is the reward received when performing action a in state s.

We assume that R_{M}(s,a) is non-negative and bounded by R_{max}, i.e., ∀s,a: 0 ≤ R_{M}(s,a) ≤ R_{max}. For simplicity we assume that the reward R_{M}(s,a) is deterministic, however all our results apply when R_{M}(s,a) is stochastic.

A strategy for an MDP assigns, at each time t, for each state s a probability for performing action a ∈ U(s), given a history F_{t−1} = {s_{1},a_{1},r_{1},...,s_{t−1},a_{t−1},r_{t−1}} which includes the states, actions and rewards observed until time t − 1. A policy is memory-less strategy, i.e., it depends only on the current state and not on the history. A deterministic policy assigns each state a unique action.

While following a policy π we perform at time t action a_{t} at state s_{t} and observe a reward r_{t} (distributed according to R_{M}(s,a)), and the next state s_{t+1} (distributed according to P_{s_{t},s_{t+1}}^{M}(a_{t})). We combine the sequence of rewards to a single value called the return, and our goal is to maximize the return. In this work we focus on discounted return, which has a parameter γ ∈ (0,1), and the discounted return of policy π is V_{M}^{π} = ∑ _{t=0}^{∞} γ^{t}r_{t}, where r_{t} is the reward observed at time t. Since all the rewards are bounded by R_{max}the discounted return is bounded by V_{max}= \frac{R_{max}}{1−γ}.

We define a value function for each state s, under policy π, as V_{M}^{π}(s) = E[∑ _{i=0}^{∞} r_{i}γ^{i}], where the expectation is over a run of policy π starting at state s. We define a state-action value function Q_{M}^{π}(s,a) = R_{M}(s,a) + γ∑ s̄P_{s,s̄}^{M}(a)V_{M}^{π}(s̄) , whose value is the return of initially performing action a at state s and then following policy π. Since γ < 1 we can define another parameter β = (1 − γ)/2, which will be useful for stating our results. (Note that as β decreases V_{max}increases.)

Let π^{∗} be an optimal policy, which maximizes the return from any start state. (It is well known that there exists an optimal strategy, which is a deterministic policy (Puterman., 1994).) This implies that for any policy π and any state s we have V_{M}^{π^{∗}}(s) ≥ V_{M}^{π}(s), and π^{∗}(s) = argmax_{a}(R_{M}(s,a)+ γ(∑_{s′}P_{s,s′}^{M}(a)max_{b}Q(s′,b)). The optimal policy is also the only fixed point of the operator, (T Q)(s,a) = R_{M}(s,a) + γ∑_{s′}P_{s,s′}(a)max_{b}Q(s′,b). We use V_{M}^{∗} and Q_{M}^{∗} for V_{M}^{π^{∗}} and Q_{M}^{π^{∗}}, respectively. We say that a policy π is an ϵ-approximation of the optimal policy if ∥V_{M}^{∗}− V_{M}^{π}∥_{∞} ≤ ϵ.

For a sequence of state-action pairs let the covering time, denoted by L, be an upper bound on the number of state-action pairs starting from any pair, until all state-action appear in the sequence. Note that the covering time can be a function of both the MDP and the sequence or just of the sequence. Initially we assume that from any start state, within L steps all state-action pairs appear in the sequence. Later, we relax the assumption and assume that with probability at least \frac{1}{2}, from any start state in L steps all state-action appear in the sequence. In this paper, the underlying policy generates the sequence of state action pairs.

The Parallel Sampling Model, PS(M), as was introduced by Kearns and Singh (1999). The PS(M) is an ideal exploration policy. A single call to PS(M) returns for every pair (s,a) the next state s′, distributed according to P_{s,s′}^{M}(a) and a reward r distributed according to R_{M}(s,a). The advantage of this model is that it allows to ignore the exploration and to focus on the learning. In some sense PS(M) can be viewed as a perfect exploration policy.

Notations: The notation g = Ω̃(f) implies that there are constants c_{1} and c_{2} such that g ≥ c_{1}f ln^{c_{2}}(f). All the norms ∥ · ∥, unless otherwise specified, are L_{∞} norms, i.e., ∥(x_{1},...,x_{n})∥ = max_{i}x_{i}.

3. Q-learning

The Q-learning algorithm (Watkins, 1989) estimates the state-action value function (for discounted return) as follows:

Q_{t+1}(s,a) = (1 − α_{t}(s,a))Q_{t}(s,a) + α_{t}(s,a)(R_{M}(s,a) + γ max_{b∈U(s′)}Q_{t}(s′,b)),  (1)

where s′ is the state reached from state s when performing action a at time t. Let T^{s,a} be the set of times, where action a was performed at state s, then α_{t}(s,a) = 0 for t ∉ T^{s,a}. It is known that Q-learning converges to Q^{∗} if each state action pair is performed infinitely often and α_{t}(s,a) satisfies for each (s,a) pair: ∑ _{t=1}^{∞} α_{t}(s,a) = ∞ and ∑ _{t=1}^{∞} α_{t}^{2}(s,a) < ∞ (Bertsekas and Tsitsiklis, 1996, Tsitsiklis, 1994, Watkins and Dyan, 1992, Littman and Szepesvári, 1996, Jaakkola et al., 1994).

Q-learning is an asynchronous process in the sense that it updates a single entry each step. Next we describe two variants of Q-learning, which are used in the proofs. The first algorithm is synchronous Q-learning, which performs the updates by using the PS(M). Specifically:

∀s,a : Q_{0}(s,a) = C
∀s,a : Q_{t+1}(s,a) = (1 − α_{t}^{ω})Q_{t}(s,a) + α_{t}^{ω}(R_{M}(s,a) + γ max_{b∈U(s̄)}Q_{t}(s̄,b)),

where s̄is the state reached from state s when performing action a and C is some constant. The learning rate is α_{t}^{ω} = \frac{1}{(t+1)^{ω}} , for ω ∈ (1/2,1]. We distinguish between a linear learning rate, which is ω = 1, and a polynomial learning rate, which is ω ∈ (\frac{1}{2},1).

The asynchronous Q-learning algorithm, is simply regular Q-learning as define in (1), and we add the assumption that the underlying strategy has a covering time of L. The updates are as follows:

∀s,a : Q_{0}(s,a) = C
∀s,a : Q_{t+1}(s,a) = (1 − α_{t}^{ω}(s,a))Q_{t}(s,a) + α_{t}^{ω}(s,a)(R_{M}(s,a) + γ max_{b∈U(s̄)}Q_{t}(s̄,b))

where s̄is the state reached from state s when performing action a and C is some constant. Let #(s,a,t) be one plus the number of times, until time t, that we visited state s and performed action a. The learning rate α_{t}^{ω}(s,a) = \frac{1}{[#(s,a,t)]^{ω}}, if t ∈ T^{s,a} and α_{t}^{ω}(s,a) = 0 otherwise. Again, ω = 1 is a linear learning rate, and ω ∈ (\frac{1}{2},1) is a polynomial learning rate.

4. Our Main Results

Our main results are upper bounds on the convergence rates of Q-learning algorithms and showing their dependence on the learning rate. The basic case is the synchronous Q-learning. We show that for a polynomial learning rate we have a complexity, which is polynomial in 1/(1−γ) = 1/(2β). In contrast, we show that linear learning rate has an exponential dependence on 1/β. Our results exhibit a sharp difference between the two learning rates, although they both converge with probability one. This distinction, which is highly important, can be observed only when we study the convergence rate, rather than convergence in the limit.

The bounds for asynchronous Q-learning are similar. The main difference is the introduction of a covering time L. For polynomial learning rate we derive a bound polynomial in 1/β, and for linear learning rate our bound is exponential in \frac{1}{β}. We also show a lower bound for linear learning rate, which is exponential in \frac{1}{β}. This implies that our upper bounds are tight, and that the gap between the two bounds is real.

We first prove the results for the synchronous Q-learning algorithm, where we update all the entries of the Q function at each time step, i.e., the updates are synchronous. The following theorem derives the bound for polynomial learning rate.

Theorem 2 Let Q_{T} be the value of the synchronous Q-learning algorithm using polynomial learning rate at time T. Then with probability at least 1 − δ, we have that ||Q_{T}− Q^{∗}|| ≤ ϵ, given that

T = Ω( ( \frac{V_{max}^{2}ln(\frac{|S| |A|V_{max}}{δβϵ})}{β^{2}ϵ^{2}}) ^{\frac{1}{ω}} + ( \frac{1}{β} ln \frac{V_{max}}{ϵ}) ^{\frac{1}{1−ω}} )

The above bound is somewhat complicated. To simplify, assume that ω is a constant and consider first only its dependence on ϵ. This gives us Ω((ln(1/ϵ)/ϵ^{2})^{1/ω} + (ln(1/ϵ))^{1/(1−ω)} ), which is optimized when ω approaches one. Considering the dependence only on β, recall that V_{max}= R_{max}/(2β), therefore the complexity is Ω̃(1/β^{4/ω} + 1/β^{1/(1−ω)} ) which is optimized for ω = 4/5. The following theorem bounds the time for linear learning rate.

Theorem 3 Let Q_{T} be the value of the synchronous Q-learning algorithm using linear learning rate at time T. Then for any positive constant ψ with probability at least 1−δ, we have ||Q_{T}−Q^{∗}|| ≤ ϵ, given that

T = Ω( ((2 + ψ)^{\frac{1}{β} ln( \frac{Vmax}{ϵ})} \frac{V_{max}^{2}ln(\frac{|S| |A|V_{max}}{δβψϵ})}{(ψβϵ)^{2}}) .

Next we state our results to asynchronous Q-learning. The bounds are similar to those of synchronous Q-learning, but have the extra dependency on the covering time L.

Theorem 4 Let Q_{T} be the value of the asynchronous Q-learning algorithm using polynomial learning rate at time T. Then with probability at least 1 − δ, we have ||Q_{T}− Q^{∗}|| ≤ ϵ, given that

T = Ω( ( \frac{L^{1+3ω} V_{max}^{2}ln(\frac{|S| |A|V_{max}}{δβϵ})}{β^{2}ϵ^{2}}) ^{\frac{1}{ω}} + ( \frac{L}{β}ln \frac{V_{max}}{ϵ}) ^{\frac{1}{1−ω}} )

The dependence on the covering time, in the above theorem, is Ω(L^{2+1/ω} + L^{1/(1−ω)} ), which is optimized for ω ≈ 0.77. For the linear learning rate the dependence is much worse, since it has to be that L ≥ |S| · |A|, as is stated in the following theorem.

Theorem 5 Let Q_{T} be the value of the asynchronous Q-learning algorithm using linear learning rate at time T. Then with probability at least 1−δ, for any positive constant ψ we have ||Q_{T}−Q^{∗}|| ≤ ϵ, given that

T = Ω( (L + ψL + 1) ^{^{\frac{1}{β}} ln^{\frac{Vmax}{ϵ}}} \frac{V_{max}^{2}ln(\frac{|S| |A|V_{max}}{δβϵψ})}{(ψβϵ)^{2}})

The following theorem shows that a linear learning rate may require an exponential dependence on 1/(2β) = 1/(1 − γ), thus showing that the gap between linear learning rate and polynomial learning rate is real and does exist for some MDPs.

Theorem 6 There exists a deterministic MDP, M, such that Q-learning with linear learning rate after T = Ω((\frac{1}{ϵ})^{\frac{1}{1−γ}} ) steps has ∥Q_{T}− Q_{M}^{∗}∥ > ϵ.

5. Experiments

In this section we present experiments using two types of MDPs as well as one we call M_{0}, which is used in the lower bound example from Section 10. The two MDP types are the “random MDP” and “line MDP”. Each type contains n states and two actions for each state.

We generate the “random MDP” as follows: For every state i, action a and state j, we assign a random number n_{i,j}(a) uniformly from [0,1]. The probability of a transition from state i to state j while performing action a is p_{i,j}(a) = \frac{n_{i,j}(a)}{∑_{k}n_{i,k}(a)}. The reward R(s,a) is deterministic and chosen at random uniformly in the interval [0,10].

For the line MDP, all the states are integers and the transition probability from state i to state j is proportional to \frac{1}{|i−j|} , where i ≠ j. The reward distribution is identical to that of the random MDP. (We implemented the random function using the function rand() in C.)

Figure 1: Example of 100 states MDP (both line and random), where the discount factor is γ = 0.7. We ran asynchronous Q-learning using a random exploration policy for 10^{8} steps.

Figure 1 demonstrates the relation between the exponent of the learning rate ω and the accuracy of the model. The best experimental value for ω is about 0.85. Note that when ω approaches one (a linear learning rate), the precision deteriorates. This behavior coincides with our theoretical results on two points. First, our theoretical results predict bad behavior when the learning rate approaches one (an exponential lower and upper bound). Second, the experiments suggest an optimal value for ω of approximately 0.85. Our theoretical results derive optimal values of optimal ω for different settings of the parameters but most give a similar range. Furthermore, the two types of MDP have similar behavior, which implies that the difference between linear and polynomial learning rates is inherent to many MDPs and not only special cases (as in the lower bound example).

Figure 2: Example of 10 state MDPs (both random and line) using two different learning rates for Q-learning. Both use random exploration policy for 10^{7} steps. The solid line is asynchronous Q-learning using ω = 0.7; the dashed line is asynchronous Q-learning using a linear learning rate (ω = 1.0).

Figure 2 demonstrates the strong relationship between discount factor, γ, and convergence rate. In this experiment, we again see similar behavior in both MDPs. When the discount factor approaches one, Q-learning using linear learning rate estimation of the Q value becomes unreliable, while Q-learning using learning rate of ω = 0.7 remains stable (the error is below 0.1).

Figure 3 compares two different learning rates ω = 0.6 and ω = 0.9 for ten state MDPs (both random and line) and finds an interesting tradeoff. For low precision levels, the learning rate of ω = 0.6 was superior, while for high precision levels the learning rate of ω = 0.9 was superior. An explanation for this behavior is that the dependence in terms of ϵ is Ω((ln(1/ϵ)/ϵ^{2})^{1/ω} + (ln(1/ϵ))^{1/(1−ω)} ), which is optimized as the learning rate approaches one.

Our last experimental result is M_{0}, the lower bound example from Section 10. Here the difference between the learning rates is the most significant, as shown in Figure 4.

6. Background from Stochastic Algorithms

Before we derive our proofs, we first introduce the proof given by Bertsekas and Tsitsiklis (1996) for the convergence of stochastic iterative algorithms; in Section 7 we show that Q-learning algorithms fall in this category. In this section we review the proof for convergence in the limit, and in the next sections we will analyze the rate at which different Q-learning algorithms converge. (We will try to keep the background as close as possible to the needs for this paper rather than giving the most general results.)

Figure 3: Random and Line MPDs (10 states each), where the discount factor is γ = 0.9. The dashed line is synchronous Q-learning using ω = 0.9 and the the solid line is synchronous Q-learning using ω = 0.6.

Figure 4: Lower bound example M_{0}, with discount factor γ = 0.9. Q-learning ran with two different learning rates, linear (dashed line) and ω = 0.65 (solid line).

This section considers a general type of iterative stochastic algorithms, which is computed as follows:

X_{t+1}(i) = (1 − α_{t}(i))X_{t}(i) + α_{t}(i)((H_{t}X_{t})(i) + w_{t}(i)),  (2)

where w_{t} is a bounded random variable with zero expectation, and each H_{t} is assumed to belong to a family H of pseudo contraction mappings (See Bertsekas and Tsitsiklis (1996) for details).

Definition 7 An iterative stochastic algorithm is well-behaved if:

1. The step size α_{t}(i) satisfies (1) ∑ _{t=0}^{∞} α_{t}(i) = ∞, (2) ∑ _{t=0}^{∞} α_{t}^{2}(i) < ∞ and (3) α_{t}(i) ∈ (0,1).

2. There exists a constant A that bounds w_{t}(i) for any history F_{t}, i.e., ∀t,i: |w_{t}(i)| ≤ A.

3. There exists γ ∈ [0,1) and a vector X^{∗} such that for any X we have ||H_{t}X −X^{∗}|| ≤ γ||X −X^{∗}||.

The main theorem states that a well-behaved stochastic iterative algorithm converges in the limit.

Theorem 8 [Bertsekas and Tsitsiklis (1996)] Let X_{t} be the sequence generated by a well-behaved stochastic iterative algorithm. Then X_{t} converges to X^{∗} with probability 1.

The following is an outline of the proof given by Bertsekas and Tsitsiklis (1996). Without loss of generality, assume that X^{∗} = 0 and ∥X_{0}∥ ≤ A. The value of X_{t} is bounded since ∥X_{0}∥ ≤ A and for any history F_{t} we have ∥w_{t}∥ ≤ A; hence, for any t we have ∥X_{t}∥ ≤ A.

Recall that β = \frac{1−γ}{2} . Let D_{1} = A and D_{k+1} = (1 − β)D_{k} for k ≥ 1. Clearly the sequence D_{k} converges to zero. We prove by induction that for every k there exists some time τ_{k} such that for any t ≥ τ_{k} we have ∥X_{t}∥ ≤ D_{k}. Note that this will guarantee that at time t ≥ τ_{k} for any i the value ∥X_{t}(i)∥ is in the interval [−D_{k},D_{k}].

The proof is by induction. Assume that there is such a time τ_{k} and we show that there exists a time τ_{k+1} such that for t ≥ τ_{k+1} we have ∥X_{t}∥ ≤ D_{k+1}. Since D_{k} converges to zero this proves that X_{t} converges to zero, which equals X^{∗}. For the proof we define for t ≥ τ the quantity

W_{t+1;τ}(i) = (1 − α_{t}(i))W_{t;τ}(i) + α_{t}(i)w_{t}(i),

where W_{τ;τ}(i) = 0. The value of W_{t;τ}bounds the contributions of w_{j}(i), j ∈ [τ,t], to the value of X_{t} (starting from time τ). We also define for t ≥ τ_{k},

Y_{t+1;τ}(i) = (1 − α_{t}(i))Y_{t;τ}(i) + α_{t}(i)γD_{k}

where Y_{τ_{k};τ_{k}} = D_{k}. Notice that Y_{t;τ_{k}} is a deterministic process. The following lemma gives the motivation for the definition of Y_{t;τ_{k}}.

Lemma 9 [Bertsekas and Tsitsiklis (1996)] For every i, we have

−Y_{t;τ_{k}}(i) + W_{t;τ_{k}}(i) ≤ X_{t}(i) ≤ Y_{t;τ_{k}}(i) + W_{t;τ_{k}}(i)

Next we use Lemma 9 to complete the proof of Theorem 8. From the definition of Y_{t;τ} and the assumption that ∑ _{t=0}^{∞} α_{t} = ∞, it follows that Y_{t;τ}converges to γD_{k} as t goes to infinity. In addition W_{t;τ_{k}} converges to zero as t goes to infinity. Therefore there exists a time τ_{k+1} such that Y_{t;τ}≤ (γ + \frac{β}{2})D_{k}, and |W_{t;τ_{k}}| ≤ βD_{k}/2. This fact, together with Lemma. 9, yields that for t ≥ τ_{k+1},

||X_{t}|| ≤ (γ + β)D_{k} = D_{k+1},

which completes the proof of Theorem 8.

7. Applying the Stochastic Theorem to Q-learning

In this section we show that both synchronous and asynchronous Q-learning are well-behaved iterative stochastic algorithms. The proof is similar in spirit to the proof given by Bertsekas and Tsitsiklis (1996) At the beginning we deal with synchronous Q-learning. First define operator H as

(HQ)(i,a) = ∑_{j=0}^{n} P_{ij}(a)(R(i,a) + γ max_{b∈U(j)} Q(j,b))

Rewriting Q-learning with H, we get

Q_{t+1}(i,a) = (1 − α_{t}(i,a))Q_{t}(i,a) + α_{t}(i,a)((HQ_{t})(i,a) + w_{t}(i,a)).

Let īis the state reached by performing at time t action a in state i and r(i,s) is the reward observed at time i; then

w_{t}(i,s) = r(i,s) + γ max_{b∈U(ī)}Q_{t}(ī,b) − ∑_{j=0}^{n} P_{ij}(a)( R(i,a) + γ max_{b∈U(j)} Q_{t}(j,b))

In synchronous Q-learning, H is computed simultaneously on all states actions pairs.

Lemma 10 Synchronous Q-learning is a well-behaved iterative stochastic algorithm.

Proof We know that for any history F_{t} E[w_{t}(i,a)|F_{t}] = 0 and |w_{t}(i,a)| ≤ V_{max}. We also know that for \frac{1}{2} < ω ≤ 1 we have that ∑ α_{t}(s,a) = ∞, ∑ α_{t}^{2}(s,a) < ∞ and α_{t}(s,a) ∈ (0,1). We need only show that H satisfies the contraction property.

|(HQ)(i,a) − (HQ̄)(i,a)| ≤ ∑_{j=0}^{n} P_{ij}(a)|γ max_{b∈U(j)} Q(j,b) − γ max_{b∈U(j)} Q̄(j,b)|

= ∑_{j=0}^{n} P_{ij}(a)γ| max_{b∈U(j)} Q(j,b) − max_{b∈U(j)} Q̄(j,b)|

≤ ∑_{j=0}^{n} P_{ij}(a)γ max_{b∈U(j)} |Q(j,b) − Q̄(j,b)|

≤ γ ∑_{j=0}^{n} P_{ij}(a)∥Q − Q̄∥ ≤ γ∥Q − Q̄∥

Since we update all (i,a) pairs simultaneously, synchronous Q-learning is well-behaved stochastic iterative algorithm.

We next show that Theorem 8 can be applied also to asynchronous Q-learning.

Lemma 11 Asynchronous Q-learning, where the input sequence has a finite covering time L, is a well-behaved iterative stochastic algorithm.

Proof We define HQ for every start state i and start time t_{1} of a phase (beginning of the covering time) until the end of the phase (completing the covering time) at time t_{2}, during which all stateaction pairs are updated. Since a state action can be performed more than once, HQ(i,a) can be performed more than once. We consider time t, in which the policy performs action a at state i and Q_{t} is the vector. We have that

|(HQ_{t})(i,a) − (HQ^{∗})(i,a)| ≤ ∑_{j=0}^{n} P_{ij}(a)|γ max_{b∈U(j)} Q_{t}(j,b) − γ max_{b∈U(j)} Q^{∗}(j,b)|

= ∑_{j=0}^{n} P_{ij}(a)γ| max_{b∈U(j)} Q_{t}(j,b) − max_{b∈U(j)} Q^{∗}(j,b)|

≤ ∑_{j=0}^{n} P_{ij}(a)γ max_{b∈U(j)} |Q_{t}(j,b) − Q^{∗}(j,b)|
≤ ∑_{j∈A} P_{ij}(a)γ max_{b∈U(j)} |Q_{t}(j,b) − Q^{∗}(j,b)|

+ ∑_{j∈B} P_{ij}(a)γ max_{b∈U(j)} |Q_{t}(j,b) − Q^{∗}(j,b)|

≤ γ∥Q_{t}− Q^{∗}∥,

where A includes the states for which during (t_{1},t) all the actions in U(i) were performed, and B = S − A. We conclude that ∥Q_{t′}− Q^{∗}∥ ≤ ∥Q_{t′−1} − Q^{∗}∥, since we only change at each time a single state-action pair, which satisfies |HQ_{t}(i,a) − Q^{∗}(i,a)| ≤ γ|Q_{t}− Q^{∗}|. We look at the operator H after performing all state-action pairs, ∥HQ − Q^{∗}∥ ≤ max_{i,a}|HQ_{t}(i,a) − Q^{∗}(i,a)| ≤ γ∥Q_{t}− Q^{∗}∥ ≤ γ∥Q − Q^{∗}∥.

8. Synchronous Q-learning

In this section we give the proof of Theorems 2 and 3. Our main focus will be the value of r_{t} = ∥Q_{t}− Q^{∗}∥, and our aim is to bound the time until r_{t} ≤ ϵ. We use a sequence of values D_{i}, such that D_{k+1} = (1 − β)D_{k} and D_{1} = V_{max}. As in Section 6, we will consider times τ_{k} such that for any t ≥ τ_{k} we have r_{t} ≤ D_{k}. We call the time between τ_{k} and τ_{k+1} the kth iteration. (Note the distinction between a step of the algorithm and an iteration, which is a sequence of many steps.)

Our proof has two parts. The first (and simple) part is bounding the number of iterations until D_{i} ≤ ϵ. The bound is derived in the following Lemma.

Lemma 12 For m ≥ \frac{1}{β} ln(V_{max}/ϵ) we have D_{m}≤ ϵ.

Proof We have that D_{1} = V_{max} and D_{i} = (1 − β)D_{i−1} . We want to find the m that satisfies D_{m} = V_{max}(1−β)^{m}≤ ϵ. By taking a logarithm over both sides of the inequality we get m ≥ \frac{1}{β} ln(V_{max}/ϵ).

The second (and much more involved) part is to bound the number of steps in an iteration. We use the following quantities introduced in Section 6. Let W_{t+1,τ}(s,a) = (1 − α_{t}^{ω}(s,a))W_{t,τ}(s,a) + α_{t}^{ω}(s,a)w_{t}(s,a), where W_{τ;τ}(s,a) = 0 and

w_{t}(s,a) = R(s,a) + γ max_{b∈U(s′)}Q_{t}(s′,b) − ∑_{j=1}^{|S|} P_{s,j}(a)( R(s,a) + γ max_{b∈U(j)} Q_{t}(j,b)) ,

where s′is the state reached after performing action a at state s. Let

Y_{t+1;τ_{k}}(s,a) = (1 − α_{t}^{ω}(s,a))Y_{t;τ_{k}}(s,a) + α_{t}^{ω}(s,a)γD_{k},

where Y_{τ_{k};τ_{k}}(s,a) = D_{k}. Our first step is to rephrase Lemma 9 for our setting.

Lemma 13 For every state s action a and time τ_{k}, we have

−Y_{t;τ_{k}}(s,a) + W_{t;τ_{k}}(s,a) ≤ Q^{∗}(s,a) − Q_{t}(s,a) ≤ Y_{t;τ_{k}}(s,a) + W_{t;τ_{k}}(s,a)

The above lemma suggests (once again) that in order to bound the error r_{t} one can bound Y_{t;τ_{k}} and W_{t;τ_{k}}separately, and the two bounds imply a bound on r_{t}. We first bound the Y_{t} term, which is deterministic process, and then we bound the term, W_{t;τ}, which is stochastic.

8.1 Synchronous Q-learning using a Polynomial Learning Rate

We start with Q-learning using a polynomial learning rate and show that the duration of iteration k, which starts at time τ_{k} and ends at time τ_{k+1}, is bounded by τ_{k}^{ω}. For synchronous Q-learning with a polynomial learning rate we define τ_{k+1} = τ_{k}+ τ_{k}^{ω}, where τ_{1} will be specified latter.

Lemma 14 Consider synchronous Q-learning with a polynomial learning rate and assume that for any t ≥ τ_{k} we have Y_{t;τ_{k}}(s,a) ≤ D_{k}. Then for any t ≥ τ_{k}+τ_{k}^{ω} = τ_{k+1} we have Y_{t;τ_{k}}(s,a) ≤ D_{k}(γ+ \frac{2}{e}β).

Proof Let Y_{τ_{k};τ_{k}}(s,a) = γD_{k}+ ρ_{τ_{k}}, where ρ_{τ_{k}} = (1 − γ)D_{k}. We can now write

Y_{t+1;τ_{k}}(s,a) = (1 − α_{t}^{ω})Y_{t;τ_{k}}(s,a) + α_{t}^{ω}γD_{k} = γD_{k}+ (1 − α_{t}^{ω})ρ_{t},

where ρ_{t+1} = ρ_{t}(1 − α_{t}^{ω}). We would like to show that after time τ_{k+1} = τ_{k}+ τ_{k}^{ω} for any t ≥ τ_{k+1} we have ρ_{t} ≤ \frac{2}{e}βD_{k}. By definition we can rewrite ρ_{t} as

ρ_{t} = (1 − γ)D_{k} ∏_{l=1}^{t−τ_{k}}(1 − α_{l+τ_{k}}^{ω}) = 2βD_{k} ∏_{l=1}^{t−τ_{k}}(1 − α_{l+τ_{k}}^{ω}) = 2βD_{k} ∏_{l=1}^{t−τ_{k}}(1 − \frac{1}{(l + τ_{k})^{ω}} ),

where the last identity follows from the fact that α_{t}^{ω} = 1/t^{ω}. Since the α_{t}^{ω}’s are monotonically decreasing

ρ_{t} ≤ 2βD_{k}(1 − \frac{1}{τ_{k}^{ω}})^{t−τ_{k}}.

For t ≥ τ_{k}+ τ_{k}^{ω} we have

ρ_{t} ≤ 2βD_{k}(1 − \frac{1}{τ_{k}^{ω}})^{τ_{k}^{ω}} ≤ \frac{2}{e}βD_{k}.

Hence, Y_{t;τ_{k}}(s,a) ≤ (γ + \frac{2}{e}β)D_{k}.

Next we bound the term W_{t;τ_{k}}by (1− \frac{2}{e})βD_{k}. The sum of the bounds for W_{t;τ_{k}}(s,a) and Y_{t;τ_{k}}(s,a) would be (γ + β)D_{k} = (1 − β)D_{k} = D_{k+1}, as desired.

Definition 15 Let W_{t;τ_{k}}(s,a) = (1 − α_{t}^{ω}(s,a))W_{t−1;τ_{k}}(s,a) + α_{t}^{ω}(s,a)w_{t}(s,a) = ∑ _{i=τ_{k}+1}^{t} η_{i}^{k,t}(s,a)w_{i}(s,a) , where η_{i}^{k,t}(s,a) = α_{i+τ_{k}}^{ω} (s,a)∏ _{j=τ_{k}+i+1}^{t} (1−α_{j}^{ω}(s,a)) and let W_{t;τ_{k}}^{l}(s,a) = ∑ _{i=τ_{k}+1}^{τ_{k}+l} η_{i}^{k,t}(s,a)w_{i}(s,a).

Note that in the synchronous model α_{t}^{ω}(s,a) and η_{i}^{k,t}(s,a) are identical for every state action pair. We also note that W_{t;τ_{k}}^{t−τ_{k}+1} (s,a) = W_{t;τ_{k}}(s,a). We have bounded the term Y_{t;τ_{k}}, for t = τ_{k+1}. This bound holds for any t ≥ τ_{k+1}, since the sequence Y_{t;τ_{k}}is monotonically decreasing. In contrast, the term W_{t;τ_{k}}is stochastic. Therefore it is not sufficient to bound W_{τ_{k+1} ;τ_{k}}, but we need to bound W_{t;τ_{k}} for t ≥ τ_{k+1}. However, it is sufficient to consider t ∈ [τ_{k+1},τ_{k+2}]. The following lemma bounds the coefficients in that interval.

Lemma 16 For any t ∈ [τ_{k+1},τ_{k+2}] and i ∈ [τ_{k},t], we have η_{i}^{k,t}= Θ(\frac{1}{τ_{k}^{ω}} ),

Proof Since η_{i}^{k,t}= α_{i+τ_{k}}^{ω} ∏ _{j=τ_{k}+i+1}^{t} (1 − α_{j}^{ω}),we can divide η_{t}^{k,t} into two parts, the first one α_{i+τ_{k}}^{ω} and the second one μ = ∏ _{j=τ_{k}+i+1}^{t} (1 − α_{j}^{ω}). We show that the first one is Θ(\frac{1}{τ_{k}^{ω}}) and the second is constant. Since α_{i+τ_{k}}^{ω} are monotonically decreasing we have for every i ∈ [τ_{k},τ_{k+2}] we have α_{τ_{k}}^{ω} ≤ α_{i}^{ω} ≤ α_{τ_{k+2}}^{ω}, thus \frac{1}{τ_{k}^{ω}} ≤ α_{t}^{ω} ≤ \frac{1}{(τ_{k+1} +τ_{k+1}^{ω})^{ω}} ≤ \frac{1}{(3τ_{k}^{ω}+τ_{k})^{ω}} < \frac{1}{4τ_{k}^{ω}}. Next we bound μ. Clearly μ is bounded from above

by 1. Also μ ≥ ∏ _{j=τ_{k}}^{τ_{k+2}} (1 − α_{j}) ≥ (1 − \frac{1}{τ_{k}^{ω}} )^{3τ_{k}^{ω}} ≥ \frac{1}{e^{3}}. Therefore, we have that for every t ∈ [τ_{k},τ_{k+2}], η_{i}^{k,t}= Θ(\frac{1}{τ_{k}^{ω}} ).

We introduce Azuma’s inequality, which bounds the deviations of a martingale. The use of Azuma’s inequality is mainly needed for the asynchronous case.

Lemma 17 (Azuma 1967) Let X_{0},X_{1},...,X_{n} be a martingale sequence such that for each 1 ≤ k ≤ n,

|X_{k}− X_{k−1}| ≤ c_{k},

where the constant c_{k} may depend on k. Then for all n ≥ 1 and any ϵ > 0

Pr [|X_{n}− X_{0}| > ϵ] ≤ 2e^{−_{\frac{ϵ}{2∑ {n \atop k=1} c^{2}_{k}}}}

Next we show that Azuma’s inequality can be applied to W_{t;τ_{k}}^{l}.

Lemma 18 For any t ∈ [τ_{k+1},τ_{k+2}] and 1 ≤ l ≤ t we have that W_{t;τ_{k}}^{l}(s,a) is a martingale sequence, which satisfies

|W_{t;τ_{k}}^{l}(s,a) − W_{t;τ_{k}}^{l−1} (s,a)| ≤ Θ(\frac{V_{max}}{τ_{k}^{ω}})

Proof We first note that W_{t;τ_{k}}^{l}(s,a) is a martingale sequence, since

E[W_{t;τ_{k}}^{l}(s,a) − W_{t;τ_{k}}^{l−1} (s,a)|F_{τ_{k}+l−1} ]= E[η_{τ_{k}+l}^{k,t} (s,a)w_{τ_{k}+l} (s,a)|F_{τ_{k}+l−1} ]
= η_{τ_{k}+l}^{k,t} E[w_{τ_{k}+l} (s,a)|F_{τ_{k}+l−1} ] = 0.

By Lemma 16 we have that η_{l}^{k,t}(s,a) = Θ(1/τ_{k}^{ω}), thus

|W_{t;τ_{k}}^{l}(s,a) − W_{t;τ_{k}}^{l−1} (s,a)| = η_{τ_{k}+l}^{k,t} (s,a)|w_{τ_{k}+l} (s,a)| ≤ Θ(\frac{V_{max}}{τ_{k}^{ω}}).

The following lemma provides a bound for the stochastic error caused by the term W_{t;τ_{k}}by using Azuma’s inequality.

Lemma 19 Consider synchronous Q-learning with a polynomial learning rate. With probability at least 1 − \frac{δ}{m} we have |W_{t;τ_{k}}| ≤ (1 − \frac{2}{e})βD_{k} for any t ∈ [τ_{k+1},τ_{k+2}], i.e.,

Pr [∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}| ≤ (1 − \frac{2}{e})βD_{k}] ≥ 1 − \frac{δ}{m}

given that τ_{k} = Θ((\frac{V_{max}^{2}ln(V_{max}|S| |A|m/(δβD_{k}))}{β^{2}D_{k}^{2}})^{1/ω}).

Proof By Lemma 18 we can apply Azuma’s inequality to W_{t;τ_{k}}^{t−τ_{k}+1} with c_{i} = Θ(\frac{V_{max}}{τ_{k}^{ω}}) (note that

W_{t;τ_{k}}^{t−τ_{k}+1} = W_{t;τ_{k}}) . Therefore, we derive that

Pr [|W_{t;τ_{k}}(s,a)| ≥ ϵ̃| t ∈ [τ_{k+1},τ_{k+2}]] ≤ 2e^{\frac{−2ϵ̃^{2}}{∑ {t \atop i=τ_{k}} c^{2}_{i}}} ≤ 2e^{−cτ_{k}^{ω} ϵ̃^{2}/V_{max}^{2}},

for some constant c > 0. Set δ̃_{k} = 2e^{−cτ_{k}^{ω} ϵ̃^{2}/V_{max}^{2}}, which holds for τ_{k}^{ω} = Θ(ln(1/δ̃)V_{max}^{2}/ϵ̃^{2}). Using the union bound we have,

Pr [∀t ∈ [τ_{k+1},τ_{k+2}] : W_{t;τ_{k}}(s,a) ≤ ϵ̃]≤ ∑_{t=τ_{k+1}}^{τ_{k+2}} Pr [W_{t;τ_{k}}(s,a) ≤ ϵ̃],

thus taking δ̃_{k} = \frac{δ}{m(τ_{k+2} −τ_{k+1} )|S||A|} assures that with probability at least 1 − \frac{δ}{m} the statement hold at every state-action pair and time t ∈ [τ_{k+1},τ_{k+2}]. As a result we have,

τ_{k} = Θ( (\frac{V_{max}^{2}ln(|S| |A| mτ_{k}^{ω}/δ)}{ϵ̃^{2}} )^{1/ω}) = Θ( (\frac{V_{max}^{2}ln(|S| |A| mV_{max}/δϵ̃)}{ϵ̃^{2}} )^{1/ω})

Setting ϵ̃= (1 − 2/e)βD_{k} gives the desire bound.

We have bounded for each iteration the time needed to achieve the desired precision level with probability 1 − \frac{δ}{m}. The following lemma provides a bound for the error in all the iterations.

Lemma 20 Consider synchronous Q-learning using a polynomial learning rate. With probability at least 1−δ, for every iteration k ∈ [1,m] and time t ∈ [τ_{k+1},τ_{k+2}] we have W_{t;τ_{k}}≤ (1− \frac{2}{e})βD_{k}, i.e.,

Pr [∀k ∈ [1,m], ∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}| ≤ (1 − \frac{2}{e})βD_{k}]≥ 1 − δ,

given that τ_{0} = Θ((\frac{V_{max}^{2}ln(V_{max}|S| |A|/(δβϵ))}{β^{2}ϵ^{2}})^{1/ω}).

Proof From Lemma 19 we know that

Pr [∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}| ≥ (1 − \frac{2}{e})βD_{k}]

= Pr [∀s,a ∀t ∈ [τ_{k+1},τ_{k+2}] : ∑_{i=τ_{k}}^{t} w_{i}(s,a)η_{i}^{k,t}≥ ϵ̃] ≤ \frac{δ}{m}

Using the union bound we have,

Pr [∀s,a ∀k ≤ m,∀t ∈ [τ_{k+1},τ_{k+2}] ∑_{i=τ_{k}}^{t} w_{i}(s,a)η_{i}^{k,t}≥ ϵ̃]

≤ ∑_{k=1}^{m} Pr [∀s,a ∀t ∈ [τ_{k+1},τ_{k+2}] ∑_{i=τ_{k}}^{t} w_{i}(s,a)η_{i}^{k,t}≥ ϵ̃] ≤ δ

where ϵ̃= (1 − \frac{2}{e})βD_{k}.

We have bounded both the size of each iteration, as a function of its starting time, and the number of the iterations needed. The following lemma solves the recurrence τ_{k+1} = τ_{k}+ τ_{k}^{ω} and bounds the total time required (which is a special case of Lemma 32).

Lemma 21 Let

a_{k+1} = a_{k}+ a_{k}^{ω} = a_{0}+ ∑_{i=0}^{k} a_{i}^{ω}.

For any constant ω ∈ (0,1), a_{k} = O((a_{0}^{1−ω} + k)^{\frac{1}{1−ω}} ) = O(a_{o}+ k^{\frac{1}{1−ω}} )

The proof of Theorem 2 follows from Lemma 21, Lemma 20, Lemma 12 and Lemma 14.

8.2 Synchronous Q-learning using a Linear Learning Rate

In this subsection, we derive results for Q-learning with a linear learning rate. The proof is very similar in spirit to the proof of Theorem 2 and we give here analogous lemmas to the ones in Subsection 8.1. First, the number of iterations required for synchronous Q-learning with a linear learning rate is the same as that for a polynomial learning rate. Therefore, we only need to analyze the number of steps in an iteration.

Lemma 22 Consider synchronous Q-learning with a linear learning rate and assume that for any t ≥ τ_{k} we have Y_{t;τ_{k}}(s,a) ≤ D_{k}. Then for any t ≥ (2+ψ)τ_{k}= τ_{k+1} we have Y_{t;τ_{k}}(s,a) ≤ D_{k}(γ+ \frac{2}{2+ψ} β)

Proof Let Y_{τ_{k};τ_{k}}(s,a) = γD_{k}+ ρ_{τ_{k}}, where ρ_{τ_{k}} = (1 − γ)D_{k}. We can now write

Y_{t+1;τ_{k}}(s,a) = (1 − α_{t})Y_{t;τ_{k}}(s,a) + α_{t}γD_{k} = γD_{k}+ (1 − α_{t})ρ_{t},

where ρ_{t+1} = ρ_{t}(1 − α_{t}). We would like show that after time (2 + ψ)τ_{k} = τ_{k+1} for any t ≥ τ_{k+1} we have ρ_{t} ≤ βD_{k}. By definition we can rewrite ρ_{t} as,

ρ_{t} = (1 − γ)D_{k} ∏_{l=1}^{t−τ_{k}}(1 − α_{l+τ_{k}}) = 2βD_{k} ∏_{l=1}^{t−τ_{k}}(1 − α_{l+τ_{k}}) = 2βD_{k} ∏_{l=1}^{t−τ_{k}}(1 − \frac{1}{l + τ_{k}} ),

where the last identity follows from the fact that α_{t} = 1/t. Simplifying the expression, and setting t = (2 + ψ)τ_{k}, we have

ρ_{t} ≤ 2D_{k}β\frac{τ_{k}}{t} = \frac{2D_{k}β}{2 + ψ}

Hence, Y_{t;τ_{k}}(s,a) ≤ (γ + \frac{2}{2+ψ} β)D_{k}.

The following lemma enables the use of Azuma’s inequality. Lemma 23 For any t ≥ τ_{k} and 1 ≤ l ≤ t we have that W_{t;τ_{k}}^{l}(s,a) is a martingale sequence, which satisfies

|W_{t;τ_{k}}^{l}(s,a) − W_{t;τ_{k}}^{l−1} (s,a)| ≤ \frac{V_{max}}{t}

Proof We first note that W_{t;τ_{k}}^{l}(s,a) is a martingale sequence, since

E[W_{t;τ_{k}}^{l}(s,a) − W_{t;τ_{k}}^{l−1} (s,a)|F_{τ_{k}+l−1} ]= E[η_{τ_{k}+l}^{k,t} (s,a)w_{τ_{k}+l} (s,a)|F_{τ_{k}+l−1} ]
= η_{τ_{k}+l}^{k,t} E[w_{τ_{k}+l} (s,a)|F_{τ_{k}+l−1} ] = 0.

For linear learning rate we have that η_{l+τ_{k}}^{k,t} (s,a) = 1/t, thus

|W_{t;τ_{k}}^{l}(s,a) − W_{t;τ_{k}}^{l−1} (s,a)| = \frac{w_{τ_{k}+l} (s,a)}{t} ≤ \frac{V_{max}}{t}.

The following Lemma provides a bound for the stochastic term W_{t;τ_{k}}. Lemma 24 Consider synchronous Q-learning with a linear learning rate. With probability at least 1 − \frac{δ}{m}, we have |W_{t;τ_{k}}| ≤ \frac{ψ}{2+ψ} βD_{k} for any t ∈ [τ_{k+1},τ_{k+2}] and any positive constant ψ, i.e.

Pr [∀t ∈ [τ_{k+1},τ_{k+2}] : W_{t;τ_{k}}≤ \frac{ψ}{2 + ψ} βD_{k}]≥ 1 − \frac{δ}{m}

given that τ_{k} = Θ(\frac{V_{max}^{2}ln(V_{max}|S| |A|m/(ψδβD_{k}))}{ψ^{2}β^{2}D_{k}^{2}}) Proof By Lemma 23 for any t ≥ τ_{k+1} we can apply Azuma’s inequality to W_{t;τ_{k}}^{t−τ_{k}+1} with c_{i} = \frac{V_{max}}{i+τ_{k}} (note that W_{t;τ_{k}}^{t−τ_{k}+1} = W_{t;τ_{k}}). Therefore, we derive that

Pr[|W_{t;τ_{k}}| ≥ ϵ̃| t ≥ τ_{k+1}] ≤ 2e^{\frac{−2ϵ̃^{2}}{∑ {t \atop i=τ_{k}} c^{2}_{i}}} = 2e^{−c \frac{t^{2}ϵ̃^{2}}{(t−τ_{k})V{2 \atop max}}} ≤ 2e^{−c \frac{tϵ̃^{2}}{V{2 \atop max}}}

for some positive constant c. Using the union bound we get

Pr [∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}| ≥ ϵ̃] ≤ Pr [∀t ≥ (2 + ψ)τ_{k}: |W_{t;τ_{k}}| ≥ ϵ̃]
≤ ∑_{t=(2+ψ)τ_{k}}^{∞} Pr [|W_{t;τ_{k}}| ≥ ϵ̃]
≤ ∑_{t=(2+ψ)τ_{k}}^{∞} 2e^{−c \frac{tϵ̃^{2}}{V{2 \atop max}}} = 2e^{−c \frac{((2+ψ)τ_{k})ϵ̃^{2}}{V{2 \atop max}}} ∑_{t=0}^{∞} e^{−_{\frac{tϵ̃}{V{2 \atop max}}}}
= \frac{2e^{−c \frac{(2+ψ)τ_{k}ϵ̃^{2}}{V{2 \atop max}}}}{1 − e^{\frac{−ϵ̃^{2}}{V{2 \atop max}}}} = Θ(\frac{e^{− \frac{c′τ_{k}ϵ̃^{2}}{V{2 \atop max}}} V_{max}^{2}}{ϵ̃^{2}}),

where the last equality is due to Taylor expansion and c′ is some positive constant. By setting

\frac{δ}{m |S| |A|}= Θ(^{\frac{e^{− \frac{c′τ_{k}ϵ̃^{2}}{V{2 \atop max}}} V_{max}^{2}}{ϵ̃^{2}}}), which holds for τ_{k} = Θ(\frac{V_{max}^{2}ln(V_{max}|S| |A|m/(δϵ̃))}{ϵ̃^{2}}), and ϵ̃= \frac{ψ}{2+ψ} βD_{k} assures us that for every t ≥ τ_{k+1} (and as a result for any t ∈ [τ_{k+1},τ_{k+2}]) with probability at least 1 − \frac{δ}{m} the statement holds at every state-action pair.

We have bounded for each iteration the time needed to achieve the desired precision level with probability 1 − \frac{δ}{m}. The following lemma provides a bound for the error in all the iterations.

Lemma 25 Consider synchronous Q-learning using a linear learning rate. With probability 1 − δ, for every iteration k ∈ [1,m], time t ∈ [τ_{k+1},τ_{k+2}] and any constant ψ > 0 we have |W_{t;τ_{k}}| ≤ \frac{ψβD_{k}}{2+ψ} ), i.e.,

Pr [∀k ∈ [1,m], ∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}| ≤ \frac{ψβD_{k}}{2 + ψ} ]≥ 1 − δ,

given that τ_{0} = Θ(\frac{V_{max}^{2}ln(V_{max}|S| |A|m/(ψδβϵ))}{ψ^{2}β^{2}ϵ^{2}}).

Proof From Lemma 19 we know that

Pr [∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}| ≥ \frac{ψβD_{k}}{2 + ψ} ]≤ \frac{δ}{m}

Using the union bound we have that,

Pr [∀k ≤ m,∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}| ≥ \frac{ψβD_{k}}{2 + ψ} ]

≤ ∑_{k=1}^{m} Pr [∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}| ≥ \frac{ψβD_{k}}{2 + ψ} ]≤ δ

The proof of Theorem 5 follows from Lemmas 25 and 22, 12 and the fact that a_{k+1} = (2 + ψ)a_{k} = (2 + ψ)^{k}a_{1}.

9. Asynchronous Q-learning

The major difference between synchronous and asynchronous Q-learning is that asynchronous Qlearning updates only one state action pair at each time while synchronous Q-learning updates all state-action pairs at each time unit. This causes two difficulties: the first is that different updates use different values of the Q function in their update. This problem is fairly easy to handle given the machinery introduced. The second, and more basic problem is that each state-action pair should occur enough times for the update to progress. To ensure this, we introduce the notion of covering time, denoted by L. We first extend the analysis of synchronous Q-learning to asynchronous Qlearning, in which each run always has covering time L, which implies that from any start state, in L steps all state-action pairs are performed. Later we relax the requirement such that the condition holds only with probability 1/2, and show that with high probability we have a covering time of LlogT for a run of length T. Note that our notion of covering time does not assume a stationary distribution of the exploration strategy; it may be the case that at some periods of time certain stateaction pairs are more frequent while in other periods different state-action pairs are more frequent. In fact, we do not even assume that the sequence of state-action pairs is generated by a strategy—it can be an arbitrary sequence of state-action pairs, along with their reward and next state.

Definition 26 Let n(s,a,t_{1},t_{2}) be the number of times that the state action pair (s,a) was performed in the time interval [t_{1},t_{2}].

In this section, we use the same notations as in Section 8 for D_{k}, τ_{k}, Y_{t;τ_{k}}and W_{t;τ_{k}}, with a different set of values for τ_{k}. We first give the results for asynchronous Q-learning using polynomial learning rate (Subsection 9.1); we give a similar proof for linear learning rates in Subsection 9.2.

9.1 Asynchronous Q-learning using a Polynomial Learning Rate

Our main goal is to show that the size of the kth iteration is Lτ_{k}^{ω}. The covering time property guarantees that in Lτ_{k}^{ω} steps each pair of state action is performed at least τ_{k}^{ω} times. For this reason we define for asynchronous Q-learning with polynomial learning rate the sequence τ_{k+1} = τ_{k}+Lτ_{k}^{ω}, where τ_{1} will be specified later. As in Subsection 8.1 we first bound the value of Y_{t;τ_{k}}

Lemma 27 Consider asynchronous Q-learning with a polynomial learning rate and assume that for any t ≥ τ_{k} we have Y_{t;τ_{k}}(s,a) ≤ D_{k}. Then for any t ≥ τ_{k}+Lτ_{k}^{ω} = τ_{k+1} we have Y_{t;τ_{k}}(s,a) ≤ D(γ+ \frac{2}{e}β)

Proof For each state-action pair (s,a) we are assured that n(s,a,τ_{k},τ_{k+1}) ≥ τ_{k}^{ω} , since the covering time is L and the underlying policy has made Lτ_{k}^{ω} steps. Using the fact that the Y_{t;τ_{k}}(s,a) are monotonically decreasing and deterministic, we can apply the same argument as in the proof of Lemma 14.

The next Lemma bounds the influence of each sample w_{t}(s,a) on W_{t;τ_{k}}(s,a).

Lemma 28 Let w̃_{i+τ_{k}}^{t}(s,a) = η_{i}^{k,t}(s,a)w_{i+τ_{k}} (s,a) then for any t ∈ [τ_{k+1},τ_{k+2}] the random variable w̃_{i+τ_{k}}^{t}(s,a) has zero mean and bounded by (L/τ_{k})^{ω}V_{max}.

Proof Note that by definition w_{τ_{k}+i} (s,a) has zero mean and is bounded by V_{max}for any history and state-action pair. In a time interval of length τ, by definition of the covering time, each state-action pair is performed at least τ/L times; therefore, η_{i}^{k,t}(s,a) ≤ (L/τ_{k})^{ω}. Looking at the expectation of w̃_{i+τ_{k}}(s,a) we observe that

E[w̃_{i+τ_{k}}^{t}(s,a)] = E[η_{i}^{k,t}(s,a)w_{i+τ_{k}} (s,a)] = η_{i}^{k,t}(s,a)E[w_{i+τ_{k}} (s,a)] = 0

Next we prove that it is bounded as well:

|w̃_{i+τ_{k}}^{t}(s,a)| = |η_{i}^{k,t}(s,a)w_{i+τ_{k}} (s,a)|
≤ |η_{i}^{k,t}(s,a)|V_{max}
≤ (L/τ_{k})^{ω}V_{max}

Next we define W_{t;τ_{k}}^{l}(s,a) = ∑ _{i=1}^{l} w̃_{i+τ_{k}}^{t}(s,a) and prove that it is martingale sequence with bounded differences.

Lemma 29 For any t ∈ [τ_{k+1},τ_{k+2}] and 1 ≤ l ≤ t we have that W_{t;τ_{k}}^{l}(s,a) is a martingale sequence, which satisfies

|W_{t;τ_{k}}^{l}(s,a) − W_{t;τ_{k}}^{l−1} (s,a)| ≤ (L/τ_{k})^{ω}V_{max}

Proof We first note that W_{t;τ_{k}}^{l}(s,a) is a martingale sequence, since

E[W_{t;τ_{k}}^{l}(s,a) − W_{t;τ_{k}}^{l−1} (s,a)|F_{τ_{k}+l−1} ]= E[w̃_{l+τ_{k}}^{t}(s,a)|F_{τ_{k}+l−1} ] = 0.

By Lemma 28 we have that w̃_{l+τ_{k}}^{t}(s,a) is bounded by (L/τ_{k})^{ω}V_{max}, thus

|W_{t;τ_{k}}^{l}(s,a) − W_{t;τ_{k}}^{l−1} (s,a)| = w̃_{l+τ_{k}}^{t}(s,a) ≤ (L/τ_{k})^{ω}V_{max}.

The following Lemma bounds the value of the term W_{t;τ_{k}}.

Lemma 30 Consider asynchronous Q-learning with a polynomial learning rate. With probability at least 1 − \frac{δ}{m} we have for every state-action pair |W_{t;τ_{k}}(s,a)| ≤ (1 − \frac{2}{e})βD_{k} for any t ∈ [τ_{k+1},τ_{k+2}], i.e.

Pr [∀s,a ∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}(s,a)| ≤ (1 − \frac{2}{e})βD_{k}] ≥ 1 − \frac{δ}{m}

given that τ_{k} = Θ((\frac{L^{1+3ω} V_{max}^{2}ln(V_{max}|S| |A|m/(δβD_{k}))}{β^{2}D_{k}^{2}} )^{1/ω}).

Proof For each state-action pair we look on W_{t;τ_{k}}^{l}(s,a) and note that W_{t;τ_{k}}(s,a) = W_{t;τ_{k}}^{t−τ_{k}+1} (s,a). Let ℓ = n(s,a,τ_{k},t), then for any t ∈ [τ_{k+1},τ_{k+2}] we have that ℓ ≤ τ_{k+2} − τ_{k} ≤ Θ(L^{1+ω} τ_{k}^{ω}). By Lemma 29 we can apply Azuma’s inequality to W_{t;τ_{k}}^{t−τ_{k}+1} (s,a) with c_{i} = (L/τ_{k})^{ω}V_{max}. Therefore, we derive that

Pr[|W_{t;τ_{k}}(s,a)| ≥ ϵ̃| t ∈ [τ_{k+1},τ_{k+2}]]≤ 2e^{\frac{−ϵ̃^{2}}{2∑ {t \atop i=τ_{k}+1,i∈T^{s,a}} c^{2}_{i}}} ≤ 2e^{−c \frac{ϵ̃^{2}τ{2ω \atop k}}{ℓV{2 \atop max}L^{2ω}}}
≤ 2e^{−c \frac{ϵ̃^{2}τ^{ω}_{k}}{L^{1+3ω} V{2 \atop max}}},

for some constant c > 0. We can set δ̃_{k}= 2e^{−cτ_{k}^{ω} ϵ̃^{2}/(L^{1+3ω} V_{max}^{2})}, which holds for τ_{k}^{ω} = Θ(ln(1/δ̃_{k})L^{1+3ω} V_{max}^{2}/ϵ̃^{2}). Using the union bound we have

Pr [∀t ∈ [τ_{k+1},τ_{k+2}] : W_{t;τ_{k}}(s,a) ≤ ϵ̃]≤ ∑_{t=τ_{k+1}}^{τ_{k+2}} Pr [W_{t;τ_{k}}(s,a) ≤ ϵ̃],

thus taking δ̃_{k} = \frac{δ}{m(τ_{k+2} −τ_{k+1} )|S||A|} assures a certainty level of 1 − \frac{δ}{m} for each state-action pair. As a result we have

τ_{k}^{ω} = Θ(\frac{L^{1+3ω} V_{max}^{2}ln(|S| |A| mτ_{k}^{ω}/δ)}{ϵ̃^{2}} ) = Θ(\frac{L^{1+3ω} V_{max}^{2}ln(|S| |A| mV_{max}/(δϵ̃))}{ϵ̃^{2}} )

Setting ϵ̃= (1 − 2/e)βD_{k} give the desired bound.

We have bounded for each iteration the time needed to achieve the desired precision level with probability 1 − \frac{δ}{m}. The following lemma provides a bound for the error in all the iterations.

Lemma 31 Consider asynchronous Q-learning using a polynomial learning rate. With probability 1 − δ, for every iteration k ∈ [1,m] and time t ∈ [τ_{k+1},τ_{k+2}] we have |W_{t;τ_{k}}(s,a)| ≤ (1 − \frac{2}{e})βD_{k}, i.e.,

Pr [∀k ∈ [1,m], ∀t ∈ [τ_{k+1},τ_{k+2}], ∀s,a: |W_{t;τ_{k}}(s,a)| ≤ (1 − \frac{2}{e})βD_{k}]≥ 1 − δ,

given that τ_{0} = Θ((\frac{L^{1+3ω} V_{max}^{2}ln(V_{max}|S| |A|m/(δβϵ))}{β^{2}ϵ^{2}} )^{1/ω}). Proof From Lemma 30 we know that

Pr [∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}| ≥ (1 − \frac{2}{e})βD_{k}] ≤ \frac{δ}{m}

Using the union bound we have that

Pr [∀k ≤ m,∀t ∈ [τ_{k+1},τ_{k+2}] |W_{t;τ_{k}}| ≥ ϵ̃] ≤ ∑_{k=1}^{m} Pr [∀t ∈ [τ_{k+1},τ_{k+2}] |W_{t;τ_{k}}| ≥ ϵ̃]≤ δ,

where ϵ̃= (1 − \frac{2}{e})βD_{k}

The following lemma solves the recurrence ∑ _{i=0}^{m−1} Lτ_{i}^{ω} + τ_{0} and derives the time complexity. Lemma 32 Let

a_{k+1} = a_{k}+ La_{k}^{ω} = a_{0}+ ∑_{i=0}^{k} La_{i}^{ω}

Then for any constant ω ∈ (0,1), a_{k} = O((a_{0}^{1−ω} + Lk)^{\frac{1}{1−ω}} ) = O(a_{0}+ (LK)^{\frac{1}{1−ω}} )). Proof We define the following series

b_{k+1} = ∑_{i=0}^{k} Lb_{i}^{ω} + b_{0}

with an initial condition

b_{0} = L^{\frac{1}{1−ω}} .

We show by induction that b_{k} ≤ (L(k + 1))^{\frac{1}{1−ω}} for k ≥ 1. For k = 0

b_{0} = L^{\frac{1}{1−ω}} (0 + 1)^{\frac{1}{1−ω}} ≤ L^{\frac{1}{1−ω}}

We assume that the induction hypothesis holds for k − 1 and prove it for k,

b_{k} = b_{k−1} + Lb_{k−1}^{ω} ≤ (Lk)^{\frac{1}{1−ω}} + L(Lk)^{\frac{ω}{1−ω}} ≤ L^{\frac{1}{1−ω}} k^{\frac{ω}{1−ω}} (k + 1) ≤ (L(k + 1))^{\frac{1}{1−ω}}

and the claim is proved.

Now we lower bound b_{k} by (L(k + 1)/2)^{1/(1−ω)} . For k = 0

b_{0} = L^{\frac{1}{1−ω}} ≥ (\frac{L}{2})^{\frac{1}{1−ω}}

Assume that the induction hypothesis holds for k − 1 and prove for k,

b_{k} = b_{k−1} + Lb_{k−1}^{ω} = (Lk/2)^{\frac{1}{1−ω}} + L(Lk/2)^{\frac{ω}{1−ω}} = L^{\frac{1}{1−ω}} ((k/2)^{\frac{1}{1−ω}} + (k/2)^{\frac{ω}{1−ω}} )
≥ L^{\frac{1}{1−ω}} ((k + 1)/2)^{\frac{1}{1−ω}} .

For a_{0} > L^{\frac{1}{1−ω}} we can view the series as starting at b_{k}= a_{0}. From the lower bound we know that the start point has moved Θ(a_{0}^{1−ω} /L). Therefore we have a total complexity of O((a_{0}^{1−ω} +Lk)^{\frac{1}{1−ω}} ) = O(a_{0}+ (LK)^{\frac{1}{1−ω}} )).

The proof of Theorem 4 follows from Lemmas 27, 31,12 and 32. In the following lemma we relax the condition of the covering time.

Lemma 33 Assume that from any start state with probability 1/2 in L steps we perform all state action pairs. Then with probability 1 − δ, from any start state we perform all state action pairs in Llog_{2}(1/δ) steps, for a run of length [Llog_{2}(1/δ)].

Proof The proof follows from the fact that after k intervals of length L (where k is a natural number), the probability of not visiting all state action pairs is 2^{−k}. Since we have k = [log_{2}(1/δ)] we get that the probability of failing is δ.

Corollary 34 Assume that from any start state with probability 1/2 in L steps we perform all state action pairs. Then with probability 1 − δ, from any start state we perform all state action pairs in Llog(T /δ) steps, for a run of length T.

9.2 Asynchronous Q-learning using a Linear Learning Rate

In this section we consider asynchronous Q-learning with a linear learning rate. Our main goal is to show that the size of the kth iteration is L(1 + ψ)τ_{k}, for any constant ψ > 0. The covering time property guarantees that in (1+ψ)Lτ_{k} steps each pair of state action is performed at least (1+ψ)τ_{k} times. The sequence of times in this case is τ_{k+1} = τ_{k}+ (1 + ψ)Lτ_{k}, where the τ_{0} will be defined latter. We first bound Y_{t;τ_{k}}and then bound the stochastic term W_{t;τ_{k}}.

Lemma 35 Consider asynchronous Q-learning with a polynomial learning rate and assume that for any t ≥ τ_{k} we have Y_{t;τ_{k}}(s,a) ≤ D_{k}. Then for any t ≥ τ_{k}+(1+ψ)Lτ_{k}= τ_{k+1} we have Y_{t;τ_{k}}(s,a) ≤ (γ + \frac{2}{2+ψ} β)D_{k}

Proof For each state-action pair (s,a) we are assured that n(s,a,τ_{k},τ_{k+1}) ≥ (1 + ψ)τ_{k} , since in an interval of (1+ψ)Lτ_{k} steps each state-action pair is visited at least (1+ψ)τ_{k} times by the definition of the covering time. Using the fact that the Y_{t;τ_{k}}(s,a) are monotonically decreasing and deterministic (thus independent), we can apply the same argument as in the proof of Lemma 22.

The following Lemma enables the use of Azuma’s inequality.

Lemma 36 For any t ≥ τ_{k} and 1 ≤ l ≤ t we have that W_{t;τ_{k}}^{l}(s,a) is a martingale sequence, which satisfies

|W_{t;τ_{k}}^{l}(s,a) − W_{t;τ_{k}}^{l−1} (s,a)| ≤ \frac{V_{max}}{n(s,a,0,t)}

Proof We first note that W_{t;τ_{k}}^{l}(s,a) is a martingale sequence, since

E[W_{t;τ_{k}}^{l}(s,a) − W_{t;τ_{k}}^{l−1} (s,a)|F_{τ_{k}+l−1} ]= E[η_{τ_{k}+l}^{k,t} (s,a)w_{τ_{k}+l} (s,a)|F_{τ_{k}+l−1} ]
= η_{τ_{k}+l}^{k,t} E[w_{τ_{k}+l} (s,a)|F_{τ_{k}+l−1} ] = 0.

For a linear learning rate we have that η_{τ_{k}+l}^{k,t} (s,a) = 1/n(s,a,0,t), thus

|W_{t;τ_{k}}^{l}(s,a) − W_{t;τ_{k}}^{l−1} (s,a)| = η_{τ_{k}+l}^{k,t} (s,a)|w_{τ_{k}+l} (s,a)| ≤ \frac{V_{max}}{n(s,a,0,t)}.

The following lemma bounds the value of the term W_{t;τ_{k}}.

Lemma 37 Consider asynchronous Q-learning with a linear learning rate. With probability at least 1 − \frac{δ}{m} we have for every state-action pair |W_{t;τ_{k}}(s,a)| ≤ \frac{ψ}{2+ψ} βD_{k} for any t ≥ τ_{k+1} and any positive constant ψ, i.e.

Pr [∀t ∈ [τ_{k+1},τ_{k+1}] : W_{t;τ_{k}}(s,a) ≤ \frac{ψ}{2 + ψ} βD_{k}]≥ 1 − \frac{δ}{m}

given that τ_{k} ≥ Θ((\frac{V_{max}^{2}ln(V_{max}|S| |A|m/(δβD_{k}ψ))}{ψ^{2}β^{2}D_{k}^{2}})).

Proof By Lemma 36 we can apply Azuma’s inequality on W_{t;τ_{k}}^{t−τ_{k}+1} (We note that W_{t;τ_{k}}^{t−τ_{k}+1} = W_{t;τ_{k}}) with c_{i} = Θ(\frac{V_{max}}{n(s,a,0,t}) for any t ≥ τ_{k+1}. Therefore, we derive that

Pr[|W_{t;τ_{k}}| ≥ ϵ̃] ≤ 2e^{\frac{−2ϵ̃^{2}}{∑ {t \atop i=τ_{k},i∈T^{s,a}} c^{2}_{i}}} ≤ 2e^{−c \frac{n(s,a,τ_{k},t)ϵ̃^{2}}{V{2 \atop max}}} ,

for some positive constant c. Let us define the following variable

ζ_{t}(s,a) = \{ \begin{matrix}1, α_{t}(s,a) ≠ 0 \\ 0, otherwise \end{matrix}

Using the union bound and the fact in an interval of length (1 + ψ)Lτ_{k} each state-action pair is visited at least (1 + ψ)τ_{k} times, we get

Pr [∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}(s,a)| ≥ ϵ̃] ≤ Pr [∀t ≥ ((1 + ψ)L + 1)τ_{k}: |W_{t;τ_{k}}(s,a)| ≥ ϵ̃]
≤ ∑_{t=((1+ψ)L+1)τ_{k}}^{∞} Pr [|W_{t;τ_{k}}(s,a)| ≥ ϵ̃]

≤ ∑_{t=((1+ψ)L+1)τ_{k}}^{∞} ζ_{t}(s,a)2e^{−c \frac{n(s,a,0,t)ϵ̃^{2}}{V{2 \atop max}}}

≤ 2e^{−c \frac{((1+ψ)τ_{k})ϵ̃^{2}}{V{2 \atop max}}} ∑_{t=0}^{∞} e^{− \frac{tϵ̃^{2}}{2V{2 \atop max}}}

= \frac{2e^{−c \frac{(1+ψ)τ_{k}ϵ̃^{2}}{V{2 \atop max}}}}{1 − e^{\frac{−ϵ̃^{2}}{V{2 \atop max}}}} = Θ(\frac{e^{− \frac{c′τ_{k}ϵ̃^{2}}{V{2 \atop max}}} V_{max}^{2}}{ϵ̃^{2}}),

for some positive constant c′. Setting \frac{δ}{m |S| |A|}= Θ(^{\frac{e^{− \frac{c′τ_{k}ϵ̃^{2}}{V{2 \atop max}}} V_{max}^{2}}{ϵ̃^{2}}}), which hold for τ_{k}= Θ(\frac{V_{max}^{2}ln(V_{max}|S| |A|m/(δϵ̃))}{ϵ̃^{2}}), and ϵ̃= \frac{ψ}{2+ψ} βD_{k} assures us that for every t ≥ τ_{k+1} (and as a result for any t ∈ [τ_{k+1},τ_{k+2}]) with probability at least 1 − \frac{δ}{m} the statement holds at every state-action pair.

We have bounded for each iteration the time needed to achieve the desired precision level with probability 1 − \frac{δ}{m}. The following lemma provides a bound for the error in all the iterations.

Lemma 38 Consider synchronous Q-learning using a linear learning rate. With probability 1 − δ, for every iteration k ∈ [1,m], time t ∈ [τ_{k+1},τ_{k+2}] and any constant ψ > 0 we have |W_{t;τ_{k}}| ≤ \frac{ψβD_{k}}{2+ψ} , i.e.,

Pr [∀k ∈ [1,m], ∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}| ≤ \frac{ψβD_{k}}{2 + ψ} ]≥ 1 − δ,

given that τ_{0} = Θ(\frac{V_{max}^{2}ln(V_{max}|S| |A|m/(δβϵψ))}{ψ^{2}β^{2}ϵ^{2}}).

Proof From Lemma 37 we know that

Pr [∀t ∈ [τ_{k+1},τ_{k+2}] : |W_{t;τ_{k}}| ≥ \frac{ψβD_{k}}{2 + ψ} ]≤ \frac{δ}{m}

Using the union bound we have that,

Pr [∀k ≤ m,∀t ∈ [τ_{k+1},τ_{k+2}] |W_{t;τ_{k}}| ≥ \frac{ψβD_{k}}{2 + ψ} ]

≤ ∑_{k=1}^{m} Pr [∀t ∈ [τ_{k+1},τ_{k+2}] |W_{t;τ_{k}}| ≥ \frac{ψβD_{k}}{2 + ψ} ]≤ δ

Theorem 5 follows from Lemmas 35, 38, 12 and the fact that a_{k+1} = a_{k}+(1+ψ)La_{k} = a_{0}((1+ ψ)L + 1)^{k}.

10. Lower Bound for Q-learning using a Linear Learning Rate

In this section we show a lower bound for Q-learning with a linear learning rate, which is O((\frac{1}{ϵ})^{\frac{1}{1−γ}} ). We consider the following MDP, denoted M_{0}, that has a single state s, a single action a, and a deterministic reward R_{M_{0}}(s,a) = 0. Since there is only one action in the MDP we denote Q_{t}(s,a) as Q_{t}(s). We initialize Q_{0}(s) = 1 and observe the time until Q_{t}(s) ≤ ϵ.

Lemma 39 Consider running synchronous Q-learning with linear learning rate on MDP M_{0}, when initializing Q_{0}(s) = 1. Then there is a time t = c(\frac{1}{ϵ})^{\frac{1}{1−γ}} for some constant c > 0, such that Q_{t} ≥ ϵ.

Proof First we prove by induction on t that

Q_{t}(s) = ∏_{i=1}^{t−1} \frac{i + γ}{i + 1} .

For t = 1 we have Q_{1}(s) = (1−1/2)Q_{0}(s)+(1/2)γQ_{0}(s) = (1+γ)/2. Assume the hypothesis holds for t − 1 and prove it for t. By definition,

Q_{t}(s) = (1 − \frac{1}{t})Q_{t−1}(s) + \frac{1}{t}γQ_{t−1}(s) = \frac{t − 1 + γ}{t} Q_{t−1}(s).

In order to help us estimate this quantity we use the Γ function. Let

Γ(x + 1,k) = \frac{1 · 2··· k}{(x + 1) · (x + 2)··· · (x + k)}k^{x}

The limit of Γ(1 + x,k), as k goes to infinity, is constant for any x. We can rewrite Q_{t}(s) as

Q_{t}(s) = \frac{1}{Γ(γ + 1,t)} \frac{t^{γ}}{t + 1} = Θ(t^{γ−1})

Therefore, there is a time t = c(\frac{1}{ϵ})^{\frac{1}{1−γ}} , for some constant c > 0, such that Q_{t}(s) ≥ ϵ.

Acknowledgments

This research was supported in part by a grant from the Israel Science Foundation. Eyal Even-Dar was partially supported by the Deutsch Institute.

References

K. Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, 68:357–367, 1967.

F. Beleznay, T. Grobler, and C. Szepesvari. Comparing value-function estimation algorithms in undiscounted problems. Technical Report TR-99-02, Mindmaker Ltd, 1999.

Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, Belmont, MA, 1996.

V.S. Borkar and S.P. Meyn. The O.D.E method for convergence of stochstic approximation and reinforcement learning. Siam J. Control, 38 (2):447–69, 2000.

Tommi Jaakkola, Michael I. Jordan, and Satinder P. Singh. On the convergence of stochastic iterative dynamic programming algorithms. Neural Computation, 6, 1994.

Michael Kearns and Satinder P. Singh. Finite-sample convergence rates for Q-learning and indirect algorithms. In M.J. Kearns, S.A. Solla, and D.A. Cohn, editors, Advances in Neural Information Processing Systems 11, pages 996–1002, 1999.

Michael L. Littman and Gaba Szepesvári. A generalized reinforcement-learning model: Convergence and applications. In L. Saitta, editor, Proceedings of the 13th International Conference on Machine Learning (ICML-96), pages 310–318, Bari, Italy, 1996. Morgan Kaufmann. URL citeseer.nj.nec.com/littman96generalized.html.

Martin L. Puterman. Markov Decision Processes—Discrete Stochastic Dynamic Programming. John Wiley and Sons, Inc., New York, NY, 1994.

R. Sutton and A. Barto. Reinforcement Learning. MIT Press., Cambridge, MA., 1998.

C. Szepesvari. The asymptotic convergence-rate of Q-learning. In M.I. Jordan, M.J. Kearns, and S.A. Solla, editors, Advances in Neural Information Processing Systems 10, pages 1064–1070, 1998.

J. Tsitsiklis. Asynchronous stochastic approximation and Q-learning, 1994.

C. Watkins and P. Dyan. Q-learning. Machine Learning, 8(3/4):279–292, 1992.

C. J. C. H. Watkins. Learning from Delayed Rewards. PhD thesis, Cambridge, England, 1989.