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

Martin Kurecka, Václav Nevyhostený, Petr Novotný, Vít UncovskýAAAI 2025 · DOI

TL;DR

This paper introduces Threshold UCT (T-UCT), a novel Monte Carlo Tree Search (MCTS) algorithm for safe sequential decision-making in Constrained Markov Decision Processes (CMDPs). T-UCT tackles the challenge of finding policies that are both safe (i.e., adhere to cost constraints) and valuable (i.e., achieve high rewards) by explicitly estimating Pareto curves of cost-utility trade-offs within the search tree.

What Problem Does This Paper Address?

In many real-world applications, autonomous agents must not only optimize their performance (e.g., maximize rewards) but also operate within strict safety constraints (e.g., minimize costs). This is formalized by Constrained Markov Decision Processes (CMDPs), where the goal is to maximize expected rewards while ensuring expected costs remain below a predefined threshold. While Monte Carlo Tree Search (MCTS) is a powerful framework for planning in complex environments, adapting it for CMDPs presents a significant challenge. Existing MCTS-based methods for CMDPs often struggle to strike a balance between safety and performance. Some are too conservative, failing to find valuable policies, while others may inadvertently violate the cost constraints due to unsound update rules or incomplete reasoning about the cost-reward trade-off. This paper aims to bridge this gap by developing an MCTS algorithm that can effectively navigate this trade-off to find policies that are both safe and rewarding.

Methods

The core innovation of T-UCT lies in its explicit estimation of Pareto curves within the MCTS search tree. Unlike previous methods that might use a single scalar value to represent the cost-reward trade-off (like a Lagrangian multiplier), T-UCT maintains a set of achievable (cost, reward) pairs at each node in the search tree. These Pareto estimates are updated using a convex hull-based backpropagation mechanism, similar to existing work but adapted for the CMDP setting.

Key novelties include:

  • Online Pareto Curve Estimation: T-UCT estimates the Pareto frontier of cost-utility trade-offs at each node in the search tree. This allows the algorithm to reason about the full spectrum of achievable outcomes.
  • Threshold-Based Action Selection: The algorithm uses these Pareto estimates to select actions that are most likely to lead to safe and valuable policies. It employs a novel action selection strategy that considers the current cost threshold and the estimated Pareto curves.
  • Sound Threshold Update Rule: A crucial contribution is a new threshold update rule that ensures the agent is not driven into excessive risk. This update rule is designed to be more robust and prevent violations of the cost constraint, addressing a known limitation in prior work.
  • Cost-Sensitive Exploration: The exploration strategy within T-UCT is adapted to be cost-sensitive, encouraging exploration of actions that are likely to lead to safe and valuable outcomes.

Datasets

The paper evaluates T-UCT on three environments:

  • Gridworld (Avoid and SoftAvoid): These are variants of established benchmarks for CMDPs. The "Avoid" task involves navigating a grid to collect rewards while avoiding traps that incur costs and can terminate the environment. "SoftAvoid" is similar but traps incur costs without terminating the environment. These tasks are evaluated on small and large maps.
  • Manhattan: This environment simulates an agent navigating a city, accepting maintenance requests for rewards, but incurring costs if deadlines are missed. This environment is based on existing work but adapted for the CMDP setting.

No new benchmarks were introduced; instead, the paper leverages existing ones to demonstrate the effectiveness of T-UCT.

Key Insights and Ideas

  • Pareto curves are crucial for balancing safety and reward: Representing the cost-reward trade-off with a set of Pareto optimal points, rather than a single scalar, provides a richer understanding of achievable outcomes and allows for more informed decision-making.
  • Sound threshold updates are critical for safety: Prior methods' unsound threshold update rules can lead to policies that violate cost constraints. T-UCT's novel update rule addresses this by ensuring the threshold is updated in a way that maintains feasibility.
  • Exploration needs to be cost-aware: Simply optimizing for reward during exploration can lead to unsafe policies. T-UCT's cost-sensitive exploration helps it discover safe and valuable strategies.
  • T-UCT achieves a better balance than existing methods: The experiments suggest that T-UCT successfully finds a sweet spot between the overly conservative CC-POMCP and the potentially unsafe RAMCP.

Key Results

T-UCT significantly outperforms state-of-the-art algorithms like CC-POMCP and RAMCP across the evaluated environments.

  • Safety: T-UCT consistently achieves high satisfaction rates (SATM and SATw), especially in challenging scenarios like the Manhattan environment where RAMCP struggles significantly.
  • Performance: While CC-POMCP is safe, it often does so at the expense of rewards, leading to very conservative behavior. RAMCP can achieve high rewards but often violates safety constraints. T-UCT strikes a good balance, achieving comparable or higher payoffs than baselines on satisfied instances.
  • Data Efficiency: T-UCT demonstrates notable data efficiency, performing well with fewer simulations per step compared to baselines, particularly in larger environments.

Limitations and Future Work

  • Limitations: The paper notes that the computational cost of T-UCT's backpropagation can be higher than baselines, especially for larger environments. The current implementation does not use function approximators, limiting its scalability to very large state spaces.
  • Future Work: The authors suggest augmenting T-UCT with function approximators for Pareto sets. This would enable T-UCT to scale to larger problems and function as a general MCTS-based reinforcement learning algorithm for cost-constrained optimization.

Summary updated

BibTeX
@inproceedings{kurecka2025threshold,
  author = {Martin Kurecka and Václav Nevyhostený and Petr Novotný and Vít Uncovský},
  title = {{Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i25.34858},
}
Figure