# Variance-Aware Prior-Based Tree Policies for Monte Carlo Tree Search

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 25 Dec 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Pgx: Hardware-Accelerated Parallel Game Simulators for Reinforcement Learning](https://mlsanity.com/paper/2303.17503/) (2023)
- [Beyond Games: A Systematic Review of Neural Monte Carlo Tree Search Applications](https://mlsanity.com/paper/2303.08060/) (2023)
- [MiniZero: Comparative Analysis of AlphaZero and MuZero on Go, Othello, and Atari Games](https://mlsanity.com/paper/2310.11305/) (2023)
- [Bayes Adaptive Monte Carlo Tree Search for Offline Model-based Reinforcement Learning](https://mlsanity.com/paper/2410.11234/) (2024)
- [Convex Regularization in Monte-Carlo Tree Search](https://mlsanity.com/paper/2007.00391/) (2020)
- [Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning](https://mlsanity.com/paper/2305.09840/) (2023)
- [Monte-Carlo tree search with uncertainty propagation via optimal transport](https://mlsanity.com/paper/2309.10737/) (2023)
- [Power Mean Estimation in Stochastic Monte-Carlo Tree_Search](https://mlsanity.com/paper/2406.02235/) (2024)
- [Extreme Value Monte Carlo Tree Search for Classical Planning](https://mlsanity.com/paper/2405.18248/) (2024)
- [A Bayesian Approach to Online Planning](https://mlsanity.com/paper/2406.02103/) (2024)
- [A Framework for Fair Evaluation of Variance-Aware Bandit Algorithms](https://mlsanity.com/paper/2510.27001/) (2025)

## Abstract (arXiv)

Monte Carlo Tree Search (MCTS) has profoundly influenced reinforcement learning (RL) by integrating planning and learning in tasks requiring long-horizon reasoning, exemplified by the AlphaZero family of algorithms. Central to MCTS is the search strategy, governed by a tree policy based on an upper confidence bound (UCB) applied to trees (UCT). A key factor in the success of AlphaZero is the introduction of a prior term in the UCB1-based tree policy PUCT, which improves exploration efficiency and thus accelerates training. While many alternative UCBs with stronger theoretical guarantees than UCB1 exist, extending them to prior-based UCTs has been challenging, since PUCT was derived empirically rather than from first principles. Recent work retrospectively justified PUCT by framing MCTS as a regularized policy optimization (RPO) problem. Building on this perspective, we introduce Inverse-RPO, a general methodology that systematically derives prior-based UCTs from a broad class of prior-free UCBs. Applying this method to the variance-aware UCB-V, we obtain two new prior-based tree policies that incorporate variance estimates into the search. Experiments indicate that these variance-aware prior-based UCTs outperform PUCT across multiple benchmarks without incurring additional computational cost. We also provide an extension of the mctx library supporting variance-aware UCTs, showing that the required code changes are minimal and intended to facilitate further research on principled prior-based UCTs. Code: github.com/Max-We/inverse-rpo.