Bi-Weekly Talk: Jip Spel: Monotonicity in pMDPs

Mittwoch, 25.01.2023, 10.30 Uhr

Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9u10

Vortragende: Jip Spel

 

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.