Gastvortrag: Marck van der Vegt: Robust Almost-Sure Reachability in Multi-Environment MDPs

Dienstag, 21.03.2023, 11.00 Uhr

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

Vortragender: Marck van der Vegt

 

 Abstract: 

This talk is about our TACAS paper, joint work between me, Nils Jansen and Sebastian Junges.
Multiple-environment MDPs (MEMDPs) capture finite sets of MDPs that share the states but differ in the transition dynamics.
These models form a proper subclass of partially observable MDPs (POMDPs).
We consider the synthesis of policies that robustly satisfy an almost-sure reachability property in MEMDPs, that is, *one* policy that satisfies a property *for all* environments.
For POMDPs, deciding the existence of robust policies is an EXPTIME-complete problem.
We show that this problem is PSPACE-complete for MEMDPs, while the policies require exponential memory in general.
We exploit the theoretical results to develop and implement an algorithm that shows promising results in synthesizing robust policies for various benchmarks.