Research map / Learning theory and algorithms / Combinatorial and search optimization
Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Threshold UCT (T-UCT), an online MCTS planner for constrained MDPs that estimates Pareto curves of cost-reward trade-offs in each node and uses threshold-based action selection and a sound threshold update rule.
Problem
Safe and valuable planning in constrained MDPs with MCTS; existing MCTS CMDP planners (CC-POMCP, RAMCP) either fail to find constraint-satisfying policies or are overly conservative.
Approach
Backpropagate full Bellman updates of Pareto curves (cost-reward) through the search tree, select actions by mixing two actions so expected cost meets the current threshold, and update the threshold soundly by accounting for action outcomes, cost discount, and surplus/deficit cases.
Key results
- T-UCT achieves about 0.74 SAT_M and 1.00 SAT_W on Manhattan, while RAMCP and CC-POMCP are lower on SAT_W for Manhattan.
- On large Gridworld instances with nonzero thresholds, RAMCP satisfies at most about half of instances while T-UCT steadily achieves 0.8 to 1.0 satisfaction.
- CC-POMCP reaches up to tenfold lower payoff than T-UCT on Manhattan because it refuses almost all maintenance requests.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use T-UCT instead of RAMCP | CMDP planning · Avoid L | SAT_M: 0.41 -> 0.76 | Helped |
| Use T-UCT instead of CC-POMCP | CMDP planning · Avoid L | SAT_M: 0.77 vs 0.76 | No clear effect |
| Use T-UCT instead of RAMCP | CMDP planning · Avoid S | SAT_M: 0.69 -> 0.78 | Helped |
| Use T-UCT instead of CC-POMCP | CMDP planning · Avoid S | SAT_M: 0.59 -> 0.78 | Helped |
| Use T-UCT instead of RAMCP | CMDP planning · Manhattan | SAT_M: 0.25 -> 0.75 | Helped |
| Use T-UCT instead of CC-POMCP | CMDP planning · Manhattan | SAT_M: 0.94 -> 0.75 | Hurt |
| Use T-UCT instead of RAMCP | CMDP planning · SoftAvoid L | SAT_M: 0.52 -> 0.81 | Helped |
| Use T-UCT instead of CC-POMCP | CMDP planning · SoftAvoid L | SAT_M: 0.91 -> 0.81 | Hurt |
| Use T-UCT instead of RAMCP | CMDP planning · SoftAvoid S | SAT_M: 0.70 -> 0.96 | Helped |
| Use T-UCT instead of CC-POMCP | CMDP planning · SoftAvoid S | SAT_M: 0.92 -> 0.96 | Helped |
| Use T-UCT instead of CC-POMCP | CMDP planning · Manhattan | payoff: up to a tenfold gap | Helped |
| Use T-UCT instead of RAMCP | CMDP planning · GridworldLarge SoftAvoid | payoff | Helped |
Surprising findings
- RAMCP's threshold update can explode and effectively ignore the cost constraint, and CC-POMCP's threshold update can yield threshold-violating policies.
- T-UCT performs far fewer simulations per step than baselines (e.g., 387 vs 349 and 427 on Manhattan) due to costlier backpropagation, yet is more sample efficient in safety.
Limitations
- Tabular setting without function approximators; future work aims to add them.
- T-UCT has higher per-simulation backpropagation cost, leading to fewer simulations per step.
- Requires a generative simulator and the Pareto estimates to be accurate for soundness guarantees.
Experimental setup
Datasets: GridworldSmall GridworldLarge Manhattan (AEV benchmark via FiMDPEnv)
Benchmarks: Gridworld Avoid (small and large) Gridworld SoftAvoid (small and large) Manhattan
Metrics: SAT_M (mean satisfaction fraction) SAT_W (weak satisfaction via t-test) mean payoff on jointly satisfied instances samples per step
Baselines: CC-POMCP RAMCP
Builds on: UCT RAMCP CC-POMCP convex hull MCTS
Closest papers by meaning
- Monte Carlo Tree Search in the Presence of Transition Uncertainty (AAAI 2024 · similarity 0.89)
- Power Mean Estimation in Stochastic Continuous Monte-Carlo Tree Search (ICML 2025 · similarity 0.88)
- Graph-Based Stochastic-Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation (NeurIPS 2026 · similarity 0.88)
- Online Robust Reinforcement Learning Through Monte-Carlo Planning (ICML 2025 · similarity 0.87)
- Monte-Carlo Tree Search with Uncertainty Propagation via Optimal Transport (ICML 2025 · similarity 0.87)
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.