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:
- Interaction: The agent executes an action in the environment, observing the subsequent state and reward.
- Model Update: The transition $\langle s, a, s' \rangle$ is recorded in a tabular dictionary, updating empirical transition probabilities and rewards.
- Planning: The agent performs MCTS using the learned tabular model as a simulator for rollouts.
- 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.
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