Monte Carlo Tree Search

Also known as MCTS

Overview

Monte Carlo Tree Search builds a partial decision tree, repeatedly selecting promising branches, evaluating outcomes through simulations or learned models, and backing those evaluations up to guide later choices. Common approaches include UCT and PUCT exploration rules, neural policy and value guidance, progressive widening for large or continuous action spaces, and parallel search. MCTS is used in games, robotics and partially observable planning, as well as language-model tasks such as mathematical reasoning, coding, and tool use; evaluations span game-playing tests, POMDP benchmarks, and reasoning benchmarks. A central challenge is allocating limited computation effectively: search depends on the quality of its models and evaluators, and more search does not always improve results, so methods need reliable uncertainty handling and fair equal-budget comparisons.

Latest papers

92 papers11 papers in the last four weeks, down 8% on the four weeks before. 0.1% of all new papers.

Mar 7, 2025

Reward-Centered ReST-MCTS: A Robust Decision-Making Framework for Robotic Manipulation in High Uncertainty Environments

Monte Carlo tree search is attractive for robotic manipulation because it can improve action selection through simulation without requiring a fully differentiable policy. In uncertain domains, however, sparse terminal rewards and noisy transitions can make shallow search brittle: many candidate branches remain indistinguishable until late rollouts, and small simulation budgets amplify this ambiguity. This paper presents Reward-Centered ReST-MCTS, a decision-making framework that decomposes intermediate feedback into rule, heuristic, optional neural, and value-estimation channels, centers the resulting process signal against matched task contexts, and uses it to bias or repair search while preserving terminal-task evaluation. The primary evidence is intentionally tiered. Local tasks and matched ManiSkill diagnostics isolate reward-center mechanisms and ablations; matched option-level ManiSkill sweeps test robustness under primitive failure, observation noise, and initial-pose shifts while not claiming standard benchmark superiority; and an official same-backbone OpenVLA-OFT/LIBERO bridge tests bounded VLA action repair. The OpenVLA-OFT clean reproduction reaches 10/10 LIBERO-Spatial successes both with and without RCRM-Guard. A single-suite same-backbone action-channel stress artifact over ten paired LIBERO-Spatial action-channel stress episodes records 0/10 unguarded successes and 9/10 guarded successes. Additional observation-noise, language-perturbation, and visual-distractor probes are reported as coverage and negative-result context rather than superiority evidence. The resulting claim is bounded: Reward-Centered ReST-MCTS is an inspectable test-time verifier for same-backbone high-uncertainty manipulation, not a replacement VLA policy or a broad standard-benchmark superiority claim.
Jul 26, 2024

Requirement-Based Testing: Enhancing Reinforcement Learning with Game Theory

We consider the automatic online synthesis of black-box test cases from functional requirements specified as automata for reactive implementations. The goal of the tester is to reach some given state, so as to satisfy a coverage criterion, while monitoring the violation of the requirements. We develop an approach based on Monte Carlo Tree Search, which is a classical technique in reinforcement learning for efficiently selecting promising inputs. Seeing the automata requirements as a game between the implementation and the tester, we develop a heuristic by biasing the search towards inputs that are promising in this game. We experimentally show that our heuristic accelerates the convergence of the Monte Carlo Tree Search algorithm, thus improving the performance of testing.