A Geometric Traversal Algorithm for Reward-Uncertain MDPs

Eunsoo Oh, Kee-Eung Kim
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:631-638, 2011.

Abstract

Markov decision processes (MDPs) are widely used in modeling decision making problems in stochastic environments. However, precise specification of the reward functions in MDPs is often very difficult. Recent approaches have focused on computing an optimal policy based on the minimax regret criterion for obtaining a robust policy under uncertainty in the reward function. One of the core tasks in computing the minimax regret policy is to obtain the set of all policies that can be optimal for some candidate reward function. In this paper, we propose an efficient algorithm that exploits the geometric properties of the reward function associated with the policies. We also present an approximate version of the method for further speed up. We experimentally demonstrate that our algorithm improves the performance by orders of magnitude.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-oh11a, title = {A Geometric Traversal Algorithm for Reward-Uncertain MDPs}, author = {Oh, Eunsoo and Kim, Kee-Eung}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {631--638}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/oh11a/oh11a.pdf}, url = {https://proceedings.mlr.press/r9/oh11a.html}, abstract = {Markov decision processes (MDPs) are widely used in modeling decision making problems in stochastic environments. However, precise specification of the reward functions in MDPs is often very difficult. Recent approaches have focused on computing an optimal policy based on the minimax regret criterion for obtaining a robust policy under uncertainty in the reward function. One of the core tasks in computing the minimax regret policy is to obtain the set of all policies that can be optimal for some candidate reward function. In this paper, we propose an efficient algorithm that exploits the geometric properties of the reward function associated with the policies. We also present an approximate version of the method for further speed up. We experimentally demonstrate that our algorithm improves the performance by orders of magnitude.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Geometric Traversal Algorithm for Reward-Uncertain MDPs %A Eunsoo Oh %A Kee-Eung Kim %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-oh11a %I PMLR %P 631--638 %U https://proceedings.mlr.press/r9/oh11a.html %V R9 %X Markov decision processes (MDPs) are widely used in modeling decision making problems in stochastic environments. However, precise specification of the reward functions in MDPs is often very difficult. Recent approaches have focused on computing an optimal policy based on the minimax regret criterion for obtaining a robust policy under uncertainty in the reward function. One of the core tasks in computing the minimax regret policy is to obtain the set of all policies that can be optimal for some candidate reward function. In this paper, we propose an efficient algorithm that exploits the geometric properties of the reward function associated with the policies. We also present an approximate version of the method for further speed up. We experimentally demonstrate that our algorithm improves the performance by orders of magnitude. %Z Reissued by PMLR on 04 October 2026.
APA
Oh, E. & Kim, K.. (2011). A Geometric Traversal Algorithm for Reward-Uncertain MDPs. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:631-638 Available from https://proceedings.mlr.press/r9/oh11a.html. Reissued by PMLR on 04 October 2026.

Related Material