  The Constrained Markov Decision Process (CMDP) formulation allows to solve
safety-critical decision making tasks that are subject to constraints. While
CMDPs have been extensively studied in the Reinforcement Learning literature,
little attention has been given to sampling-based planning algorithms such as
MCTS for solving them. Previous approaches perform conservatively with respect
to costs as they avoid constraint violations by using Monte Carlo cost
estimates that suffer from high variance. We propose Constrained MCTS (C-MCTS),
which estimates cost using a safety critic that is trained with Temporal
Difference learning in an offline phase prior to agent deployment. The critic
limits exploration by pruning unsafe trajectories within MCTS during
deployment. C-MCTS satisfies cost constraints but operates closer to the
constraint boundary, achieving higher rewards than previous work. As a nice
byproduct, the planner is more efficient w.r.t. planning steps. Most
importantly, under model mismatch between the planner and the real world,
C-MCTS is less susceptible to cost violations than previous work.
