# Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 29 references that are in the map.
- First posted on arXiv 7 Jul 2024.

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

- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Agent57: Outperforming the Atari Human Benchmark](https://mlsanity.com/paper/2003.13350/) (2020)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Never Give Up: Learning Directed Exploration Strategies](https://mlsanity.com/paper/2002.06038/) (2020)
- [Count-Based Exploration with the Successor Representation](https://mlsanity.com/paper/1807.11622/) (2018)
- [State Entropy Maximization with Random Encoders for Efficient Exploration](https://mlsanity.com/paper/2102.09430/) (2021)
- [Monte-Carlo Tree Search as Regularized Policy Optimization](https://mlsanity.com/paper/2007.12509/) (2020)
- [Autonomous Penetration Testing using Reinforcement Learning](https://mlsanity.com/paper/1905.05965/) (2019)
- [A0C: Alpha Zero in Continuous Action Space](https://mlsanity.com/paper/1805.09613/) (2018)
- [R'enyi State Entropy for Exploration Acceleration in Reinforcement Learning](https://mlsanity.com/paper/2203.04297/) (2022)
- [Asymptotically Optimal Sampling-based Kinodynamic Planning](https://mlsanity.com/paper/1407.2896/) (2014)
- [Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation](https://mlsanity.com/paper/1809.07051/) (2018)
- [Asymptotically Optimal Planning by Feasible Kinodynamic Planning in State-Cost Space](https://mlsanity.com/paper/1505.04098/) (2015)
- [POLY-HOOT: Monte-Carlo Planning in Continuous Space MDPs with Non-Asymptotic Analysis](https://mlsanity.com/paper/2006.04672/) (2020)
- [CARLA Real Traffic Scenarios -- novel training ground and benchmark for autonomous driving](https://mlsanity.com/paper/2012.11329/) (2020)
- [A Survey on the Integration of Machine Learning with Sampling-based Motion Planning](https://mlsanity.com/paper/2211.08368/) (2022)
- [A Comparison of Monte Carlo Tree Search and Mathematical Optimization for Large Scale Dynamic Resource Allocation](https://mlsanity.com/paper/1405.5498/) (2014)
- [Roadmaps with Gaps over Controllers: Achieving Efficiency in Planning under Dynamics](https://mlsanity.com/paper/2310.03239/) (2023)

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

- [Online Decision-Making Under Uncertainty for Vehicle-to-Building Systems](https://mlsanity.com/paper/2601.03476/) (2026)

## Abstract (arXiv)

Monte Carlo tree search (MCTS) has been successful in a variety of domains, but faces challenges with long-horizon exploration when compared to sampling-based motion planning algorithms like Rapidly-Exploring Random Trees. To address these limitations of MCTS, we derive a tree search algorithm based on policy optimization with state occupancy measure regularization, which we call it Volume-MCTS. We show that count-based exploration and sampling-based motion planning can be derived as approximate solutions to this state occupancy measure regularized objective. We test our method on several robot navigation problems, and find that Volume-MCTS outperforms AlphaZero and displays significantly better long-horizon exploration properties.