Monte-Carlo Tree Search for Constrained POMDPs
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 multiobjective 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 realworld 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.
and in the black-box simulation of the history. In contrast, solution methods for CPOMDPs, e.g. dynamic programming [11], linear programming [18], and online uniform-cost search [23], are not yet advanced up to this level, partly due to requiring an explicit model of the environment. This prevents CPOMDP from being a practical approach for modeling real-world applications.
In this paper, we present an MCTS algorithm for CPOMDPs, which precisely addresses the scalability. To the best of our knowledge, extending MCTS to CPOMDPs (or even CMDPs) has remained unexplored since it is not straightforward to handle the constrained optimization in tree search. This challenge is compounded by the fact that optimal policies can be stochastic. 1 In order to develop MCTS for CPOMDPs, we first show that solving CPOMDPs is essentially equivalent to jointly solving an unconstrained POMDP while optimizing its LP-induced parameters that control the tradeoff between the reward and the costs. From this result, we present our algorithm, Cost-Constrained POMCP (CC-POMCP), for solving large CPOMDPs that combine traditional MCTS with LP-induced parameter optimization. In the experiments section, we demonstrate that CC-POMCP converges to the optimal stochastic action selection using a synthetic domain and that it is able to handle very large problems including constrained variants of Rocksample (15,15) and Atari 2600 arcade game, pushing the state-of-the-art scalability in CPOMDP solvers.
This paper addresses a potentially important problem by giving an algorithm that can solve large constrained  POMDPs with online methods. A constrained POMDP, which augments a traditional POMDP with multi-attribute cost constraints, is an important extension that can help model a wider range of real-world phenomena than a POMDP can.  Having such an algorithm for solving large CPOMDPs is a very valuable contribution. The authors provide, in this paper, a derivation of an unconstrained objective to be solved (resulting from taking the dual of the CPOMDP's linear program), backed by theoretical justification, and an adaptation of the online search algorithm, POMCP, that incorporates cost constraints by approximately optimizing the objective.  The paper is extremely well-written, free of typos, and clear in its presentation. I especially liked the separation between the derivation of the objective being minimized (Section 3: eq. 3 and 4, leading up to the three-step process outlined at the end) and the approximation algorithm CC-POMCP (Section 4). I noticed there was no related work section, except for the paragraph starting "Although the CPOMDP..." in the Introduction, but maybe this is okay due to the minimal previous work on this subject.  (I don't know of any obviously missing references.)  I am assuming that the derivation, starting from section 3, is your novel work (the theorem 1 procedure is very cool).  If that is not true, then please indicate more clearly what aspects of the paper are novel.  I was somewhat surprised by the result that the optimal policy for a CPOMDP is generally stochastic.  It would be great if you could give a small example illustrating that fact, just for general edification of the reader.  Several experiments are conducted to show the effectiveness of the proposed algorithm.  They are well done, but ultimately somewhat disappointing. - The Rocksample domains, even though they are widely used to benchmark POMDP solvers, are actually really surprisingly easy to solve.  The reason is that the uncertainty about the individual rocks is basically completely uncoupled, and so it's really more of a large collection of small POMDPs with something like a TSP to connect them.  Further, the small POMDPs are relatively easy, given the actual observation probabilities, and there's very little branching in the optimal policy. - Given the nice ability of CPOMDPs to handle MA problems, it would have been good to see a domain that illustrates that.  I could imagine something like oil exploration where:  information about one test well actually give information about others (unlike the rocks) and where there are budgets for number of wells, distance traveled, total energy expended, etc. - The Pong domain seems very contrived, and seems to me to do a disservice to a very beautiful algorithm and paper.  When describing your main algorithm CC-POMDP, I think it would be very helpful to readers if you were to identify the differences from the standard POMCP algorithm. For example, perhaps you could use a different color to indicate those differences.   --------------- After reading the author response and other reviews, my opinion above still holds.