Article ID: | iaor20164509 |
Volume: | 41 |
Issue: | 4 |
Start Page Number: | 1484 |
End Page Number: | 1509 |
Publication Date: | Nov 2016 |
Journal: | Mathematics of Operations Research |
Authors: | Mannor Shie, Xu Huan, Mebel Ofir |
Keywords: | programming: markov decision, optimization, planning, heuristics |
Markov decision processes are a common tool for modeling sequential planning problems under uncertainty. In almost all realistic situations, the system model cannot be perfectly known and must be approximated or estimated. Thus, we consider Markov decision processes under parameter uncertainty, which effectively adds a second layer of uncertainty. Most previous studies restrict to the case that uncertainties among different states are uncoupled, which leads to conservative solutions. On the other hand, robust MDPs with general coupled uncertainty sets are known to be computationally intractable. In this paper we make a first attempt at identifying subclasses of coupled uncertainty that are flexible enough to overcome conservativeness yet still lead to tractable problems. We propose a new class of uncertainty sets termed ‘