Efficient approximate planning in continuous space Markovian decision problems.
Monte-Carlo planning algorithms for planning in continuous state-space, discounted Markovian Decision Problems (MDPs) having a smooth transition law and a finite action space are considered. We prove various polynomial complexity results for the considered algorithms, improving upon several known bounds.
Introduction
MDPs provide a clean and simple, yet fairly rich framework for studying various aspects of
intelligence, such as, e.g., planning. A well-known practical limitation planning in MDPs
is called the curse of dimensionality [1], referring to the exponential rise in the resources
required to compute (even approximate) solutions to an MDP as the size of the MDP (the
number of state variables) increases. For example, conventional dynamic programming
(DP) algorithms, such as value- or policy-iteration scale exponentially with the size even
if they are used as subroutines to sophisticated multigrid algorithms [4]. Moreover, the
curse of dimensionality is not akin to any kind of special algorithm as shown by a result
of Chow and Tsitsiklis [3].
Recently, Kearns et al. have shown that a certain on-line, tree building algorithm avoids
the curse of dimensionality in discounted MDPs [8]. Recently, this result has also been
extended to partially observable MDPs (POMDPs) by the same authors [7]. The bounds
Homepage http://victoria.mindmaker.hu/~szepes
in these two papers are independent of the size of the state space, but scale exponentially
with 1
, the eective horizon-time, where
is the discount factor of the MDP.
In this paper we consider another on-line planning algorithm that will be shown to
scale polynomially with the horizon-time, as well. The price of this is that we have to
assume more regularity on the class of models in which the new results will be true. In
particular, we will restrict ourselves to stochastic MDPs with nite action spaces and state
space assume that the transition probability kernel of the MDPs are
subject to the Lipschitz-condition jp(x
for any states
action a 2 A. Here L p > 0 is a given xed number (our upper bounds
will be poly-logarithmic in L p ) and kk 1
denotes the ' 1 norm of vectors. Another restriction
(quite common in the literature) that we will assume is the uniform boundedness of the
transition probabilities (the bound shall be denoted by K p ) and of the immediate rewards
(bound denoted by K r ). Further, our bounds will depend on the dimension of the state
space, d. 1
The idea of the considered algorithms largely originates in the algorithm considered
by Rust [12], who studied an even more restricted class of problems for which he proved
the following result: Fix an MDP. Call a random, real-valued function ^
V with domain
"-optimal in the mean if E


", where V  is the optimal value function
underlying the MDP and kk is the maximum-norm and the expectation is taken over
the random function ^
. Given any " > 0, the algorithm builds up a (random) cache C "
and then, given any x 2 X and using the cache C " , the algorithm draws samples from a
being "-optimal in the mean. Rust has shown that both phases
of the algorithm are polynomial in jAj, K r =", L p , L r , d, K r , K p , 1=(1
the Lipschitz factor of the immediate rewards. Note that Rust's bound scales polynomialy
with the eective horizon-time, so all we need to do is to extend his algorithm to planning
in such a way that this property is kept.
The following algorithm , yielding almost optimal policies with high probability, is
such an algorithm: Fix the random sample N and consider ^
V and a state x. Using
Markov's inequality we get that P(k ^
if we could compute
R
dy then a contraction argument would show that
drawing
samples is sucient for ensuring the "-optimality of  with probability at least 1 . Note
that in this bound the number of samples depends polynomially on 1=, { ideally one
would like to have a poly-logarithmic dependence on 1=. Furthermore, carrying out the
above calculations requires the evaluation of jAj integrals over the state space, that must
themselves be approximated. 2 Clearly, the bound that follows in this way will majorize
the bound obtained above by Markov's inequality, and will still depend polynomially on
1=. One can also obtain a uniformly optimal policy by re-drawing the random samples
1 The bounds developed by Kearns et. al do not exhibit any dependence on the state space.
One might either want to reuse the samples drawn earlier or draw new samples. The second approach
is easier to analyze, whilst the rst one may appear more elegant for some.
for each query (this algorithm does not have an o-line phase). Bounds on the number of
samples and the number of steps of the computation can be computed by some tedious
calculations for this case as well in the above manner.
The main result of this article is the sharpening of the estimates sketched above by the
application of maximal inequalities. In particular, our estimate will be poly-logarithmic
in 1= and L p (instead of being polynomial in them) and we drop the Lipschitz continuity
restriction of the immediate rewards. Further, our bound for the number of samples will be
poly-logarithmic in the size of the action space, as well. We will also derive novel bounds
for the complexity of calculating uniformly optimal policies using the algorithm outlined
above.
The organization of the paper is as follows: In Section 2 we provide the necessary
background. The algorithm is given in Section 3, the main result of the paper is formulated
in Section 4. The proof of the main result is given in Section 5, and conclusions are drawn
in Section 6.
Preliminaries
We assume that the reader is familiar with the basics of the theory of MDPs. Readers who
lack the necessary background are referred to the book of Dynkin and Yuskevich [6] or the
more recent books [2] and [10].
2.1 Notation
refers to the ' p norm of vectors and the L p norm of functions,
depending on the type of its argument. Lip p denotes the set of mappings that are Lipschitz-continuous
in the norm kk means that there exists a positive constant L > 0
s.t. kf(x) f(y)k p  L kx yk p (domains of the mappings are suppressed). L is called
the k  k p -Lipschitz constant of f . Lip p (
denotes the set of mappings whose kk p
Lipschitz constant is not larger than
. A mapping T is called a contraction in the norm kk p
< 1. For brevity, the maximum-norm kk 1 will be denoted
by kk. Let V be any set, T : V!V and S : V!V. Then the mapping
by V. The set of natural numbers will be denoted by N , the set of reals
by R. If t 2 N then T t denotes the map that is the product of T with itself t-times. We say
that holds for all v 2 V. ! will in general denote an elementary event
of the probability space under consideration, lhs means \left-hand-side", and rhs means
\right-hand-side". We dene B(X
for K > 0, BK (X g.
2.2 The Model
Let us consider the continuous space discounted MDP given by (X ; A; p;
is the state space, A is the action space, p is a measurable transition

Table

1: Pseudo-code of the algorithm
(model parameters).
1. Compute t and N as dened in Theorem 5.18.
2. Draw independent samples uniformly distributed over X .
3. Compute
according to (2).
4. Let v
5. Repeat t times: v i :=
g.
6. Let a
g.
7. Return a  .
law:
is a measurable
function, called the reward function and 0 <
< 1 is the discount factor. We further
assume the followings:
Assumption 2.1. A is nite.
Assumption 2.2. There exist constants K
A.
Assumption 2.3. There exists some constant K r > 0 s.t. krk 1 < K r .
3 The Algorithm
First, we give the pseudo-code of the on-line planning algorithm that yields uniformly
optimal policies and then we introduce the formalism required to present the main results
and the sketches of the proofs. The pseudo-code of the algorithm can be seen in Table 1.
Note that at the expense of increasing the computation time one may downscale the storage
requirement of the algorithm from O(N 2 ) to O(N) if Step 3 of the algorithm is omitted.
Then Equation (2) must be used in Steps 5 and 6. Note that one may still precompute the
normalizing factor of (2) for speeding up the computations since the storage requirements
for these normalizing factors depend only linearly on N .
Now, we introduce the notation necessary to state the main results. Let T a
B(X ) be dened by
Z
Here a 2 A is arbitrary and the integral should be understood here and in what follows
over X . For a stationary policy dened by
Finally, let the Bellman-operator dened by
a2A
Under our assumptions, T is known to have a unique xed-point, V  , called the optimal-
value function. V  is known to be uniformly bounded. It is also known that any (sta-
is optimal in the sense that for any
given initial state the total expected discounted return resulting from the execution of
is maximal. (The execution of a policy  means the execution of action (x)
whenever the actual state is x.) A policy is called myopic or greedy w.r.t. the function
our case the action set A is nite, the existence of a
myopic policy is guaranteed for any given uniformly bounded function V .
Now let x us denote
be dened by
where
0; otherwise:
(2)
Similarly,
a2A
be dened by
Throughout the paper we are going to work with independent random variables
being uniformly distributed over X . 3 X 1:N will be used to denote (X
the random operators ^
TN a , ^
TN  and ^
TN by the respective equations
TN
TN is called the random Bellman-operator and is intended to approximate the true
Bellman-operator T .
3 The uniform distribution is used for simplicity only. Any other sampling distribution with support
covering X could be used if the algorithm is modied appropriately (importance sampling). The form
of the ideal sampling distribution is far from being clear since a single sample-set is used to estimate an
innite number of integrals. The form of the ideal distribution should be the subject of future research.
dened by
dened by
dened by
a2A
and, nally, let ^
dened by
a2A
The following proposition is at the heart of the proposed computational mechanism:
Proposition 3.1. For any integer t > 0,
x 1:N
x 1:N
and in particular,
Proof. By inspection.
Remark 3.2. According to Proposition 3.1, one can compute
in two phases,
the rst of which we could call the o-line phase and the second of which we could call
the on-line phase. In the o-line phase one computes the N dimensional vector v (t)
time,whilst in the second phase one computes the
value of
evaluating
N )(x). This second step takes
thus the whole procedure takes O((t time. Further, it is
easy to see that the procedure takes O(N
Now the algorithm whose pseudocode was given above can be formulated as follows:
Assume that we are given a xed " > 0. On the basis of " and L
we
compute some integer t > 0 and another integer N > 0. Each time we need to compute
an action of the randomized policy  for some state x, we rst draw a random sample
4 Here we assume that the basic algebraic operations over reals take O(1) time and that the storage of
a real-number takes up O(1) storage-space. We also assume that ^
1:N is not stored.
X 1:N and compute v (t)
random action of (x)
is computed by evaluating
The resulting policy will be shown to be "-optimal.
Another, computationally less expensive method is to hold the random sample X 1:N
xed and, accordingly, compute v (t)
only once. Then the computation of (x) using (4)
costs only O(jAjN 2 ) steps. This policy will be shown to be "-optimal with high probability
in Theorem 5.13.
The rst result shows that the algorithm just described yields a uniformly approximately
optimal policy with high probability and has polynomial complexity:
Theorem 4.1. Let
log(1=
and let

log
d log
let the stationary policy  be dened by ^
It is easy to see that the complexity of the algorithm meets indeed what we said before.
The next result shows that the modied, fully on-line algorithm given in Table 1 yields a
uniformly approximately optimal policy and has also polynomial complexity:
Theorem 4.2. Let
and let N be the smallest integer larger than

d log
let the stochastic stationary policy  : X  A ! [0; 1] be dened by
1:N is the policy dened by ^
is "-optimal and given a state x, a random action of  can be computed in time and
space polynomial in K r =", d, K r , K p , log L p , jAj and 1=(1
The rough outline of the proof is as follows: Under our assumptions, Pollard's maximal
inequality (cf. [9]) ensures that for any given xed function V 0 ,


is small
with high probability. 5 Using the triangle inequality one then reduces the comparison of
to those of ^
varies from zero to n 1. More
precisely, one shows that if the dierences between ^
are small for all


will be small, as well. Using this proposition it is
then easy to prove a maximal inequality for


Now, one can use standard contraction arguments to prove an inequality that bounds
the dierence of the value of a policy that is \approximately" greedy w.r.t. some function
in terms of the Bellman-residuals (see e.g. [14]). The plan is to use this inequality for
TN . Some more calculations yield Theorem 4.1.
Then, it is proven that if a policy selects only \good actions" (i.e., actions from A "
f a for a suitable ") then it is itself \good" (close to
optimal). Next, we relax the condition of \selecting good actions" to \selecting good
actions with high probability". Such policies can be shown to be \good", as well (cf.
Lemma 5 of [8]). Finally, it is shown that if a policy is good with high probability then it
selects good actions with high probability and thus, in turn, it must be \good". This will
nish the proof of Theorem 5.18.
5 Proof
We prove the theorem in the next three sections. First, we prove some maximal inequalities
for the random Bellman-operators ^
TN a . Next we show how these can be extended to powers
of
TN and, nally, we apply all these to prove the main results.
5 We must rely on Pollard's maximal inequality instead of the simpler Cherno-bounds because the
state space is continuous and the sup-norm above involves a supremum over the state space. Further, this
result is derived in two steps, using an idea of Rust [12].
5.1 Maximal Inequalities for Random Bellman Operators
We shall need some auxilliary operators which are easier to approach by maximal inequal-
ities. Let
~
TN a V
~
a2A
TN a V )(x)g:
We need some denitions and results from the theory of empirical processes (cf. [9]).
~
TN a V
~
a2A
TN a V )(x)g:
We need some denitions and results from the theory of uniform deviations (cf. [9]).
Denition 5.1. Let A  R d . The set S  A is an epsilon-cover of A if for all t 2 A
there exists an element s of S s.t. 1
d
". The set of "-covers of A will be denoted
").
Denition 5.2. The "-covering number of a set A is dened by
The number log N ("; A) is called the \metric entropy" of A. Let z
(R d ) n and let F  R R d
. We dene
The following theorem is due to Pollard (see [9]):
Theorem 5.3 (Pollard, 1984). Let n > 0 be an integer, "
be
a set of measurable functions. Let X d be i.i.d. random variables. Then

sup
n
8E
e
An elegant proof of this theorem can be found in [5][pp. 492]. In general, some further
assumptions are needed to make the result of the above sup measurable. Measurability
problems, however, are now well understood so we shall not worry about this detail. Readers
who keep worrying should understood all the probability bounds except for the main
result as outer/inner-probability bounds (whichever is appropriate). Note that in the nal
result we work with measurable sets and therefore there is no need to refer to outer/inner
probability measures.
Firstly, we extend this theorem to functions mapping R d into [ M;M ].
Corollary 5.3.1. Let n > 0 be an integer, " d be a set of
measurable functions. Let X d be i.i.d. random variables. Then

sup
n
8E
Proof. Let denote the positive and negativ parts of f , respectively (f
. By Theorem 5.3
it is sucient to prove that
where
Denote the lhs of (8) by A and let ! 2 A. Then since D n (f
proving
the corollary.
Denition 5.4. Let d 2 N , d > 0 and let  > 0. Let
and let Grid() be dened by
where ties are broken in favor of points having smaller coordinates.
Remark 5.5. kx P  xk 1
d  and jGrid()j  (
Lemma 5.6. Let K >
log
log
and N
a2A

~
TN a V T a V

Proof. We shall make use of Corollary 5.3.1. Let F(x 1:N
z N (V;
Easily, z N (V; x; a)  [ In order to estimate N ("; F(X 1:N )) from above, we
construct an "-cover of F(X 1:N ). We claim that
is an "-cover of F(X 1:N ) if  is chosen appropriately. In order to prove this let us pick up
an arbitrary element z N (V; x; a) of F(X 1:N ). ThenN
Therefore, if d) then S  is an "-cover of F(X 1:N ). By Remark 5.5, N ("; F(X 1:N
d
By Corollary 5.3.1, if
log
log
then (10) holds.
Now, we shall prove a similar result for ^
TN a using ideas from the proof of Corollary to
Theorem 3.4 of [12].
Lemma 5.7. Let K >

log
d log
log
a2A

TN a V T a V

Proof. Let us pick up some . By the triangle inequality

TN a V T a V


TN a V ~
TN a V


~
TN a V T a V

Let
If
TN a V )(x) ( ~
TN a V )(x)
then by simple
algebraic manipulations we get
TN a V )(x) ( ~
TN a V )(x)
Since, by assumption jV (X i )j  K, we have
TN a V )(x) ( ~
TN a V )(x)
R be dened by observe that
TN a e)(x)
and therefore by (14) we have
TN a V )(x) ( ~
TN a V )(x)
K
(T a e)(x) ( ~
TN a e)(x)
Note that this inequality holds also when p N (x; a) = 0. Taking the supremum over X
yields

TN a V ~
TN a V

K

T a e ~
TN a e

By (13) we have

TN a V T a V

K

~
TN a e T a e


~
TN a V T a V


~

Therefore
a2A

TN a V T a V

a2A

~
TN a V T a V

Now, the statement of the lemma follows using Lemma 5.6 if one lets N
5.2 Maximal Inequalities for Powers of Random Bellman Operator

First we need a proposition that relates the xed point of a contraction operator and an
operator that is "approximating" the contraction.
Proposition 5.8. Let B be a Banach-space and x some
be operators of B such that T 1
for some  > 0. Then


Proof. We prove the statement by induction; namely, we prove that
holds for all 0  s  t. The statement is obvious for Assume that we have already
proven (17) for s 1. By the triangle inequality, kT s




), the rst term of the rhs can be bounded
by


, which in turn can be bounded by
), by the induction
hypothesis. The second term, on the other hand, can be bounded by , by (15). Since
inequality (17) holds for s as well, thus proving the proposition.
We cite the next proposition without proof, as the proof is both elementary and is well
known.
Proposition 5.9. Let
). Then the Bellman-operator T maps BK (X ) into
Now, follows the main result of this section.
Lemma 5.10. Let t > 0 be an integer, " > 0,  > 0,

log
d log
log
If N  p 3 (d;
a2A




Proof. Let g. By Proposition 5.9, B 0  BK (X ).
By Lemma 5.7, if N  p 2 (d; "(1
a2A

TN a V T a V

"(1
Let the elementary event ! be such that
a2A

TN a (!)V T a V

"(1
If we show that
a2A

TN a (!)T t



then the proof is nished.
Obviously,
a2A

TN a (!)T t

by the construction of B 0 and since 1
1.
Now, note that


a2A

TN a (!)V T a V

holds for all V 2 B(X ). Since by the choice of ! and N ,
a2A

TN a (!)T s

"(1
we also have


"(1
Moreover, since ^
Proposition 5.8 can be applied with the choice


":
This together with (20) yields (19), thus proving the theorem.
5.3 Proving the "-optimality of the Algorithm
First, we prove an inequality similar to that of [14], but here we use both approximate
value functions and approximate operators.
be such that
Then


Note that since A is nite, the policy dened in the lemma exists.
Proof. We compare T k
since these are known to converge to V  and V  , re-
spectively. Firstly, we write the dierence T k
in the form of a telescoping sum:
Using the triangle inequality, T; T  2 Lip 1 (


Using the
and thus




a2A


On the other hand, kT therefore by (22),


which combined with (23) yields


a2A


Taking the limes superior of both sides when k !1 yields the lemma.
Note that if ^
a then we get back the tight bounds of [14]. 6
The next lemma exploits that if V
then the Bellman-
error can be related to the quality of approximation of T a by ^
6 Note that the lemma still holds if we replace the special operators ^
by operators
Lemma 5.12. Let
log(1=
assume that
a2A


Further,
Proof. We use Lemma 5.11. Let us bound the Bellman-error
rst:




a2A




), the second term is bounded by




where we have used that ^
Therefore, by
Lemma 5.11 we have
a2A


Using the denition of t and (24) we get kV  V  k  ", proving the lemma.
Now, we are in the position to prove the following theorem:
Theorem 5.13. Let
and let

log
d log
log
let the stationary policy  dened
Proof. The proof combines Lemmas 5.12 and 5.10. Firstly, we bound
a2A

TN a

Let ~
be dened by
~

TN a

(~ does not depend on x). Then

TN ~


TN ~







a2A


a2A




Therefore if
then by Lemma 5.10 and Lemma 5.12, kV  V  k  " with probability at least 1 .
In order to nish the proof of the main theorem we will prove that in discounted problems
stochastic policies that generate "-optimal actions with high probability are uniformly
good. This result appears in the context of nite models in [8], though due to space limits,
without a proof. For completeness, we Since our model has an innite state space and also
for the sake of completeness, here we present the proof. We start with the denition of
"-optimal actions and then prove three simple lemmas.
Denition 5.14. Let " > 0, and consider a discounted MDP (X ; A; p;
We call the
set
the set of "-optimal actions. Elements of this set are called "-optimal.
Lemma 5.15. Let  : X  A ! [0; 1] be a stationary stochastic policy that selects only
"-optimal actions: for all x 2 X and a 2 A from (x; a) > 0 it follows that a 2 A " (x).
Proof. From the denition of  it is immediate that kT
and
a2A
Now, consider the telescopicing sum
Therefore,




The next lemma will be applied to show if two policies are \close to each other" then so
are their evaluation functions. Both the lemma and its proof are very similar to those of
Proposition 5.8.
Lemma 5.16. Let B be a Banach-space, BK  f g. Assume that
are such that for some  > 0 kT holds for all V 2 BK
and
< 1. Then kT s
the xed points of T 1 and T 2 also satisfy kV
Proof. The proof is almost identical to that of Proposition 5.8. One proves by induction
that kT s
holds for all s  0. Here V 2 BK is xed. Indeed,
the inequality holds for Assuming that it holds for s 1 with s  1 one gets




showing the rst part of the statement. The second part is proven by taking
the limes superior of both sides when s !1.
Now, we are ready to prove the lemma showing that policies that choose "-optimal actions
with high probability are uniformly good.
be a stochastic
policy that selects "-optimal actions with probability at least 1 . Then kV  V  k
Proof. Let
a) denote the probability of selecting non-optimal actions
in state x be the
policy dened by
0; otherwise.
We claim that T  and T  0
are \close" to each other. For, let
a2A
and since kT a V k  K,
a2A
Further,
a2A
a)
a)
2:
Therefore,
and BK (X ) satisfy the assumptions of
Lemma 5.16, and the xed point of T  and T  0
are V  and V  0
, respectively, we have
Further, by construction  0 selects only "-optimal actions and thus by Lemma 5.15,
Combining this with (27), we get that kV  V  k  ("
nishing the
proof.
We are ready to prove the main result of the paper:
Theorem 5.18. Let
log(1=
and let

log
log
Choose
and let
Further, let the stochastic stationary policy  : X A! [0; 1] be dened
by
where  X 1:N is the policy dened by ^
TN V . Then  is "-optimal and given a
state x, a random action of  can be computed in time and space polynomial in 1=", d, K,
log L p , jAj and 1=(1
Proof. The second part of the statement is immediate (cf. Remark 3.2). The bound on
the time of computation is
and the space requirement of the algorithm is 7
For the rst part, x X 1:N . By Theorem 5.13, if
We claim that if ! is such that kV (!) V  k  " 0 then  X 1:N (!)(a) 2
us pick up such an !, let
(!); note that
Therefore, using the denition of
" (x), we get that  X 1:N (!)(a) 2 A " 0 (1+
This shows that
Now, by Lemma 5.17, the policy  dened by (31) is (("
))-optimal,
i.e.,
Substituting the denitions of " 0 and  yields the result.
6 Conclusions and Further Work
In this article we have considered an on-line planning algorithm that was shown to avoid the
curse of dimensionality. Bounds following from Rust's original result by Markov's inequality
were improved on in several ways: our bounds depend poly-logarithmically on the Lipschitz
constant of the transition probabilities, they do not depend on the Lipschitz constant of the
immediate rewards (we dropped the assumption of having Lipschitz-continuous immediate
7 Assuming that only the normalization factors of the transition probabilities
are stored.
reward functions), and the number of samples depends on the cardinality of the action set
in a poly-logarithmic way, as well.
It is interesting to note that although our bounds depend poly-logarithmically on the
Lipschitz constant of the transition probabilities (characterizing how \fast" is the dynam-
ics), they depend polynomially on the bound of the transition probabilities (characterizing
the randomness of the MDP). Therefore, perhaps not surprisingly, for these kind of Monte-Carlo
algorithms faster dynamics are easier to cope with than less random dynamics (with
transition probability functions).
As a consequence of our result, many interesting questions arise. For example, dierent
variants of the proposed algorithm could be compared, such as multigrid versions, versions
using quasi-random numbers, or versions that use importance sampling. Further, in prac-
tice, one would of course work with truncated probabilities to save some computational
resources. The eect of this truncation needs to be explored, as well.
Note that the Lipschitz condition on p can be replaced by an appropriate condition
on the metric-entropy of p(xj; a) and the proofs will still go through. Therefore the
proofs can be extended to Holder-classes of transition laws or local Lipschitz classes (e.g.
) (in this case one would need to use bracketing
smooth functions, Sobolev classes, etc.
One of the most interesting problems is to extend the results to innite action spaces.
Such an extension surely needs some regularity assumptions put on the dependence of
the transition probability law and the reward function on the actions. It would also be
interesting to prove similar results for discrete MDPs having a factorized representation.
The presented algorithm may nd applications in economic problems without any mod-
ications [11]. We also work on applications on deterministic continuous state-space, nite-
action space control problems and partially observable MDPs over discrete spaces. Also,
a combination with look-a-head search can be interesting from the practical point of view.
The algorithm was tried in practice on some standard problems (car-on-the-hill, acrobot)
and it was observed to yield quite a good performance even if the number of samples was
quite law. It was also observed that boundary eects can interfere negatively with the
algorithm. The details of these experiments, however, will be described elsewhere.



--R

Dynamic Programming.
Dynamic Programming: Deterministic and Stochastic Models.
The complexity of dynamic programming.
An optimal multigrid algorithm for continuous state discrete time stochastic control.

Controlled Markov Processes.
Approximate planning in large POMDPs via reusable trajectories.
A sparse sampling algorithm for near-optimal planning in large Markovian decision processes
Convergence of Stochastic Processes.
Markov Decision Processes
Structural estimation of Markov decision processes.
Using randomization to break the curse of dimensionality.


--TR
Dynamic programming: deterministic and stochastic models
The complexity of dynamic programming
Markov Decision Processes
A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes
Dynamic Programming

--CTR
Jared Go , Thuc Vu , James J. Kuffner, Autonomous behaviors for interactive vehicle animations, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France
Jared Go , Thuc D. Vu , James J. Kuffner, Autonomous behaviors for interactive vehicle animations, Graphical Models, v.68 n.2, p.90-112, March 2006
monte-carlo algorithms;markovian decision problems;value iteration;planning