Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves
This addresses the challenge of efficient and safe planning in CMDPs for applications like robotics and games, offering a novel method to overcome limitations in existing MCTS-based approaches.
The paper tackles the problem of safe sequential decision making in constrained Markov decision processes (CMDPs) by introducing Threshold UCT (T-UCT), a Monte Carlo tree search-based algorithm that explicitly estimates Pareto curves of cost-utility trade-offs to find safe and valuable policies, with experiments showing it significantly outperforms state-of-the-art methods.
Constrained Markov decision processes (CMDPs), in which the agent optimizes expected payoffs while keeping the expected cost below a given threshold, are the leading framework for safe sequential decision making under stochastic uncertainty. Among algorithms for planning and learning in CMDPs, methods based on Monte Carlo tree search (MCTS) have particular importance due to their efficiency and extendibility to more complex frameworks (such as partially observable settings and games). However, current MCTS-based methods for CMDPs either struggle with finding safe (i.e., constraint-satisfying) policies, or are too conservative and do not find valuable policies. We introduce Threshold UCT (T-UCT), an online MCTS-based algorithm for CMDP planning. Unlike previous MCTS-based CMDP planners, T-UCT explicitly estimates Pareto curves of cost-utility trade-offs throughout the search tree, using these together with a novel action selection and threshold update rules to seek safe and valuable policies. Our experiments demonstrate that our approach significantly outperforms state-of-the-art methods from the literature.