Conditional expected accumulated rewards in Markov decision processes
- 11:00 27th February 2017 ( week 7, Hilary Term 2017 )Room 441, Wolfson Building, Parks Road
The talk addresses the problem of computing maximal conditional expected accumulated rewards until reaching a target state, briefly called maximal conditional expectations, in finite-state Markov decision processes (MDPs) where the condition is given as a reachability constraint. Conditional expectations of this type can, e.g., stand for the maximal expected termination time of probabilistic programs with non-determinism, under the condition that the program eventually terminates, or for the worst-case expected penalty to be paid, assuming that at least three deadlines are missed. The problem to check whether the maximal conditional expectation is finite is in P. Assumung finiteness, the problem to check whether the maximal conditional expectation exceeds a given rational threshold is PSPACE-hard for general MDPs and PSPACE-complete for acyclic MDPs. An iterative strategy-improvement algorithm can be used to compute the maximal conditional expectation and an optimal scheduler in exponential time.
Speaker bio
Christel Baier is a full professor and head of the chair for Algebraic and Logic Foundations of Computer Science at the Faculty of Computer Science of the Technische Universität Dresden since 2006. From the University of Mannheim she received her Diploma in Mathematics in 1990, her Ph.D. in Computer Science in 1994 and her Habilitation in 1999. She was an associate professor for Theoretical Computer Science at the University of Bonn from 1999 to 2006. Her research focuses on model checking, quantitative analysis of stochastic systems, concurrency theory, automata theory and temporal logic. She is involved in several projects, including the collaborative research center ``Highly-adaptive energy efficient computing (HAEC)'', the cluster of excellence ``center for Advanced Electronics Dresden (cfaed)'' and the research training groups ``Quantitative automata and logics (QuantLA)'' and ``Role-based software infrastructures for continuous context-sensitive systems (RoSI)''. She is a member of the review board for computer science in the German Research Foundation (2012-2020) and of Academia Europa (since 2011). She is editor-in-chief of the journal Acta Informatica and in the steering committee of FoSSaCS.Share this:
