Doctoral thesis (Dissertations and theses)
Contributions to Monte Carlo Search
Lupien St-Pierre, David
2013
 

Files


Full Text
thesis_dlspierre.pdf
Author preprint (2.51 MB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Monte-Carlo; AI; Games
Abstract :
[en] This research is motivated by improving decision making under uncertainty and in particular for games and symbolic regression. The present dissertation gathers research contributions in the field of Monte Carlo Search. These contributions are focused around the selection, the simulation and the recommendation policies. Moreover, we develop a methodology to automatically generate an MCS algorithm for a given problem. For the selection policy, in most of the bandit literature, it is assumed that there is no structure or similarities between arms. Thus each arm is independent from one another. In several instances however, arms can be closely related. We show both theoretically and empirically, that a significant improvement over the state-of-the-art selection policies is possible. For the contribution on simulation policy, we focus on the symbolic regression problem and ponder on how to consistently generate different expressions by changing the probability to draw each symbol. We formalize the situation into an optimization problem and try different approaches. We show a clear improvement in the sampling process for any length. We further test the best approach by embedding it into a MCS algorithm and it still shows an improvement. For the contribution on recommendation policy, we study the most common in combination with selection policies. A good recommendation policy is a policy that works well with a given selection policy. We show that there is a trend that seems to favor a robust recommendation policy over a riskier one. We also present a contribution where we automatically generate several MCS algorithms from a list of core components upon which most MCS algorithms are built upon and compare them to generic algorithms. The results show that it often enables discovering new variants of MCS that significantly outperform generic MCS algorithms.
Disciplines :
Computer science
Author, co-author :
Lupien St-Pierre, David ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore)
Language :
English
Title :
Contributions to Monte Carlo Search
Defense date :
29 July 2013
Number of pages :
149
Institution :
ULiège - Université de Liège
Degree :
Doctorat en Sciences de l'Ingénieur
Promotor :
Louveaux, Quentin ;  Université de Liège - ULiège > Montefiore Institute of Electrical Engineering and Computer Science
Ernst, Damien  ;  Université de Liège - ULiège > Montefiore Institute of Electrical Engineering and Computer Science
President :
Boigelot, Bernard  ;  Université de Liège - ULiège > Montefiore Institute of Electrical Engineering and Computer Science
Jury member :
Teytaud, Olivier
Lucas, Simon M.
Cazenave, Tristan
Available on ORBi :
since 20 August 2013

Statistics


Number of views
98 (13 by ULiège)
Number of downloads
174 (6 by ULiège)

Bibliography


Similar publications



Contact ORBi