Bisimulation Metrics for Continuous Markov Decision Processes
Authors:
- Norm FernsNFNorm Ferns
- Prakash PanangadenPPPrakash Panangaden
- Doina PrecupDPDoina Precup
- 1 January 2011
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 40 (6) , 1662-1714
Abstract
In recent years, various metrics have been developed for measuring the behavioral similarity of states in probabilistic transition systems [J. Desharnais et al., Proceedings of CONCUR'99, Springer-Verlag, London, 1999, pp. 258–273; F. van Breugel and J. Worrell, Proceedings of ICALP'01, Springer-Verlag, London, 2001, pp. 421–432]. In the context of finite Markov decision processes (MDPs), we have built on these metrics to provide a robust quantitative analogue of stochastic bisimulation [N. Ferns, P. Panangaden, and D. Precup, Proceedings of UAI-04, AUAI Press, Arlington, VA, 2004, pp. 162–169] and an efficient algorithm for its calculation [N. Ferns, P. Panangaden, and D. Precup, Proceedings of UAI-06, AUAI Press, Arlington, VA, 2006, pp. 174–181]. In this paper, we seek to properly extend these bisimulation metrics to MDPs with continuous state spaces. In particular, we provide the first distance-estimation scheme for metrics based on bisimulation for continuous probabilistic transition systems. Our work, based on statistical sampling and infinite dimensional linear programming, is a crucial first step in formally guiding real-world planning, where tasks are usually continuous and highly stochastic in nature, e.g., robot navigation, and often a substitution with a parametric model or crude finite approximation must be made. We show that the optimal value function associated with a discounted infinite-horizon planning task is continuous with respect to metric distances. Thus, our metrics allow one to reason about the quality of solution obtained by replacing one model with another. Alternatively, they may potentially be used directly for state aggregation.Keywords
This publication has 44 references indexed in Scilit:
- A Computational Study of Cost Reoptimization for Min-Cost Flow ProblemsINFORMS Journal on Computing, 2006
- Metrics for labelled Markov processesTheoretical Computer Science, 2004
- Performance measure sensitive congruences for Markovian process algebrasTheoretical Computer Science, 2003
- On Choosing and Bounding Probability MetricsInternational Statistical Review, 2002
- Bisimulation for Labelled Markov ProcessesInformation and Computation, 2002
- Stochastic dynamic programming with factored representationsArtificial Intelligence, 2000
- Decision-Theoretic Planning: Structural Assumptions and Computational LeverageJournal of Artificial Intelligence Research, 1999
- Scale-sensitive dimensions, uniform convergence, and learnabilityJournal of the ACM, 1997
- When Scott is weak on the topMathematical Structures in Computer Science, 1997
- Uniform and universal Glivenko-Cantelli classesJournal of Theoretical Probability, 1991