MDPs with Unawareness

Joseph Y. Halpern, Nan Rong, Ashutosh Saxena
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:236-243, 2010.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-halpern10a, title = {MDPs with Unawareness}, author = {Halpern, Joseph Y. and Rong, Nan and Saxena, Ashutosh}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {236--243}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/halpern10a/halpern10a.pdf}, url = {https://proceedings.mlr.press/r8/halpern10a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T MDPs with Unawareness %A Joseph Y. Halpern %A Nan Rong %A Ashutosh Saxena %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-halpern10a %I PMLR %P 236--243 %U https://proceedings.mlr.press/r8/halpern10a.html %V R8 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Halpern, J.Y., Rong, N. & Saxena, A.. (2010). MDPs with Unawareness. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:236-243 Available from https://proceedings.mlr.press/r8/halpern10a.html. Reissued by PMLR on 04 October 2026.

Related Material