Graphics enhanced version of this site

Solving Uncertain Markov Decision Problems
J. Bagnell, A.Y. Ng, and J. Schneider
tech. report CMU-RI-TR-01-25, Robotics Institute, Carnegie Mellon University, August, 2001.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [970 KB]
Compressed postscript (ps.gz) [2556 KB]

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

The authors consider the fundamental problem of finding good policies in uncertain models. It is demonstrated that although the general problem of finding the best policy with respect to the worst model is NP-hard, in the special case of a convex uncertainty set the problem is tractable. A stochastic dynamic game is proposed, and the security equilibrium solution of the game is shown to correspond to the value function under the worst model and the optimal controller. The authors demonstrate that the uncertain model approach can be used to solve a class of \emph{nearly} Markovian Decision Problems, providing lower bounds on performance in stochastic models with higher-order interactions. The framework considered establishes connections between and generalizes paradigms of stochastic optimal, mini-max, and $H_\infty$/robust control. Applications are considered, including robustness in reinforcement learning, planning in nearly Markovian decision processes, and bounding error due to sensor discretization in noisy, continuous state-spaces.

Associated labs/groups: Reliable Autonomous Systems Lab and Auton Lab
Associated projects: Auton Project and Federation of Intelligent Robotic Explorers Project

J. Bagnell, A.Y. Ng, and J. Schneider, Solving Uncertain Markov Decision Problems, tech. report CMU-RI-TR-01-25, Robotics Institute, Carnegie Mellon University, August, 2001.

@techreport{Bagnell_2001_3790,
   author = "James (Drew) Bagnell and Andrew Y. Ng and Jeff Schneider",
   title = "Solving Uncertain Markov Decision Problems",
   institution = "Robotics Institute, Carnegie Mellon University",
   month = "August",
   year = "2001",
   number = "CMU-RI-TR-01-25",
   address = "Pittsburgh, PA"
}