This website uses technically necessary cookies to offer the best possible functionality.

Skip to Content Skip to Main Navigation Skip to Search

UnRAVeL – UNcertainty and Randomness in Algorithms, VErification and Logic

Bi-Weekly Talk: Jip Spel: Monotonicity in pMDPs

Wednesday, January 25, 2023, 10:30am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10

Abstract:

We present a simple algorithm to check whether the expected total reward in a parametric Markov decision process (pMDP) is monotonic in (some of) the parameters. We use the results for monotonicity for parametric Markov chains, and try to find an optimal scheduler to resolve the non-determinism in pMDPs on-the-fly.

The idea is to construct---only using the graph structure of the Markov decision process, local transition probabilities, and state rewards---a pre-order on the states. Based on this pre-order we try to find an optimal scheduler, and check for a sufficient condition for monotonicity.

Experiments show that monotonicity in several benchmarks is automatically detected.

last updated : 06/03/2023