ME-MCTS: Online Generalization by Combining Multiple Value Estimators

Hendrik Baier, Michael KaisersIJCAI 2021 · DOI

TL;DR

This paper introduces ME-MCTS, a novel approach to improve Monte Carlo Tree Search (MCTS) by combining multiple "value estimators" that generalize across game states. By intelligently blending these estimators, ME-MCTS achieves significantly better performance than standard MCTS and MCTS with single generalization techniques across various board games.

What Problem Does This Paper Address?

MCTS is a powerful search algorithm for games, but vanilla MCTS struggles with large search spaces because it doesn't effectively generalize knowledge across similar game states. While techniques like "history heuristics" or "RAVE" aim to address this by creating "abstractors" that generalize action values, these have typically been applied in isolation or only to specific parts of the MCTS search (selection or rollout). This paper tackles the challenge of online generalization in MCTS, meaning the ability to learn and adapt during a game, by proposing a framework that can combine multiple such abstractors to guide the entire search process.

Methods

The core innovation is the Multiple Estimator Monte Carlo Tree Search (ME-MCTS) framework. It formalizes "history abstractors" as a general concept for contextual action value estimators. These abstractors maintain value estimates and sample counts for different "contexts" (generalized histories).

ME-MCTS then uses a convex combination of multiple value estimators to guide action selection. This includes:

  • The MCTS tree itself (Ahistory): This is the unbiased, but non-generalizing, estimator.
  • Multiple abstractors: These are the generalizing estimators.

The weights for combining these estimators are learned by minimizing the expected mean squared error (MSE) of the combined estimate. This involves estimating the MSE matrix of the individual estimators, which captures their biases and variances. The paper also incorporates an upper confidence bound mechanism to balance exploration and exploitation.

Datasets

The paper evaluates ME-MCTS on four fully observable, deterministic, alternating-turn games:

  • Breakthrough
  • Knightthrough
  • Othello
  • Rolit

These are standard benchmarks for evaluating game AI algorithms.

Key Insights and Ideas

  • Combining estimators is better than using one: The central idea is that a diverse set of generalizing estimators, when combined intelligently, can outperform any single estimator.
  • Blurring the lines between selection and rollout: ME-MCTS applies generalization uniformly across all move choices within a simulation, removing the traditional distinction between the selection and rollout phases.
  • Formalizing "history abstractors": Providing a unified framework for various online generalization techniques makes it easier to plug them into ME-MCTS.
  • The importance of weighting: Simply having multiple estimators isn't enough; learning how to optimally weight their contributions based on their estimated reliability (bias and variance) is crucial for success.

Key Results

  • Significant improvements over vanilla MCTS: ME-MCTS consistently outperformed vanilla MCTS across all tested games, both when using random rollouts and static evaluation functions.
  • Combinations outperform single abstractors: In most games, combining two abstractors (e.g., Aglobal and A3x3) led to better performance than using the best single abstractor. Combining three abstractors further improved performance in some cases.
  • Abstractors are domain-dependent: The effectiveness of individual abstractors varied across games, highlighting the need for flexible combination strategies. For example, A3x3 was less effective in Rolit.
  • Performance with evaluation functions: ME-MCTS also showed strong results when combined with static evaluation functions, a popular trend in modern game AI.

Limitations and Future Work

  • Deterministic, fully observable games: The current experiments are limited to these settings. The authors suggest ME-MCTS naturally extends to more challenging domains like MDPs, stochastic games, or partially observable games.
  • Computational Overhead: The overhead of computing and combining abstractors can be significant, especially within tight time limits. Future work could explore optimizations, incremental computations, and caching.
  • Learning Abstraction Functions: The paper uses pre-defined abstractors. Learning optimal abstraction functions end-to-end (e.g., using neural networks) is a promising future direction.
  • More sophisticated estimator combination: Exploring more advanced methods for estimating the MSE matrix and combining estimators, potentially using function approximators that can assess uncertainty, is also suggested.

Summary updated

BibTeX
@inproceedings{baier2021me,
  author = {Hendrik Baier and Michael Kaisers},
  title = {{ME-MCTS: Online Generalization by Combining Multiple Value Estimators}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/555},
}
Figure