Optimization Online


Singularly Perturbed Markov Decision Processes: A Multiresolution Algorithm

Chin Pang Ho (c.ho12***at***imperial.ac.uk)
Panos Parpas (p.parpas***at***imperial.ac.uk)

Abstract: Singular perturbation techniques allow the derivation of an aggregate model whose solution is asymptotically optimal for Markov Decision Processes with strong and weak interactions. We develop an algorithm that takes advantage of the asymptotic optimality of the aggregate model in order to compute the solution of the original model with theoretically better complexity than conventional contraction algorithms. Based on our complexity analysis we show that the major benefit of aggregation is that the reduced order model is no longer ill conditioned, and the reduction in the number of states (due to aggregation) is a secondary benefit. This is a surprising result since intuition would suggest that the reduced order model can be solved more efficiently because it has fewer states. However we show that this is not necessarily the case. Our convergence analysis and numerical experiments show that the proposed algorithm can compute the optimal solution with a reduction in computational complexity without any penalty in accuracy.

Keywords: Markov decision processes, multiscale modeling, multigrid methods, weak and strong interactions

Category 1: Other Topics (Dynamic Programming )

Citation: Working paper, Department of Computing, Imperial College London, November 2013

Download: [PDF]

Entry Submitted: 11/06/2013
Entry Accepted: 11/06/2013
Entry Last Modified: 06/17/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society