Robust Online Optimization of Reward-Uncertain MDPs

Regan, Kevin; Boutilier, Craig

doi:10.5591/978-1-57735-516-8/IJCAI11-361

Robust Online Optimization of Reward-Uncertain MDPs

Kevin Regan, Craig Boutilier

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2165-2170.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-361

Abstract

Imprecise-reward Markov decision processes (IRMDPs) are MDPs in which the reward function is only partially specified (e.g., by some elicitation process). Recent work using minimax regret to solve IRMDPs has shown, despite their theoretical intractability, how the set of policies that are nondominated w.r.t. reward uncertainty can be exploited to accelerate regret computation. However, the number of nondominated policies is generally so large as to undermine this leverage. In this paper, we show how the quality of the approximation can be improved online by pruning/adding nondominated policies during reward elicitation, while maintaining computational tractability. Drawing insights from the POMDP literature, we also develop a new anytime algorithm for constructing the set of nondominated policies with provable (anytime) error bounds. These bounds can be exploited to great effect in our online approximation scheme.

Kevin Regan, and Craig Boutilier. 2011. Robust Online Optimization of Reward-Uncertain MDPs. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2165–2170. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-361

@inproceedings{ijcai2011p361,
  title     = {Robust Online Optimization of Reward-Uncertain MDPs},
  author    = {Regan, Kevin and Boutilier, Craig},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2165--2170},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-361},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-361},
}

TY  - CPAPER
TI  - Robust Online Optimization of Reward-Uncertain MDPs
AU  - Regan, Kevin
AU  - Boutilier, Craig
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2165
EP  - 2170
DO  - 10.5591/978-1-57735-516-8/IJCAI11-361
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-361
ER  -