Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#318320] of Mauro Maggioni

Papers Published

  1. Maggioni, M; Mahadevan, S, Fast direct policy evaluation using multiscale analysis of Markov diffusion processes, Icml 2006 Proceedings of the 23rd International Conference on Machine Learning, vol. 2006 (October, 2006), pp. 601-608
    (last updated on 2019/02/16)

    Policy evaluation is a critical step in the approximate solution of large Markov decision processes (MDPs), typically requiring O(|S|3) to directly solve the Bellman system of |S| linear equations (where |S| is the state space size in the discrete case, and the sample size in the continuous case). In this paper we apply a recently introduced multiscale framework for analysis on graphs to design a faster algorithm for policy evaluation. For a fixed policy π, this framework efficiently constructs a multiscale decomposition of the random walk Pπ associated with the policy π. This enables efficiently computing medium and long term state distributions, approximation of value functions, and the direct computation of the potential operator (I - γPπ)-1 needed to solve Bellman's equation. We show that even a preliminary non-optimized version of the solver competes with highly optimized iterative techniques, requiring in many cases a complexity of O(|S|).
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320