Guest Talk: Raphaël Berthon: Mixing Probabilistic and non-Probabilistic Objectives in Markov Decision Processes
Thursday, June 17, 2021, 10:00am
Location: Online session
Meeting-ID: 215 989 3416
Speaker: Raphaël Berthon (ULB, Belgien)
Abstract:
In the setting of games, an objective must be fulfilled whatever happens ("surely"), while on an MDP, an objective must be ensured with probability one ("almost-surely"). Combinations of these objectives are actively studied as it gives tools to model the control of a system in a stochastic environment. We consider omega-regular objectives using parity objectives, and we are interested in strategies ensuring combinations of such conditions, and the associated complexity analysis. We begin by showing how to satisfy a conjunction of one sure and one almost-sure condition, using techniques relying on the analysis of end-components. We then present two extensions of this result. The first extension replaces the almost-sure condition with a parity objective that must hold with a probability greater than a threshold. Such conditions are solved using linear programming, that do not interact naturally with sure conditions. The second extension considers Boolean combinations of sure and almost-sure conditions. We again use analysis of end-components, in conjunction with oracles to handle the Boolean combination, as it encompasses a SAT problem.