Convex Regularization in Monte-Carlo Tree Search

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

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

16 Lataukset (Pure)


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.

OtsikkoProceedings of the 38th International Conference on Machine Learning, PMLR 139, 2021
ToimittajatM Meila, T Zhang
TilaJulkaistu - 2021
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaInternational Conference on Machine Learning - Virtual, Online
Kesto: 18 heinäk. 202124 heinäk. 2021
Konferenssinumero: 38


NimiProceedings of Machine Learning Research
ISSN (painettu)2640-3498


ConferenceInternational Conference on Machine Learning
KaupunkiVirtual, Online


Sukella tutkimusaiheisiin 'Convex Regularization in Monte-Carlo Tree Search'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä