Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
MDPs with Unawareness
Joseph Halpern, Nan Rong, Ashutosh Saxena
Abstract:
Markov decision processes (MDPs) are widely used for modeling decision-making problems in robotics, automated control, and economics. Traditional MDPs assume that the decision maker (DM) knows all states and actions. However, this may not be true in many situations of interest. We define a new framework, MDPs with unawareness (MDPUs) to deal with the possibilities that a DM may not be aware of all possible actions. We provide a complete characterization of when a DM can learn to play near-optimally in an MDPU, and give an algorithm that learns to play near-optimally when it is possible to do so, as efficiently as possible. In particular, we characterize when a near-optimal solution can be found in polynomial time.
Keywords:
Pages: 228-235
PS Link:
PDF Link: /papers/10/p228-halpern.pdf
BibTex:
@INPROCEEDINGS{Halpern10,
AUTHOR = "Joseph Halpern and Nan Rong and Ashutosh Saxena",
TITLE = "MDPs with Unawareness",
BOOKTITLE = "Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-10)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2010",
PAGES = "228--235"
}


hosted by DSL   •   site info   •   help