Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00141808" target="_blank" >RIV/00216224:14330/25:00141808 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1609/aaai.v39i25.34858" target="_blank" >https://doi.org/10.1609/aaai.v39i25.34858</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1609/aaai.v39i25.34858" target="_blank" >10.1609/aaai.v39i25.34858</a>
Alternative languages
Result language
angličtina
Original language name
Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA23-06963S" target="_blank" >GA23-06963S: VESCAA: Verifiable and Efficient Synthesis of Controllers for Autonomous Agents</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence and Thirty-Seventh Conference on Innovative Applications of Artificial Intelligence and Fifteenth Symposium on Educational Advances in Artificial Intelligence
ISBN
9781577358978
ISSN
2159-5399
e-ISSN
—
Number of pages
10
Pages from-to
26569-26578
Publisher name
AAAI Press
Place of publication
Washington (DC)
Event location
Philadelphia, USA
Event date
Jan 1, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001477487000042