# Monte-Carlo tree search with uncertainty propagation via optimal transport

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 37 references that are in the map.
- First posted on arXiv 19 Sep 2023.

## Builds on (most cited first, 9 of 9)

- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Entropic Regularization of Markov Decision Processes](https://mlsanity.com/paper/1907.04214/) (2019)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Generalized Mean Estimation in Monte-Carlo Tree Search](https://mlsanity.com/paper/1911.00384/) (2019)

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

- [Predicting and Publishing Accurate Imbalance Prices Using Monte Carlo Tree Search](https://mlsanity.com/paper/2411.04011/) (2024)
- [Variance-Aware Prior-Based Tree Policies for Monte Carlo Tree Search](https://mlsanity.com/paper/2512.21648/) (2025)
- [Variance Driven Exploration: A Provable and Efficient Methodology for Pure Exploration in Highly Stochastic Environments](https://mlsanity.com/paper/2608.21995/) (2026)

## Abstract (arXiv)

This paper introduces a novel backup strategy for Monte-Carlo Tree Search (MCTS) designed for highly stochastic and partially observable Markov decision processes. We adopt a probabilistic approach, modeling both value and action-value nodes as Gaussian distributions. We introduce a novel backup operator that computes value nodes as the Wasserstein barycenter of their action-value children nodes; thus, propagating the uncertainty of the estimate across the tree to the root node. We study our novel backup operator when using a novel combination of L1-Wasserstein barycenter with α-divergence, by drawing a notable connection to the generalized mean backup operator. We complement our probabilistic backup operator with two sampling strategies, based on optimistic selection and Thompson sampling, obtaining our Wasserstein MCTS algorithm. We provide theoretical guarantees of asymptotic convergence to the optimal policy, and an empirical evaluation on several stochastic and partially observable environments, where our approach outperforms well-known related baselines.