An Inverse Method for Policy-Iteration Based Algorithms
Authors:
- Laurent FribourgLFLaurent Fribourg
- Etienne AndréEAEtienne André
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- How to solve large scale deterministic games with mean payoff by policy iteration2006
- Numerical Computation of Spectral Elements in Max-Plus Algebra ☆IFAC Proceedings Volumes, 1998
- A theory of timed automataTheoretical Computer Science, 1994
- Dynamic Programming and Markov ProcessesTechnometrics, 1961