Approximate Dynamic Programming By Minimizing Distributionally Robust\n Bounds

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