Point-Based Value Iteration for Constrained POMDPs

Kim, Dongho; Lee, Jaesong; Kim, Kee-Eung; Poupart, Pascal

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

Point-Based Value Iteration for Constrained POMDPs

Dongho Kim, Jaesong Lee, Kee-Eung Kim, Pascal Poupart

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1968-1973.

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

Abstract

Constrained partially observable Markov decision processes (CPOMDPs) extend the standard POMDPs by allowing the specification of constraints on some aspects of the policy in addition to the optimality objective for the value function. CPOMDPs have many practical advantages over standard POMDPs since they naturally model problems involving limited resource or multiple objectives. In this paper, we show that the optimal policies in CPOMDPs can be randomized, and present exact and approximate dynamic programming methods for computing randomized optimal policies. While the exact method requires solving a minimax quadratically constrained program (QCP) in each dynamic programming update, the approximate method utilizes the point-based value update with a linear program (LP). We show that the randomized policies are significantly better than the deterministic ones. We also demonstrate that the approximate point-based method is scalable to solve large problems.

Dongho Kim, Jaesong Lee, Kee-Eung Kim, and Pascal Poupart. 2011. Point-Based Value Iteration for Constrained POMDPs. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1968–1973. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-329

@inproceedings{ijcai2011p329,
  title     = {Point-Based Value Iteration for Constrained POMDPs},
  author    = {Kim, Dongho and Lee, Jaesong and Kim, Kee-Eung and Poupart, Pascal},
  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     = {1968--1973},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-329},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-329},
}

TY  - CPAPER
TI  - Point-Based Value Iteration for Constrained POMDPs
AU  - Kim, Dongho
AU  - Lee, Jaesong
AU  - Kim, Kee-Eung
AU  - Poupart, Pascal
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  - 1968
EP  - 1973
DO  - 10.5591/978-1-57735-516-8/IJCAI11-329
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-329
ER  -