  Approximate dynamic programming is a popular method for solving large Markov
decision processes. This paper describes a new class of approximate dynamic
programming (ADP) methods- distributionally robust ADP-that address the curse
of dimensionality by minimizing a pessimistic bound on the policy loss. This
approach turns ADP into an optimization problem, for which we derive new
mathematical program formulations and analyze its properties. DRADP improves on
the theoretical guarantees of existing ADP methods-it guarantees convergence
and L1 norm based error bounds. The empirical evaluation of DRADP shows that
the theoretical guarantees translate well into good performance on benchmark
problems.
