An Inverse Method for Policy-Iteration Based Algorithms

Laurent Fribourg
(LSV Cachan)
Etienne André
(LSV Cachan)

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.

In Axel Legay: Proceedings International Workshop on Verification of Infinite-State Systems (INFINITY 2009), Bologna, Italy, 31th August 2009, Electronic Proceedings in Theoretical Computer Science 10, pp. 44–61.
Published: 17th November 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.10.4 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org