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)

Abstrakti

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.

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

Julkaisusarja

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

Conference

ConferenceInternational Conference on Machine Learning
LyhennettäICML
KaupunkiVirtual, Online
Ajanjakso18/07/202124/07/2021

Sormenjälki

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

Siteeraa tätä