# Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves

arXiv: https://arxiv.org/abs/2412.13962 · HTML: https://mlsanity.com/paper/2412.13962/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 12 of its 29 references that are in the map.
- First posted on arXiv 18 Dec 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 12 of 12)

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach](https://mlsanity.com/paper/1506.02188/) (2015)
- [Constrained Markov Decision Processes via Backward Value Functions](https://mlsanity.com/paper/2008.11811/) (2020)
- [Qualitative Controller Synthesis for Consumption Markov Decision Processes](https://mlsanity.com/paper/2005.07227/) (2020)
- [ConstrainedZero: Chance-Constrained POMDP Planning using Learned Probabilistic Failure Surrogates and Adaptive Safety Constraints](https://mlsanity.com/paper/2405.00644/) (2024)
- [Reinforcement Learning of Risk-Constrained Policies in Markov Decision Processes](https://mlsanity.com/paper/2002.12086/) (2020)
- [Expectation Optimization with Probabilistic Guarantees in POMDPs with Discounted-sum Objectives](https://mlsanity.com/paper/1804.10601/) (2018)
- [Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes](https://mlsanity.com/paper/1805.02946/) (2018)
- [Vulcan: A Monte Carlo Algorithm for Large Chance Constrained MDPs with Risk Bounding Functions](https://mlsanity.com/paper/1809.01220/) (2018)

## Built on by (most cited first, 2 of 2)

- [Tail-Risk-Safe Monte Carlo Tree Search under PAC-Level Guarantees](https://mlsanity.com/paper/2508.05441/) (2025)
- [Online Robust Reinforcement Learning Through Monte-Carlo Planning](https://mlsanity.com/paper/2609.18599/) (2026)

## Abstract (arXiv)

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.