Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 12 of its 29 references that are in the map. First posted on arXiv 18 Dec 2024.
Builds on
12 of 29 references.
References · 12
- 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
- 2018Reward Constrained Policy Optimizationcited by 397
- 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 320
- 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 278
- 2015Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approachcited by 162
- 2020Constrained Markov Decision Processes via Backward Value Functionscited by 33
- 2020Qualitative Controller Synthesis for Consumption Markov Decision Processescited by 9
- 2024ConstrainedZero: Chance-Constrained POMDP Planning using Learned Probabilistic Failure Surrogates and Adaptive Safety Constraintscited by 7
- 2020Reinforcement Learning of Risk-Constrained Policies in Markov Decision Processescited by 5
- 2018Expectation Optimization with Probabilistic Guarantees in POMDPs with Discounted-sum Objectivescited by 4
- 2018Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processescited by 4
- 2018Vulcan: A Monte Carlo Algorithm for Large Chance Constrained MDPs with Risk Bounding Functionscited by 2
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.