Tabular Model Learning in Monte Carlo Tree Search

Alberto Castellini, Davide Bragantini, Davide Rossignolo, Federico Segala, Alessandro FarinelliIPS-RCRA-SPIRIT@AI*IA 2023 · OpenReview

Abstract

Monte Carlo Tree Search (MCTS) typically requires a perfect environment simulator, a requirement that limits its applicability in real-world scenarios where dynamics are unknown. This paper introduces MCTS-TML (Monte Carlo Tree Search with Tabular Model Learning), an algorithm that learns transition dynamics on-the-fly. By integrating a tabular model-learning approach with MCTS planning, MCTS-TML achieves superior sample efficiency compared to traditional model-free and model-based reinforcement learning methods like Q-learning and Dyna-Q.

Introduction

Monte Carlo Tree Search (MCTS) has demonstrated remarkable success in complex decision-making tasks, most notably in game-playing agents like AlphaGo. However, its reliance on a perfect "forward model" or simulator poses a significant barrier for deployment in domains such as robotics or autonomous driving, where environment dynamics are not known a priori. While complex Bayesian Reinforcement Learning techniques have been proposed to address this, this work explores a simpler alternative: learning a tabular model of the environment from scratch and using it to drive MCTS planning.

Methodology

The proposed algorithm, MCTS-TML, operates in discrete state and action spaces through a four-step iterative loop:

  1. Interaction: The agent executes an action in the environment, observing the subsequent state and reward.
  2. Model Update: The transition $\langle s, a, s' \rangle$ is recorded in a tabular dictionary, updating empirical transition probabilities and rewards.
  3. Planning: The agent performs MCTS using the learned tabular model as a simulator for rollouts.
  4. Exploration of Unknowns: When the search encounters an unvisited state-action pair, a basic prior ($M_{prior}$) is used to simulate a random transition, ensuring the search process remains robust.

Unlike Dyna-Q, which uses a learned model for 1-step temporal difference (TD) updates, MCTS-TML leverages the model for deep, multi-step Monte Carlo rollouts to inform immediate action selection.

Experimental Setup

The algorithm was evaluated on the Gymnasium "Frozen Lake" environment, a grid-world task requiring the agent to navigate to a goal while avoiding hazards. Two variants were tested:

  • Deterministic: Actions result in certain transitions.
  • Stochastic: Actions have a high probability of success but include a "slip" factor.

Results and Discussion

MCTS-TML demonstrates significant improvements in both sample efficiency and model accuracy over baselines.

Performance and model learning comparisons across deterministic (a, b) and stochastic (c, d) environments.

Sample Efficiency

In deterministic environments, MCTS-TML matches the performance of an "Oracle" MCTS (equipped with a perfect model) within approximately 15 episodes. In contrast, Dyna-Q requires over 200 episodes to reach comparable levels, and standard Q-learning takes roughly 140 episodes to even surpass Dyna-Q. In stochastic settings, MCTS-TML continues to dominate, although convergence is slower due to the need for multiple observations to estimate transition probabilities accurately.

Model Accuracy

A key insight is that superior planning leads to better model learning. MCTS-TML learns the true underlying model faster and more accurately than Dyna-Q. As shown in the results, the mathematical distance between the learned and true models drops rapidly for MCTS-TML, whereas Dyna-Q's model error often plateaus, likely due to the lower-quality data generated by its less effective exploration/exploitation trade-offs.

Conclusion and Future Work

MCTS-TML proves that deep lookahead planning with a learned tabular model is more efficient than 1-step TD updates. However, the current tabular approach is limited to small, discrete environments. Future research will focus on scaling the algorithm using neural network representations for continuous and high-dimensional spaces, and incorporating safety constraints via confidence intervals on model estimates.

Summary updated

BibTeX
@inproceedings{castellini2023tabular,
  author = {Alberto Castellini and Davide Bragantini and Davide Rossignolo and Federico Segala and Alessandro Farinelli},
  title = {{Tabular Model Learning in Monte Carlo Tree Search}},
  booktitle = {IPS-RCRA-SPIRIT@AI*IA},
  year = {2023},
  url = {https://openreview.net/forum?id=KE82rFw8lr},
}
Figure