Amplifying Exploration in Monte-Carlo Tree Search by Focusing on the
Unknown
- URL: http://arxiv.org/abs/2402.08511v1
- Date: Tue, 13 Feb 2024 15:05:54 GMT
- Title: Amplifying Exploration in Monte-Carlo Tree Search by Focusing on the
Unknown
- Authors: Cedric Derstroff, Jannis Brugger, Jannis Bl\"uml, Mira Mezini, Stefan
Kramer, Kristian Kersting
- Abstract summary: Monte-Carlo tree search (MCTS) strategically allocates computational resources to focus on promising segments of the search tree.
Our proposed methodology, denoted as AmEx-MCTS, solves this problem by introducing a novel MCTS formulation.
Our empirical evaluation demonstrates the superior performance of AmEx-MCTS, surpassing classical MCTS and related approaches by a substantial margin.
- Score: 19.664506834858244
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Monte-Carlo tree search (MCTS) is an effective anytime algorithm with a vast
amount of applications. It strategically allocates computational resources to
focus on promising segments of the search tree, making it a very attractive
search algorithm in large search spaces. However, it often expends its limited
resources on reevaluating previously explored regions when they remain the most
promising path. Our proposed methodology, denoted as AmEx-MCTS, solves this
problem by introducing a novel MCTS formulation. Central to AmEx-MCTS is the
decoupling of value updates, visit count updates, and the selected path during
the tree search, thereby enabling the exclusion of already explored subtrees or
leaves. This segregation preserves the utility of visit counts for both
exploration-exploitation balancing and quality metrics within MCTS. The
resultant augmentation facilitates in a considerably broader search using
identical computational resources, preserving the essential characteristics of
MCTS. The expanded coverage not only yields more precise estimations but also
proves instrumental in larger and more complex problems. Our empirical
evaluation demonstrates the superior performance of AmEx-MCTS, surpassing
classical MCTS and related approaches by a substantial margin.
Related papers
- Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization [18.25487451605638]
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.
arXiv Detail & Related papers (2024-07-07T22:58:52Z) - LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget.
Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
arXiv Detail & Related papers (2024-06-29T05:14:04Z) - Autonomous Tree-search Ability of Large Language Models [58.68735916408101]
Large Language Models have excelled in remarkable reasoning capabilities with advanced prompting techniques.
Recent works propose to utilize external programs to define search logic, such that LLMs can perform passive tree search to solve more challenging reasoning tasks.
We propose a new concept called autonomous tree-search ability of LLM, which can automatically generate a response containing search trajectories for the correct answer.
arXiv Detail & Related papers (2023-10-14T14:14:38Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding.
Specifically, we use individual paths to assist the agents with the the goal-reaching behavior.
We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
arXiv Detail & Related papers (2023-07-25T12:33:53Z) - Continuous Monte Carlo Graph Search [61.11769232283621]
Continuous Monte Carlo Graph Search ( CMCGS) is an extension of Monte Carlo Tree Search (MCTS) to online planning.
CMCGS takes advantage of the insight that, during planning, sharing the same action policy between several states can yield high performance.
It can be scaled up through parallelization, and it outperforms the Cross-Entropy Method (CEM) in continuous control with learned dynamics models.
arXiv Detail & Related papers (2022-10-04T07:34:06Z) - BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
We discuss an alternative approach to novelty estimation, dubbed Behavior Recognition based Novelty Search (BR-NS)
BR-NS does not require an archive, makes no assumption on the metrics that can be defined in the behavior space and does not rely on nearest neighbours search.
We conduct experiments to gain insight into its feasibility and dynamics as well as potential advantages over archive-based NS in terms of time complexity.
arXiv Detail & Related papers (2021-04-08T17:31:34Z) - Prioritized Architecture Sampling with Monto-Carlo Tree Search [54.72096546595955]
One-shot neural architecture search (NAS) methods significantly reduce the search cost by considering the whole search space as one network.
In this paper, we introduce a sampling strategy based on Monte Carlo tree search (MCTS) with the search space modeled as a Monte Carlo tree (MCT)
For a fair comparison, we construct an open-source NAS benchmark of a macro search space evaluated on CIFAR-10, namely NAS-Bench-Macro.
arXiv Detail & Related papers (2021-03-22T15:09:29Z) - Improved POMDP Tree Search Planning with Prioritized Action Branching [33.94599291823342]
This paper proposes a method called PA-POMCPOW to sample a subset of the action space that provides varying mixtures of exploitation and exploration for inclusion in a search tree.
Experiments show that PA-POMCPOW is able to outperform existing state-of-the-art solvers on problems with large discrete action spaces.
arXiv Detail & Related papers (2020-10-07T18:33:57Z) - Unlucky Explorer: A Complete non-Overlapping Map Exploration [0.949996206597248]
We introduce the Maze Dash puzzle as an exploration problem where the agent must find a Hamiltonian Path visiting all the cells.
An optimization has been applied to the proposed Monte-Carlo Tree Search (MCTS) algorithm to obtain a promising result.
Our comparison indicates that the MCTS-based approach is an up-and-coming method that could cope with the test cases with small and medium sizes.
arXiv Detail & Related papers (2020-05-28T17:19:24Z) - The Second Type of Uncertainty in Monte Carlo Tree Search [2.564530030795554]
Monte Carlo Tree Search (MCTS) efficiently balances exploration and exploitation in tree search based on count-derived uncertainty.
We first show how, due to the lack of this second uncertainty type, MCTS may completely fail in well-known sparse exploration problems.
We then introduce a new algorithm, which estimates the size of the subtree below an action, and leverages this information in the UCB formula to better direct exploration.
arXiv Detail & Related papers (2020-05-19T09:10:51Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.