\documentclass[twoside,11pt]{article}
\usepackage{jmlr2e, epsfig}

%
% this command enables to remove a whole part of the text
% from the printout
% to use it just enter
% \remove{
% before the text to be excluded and
% }
% after the text
\newcommand{\remove}[1]{}
\newcommand{\colt}[1]{}

%
% The following macros are used to generate nice code for programs.
% See example on how to use it below
%

%%%%%%%%%%%%%%%%%%%%% program macros %%%%%%%%%%%%%%%%%



% a blank line
\def\blankline{\hbox{}}

%%%%%%%%%%%%%%%%%%%%% End of PROGRAM macros %%%%%%%%%%%%%%%%%


%
% The following macro is used to generate the header.
%
%


%
% Use these macros for organizing sections of your notes.
% Each command takes two arguments: (1) the title of the section and and
% (2) a keyword for that section to appear in the index.  (See examples.)
% Please don't use \section, \subsection, and \subsubsection directly!
%

%\newcommand{\topic}[2]{\section{#1} \index{#2} \markright{#1}}
%\newcommand{\subtopic}[2]{\subsection{#1} \index{#2}}
%\newcommand{\subsubtopic}[2]{\subsubsection{#1} \index{#2}}
\remove{
\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{stat}{}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
%\newcommand{\qed}{\hfill $\Box$}
%\newenvironment{proof}{\par{\noindent \bf Proof:}}{\qed \par}
\newenvironment{proof}{{\em Proof:}}{\hfill\rule{2mm}{2mm}}{\par}
}
\newcommand{\qed}{\hfill\BlackBox\\[2mm]}

\jmlrheading{5}{2003}{1-25}{4/02; Revised 9/02}{12/03}{Eyal Even-Dar and Yishay Mansour}

% Short headings should be running head and authors last names

\ShortHeadings{Learning Rates for Q-learning}{Even-Dar and
Mansour}





%\setcounter{page}{0}
%\def\thepage{}
%\pagestyle{empty}

\begin{document}
\title{Learning Rates for Q-learning}

\author{\name Eyal Even-Dar \email evend@cs.tau.ac.il\\
       \name Yishay Mansour \email mansour@cs.tau.ac.il \\
       \addr School of Computer Science\\
       Tel-Aviv University\\
       Tel-Aviv, 69978, Israel
}
\editor{Peter Bartlett} \maketitle
%\tableofcontents
%\normalsizedb




\begin{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^\omega$ at time $t$ where $\omega\in(1/2,1)$,
we show that the convergence rate is polynomial in $1/(1-\gamma)$,
where $\gamma$ 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-\gamma)$.
In addition we show a simple example that proves this exponential behavior
is inherent for linear learning rates.
\end{abstract}

\begin{keywords}
Reinforcement Learning, Q-Learning, Stochastic Processes,
Convergence Bounds, Learning Rates.
\end{keywords}
%\pagenumbering{arabic}
%\newpage
\section{Introduction}

% RL & MDP
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 \citep{sb98,bt96}.


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 {\em return}  combines
a sequence of rewards into a single value that the agent tries to optimize.
A {\em discounted return} has a parameter $\gamma\in(0,1)$ where the reward received
at step $k$ is discounted by $\gamma^k$.
% Learning & Q-learning

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
Q-learning \citep{wat89}.
%Whats known on Q-learning (limit & batch)

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 construct the
optimal policy. There are various proofs that Q-learning does
converge to the optimal Q function, under very mild conditions \citep{bt96,tsi94,wat92,lit96,jakcon,ode}. 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).
%Our results

We build on the proof technique of \cite{bt96}, 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^\omega$, where $\omega\in(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-\gamma)$, while for a
linear learning rate the convergence rate is exponential in
$1/(1-\gamma)$. 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/\epsilon)^{1/(1-\gamma)})$ updates, using a linear learning
rate, until we reach a value of $\epsilon$. \remove{ In addition
we also state a general lower bound, which is the same as for the
PAC model.}


The different behavior might be explained by the asymptotic
behavior of $\sum_t \alpha_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 $\sum_{t=1}^T \alpha_t = O(\ln
(T))$, whereas using  polynomial learning rate it behaves as
$O(T^{1 - \omega})$. 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.




%related work

The convergence rate of Q-learning in a batch setting, where many
samples are averaged for each update, was analyzed by \cite{ks98}.
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.
\remove{ A batch Q-learning overcomes the problems of a standard
Q-learning, which can be seen in this paper, by two major methods.
The first one is resetting the learning rate in each phase (note
that the average of the rewards and of the next state value can be
achieved by simply using linear learning rate from zero) and the
second one is to take into consideration only the value of the Q
vector from the beginning of each phase. The first idea gives this
algorithm the ability to converge faster (in this variant $\sum_t
\alpha_t$ is much larger than in the standard Q-learning using
linear learning rate). Since the Q-value is not updated during a
phase and we use only the initial Q-value in each phase , the
batch Q-learning has an "immunity" from bad samples during each
phase. At the end of the phase there are enough samples to be
close to the real distribution the error from the next state value
is bounded since we use only the initial value. Therefore, the
noise term is handled and the updated Q-value is contracted with
respect to the distance from the optimal value. }

The convergence of Q-learning with linear learning rate
was studied by \cite{s97} 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 \cite{s97} shows a convergence rate, which is
exponential in $1/(1-\gamma)$.
%however some of the constant there can be as large as the log of the number of states.
%
\cite{bgs99} give an exponential lower bound in
the number of the states for undiscounted return.
%The paper is organized as follows.
%In section \erf{section_model} we describe the model


\section{The Model}
\label{section_model}

We define a Markov Decision process (MDP) as follows
\begin{definition}
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^M_{i,j}(a)$ is the transition probability
from state $i$ to state $j$ when performing action $a \in U(i)$ in state $i$, and
$R_M(s,a)$ is the reward received when performing action $a$ in state $s$.
\end{definition}

We assume that $R_M(s,a)$ is non-negative and bounded by $R_{max}$, i.e.,
$\forall s,a : \;\; 0 \leq R_M(s,a) \leq 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\in 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 $\pi$ 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^M_{s_t,s_{t+1}}(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 {\em discounted
return}, which has a parameter $\gamma\in (0,1)$, and the
discounted return of policy $\pi$ is $ V^\pi_M =
\sum_{t=0}^{\infty}\gamma^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- \gamma}$.

We define a value function for each state $s$, under policy $\pi$,
as $V^{\pi}_M (s)= E[\sum_{i=0}^\infty r_i\gamma^i]$, where the
expectation is over a run of policy $\pi$ starting at state $s$.
We define a state-action value function $Q^{\pi}_M(s,a) =
R_M(s,a)+
\gamma\sum_{\bar{s}}P_{s,\bar{s}}^M(a)V_{M}^{\pi}(\bar{s})$ ,
whose value is  the return of initially performing action $a$ at
state $s$ and then following policy $\pi$. Since $\gamma < 1 $ we
can define another parameter $\beta=(1-\gamma)/2$, which will be
useful for stating our results. (Note that as $\beta$ decreases
$V_{max}$ increases.)

Let $\pi^*$ 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 \citep{Puterman}.)
This implies that for any policy $\pi$ and any state $s$ we have $
V^{\pi^*}_M(s) \geq V^{\pi}_M(s)$, and $\pi^*(s) =
{argmax}_{a}(R_M(s,a) + \gamma(\sum_{s'}P^M_{s,s'}(a) \max_b
Q(s',b))$. The optimal policy is also the only fixed point of the
operator, $(TQ)(s,a) = R_M(s,a) + \gamma
\sum_{s'}P_{s,s'}(a)\max_bQ(s',b)$. We use $V_M^*$ and $Q_M^*$ for
$V^{\pi^*}_M$ and $Q^{\pi^*}_M$, respectively.
%
We say that a policy $\pi$ is an $\epsilon$-approximation of the optimal
policy if $ \| V_M^* - V_M^\pi\|_\infty \leq \epsilon$.


For a sequence of state-action pairs let the {\em 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
\cite{ks98}. 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^M_{s,s'}(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.

{\bf Notations:} The notation $g=\tilde{\Omega}(f)$ implies that there are
constants $c_1$ and $c_2$ such that $g\geq c_1 f \ln^{c_2} (f)$. All the
norms $\| \cdot \|$, unless otherwise specified, are $L_\infty$ norms,
i.e., $\|(x_1, \ldots, x_n)\|=\max_i x_i$.

\section{Q-learning}

The Q-learning algorithm \citep{wat89} estimates the state-action value function
(for discounted return) as follows:
\begin{equation}
\label{eq-ql} Q_{t+1}(s,a) = (1 - \alpha_t(s,a))Q_t(s,a) +
\alpha_t(s,a)(R_M(s,a) + \gamma \max_{b \in U(s')} Q_t(s',b)),
\end{equation}
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
 $\alpha_t(s,a) = 0$ for $t \notin T^{s,a}$.
It is known that Q-learning converges to $Q^*$ if each state action pair is performed
infinitely often and $\alpha_t(s,a) $ satisfies for each $(s,a)$ pair:
$\sum_{t=1}^{\infty}\alpha_t(s,a) = \infty$ and $\sum_{t=1}^{\infty}\alpha_t^2(s,a) < \infty$
\citep{bt96,tsi94,wat92,lit96,jakcon}.


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
{\em synchronous Q-learning}, which performs the updates by using
the $PS(M)$. Specifically:
\begin{eqnarray*}
\forall{s,a} & : & Q_{0}(s,a) = C \\
\forall{s,a} & : & Q_{t+1}(s,a) = (1 -
\alpha_{t}^{\omega})Q_{t}(s,a) + \alpha_{t}^{\omega}(R_M(s,a) +
\gamma\max_{b \in U(\bar{s})}Q_{t}(\bar{s},b)),
\end{eqnarray*}
where $\bar{s}$ is the state reached from state $s$ when
performing action $a$ and $C$ is some constant. The learning rate
is $\alpha_t^{\omega} = \frac{1}{(t+1)^{\omega}}$, for
$\omega\in(1/2,1]$. We distinguish between a {\em linear learning
rate}, which is $\omega=1$, and a {\em polynomial learning rate},
which is  $\omega\in (\frac{1}{2} ,1)$.

The {\em asynchronous Q-learning algorithm}, is simply regular
Q-learning as define in (\ref{eq-ql}), and we add the assumption
that the underlying strategy has a covering time of $L$. The
updates are as follows:
\begin{eqnarray*}
\forall{s,a} & :& Q_{0}(s,a) = C\\
\forall{s,a} & :& Q_{t+1}(s,a) = (1 - \alpha_{t}^{\omega}(s,a))Q_{t}(s,a) +
\alpha_{t}^{\omega}(s,a)(R_M(s,a) + \gamma \max_{b \in U(\bar{s})} Q_{t}(\bar{s},b) )
\end{eqnarray*}
where $\bar{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 $\alpha_t^{\omega}(s,a) =  \frac{1}{ [\#(s,a,t)]^{\omega}}$,
if $t \in T^{s,a}$ and $\alpha_t^{\omega}(s,a) = 0$ otherwise.
Again, $\omega = 1$ is a  linear learning rate, and $\omega \in (\frac{1}{2},1)$
is a polynomial learning rate.


%In this paper
%we first analyze the synchrouns Q-learning algorithm and then generalize
%the results to the asynchrouns Q-learning algorithm assuming a covering time $L$.

\section{Our Main Results}
\label{section_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-\gamma)=1/(2\beta)$. In contrast, we show that
linear learning rate has an exponential dependence on $1/\beta$.
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/\beta$,
and
for linear learning rate our bound is exponential in $\frac{1}{\beta}$.
We also show a lower bound for linear learning rate,
which is exponential in $\frac{1}{\beta}$.
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.


\begin{theorem}
\label{the:psmw} 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 - \delta$, we have that $|| Q_T
- Q^* || \leq \epsilon$, given that
\[
T = \Omega\left(\left(\frac {V_{max}^2 \ln(\frac{|S|\;|A|
V_{max}}{\delta\beta\epsilon})}
{\beta^2\epsilon^2}\right)^{\frac{1}{\omega}} +
\left(\frac{1}{\beta}\ln\frac{V_{max}}{\epsilon}\right)^{\frac{1}{1-\omega}}\right)
%
%T = O\left(\left(\left(\frac {(V_{max}^{\frac{2}{\omega}}
%\ln^{\frac{1}{\omega}}(\frac{1}{\delta}+ |S| + |A| +
%\frac{1}{\beta}\ln(\frac{V_{max}}{\epsilon}) + ((\frac{1}{\beta \epsilon}))^{\frac{2}{\omega}})}
%{\beta^{\frac{2}{\omega}}\epsilon^{\frac{2}{\omega}}}\right)^{1 - \omega}
%+ \frac{1}{\beta}\ln\frac{V_{max}}{\epsilon}\right)^{\frac{1}{1-\omega}}\right)
\]
\end{theorem}

The above bound is somewhat complicated. To simplify, assume that
$\omega$ is a constant and consider first only its dependence on
$\epsilon$. This gives us $\Omega ((\ln (1/\epsilon)/
\epsilon^2)^{1/\omega} + (\ln (1/\epsilon))^{1/(1-\omega)} )$,
which is optimized when $\omega$ approaches one.
%
Considering the dependence only on $\beta$, recall that $V_{max}= R_{max}/(2\beta)$,
therefore the complexity is
$ \tilde\Omega (1 /\beta^{4/\omega} + 1/\beta^{1/(1-\omega)} )$
which is optimized for $\omega=4/5$.
%
The following theorem bounds the time for linear learning rate.

\begin{theorem}
\label{the:psm1} Let $Q_T$ be the value of the synchronous
Q-learning algorithm using linear learning rate at time $T$. Then
for any positive constant $\psi$ with probability at least $1-
\delta$, we have $|| Q_T - Q^* || \leq \epsilon$, given that
\[
T = \Omega\left(((2+\psi)^{\frac{1}{\beta}\ln(\frac{V_{max}}{\epsilon}
)}
\frac{V_{max}^{2}\ln(\frac{|S| \; |A| V_{max} }{\delta\beta\psi\epsilon} )}
{ (\psi \beta \epsilon)^2}\right).
%
%T = O\left((\frac{V_{max}}{\epsilon})^{\frac{1}{\beta}}
%\frac{V_{max}^{2}\ln(\frac{1}{\delta} + |S| + |A|  +
%\frac{1}{\beta}\ln(\frac{V_{max}}{\epsilon})+\frac{1}{\beta \epsilon})}{
%(\beta \epsilon)^2}\right).
\]

\end{theorem}


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$.
\begin{theorem}
\label{the:mainw} 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- \delta$, we have $|| Q_T - Q^*
|| \leq \epsilon$, given that
$$
T = \Omega\left( \left(\frac{L^{1+ 3
\omega}V_{max}^2\ln(\frac{|S|\;|A| V_{max}}{\delta\beta\epsilon}
)} {\beta^2\epsilon^2}\right)^{\frac{1}{\omega}} +
\left(\frac{L}{\beta}\ln\frac{V_{max}}{\epsilon}\right)^{\frac{1}{1-\omega}}\right)
$$
\end{theorem}

The dependence on the covering time, in the above theorem, is
$\Omega(L^{2+1/\omega} +L^{1/(1-\omega)})$, which is optimized for
$\omega \approx 0.77$. For the linear learning rate the dependence
is much worse, since it has to be that $L\geq |S| \cdot |A|$, as
is stated in the following theorem.

\begin{theorem}
\label{the:main1} 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 -\delta$, for any positive constant
$\psi$ we have $|| Q_T - Q^* || \leq \epsilon$, given that
$$
T = \Omega\left(\left(L+\psi L +
1\right)^{\frac{1}{\beta}\ln{\frac{V_{max}}{\epsilon}}}
%(\frac{V_{max}}{\epsilon})^{\frac{1}{3\beta}}
\frac{V_{max}^{2}\ln(\frac{|S| \; |A| V_{max} }{\delta\beta\epsilon\psi})}
{(\psi \beta \epsilon)^2}\right)
$$
\end{theorem}


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

\begin{theorem}
\label{the:lower} There exists a deterministic MDP, M, such that
Q-learning with linear learning rate after
$T=\Omega((\frac{1}{\epsilon})^{\frac{1}{1- \gamma}}) $ steps has
$\|Q_T - Q_M^*\| > \epsilon$.
\end{theorem}

\remove{ The following theorem is a general lower bound for any
learning algorithm. This bound is similar to the PAC lower bound.

\begin{theorem}
\label{the:lowergen}
There exists an MDP, M, such that any learning algorithm $A$ that after $T$ steps outputs
a policy $\pi$,
if $T<c(\frac{\ln(\frac{1}{\delta})}{\epsilon^2})$ , for some constant $c$,
then with probability at least $\frac{1}{2}$ we have that $\|Q^\pi - Q^*\| > \epsilon$.
\end{theorem}
}


\section{Experiments}
\label{section-exp} 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 \ref{app:lower}. 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)}{\sum_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 \neq j$. The reward distribution is
identical to that of the random MDP. (We implemented the random
function using the function rand() in C.)
\begin{figure}[htb]
%\psfig{file=100StaSync0.7100mill.eps ,width=4in ,clip=}
\psfig{file=100st-rand.eps ,width=2.98in,height=3in}
\psfig{file=100st-line.eps ,width=2.98in,height=3in}
\caption{Example of 100 states MDP (both line and random), where
the discount factor is $\gamma = 0.7$. We ran asynchronous
Q-learning using a random exploration policy for $10^8$ steps.}
\label{fig:100states}
\end{figure}


Figure \ref{fig:100states} demonstrates the relation between the
exponent of the learning rate $\omega$ and the accuracy of the model. The
best experimental value for $\omega$ is about $0.85$. Note that
when $\omega$ 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 $\omega$ of approximately $0.85$. Our
theoretical results derive optimal values of optimal $\omega$ 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).
\begin{figure}[htb]
\psfig{file=dis-rand.eps ,width=2.98in ,clip=}
\psfig{file=dis-line.eps ,width=2.98in ,clip=} \caption{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 $\omega = 0.7$; the
dashed line is asynchronous Q-learning using a linear learning
rate ($\omega = 1.0$).} \label{fig:discount}
\end{figure}

Figure \ref{fig:discount} demonstrates the strong relationship between
discount factor, $\gamma$, 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 $\omega = 0.7$ remains
stable (the error is below 0.1).

Figure \ref{fig:69} compares two different learning rates
$\omega =0.6$ and $\omega =0.9$ for ten state MDPs (both random
and line) and finds an interesting tradeoff. For low precision
levels, the learning rate of $\omega =0.6$ was superior, while for
high precision levels the learning rate of $\omega =0.9$ was
superior. An explanation for this behavior is that the dependence
in terms of $\epsilon$ is $\Omega ((\ln (1/\epsilon)/
\epsilon^2)^{1/\omega} + (\ln (1/\epsilon))^{1/(1-\omega)} )$,
which is optimized as the learning rate approaches one.

\begin{figure}[htb]
\psfig{file=eps69-rand.eps ,width=2.98in ,clip=}
\psfig{file=eps69-line.eps ,width=2.98in ,clip=} \caption{Random and Line MPDs (10 states each), where the discount factor
is $\gamma = 0.9$. The dashed line is synchronous  Q-learning
using $\omega = 0.9$ and the the solid line is
synchronous Q-learning using $\omega = 0.6$.}
\label{fig:69}
\end{figure}

\remove{
\begin{figure}[htb]
\psfig{file=cover.eps ,width=4in ,clip=} \caption{Example of line
MDP, where the discount factor is $\gamma= 0.7$. Asynchronous
Q-learning ran for ten million steps.} \label{fig:cover}
\end{figure}

In Figure \ref{fig:cover}, we wanted to see how is the relation
between number of states and the convergence rate. Thus we got
that the difference was bigger hand in hand with size of the MDP
which implies on the covering time. }

Our last experimental result is $M_0$, the lower bound example from
Section \ref{app:lower}. Here the difference between the learning
rates is the most significant, as shown in Figure \ref{fig:lower}.%\ref{fig:low2}.

\begin{figure}[bth]
\centering \psfig{file=lower.eps ,width=3.2in ,clip=}
\caption{Lower bound example $M_0$, with discount
factor $\gamma = 0.9$. Q-learning ran with two different
learning rates, linear (dashed line) and $\omega= 0.65$ (solid
line).} \label{fig:lower}
\end{figure}


\section{Background from Stochastic Algorithms}
\label{sec:sto}

%To build the proof for Theorem ~\ref{the:psm1}
Before we derive our proofs,
we first introduce the proof given by \cite{bt96}
for the convergence of stochastic iterative algorithms; in Section \ref{section:applying}
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.)

This section considers a general type of {\em iterative stochastic algorithms},
which is computed as follows:
\begin{equation}
\label{sta:type}
X_{t+1}(i) = (1 - \alpha_{t}(i))X_{t}(i) + \alpha_{t}(i)((H_{t}X_{t})(i) + w_{t}(i)),
\end{equation}
where $w_{t}$ is a bounded random variable with zero expectation,
and each $H_t$ is assumed to belong to a family ${\cal H}$ of
pseudo contraction mappings (See \cite{bt96} for details).

\begin{definition}
\label{def:cond}
An iterative stochastic algorithm is well-behaved if:
\begin{enumerate}
\item The step size $\alpha_{t}(i)$ satisfies
(1) $\sum_{t=0}^{\infty}\alpha_{t}(i) = \infty$,
(2) $\sum_{t=0}^{\infty}\alpha_{t}^{2}(i) < \infty$ and
(3) $\alpha_t(i) \in (0,1)$.
\item
There exists a constant $A$ that bounds $w_t(i)$ for any history
$F_t$, i.e., $\forall t,i :\;|w_{t}(i)| \leq A$.
\item
There exists $\gamma \in [0,1)$ and a vector $X^*$ such that for any $X$
we have $||H_{t}X - X^*|| \leq \gamma||X - X^*||$.
%\item there exists a nonnegative random sequence $\theta_{t}$, that converges to zero with probability 1, and is such that
%$$\forall i,t \;\;\; |u_{t}(i)| \leq \theta_{t}(||r_{t}||+ 1)$$
\end{enumerate}
\end{definition}

\remove{
The following fact (proven in \cite{bt96}) shows the connection
with the Q-learning algorithms.

\begin{fact}
Synchronous Q-learning and Asynchronous Q-learning are both
well-behaved stochastic iterative algorithms.
\end{fact}
The proof of this fact can be found in Section~\ref{section:applying}. } The main theorem states that a well-behaved stochastic iterative algorithm converges in the limit.


\begin{theorem}
\label{the:sto} [\cite{bt96}] Let $X_{t}$ be the sequence
generated by a well-behaved stochastic iterative algorithm. Then
$X_{t}$ converges to $X^{*}$ with probability $1$.
\end{theorem}

%\begin{proof}
The following is an outline of the proof given by \cite{bt96}.
Without loss of generality, assume that $X^{*} = 0$ and $\|X_0\|\leq A$.
The value of $X_{t}$ is bounded since $\|X_0\| \leq A$ and for any history $F_t$
we have $\| w_t \| \leq A$; hence, for any $t$
we have $\| X_t \| \leq A$.

Recall that $\beta = \frac{1 - \gamma}{2}$. Let $D_1 = A$ and
$D_{k+1} = (1 - \beta)D_{k}$ for $k \geq 1$. Clearly the sequence
$D_{k}$ converges to zero. We prove by induction that for every
$k$ there exists some time $\tau_{k}$ such that for any $t \geq
\tau_k$ we have $\|X_{t}\| \leq D_{k}$. Note that this will
guarantee that at time $t\geq \tau_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 $\tau_k$ and we show that there
exists a time $\tau_{k+1}$ such that for $t \geq \tau_{k+1}$ we have $\|X_{t}\| \leq D_{k+1}$.
Since $D_k$ converges to zero this proves that $X_{t}$ converges to zero, which equals $X^*$.
%Let $W_{0}(i) = 0$ and
%$$W_{t+1} = (1-\alpha_{t})W_{t}(i) + \alpha_{t}(i)w_{t}(i)$$
%We know that since $r_{t}$ is bounded, the variance of $w_t$
% is bounded and therefore $W_{t}$ converges to zero.
%
For the proof we define for $t \geq \tau$ the quantity
$$
W_{t+1;\tau}(i) = (1-\alpha_{t}(i))W_{t;\tau} (i) +
\alpha_{t}(i)w_{t}(i),
$$
where $W_{\tau;\tau}(i) = 0$.
The value of $W_{t;\tau}$ bounds the contributions of $w_{j}(i)$, $ j \in [\tau,t]$,
to the value of $X_t$ (starting from time $\tau$).
We also define for $t\geq \tau_k$,
$$
Y_{t+1;\tau}(i) = (1-\alpha_{t}(i))Y_{t;\tau}(i) +\alpha_{t}(i)\gamma D_{k}
$$
where $Y_{\tau_k;\tau_k}=D_k$.
Notice that $Y_{t;\tau_k}$ is a deterministic process.
The following lemma gives the motivation for the definition of $Y_{t;\tau_k}$.

\begin{lemma}
\label{lem:stoch1} [\cite{bt96}] For every i, we have
$$-Y_{t;\tau_k}(i) + W_{t;\tau_{k}}(i) \leq X_{t}(i) \leq Y_{t;\tau_k}(i) + W_{t;\tau_{k}}(i)$$
\end{lemma}
Next we use Lemma \ref{lem:stoch1} to complete the proof of
Theorem \ref{the:sto}. From the definition of $Y_{{t;\tau}}$ and
the assumption that $\sum_{t=0}^{\infty}\alpha_{t} = \infty$, it
follows that $Y_{{t;\tau}}$ converges to $\gamma D_{k}$ as $t$
goes to infinity. In addition $W_{t;\tau_k}$ converges to zero as
$t$ goes to infinity. Therefore there exists a time $\tau_{k+1}$
such that $Y_{t;\tau} \leq (\gamma+\frac{\beta}{2})D_k$, and
$|W_{t;\tau_k} | \leq \beta D_k/2$. This fact, together with
Lemma.~\ref{lem:stoch1}, yields that for $t\geq \tau_{k+1}$,
\[
||X_{t}|| \leq (\gamma + \beta ) D_{k} = D_{k+1},
\]
%Therefore , there exists some time $t_{k+1}$ such that
%$||X_{t}|| \leq D_{k+1}$ for all $ t \geq t_{k+1}$
which completes the proof of Theorem \ref{the:sto}.

\section{Applying the Stochastic Theorem to Q-learning}
\label{section:applying} 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 \cite{bt96} At the beginning we deal with
synchronous Q-learning. First define operator $H$ as
$$(HQ)(i,a) = \sum_{j=0}^n P_{ij}(a)(R(i,a) + \gamma \max_{b \in U(j)}Q(j,b))$$
Rewriting Q-learning with $H$, we get
$$Q_{t+1}(i,a) = (1 - \alpha_t(i,a))Q_t(i,a) + \alpha_t(i,a)((HQ_t)(i,a) + w_t(i,a)).$$
Let $\bar{i}$ 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) + \gamma \max_{b \in U(\bar{i})}Q_t(\bar{i},b) -
\sum_{j=0}^n P_{ij}(a)\left(R(i,a) + \gamma \max_{b \in
U(j)}Q_t(j,b)\right)$$ In synchronous Q-learning, $H$ is
computed simultaneously on all states actions pairs.
\begin{lemma}
\label{lem:Contraction} Synchronous Q-learning is a well-behaved
iterative stochastic algorithm.
\end{lemma}
\begin{proof}
We know that for any history $F_t$ $E[w_t(i,a) | F_t] = 0$ and
$|w_t(i,a)| \leq V_{max}$. We also know that for $\frac{1}{2} <
\omega \leq 1$ we have that $\sum\alpha_t(s,a) = \infty$,
$\sum\alpha_t^2(s,a) < \infty$ and $\alpha_t(s,a) \in (0,1)$.
\\We need only show that $H$ satisfies the contraction property.
\begin{eqnarray*}
|(HQ)(i,a) - (H\bar{Q})(i,a)| & \leq
&\sum_{j=0}^nP_{ij}(a)|\gamma\max_{b \in U(j)}Q(j,b) -
\gamma\max_{b \in U(j)}\bar{Q}(j,b)|
\\ & = & \sum_{j=0}^nP_{ij}(a)\gamma|\max_{b \in U(j)}Q(j,b) - \max_{b \in U(j)}\bar{Q}(j,b)|
\\ & \leq & \sum_{j=0}^nP_{ij}(a)\gamma\max_{b \in U(j)}|Q(j,b) - \bar{Q}(j,b)|
\\& \leq & \gamma\sum_{j=0}^nP_{ij}(a)\|Q - \bar{Q}\| \leq \gamma\|Q - \bar{Q}\|
\end{eqnarray*}

Since we update all $(i,a)$ pairs simultaneously, synchronous
Q-learning is well-behaved stochastic iterative algorithm.
\end{proof}

We next show that Theorem~\ref{the:sto} can be applied also to asynchronous  Q-learning.
\begin{lemma}
\label{lem:Qstoch} Asynchronous Q-learning, where the input
sequence has a finite covering time $L$, is a well-behaved
iterative stochastic algorithm.
\end{lemma}
\begin{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
state-action 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
\begin{eqnarray*}
|(HQ_t)(i,a) - (HQ^*)(i,a)| & \leq
&\sum_{j=0}^nP_{ij}(a)|\gamma\max_{b \in U(j)}Q_t(j,b) -
\gamma\max_{b \in U(j)}Q^*(j,b)|
\\& = &\sum_{j=0}^nP_{ij}(a)\gamma|\max_{b \in U(j)}Q_t(j,b) - \max_{b \in U(j)}Q^*(j,b)|
\\& \leq & \sum_{j=0}^nP_{ij}(a)\gamma\max_{b \in U(j)}|Q_t(j,b) - Q^*(j,b)|
\\& \leq & \sum_{j \in A}P_{ij}(a)\gamma\max_{b \in U(j)}|Q_t(j,b) - Q^*(j,b)|
\\& & +  \sum_{j \in B}P_{ij}(a)\gamma\max_{b \in U(j)}|Q_t(j,b) - Q^*(j,b)|
\\& \leq & \gamma\|Q_t - Q^*\|,
\end{eqnarray*}
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^*\| \leq \|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)| \leq \gamma|Q_t- Q^*|$. We look at the
operator $H$ after performing all state-action pairs, $\|HQ -
Q^*\| \leq max_{i,a}|HQ_t(i,a) - Q^*(i,a)| \leq \gamma\|Q_t- Q^*\|
\leq \gamma\|Q- Q^*\|.$
\end{proof}


\section{Synchronous Q-learning}
\label{section_synchronous}

In this section we give the proof of Theorems~\ref{the:psmw} and
\ref{the:psm1}. Our main focus will be the value of $r_t
=\|Q_t -Q^* \|$, and our aim is to bound the time until $r_t\leq
\epsilon$. We use a sequence of values $D_i$, such that $D_{k+1} =
(1 - \beta)D_k$ and $D_1 = V_{max}$. As in Section \ref{sec:sto},
we will consider times $\tau_k$ such that for any $t\geq \tau_k$
we have $r_t \leq D_k$. We call the time between $\tau_k$ and
$\tau_{k+1}$ the $k$th 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\leq \epsilon$.
The bound is derived in the following Lemma.

\begin{lemma}
\label{lemma:num} For $m\geq \frac{1}{\beta}\ln
(V_{max}/\epsilon)$ we have $D_m\leq \epsilon$.
\end{lemma}
\begin{proof}
We have that $D_1 = V_{max}$ and $D_i = (1-\beta)D_{i-1}$. We want
to find the $m$ that satisfies $D_m = V_{max}(1-\beta)^m \leq
\epsilon$. By taking a logarithm over both sides of the inequality
we get $m \geq \frac{1}{\beta}\ln (V_{max}/\epsilon)$.
\end{proof}

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~\ref{sec:sto}. Let $W_{t+1,\tau}(s,a) =
(1-\alpha^\omega_{t}(s,a))W_{t,\tau}(s,a) +
\alpha^\omega_{t}(s,a)w_{t}(s,a)$, where $W_{\tau;\tau} (s,a) = 0$
and
\[
w_t(s,a) = R(s,a) + \gamma \max_{b \in U(s')}Q_t(s',b) -
 \sum_{j=1}^{|S|} P_{s,j}(a)\left(R(s,a) + \gamma \max_{b \in U(j)}Q_t(j,b)\right),
\]
where $s'$ is the state reached after performing action $a$ at state $s$.
Let
\[
Y_{t+1;\tau_k}(s,a) = (1-\alpha^\omega_{t}(s,a))Y_{t;\tau_k}(s,a)
+\alpha^\omega_t(s,a)\gamma D_k ,
\]
where $Y_{\tau_k;\tau_k}(s,a) = D_k$.
%
Our first step is to rephrase Lemma \ref{lem:stoch1} for our setting.

\begin{lemma}
\label{lem:stoch2}
For every state $s$ action $a$ and time $\tau_k$, we have
$$-Y_{t;\tau_k}(s,a) + W_{t;\tau_k}(s,a) \leq  Q^*(s,a) - Q_t(s,a)
\leq Y_{t;\tau_k}(s,a) + W_{t;\tau_k}(s,a)$$
\end{lemma}


The above lemma suggests (once again) that in order to bound the error $r_t$ one can
bound $Y_{t;\tau_k}$ and $W_{t;\tau_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;\tau}$, which is stochastic.
%??? maybe better not ????
%To simplify the notation we use $Y_{t;\tau_k}$, $W_{t;\tau}$ and $w_{i}$ instead of
%$Y_{t;\tau_k}(s,a)$, $W_{t,\tau}(s,a)$ and $w_i(s,a)$, respectively.
%?????
\subsection{Synchronous Q-learning using a Polynomial Learning Rate}
\label{sec-sync-poly}
We start with
Q-learning using a polynomial learning rate and
show that the duration of iteration $k$, which starts at time $\tau_k$
and ends at time $\tau_{k+1}$,
is bounded by $\tau^\omega_k$.
For synchronous Q-learning with a polynomial learning rate
we define $\tau_{k+1}=\tau_k+\tau_k^\omega$, where $\tau_1$
will be specified latter.


\begin{lemma}
\label{lem:IterSizew}
%Let $Y_{\tau} = D_k$.  If there exists a time $\tau$ such
Consider synchronous Q-learning with a polynomial learning rate and
assume that for any $t \geq \tau_k$ we have $Y_{t;\tau_k}(s,a) \leq D_k$.
Then for any $t \geq \tau_k + \tau_k^{\omega}=\tau_{k+1}$ we have
$Y_{t;\tau_k} (s,a) \leq D_k(\gamma+ \frac{2}{e}\beta) $.
\end{lemma}

\begin{proof}
Let $Y_{\tau_k;\tau_k}(s,a) = \gamma D_k + \rho_{\tau_k}$,
where $\rho_{\tau_k} = (1 - \gamma)D_k$.
We can now write
\[
Y_{t+1;\tau_k}(s,a) = (1- \alpha^\omega_t)Y_{t;\tau_k}(s,a) +
\alpha^\omega_t\gamma D_k = \gamma D_k + (1
-\alpha^\omega_t)\rho_t,
\]
where $\rho_{t+1} = \rho_t(1- \alpha_t^\omega)$. We would like to
show that after time $\tau_{k+1} = \tau_k + \tau_k^{\omega}$ for
any $ t \geq \tau_{k+1}$ we have $\rho_t \leq \frac{2}{e}\beta
D_k$. By definition we can rewrite $\rho_t$ as
$$
\rho_t = (1-\gamma)D_k\prod_{l=1}^{t-\tau_k}(1-\alpha^\omega_{l+\tau_k}) =
2\beta D_k\prod_{l=1}^{t-\tau_k}(1-\alpha^\omega_{l+\tau_k})
= 2\beta D_k\prod_{l=1}^{t-\tau_k} (1-\frac{1}{(l+\tau_k)^{\omega}}),
$$
where the last identity follows from the fact that $\alpha^\omega_t = 1/ t^\omega$.
Since the $\alpha^\omega_t$'s are monotonically decreasing
$$
\rho_t \leq 2\beta D_k (1-\frac{1}{\tau_k^{\omega}})^{t-\tau_k}.
$$
For $t \geq \tau_k + \tau_k^\omega$ we have
$$
\rho_t\leq 2\beta D_k (1-\frac{1}{\tau_k^{\omega}})^{\tau_k^{\omega}} \leq \frac{2}{e}\beta D_k.
$$
Hence, $Y_{t;\tau_k}(s,a) \leq (\gamma + \frac{2}{e}\beta) D_k$.
\end{proof}

Next we bound the term
$W_{t;\tau_k}$ by $(1 - \frac{2}{e})\beta D_k$. The sum of
the bounds for $W_{t;\tau_k}(s,a)$ and $Y_{t;\tau_k}(s,a)$
would be $(\gamma+ \beta)D_k = (1-\beta)D_k=D_{k+1}$,
as desired.

\begin{definition}
Let $W_{t;\tau_k}(s,a) = (1 - \alpha^\omega_t(s,a))W_{t-1;\tau_k}(s,a) + \alpha^\omega_t(s,a) w_{t}(s,a)
\\ = \sum_{i=\tau_k+1}^t\eta_i^{k,t}(s,a)w_{i}(s,a)$
, where $\eta_i^{k,t}(s,a) =
\alpha^\omega_{i+\tau_k}(s,a)\prod_{j=\tau_k + i + 1}^{t}(1 -
\alpha_{j}^\omega(s,a))$ and let $W^l_{t;\tau_k}(s,a) =
\sum_{i=\tau_k+1}^{\tau_k + l}\eta_i^{k,t}(s,a)w_{i}(s,a)$.
\end{definition}
Note that in the synchronous model $\alpha^\omega_t(s,a)$ and
$\eta_i^{k,t}(s,a)$ are identical for every state action pair. We
also note that $W^{t - \tau_k + 1}_{t;\tau_k}(s,a) =
W_{t;\tau_k}(s,a)$. We have bounded the term $Y_{t;\tau_k}$, for
$t=\tau_{k+1}$. This bound holds for any $t\geq \tau_{k+1}$, since
the sequence $Y_{t;\tau_k}$ is monotonically decreasing. In
contrast, the term $W_{t;\tau_k}$ is stochastic. Therefore it is
not sufficient to bound $W_{\tau_{k+1};\tau_k}$, but we  need to
bound $W_{t;\tau_k}$ for $t\geq \tau_{k+1}$. However, it is
sufficient to consider $t \in [\tau_{k+1},\tau_{k+2}]$. The
following lemma bounds the coefficients in that interval.

\begin{lemma}
\label{lem:Coef}
For any $t \in [\tau_{k+1} ,\tau_{k+2}]$ and
$i \in [\tau_k, t]$, we have
$
\eta_{i}^{k,t} = \Theta(\frac{1}{{\tau_k}^{\omega}}),
$
%where $\tau_{k+1} = \tau_{k} + \tau_k^{\omega}$ and $\tau_{k+2} = \tau_{k+1} + \tau_{k+1}^{\omega}$.
\end{lemma}
\begin{proof}
Since $\eta_i^{k,t} = \alpha^{\omega}_{i+\tau_k}\prod_{j=\tau_k +
i + 1}^{t}(1 - \alpha^{\omega}_{j})$,we can divide $\eta_t^{k,t}$
into two parts, the first one $\alpha^{\omega}_{i+\tau_k}$ and the
second one $\mu = \prod_{j=\tau_k + i + 1}^{t}(1 -
\alpha^{\omega}_{j})$. We show that the first one is
$\Theta(\frac{1}{\tau_k^{\omega}})$ and the second is constant.
\\Since $\alpha^{\omega}_{i+\tau_k}$ are monotonically decreasing we have for every $i \in [\tau_{k},\tau_{k+2}]$ we have $\alpha^{\omega}_{\tau_k} \leq \alpha^{\omega}_{i} \leq \alpha^{\omega}_{\tau_{k + 2}}$, thus
$\frac{1}{\tau_k^{\omega}} \leq \alpha^{\omega}_{t} \leq
\frac{1}{(\tau_{k+1} + \tau_{k+1}^{\omega})^{\omega}} \leq
\frac{1}{(3\tau_k^{\omega} + \tau_k)^{\omega}} <
\frac{1}{4\tau_k^{\omega}}$. Next we bound $\mu$. Clearly $\mu$ is
bounded from above by $1$. Also $ \mu \geq
\prod_{j=\tau_k}^{\tau_{k+2}}(1 - \alpha_{j}) \geq (1-
\frac{1}{{\tau_k}^{\omega}})^{3{\tau_k}^{\omega}} \geq
\frac{1}{e^3}$. Therefore, we have that for every $t \in [\tau_{k}
,\tau_{k+2}]$, $ \eta_{i}^{k,t} =
\Theta(\frac{1}{{\tau_k}^{\omega}}).$
\end{proof}


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.
\begin{lemma}
[\citealt{ azuma}] Let $X_0,X_1,...,X_n$ be a martingale sequence
such that for each $1 \leq k \leq n$,
$$
|X_k - X_{k-1} | \leq c_k,
$$
where the constant $c_k$ may depend on $k$. Then for all $n \geq
1$ and any $\epsilon > 0$
$$
Pr\left[|X_n - X_0| > \epsilon \right] \leq
2e^{-\frac{\epsilon}{2\sum_{k=1}^n c_k^2}}
$$
\end{lemma}

Next we show that Azuma's inequality can be applied to
$W_{t;\tau_k}^l$.

\begin{lemma}
\label{lem:azum-help-syn-poly} For any $t \in [\tau_{k+1},
\tau_{k+2}]$ and $1 \leq l \leq t$ we have that
$W_{t;\tau_k}^l(s,a)$ is a martingale sequence, which satisfies
$$
|W_{t;\tau_k}^l(s,a) - W_{t;\tau_k}^{l-1}(s,a)| \leq
\Theta(\frac{V_{max}}{\tau_k^\omega})
$$
\end{lemma}
\begin{proof}
We first note that $W_{t;\tau_k}^l(s,a)$ is a martingale sequence,
since
\begin{eqnarray*}
E[W_{t;\tau_k}^l(s,a) - W_{t;\tau_k}^{l-1}(s,a)|F_{\tau_k+l - 1}]
& = & E[\eta_{\tau_k+l}^{k,t}(s,a)w_{\tau_k + l}(s,a)|F_{\tau_k+l
- 1} ]\\ & = & \eta_{\tau_k + l}^{k,t}E[w_{\tau_k +
l}(s,a)|F_{\tau_k+l - 1} ]= 0. \end{eqnarray*} By Lemma
\ref{lem:Coef} we have that $\eta_l^{k,t}(s,a) = \Theta(1/
\tau_k^\omega)$, thus
$$|W_{t;\tau_k}^l(s,a) - W_{t;\tau_k}^{l-1}(s,a)| = \eta_{\tau_k +
l} ^{k,t}(s,a) |w_{\tau_k + l}(s,a)| \leq
\Theta(\frac{V_{max}}{\tau_k^\omega}).$$
\end{proof}

 The following lemma provides a bound for the
stochastic error caused by the term $W_{t;\tau_k}$ by using
Azuma's inequality.


\begin{lemma}
\label{lem:noise1} Consider synchronous Q-learning with a
polynomial learning rate. With probability at least $1 -
\frac{\delta}{m}$ we have $|W_{t;\tau_k}| \leq (1 -
\frac{2}{e})\beta D_k$ for any $t \in [\tau_{k+1},\tau_{k+2}]$,
i.e.,
$$
Pr\left[\forall t \in [\tau_{k+1}, \tau_{k+2}]: \;\;
|W_{t;\tau_k}| \leq (1 - \frac{2}{e})\beta D_k\right]
\geq 1 - \frac{\delta}{m}
$$
given that
$\tau_k = \Theta((\frac {V_{max}^2\ln(V_{max} |S|\; |A| m/(\delta\beta D_k))}
{\beta^2D_k^2})^{1/\omega})$.
\end{lemma}

\begin{proof}
By Lemma \ref{lem:azum-help-syn-poly} we can apply Azuma's
inequality to $W_{t;\tau_k}^{t - \tau_k + 1}$ with $c_i =
\Theta(\frac{V_{max}}{\tau_k^\omega})$ (note that $W_{t;\tau_k}^{t
- \tau_k + 1} =  W_{t;\tau_k})$ . Therefore, we derive that
\begin{eqnarray*}
Pr\left[|W_{t;\tau_k}(s,a)| \geq \tilde{\epsilon} \;|\; t \in [\tau_{k+1},\tau_{k+2}] \right]
& \leq & 2e^{\frac{-2 \tilde{\epsilon}^2}{\sum_{i=\tau_k}^{t}c_i^2}}
\leq 2e^{-c\tau_k^{\omega}\tilde{\epsilon}^2/V_{max}^2},
\end{eqnarray*}
for some constant $c>0$.
Set
$\tilde{\delta}_k =  2e^{-c\tau_k^{\omega}\tilde{\epsilon}^2/V_{max}^2}$,
which holds for
$\tau^\omega_k = \Theta(\ln(1/\tilde{\delta})V_{max}^2/\tilde{\epsilon^2})$.
%
Using the union bound we have,
$$
Pr\left[\forall t \in [\tau_{k+1}, \tau_{k+2}] : \;W_{t;\tau_k}(s,a) \leq \tilde{\epsilon}\right]
\leq \sum_{t=\tau_{k+1}}^{\tau_{k+2}} Pr\left[W_{t;\tau_k}(s,a) \leq \tilde{\epsilon} \right],
$$
thus taking $\tilde{\delta}_k = \frac{\delta}{m (\tau_{k+2} - \tau_{k+1}) |S||A|}$
assures that with probability at least
$1 - \frac{\delta}{m}$ the statement hold at every state-action pair
and time $t\in[\tau_{k+1},\tau_{k+2}]$.
As a result we have,
\[
\tau_k  =
\Theta\left((\frac{V_{max}^2\ln(|S|\;|A|\;m\tau_k^\omega/\delta)}
{\tilde{\epsilon}^2})^{1/\omega}\right)
=
\Theta\left((\frac{V_{max}^2\ln(|S|\;|A|\;m V_{max}/\delta\tilde{\epsilon})}
{\tilde{\epsilon}^2})^{1/\omega}\right)
\]
Setting $\tilde{\epsilon}=(1-2/e)\beta D_k$ gives the desire bound.
\end{proof}

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

\begin{lemma}
\label{lem:noise} Consider synchronous Q-learning using a
polynomial learning rate. With probability at least $1 - \delta$,
for every iteration $k\in[1,m]$ and time $t \in
[\tau_{k+1},\tau_{k+2}]$ we have $W_{t;\tau_k} \leq (1 -
\frac{2}{e}) \beta D_k$, i.e.,
$$
Pr\left[\forall k \in [1,m],\; \forall t \in [\tau_{k+1},\tau_{k+2}]: \;\;
|W_{t;\tau_k}| \leq (1 - \frac{2}{e})\beta D_k\right]
\geq 1 - \delta,
$$
given that
$\tau_0 = \Theta((\frac {V_{max}^2
\ln(V_{max} |S|\; |A| /(\delta\beta \epsilon))}{\beta^2 \epsilon^2})^{1/\omega})$.
\end{lemma}

\begin{proof}
 From Lemma~\ref{lem:noise1} we know that
\begin{eqnarray*}
\lefteqn{Pr\left[\forall t \in [\tau_{k+1},\tau_{k+2}]:\;\;|W_{t;\tau_k}| \geq (1 - \frac{2}{e})\beta D_k\right]}\\
& & = Pr\left[\forall s,a \;\forall t \in [\tau_{k+1},\tau_{k+2}]:
\;\;\sum_{i=\tau_{k}}^t w_{i}(s,a)\eta_i^{k,t} \geq
\tilde{\epsilon} \right] \leq \frac{\delta}{m}
\end{eqnarray*}
Using the union bound we have,
\begin{eqnarray*}
\lefteqn {Pr\left[\forall s,a\; \forall k \leq m, \forall t \in [\tau_{k+1},\tau_{k+2}]\;\;
\sum_{i=\tau_{k}}^{t}w_{i}(s,a)\eta_i^{k,t} \geq \tilde{\epsilon}\right]}\\
& & \;\;\;\leq \sum_{k = 1}^mPr\left[\forall s,a \;\forall t \in
[\tau_{k+1},\tau_{k+2}]\;\;\sum_{i=\tau_{k}}^{t}w_{i}(s,a)\eta_i^{k,t}
\geq \tilde{\epsilon}\right] \leq \delta
\end{eqnarray*}
where $\tilde{\epsilon} = (1 - \frac{2}{e})\beta D_k$.
\end{proof}

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
$\tau_{k+1}=\tau_k+\tau_k^\omega$ and bounds the total time
required (which is a special case of Lemma
\ref{lem:asynch_series_poly}).

\begin{lemma}
\label{lem:series}
Let
$$a_{k+1} = a_k+a_k^\omega= a_0+\sum_{i=0}^{k}a_i^{\omega}. $$
For any constant $\omega \in (0,1)$, $a_k = O((a_0^{1-
\omega}+k)^{\frac{1}{1 - \omega}}) = O(a_o + k^{\frac{1}{1 -
\omega}})$
\end{lemma}


The proof of Theorem ~\ref{the:psmw} follows from
Lemma \ref{lem:series}, Lemma \ref{lem:noise}, Lemma \ref{lemma:num} and Lemma \ref{lem:IterSizew}.


\subsection{Synchronous Q-learning using a Linear Learning Rate}
\label{app:synch_linear}

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 \ref{the:psmw} and we give here analogous
lemmas to the ones in Subsection \ref{sec-sync-poly}. 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.

\begin{lemma}
\label{lem:IterSize1}
Consider synchronous Q-learning with a linear learning rate and
assume that for any $t \geq \tau_k$ we have $Y_{t;\tau_k}(s,a) \leq D_k$.
Then for any $t \geq (2 + \psi)\tau_k =\tau_{k+1}$ we have
$Y_{t;\tau_k} (s,a) \leq D_k(\gamma + \frac{2}{2+\psi}\beta) $
\end{lemma}

\begin{proof}
Let $Y_{\tau_k;\tau_k}(s,a) = \gamma D_k + \rho_{\tau_k}$, where
$\rho_{\tau_k} = (1 - \gamma)D_k$. We can now write
\[
Y_{t+1;\tau_k}(s,a) = (1- \alpha_t)Y_{t;\tau_k}(s,a) + \alpha_t
\gamma D_k = \gamma D_k + (1 -\alpha_t)\rho_t,
\]
where $\rho_{t+1} = \rho_t(1- \alpha_t)$. We would like show that
after time $ (2+\psi)\tau_k =\tau_{k+1}$ for any $ t \geq
\tau_{k+1}$ we have $\rho_t \leq \beta D_k$. By definition we can
rewrite $\rho_t$ as,
$$
\rho_t = (1- \gamma ) D_k\prod_{l=1}^{t-\tau_k}(1-\alpha_{l+\tau_k}) =
2\beta D_k\prod_{l=1}^{t-\tau_k}(1-\alpha_{l+\tau_k})
= 2\beta D_k\prod_{l=1}^{t-\tau_k} (1-\frac{1}{l+\tau_k}),
$$
where the last identity follows from the fact that $\alpha_t = 1/ t$.
Simplifying the expression, and setting $t=(2+\psi)\tau_k$, we have
$$
\rho_t \leq 2D_{k}\beta\frac{\tau_k}{t}
= \frac{2D_k\beta}{2+\psi}$$
Hence, $Y_{t;\tau_k}(s,a) \leq (\gamma + \frac{2}{2 + \psi}\beta) D_k$.
\end{proof}

The following lemma enables the use of Azuma's inequality.
\begin{lemma}
\label{lem-help_azu-lin}For any $t \geq \tau_k$ and $1 \leq l \leq
t$ we have that $W_{t;\tau_k}^l(s,a)$ is a martingale sequence,
which satisfies
$$
|W_{t;\tau_k}^l(s,a) - W_{t;\tau_k}^{l-1}(s,a)| \leq
\frac{V_{max}}{t}
$$
\end{lemma}
\begin{proof}
We first note that $W_{t;\tau_k}^l(s,a)$ is a martingale sequence,
since \begin{eqnarray*} E[W_{t;\tau_k}^l(s,a) -
W_{t;\tau_k}^{l-1}(s,a)|F_{\tau_k+l - 1} ] & = &
E[\eta_{\tau_k+l}^{k,t}(s,a)w_{\tau_k + l}(s,a)|F_{\tau_k+l - 1}
]\\ & = & \eta_{\tau_k+l}^{k,t} E[w_{\tau_k + l}(s,a)|F_{\tau_k+l
- 1} ]= 0.\end{eqnarray*} For linear learning rate we have that
$\eta_{l + \tau_k}^{k,t}(s,a)= 1/ t$, thus
$$|W_{t;\tau_k}^l(s,a) - W_{t;\tau_k}^{l-1}(s,a)| =
\frac{w_{\tau_k + l}(s,a)}{t} \leq \frac{V_{max}}{t}.$$
\end{proof}


The following Lemma provides a bound for the stochastic term $W_{t;\tau_k}$.
\begin{lemma}
\label{lem:l1} Consider synchronous Q-learning with a linear
learning rate. With probability at least $1 - \frac{\delta}{m}$,
we have $|W_{t;\tau_k}| \leq  \frac{\psi}{2+\psi}\beta D_k$ for
any $t \in [\tau_{k+1},\tau_{k+2}]$ and any positive constant
$\psi$, i.e.
$$
Pr\left[\forall t \in [\tau_{k+1}, \tau_{k+2}]: \;\;
 W_{t;\tau_k} \leq \frac{\psi}{2 + \psi}\beta D_k\right]
\geq 1 - \frac{\delta}{m}
$$
given that
$\tau_k = \Theta(\frac {V_{max}^2\ln(V_{max} |S|\; |A| m/(\psi\delta\beta D_k))}
{\psi^2\beta^2 D_k^2})$
\end{lemma}


\begin{proof}
By Lemma \ref{lem-help_azu-lin} for any $t \geq \tau_{k+1}$ we can
apply Azuma's inequality to $W_{t;\tau_k}^{t - \tau_k + 1}$ with
$c_i = \frac{V_{max}}{i + \tau_k}$ (note that $W_{t;\tau_k}^{t -
\tau_k + 1} = W_{t;\tau_k}$). Therefore, we derive that
$$
Pr[|W_{t;\tau_k}| \geq \tilde{\epsilon} \;|\; t \geq \tau_{k+1}] \leq
2e^{\frac{-2 \tilde{\epsilon}^2}{\sum_{i=\tau_k}^{t}c_i^2}} =
2e^{-c\frac{t^2\tilde{\epsilon}^2}{(t - \tau_k)V_{max}^2 }} \leq
2e^{-c\frac{t\tilde{\epsilon}^2}{V_{max}^2 }}
$$
for some positive constant $c$.
Using the union bound we get
\begin{eqnarray*}
Pr\left[\forall t \in [\tau_{k+1}, \tau_{k+2}]:\;|W_{t;\tau_k}| \geq \tilde{\epsilon}\right]
& \leq & Pr\left[\forall t \geq (2+\psi)\tau_k:\;|W_{t;\tau_k}| \geq \tilde{\epsilon}\right] \\
& \leq & \sum_{t=(2+\psi)\tau_k}^{\infty}Pr\left[|W_{t;\tau_k}| \geq \tilde{\epsilon}\right]\\
& \leq & \sum_{t=(2+\psi)\tau_k}^{\infty} 2e^{-c\frac{t \tilde{\epsilon}^2}{V_{max}^2 }}
=  2e^{-c\frac{((2+\psi)\tau_k)\tilde{\epsilon}^2}{V_{max}^2}}
\sum_{t = 0}^{\infty}e^{-\frac{t\tilde{\epsilon}}{V_{max}^2}}\\
& = &\frac{2e^{-c\frac{(2+\psi)\tau_k\tilde{\epsilon}^2}{V_{max}^2}}} {1 - e^{\frac{-\tilde{\epsilon}^2}{V_{max}^2}}}
 =  \Theta(\frac{e^{-\frac{c'\tau_k \tilde{\epsilon}^2}{V_{max}^2}}V_{max}^2}{\tilde{\epsilon}^2}),
\end{eqnarray*}
where the last equality is due to Taylor expansion and $c'$ is
some positive constant. By setting $\frac{\delta}{m\;|S|\;|A|} =
\Theta(\frac{e^{-\frac{c'\tau_k
\tilde{\epsilon}^2}{V_{max}^2}}V_{max}^2}{\tilde{\epsilon}^2})$,
which holds for $\tau_k = \Theta(\frac {V_{max}^2\ln(V_{max} |S|\;
|A| m/(\delta\tilde{\epsilon}))} {\tilde{\epsilon}^2})$, and
$\tilde{\epsilon} = \frac{\psi}{2+\psi}\beta D_k$ assures us that
for every $t \geq \tau_{k+1}$ (and as a result for any $t \in
[\tau_{k+1},\tau_{k+2}]$) with probability at least $1 -
\frac{\delta}{m}$ the statement holds at every state-action pair.
\end{proof}

We have bounded for each iteration the time needed to achieve the desired precision level
with probability $1 - \frac{\delta}{m}$.
The following lemma provides a bound for the error in all the iterations.
\begin{lemma}
\label{lem:noise-linear-sync}
Consider synchronous Q-learning using a linear learning rate.
With probability $1 - \delta$,
for every iteration $k\in[1,m]$, time $t \in [\tau_{k+1},\tau_{k+2}]$
and any constant $\psi>0$ we have
$|W_{t;\tau_k}| \leq \frac{\psi\beta D_k}{2+\psi})$, i.e.,
$$
Pr\left[\forall k \in [1,m],\; \forall t \in [\tau_{k+1},\tau_{k+2}]: \;\;
|W_{t;\tau_k}| \leq \frac{\psi\beta D_k}{2+\psi}\right]
\geq 1 - \delta,
$$
given that
$\tau_0 = \Theta(\frac {V_{max}^2\ln(V_{max} |S|\; |A| m/(\psi\delta\beta \epsilon))}
{\psi^2\beta^2 \epsilon^2})$.
\end{lemma}

\begin{proof}
 From Lemma~\ref{lem:noise1} we know that
$$
Pr\left[\forall t \in [\tau_{k+1}, \tau_{k+2}]: \;\;
 |W_{t;\tau_k}| \geq \frac{\psi\beta D_k}{2+\psi}\right]
\leq \frac{\delta}{m}
$$
Using the union bound we have that,
\begin{eqnarray*}
\lefteqn{Pr\left[\forall k \leq m, \forall t \in [\tau_{k+1},\tau_{k+2}]:\;\;|W_{t;\tau_k}|
\geq \frac{\psi\beta D_k}{2+\psi}\right]}\\
& &\leq \sum_{k=1}^mPr\left[\forall t \in
[\tau_{k+1},\tau_{k+2}]:\;\;|W_{t;\tau_k}| \geq \frac{\psi\beta
D_k}{2+\psi}\right] \leq \delta
\end{eqnarray*}
\end{proof}

The proof of Theorem ~\ref{the:main1} follows from
Lemmas ~\ref{lem:noise-linear-sync} and  ~\ref{lem:IterSize1},~\ref{lemma:num} and the fact that
$a_{k+1} = (2+\psi)a_k =(2+\psi)^k a_1$.





\section{Asynchronous Q-learning}


The major difference between synchronous and asynchronous
Q-learning is that asynchronous Q-learning 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
Q-learning, 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 $L\log T$ 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 state-action 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.

\begin{definition}
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]$.
\end{definition}
In this section, we use the same notations as in Section
\ref{section_synchronous} for $D_k$, $\tau_k$, $Y_{t;\tau_k}$ and
$W_{t;\tau_k}$, with a different set of values for $\tau_k$. We
first give the results for asynchronous Q-learning using 
polynomial learning rate (Subsection \ref{sec:async-poly}); we give
a similar proof for linear learning rates in Subsection
\ref{app:asynch_linear}.

\subsection{Asynchronous Q-learning using a Polynomial Learning Rate}
\label{sec:async-poly}
Our main goal is to show that the size of the $k$th iteration is $L\tau_k^{\omega}$.
The covering time property guarantees
that in $L\tau_k^{\omega}$ steps each pair of state action is performed
at least $ \tau_k^{\omega}$ times.
For this reason we define for asynchronous Q-learning with
polynomial learning rate the sequence $\tau_{k+1}=\tau_k + L\tau_k^\omega$, where
$\tau_1$ will be specified later.
As in Subsection \ref{sec-sync-poly} we first bound the value of $Y_{t;\tau_k}$






\begin{lemma}
\label{lem:AsyIterSizePoly}
Consider asynchronous Q-learning with a polynomial learning rate and
assume that for any $t \geq \tau_k$ we have $Y_{t;\tau_k}(s,a) \leq D_k$.
Then for any $t \geq \tau_k + L \tau_k^{\omega}=\tau_{k+1}$ we have
$Y_{t;\tau_k} (s,a) \leq D(\gamma + \frac{2}{e}\beta) $
\end{lemma}
\begin{proof}
For each state-action pair  $(s, a)$ we are assured that $n(s,a,\tau_{k},\tau_{k+1}) \geq \tau_{k}^{\omega}$
, since the covering time is $L$ and the underlying policy has made $L\tau_k^{\omega}$ steps.
Using the fact that the $Y_{t;\tau_k} (s,a)$ are monotonically decreasing and deterministic,
we can apply the  same argument as in the proof of Lemma ~\ref{lem:IterSizew}.
\end{proof}


The next Lemma bounds the influence of each sample $w_t(s,a)$ on
$W_{t;\tau_k}(s,a)$.
\begin{lemma}
\label{lem:async-noise-help} Let $\tilde{w}_{i + \tau_k}^t(s,a) =
\eta_i^{k,t}(s,a) w_{i + \tau_k}(s,a)$ then for any $t \in
[\tau_{k+1},\tau_{k+2}]$ the random variable $\tilde{w}_{i +
\tau_k}^t(s,a)$ has zero mean and bounded by $(L/\tau_k)^\omega
V_{max}$.
\end{lemma}
\begin{proof}
Note that by definition
$w_{\tau_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 $\tau$, by definition of the covering time,
each state-action pair is performed at least $\tau/L$ times;
therefore, $\eta^{k,t}_i (s,a) \leq (L/\tau_k)^\omega$.
Looking at the expectation of $\tilde{w}_{i + \tau_k}(s,a)$ we observe that
$$
E[\tilde{w}_{i + \tau_k}^t(s,a)] = E[\eta_i^{k,t}(s,a) w_{i +
\tau_k}(s,a)] = \eta_i^{k,t}(s,a)E[w_{i + \tau_k}(s,a)] =  0
$$
Next we prove that it is bounded as well:
\begin{eqnarray*}
|\tilde{w}^t_{i + \tau_k}(s,a)| & = &|\eta_i^{k,t}(s,a) w_{i + \tau_k}(s,a)| \\
& \leq & |\eta_i^{k,t}(s,a)| V_{max}\\
& \leq & (L/\tau_k)^\omega V_{max}
\end{eqnarray*}

\end{proof}

Next we define $W_{t;\tau_k}^l(s,a) = \sum_{i = 1}^l
\tilde{w}^t_{i + \tau_k}(s,a)$ and prove that it is martingale
sequence with bounded differences.
\begin{lemma}
\label{azum-help-asyn-poly} For any $t \in
[\tau_{k+1},\tau_{k+2}]$ and $1 \leq l \leq t$ we have that
$W_{t;\tau_k}^l(s,a)$ is a martingale sequence, which satisfies
$$
|W_{t;\tau_k}^l(s,a) - W_{t;\tau_k}^{l-1}(s,a)| \leq
(L/\tau_k)^\omega V_{max}
$$
\end{lemma}
\begin{proof}
We first note that $W_{t;\tau_k}^l(s,a)$ is a martingale sequence,
since \begin{eqnarray*}E[W_{t;\tau_k}^l(s,a) -
W_{t;\tau_k}^{l-1}(s,a)|F_{\tau_k+l - 1} ] & = & E[\tilde{w}_{l +
\tau_k}^t(s,a)|F_{\tau_k+l - 1} ] = 0.\end{eqnarray*} By Lemma
\ref{lem:async-noise-help} we have that $\tilde{w}^t_{l +
\tau_k}(s,a)$ is bounded by $(L/\tau_k)^\omega V_{max}$, thus
$$|W_{t;\tau_k}^l(s,a) - W_{t;\tau_k}^{l-1}(s,a)| = \tilde{w}^t_{l +
\tau_k}(s,a) \leq (L/\tau_k)^\omega V_{max}.$$
\end{proof}
  The following Lemma bounds the value of the term $W_{t;\tau_k}$.

\begin{lemma}
\label{lem:asynch_noise_poly}
Consider asynchronous Q-learning with a polynomial learning rate.
With probability at least $1 - \frac{\delta}{m}$ we have for every
state-action pair $|W_{t;\tau_k}(s,a)| \leq (1 - \frac{2}{e})\beta D_k$
for any $t \in [\tau_{k+1},\tau_{k+2}]$, i.e.
$$
Pr\left[\forall s,a \;\forall t \in [\tau_{k+1}, \tau_{k+2}]: \;\; |W_{t;\tau_k}(s,a)| \leq
(1 - \frac{2}{e})\beta D_k \right]
\geq 1 - \frac{\delta}{m}
$$
given that $\tau_k = \Theta((\frac {L^{1 + 3\omega}
V_{max}^2\ln(V_{max} |S|\; |A| m/(\delta\beta
D_k))}{\beta^2D_k^2})^{1/\omega})$.
\end{lemma}
\begin{proof}
For each state-action pair we look on $W_{t;\tau_k}^l(s,a)$ and
note that $W_{t;\tau_k}(s,a) = W_{t;\tau_k}^{t - \tau_k +
1}(s,a)$. Let $\ell=n(s,a,\tau_k,t)$, then for any $t \in
[\tau_{k+1}, \tau_{k+2}]$ we have that $\ell \leq \tau_{k+2} -
\tau_k \leq \Theta(L^{1 + \omega}\tau_k^\omega)$. By Lemma
\ref{azum-help-asyn-poly} we can apply Azuma's inequality to
$W_{t;\tau_k}^{t - \tau_k + 1}(s,a)$ with $c_i = (L/\tau_k)^\omega
V_{max}$. Therefore, we derive that
\begin{eqnarray*}
Pr[|W_{t;\tau_k}(s,a) | \geq \tilde{\epsilon} \; | \; t \in
[\tau_{k+1},\tau_{k+2}]] & \leq & 2e^{\frac{-
\tilde{\epsilon}^2}{2\sum_{i = \tau_k + 1, i \in
T^{s,a}}^{t}c_i^2}}
 \leq 2e^{-c\frac{\tilde{\epsilon}^2\tau_k^{2\omega}}{\ell V_{max}^2L^{2\omega} }}
\\ & \leq & 2e^{-c\frac{\tilde{\epsilon}^2\tau_k^{\omega}}{
L^{1+3\omega}V_{max}^2}},
\end{eqnarray*}
for some constant $c>0$. We can set $\tilde{\delta}_k =
2e^{-c\tau_k^{\omega}\tilde{\epsilon}^2/(L^{1+
3\omega}V^2_{max})}$, which holds for $\tau^\omega_k =
\Theta(\ln(1/\tilde{\delta_k})L^{1 +
3\omega}V_{max}^2/\tilde{\epsilon}^2)$.
%
Using the union bound we have
$$Pr\left[\forall t \in [\tau_{k+1},\tau_{k+2}] :\;W_{t;\tau_k}(s,a) \leq \tilde{\epsilon}\right]
\leq \sum_{t=\tau_{k+1}}^{\tau_{k+2}} Pr\left[W_{t;\tau_k}(s,a)
\leq \tilde{\epsilon} \right],$$ thus taking $\tilde{\delta}_k =
\frac{\delta}{m (\tau_{k+2} - \tau_{k+1}) |S||A|}$ assures
a certainty level of $1 - \frac{\delta}{m}$ for each state-action
pair. As a result we have
\[
\tau^\omega_k  = \Theta(\frac{L^{1+3\omega}V_{max}^2\ln (|S| \;
|A| \; m \tau_k^\omega /\delta)} {\tilde{\epsilon}^2} )
 =
\Theta(\frac{L^{1+3\omega} V_{max}^2\ln (|S| \; |A| \; m
V_{max}/(\delta\tilde{\epsilon}))} {\tilde{\epsilon}^2} )
\]
Setting $\tilde{\epsilon}=(1-2/e)\beta D_k$ give the desired bound.
\end{proof}
We have bounded for each iteration the time needed to achieve the
desired precision level with probability $1 - \frac{\delta}{m}$.
The following lemma provides a bound for the error in all the
iterations.

\begin{lemma}
\label{lem:total-noise-poly-async}
Consider asynchronous Q-learning using a polynomial learning rate.
With probability $1 - \delta$,
for every iteration $k\in[1,m]$ and time $t \in [\tau_{k+1},\tau_{k+2}]$ we have
$|W_{t;\tau_k}(s,a)| \leq (1 - \frac{2}{e})\beta D_k$, i.e.,
$$
Pr\left[\forall k \in [1,m],\; \forall t \in [\tau_{k+1},\tau_{k+2}],\; \forall s,a: \;\;
|W_{t;\tau_k}(s,a)| \leq (1 - \frac{2}{e})\beta D_k\right]
\geq 1 - \delta,
$$
given that $\tau_0 = \Theta((\frac {L^{1 +
3\omega}V_{max}^2\ln(V_{max} |S|\; |A| m/(\delta\beta \epsilon))}
{\beta^2\epsilon^2})^{1/\omega})$.
\end{lemma}

\begin{proof}
 From Lemma~\ref{lem:asynch_noise_poly} we know that
 $$
Pr\left[\forall t \in [\tau_{k+1}, \tau_{k+2}]: \;\;
 |W_{t;\tau_k}| \geq (1 - \frac{2}{e})\beta D_k\right]
\leq \frac{\delta}{m}
$$
%$$Pr\left[\forall t \in [\tau_{k+1},\tau_{k+2}]\;\;W_{t;\tau_k} \geq (1 - \frac{2}{e})\beta D_k\right] = Pr\left[\forall t \in [\tau_{k+1},\tau_{k+2}] \;\;\sum_{i=\tau_{k}}^t w_{i}\eta_i^{k,t} \geq \tilde{\epsilon} \right] \leq \frac{\delta}{m}$$
Using the union bound we have that
\begin{eqnarray*}
Pr\left[\forall k \leq m, \forall t \in
[\tau_{k+1},\tau_{k+2}]\;\;|W_{t;\tau_k}| \geq
\tilde{\epsilon}\right] & \leq & \sum_{k=1}^mPr\left[\forall t \in
[\tau_{k+1},\tau_{k+2}]\;\;|W_{t;\tau_k}| \geq
\tilde{\epsilon}\right] \leq  \delta,
\end{eqnarray*}
where $\tilde{\epsilon} = (1 - \frac{2}{e})\beta D_k$
\end{proof}





%We have shown that we can also apply the results into asynchronous algorithm too.
The following lemma solves the recurrence $\sum_{i=0}^{m-1}
L\tau_i^{\omega} + \tau_0$ and derives the time complexity.

\begin{lemma}
\label{lem:asynch_series_poly}
Let
$$a_{k+1} = a_k+La_k^\omega= a_0+\sum_{i=0}^{k}La_i^{\omega} $$
Then for any constant $\omega \in (0,1)$, $a_k = O((a_0^{1-
\omega}+Lk)^{\frac{1}{1 - \omega}}) = O(a_0 + (LK)^{\frac{1}{1 -
\omega}})).$
\end{lemma}
\begin{proof}
We define the following series
$$b_{k+1} = \sum_{i=0}^{k}Lb_{i}^{\omega} + b_0$$
with an initial condition
$$b_{0} = L^{\frac{1}{1 - \omega}}.$$
We show by induction that $b_k \leq (L(k+1))^{\frac{1}{1 - \omega}}$
for $k \geq 1$. For $k = 0$
$$
b_0 =L^{\frac{1}{1 - \omega}}(0 + 1)^{\frac{1}{1 - \omega}} \leq L^{\frac{1}{1 - \omega}}
$$
We assume that the induction hypothesis holds for $k-1$ and prove it for $k$,
$$b_k = b_{k-1} + Lb_{k-1}^{\omega} \leq (Lk)^{\frac{1}{1 - \omega}} + L(Lk)^{\frac{\omega}{1 - \omega}}
\leq L^{\frac{1}{1 - \omega}}k^{\frac{\omega}{1 - \omega}}(k+1) \leq (L(k+1))^{\frac{1}{1-\omega}}$$
and the claim is proved.

%We define $s = 2^{\frac{1}{1 - \omega}}$
Now we lower bound $b_k$ by $(L(k+1)/2)^{1/(1-\omega)}$. For $k = 0$
$$
b_0 = L^{\frac{1}{1 - \omega}}  \geq (\frac{L}{2})^{\frac{1}{1-\omega}}
$$
Assume that the induction hypothesis holds for  $k-1$ and prove for $k$,
\begin{eqnarray*}
b_k & = & b_{k-1} + Lb_{k-1}^{\omega} =
(Lk/2)^{\frac{1}{1-\omega}} + L(Lk/2)^{\frac{\omega}{1-\omega}} =
L^{\frac{1}{1 - \omega}} ((k/2)^{\frac{1}{1-\omega}} +
(k/2)^{\frac{\omega}{1-\omega}})\\ & \geq & L^{\frac{1}{1 -
\omega}}((k+1)/2)^{\frac{1}{1-\omega}}.
\end{eqnarray*}
%(the last inequality is true $\forall k > 1$).

For $a_0 > L^{\frac{1}{1 - \omega}}$ we can view the series as
starting at $b_k=a_0$. From the lower bound we know that the start
point has moved $\Theta(a_0^{1 - \omega} / L)$. Therefore we have
a total complexity of $O((a_0^{1-\omega}+Lk)^{\frac{1}{1-\omega}})
= O(a_0 + (LK)^{\frac{1}{1 - \omega}})).$
%Otherwise, we have a total complexity of $O((Lk)^{\frac{1}{1-\omega}})$.
%\qed

\end{proof}
The proof of Theorem~\ref{the:mainw} follows from
Lemmas~\ref{lem:AsyIterSizePoly},~\ref{lem:total-noise-poly-async},\ref{lemma:num} and~\ref{lem:asynch_series_poly}.
%
In the following lemma we relax the condition of the covering time.


\begin{lemma}
\label{lem-prob-cover}
Assume that from any start state
with probability $1/2$ in $L$ steps we perform all state action pairs.
Then with probability $1-\delta$, from any start state we perform all state action pairs
in $L\log_2 (1/\delta)$ steps, for a run of length $[L\log_2 (1/\delta)]$.
\end{lemma}
\begin{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/\delta)]$ we get that the probability of failing is
$\delta$.
\end{proof}

\begin{corollary}
Assume that from any start state
with probability $1/2$ in $L$ steps we perform all state action pairs.
Then with probability $1-\delta$, from any start state we perform all state action pairs
in $L\log (T/\delta)$ steps, for a run of length $T$.
\end{corollary}


\subsection{Asynchronous Q-learning using a Linear Learning Rate}
\label{app:asynch_linear}

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

\begin{lemma}
\label{lem:AsyncIterSize_linear}
Consider asynchronous Q-learning with a polynomial learning rate and
assume that for any $t \geq \tau_k$ we have $Y_{t;\tau_k}(s,a) \leq D_k$.
Then for any $t \geq \tau_k +  (1+\psi)L\tau_k=\tau_{k+1}$ we have
$Y_{t;\tau_k} (s,a) \leq (\gamma + \frac{2}{2+\psi}\beta) D_k $
\end{lemma}
\begin{proof}
For each state-action pair $(s,a)$ we are assured that
$n(s,a,\tau_{k},\tau_{k+1}) \geq (1+\psi)\tau_{k}$ , since in an
interval of  $(1+\psi)L\tau_k$ steps each state-action pair is
visited at least $(1+\psi)\tau_k$ times by the definition of the
covering time. Using the fact that the $Y_{t;\tau_k} (s,a)$ are
monotonically decreasing and deterministic (thus independent), we
can apply the same argument as in the proof of Lemma
~\ref{lem:IterSize1}.
\end{proof}

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

\begin{lemma}
\label{lem:azum-help-asyn-lin} For any $t \geq \tau_k$ and $1 \leq
l \leq t$ we have that $W_{t;\tau_k}^l(s,a)$ is a martingale
sequence, which satisfies
$$
|W_{t;\tau_k}^l(s,a) - W_{t;\tau_k}^{l-1}(s,a)| \leq
\frac{V_{max}}{n(s,a,0,t)}
$$
\end{lemma}
\begin{proof}
We first note that $W_{t;\tau_k}^l(s,a)$ is a martingale sequence,
since \begin{eqnarray*}E[W_{t;\tau_k}^l(s,a) -
W_{t;\tau_k}^{l-1}(s,a)|F_{\tau_k+l - 1}] & = & E[\eta_{\tau_k +
l}^{k,t}(s,a)w_{\tau_k + l}(s,a)|F_{\tau_k+l - 1}]\\ & = &
\eta_{\tau_k + l}^{k,t}E[w_{\tau_k + l}(s,a)|F_{\tau_k+l - 1} ]=
0.\end{eqnarray*} For a linear learning rate we have that
$\eta_{\tau_k + l}^{k,t}(s,a)= 1/ n(s,a,0,t)$, thus
$$|W_{t;\tau_k}^l(s,a) - W_{t;\tau_k}^{l-1}(s,a)| =
\eta_{\tau_k + l}^{k,t}(s,a) |w_{\tau_k + l}(s,a)| \leq
\frac{V_{max}}{n(s,a,0,t)}.$$
\end{proof}


The following lemma bounds the value of the term $W_{t;\tau_k}$.

\begin{lemma}
\label{lem:asyncnoise2}
Consider asynchronous Q-learning with a linear learning rate.
With probability at least $1 - \frac{\delta}{m}$ we have for every
state-action pair $|W_{t;\tau_k}(s,a)| \leq \frac{\psi}{2+\psi}\beta D_k$
for any $t \geq \tau_{k+1}$  and any positive constant $\psi$, i.e.
$$
Pr\left[\forall t \in [\tau_{k+1},\tau_{k+1}]: \;\; W_{t;\tau_k}(s,a) \leq \frac{\psi}{2+\psi}\beta D_k\right]
\geq 1 - \frac{\delta}{m}
$$
given that
$\tau_k \geq \Theta((\frac {V_{max}^2\ln(V_{max} |S|\; |A| m/(\delta\beta D_k\psi))}{\psi^2\beta^2D_k^2}))$.
\end{lemma}
\begin{proof}
By Lemma \ref{lem:azum-help-asyn-lin} we can apply Azuma's
inequality on $W_{t;\tau_k}^{t - \tau_k +1}$ (We note that
$W_{t;\tau_k}^{t - \tau_k + 1} =  W_{t;\tau_k})$ with $c_i =
\Theta(\frac{V_{max}}{n(s,a,0,t})$ for any $t \geq \tau_{k+1}$.
Therefore, we derive that
\begin{eqnarray*}
Pr[|W_{t;\tau_k}| \geq \tilde{\epsilon}] & \leq &
2e^{\frac{-2 \tilde{\epsilon}^2}{\sum_{i=\tau_k, i \in T^{s,a}}^{t}c_i^2}}
\leq 2e^{-c\frac{n(s,a,\tau_k,t)\tilde{\epsilon}^2}{V_{max}^2 }},
\end{eqnarray*}
for some positive constant $c$.
Let us define the following variable

\[ \zeta_t(s,a) =
   \left\{ \begin{array}{l}
       1,\;\; \alpha_t(s,a) \neq 0\\
       0,\;\; \mbox{otherwise} \end{array}\right. \]


Using the union bound  and the fact in an interval of length $(1+\psi)L\tau_k$ each state-action pair
is visited at least $(1+\psi)\tau_k$ times, we get
\begin{eqnarray*}
Pr\left[\forall t \in [\tau_{k+1}, \tau_{k+2}]:\;|W_{t;\tau_k}(s,a)| \geq \tilde{\epsilon}\right]
& \leq &Pr\left[\forall t \geq ((1+\psi)L+1)\tau_k:\;|W_{t;\tau_k}(s,a)| \geq \tilde{\epsilon}\right]\\
& \leq & \sum_{t=((1+\psi)L+1)\tau_k}^{\infty}Pr\left[|W_{t;\tau_k}(s,a)| \geq \tilde{\epsilon}\right]\\
& \leq & \sum_{t=((1+\psi)L+1)\tau_k}^{\infty}\zeta_t(s,a) 2e^{-c\frac{n(s,a,0,t)\tilde{\epsilon}^2}{V_{max}^2 }}\\
& \leq &  2e^{-c\frac{((1+\psi)\tau_k)\tilde{\epsilon}^2}{V_{max}^2}}\sum_{t = 0}^{\infty}e^{-\frac{t\tilde{\epsilon}^2}{2V_{max}^2}}\\
& = &\frac{2e^{-c\frac{(1+\psi)\tau_k\tilde{\epsilon}^2}{V_{max}^2}}} {1 - e^{\frac{-\tilde{\epsilon}^2}{V_{max}^2}}}
 =  \Theta(\frac{e^{-\frac{c'\tau_k
 \tilde{\epsilon}^2}{V_{max}^2}}V_{max}^2}{\tilde{\epsilon}^2}),
\end{eqnarray*}
for some positive constant $c'$. Setting
$\frac{\delta}{m\;|S|\;|A|} = \Theta(\frac{e^{-\frac{c'\tau_k
\tilde{\epsilon}^2}{V_{max}^2}}V_{max}^2}{\tilde{\epsilon}^2}) $,
which hold for $\tau_k = \Theta(\frac {V_{max}^2\ln(V_{max} |S|\;
|A| m/(\delta\tilde{\epsilon}))} {\tilde{\epsilon}^2})$, and
$\tilde{\epsilon} = \frac{\psi}{2+\psi}\beta D_k$ assures us that
for every $t \geq \tau_{k+1}$ (and as a result for any $t \in
[\tau_{k+1},\tau_{k+2}]$) with probability at least $1 -
\frac{\delta}{m}$ the statement holds at every state-action pair.

\end{proof}

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

\begin{lemma}
\label{lem:noise-linear-async}
Consider synchronous Q-learning using a linear learning rate.
With probability $1 - \delta$,
for every iteration $k\in[1,m]$, time $t \in [\tau_{k+1},\tau_{k+2}]$
and any constant $\psi > 0$ we have
$|W_{t;\tau_k}| \leq \frac{\psi \beta D_k}{2+\psi} $, i.e.,
$$
Pr\left[\forall k \in [1,m],\; \forall t \in [\tau_{k+1},\tau_{k+2}]: \;\;
|W_{t;\tau_k}| \leq \frac{\psi \beta D_k}{2+\psi}\right]
\geq 1 - \delta,
$$
given that
$\tau_0 = \Theta(\frac {V_{max}^2\ln(V_{max} |S|\; |A| m/(\delta\beta \epsilon\psi))}
{\psi^2\beta^2 \epsilon^2})$.
\end{lemma}

\begin{proof}
 From Lemma~\ref{lem:asyncnoise2} we know that
\begin{eqnarray*}
Pr\left[\forall t \in [\tau_{k+1}, \tau_{k+2}]: \;\;
 |W_{t;\tau_k}| \geq \frac{\psi \beta D_k}{2 + \psi}\right] \leq \frac{\delta}{m}
\end{eqnarray*}

Using the union bound we have that,
\begin{eqnarray*}
\lefteqn{Pr\left[\forall k \leq m, \forall t \in [\tau_{k+1},\tau_{k+2}]\;\;|W_{t;\tau_k}| \geq \frac{\psi \beta D_k}{2 + \psi}\right]}\\
& & \leq \sum_{k=1}^mPr\left[\forall t \in
[\tau_{k+1},\tau_{k+2}]\;\;|W_{t;\tau_k}| \geq \frac{\psi \beta
D_k}{2 + \psi}\right] \leq \delta
\end{eqnarray*}
\end{proof}


Theorem~\ref{the:main1} follows from Lemmas~\ref{lem:AsyncIterSize_linear},
\ref{lem:noise-linear-async}, \ref{lemma:num} and the fact that
$a_{k+1}=a_k+(1+\psi)La_k=a_0((1+\psi)L+1)^k$.


\section{Lower Bound for Q-learning using a Linear Learning Rate}
\label{app:lower}

In this section we show a lower bound for Q-learning
with a linear learning rate, which is $O((\frac{1}{\epsilon})^{\frac{1}{1-\gamma}})$.
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) \leq \epsilon$.

\begin{lemma}
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}{\epsilon})^{\frac{1}{1- \gamma}}$ for some
constant $c > 0$, such that $Q_t \geq \epsilon$.
\end{lemma}

\begin{proof}
First we prove by induction on $t$ that
$$
Q_t(s) = \prod_{i=1}^{t-1}\frac{i + \gamma}{i + 1} .
$$
For $t =1$ we have
$Q_1 (s) = (1 - 1/2) Q_0(s) + (1/2)\gamma Q_0(s)  = (1+\gamma)/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} \gamma Q_{t-1}(s)
= \frac{t-1 + \gamma}{t} Q_{t-1}(s).
$$

In order to help us estimate this quantity we use the $\Gamma$ function.
Let
$$
\Gamma(x+1,k) = \frac{1 \cdot 2 \cdots  k}{(x+1) \cdot (x+2) \cdots \cdot (x+k)}k^x
$$
The limit of $\Gamma(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}{\Gamma(\gamma+1,t)} \frac{t^\gamma}{t+1}
%= O({t^\gamma}) \frac{1}{t+1}
= \Theta(t^{\gamma - 1})
$$

Therefore, there is a time
$ t= c(\frac{1}{\epsilon})^{\frac{1}{1- \gamma}}$, for some constant $c>0$,
such that $Q_t(s) \geq \epsilon$.
\end{proof}

%Therefore, we have shown an example in which the convergence rate of
% Q-learning is asymptotically $\Omega(\frac{1}{\epsilon}^{\frac{1}{1- \gamma}})$,
% thus proving Theorem ~\ref{the:lower}.




\remove{
\section{General Lower Bound for Q-learning}

We show a general $
\Omega(\frac{1}{\epsilon^2}\ln(\frac{1}{\delta}))$ lower bound for
estimating the Q function, not necessarily using Q-learning, on
the number of steps required to get an accuracy of $\epsilon$ with
probability $1 - \delta$. The lower bound is identical in spirit
to the one of PAC learning. We use here the following Lemma from
~\cite{anthony99neural}


\begin{lemma}
\label{lem:alpha} Suppose that $\alpha$ is a random variable
uniformly distributed on ${\alpha\_ , \alpha_+}$, where $\alpha\_
= \frac{1}{2} - \frac{\epsilon}{2}$ and $\alpha_+ = \frac{1}{2} +
\frac{\epsilon}{2}$, with $0 < \epsilon < 1$. Suppose that
$\xi_1,...,\xi_m$ are $i.i.d$ (independent and identically
distributed) $\{0,1\}$-valued random variables with $Pr(\xi_i = 1)
= \alpha$ for all $i$.  Let $f$ be function from $\{0,1\}^m$ to
${\alpha\_ , \alpha_+}$. Then $Pr(f(\xi_1,...,\xi_m) \neq \alpha)
> \frac{1}{4}(1 - (\sqrt{1 - \exp(\frac{-2[m/2]\epsilon^2}{1 -
\epsilon^2})} ))$ Hence, if this probability is no more than
$\delta$, where $0 < \delta < \frac{1}{4}$, then
$$ m \geq 2[\frac{1-\epsilon^2}{2\epsilon^2}\ln(\frac{1}{ 8 \delta (1- 2\delta) } )].$$
\end{lemma}

We consider the following MDP, denoted $M_1$ that has one state
$s$ and one action $a$ and the reward is one with probability $p$
and zero with probability $1 - p$. Let $g(\xi_1,...\xi_m)$ be
function that calculates the estimated return value of action $a$
where $\xi_i$ are the ones defined in Lemma~\ref{lem:alpha} We
will have the following Lemma.
\begin{lemma}
\label{lem:est} Consider MDP,$M_1$, where $g(\xi_1,...\xi_m)$
tries to estimate $R_M^a(s)$.
\\Then $|g(\xi_1,...\xi_m) - R_M^a(s)| \leq \frac{\epsilon}{2}$
with probability at least$1 - \delta$
only if $m \geq 2[\frac{1-\epsilon^2}{2\epsilon^2}\ln(\frac{1}{ 8 \delta (1- 2\delta) } )] $

\end{lemma}
\begin{proof}
Let us look at the problem of deciding if the reward is $\alpha =
\{\alpha\_ ,\alpha_+\}$, which are the only possible values( as
introduced in the former Lemma). Now assume that we have a
function $g(\xi_1,...\xi_m)$ that has a precision level of
$\frac{\epsilon}{2}$ with probability at least $1 - \delta$ for $m
<  2[\frac{1-\epsilon^2}{2\epsilon^2}\ln(\frac{1}{ 8 \delta (1-
2\delta) } )]$ . Then we can make the following decision rule:
\[ f(\xi_1,...,\xi_m) =
   \left\{ \begin{array}{l}
       \alpha_+,\;\; g(\xi_1,...,\xi_m) \geq \frac{1}{2}\\
       \alpha_{-},\;\; g(\xi_1,...,\xi_m) < \frac{1}{2} \end{array}\right. \]
\remove{
\begin{eqnarray*}
f(\xi_1,...,\xi_m) & = & \alpha_+    g(\xi_1,...,\xi_m) \geq \frac{1}{2}
\\ f(\xi_1,...,\xi_m) & = & \alpha_{-}    g(\xi_1,...,\xi_m) < \frac{1}{2}
\end{eqnarray*}
} Without loss of generality assume $\alpha = \alpha_+$ where
$\alpha_+ = \frac{1}{2} + \frac{\epsilon}{2}$, then with
probability $1 - \delta$ $g(\xi_1,...,\xi_m) \geq \frac{1}{2}$
(since the precision level is $\frac{\epsilon}{2}$) then with
probability at least $1 - \delta$ the decision rule succeeds. This
is contradiction to Lemma ~\ref{lem:alpha}. Therefore, we conclude
the number of samples should be larger than
$2[\frac{1-\epsilon^2}{2\epsilon^2}\ln(\frac{1}{ 8 \delta (1-
2\delta) } )] $.
\end{proof}
 From Lemma~\ref{lem:est} we conclude that the number of samples needed to have precision level of $\epsilon$ with probability at least $1 - \delta$ is at least
$\Theta(\frac{1}{\epsilon^2}\ln(\frac{1}{\delta}))$. Therefore, we
derive the proof of Theorem ~\ref{the:lowergen} from Lemma
~\ref{lem:est}. }

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


\bibliographystyle{natbib}
\bibliography{rein}        % rein.bib is the name of our database

\end{document}
