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

Tuesday, March 21, 2023, 11:00am

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

Speaker: 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.