Novelty and MCTS
Hendrik Baier, Michael Kaisers · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2021
Novelty search has become a popular technique in different fields such as evolutionary computing, classical AI planning, and deep reinforcement learning. Searching for novelty instead of, or in addition to, directly maximizing the search objective, aims at avoiding dead ends and local minima, and overall improving exploration. We propose and test the integration of novelty into Monte Carlo Tree Search (MCTS), a state-of-the-art framework for online RL planning, by linearly combining value estimates with novelty scores during the selection phase of MCTS. Three different novelty measures are adapted from the literature, integrated into MCTS, and tested in four different board games. The initial results are promising and point towards potential for novelty as "online generalization for uncertainty" in more challenging search settings.