Vulcan: A Monte Carlo Algorithm for Large Chance Constrained MDPs with Risk Bounding Functions

Chance Constrained Markov Decision Processes maximize reward subject to a\nbounded probability of failure, and have been frequently applied for planning\nwith potentially dangerous outcomes or unknown environments. Solution\nalgorithms have required strong heuristics or have been limited to relatively\nsmall problems with up to millions of states, because the optimal action to\ntake from a given state depends on the probability of failure in the rest of\nthe policy, leading to a coupled problem that is difficult to solve. In this\npaper we examine a generalization of a CCMDP that trades off probability of\nfailure against reward through a functional relationship. We derive a\nconstraint that can be applied to each state history in a policy individually,\nand which guarantees that the chance constraint will be satisfied. The approach\ndecouples states in the CCMDP, so that large problems can be solved\nefficiently. We then introduce Vulcan, which uses our constraint in order to\napply Monte Carlo Tree Search to CCMDPs. Vulcan can be applied to problems\nwhere it is unfeasible to generate the entire state space, and policies must be\nreturned in an anytime manner. We show that Vulcan and its variants run tens to\nhundreds of times faster than linear programming methods, and over ten times\nfaster than heuristic based methods, all without the need for a heuristic, and\nreturning solutions with a mean suboptimality on the order of a few percent.\nFinally, we use Vulcan to solve for a chance constrained policy in a CCMDP with\nover $10^{13}$ states in 3 minutes.\n