  We develop a regression based primal-dual martingale approach for solving
finite time horizon MDPs with general state and action space. As a result, our
method allows for the construction of tight upper and lower biased
approximations of the value functions, and, provides tight approximations to
the optimal policy. In particular, we prove tight error bounds for the
estimated duality gap featuring polynomial dependence on the time horizon, and
sublinear dependence on the cardinality/dimension of the possibly infinite
state and action space.From a computational point of view the proposed method
is efficient since, in contrast to usual duality-based methods for optimal
control problems in the literature, the Monte Carlo procedures here involved do
not require nested simulations.
