Near-Optimal Reinforcement Learning in Polynomial Time.
We present new algorithms for reinforcement learning and prove that they have polynomial bounds on the resources required to achieve near-optimal return in general Markov decision processes. After observing that the number of actions required to approach the optimal return is lower bounded by the mixing time T of the optimal policy (in the undiscounted case) or by the horizon time T (in the discounted case), we then give algorithms requiring a number of actions and total computation time that are only polynomial in T and the number of states and actions, for both the undiscounted and discounted cases. An interesting aspect of our algorithms is their explicit handling of the Exploration-Exploitation trade-off.
Introduction
In reinforcement learning, an agent interacts with an unknown environment,
and attempts to choose actions that maximize its cumulative payo (Sut-
ton & Barto, 1998; Barto et al., 1990; Bertsekas & Tsitsiklis, 1996). The
environment is typically modeled as a Markov decision process (MDP), and
it is assumed that the agent does not know the parameters of this process,
but has to learn how to act directly from experience. Thus, the reinforcement
learning agent faces a fundamental trade-o between exploitation and
exploration (Bertsekas, 1987; Kumar & Varaiya, 1986; Thrun, 1992): that
is, should the agent exploit its cumulative experience so far, by executing
the action that currently seems best, or should it execute a dierent action,
with the hope of gaining information or experience that could lead to higher
future payos? Too little exploration can prevent the agent from ever converging
to the optimal behavior, while too much exploration can prevent the
agent from gaining near-optimal payo in a timely fashion.
There is a large literature on reinforcement learning, which has been
growing rapidly in the last decade. Many dierent algorithms have been
proposed to solve reinforcement learning problems, and various theoretical
results on the convergence properties of these algorithms have been proven.
For example, Watkins Q-learning algorithm guarantees asymptotic convergence
to optimal values (from which the optimal actions can be derived)
provided every state of the MDP has been visited an innite number of times
(Watkins, 1989; Watkins & Dayan, 1992; Jaakkola et al., 1994; Tsitsiklis,
1994). This asymptotic result does not specify a strategy for achieving this
innite exploration, and as such does not provide a solution to the inherent
exploitation-exploration trade-o. To address this, Singh et al. (1998) specify
two exploration strategies that guarantee both su-cient exploration for
asymptotic convergence to optimal actions, and asymptotic exploitation, for
both the Q-learning and SARSA algorithms (a variant of Q-learning) (Rum-
mery & Niranjan, 1994; Singh & Sutton, 1996; Sutton, 1995). Gullapalli and
Barto (1994) and Jalali and Ferguson (1989) presented algorithms that learn
a model of the environment from experience, perform value iteration on the
estimated model, and with innite exploration converge to the optimal policy
asymptotically.
These results, and to the best of our knowledge, all other results for
reinforcement learning in general MDPs, are asymptotic in nature, providing
no guarantee on either the number of actions or the computation time the
agent requires to achieve near-optimal performance.
On the other hand, non-asymptotic results become available if one considers
restricted classes of MDPs, if the model of learning is modied from
the standard one, or if one changes the criteria for success. Thus, Saul and
Singh (1996) provide an algorithm and learning curves (convergence rates)
for an interesting special class of MDPs problem designed to highlight a
particular exploitation-exploration trade-o. Fiechter (1994; 1997), whose
results are closest in spirit to ours, considers only the discounted-payo
case, and makes the learning protocol easier by assuming the availability of
a \reset" button that allows his agent to return to a set of start-states at
arbitrary times. Others have provided non-asymptotic results for prediction
in uncontrolled Markov processes (Schapire & Warmuth, 1994; Singh &
Dayan, 1998).
Thus, despite the many interesting previous results in reinforcement
learning, the literature has lacked algorithms for learning optimal behavior
in general MDPs with provably nite bounds on the resources (actions
and computation time) required, under the standard model of learning in
which the agent wanders continuously in the unknown environment. The results
presented in this paper ll this void in what is essentially the strongest
possible sense.
We present new algorithms for reinforcement learning, and prove that
they have polynomial bounds on the resources required to achieve near-optimal
payo in general MDPs. After observing that the number of actions
required to approach the optimal return is lower bounded, for any algorithm,
by the mixing time T of the optimal policy (in the undiscounted-payo
case) or by the horizon time T (in the discounted-payo case), we then give
algorithms requiring a number of actions and total computation time that
are only polynomial in T and the number of states, for both the undiscounted
and discounted cases. An interesting aspect of our algorithms is their rather
explicit handling of the exploitation-exploration trade-o.
Two important caveats apply to our current results, as well as all the
prior results mentioned above. First, we assume that the agent can observe
the state of the environment, which may be an impractical assumption for
some reinforcement learning problems. Second, we do not address the fact
that the state space may be so large that we will have to resort to methods
such as function approximation. While some results are available on reinforcement
learning and function approximation (Sutton, 1988; Singh et al.,
1995; Gordon, 1995; Tsitsiklis & Roy, 1996), and for partially observable
MDPs (Chrisman, 1992; Littman et al., 1995; Jaakkola et al., 1995), they
are all asymptotic in nature. The extension of our results to such cases is
left for future work.
The outline of the paper is as follows: in Section 2, we give standard
denitions for MDPs and reinforcement learning. In Section 3, we argue
that the mixing time of policies must be taken into consideration in order to
obtain nite-time convergence results in the undiscounted case, and make
related technical observations and denitions. Section 4 makes similar arguments
for the horizon time in the discounted case, and provides a needed
technical lemma. The heart of the paper is contained in Section 5, where
we state and prove our main results, describe our algorithms in detail, and
provide intuitions for the proofs of convergence rates. Section 6 eliminates
some technical assumptions that were made for convenience during the main
proofs, while Section 7 discusses some extensions of the main theorem that
were deferred for the exposition. Finally, in Section 8 we close with a discussion
of future work.
Preliminaries and Denitions
We begin with the basic denitions for Markov decision processes.
Denition 1 A Markov decision process (MDP) M on states
and with actions a
The transition probabilities P a
which for any action a,
and any states i and j, specify the probability of reaching state j after
executing action a from state i in M . Thus,
state i and action a.
The payo distributions, for each state i, with mean RM (i) (where
R max  RM (i)  0), and variance Var M (i)  Var max . These distributions
determine the random payo received when state i is visited.
For simplicity, we will assume that the number of actions k is a constant;
it will be easily veried that if k is a parameter, the resources required by
our algorithms scale polynomially with k.
Several comments regarding some benign technical assumptions that we
will make on payos are in order here. First, it is common to assume that
payos are actually associated with state-action pairs, rather than with
states alone. Our choice of the latter is entirely for technical simplicity,
and all of the results of this paper hold for the standard state-action pay-
os model as well. Second, we have assumed xed upper bounds R max and
Var max on the means and variances of the payo distributions; such a restriction
is necessary for nite-time convergence results. Third, we have
assumed that expected payos are always non-negative for convenience, but
this is easily removed by adding a su-ciently large constant to every payo.
Note that although the actual payos experienced are random variables
governed by the payo distributions, for most of the paper we will be able to
perform our analyses in terms of the means and variances; the only exception
will be in Section 5.5, where we need to translate high expected payos into
high actual payos.
We now move to the standard denition of a stationary and deterministic
policy in an MDP.
Denition 2 Let M be a Markov decision process over states
with actions a . A policy in M is a mapping
g.
Later we will have occasion to dene and use non-stationary policies, that
is, policies in which the action chosen from a given state also depends on
the time of arrival at that state.
An MDP M , combined with a policy , yields a standard Markov process
on the states, and we will say that  is ergodic if the Markov process
resulting from  is ergodic (that is, has a well-dened stationary distribu-
tion). For the development and exposition, it will be easiest to consider
MDPs for which every policy is ergodic, the so-called unichain MDPs (Put-
erman, 1994). In a unichain MDP, the stationary distribution of any policy
does not depend on the start state. Thus, considering the unichain case
simply allows us to discuss the stationary distribution of any policy without
cumbersome technical details, and as it turns out, the result for unichains
already forces the main technical ideas upon us. Our results generalize to
non-unichain (multichain) MDPs with just a small and necessary change to
the denition of the best performance we can expect from a learning algo-
rithm. This generalization to multichain MDPs will be given in Section 7.
In the meantime, however, it is important to note that the unichain assumption
does not imply that every policy will eventually visit every state,
or even that there exists a single policy that will do so quickly; thus, the
exploitation-exploration dilemma remains with us strongly.
The following denitions for nite-length paths in MDPs will be of repeated
technical use in the analysis.
Denition 3 Let M be a Markov decision process, and let  be a policy in
M . A T-path in M is a sequence p of T
of
The probability that p is traversed in M upon starting in state i 1 and executing
policy  is
Pr
We now dene the two standard measures of the return of a policy.
Denition 4 Let M be a Markov decision process, let  be a policy in M ,
and let p be a T -path in M . The (expected) undiscounted return along
in M is
(R
and the (expected) discounted return along p in M is
< 1 is a discount factor that makes future reward less valuable
than immediate reward. The T-step undiscounted return from state i is
U
Pr
and the T-step discounted return from state i is
Pr
where in both cases the sum is over all T -paths p in M that start at i. We
dene U
are in the unichain case, U
M (i) is independent of i, and we will simply write
U
M .
Furthermore, we dene the optimal T-step undiscounted return
from i in M by
U
fU
and similarly, the optimal T-step discounted return from i in M by
Also, U
are in the unichain case, U
M (i) is independent of i, and we will simply write
U
M . The existence of these limits is guaranteed in the unichain case.
Finally, we denote the maximum possible T -step return by G T
the undiscounted case G T
while in the discounted case G T
TR max .
3 The Undiscounted Case and Mixing Times
It is easy to see that if we are seeking results about the undiscounted return
of a learning algorithm after a nite number of steps, we need to take into
account some notion of the mixing times of policies in the MDP. To put it
simply, in the undiscounted case, once we move from the asymptotic return
to the nite-time return, there may no longer be a well-dened notion of
\the" optimal policy. There may be some policies which will eventually yield
high return (for instance, by nally reaching some remote, high-payo state),
but take many steps to approach this high return, and other policies which
yield lower asymptotic return but higher short-term return. Such policies
are simply incomparable, and the best we could hope for is an algorithm
that \competes" favorably with any policy, in an amount of time that is
comparable to the mixing time of that policy .
The standard notion of mixing time for a policy  in a Markov decision
process M quanties the smallest number T of steps required to ensure
that the distribution on states after T steps of  is within  of the stationary
distribution induced by , where the distance between distributions
is measured by the Kullback-Leibler divergence, the variation distance, or
some other standard metric. Furthermore, there are well-known methods
for bounding this mixing time in terms of the second eigenvalue of the transition
matrix P
M , and also in terms of underlying structural properties of
the transition graph, such as the conductance (Sinclair, 1993). It turns out
that we can state our results for a weaker notion of mixing that only requires
the expected return after T steps to approach the asymptotic return.
Denition 5 Let M be a Markov decision process, and let  be an ergodic
policy in M . The -return mixing time of  is the smallest T such that
for all T 0  T , jU
Suppose we are simply told that there is a policy  whose asymptotic
return U
exceeds some value R in an unknown MDP M , and that the
Reward R
Reward 0
1- D
Figure

1: A simple Markov process demonstrating that nite-time convergence
results must account for mixing times.
-return mixing time of  is T . In principle, a su-ciently clever learning
algorithm (for instance, one that managed to discover  \quickly") could
achieve return close to U
M  in not much more than T steps. Conversely,
without further assumptions on M or , it is not reasonable to expect any
learning algorithm to approach return U
M in many fewer than T steps. This
is simply because it may take the assumed policy  itself on the order of
T steps to approach its asymptotic return. For example, suppose that M
has just two states and only one action (see Figure 1): state 0 with payo
0, self-loop probability 1 , and probability  of going to state 1; and
absorbing state 1 with payo R >> 0. Then for small  and , the -return
mixing time is on the order of 1=; but starting from state 0, it really will
require on the order of 1= steps to reach the absorbing state 1 and start
approaching the asymptotic return R.
We now relate the notion of -return mixing time to the standard notion
of mixing time.
be a Markov decision process on N states, and let  be
an ergodic policy in M . Let T be the smallest value such that for all T 0  T ,
for any state i, the probability of being in state i after T 0 steps of  is within
of the stationary probability of i under . Then the -return
mixing time of  is at most 3TRmax
.
The proof of the lemma follows in a straightforward way from the linearity
of expectations, and is omitted. The important point is that the -return
mixing time is polynomially bounded by the standard mixing time, but may
in some cases be substantially smaller. This would happen, for instance, if
the policy quickly settles on a subset of states with common payo, but takes
a long time to settle to its stationary distribution within this subset. Thus,
we will choose to state our results for the undiscounted return in terms of
the -return mixing time, but can always translate into the standard notion
via Lemma 1.
With the notion of -return mixing time, we can now be more precise
about what type of result is reasonable to expect for the undiscounted case.
We would like a learning algorithm such that for any T , in a number of
actions that is polynomial in T , the return of the learning algorithm is close
to that achieved by the best policy among those that mix in time T . This
motivates the following denition.
Denition 6 Let M be a Markov decision process. We dene  T;
M to be the
class of all ergodic policies  in M whose -return mixing time is at most
T . We let opt( T;
M ) denote the optimal expected asymptotic undiscounted
return among all policies in  T;
M .
Thus, our goal in the undiscounted case will be to compete with the policies
in  T;
M in time that is polynomial in T , 1= and N . We will eventually
give an algorithm that meets this goal for every T and  simultaneously . An
interesting special case is when is the -mixing time of the
asymptotically optimal policy, whose asymptotic return is U  . Then in time
polynomial in T  , 1= and N , our algorithm will achieve return exceeding
U   with high probability. It should be clear that, modulo the degree of
the polynomial running time, such a result is the best that one could hope
for in general MDPs.
4 The Discounted Case and the Horizon Time
For the discounted case, the quantication of which policies a learning algorithm
is competing against is more straightforward, since the discounting
makes it possible in principle to compete against all policies in time proportional
to the horizon time. In other words, unlike in the undiscounted
case, the expected discounted return of any policy after T  1=(1
steps
approaches the expected asymptotic discounted return. This is made precise
by the following lemma.
be any Markov decision process, and let  be any policy
in M . If
then for any state i,
We call the value of the lower bound on T given above the -horizon time
for the discounted MDP M .
Proof: The lower bound on V
M (i) follows trivially from the denitions,
since all expected payos are nonnegative. For the upper bound, x any
innite path p, and let R 1 be the expected payos along this path.
Then
is the T -path prex of the innite path p. Solving
for T yields the desired bound on T ; since the inequality holds for every xed
path, it also holds for the distribution over paths induced by any policy .In the discounted case, we must settle for a notion of \competing" that
is slightly dierent than for the undiscounted case. The reason is that while
in the undiscounted case, since the total return is always simply averaged ,
a learning algorithm can recover from its \youthful mistakes" (low return
during the early part of learning), this is not possible in the discounted case
due to the exponentially decaying eects of the discounting factor. The
most we can ask for is that, in time polynomial in the -horizon time, the
learning algorithm has a policy that, from its current state, has discounted
return within  of the asymptotic optimal for that state. Thus, if time were
reinitialized to 0, with the current state being the start state, the learned
policy would have near-optimal expected return. This is the goal that our
algorithm will achieve for general MDPs in the discounted case.
5 Main Theorem
We are now ready to describe our new learning algorithms, and to state
and prove our main theorem: namely, that the new algorithms will, for a
general MDP, achieve near-optimal performance in polynomial time, where
the notions of performance and the parameters of the running time (mixing
and horizon times) have been described in the preceding sections. For ease
of exposition only , we will rst state the theorem under the assumption
that the learning algorithm is given as input a \targeted" mixing time T ,
and the optimal return opt( T;
achieved by any policy mixing within T
steps (for the undiscounted case), or the optimal value function V  (i) (for
the discounted case). This simpler case already contains the core ideas of
the algorithm and analysis, and these assumptions are entirely removed in
Section 6.
Theorem 3 (Main Theorem) Let M be a Markov decision process over N
states.
(Undiscounted case) Recall that  T;
M is the class of all ergodic policies
whose -return mixing time is bounded by T , and that opt( T;
M ) is the
optimal asymptotic expected undiscounted return achievable in  T;
M .
There exists an algorithm A, taking inputs ; -; N;T and opt( T;
such that the total number of actions and computation time taken by
A is polynomial in 1=; 1=-; N , T , and R max , and with probability at
least 1 -, the total actual return of A exceeds opt( T;
(Discounted case) Let V  (i) denote the value function for the policy
with the optimal expected discounted return in M . Then there exists
an algorithm A, taking inputs ; -; N and V  (i), such that the total
number of actions and computation time taken by A is polynomial
in 1=; 1=-; N , the horizon time
), and R max , and with
probability at least 1 -, A will halt in a state i, and output a policy
The remainder of this section is divided into several subsections, each
describing a dierent and central aspect of the algorithm and proof. The
full proof of the theorem is rather technical, but the underlying ideas are
quite intuitive, and we sketch them rst as an outline.
5.1 High-Level Sketch of the Proof and Algorithms
Although there are some dierences between the algorithms and analyses
for the undiscounted and discounted cases, for now it will be easiest to
think of there being only a single algorithm. This algorithm will be what is
commonly referred to as indirect or model-based : namely, rather than only
maintaining a current policy or value function, the algorithm will actually
maintain a model for the transition probabilities and the expected payos
for some subset of the states of the unknown MDP M . It is important
to emphasize that although the algorithm maintains a partial model of M ,
it may choose to never build a complete model of M , if doing so is not
necessary to achieve high return.
It is easiest to imagine the algorithm as starting by doing what we
will call balanced wandering . By this we mean that the algorithm, upon
arriving in a state it has never visited before, takes an arbitrary action
from that state; but upon reaching a state it has visited before, it takes the
action it has tried the fewest times from that state (breaking ties between
actions randomly). At each state it visits, the algorithm maintains the
obvious statistics: the average payo received at that state so far, and for
each action, the empirical distribution of next states reached (that is, the
estimated transition probabilities).
A crucial notion for both the algorithm and the analysis is that of a
known state. Intuitively, this is a state that the algorithm has visited \so
many" times (and therefore, due to the balanced wandering, has tried each
action from that state many times) that the transition probability and expected
payo estimates for that state are \very close" to their true values in
M . An important aspect of this denition is that it is weak enough that \so
many" times is still polynomially bounded, yet strong enough to meet the
simulation requirements we will outline shortly. The fact that the denition
of known state achieves this balance is shown in Section 5.2.
States are thus divided into three categories: known states, states that
have been visited before, but are still unknown (due to an insu-cient number
of visits and therefore unreliable statistics), and states that have not even
been visited once. An important observation is that we cannot do balanced
wandering indenitely before at least one state becomes known: by the
Pigeonhole Principle, we will soon start to accumulate accurate statistics at
some state. This fact will be stated more formally in Section 5.5.
Perhaps our most important denition is that of the known-state MDP .
If S is the set of currently known states, the current known-state MDP
is simply an MDP M S that is naturally induced on S by the full MDP M ;
brie
y, all transitions in M between states in S are preserved in M S , while all
other transitions in M are \redirected" in M S to lead to a single additional,
absorbing state that intuitively represents all of the unknown and unvisited
states.
Although the learning algorithm will not have direct access to M S , by
virtue of the denition of the known states, it will have an approximation
. The rst of two central technical lemmas that we prove (Section 5.2)
shows that, under the appropriate denition of known state, ^
good simulation accuracy : that is, the expected T -step return of any policy
M S is close to its expected T -step return in M S . (Here T is either the
mixing time that we are competing against, in the undiscounted case, or the
horizon time, in the discounted case.) Thus, at any time, ^
M S is a partial
model of M , for that part of M that the algorithm \knows" very well.
The second central technical lemma (Section 5.3) is perhaps the most
enlightening part of the analysis, and is named the \Explore or Exploit"
Lemma. It formalizes a rather appealing intuition: either the optimal (T -
step) policy achieves its high return by staying, with high probability, in
the set S of currently known states | which, most importantly, the algorithm
can detect and replicate by nding a high-return exploitation policy
in the partial model ^
S | or the optimal policy has signicant probability
of leaving S within T steps | which again the algorithm can detect and
replicate by nding an exploration policy that quickly reaches the additional
absorbing state of the partial model ^
Thus, by performing two o-line, polynomial-time computations on ^
(Section 5.4), the algorithm is guaranteed to either nd a way to get near-optimal
return in M quickly, or to nd a way to improve the statistics at
an unknown or unvisited state. Again by the Pigeonhole Principle, the
latter case cannot occur too many times before a new state becomes known,
and thus the algorithm is always making progress. In the worst case, the
algorithm will build a model of the entire MDP M , but if that does happen,
the analysis guarantees that it will happen in polynomial time.
The following subsections
esh out the intuitions sketched above, providing
the full proof of Theorem 3. In Section 6, we show how to remove
the assumed knowledge of the optimal return.
5.2 The Simulation Lemma
In this section, we prove the rst of two key technical lemmas mentioned in
the sketch of Section 5.1: namely, that if one
M is a su-ciently accurate
approximation of another MDP M , then we can actually approximate
the T -step return of any policy in M quite accurately by its T -step return
M .
Eventually, we will appeal to this lemma to show that we can accurately
assess the return of policies in the induced known-state MDP M S by computing
their return in the algorithm's approximation ^
(that is, we will
appeal to Lemma 4 below using the settings
important technical point is that the goodness of approximation required
depends only polynomially on 1=T , and thus the denition of known state
will require only a polynomial number of visits to the state.
We begin with the denition of approximation we require.
Denition 7 Let M and ^
M be Markov decision processes over the same
state space. Then we say that
M is an -approximation of M if:
For any state i,
RM (i)   R ^
For any states i and j, and any action a,
P a
We now state and prove the Simulation Lemma, which says that provided
M is su-ciently close to M in the sense just dened, the T -step return of
policies in ^
and M will be similar.
Lemma 4 (Simulation Lemma) Let M be any Markov decision process over
states.
(Undiscounted
M be an O((=(NTG T
of M . Then for any policy  in  T;=2
1 , and for any state i,
U
(Discounted Case) Let T  (1=(1
))), and let
M be an O(=(NTG T
)-approximation of M . Then for any policy
and any state i,
1 Note that the lemma for the undiscounted case is stated with respect to those policies
whose =2-return mixing time is T , as opposed to -return mixing time. However, the =2-
return and -return mixing times are linearly related by standard eigenvalue arguments.
Proof: Let us x a policy  and a start state i. Let us say that a
transition from a state i 0 to a state j 0 under action a is -small in M if
P a
. Then the probability that T steps from state i following
policy  will cross at least one -small transition is at most NT . This is
because the total probability of all -small transitions in M from any state i 0
under action (i 0 ) is at most N , and we have T independent opportunities
to cross such a transition. This implies that the total expected contribution
to either U
by the walks of  that cross at least one
-small transition of M is at most NTG T
Similarly, since P a
implies P a
M is an -
approximation of M ), the total contribution to either U
by the walks of  that cross at least one -small transition of M is at most
. We can thus bound the dierence between U
U
restricted to these walks by
. We will eventually determine a choice for  and solve
for .
Thus, for now we restrict our attention to the walks of length T that do
not cross any -small transition of M . Note that for any transition satisfying
P a
, we can convert the additive approximation
P a
to the multiplicative approximation
(1 )P a
=. Thus, for any T -path p that, under , does not cross any
-small transitions of M , we have
For any T -path p, the approximation error in the payos yields
and
Since these inequalities hold for any xed T -path that does not traverse any
-small transitions in M under , they also hold when we take expectations
over the distributions on such T -paths in M and ^
M induced by . Thus,
and
where the additive =4 terms account for the contributions of the T -paths
that traverse -small transitions under , as bounded by Equation (19).
For the upper bounds, we will use the following Taylor expansion:
Now to complete the analysis for the undiscounted case, we need two conditions
to hold:
and
because then
=2. The rst
condition would be satised if
solving for  we
obtain T=2  =8G T
or   =(4T G T
This value of  also implies
that is a constant and therefore satisfying the second condition
would require that
Recalling the earlier constraint given by Equation (19), if we choose
, then we nd that
and
=(4T G T
and are all satised by the choice of  given in the lemma. A
similar argument yields the desired lower bound, which completes the proof
for the undiscounted case. The analysis for the discounted case is entirely
analogous, except we must additionally appeal to Lemma 2 in order to relate
the T -step return to the asymptotic return. 2
The Simulation Lemma essentially determines what the denition of
known state should be: one that has been visited enough times to ensure
(with high probability) that the estimated transition probabilities and the
estimated payo for the state are all within O((=(NTG T
values. The following lemma, whose proof is a straightforward application
of Cherno bounds, makes the translation between the number of visits to
a state and the desired accuracy of the transition probability and payo
estimates.
Lemma 5 Let M be a Markov decision process. Let i be a state of M
that has been visited at least m times, with each action a having
been executed at least bm=kc times from i. Let ^
P a
M (ij) denote the empirical
probability transition estimates obtained from the m visits to i. For
with probability at least 1 -, we have
P a
for all states j and actions a, and
RM (i) RM
where Var (i)] is the maximum variance of the random
payos over all states.
Thus, we get our formal denition of known states:
Denition 8 Let M be a Markov decision process. We say that a state i
of M is known if each action has been executed from i at least
times.
5.3 The \Explore or Exploit" Lemma
Lemma 4 indicates the degree of approximation required for su-cient simulation
accuracy, and led to the denition of a known state. If we let S
denote the set of known states, we now specify the straightforward way in
which these known states dene an induced MDP. This induced MDP has
an additional \new" state, which intuitively represents all of the unknown
states and transitions.
Denition 9 Let M be a Markov decision process, and let S be any subset
of the states of M . The induced Markov decision process on S, denoted
S , has states S [ fs 0 g, and transitions and payos dened as follows:
For any state i 2 S, RMS all payos in M S are deterministic
(zero variance) even if the payos in M are stochastic.
For any action a, P a
MS is an absorbing state.
For any states any action a, P a
MS
(ij). Thus,
transitions in M between states in S are preserved in M S .
For any state i 2 S and any action a, P a
MS (is 0
2S P a
(ij). Thus,
all transitions in M that are not between states in S are redirected to
s 0 in M S .
Denition 9 describes an MDP directly induced on S by the true unknown
MDP M , and as such preserves the true transition probabilities between
states in S. Of course, our algorithm will only have approximations to
these transition probabilities, leading to the following obvious approximation
to
M denote the obvious empirical approximation
to
S is the natural approximation to M S . The following lemma
establishes the simulation accuracy of ^
immediately from
Lemma 4 and Lemma 5.
Lemma 6 Let M be a Markov decision process, and let S be the set of
currently known states of M . Then with probability at least 1 -,
(Undiscounted Case) For any policy  in  T;=2
MS , and for any state i,
U
MS
MS
MS
(Discounted Case) Let T  (1=(1
))). Then for
any policy  and any state i,
MS (i)   V
MS (i)  V
MS (37)that is, the states of ^
are simply all the states visited so far, the transition probabilities
of
M are the observed transition frequencies, and the rewards are the observed
rewards
Let us also observe that any return achievable in M S (and thus approximately
achievable in ^
achievable in the \real world"
Lemma 7 Let M be a Markov decision process, and let S be the set of
currently known states of M . Then for any policy  in M , any state i 2 S,
and any T , U
MS
MS
Proof: Follows immediately from the facts that M S and M are identical
on S, the expected payos are non-negative, and that outside of S no payo
is possible in M S . 2
We are now at the heart of the analysis: we have identied a \part" of the
unknown MDP M that the algorithm \knows" very well, in the form of the
approximation
M S to M S . The key lemma follows, in which we demonstrate
the fact that M S (and thus, by the Simulation Lemma, ^
must always
provide the algorithm with either a policy that will yield large immediate
return in the true MDP M , or a policy that will allow rapid exploration of
an unknown state in M (or both).
Lemma 8 (Explore or Exploit Lemma) Let M be any Markov decision pro-
cess, let S be any subset of the states of M , and let M S be the induced
Markov decision process on M . For any i 2 S, any T , and any 1 >  > 0,
either there exists a policy  in M S such that U
MS
(respectively, V
MS
there exists a policy  in M S
such that the probability that a walk of T steps following  will terminate in
Proof: We give the proof for the undiscounted case; the argument for the
discounted case is analogous. Let  be a policy in M satisfying U
U
suppose that U
MS
witnesses the claim of the lemma). We may write
U
Pr
Pr
r
Pr
where the sums are over, respectively, all T -paths p in M that start in state
all T -paths q in M that start in state i and in which every state in q
is in S, and all T -paths r in M that start in state i and in which at least
one state is not in S. Keeping this interpretation of the variables p; q and r
xed, we may write
Pr
Pr
MS [q]U MS (q)  U
MS (i; T
The equality follows from the fact that for any path q in which every state
is in S, Pr
MS [q] and UM and the inequality from
the fact that U
MS takes the sum over all T -paths in M S , not just those
that avoid the absorbing state s 0 . Thus
Pr
which implies that X
r
Pr
r
Pr
r
Pr
and so X
r
Pr
as desired. 2
5.4 O-line Optimal Policy Computations
Let us take a moment to review and synthesize. The combination of Lemmas
6, 7 and 8 establishes our basic line of argument:
At any time, if S is the set of current known states, the T -step return
of any policy  in ^
lower bounds the T -step return
of (any extension of)  in M .
At any time, there must either be a policy in ^
whose T -step return
in M is nearly optimal, or there must be a policy in ^
M S that will
quickly reach the absorbing state | in which case, this same policy,
executed in M , will quickly reach a state that is not currently in the
known set S.
In this section, we discuss how with two o-line, polynomial-time computations
, we can nd both the policy with highest return (the
exploitation policy), and the one with the highest probability of reaching
the absorbing state in T steps (the exploration policy). This essentially
follows from the fact that the standard value iteration algorithm from the
dynamic programming literature is able to nd T -step optimal policies for
an arbitrary MDP with N states in O(N 2 T ) computation steps for both the
discounted and the undiscounted cases.
For the sake of completeness, we present the undiscounted and discounted
value iteration algorithms (Bertsekas & Tsitsiklis, 1989) below. The
optimal T -step policy may be non-stationary, and is denoted by a sequence
t (i) is the optimal action to be taken from
state i on the t th step.
T-step Undiscounted Value Iteration:
Initialize: for all
For
for all i, U t (i)
MS
MS
(ij)U t+1 (j)
for all i
MS
MS
(ij)U t+1 (j)]
Undiscounted value iteration works backwards in time, rst producing the
optimal policy for time step T , then the optimal policy for time step T 1,
and so on. Observe that for nite T a policy that maximizes cumulative
T -step return will also maximize the average T -step return.
T-step Discounted Value Iteration:
Initialize: for all
For
for all
MS
a
MS (ij)V t+1 (j)
for all i
MS
MS
(ij)V t+1 (j)]
Again, discounted value iteration works backwards in time, rst producing
the optimal policy for time step T , then the optimal policy for time step
T 1, and so on.
Note that the total computation involved is O(N 2 T ) for both the discounted
and the undiscounted cases.
Our use of value iteration will be straightforward: at certain points in
the execution of the algorithm, we will perform value iteration o-line twice:
once on ^
(using either the undiscounted or discounted version, depending
on the measure of return), and a second time on what we will denote ^
(on which the computation will use undiscounted value iteration, regardless
of the measure of return).
The
S has the same transition probabilities as
dierent
payos: in ^
S , the absorbing state s 0 has payo R max and all other states
have payo 0. Thus we reward exploration (as represented by visits to s 0 )
rather than exploitation. If ^
is the policy returned by value iteration on
0 is the policy returned by value iteration on ^
guarantees that either the T -step return of ^
from our current known state
approaches the optimal achievable in M (which for now we are assuming we
know, and can thus detect), or the probability that ^
that the execution of ^  0 in M reaches an unknown or unvisited state in T
steps with signicant probability (which we can also detect).
Putting it All Together
All of the technical pieces we need are now in place, and we now give a
more detailed description of the algorithm, and tie up some loose ends. In
Section 6, we remove the assumption that we know the optimal returns that
can be achieved in M .
In the sequel, we will use the expression balanced wandering to denote
the steps of the algorithm in which the current state is not a known state,
and the algorithm executes the action that has been tried the fewest times
before from the current state. Note that once a state becomes known, by
denition it is never involved in a step of balanced wandering again. We use
m known to denote the number of visits required to a state before it becomes a
known state (dierent for the undiscounted and discounted cases), as given
by Denition 8.
We call the algorithm the Explicit Explore or Exploit (or
because whenever the algorithm is not engaged in balanced wandering, it
performs an explicit o-line computation on the partial model in order to
nd a T -step policy guaranteed to either exploit or explore. In the description
that follows, we freely mix the description of the steps of the algorithm
with observations that will make the ensuing analysis easier to digest.
The Explicit Explore or Exploit
(Initialization) Initially, the set S of known states is empty.
(Balanced Wandering) Any time the current state is not in S, the
algorithm performs balanced wandering.
(Discovery of New Known States) Any time a state i has been visited
known times during balanced wandering, it enters the known set S,
and no longer participates in balanced wandering.
Observation: Clearly, after N(m known 1)+1 steps of balanced wan-
dering, by the Pigeonhole Principle some state becomes known. This
is the worst case, in terms of the time required for at least one state
to become known. More generally, if the total number of steps of balanced
wandering the algorithm has performed ever exceeds Nm known ,
then every state of M is known (even if these steps of balanced wandering
are not consecutive). This is because each known state can
account for at most m known steps of balanced wandering.
(O-line Optimizations) Upon reaching a known state i 2 S during
balanced wandering, the algorithm performs the two o-line optimal
policy computations on ^
S described in Section 5.4:
{ (Attempted Exploitation) If the resulting exploitation policy ^
achieves return from i in ^
S that is at least U  =2 (respec-
tively, in the discounted case, at least V  (i) =2), the algorithm
executes
for the next T steps (respectively, halts and outputs
Here T is the given =2-mixing time given to the algorithm
as input (respectively, the horizon time).
{ (Attempted Exploration) Otherwise, the algorithm executes the
resulting exploration policy (derived from the o-line computation
steps in M , which by Lemma 8 is guaranteed
to have probability at least =(2G T
leaving the set S.
(Balanced Wandering) Any time an attempted exploitation or attempted
exploration visits a state not in S, the algorithm immediately
resumes balanced wandering.
Observation: Thus, every action taken by the algorithm in M is
either a step of balanced wandering, or is part of a T -step attempted
exploitation or attempted exploration.
This concludes the description of the algorithm; we can now wrap up
the analysis.
One of the main remaining issues is our handling of the condence parameter
- in the statement of the main theorem: for both the undiscounted
and discounted case, Theorem 3 ensures that a certain performance guarantee
is met with probability at least 1 -. There are essentially three dierent
sources of failure for the algorithm:
At some known state, the algorithm actually has a poor approximation
to the next-state distribution for some action, and thus ^
S does not
have su-ciently strong simulation accuracy for M S .
Repeated attempted explorations fail to yield enough steps of balanced
wandering to result in a new known state.
(Undiscounted case only) Repeated attempted exploitations fail to result
in actual return near U  .
Our handling of the failure probability - is to simply allocate -=3 to
each of these sources of failure. The fact that we can make the probability
of the rst source of failure (a \bad" known state) controllably small is
quantied by Lemma 6. Formally, we use - Lemma 6 to meet
the requirement that all states in M S be known simultaneously.
For the second source of failure (failed attempted explorations), a standard
Cherno bound analysis su-ces: by Lemma 8, each attempted exploration
can be viewed as an independent Bernoulli trial with probability
at least =(2G T
least one step of balanced wandering).
In the worst case, we must make every state known before we can exploit,
requiring Nm known steps of balanced wandering. The probability of having
fewer than Nm known steps of balanced wandering will be smaller than -=3
if the number of (T -step) attempted explorations is
O((G T
We can now nish the analysis for the discounted case. In the discounted
case, if we ever discover a policy ^
whose return from the current state i in
M S is close to V  (i) (attempted exploitation), then the algorithm is nished
by arguments already detailed | since (with high probability) ^
M S is a very
accurate approximation of part of M , ^
must be a near-optimal policy from
in M as well (Lemma 7). As long as the algorithm is not nished, it must
be engaged in balanced wandering or attempted explorations, and we have
already bounded the number of such steps before (with high probability)
every state is in the known set S. If and when S does contain all states
of M , then ^
M S is actually an accurate approximation of the entire MDP
M , and then Lemma 8 ensures that exploitation must be possible (since
exploration is not). We again emphasize that the case in which S eventually
contains all of the states of M is only the worst case for the analysis | the
algorithm may discover it is able to halt with a near-optimal exploitation
policy long before this ever occurs.
Using the value of m known given for the discounted case by Denition 8,
the total number of actions executed by the algorithm in the discounted case
is thus bounded by T times the maximum number of attempted explorations,
given by Equation (45), for a bound of
The total computation time is bounded by O(N 2 T ) (the time required for
the o-line computations) times the maximum number of attempted explo-
rations, giving
For the undiscounted case, things are slightly more complicated, since
we do not want to simply halt upon nding a policy whose expected return
is near U  , but want to achieve actual return approaching U  , which
is where the third source of failure (failed attempted exploitations) enters.
We have already argued that the total number of T -step attempted explorations
the algorithm can perform before S contains all states of M is
polynomially bounded. All other actions of the algorithm must be accounted
for by T -step attempted exploitations. Each of these T -step attempted exploitations
has expected return at least U  =2. The probability that the
actual return, restricted to just these attempted exploitations, is less than
U  3=4, can be made smaller than -=3 if the number of blocks exceeds
O((1=) 2 log(1=-)); this is again by a standard Cherno bound analysis.
However, we also need to make sure that the return restricted to these
exploitation blocks is su-cient to dominate the potentially low return of
the attempted explorations. It is not di-cult to show that provided the
number of attempted exploitations exceeds O(G T
times the number
of attempted explorations (bounded by Equation (45)), both conditions are
satised, for a total number of actions bounded by O(T=) times the number
of attempted explorations, which is
The total computation time is thus O(N 2 T=) times the number of attempted
explorations, and thus bounded by
This concludes the proof of the main theorem. We remark that no serious
attempt to minimize these worst-case bounds has been made; our immediate
goal was to simply prove polynomial bounds in the most straightforward
manner possible. It is likely that a practical implementation based on the
algorithmic ideas given here would enjoy performance on natural problems
that is considerably better than the current bounds indicate. (See Moore
and Atkeson, 1993, for a related heuristic algorithm.)
6 Eliminating Knowledge of the Optimal Returns
and the Mixing Time
In order to simplify our presentation of the main theorem, we made the assumption
that the learning algorithm was given as input the targeted mixing
time T and the optimal return opt( T;
achievable in this mixing time (in
the undiscounted case), or the value function V  (i) (in the discounted case;
the horizon time T is implied by knowledge of the discounting factor
In this section, we sketch the straightforward way in which these assumptions
can be removed without changing the qualitative nature of the results,
and brie
y discuss some alternative approaches that may result in a more
practical version of the algorithm.
Let us begin by noting that knowledge of the optimal returns opt( T;
or V  (i) is used only in the Attempted Exploitation step of the algorithm,
where we must compare the return possible from our current state in ^
with the best possible in the entire unknown MDP M . In the absence of
this knowledge, the Explore or Exploit Lemma (Lemma ensures us that
it is safe to have a bias towards exploration. More precisely, any time we
arrive in a known state i, we will rst perform the Attempted Exploration
o-line computation on the modied known-state MDP ^
S described in
Section 5.4, to obtain the optimal exploration policy ^  0 . Since it is a simple
matter to compute the probability that ^  0 will reach the absorbing state s 0
of
S in T steps, we can then compare this probability to the lower bound
As long as this lower bound is exceeded, we may
0 in an attempt to visit a state not in S. If this lower bound is not
guarantees that the o-line computation on ^
S in the
Attempted Exploitation step must result in an exploitation policy ^
that is
close to optimal. As before, in the discounted case we halt and output ^
while in the undiscounted case we execute ^
in M and continue.
Note that this exploration-biased solution to removing knowledge of
results in the algorithm always exploring all states of
M that can be reached in a reasonable amount of time, before doing any ex-
ploitation. Although this is a simple way of removing the knowledge while
keeping a polynomial-time algorithm, practical variants of our algorithm
might pursue a more balanced strategy, such as the standard approach of
having a strong bias towards exploitation instead, but doing enough exploration
to ensure rapid convergence to the optimal performance. For instance,
we can maintain a schedule (t) 2 [0; 1], where t is the total number of actions
taken in M by the algorithm so far. Upon reaching a known state, the
algorithm performs Attempted Exploitation (execution of ^
Attempted Exploration (execution of ^
(t). For choices such as analyses ensure that we
will still explore enough that ^
S will, in polynomial time, contain a policy
whose return is near the optimal of M , but the return we have enjoyed
in the meantime may be much greater than the exploration-biased solution
given above. Note that this approach is similar in spirit to the \-greedy"
method of augmenting algorithms such as Q-learning with an exploration
component, but with a crucial dierence: while in -greedy exploration, we
with probability (t) attempt a single action designed to visit a rarely visited
state, here we are proposing that with probability (t) we execute a
multi-step policy for reaching an unknown state, a policy that is provably
justied by ^
S .
For the undiscounted case, it still remains to remove our assumption
that the algorithm knows the targeted mixing time T . Indeed, we would
like to state our main theorem for any value of T : that is, for any T , as long
as we run the algorithm for a number of steps that is polynomial in T and
the other parameters, the total return will exceed opt( T;
probability. This is easily accomplished: ignoring all other parameters, we
already have an algorithm A(T ) that, given T as input, runs for P (T ) steps
for some xed polynomial P () and meets the desired criterion. We now
propose a new algorithm A 0 , which does not need T as input, and simply
runs A sequentially for :. For any T , the amount of time A 0
must be run before A 0 has executed A(T ) is
which is still polynomial in T . We just need to run A 0 for su-ciently many
steps after the rst steps to dominate any low-return periods that took
place in those P 0 (T ) steps, similar to the analysis done for the undiscounted
case towards the end of Section 5.5. We again note that this solution, while
su-cient for polynomial time, is far from the one we would implement in
practice: for instance, we would clearly want to modify the algorithm so
that the many sequential executions of A shared and accumulated common
partial models of M .
7 The Multichain Case
The main issue in extending our results to arbitrary multichain MDPs is that
the asymptotic undiscounted return for any policy  is not independent of
the start state. This makes the undiscounted case for multichain MDPs
look a lot like the usual discounted case. Indeed, our results extend to arbitrary
multichain MDPs in the discounted case without any modication.
Therefore, one way to deal with the undiscounted-case multichain MDPs is
to only ask that given polynomial time our algorithm will be in a state for
which it has a policy that has an expected return that is near-optimal for
that state. Another way is to modify what we can expect when we compete
against a policy: instead of expecting to compete against the largest asymptotic
return over any start state for that policy, we can compete against
the lowest asymptotic return over any start state for that policy. Thus, we
modify Denitions 5 and 6 as follows:
be a Markov decision process, and let  be any policy
in M . The -return mixing time of  is the smallest T such that for all
M (i)j   for all i.
Definition 6 Let M be an arbitrary Markov decision process. We dene
M to be the class of all policies in M whose -return mixing time is at
most T . We let opt( T;
M (i)], be the optimal expected
asymptotic undiscounted return among all policies in  T;
M .
Under these rened denitions, all of our undiscounted-case results on
unichain MDPs extend without modication to arbitrary MDPs.
8 Future Work
There are a number of interesting lines for further research.
Practical implementation. Although the polynomial bounds proven
here are far too large to immediately claim the practical relevance of
our algorithm, we feel that the underlying algorithmic ideas are very
promising and will eventually result in a competitive algorithm. We
are currently examining the practical issues and choices that arise for
an implementation, some of which were discussed brie
y in Section 6,
and we hope to report on an implementation and experiments soon.
A model-free version. Partially related to the last item, it would
be nice to nd an algorithm similar to ours that did not require maintaining
a partial model, but only a policy (or perhaps several). We
are currently investigating this as well.
Large state spaces. It would be interesting to study the applicability
of recent methods for dealing with large state spaces, such as function
approximation, to our algorithm. This has been recently investigated
in the context of factored MDPs (Kearns & Koller, 1999).

Acknowledgements

We give warm thanks to Tom Dean, Tom Dietterich, Tommi Jaakkola, Leslie
Kaelbling, Michael Littman, Lawrence Saul, Terry Sejnowski, and Rich Sutton
for valuable comments. Satinder Singh was supported by NSF grant
IIS-9711753 for the portion of this work done while he was at the University
of Colorado, Boulder.



--R

Sequential decision problems and neural networks.
Dynamic Programming: Deterministic and Stochastic Models.
Parallel and Distributed Compu- tation: Numerical Methods

Athena Scienti


Expected mistake bound model for on-line reinforcement learning
Stable function approximation in dynamic program- ming
Convergence of indirect adaptive asynchronous value iteration algorithms.
On the convergence of stochastic iterative dynamic programming algorithms.
Reinforcement learning algorithm for partially observable Markov decision problems.
A distributed asynchronous algorithm for expected average cost dynamic programming.

Stochastic Systems: Estimation

Markov decision processes

Learning curve bounds for markov decision processes with undiscounted rewards.
On the worst-case analysis of temporal-dierence learning algorithms
Machine Learning:
Algorithms for random generation and counting: a Markov chain approach.
Analytical mean squared error curves for temporal di
Reinforcement learning with soft state aggregation.
Convergence results for single-step on-policy reinforcement learning algo- rithms
Reinforcement learning with replacing eligibility traces.

Generalization in reinforcement learning: Successful examples using sparse coarse coding.
Reinforcement Learning: An Introduc- tion
The role of exploration in learning control.
Asynchronous stochastic approximation and Q- learning

Learning from Delayed Rewards.

--TR

--CTR
David Wingate , Kevin D. Seppi, P3VI: a partitioned, prioritized, parallel value iterator, Proceedings of the twenty-first international conference on Machine learning, p.109, July 04-08, 2004, Banff, Alberta, Canada
Alexander L. Strehl , Michael L. Littman, A theoretical analysis of Model-Based Interval Estimation, Proceedings of the 22nd international conference on Machine learning, p.856-863, August 07-11, 2005, Bonn, Germany
Alexander L. Strehl , Lihong Li , Eric Wiewiora , John Langford , Michael L. Littman, PAC model-free reinforcement learning, Proceedings of the 23rd international conference on Machine learning, p.881-888, June 25-29, 2006, Pittsburgh, Pennsylvania
Shie Mannor , Duncan Simester , Peng Sun , John N. Tsitsiklis, Bias and variance in value function estimation, Proceedings of the twenty-first international conference on Machine learning, p.72, July 04-08, 2004, Banff, Alberta, Canada
Reveliotis , Theologos Bountourelis, Efficient PAC Learning for Episodic Tasks with Acyclic State Spaces, Discrete Event Dynamic Systems, v.17 n.3, p.307-327, September 2007
Carlos Diuk , Alexander L. Strehl , Michael L. Littman, A hierarchical approach to efficient reinforcement learning in deterministic domains, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
Eyal Even-Dar , Shie Mannor , Yishay Mansour, Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems, The Journal of Machine Learning Research, 7, p.1079-1105, 12/1/2006
Daniela Pucci De Farias , Nimrod Megiddo, Combining expert advice in reactive environments, Journal of the ACM (JACM), v.53 n.5, p.762-799, September 2006
Pieter Abbeel , Andrew Y. Ng, Exploration and apprenticeship learning in reinforcement learning, Proceedings of the 22nd international conference on Machine learning, p.1-8, August 07-11, 2005, Bonn, Germany
Daniela Pucci de Farias , Benjamin Van Roy, A Cost-Shaping Linear Program for Average-Cost Approximate Dynamic Programming with Performance Guarantees, Mathematics of Operations Research, v.31 n.3, p.597-620, August 2006
Amol Deshpande , Zachary Ives , Vijayshankar Raman, Adaptive query processing, Foundations and Trends in Databases, v.1 n.1, p.1-140, January 2007
markov decision processes;reinforcement learning;exploration versus exploitation