# Convex Hull Monte-Carlo Tree Search

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

## Key facts

- Cited by 8 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 9 Mar 2020.

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

- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [Sample-Efficient Multi-Objective Learning via Generalized Policy Improvement Prioritization](https://mlsanity.com/paper/2301.07784/) (2023)
- [Risk Aware and Multi-Objective Decision Making with Distributional Monte Carlo Tree Search](https://mlsanity.com/paper/2102.00966/) (2021)
- [Monte Carlo Tree Search Algorithms for Risk-Aware and Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2211.13032/) (2022)
- [Heuristic Search for Multi-Objective Probabilistic Planning](https://mlsanity.com/paper/2303.14363/) (2023)
- [On Solving a Stochastic Shortest-Path Markov Decision Process as Probabilistic Inference](https://mlsanity.com/paper/2109.05866/) (2021)
- [Feature Acquisition using Monte Carlo Tree Search](https://mlsanity.com/paper/2212.11360/) (2022)
- [MoFlow: Multi-Objective Agentic Workflow Generation](https://mlsanity.com/paper/2609.38294/) (2026)

## Abstract (arXiv)

This work investigates Monte-Carlo planning for agents in stochastic environments, with multiple objectives. We propose the Convex Hull Monte-Carlo Tree-Search (CHMCTS) framework, which builds upon Trial Based Heuristic Tree Search and Convex Hull Value Iteration (CHVI), as a solution to multi-objective planning in large environments. Moreover, we consider how to pose the problem of approximating multiobjective planning solutions as a contextual multi-armed bandits problem, giving a principled motivation for how to select actions from the view of contextual regret. This leads us to the use of Contextual Zooming for action selection, yielding Zooming CHMCTS. We evaluate our algorithm using the Generalised Deep Sea Treasure environment, demonstrating that Zooming CHMCTS can achieve a sublinear contextual regret and scales better than CHVI on a given computational budget.