License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.411
URN: urn:nbn:de:0030-drops-33286
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3328/
Go to the corresponding LIPIcs Volume Portal

Bertrand, Nathalie ; Genest, Blaise

Minimal Disclosure in Partially Observable Markov Decision Processes

pdf-format:
10.pdf (0.4 MB)

Abstract

For security and efficiency reasons, most systems do not give the
users a full access to their information. One key specification
formalism for these systems are the so called Partially Observable Markov Decision Processes (POMDP for short), which have been extensively studied in several research communities, among which AI and model-checking. In this paper we tackle the problem of the minimal information a user needs at runtime to achieve a simple goal, modeled as reaching an objective with probability one. More precisely, to achieve her goal, the user can at each step either choose to use the partial information, or pay a fixed cost and receive the full information. The natural question is then to minimize the cost the user needs to fulfill her objective. This optimization question gives rise to two different problems, whether we consider to minimize the worst case cost, or the average cost. On
the one hand, concerning the worst case cost, we show that efficient
techniques from the model checking community can be adapted to compute the optimal worst case cost and give optimal strategies for the users. On the other hand, we show that the optimal average price (a question typically considered in the AI community) cannot be computed in general, nor can it be approximated in polynomial time even up to a large approximation factor.

BibTeX - Entry

@InProceedings{bertrand_et_al:LIPIcs:2011:3328,
  author =	{Nathalie Bertrand and Blaise Genest},
  title =	{{Minimal Disclosure in Partially Observable Markov Decision Processes }},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{411--422},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3328},
  URN =		{urn:nbn:de:0030-drops-33286},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.411},
  annote =	{Keywords: Partially Observable Markov Decision Processes, Stochastic Games, Model-Checking, Worst-Case/Average-Case Analysis}
}

Keywords: Partially Observable Markov Decision Processes, Stochastic Games, Model-Checking, Worst-Case/Average-Case Analysis
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI