Robust Approximate Optimization for Large Scale Planning Problems

Developing scalable and adaptive algorithms for reasoning and acting under uncertainty is an important area in artificial Intelligence. A large subclass of these problems may be formulated as Markov decision processes and are typically solved by Approximate Dynamic Programming (ADP). While ADP has recently gained traction in many domains, the successful applications often require extensive parameter tuning in order to obtain a sufficiently small approximation error. The goal of my thesis is to develop ADP methods that reduce the need for extensive tuning. I particularly focus on Approximate Linear Programming (ALP), a type of ADP. ALP has a number of theoretical advantages over other approximate dynamic programming methods, but in practice it suffers from the same performance issues as other ADP algorithms. These issues are mostly due to a large approximation error. I analyze the approximation error and propose methods for mitigating it. First, I examine various linear program formulations and their effect on the approximation error. ALP, like other ADP methods, involves sampling, which often significantly contributes to degradation in the solution quality. I analyze the sampling error and propose methods for minimizing it. Finally, the representation used in the approximation plays a crucial role in the performance. I therefore describe approaches to automatically tuning the representation in some common settings.