文章基本信息

标题：An Inverse Method for Policy-Iteration Based Algorithms
本地全文：下载
作者：Laurent Fribourg ; Etienne André
期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2009
卷号：10
页码：44-61
DOI：10.4204/EPTCS.10.4
出版社：Open Publishing Association
摘要：We present an extension of two policy-iteration based algorithms on weighted graphs (viz., Markov Decision Problems and Max-Plus Algebras). This extension allows us to solve the following inverse problem: considering the weights of the graph to be unknown constants or parameters, we suppose that a reference instantiation of those weights is given, and we aim at computing a constraint on the parameters under which an optimal policy for the reference instantiation is still optimal. The original algorithm is thus guaranteed to behave well around the reference instantiation, which provides us with some criteria of robustness. We present an application of both methods to simple examples. A prototype implementation has been done.