Convex Regularization in Monte-Carlo Tree Search

Tuan Dam*, Carlo D'Eramo, Jan Peters, Joni Pajarinen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2 Downloads (Pure)

Abstract

Monte-Carlo planning and Reinforcement Learning (RL) are essential to sequential decision making. The recent AlphaGo and AlphaZero algorithms have shown how to successfully combine these two paradigms to solve large-scale sequential decision problems. These methodologies exploit a variant of the well-known UCT algorithm to trade off the exploitation of good actions and the exploration of unvisited states, but their empirical success comes at the cost of poor sample-efficiency and high computation time. In this paper, we overcome these limitations by introducing the use of convex regularization in Monte-Carlo Tree Search (MCTS) to drive exploration efficiently and to improve policy updates. First, we introduce a unifying theory on the use of generic convex regularizers in MCTS, deriving the first regret analysis of regularized MCTS and showing that it guarantees an exponential convergence rate. Second, we exploit our theoretical framework to introduce novel regularized backup operators for MCTS, based on the relative entropy of the policy update and, more importantly, on the Tsallis entropy of the policy, for which we prove superior theoretical guarantees. We empirically verify the consequence of our theoretical results on a toy problem. Finally, we show how our framework can easily be incorporated in AlphaGo and we empirically show the superiority of convex regularization, w.r.t. representative baselines, on well-known RL problems across several Atari games.

Original languageEnglish
Title of host publicationProceedings of the 38th International Conference on Machine Learning, PMLR 139, 2021
EditorsM Meila, T Zhang
PublisherJMLR
Number of pages11
Publication statusPublished - 2021
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Machine Learning - Virtual, Online
Duration: 18 Jul 202124 Jul 2021
Conference number: 38

Publication series

NameProceedings of Machine Learning Research
PublisherJMLR
Volume139
ISSN (Print)2640-3498

Conference

ConferenceInternational Conference on Machine Learning
Abbreviated titleICML
CityVirtual, Online
Period18/07/202124/07/2021

Keywords

  • GAME
  • GO

Fingerprint

Dive into the research topics of 'Convex Regularization in Monte-Carlo Tree Search'. Together they form a unique fingerprint.

Cite this