Optimizing expectation with guarantees in POMDPs Conference Paper

Author(s): Chatterjee, Krishnendu; Novotný, Petr; Pérez, Guillermo A; Raskin, Jean-François; Zikelic, Djordje
Title: Optimizing expectation with guarantees in POMDPs
Affiliation IST Austria
Abstract: A standard objective in partially-observable Markov decision processes (POMDPs) is to find a policy that maximizes the expected discounted-sum payoff. However, such policies may still permit unlikely but highly undesirable outcomes, which is problematic especially in safety-critical applications. Recently, there has been a surge of interest in POMDPs where the goal is to maximize the probability to ensure that the payoff is at least a given threshold, but these approaches do not consider any optimization beyond satisfying this threshold constraint. In this work we go beyond both the “expectation” and “threshold” approaches and consider a “guaranteed payoff optimization (GPO)” problem for POMDPs, where we are given a threshold t and the objective is to find a policy σ such that a) each possible outcome of σ yields a discounted-sum payoff of at least t, and b) the expected discounted-sum payoff of σ is optimal (or near-optimal) among all policies satisfying a). We present a practical approach to tackle the GPO problem and evaluate it on standard POMDP benchmarks.
Keywords: verification; probabilistic planning; Partially-observable Markov decision processes; Discounted payoff
Conference Title: AAAI: Conference on Artificial Intelligence
Volume: 5
Conference Dates: February 4 - 9, 2017
Conference Location: San Francisco, CA, USA
Publisher: AAAI Press  
Date Published: 2017-01-01
Start Page: 3725
End Page: 3732
Notes: The research leading to these results was supported by the Austrian Science Fund (FWF) NFN Grant no.S11407-N23 (RiSE/SHiNE); two ERC Starting grants (279307: Graph Games, 279499: inVEST); theVienna Science and Technology Fund (WWTF) through project ICT15-003; and the People Programme(Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) underREA grant agreement no. [291734].
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work