Skip to content. | Skip to navigation

Personal tools
Log in
Sections
You are here: Home Papers Monte-Carlo Tree Search for Constrained POMDPs

Jongmin Lee, Geon-Hyeong Kim, Pascal Poupart, and Kee-Eung Kim (2018)

Monte-Carlo Tree Search for Constrained POMDPs

In: Proceedings of Neural Information Processing Systems (NeurIPS).

Monte-Carlo Tree Search (MCTS) has been successfully applied to very large POMDPs, a standard model for stochastic sequential decision-making problems. However, many real-world problems inherently have multiple goals, where multi-objective formulations are more natural. The constrained POMDP (CPOMDP) is such a model that maximizes the reward while constraining the cost, extending the standard POMDP model. To date, solution methods for CPOMDPs assume an explicit model of the environment, and thus are hardly applicable to large-scale real-world problems. In this paper, we present CC-POMCP (Cost-Constrained POMCP), an online MCTS algorithm for large CPOMDPs that leverages the optimization of LP-induced parameters and only requires a black-box simulator of the environment. In the experiments, we demonstrate that CC-POMCP converges to the optimal stochastic action selection in CPOMDP and pushes the state-of-the-art by being able to scale to very large problems.