  We introduce a mesh-type approach for tackling discrete-time, finite-horizon
Markov Decision Processes (MDPs) characterized by state and action spaces that
are general, encompassing both finite and infinite (yet suitably regular)
subsets of Euclidean space. In particular, for bounded state and action spaces,
our algorithm achieves a computational complexity that is tractable in the
sense of Novak and Wozniakowski, and is polynomial in the time horizon. For
unbounded state space the algorithm is "semi-tractable" in the sense that the
complexity is proportional to $\epsilon^{-c}$ with some dimension independent
$c\geq2$, for achieving an accuracy $\epsilon$, and polynomial in the time
horizon with degree linear in the underlying dimension. As such the proposed
approach has some flavor of the randomization method by Rust which deals with
infinite horizon MDPs and uniform sampling in compact state space. However, the
present approach is essentially different due to the finite horizon and a
simulation procedure due to general transition distributions, and more general
in the sense that it encompasses unbounded state space. To demonstrate the
effectiveness of our algorithm, we provide illustrations based on
Linear-Quadratic Gaussian (LQG) control problems.
