License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2016.29
URN: urn:nbn:de:0030-drops-65698
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6569/
Go to the corresponding LIPIcs Volume Portal

Alur, Rajeev ; Faella, Marco ; Kannan, Sampath ; Singhania, Nimit

Hedging Bets in Markov Decision Processes

pdf-format:
LIPIcs-CSL-2016-29.pdf (0.5 MB)

Abstract

The classical model of Markov decision processes with costs or rewards, while widely used to formalize optimal decision making, cannot capture scenarios where there are multiple objectives for the agent during the system evolution, but only one of these objectives gets actualized upon termination. We introduce the model of Markov decision processes with alternative objectives (MDPAO) for formalizing optimization in such scenarios. To compute the strategy to optimize the expected cost/reward upon termination, we need to figure out how to balance the values of the alternative objectives. This requires analysis of the underlying infinite-state process that tracks the accumulated values of all the objectives. While the decidability of the problem of computing the exact optimal strategy for the general model remains open, we present the following results. First, for a Markov chain with alternative objectives, the optimal expected cost/reward can be computed in polynomial-time. Second, for a single-state process with two actions and multiple objectives we show how to compute the optimal decision strategy. Third, for a process with only two alternative objectives, we present a reduction to the minimum expected accumulated reward problem for one-counter MDPs, and this leads to decidability for this case under some technical restrictions. Finally, we show that optimal cost/reward can be approximated up to a constant additive factor for the general problem.

BibTeX - Entry

@InProceedings{alur_et_al:LIPIcs:2016:6569,
  author =	{Rajeev Alur and Marco Faella and Sampath Kannan and Nimit Singhania},
  title =	{{Hedging Bets in Markov Decision Processes}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{29:1--29:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Jean-Marc Talbot and Laurent Regnier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6569},
  URN =		{urn:nbn:de:0030-drops-65698},
  doi =		{10.4230/LIPIcs.CSL.2016.29},
  annote =	{Keywords: Markov decision processes, Infinite state systems, Multi-objective optimization}
}

Keywords: Markov decision processes, Infinite state systems, Multi-objective optimization
Collection: 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)
Issue Date: 2016
Date of publication: 29.08.2016

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