On structural properties of MDPs that bound loss due to shallow planning

Nan Jiang, Satinder Singh, Ambuj Tewari

Research output: Contribution to journalConference articlepeer-review


Planning in MDPs often uses a smaller planning horizon than specified in the problem to save computational expense at the risk of a loss due to suboptimal plans. Jiang et al. [2015b] recently showed that smaller than specified planning horizons can in fact be beneficial in cases where the MDP model is learned from data and therefore not accurate. In this paper, we consider planning with accurate models and investigate structural properties of MDPs that bound the loss incurred by using smaller than specified planning horizons. We identify a number of structural parameters some of which depend on the reward function alone, some on the transition dynamics alone, and some that depend on the interaction between rewards and transition dynamics. We provide planning loss bounds in terms of these structural parameters and, in some cases, also show tightness of the upper bounds. Empirical results with randomly generated MDPs are used to validate qualitative properties of our theoretical bounds for shallow planning.

Original languageEnglish (US)
Pages (from-to)1640-1647
Number of pages8
JournalIJCAI International Joint Conference on Artificial Intelligence
StatePublished - 2016
Externally publishedYes
Event25th International Joint Conference on Artificial Intelligence, IJCAI 2016 - New York, United States
Duration: Jul 9 2016Jul 15 2016

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'On structural properties of MDPs that bound loss due to shallow planning'. Together they form a unique fingerprint.

Cite this