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. Tra- ditional MDPs assume that the decision maker (DM) knows all states and actions. However, this may not be true in many situations of in- terest. We define a new framework, MDPs with unawareness (MDPUs) to deal with the possibil- ities 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. Tra- ditional MDPs assume that the decision maker (DM) knows all states and actions. However, this may not be true in many situations of in- terest. We define a new framework, MDPs with unawareness (MDPUs) to deal with the possibil- ities 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. Tra- ditional MDPs assume that the decision maker (DM) knows all states and actions. However, this may not be true in many situations of in- terest. We define a new framework, MDPs with unawareness (MDPUs) to deal with the possibil- ities 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