% This file was updated slightly by Andrew Moore for ICML-2006
% This file was updated slightly by Kristian Kersting for ICML-2005
% from the file made available from the ICML-2004 web site.

% This file was updated by Dale Schuurmans and Jennifer Dy for ICML-2004
% from a file modifed slightly by Terran Lane for to support/document
% the new option to the ``usepackage'' statement that selects between the
% review and final version of the paper.

% This file was updated slightly by Tom Fawcett for ICML-2003
% from the file made available from the ICML-2002 web site.

% This file was modified by Claude Sammut for ICML-2002 from the file
% made available by Pat Langley, Claude-Nicolas Fiechter, Mehmet Goker,
% Cynthia Thompson and Andrea Danyluck for ICML-2K and ICLML-2001.

% Use the following line _only_ if you're still using LaTeX 2.09.
%\documentstyle[icml2006,epsf,mlapa]{article}
% If you rely on Latex2e packages, replace the above line with:
\documentclass{article}
% Use the following version of the ``usepackage'' statement for
% submitting the draft version of the paper for review.  This will set
% the note in the first column to ``Under review.  Do not distribute.''
%\usepackage{icml2006}
% Use this version of the ``usepackage'' statement after the paper has
% been accepted, when creating the final version.  This will set the
% note in the first column to ``Appearing in''
\usepackage[accepted]{icml2006}
\usepackage{epsf}
\usepackage{mlapa}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{mathrsfs}

\newcommand{\namecite}[1]{\aunpcite{#1}~\yrcite{#1}}
\newcommand{\naive}{na\"{\i}ve}
\newcommand{\rmax}{R_{\rm max}}
\newcommand{\smax}{s_{\rm max}}
\newcommand{\vmax}{v_{\rm max}}
\newcommand{\rmin}{R_{\rm min}}
\newcommand{\argmax}{\mathop{\rm argmax}}
\newcommand{\argmin}{\mathop{\rm argmin}}

\newenvironment{proof}{{\bf Proof:}}{$\Box$}
\newenvironment{proofsketch}{{\bf Proof sketch:}}{$\Box$}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}

% The \icmltitle is too long. Therefore, a short form for the running title
% is supplied just before \begin{document}
\icmltitlerunning{PAC Model-Free Reinforcement Learning}

\begin{document}

\twocolumn[
\icmltitle{PAC Model-Free Reinforcement Learning}

\icmlauthor{Alexander L. Strehl}{strehl@cs.rutgers.edu}
\icmlauthor{Lihong Li}{lihong@cs.rutgers.edu}
\icmladdress{ Department of Computer Science, Rutgers University,
Piscataway, NJ 08854 USA}
\icmlauthor{Eric Wiewiora}{ewiewior@cs.ucsd.edu}
\icmladdress{ Computer Science and Engineering Department
University of California, San Diego}
\icmlauthor{John Langford}{jl@hunch.net}
\icmladdress{ TTI-Chicago, 1427 E 60th Street, Chicago, IL 60637 USA}
\icmlauthor{Michael L. Littman}{mlittman@cs.rutgers.edu}
\icmladdress{ Department of Computer Science, Rutgers University,
Piscataway, NJ 08854 USA}
\vskip 0.3in
]

\begin{abstract}
For a Markov Decision Process with finite state (size $S$) and
action spaces (size $A$ per state), we propose a new
algorithm---Delayed Q-Learning.   We prove it is PAC, achieving near optimal
performance
except for $\tilde{O}(S A)$ timesteps using $O(S A)$ space, improving
on the $\tilde{O}(S^2 A)$ bounds of best previous algorithms.  This result
proves efficient reinforcement learning is possible without
learning a model of the MDP from experience.  Learning takes place from
a single continuous thread of experience---no resets nor
parallel sampling is used.  Beyond its smaller storage and
experience requirements, Delayed Q-learning's per-experience
computation cost is much less than that of previous PAC
algorithms.
\end{abstract}

\section{Introduction}

In the reinforcement-learning (RL) problem~\cite{sutton98}, an agent
acts in an unknown or incompletely known
environment with the goal of
maximizing an external reward signal.  One of the fundamental obstacles
in RL is the exploration-exploitation dilemma: whether to act to gain new
information (explore) or to act consistently
with past experience to maximize reward (exploit).  This paper models
the RL problem as
a Markov Decision Process (MDP) environment with finite state and
action spaces.

When evaluating RL algorithms, there are three essential traits to
consider: {\it space complexity}, {\it computational
complexity}, and {\it sample complexity}.
We define a {\it timestep} to be a single interaction with the environment.
Space complexity measures the
amount of memory required to implement the algorithm while computational
complexity measures the amount of operations needed to execute the
algorithm, per timestep.  Sample complexity measures the
amount of timesteps for which the
algorithm does not behave near optimally or, in other words, the
amount of experience it
takes to learn to behave well.

We will call algorithms whose sample complexity can be bounded by a
polynomial in the environment size and approximation parameters, with
high probability, {\it PAC-MDP} ({\it Probably Approximately
Correct in Markov Decision Processes}).  All algorithms known to be
PAC-MDP to date
involve the maintenance and solution (often by value iteration or
mathematical programming) of an
internal MDP model.  Such algorithms, including $\rmax$~\cite{brafman02},
E$^3$~\cite{kearns02}, and MBIE~\cite{strehl05b}, are called
{\it model-based algorithms} and have relatively high space and
computational complexities.  Another class of algorithms, including most forms of
Q-learning~\cite{Watkins92}, make no effort to learn a model and can be called {\it
model free}.

It is difficult to articulate a hard and fast rule
dividing model-free and model-based algorithms, but model-based
algorithms generally retain some transition information during
learning whereas model-free algorithms only keep value-function
information.  Instead of formalizing this intuition,
we have decided to adopt a crisp, if somewhat unintuitive, definition.
For our purposes, a \emph{model-free RL algorithm} is
one whose space complexity is asymptotically less than the space required to
store an MDP.
\begin{definition}
A learning algorithm is said to be {\bf model free} if its space
complexity is always $o({S}^2 {{A}})$, where ${S}$ is the number of states and ${A}$
is the number of actions of the MDP used for learning.
\end{definition}
Although they tend to have low space and computational complexity, no
model-free algorithm has been proven to be PAC-MDP.  In this paper, we
present a new model-free algorithm, {\bf Delayed Q-learning}, and
prove it is the first such algorithm.
% that it is PAC-MDP.

The hardness of learning an arbitrary MDP as measured by sample
complexity is still relatively unexplored.  For simplicity, we let
$\tilde{O}(\cdot)$ ($\tilde{\Omega}(\cdot)$) represent $O(\cdot)$
($\Omega(\cdot)$) where logarithmic factors are ignored.
When we
%ignore logarithmic factors and
consider only the dependence on ${S}$ and ${A}$,
the lower bound of \namecite{kakade03} says that
%there is a known lower bound of $\Omega({S} {A})$ for the sample
%complexity of any PAC-MDP algorithm \cite{kakade03}.
with probability greater than $1 - \delta$, the sample complexity of any
algorithm will be $\tilde{\Omega}({S} {A})$.
However, the best upper bound known provides an algorithm whose sample
complexity is $\tilde{O}({S}^2 {A})$ with probability at least $1 - \delta$.
In other words, there are algorithms whose sample complexity is
known to be no greater than approximately
the number of bits required to specify an MDP to
fixed precision.
%the time it takes to learn
%an unknown MDP.
However, there has been no argument proving that learning to act
near-optimally takes as long as approximating the dynamics of an
MDP.  We solve this open problem, first posed by
\namecite{kakade03}, by showing that Delayed Q-learning has sample
complexity $\tilde{O}({S} {A})$, with high probability.
Our result therefore proves that efficient RL is possible without
learning a model of the environment from experience.


\section{Definitions and Notation}
\label{s:definitions}
This section introduces the Markov Decision Process notation used
throughout the paper; see \namecite{sutton98} for an introduction. An MDP
$M$ is a five tuple $\langle S,A,T,R, \gamma \rangle$, where $S$ is the
state space, $A$ is the action space, $T: S\times A\times S \rightarrow
\mathbb{R}$ is a transition function, $R: S\times A \rightarrow
\mathbb{R}$ is a reward function, and $0\le\gamma<1$ is a discount
factor on the summed sequence of rewards.  We also let $S$ and $A$
denote the number of states and the number of actions, respectively.
{From} state $s$ under action
$a$, the agent receives a random reward
$r$, which has expectation $R(s,a)$, and is transported to state $s'$ with probability
$T(s'|s,a)$.  A policy is a strategy for choosing actions.  Only
deterministic policies are dealt with in this paper. A stationary policy
is one that produces an action based on only the current state.  We
assume that rewards all lie between
$0$ and $1$.
%and we let $r_t$ denote the reward at time $t$ ($r$th reward
%received by the agent).
For any policy $\pi$, let $V^{\pi}_{M}(s)$ ($Q^{\pi}_{M}(s,a)$)
denote the discounted, infinite-horizon value (action-value or Q-value)
function for $\pi$ in $M$ (which may be omitted from the notation)
from state $s$. If $T$ is a positive integer, let $V_M^{\pi}(s,T)$
denote the $T$-step value  function of policy $\pi$. Specifically,
$V_M^{\pi}(s) = E[\sum_{j=1}^{\infty} {{\gamma}^{j-1} r_{j}}]$ and
$V_M^{\pi}(s,T) = E[\sum_{j=1}^T {{\gamma}^{j-1} r_{j}}]$ where
$[r_1, r_2, \ldots]$ is the reward sequence generated by following
policy $\pi$ from state $s$.
%let $s$ and
%$r_t$ be the
%$t$th encountered state and received reward, respectively, resulting
%from execution of policy $\pi$ in some MDP $M$. Then, $V_M^{\pi}(s) =
%E[\sum_{j=0}^{\infty} {{\gamma}^j r_{t+j}}]$ and $V_M^{\pi}(s,T) =
%E[\sum_{j=0}^{T-1} {{\gamma}^j r_{t+j}}]$.
These expectations are
taken over all possible infinite paths the agent might follow.
%from the $t$th step and onward.
The optimal policy is denoted $\pi^*$ and has value functions $V_M^*(s)$ and
$Q_M^*(s,a)$. Note that a policy
cannot have a value greater than ${1}/{(1-\gamma)}$ in any state.
%$\vmax := {1}/{(1-\gamma)}$.

\section {Learning Efficiently}

In our discussion, we assume that the learner receives ${S}$, ${A}$,
$\epsilon$, $\delta$, and $\gamma$ as input.
The learning problem is defined as follows. The agent always
occupies a single state $s$ of the MDP $M$.  The learning algorithm is told
this state and must select an action $a$.  The agent receives a reward
$r$  and is then transported to another state $s'$ according to the
rules from Section \ref{s:definitions}.  This procedure
then repeats forever.  The first state occupied by the agent may be
chosen arbitrarily.

There has been much discussion in the
%reinforcement-learning
RL
community over what defines
%an efficient learning algorithm
efficient learning or how to define sample complexity.  For any
fixed $\epsilon$, \namecite{kakade03} defines the {\bf sample
complexity of exploration} (sample complexity, for short) of an
algorithm ${\cal A}$ to be the number of timesteps $t$ such that
the non-stationary policy at time $t$, ${\cal A}_t$, is not
$\epsilon$-optimal from the current state\footnote{Note that
${\cal A}_t$ is completely defined by $\cal A$ and the agent's
history up to time $t$.}, $s_t$ at time $t$ (formally $V^{{\cal
A}_t}(s_t) < V^*(s_t) - \epsilon$).  We believe this definition
captures the essence of measuring learning.  An algorithm ${\cal
A}$ is then said to be {\bf PAC-MDP} (Probably Approximately
Correct in Markov Decision Processes) if, for any $\epsilon$ and
$\delta$, the sample complexity of ${\cal A}$ is less than some
polynomial in the relevant quantities (${S}, {A}, 1/\epsilon,
1/\delta, 1/{(1- \gamma)}$), with probability at least $1 -
\delta$.

The above definition penalizes the learner for executing a
non-$\epsilon$-optimal policy rather than for a non-optimal
policy.  Keep in mind that, with only a finite amount of
experience, no algorithm can identify the optimal policy with
complete confidence.  In addition, due to noise,
%in the environment,
any algorithm may be misled about the underlying dynamics of the
system. Thus, a failure probability of at most $\delta$ is allowed.
%Thus, the given definition also allows for arbitrary
%behavior by the learner, $\delta$ fraction of the time.
See
\namecite{kakade03} for a full motivation of this performance
measure.

\section {Delayed Q-learning}

In this section we describe a new reinforcement-learning algorithm,
Delayed Q-learning.

Delayed Q-learning maintains Q-value estimates, $Q(s,a)$ for each
state-action pair $(s,a)$.  At time $t (= 1,2,\ldots)$, let $Q_t(s,a)$
denote the algorithm's current Q-value estimate for $(s,a)$ and let
$V_t(s)$ denote $\max_{a \in A} {Q_t(s,a)}$.  The learner always acts
greedily with respect to its estimates, meaning that if $s$ is the $t$th
state reached, $a' := \argmax_{a \in A} {Q_t(s,a)}$ is the next action
chosen.

In addition to Q-value estimates, the algorithm maintains a
Boolean flag {\tt LEARN}$(s,a)$, for each $(s,a)$.  Let ${\tt
LEARN}_{t}(s,a)$ denote the value of {\tt LEARN}$(s,a)$ at time
$t$, that is, the value immediately before the $t$th action is
taken.  The flag indicates whether the learner is considering a
modification to its Q-value estimate $Q(s,a)$.  The algorithm also
relies on two free parameters, $\epsilon_1 \in (0,1)$ and a
positive integer $m$. In the analysis of Section \ref{s:analysis},
we provide precise values for these parameters in terms of the
other inputs (${S}$, ${A}$, $\epsilon$, $\delta$, and $\gamma$)
that guarantee the resulting algorithm is PAC-MDP. Finally, a
counter $l(s,a)$ ($l_t(s,a)$ at time $t$) is also maintained for
each $(s,a)$.  Its value represents the amount of data (sample
points) acquired for use in an upcoming update of $Q(s,a)$.  Once
$m$ samples are obtained and ${\tt LEARN}(s,a)$ is $\tt true$, an
update is attempted.

\subsection {Initialization of the Algorithm}

The Q-value estimates are initialized to $1/(1-\gamma)$, the counters
$l(s,a)$ to zero, and the ${\tt LEARN}$ flags to ${\tt
true}$.  That is, $Q_1(s,a) = 1/(1-\gamma)$, $l_1(s,a) = 0$, and ${\tt
LEARN}_{1}(s,a) = {\tt true}$ for all $(s,a) \in S \times A$.
%The Q-value estimates are initialized to $1/(1-\gamma)$, that is,
%$Q_1(s,a) = 1/(1-\gamma)$ for all $(s,a)$.  The counters $l(s,a)$ are
%initialized to zero ($l_1(s,a) = 0$) for all $(s,a)$.
%Before learning begins, the ${\tt LEARN}$ flags are all set to ${\tt
%true}$, specifically, ${\tt LEARN}_{1}(s,a) = {\tt true}$ for all
%$(s,a) \in S \times A$.

\subsection {The Update Rule}
\label {s:update_rule}

Suppose that at time $t \geq 1$, action $a$ is performed from
state $s$, resulting in an {\it attempted update}, according to
the rules to be defined in Section~\ref{s:learn_flags}.  Let
$s_{k_1},s_{k_2},\ldots,s_{k_m}$ be the $m$ most recent next-states observed
from executing $(s,a)$, at times $k_1 < k_2 < \dots < k_m$,
respectively ($k_m = t$).  For the remainder of the paper, we also
let $r_i$ denote the $i$th reward received during execution of
Delayed Q-learning.

Thus, at time $k_i$, action
$a$ was taken from state $s$, resulting in a transition to state
$s_{k_i}$ and an immediate reward $r_{k_i}$.  After the $t$th action, the following update occurs:
\begin{equation}
\label{e:delayed_update}
Q_{t+1}(s,a) = \frac{1}{m}\sum_{i=1}^{m} {(r_{k_i} + {\gamma}V_{k_i}(s_{k_i}))} + \epsilon_1
\end{equation}
as long as performing the update would result in a
new Q-value estimate that is at least $\epsilon_1$ smaller than
the previous estimate.
%\footnote{This condition is enforced only for
%reasons related to the theoretical analysis of Delayed Q-learning.}.
In other words, the
following equation must be satisfied for an update to occur:
\begin{equation}
\label{e:delayed_update_condition}
Q_{t}(s,a) - \left ( \frac{1}{m} \sum_{i=1}^{m} {(r_{k_i}+ \gamma V_{k_i}(s_{k_i}))}\right) \geq 2{\epsilon_1}.
\end{equation}
If any of the above conditions do not hold, then no update is performed.
In this case, $Q_{t+1}(s,a) = Q_{t}(s,a)$.

\subsection {Maintenance of the {\tt LEARN} Flags}
\label {s:learn_flags}

We provide an intuition behind the behavior of the ${\tt LEARN}$
flags.  Please see Section \ref{s:implementation} for a formal
description of the update rules.
% We assume that $m \geq 2$.
%\footnote{
%To account for
%the very unlikely case that m = 1, we would need to slightly complicate the
%details of this section and the proofs of Lemmas \ref{l:succ_update},
%\ref{l:Kfacts2} and
%\ref{l:am_bound} (the pseudocode of Section \ref{s:implementation} is
%still valid), because, when $m = 1$, the entire cycle of
%experiencing $(s,a)$ $m$ times and attempting to update $Q(s,a)$ can
%occur within a single timestep.}
The main
computation of the algorithm is that every time a state-action pair
$(s,a)$ is experienced $m$ times, an update of $Q(s,a)$ is attempted as
in Section \ref{s:update_rule}.  For our analysis to hold, however, we
cannot allow  an infinite number of attempted updates.  Therefore,
attempted updates are only allowed for $(s,a)$ when ${\tt LEARN}(s,a)$
is $\tt true$.  Besides being set to $\tt true$ initially, ${\tt
LEARN}(s,a)$ is also set to $\tt true$ when any state-action pair is
updated (because our estimate $Q(s,a)$ may need to reflect this change).
${\tt LEARN}(s,a)$ can only change from $\tt true$ to $\tt
false$ when no updates are made during a length of time for which
$(s,a)$ is experienced $m$ times and the next attempted update of $(s,a)$
fails.  In this case, no more attempted updates of $(s,a)$ are allowed
until another Q-value estimate is updated.


% problems with the following (when unsuccessful update occurs but learn
%should stay to true
%Suppose $(s,a)$ is experienced at time $t$.
%If $l(s,a)$ is equal to $m - 1$ ($l_{t}(s,a) =
%m-1$), and ${\tt LEARN}(s,a)$ is equal to true (${\tt LEARN}_{t}(s,a) = {\tt
%true}$), then we call such a timestep an ``attempted update'' for $(s,a)$.
%If condition
%(\ref{e:delayed_update_condition})
%is satisfied, then a ``successful update'' occurs, $Q_{t+1}(s,a)$ is
%computed using Equation (\ref{e:delayed_update}),
%${\tt
%LEARN}(s,a)$ is set to ${\tt true}$ (${\tt LEARN}_{t+1}(s,a) = {\tt
%true}$), and $l(s,a)$ is reset to
%$0$ ($l_{t+1}({s,a}) = 0$).  Otherwise,  an ``unsuccessful update''
%occurs, and ${\tt LEARN}(s,a)$ is set to ${\tt false}$ (${\tt
%LEARN}_{t+1}(s,a) = {\tt false}$).
%%
%If ${\tt LEARN}(s,a) = {\tt
%true}$, and $l(s,a)$ is less than $m - 1$, then we set $l_{t+1}(s,a) =
%l_{t}(s,a) + 1$ and ${\tt LEARN}(s,a)$ remains set to ${\tt true}$.
%%
%If ${\tt LEARN}(s,a)
%= {\tt false}$, then ${\tt LEARN}(s,a)$ is set to ${\tt
%true}$ and $l(s,a)$ to $1$ if a successful update of any state-action
%pair has occured since the last attempted update of $(s,a)$ (or since $t
%= 0$ if no attempted updates of $(s,a)$ have been performed).
%Otherwise, ${\tt LEARN}(s,a)$  remains equal to ${\tt false}$.

\subsection {Implementation of Delayed Q-learning}
\label {s:implementation}

We provide an efficient implementation, Algorithm \ref{a:dql}, of
Delayed  Q-learning that achieves our desired computational and space
complexities.
%For simplicity, we have omitted the action-selection step.
\begin{algorithm} [h]
\caption{Delayed Q-learning} \label{dql}
\begin{algorithmic}[1]
\label{a:dql}
\item {\bf Inputs:} $\gamma$, $S$, $A$, $m$, $\epsilon_1$
\FORALL{$(s,a)$}
\STATE $Q(s,a) \leftarrow 1/(1-\gamma)$  \hspace{3mm} {\small \textit{\textsf{// Q-value estimates}}}
\STATE $U(s,a) \leftarrow 0$  \hspace{3mm}  {\small \textit{\textsf{// used for attempted updates}}}
\STATE $l(s,a) \leftarrow 0$  \hspace{3mm}  {\small \textit{\textsf{// counters}}}
\STATE $t(s,a) \leftarrow 0$ \hspace{3mm}  {\small \textit{\textsf{// time of last attempted update}}}
\STATE $LEARN(s,a) \leftarrow true$  \hspace{3mm}  {\small \textit{\textsf{// the LEARN flags}}}
\ENDFOR
\STATE $t^* \leftarrow 0$  \hspace{3mm}  {\small \textit{\textsf{// time of most recent Q-value change}}}
\FOR{$t=1,2,3,\cdots$}
\STATE Let $s$ denote the state at time $t$.
\STATE Choose action $a := \argmax_{a' \in A} {Q(s,a')}$.
\STATE Let $r$ be the immediate reward and $s'$ the next state after
executing action $a$ from state $s$.
\IF{$LEARN(s,a)=true$}
\STATE
%$$q(s,a) \leftarrow \frac{q(s,a)l(s,a) + r + \gamma \max_{a'}Q(s',a')}{l(s,a)+1} $$
$U(s,a) \leftarrow U(s,a) + r + \gamma \max_{a'}Q(s',a')$
\STATE $l(s,a) \leftarrow l(s,a) + 1$
\IF{$l(s,a)=m$} \IF{$Q(s,a) - U(s,a)/m \ge 2 \epsilon_1$}
\STATE
$Q(s,a) \leftarrow U(s,a)/m + \epsilon_1$ \STATE $t^* \leftarrow t$
\ELSIF{$t(s,a) \ge t^*$}
\STATE $LEARN(s,a) \leftarrow \mbox{\tt false}$
\ENDIF
\STATE $t(s,a) \leftarrow t$, $U(s,a) \leftarrow 0$, $l(s,a) \leftarrow 0$
%\STATE $U(s,a) \leftarrow 0$
%\STATE $l(s,a) \leftarrow 0$
\ENDIF
\ELSIF{$t(s,a) < t^*$}
\STATE $LEARN(s,a) \leftarrow true$
\ENDIF
\ENDFOR
\end{algorithmic}
\end{algorithm}

\subsection{Discussion}

Delayed Q-learning is similar in many aspects to traditional Q-learning.
Suppose that at time $t$, action $a$ is taken from state $s$ resulting
in reward $r_t$ and next-state $s'$.  Then, the Q-learning update is
\begin {equation}
\label {e:Q_learning}
Q_{t+1}(s,a) = (1 - \alpha_t)Q_{t}(s,a) + \alpha_t(r_{t} + \gamma V_{t}(s'))
\end {equation}
where $\alpha_t \in [0,1]$ is the learning rate.  Note that if we let
$\alpha_t = {1}/{(l_t(s,a)+1)}$, then $m$ repetitions of Equation~\ref{e:Q_learning}
is similar to
the update for Delayed Q-learning (Equation \ref{e:delayed_update})
minus a small bonus of $\epsilon_1$.  However, Q-learning
changes its Q-value estimates on every timestep, while
Delayed Q-learning waits for $m$
sample updates to make any changes.  This variation has an averaging effect that
mitigates some of the effects of randomness and, when combined with the
bonus of $\epsilon_1$, achieves optimism ($Q(s,a)
\geq Q^*(s,a)$) with high probability (see Lemma
\ref{l:delayed_optimism}).

The property of optimism is useful for safe
exploration and appears in many existing RL algorithms.  The intuition is that if an action's Q-value is overly
optimistic the agent will learn much by executing that action.  Since
the action-selection strategy is greedy, the Delayed Q-learning agent
will tend to choose
overly optimistic actions, therefore achieving directed exploration when
necessary.  If sufficient learning has been completed and all Q-values
are close to their true $Q^*$-values, selecting the maximum will guarantee
near-optimal behavior.  In the next section, we provide a formal argument
that Delayed Q-learning exhibits sufficient exploration for learning,
specifically that it is PAC-MDP.


%>  (1) DQL is similar to QL with step sizes 1/t (for t=1...m), except that
%> the update is batch and t cycles from 1 through m.
%>  (2) What makes DQL PAC, intuitively, includes
%>     (i) it encourages exploration by maintaining an optimistic estimate of
%> Q(.,.), which is achieved by optimistic initialization and the epsilon_1
%> bonus
%>     (ii) it requires a sufficient update condition (Eqn 2) to bound the
%> total number of attempted updates
%>     (iii) it adopts the idea of delayed, batch updates, which avoids the
%> often problematic learning rates and also alleviates the impacts of
%> randomness.

\section {Analysis}
\label{s:analysis}

We briefly address space and computational complexity before
focusing on analyzing the sample complexity of Delayed Q-learning.

\subsection {Space and Computational Complexity}

An implementation of Delayed Q-learning, as in Section~\ref{s:implementation}, can be achieved with $O({S}
{A})$ space complexity\footnote{We measure complexity assuming
individual numbers require unit storage and can be manipulated
arithmetically in unit time.  Removing this assumption increases space
and computational complexities by logarithmic factors.}.  With use of a
priority queue for choosing
actions with maximum value, the algorithm can
achieve $O(\ln{A})$ computational complexity per timestep.
Asymptotically, Delayed Q-learning's computational and space complexity
are on par with those of Q-learning.  In contrast, the $\rmax$ algorithm, a standard
model-based method, has worst-case space complexity of $\Theta({S}^2 A)$ and
computational complexity of $\Omega({{S}}^2 A)$ per experience.

\subsection {Sample Complexity}

The main result of this section, whose proof is provided in Section
\ref{s:main}, is that the Delayed Q-learning algorithm is PAC-MDP:
%
\begin{theorem}
\label {p:delayed_pac}
Let $M$ be any MDP and let $\epsilon$ and $\delta$ be two positive real
numbers.  If Delayed Q-learning is executed on MDP $M$, then it will
follow an $\epsilon$-optimal policy on all but $O\left({
\frac{{S}{A}}{{(1-\gamma)}^8{\epsilon}^4}}
\ln{\frac{1}{\delta}} \ln{\frac{1}{\epsilon(1-\gamma)}}
\ln{\frac{{S}{A}}{\delta\epsilon(1-\gamma)} }\right)$
timesteps, with probability at least $1 - \delta$.
\end{theorem}
%

To analyze the sample complexity of Delayed Q-learning, we first
bound the number of successful updates. By
Condition~\ref{e:delayed_update_condition}, there can be no more
than
\begin{equation}
\kappa := \frac{1}{(1-\gamma)\epsilon_1}
\end{equation}
successful updates of a fixed state-action pair $(s,a)$.  This
bound follows from the fact that $Q(s,a)$ is initialized to
$1/(1-\gamma)$ and that every successful update of $Q(s,a)$
results in a decrease of at least $\epsilon_1$.  Also, by our
assumption of non-negative rewards, it is impossible for any
update to result in a negative Q-value estimate. Thus, the total
number of successful updates is at most ${S} {A} \kappa$.

Now, consider the number of attempted updates for a single
state-action pair $(s,a)$.  At the beginning of learning, ${\tt
LEARN}(s,a) = {\tt true}$, which means that once $(s,a)$ has been
experienced $m$ times, an attempted update will occur.  After
that, a successful update of some Q-value estimate must take place
for ${\tt LEARN}(s,a)$ to be set to $\tt true$.  Therefore, there
can be at most $1 + {S} {A} \kappa$ attempted updates of $(s,a)$.
Hence, there are at most
\begin{equation}
{S} {A} (1 + {S} {A} \kappa)% = SA \left( 1 + \frac{SA}{(1-\gamma)\epsilon_1} \right)
\end{equation}
total attempted updates.

During timestep $t$ of learning, we define $K_t$ to be the set of all
state-action pairs $(s,a)$ such that:
\begin{equation}
\label{e:delayed}
Q_{t}(s,a) - \left({R(s,a) + \gamma \sum_{s'}{T(s'|s,a)V_t(s')}}\right)
\leq
3\epsilon_1.
\end{equation}
Observe that $K_t$ is defined by the true transition and reward
functions $T$ and $R$, and therefore cannot be known to the learner.

Now, consider the following statement:

\vspace{1ex}

{\bf Assumption A1}
{\it Suppose an attempted update of state-action pair (s,a) occurs
at time $t$, and that the $m$ most recent experiences of $(s,a)$
happened at times $k_1 < k_2 < \dots < k_m = t$.
If $(s,a) \not \in K_{k_1}$ then the
attempted update will be successful.}

\vspace{1ex}

During any given infinite-length execution of Delayed Q-learning,
the statement $(A1)$ may be true (all attempted updates with $(s,a) \not
\in K_{k_1}$ are successful) or it may be broken (some unsuccessful update
may occur when $(s,a) \not \in K_{k_1})$.  When $(s,a) \not \in
K_{k_1}$, as above, our value function estimate $Q(s,a)$ is very
inconsistent with our other value function estimates.  Thus, we would
expect our next attempted update to succeed.  The next lemma shows
this intuition is valid.  Specifically, with probability at least $1 -
\delta/3$, $A1$ will be true.  We are now ready to specify a value for
$m$:
\begin {equation}
\label {e:m_definition} m := \frac{\ln{ \left({ {3 {S} {A} (1 +
{S} {A} \kappa)} / {\delta}
}\right)}}{2{\epsilon_1}^2(1-\gamma)^2} \:.
\end {equation}

\begin{lemma}
\label{l:succ_update}
The probability that $A1$ is violated
during execution of Delayed Q-learning is at most $\delta/3$.
\end{lemma}

%\begin{proofsketch}
%Suppose that on some fixed timestep, $k_1$, during execution of Delayed
%Q-learning, a state-action pair $(s,a) \not \in K_{k_1}$ is experienced.
%Also suppose that if $(s,a)$ is experienced $m-1$ more
%times, then an attempted update will result.
%%First, note that the
%%number of timesteps for which such a situation can happen is  bounded by
%%the number of attempted updates, which is bounded by  ${S} {A} (1 + {S}
%%{A} \kappa)$.
%Let ${\cal Q} = (s[1],r[1]),\ldots,(s[m],r[m])$ be any
%sequence of $m$ next-state and immediate reward tuples.
%%(we interpert
%%$(s_i,r_i)$ to be a possible next-state and immediate reward recieved by
%%the agent after taking action $a$ from state $s$ for the $i$ time after
%%and including timestep $k_1$).
%Due to the Markov assumption, on
%any timestep for which the agent is in state $s$ and chooses
%action $a$, the resulting next-state and immediate reward are chosen
%independently of the history of the agent.  Thus, the probability that
%$(s,a)$ is experienced by the agent $m-1$ more times after timestep $k_1$ and
%that the resulting next-state and immediate reward sequence equals
%$\cal Q$ is at most the probability that
%$\cal Q$ is obtained by $m$ indepedent draws of next-state and
%reward tuples from the transition and reward distributions (for
%state-action pair $(s,a)$).
%We now analyze the probability that a
%random sequence $\cal Q$ could cause an unsuccessful update of
%$(s,a)$.
%
%Suppose that $m$ rewards, $r[1],\ldots,r[m]$, and $m$ next states,
%$s[1],\ldots,s[m]$, are drawn independently from the reward and
%transition distributions, respectively, for $(s,a)$.
%%Let $X_1, X_2,
%%\ldots, X_m$ be the $m$ independently and identically distributed random
%%variables defined by:
%%\begin{equation}
%%X_i := r{[i]} + \gamma V_{k_1}(s[i]).
%%\end{equation}
%%Note that $X_i$ is defined in terms of the (fixed) value function at time $k_1$,
%%$V_{k_1}(\cdot)$ and has range $0 \leq X_i \leq 1/(1-\gamma)$.  We claim that the
%%expected value of $X_i$, $E[X_i]$, is at most $Q_{k_1}(s,a) - 3\epsilon_1$; note that:
%%%\begin{eqnarray*}
%%%\lefteqn{E[X_i]}\\
%%%& = &  E[r_{k_i}] + \gamma E[V_{k_1}(s_i)] \\
%%%& = & R(s,a) + \gamma \sum_{s' \in S} {T(s'|s,a)V_{k_1}(s')} \\
%%%& < & Q_t(s,a) - 3\epsilon_1.
%%%\end{eqnarray*}
%%$E[X_i] = R(s,a) + \gamma \sum_{s' \in S} {T(s'|s,a)V_{k_1}(s')} <
%%Q_t(s,a) - 3\epsilon_1$.
%%This follows from the fact that $(s,a) \not \in K_{k_1}$.  By
%%the Hoeffding bound,
%%\begin {equation*}
%%\Pr \left[ {(1/m)\sum_{i=1}^{m}{X_i} - E[X_1] \geq \epsilon_1}
%%\right ] \leq e^{(- 2{\epsilon_1}^2 m)(1-\gamma)^2}.
%%\end {equation*}
%%The value of $m$ (Equation \ref{e:m_definition}) guarantees that
%%\begin {equation}
%%\label {e:closeness_1}
%%{(1/m)\sum_{i=1}^{m}{X_i} - E[X_1]  < \epsilon_1}
%%\end {equation}
%%holds with probability at least $1 - \delta/{(3 {S} {A} (1 + {S}
%%{A} \kappa))}$.
%By a straightforward application of the Hoeffding bound (with random
%variables $X_i := r{[i]} + \gamma V_{k_1}(s[i])$) it can be shown that
%our choice of $m$ guarantees that
%${(1/m)\sum_{i=1}^{m}{(r{[i]} + \gamma V_{k_i}(s[i]))} - E[X_1]  < \epsilon_1}$ holds with
%probability at least $1 - \delta/{(3 {S} {A} (1 + {S} {A} \kappa))}$.
%Now, we claim that if this does hold and an
%attempted update is performed for $(s,a)$ using these $m$ samples, then
%the resulting update will be successful.  To see this, suppose that $(s,a)$
%is experienced at times $k_1 < k_2 < \dots < k_m = t$ and at time $k_i$
%the agent is transitioned to state $s[i]$ and receives reward $r[i]$ after
%taking action $a$ from state $s$ (causing an attempted update at
%time $t$).  Then, we have that
%\begin{eqnarray*}
%\lefteqn{Q_{t}(s,a) - \left ( {\frac{1}{m} \sum_{i=1}^{m} {(r{[i]} + \gamma V_{k_i}(s[i]))}}\right)}\\
%& \geq & Q_{t}(s,a) - E[X_1] - \epsilon_1 > 2 \epsilon_1.
%\end{eqnarray*}
%The first step above used the fact that $V_{t_1}(s) \geq V_{t_2}(s)$ for
%all states $s$ and times $t_1,t_2$ such that $t_1 < t_2$.
%Therefore, with high probability,
%Condition~\ref{e:delayed_update_condition} will be satisfied and the
%attempted update of $Q(s,a)$ at time $k_{m}$ will be successful.
%
%Finally, we extend our argument, using the union bound to all possible
%timesteps $k_1$ satisfying the condition above.
%%Specifically, we have
%%bounded
%%the probability of the following individual events: The $k$th attempted
%%update for $(s,a)$ (for $k = 1,\ldots,\kappa$) is unsuccessful (note
%%that this event, for a given $k$ cannot occur unless there is a $k$th
%%attempted update for $(s,a)$).
%%%a timestep $k_1$ occurs as above and that an unsuccessful update occurs
%%%for the corresponding $(s,a)$ on the next attempted update of $(s,a)$).
%The number of such timesteps is bounded by the number of attempted
%updates ($\leq {S} {A} (1 + {S} {A} \kappa)$).
%\end{proofsketch}

\begin{proofsketch}
Fix any timestep $k_1$ (and the complete history of the agent up to $k_1$)
satisfying: $(s,a) \not \in K_{k_1}$ is to be
experienced by the agent on timestep $k_1$ and if $(s,a)$ is experienced
$m-1$ more times after timestep $k_1$, then an attempted update will
result.
Let ${\cal Q} = [ (s[1],r[1]),\ldots,(s[m],r[m]) ] \in {(S\times \mathbb{R})}^m$ be
any sequence of $m$ next-state and immediate reward tuples. Due to
the Markov assumption,
%on any timestep for which
whenever the agent is in state $s$ and chooses
action $a$, the resulting next-state and immediate reward are chosen
independently of the history of the agent.  Thus, the probability that
$(s,a)$ is experienced
%by the agent
$m-1$ more times
%after timestep $k_1$
and that the resulting next-state and immediate reward sequence equals
$\cal Q$ is at most the probability that
$\cal Q$ is obtained by $m$ independent draws
%of next-state and reward tuples
from the transition and reward distributions (for $(s,a)$).
%We now analyze the probability that a
%random sequence $\cal Q$ could cause an unsuccessful update of
%$(s,a)$.
Therefore, it suffices to prove this lemma by showing that the
probability that a random sequence $\mathcal{Q}$ could cause an
unsuccessful update of $(s,a)$ is at most $\delta/3$.  We prove this statement next.

Suppose that $m$ rewards, $r[1],\ldots,r[m]$, and $m$ next states,
$s[1],\ldots,s[m]$, are drawn independently from the reward and
transition distributions, respectively, for $(s,a)$.
By a straightforward application of the Hoeffding bound (with random
variables $X_i := r{[i]} + \gamma V_{k_1}(s[i])$), it can be shown that
our choice of $m$ guarantees that
${(1/m)\sum_{i=1}^{m}{(r{[i]} + \gamma V_{k_1}(s[i]))} - E[X_1]  < \epsilon_1}$ holds with
probability at least $1 - \delta/{(3 {S} {A} (1 + {S} {A} \kappa))}$.
If it does hold and an
attempted update is performed for $(s,a)$ using these $m$ samples, then
the resulting update will succeed.  To see the claim's validity, suppose that $(s,a)$
is experienced at times $k_1 < k_2 < \dots < k_m = t$ and at time $k_i$
the agent is transitioned to state $s[i]$ and receives reward $r[i]$
%after taking action $a$ from state $s$
(causing an attempted update at time $t$).  Then, we have that
\begin{eqnarray*}
\lefteqn{Q_{t}(s,a) - \left ( {\frac{1}{m} \sum_{i=1}^{m} {(r{[i]} + \gamma V_{k_i}(s[i]))}}\right)}\\
& > & Q_{t}(s,a) - E[X_1] - \epsilon_1 \,\,>\,\, 2 \epsilon_1.
\end{eqnarray*}
%We have used the fact that $V_{t_1}(s) \geq V_{t_2}(s)$ for
%all states $s$ and times $t_1,t_2$ such that $t_1 < t_2$.
We have used the fact that $V_{k_i}(s') \leq V_{k_1}(s')$ for all $s'$ and $i =
1,\ldots,m$.
Therefore, with high probability,
Condition~\ref{e:delayed_update_condition} will be satisfied and the
attempted update of $Q(s,a)$ at time $k_{m}$ will succeed.

Finally, we extend our argument, using the union bound, to all possible
timesteps $k_1$ satisfying the condition above.
%Specifically, we have
%bounded
%the probability of the following individual events: The $k$th attempted
%update for $(s,a)$ (for $k = 1,\ldots,\kappa$) is unsuccessful (note
%that this event, for a given $k$ cannot occur unless there is a $k$th
%attempted update for $(s,a)$).
%%a timestep $k_1$ occurs as above and that an unsuccessful update occurs
%%for the corresponding $(s,a)$ on the next attempted update of $(s,a)$).
The number of such timesteps is bounded by the same bound we showed for the
number of attempted updates (${S} {A} (1 + {S} {A} \kappa)$).
\end{proofsketch}

The next lemma states that, with high probability, Delayed Q-learning
will maintain optimistic Q-values.

\begin{lemma}
\label{l:delayed_optimism}
During execution of Delayed Q-learning,
$Q_t(s,a) \geq Q^*(s,a)$ holds for all timesteps $t$ and state-action
pairs $(s,a)$, with probability at least $1 - \delta/3$.
\end{lemma}

\begin {proofsketch}
It can be shown, by a similar argument as in the proof of Lemma
\ref{l:succ_update},
%an application of the Hoeffding bound and the Union
%bound,
that
${(1/m)\sum_{i=1}^{m}{{(r_{k_i} + \gamma V^*(s_{k_i}))}}  > Q^*(s,a) -
\epsilon_1}$ holds, for all attempted updates, with probability at least
$1 - \delta/3$.  Assuming this equation does hold, the proof is by induction
on the timestep $t$.
%
For the base
case, note that $Q_1(s,a) = 1/(1-\gamma) \geq Q^*(s,a)$ for all $(s,a)$.
Now, suppose the claim holds for all timesteps less than or equal to
$t$. Thus, we have that $Q_{t}(s,a) \geq Q^*(s,a)$, and $V_{t}(s) \geq
V^*(s)$ for all $(s,a)$. Suppose $s$ is the $t$th state reached and $a$ is
the action taken at time $t$.
%
If it doesn't result in an attempted update or it results in an
unsuccessful update, then no Q-value estimates change, and we
are done.  Otherwise, by Equation~\ref{e:delayed_update}, we have that
$Q_{t+1}(s,a) =({1}/{m})
\sum_{i=1}^{m} {(r_{k_i} + \gamma V_{k_i}(s_{k_i}))} + \epsilon_1  \geq
({1}/{m}) \sum_{i=1}^{m} {(r_{k_i} + \gamma V^*(s_{k_i}))} + \epsilon_1 \geq
Q^*(s,a)$, by the induction hypothesis and an application of the
equation from above.
\end {proofsketch}
%
%\begin {lemma}
%\label {l:Kfacts}
%If $(s,a) \in K_{t_1}$ and $(s,a) \not \in K_{t_2}$ with $t_1 <
%t_2$, then a successful update of some Q-value (not necessarily $Q(s,a)$)
%occurred between times $t_1$ and $t_2$.  Similarly, if $(s,a) \not \in
%K_{t_1}$ and $(s,a) \in K_{t_2}$ with $t_1 < t_2$, then a successful
%update of $Q(s,a)$ occurred between times $t_1$ and $t_2$.
%\end {lemma}
%
%\begin {proof}
%The first statement of the lemma follows from the fact that if no
%successful updates occur between times $t_1$ and $t_2$, then $K_{t_1} =
%K_{t_2}$.  The second statement follows from the fact that $V_{t_1}(s') \geq
%V_{t_2}(s')$ for all states $s'$.
%\end {proof}

\begin {lemma}
\label {l:Kfacts2}
If Assumption $A1$ holds, then the following statement holds:
If an unsuccessful update occurs at time $t$ and ${\tt LEARN}_{t+1}(s,a)
= {\tt false}$, then $(s,a) \in K_{t+1}$.
\end {lemma}

\begin {proof}
Suppose an attempted update of $(s,a)$ occurs at time $t$.
Let $s_{k_1},s_{k_2},\ldots,s_{k_m}$ be the $m$ most recent
next-states resulting from executing action $a$
from state $s$ at times $k_1 < k_2 < \dots < k_m = t$, respectively.
By $A1$, if $(s,a) \not \in K_{k_1}$, then the update will be
successful.
Now, suppose that $(s,a) \in
K_{k_1}$ but that $(s,a) \not \in K_{k_i}$ for some $i \in \{
2,\dots,m \}$.  In this case, the attempted update at time $k_m$ may be
unsuccessful.  However,  some Q-value estimate
was successfully updated between time $k_1$ and time $k_m$ (otherwise
$K_{k_1}$ would equal $K_{k_1}$).  Thus, by
the rules of Section \ref{s:learn_flags}, ${\tt LEARN}(s,a)$ will be set
to $\tt true$ after this unsuccessful update (${\tt LEARN}_{t+1}(s,a)$ will
be true).
\end {proof}

The following lemma bounds the number of timesteps $t$ in which a
state-action pair $(s,a) \not \in K_t$ is experienced.

\begin{lemma}
\label {l:am_bound}
%Let $m$ be chosen as in Equation~\ref{e:m_definition} and suppose that assumption A1 holds.  Then,
The number of timesteps $t$ such
that a state-action pair $(s,a) \not \in K_t$ is experienced is at most
$2 m {S} {A} \kappa$.
\end{lemma}

\begin{proof}
Suppose $(s,a) \not \in K_t$ is experienced at time $t$ and ${\tt
LEARN}_{t}(s,a) = {\tt false}$ (implying the last attempted update was
unsuccessful).
 By Lemma \ref{l:Kfacts2},
we have that $(s,a) \in K_{t'+1}$ where $t'$ was the time of the
last attempted update of $(s,a)$.  Thus, some successful update has occurred since time
$t'+1$.  By the rules of Section \ref{s:learn_flags}, we have that ${\tt
LEARN}(s,a)$ will be set to $\tt true$ and by $A1$, the
next attempted update will succeed.

Now, suppose that $(s,a) \not \in K_t$ is experienced at time $t$ and ${\tt
LEARN}_t(s,a) = {\tt true}$.  Within at most $m$ more experiences of
$(s,a)$, an attempted update of $(s,a)$ will occur.  Suppose this
attempted update takes place
at time $q$ and that the $m$ most recent experiences of $(s,a)$
happened at times $k_1 < k_2 < \dots < k_m = q$.
By $A1$, if $(s,a) \not \in K_{k_1}$, the update
will be successful.
%If, on the other hand,
Otherwise, if $(s,a)
\in K_{k_1}$, then
%by Lemma \ref{l:Kfacts}
some successful update must have
occurred between times $k_1$ and $t$ (since $K_{k_1} \not = K_t$).  Hence, even if the update is
unsuccessful, ${\tt LEARN}(s,a)$ will remain $\tt true$, $(s,a) \not \in
K_{q+1}$ will hold,
%(see Lemma \ref{l:Kfacts}),
and the next
attempted update of $(s,a)$ will be successful.

In either case, if $(s,a) \not \in K_t$, then within at
most $2 m$ more experiences of $(s,a)$, a successful update of $Q(s,a)$
will occur.  Thus, reaching a state-action pair
not in $K_t$ at time $t$ will happen at most $2 m {S} {A} \kappa$ times.
\end{proof}

We will make use of the following lemma from \namecite{strehl05b}.

\begin{lemma}{\bf (Generalized Induced Inequality)}
\label{l:gii}
Let $M$ be an MDP, $K$ a set of state-action pairs, $M'$ an MDP
equal to $M$ on $K$ (identical transition and reward functions), $\pi$
a  policy, and $T$ some positive integer.  Let
$A_M$
be the
event that a state-action pair not in $K$ is encountered in a trial generated by
starting from state $s$ and following $\pi$ for $T$ timesteps in $M$.
Then,
$$V_M^\pi (s,T)
\geq
V_{M'}^\pi (s,T) - \Pr(A_M)/(1-\gamma).$$
\end{lemma}

\subsubsection {Proof of the Main Result}
\label{s:main}

%\begin{proof}
{\bf Proof of Theorem \ref{p:delayed_pac}:}
Suppose Delayed Q-learning is run on MDP $M$.
We assume that $A1$ holds and that $Q_t(s,a)
\geq Q^*(s,a)$ holds for all timesteps $t$ and
state-action pairs $(s,a)$.  The probability that either one of these
assumptions is broken is at most $2\delta/3$, by Lemmas
\ref{l:succ_update} and \ref{l:delayed_optimism}.

Consider timestep $t$ during learning.  Let ${\cal A}_t$ be the
non-stationary policy being executed by the learning algorithm.
Let $\pi_t$ be the current greedy policy, that is, for all states
$s$, ${\pi}_t(s) = \argmax_a {Q_t(s,a)}$.  Let $s_t$ be the
current state, occupied by the agent at time $t$.  We define a new
MDP, $M'$.  This MDP is equal to $M$ on $K_t$ (identical
transition and reward functions).  For $(s,a) \not \in K_t$, we
add a distinguished state $S_{s,a}$ to the state space of $M'$ and
a transition of probability one to that state from $s$ when taking
action $a$. Furthermore, $S_{s,a}$ self-loops on all actions with
reward $[Q_t(s,a) - R(s,a)](1-\gamma)/\gamma$ (so that
$V^\pi_{M'}(S_{s,a}) = [Q_t(s,a) - R(s,a)]/\gamma$ and
$Q^{\pi}_{M'}(s,a) = Q_t(s,a)$, for any policy $\pi$).    Let $T =
O(\frac{1}{1-\gamma}\ln{\frac{1}{\epsilon_2(1- \gamma)}})$ be
large enough so that $|V^{\pi_t}_{M'}(s_t,T)- V^{\pi_t}_{M'}(s_t)|
\leq \epsilon_2$ (see Lemma 2 of \namecite{kearns02}). Let $\Pr(A_M)$
denote the probability of reaching a state-action pair $(s,a)$ not
in $K_t$, while executing policy ${{\cal A}_t}$ from state $s_t$
in $M$ for $T$ timesteps.  Let $\Pr(U)$ denote the probability of
the algorithm performing a successful update on some state-action
pair $(s,a)$, while executing policy ${{\cal A}_t}$ from state
$s_t$ in $M$ for $T$ timesteps.  We have that
\begin{eqnarray*}
\lefteqn{V_M^{{\cal A}_t} (s_t,T)}\\
& \geq & V_{M'}^{{\cal A}_t} (s_t,T) -  \Pr(A_M)/(1-\gamma) \\
& \geq & V_{M'}^{\pi_t} (s_t,T) -  \Pr(A_M)/(1-\gamma) - \Pr(U)/(1-\gamma) \\
& \geq & V_{M'}^{\pi_t} (s_t) - \epsilon_2 - (\Pr(A_M) +
\Pr(U))/(1-\gamma).
\end{eqnarray*}
The first step above follows from Lemma \ref{l:gii}\footnote{Lemma
\ref{l:gii} is valid for all policies, including non-stationary ones.}.
The second
step follows from the fact that ${\cal A}_t$ behaves identically to
$\pi_t$ as long as no Q-value estimate updates are performed.  The third
step follows from the definition of $T$ above.

Now, consider two mutually exclusive cases.
First, suppose that $\Pr(A_M) + \Pr(U) \geq
{\epsilon_2(1-\gamma)}$, meaning that an agent following ${\cal A}_t$ will
either perform a successful update in $T$ timesteps, or encounter some
$(s,a) \not \in K_t$ in $T$ timesteps with probability at least
${\epsilon_2(1-\gamma)}/2$ (since $\Pr(A_M~\mathrm{or}~U) \geq
(\Pr(A_M)+\Pr(U))/2$).  The former event cannot happen more than ${S}
{A} \kappa$ times.  By assumption, the latter event will
happen no more than $2 m {S} {A} \kappa$ times (see Lemma \ref{l:am_bound}).
Define
$
\zeta = (2 m + 1) {S} {A} \kappa.
$
Using the Hoeffding bound, after $O(\frac{\zeta T}{\epsilon_2(1-
\gamma)}\ln{1/\delta})$ timesteps where $\Pr(A_M) + \Pr(U) \geq
{\epsilon_2(1-\gamma)}$, every state-action pair will have been
updated $1 / (\epsilon_1(1-\gamma))$ times, with probability at least $1 -
\delta/3$, and no futher updates will be possible.  This fact implies that
the number of timesteps $t$ such that $\Pr(A_M) + \Pr(U) \geq
{\epsilon_2(1-\gamma)}$ is bounded by $O(\frac{\zeta T}{\epsilon_2(1-\gamma)}\ln{1/\delta})$, with high probability.

Next, suppose that  $\Pr(A_M) + \Pr(U) < {\epsilon_2(1-\gamma)}$.  We claim that
the following holds for all states $s$:
\begin {equation}
\label {e:delayed_closeness}
0 < V_t(s) - V^{{{\pi_t}}}_{M'}(s) \leq \frac{3\epsilon_1}{1-\gamma}.
\end {equation}
Recall that for all $(s,a)$, either $Q_t(s,a) = Q^{{{\pi_t}}}_{M'}(s,a)$ (when
$(s,a) \not \in K_t$), or $Q_t(s,a) - \left({R(s,a) + \gamma
\sum_{s'}{T(s'|s,a)V_t(s')}}\right) \leq 3\epsilon_1$ (when $(s,a) \in K_t$).
%If $a_s$ denotes ${{\pi_t}}(s)$, then
Note that $V^{{{\pi_t}}}_{M'}$ is the solution
to the following set of equations:
%
\begin{eqnarray*}
    V^{{{\pi_t}}}_{M'}(s) %
&=& R(s,{{\pi_t}}(s)) + \gamma \sum_{s'\in S}{T(s'|s,{{\pi_t}}(s))V^{{{\pi_t}}}_{M'}(s')}, \\
& & \qquad\qquad\qquad\qquad\qquad \mbox{if $(s,{{\pi_t}}(s)) \in K$}, \\
    V^{{{\pi_t}}}_{M'}(s) %
&=& Q_t(s,{{\pi_t}}(s)), \qquad\qquad\,\,\, \mbox{if $(s,{{\pi_t}}(s)) \not \in K$}.
\end{eqnarray*}
%
%$$ V^{{{\pi_t}}}_{M'}(s) = R(s,a_s) + \gamma \sum_{s'\in
%S}{T(s'|s,a_s)V^{{{\pi_t}}}_{M'}(s')} ~,~ (s,a_s) \in K $$
%$$ V^{{{\pi_t}}}_{M'}(s) = Q_t(s,a_s) ~,~ (s,a_s) \not \in K. $$

The vector $V_t$ is the solution to a similar set of equations
except with some additional positive reward terms, each bounded by $3\epsilon_1$.
Using these facts, we have that
\begin{eqnarray*}
\lefteqn{V^{{\cal A}_t}_{M}(s_t) \geq V^{{\cal A}_t}_{M}(s_t,T)}\\
& \geq & V_{M'}^{\pi_t} (s_t,T) - \epsilon_2 - (\Pr(A_M) + \Pr(U))/(1-\gamma) \\
& \geq & V_{M'}^{\pi_t} (s_t) - \epsilon_2 - \epsilon_2 \\
& \geq & V_t(s_t) - 3\epsilon_1/(1-\gamma) - 2 \epsilon_2 \\
& \geq & V^*(s_t) - 3\epsilon_1/(1-\gamma) - 2 \epsilon_2.
\end{eqnarray*}
The third step follows from the fact that $\Pr(A_M) + \Pr(U) <
{\epsilon_2(1-\gamma)}$ and the fourth step from
Equation~\ref{e:delayed_closeness}. The last step made use of our
assumption that $V_t(s_t) \geq V^*(s_t)$ always holds.

Finally, by setting $\epsilon_1 := \epsilon(1-\gamma)/9$ and
$\epsilon_2 := \epsilon/3$, we have that
\begin{eqnarray*}
V_{{\cal A}_t}^{{{\pi_t}}}(s_t,T) \geq V^*(s_t) - \epsilon
\end{eqnarray*}
is true for all but
$O(\frac{\zeta T}{\epsilon_2(1-\gamma)}\ln{1/\delta})$
$$
= O\left({
\frac{{S}{A}}{{\epsilon}^4{(1-\gamma)}^8}}
\ln{\frac{1}{\delta}} \ln{\frac{1}{\epsilon(1-\gamma)}} \ln{\frac{{S}{A}}{\delta\epsilon(1-\gamma)}
}\right)
$$
timesteps, with probability at least $1 - \delta$.  We guarantee a
failure probability of at most $\delta$ by bounding the three
sources of failure: from Lemmas \ref{l:succ_update},
\ref{l:delayed_optimism}, and from the above application of
Hoeffding's bound. Each of these will fail with probability at
most $\delta/3$. $\Box$
%\end {proof}

Ignoring log factors, the best sample complexity bound previously proven
has been
$$
\tilde{O}\left( { \frac {{S}^2 {A}}{\epsilon^3 {(1 - \gamma)}^3} } \right)
$$
for the $\rmax$ algorithm as analyzed by \namecite{kakade03}.  Using
the notation of \namecite{kakade03}\footnote{The use of {\it normalized} value
functions reduces the dependence on $1/(1-\gamma)$.}, our bound of
Theorem \ref{p:delayed_pac} reduces to
$$
\tilde{O}\left({
\frac{{S}{A}}{{\epsilon}^4{(1-\gamma)}^4}
}\right).
$$
It is clear that there is no strict improvement of the bounds, since a
factor of $S$ is being traded for one of $1/(\epsilon (1-\gamma))$.
Nonetheless, to the extent that the dependence on ${S}$ and $A$ is of
primary importance, this tradeoff is a net improvement.
We also note that the best lower bound known for the problem, due
to \namecite{kakade03}, is $\tilde{\Omega}\left({
{{S}{A}}/{({\epsilon}{(1-\gamma)})} }\right)$.

%For completeness, we also analyzed a version of Delayed
%Q-learning for finding a near-optimal policy with respect to a
%hard horizon time $H$ (see \namecite{kakade03}).
%%See \namecite{kakade03} for a discussion
%%of how to evaluate hard horizon policies in an online exploration
%%setting.
%We find that the agent will follow an $\epsilon$-optimal policy
%for horizon $H$ on all but $\tilde{O}({SAH^5}/{\epsilon^4})$
%%\[ \tilde{O}\Bigg( \frac{SAH^5}{\epsilon^4} \Bigg) \]
%timesteps, with probability at least $1-\delta$.

Our analysis of Delayed Q-learning required that %the discount factor,
$\gamma$ be less than $1$.  The analyses of
\namecite{kakade03} and \namecite{kearns02}, among others, also
considered the case of $\gamma = 1$.  Here, instead of evaluating
a policy with respect to the infinite horizon, only the next $H$
action-choices of the agent contribute to the value function.  See
\namecite{kakade03} for a discussion of how to evaluate hard
horizon policies in an online exploration setting.  For
completeness, we also analyzed a version of Delayed Q-learning
that works in this setting.  We find that the agent will follow an
$\epsilon$-optimal policy for horizon $H$ on all but $\tilde{O}(
{SAH^5}/{\epsilon^4})$ timesteps, with probability at least
$1-\delta$.  In terms of the dependence on the number of states
($S$), this bound is an improvement (from quadratic to linear)
over previous bounds.


\section {Related Work}

There has been a great deal of theoretical work analyzing RL algorithms.  Early
results include proving that under certain conditions various
algorithms can, in the limit, compute the optimal value function from
which the optimal policy can be extracted
%\cite{Watkins92,bertsekas96}
\cite{Watkins92}. These convergence results make no
% ,littman96
performance guarantee after only a finite amount of experience.
\namecite{evendar03b} studied the convergence rate
of Q-learning.  They showed that, under a certain assumption, Q-learning
converges to a near-optimal value function in a polynomial number of
timesteps.  The result requires input of an exploration policy that, with high
probability, tries every state-action pair every $L$ timesteps (for
some polynomial $L$).  Such a policy may be hard to find in some MDPs
and is impossible in others.  The work by \namecite{fiechter94} proves
that efficient learning (PAC) is achievable, via a model-based algorithm, when the agent
has an action that {\it resets} it to a distinguished start state.

Other recent work has shown that various
model-based algorithms, including E$^3$
\cite{kearns02}, $\rmax$~\cite{brafman02}, and MBIE \cite{strehl05b}, are
PAC-MDP.  The bound from
Theorem \ref{p:delayed_pac} improves upon those bounds when only the
dependence of ${S}$ and ${A}$ is considered.  Delayed Q-learning is also
significantly more computationally efficient than these algorithms.
%any algorithm previously known to be PAC-MDP.

Delayed Q-learning can be viewed as an approximation of
the real-time dynamic programming algorithm \cite{Barto95}, with an
added exploration bonus (of $\epsilon_1$).  The algorithm and its analysis are also similar
to phased Q-learning and its analysis \cite{kearns99c}.  In both of the above works,
exploration is not completely dealt with.  In the former, the transition
matrix is given as input to the agent.  In the latter, an idealized
exploration policy, one that samples every state-action pair
simultaneously, is assumed to be provided to the agent.

% commented out for now -Alex
%The labeled RTDP algorithm of \namecite{bonet03} is a planning algorithm
%that detects state-actions for which a bellman update would result in at
%least a small change to the current Q-value estimates (see Equation
%\ref{e:delayed}).  Once identified, it updates these state-actions,
%until near-optimal convergence is accomplished.  The analysis of delayed
%Q-learning makes use of a similar intuition.  However, delayed Q-learning
%doesn't require input of the MDP, as does labeled RTDP.  In addition,
%the goals of our analysis (PAC in terms of policies) are not synonymous
%with those of labeled RTDP (fast convergence of value function).

\section {Conclusion}

We presented Delayed Q-learning, a provably efficient model-free
reinforcement-learning algorithm.  Its analysis solves an important open problem
in the community.  Future work includes closing the gap between the
upper and lower bounds on PAC-MDP learning (see Section \ref{s:main}).  More
important is how to extend the results, using
generalization, to richer world models with an infinite number of states
and actions.

\section*{Acknowledgments}

%{\small
Thanks to the National Science Foundation (IIS-0325281).
We also thank Yishay Mansour, Sham M. Kakade, Satinder Singh, and
our anonymous reviewers for suggestions.  Eric Wiewiora
contributed to this research as an intern at TTI-Chicago.
%}

%\nocite{aha:thesis90,fisher:aaai89,jones:mlj94,langley:book95,maloof:tr98,shrager:book90}

{\small
\bibliography{mlittman}
}
\bibliographystyle{mlapa}

\end{document}