Monte-Carlo Tree Search as Regularized Policy Optimization

Jean-Bastien Grill, Florent Altché, Yunhao Tang, Thomas Hubert, Michal Valko, Ioannis Antonoglou, Rémi Munos

Introduction

AlphaZero and its successor, MuZero, represent the state-of-the-art in reinforcement learning (RL) for complex games and environments. Central to their success is the PUCT (Predictor Upper Confidence Bound applied to Trees) heuristic, which guides action selection during search. Despite its empirical success, PUCT remains a handcrafted heuristic with a somewhat opaque theoretical connection to model-free policy optimization.

This paper provides a theoretical bridge between Monte-Carlo Tree Search (MCTS) and regularized policy optimization. By reframing MCTS as a discrete approximation of a continuous optimization problem, the authors derive a more robust and expressive policy distribution that significantly improves performance, particularly in simulation-constrained settings.

The core contribution of this work is the proof that AlphaZero’s action selection formula is essentially tracking the solution to a regularized objective involving a "reversed KL-divergence." This insight allows the authors to move beyond simple visit counts (the number of times an action was explored) as the primary policy indicator.

Visit counts are inherently limited:

  1. Lagging Indicators: When a search discovers a high-value state, Q-values update immediately, but visit counts require many more simulations to reflect this new information.
  2. Discreteness: Visit counts are integers. In low-budget scenarios (e.g., 5 simulations), the resulting policy can only express probabilities in coarse increments (0%, 20%, 40%, etc.).

To address this, the authors derive an analytical distribution, $\bar{\pi}$, based directly on the Q-values found during search. Unlike visit counts, $\bar{\pi}$ is continuous and reacts instantly to value updates.

The "ALL" Algorithm

The authors propose the ALL algorithm, which integrates the optimized distribution $\bar{\pi}$ into three key components of the RL loop:

  • ACT: Using $\bar{\pi}$ to select actions in the actual environment.
  • SEARCH: Using $\bar{\pi}$ to sample actions while traversing the search tree.
  • LEARN: Using $\bar{\pi}$ as the training target for the neural network, replacing the traditional visit count distribution.

Experimental Results

The researchers evaluated the ALL algorithm against the MuZero baseline on Atari 2600 games and the DeepMind Control Suite.

Robustness to Low Simulation Budgets

A key finding is the algorithm's resilience when the search budget is limited. In many environments, the ALL variant with a very small number of simulations per step can match or exceed the performance of standard MuZero using ten times the budget.

Figure 1: Episode return vs. simulations per step. The ALL variant (blue) significantly outperforms MuZero (red) at low simulation counts, demonstrating superior efficiency.

Learning Efficiency and Performance

Across the Atari benchmark, the ALL variant consistently reached higher scores faster than the baseline. The continuous nature of the $\bar{\pi}$ distribution allows for more nuanced policy learning, which is especially beneficial in tasks with larger action spaces, such as discretized continuous control in the DeepMind Control Suite.

Figure 2: Learning curves for MuZero and ALL at different simulation budgets (5 and 50). The ALL variant shows faster convergence and higher final returns across both settings.

Conclusion and Future Work

By unifying MCTS with regularized policy optimization, this research provides a solid theoretical foundation for the heuristics used in AlphaZero-style agents. The resulting ALL algorithm is more simulation-efficient and expressive than standard MCTS. While the current implementation relies on action space discretization for continuous control, this work opens the door for future research into truly continuous tree search algorithms and further cross-pollination between planning and model-free RL paradigms.

Summary updated

Abstract

The combination of Monte-Carlo tree search (MCTS) with deep reinforcement learning has led to significant advances in artificial intelligence. However, AlphaZero, the current state-of-the-art MCTS algorithm, still relies on handcrafted heuristics that are only partially understood. In this paper, we show that AlphaZero's search heuristics, along with other common ones such as UCT, are an approximation to the solution of a specific regularized policy optimization problem. With this insight, we propose a variant of AlphaZero which uses the exact solution to this policy optimization problem, and show experimentally that it reliably outperforms the original algorithm in multiple domains.
BibTeX
@inproceedings{grill2020monte,
  author = {Jean-Bastien Grill and Florent Altché and Yunhao Tang and Thomas Hubert and Michal Valko and Ioannis Antonoglou and Rémi Munos},
  title = {{Monte-Carlo Tree Search as Regularized Policy Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=ypMD1JMHDde},
}

Loading related content...

Figure