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

Liam Schramm

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

Liam Schramm

Chair of Information Technology (150)

Research output: Contribution to conference › Poster › Research › peer-review

2 Downloads (Pure)

Abstract

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 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.

Original language	English
Publication status	Published - 17 Sept 2025
Event	18th European Workshop on Reinforcement Learning - Eberhard Karls University of Tübingen, Tübingen, Germany Duration: 17 Sept 2025 → 19 Sept 2025 https://euro-workshop-on-reinforcement-learning.github.io/ewrl18/

Conference

Conference	18th European Workshop on Reinforcement Learning
Abbreviated title	EWRL18
Country/Territory	Germany
City	Tübingen
Period	17/09/25 → 19/09/25
Internet address	https://euro-workshop-on-reinforcement-learning.github.io/ewrl18/

Access to Document

EWRL VolumeMCTS poster v3.pptx-1

Cite this

@conference{6df95843f63549aebbe77884eba55a1d,

title = "Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization",

abstract = "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 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. ",

author = "Liam Schramm",

year = "2025",

month = sep,

day = "17",

language = "English",

note = "18th European Workshop on Reinforcement Learning, EWRL18 ; Conference date: 17-09-2025 Through 19-09-2025",

url = "https://euro-workshop-on-reinforcement-learning.github.io/ewrl18/",

}

TY - CONF

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

AU - Schramm, Liam

PY - 2025/9/17

Y1 - 2025/9/17

N2 - 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 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.

AB - 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 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.

M3 - Poster

T2 - 18th European Workshop on Reinforcement Learning

Y2 - 17 September 2025 through 19 September 2025

ER -