Lab Lunch: 23 February 2021 - Richard Mayr

Title: Strategy Complexity of Parity Objectives in Countable MDPs

Abstract:

We give an overview of the mathematical techniques used for reasoning about strategy complexity in countably infinite Markov decision processes (MDPs). In particular, we discuss the exact strategy complexity of \eps-optimal strategies for Parity objectives, and the complexity of optimal strategies, where they exist.