BISIMULATION METRICS FOR CONTINUOUS MARKOV DECISION PROCESSES
BISIMULATION METRICS FOR CONTINUOUS MARKOV DECISION PROCESSES
复制标题
DOI：
10.1137/10080484x
复制
发表时间：
2011-01-01
影响因子：
1.6
通讯作者：
Precup, Doina
中科院分区：
文献类型：
--
作者：
Ferns, Norm;Panangaden, Prakash;Precup, Doina
近年来，已经开发了用于测量概率转换系统中状态的行为相似性的各种度量[J. Desharnais等人，《CONCUR'99会议记录》，Springer-Verlag，伦敦，1999年，pp. 258-273; F.货车Breugel和J. Worrell，ICALP'01会议记录，Springer-Verlag，伦敦，2001年，第100页。421-432]。在有限马尔可夫决策过程（MDP）的背景下，我们基于这些指标来提供随机互模拟的鲁棒定量模拟[N. Ferns、P. Panangeli和D. Precup，Proceedings of UAI-04，AUAI Press，阿灵顿，VA，2004，pp. 162-169]及其计算的有效算法[N. Ferns、P. Panangeli和D. Precup，Proceedings of UAI-06，AUAI Press，阿灵顿，VA，2006，pp. 174-181]。在本文中，我们试图适当地扩展这些互模拟度量连续状态空间的MDP。特别是，我们提供了第一个距离估计方案的度量连续概率转移系统的互模拟的基础上。我们的工作，基于统计抽样和无限维线性规划，是正式指导现实世界规划的关键的第一步，其中任务通常是连续的，本质上是高度随机的，例如。例如，在一个实施例中，机器人导航，并且通常必须用参数模型或粗略的有限近似来代替。我们表明，最优值函数与折扣无限地平线规划任务是连续的度量距离。因此，我们的指标允许一个原因的解决方案的质量，通过更换一个模型与另一个。或者，它们可能直接用于状态聚合。
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.