Output details
11 - Computer Science and Informatics
University College London
Lagrange dual decomposition for finite horizon Markov decision processes
<12>Solving finite-horizon Markov Decision Processes is a known computationally difficult problem. This paper is the first to develop an algorithm based on Lagrange Duality for solving MDPs. The method was described by a reviewer as an important new algorithm for this long-standing problem. The algorithm has remarkable empirical performance, far in excess of previous approaches. We believe that this approach will become one of the standard textbook approaches to solving this class of MDPs and part of the central core of algorithms in computer science. This resulted in an invited talk at the Royal Statistical Society and Imperial College London.