{"action":"created","issue":{"url":"https://api.github.com/repos/gcp/leela-zero/issues/860","repository_url":"https://api.github.com/repos/gcp/leela-zero","labels_url":"https://api.github.com/repos/gcp/leela-zero/issues/860/labels{/name}","comments_url":"https://api.github.com/repos/gcp/leela-zero/issues/860/comments","events_url":"https://api.github.com/repos/gcp/leela-zero/issues/860/events","html_url":"https://github.com/gcp/leela-zero/issues/860","id":296232530,"number":860,"title":"MCTS alternatives","user":{"login":"roy7","id":4165289,"avatar_url":"https://avatars0.githubusercontent.com/u/4165289?v=4","gravatar_id":"","url":"https://api.github.com/users/roy7","html_url":"https://github.com/roy7","followers_url":"https://api.github.com/users/roy7/followers","following_url":"https://api.github.com/users/roy7/following{/other_user}","gists_url":"https://api.github.com/users/roy7/gists{/gist_id}","starred_url":"https://api.github.com/users/roy7/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/roy7/subscriptions","organizations_url":"https://api.github.com/users/roy7/orgs","repos_url":"https://api.github.com/users/roy7/repos","events_url":"https://api.github.com/users/roy7/events{/privacy}","received_events_url":"https://api.github.com/users/roy7/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":119,"created_at":"2018-02-11T22:29:56Z","updated_at":"2018-05-06T03:01:33Z","closed_at":null,"author_association":"CONTRIBUTOR","body":"Since a lot of people are working on tuning FPU at the moment and some people are exploring tweaks to the search algorithm I wanted to share a few areas of research I was looking over this evening, in case the more mathematical programmers among us were interested in trying these with LZ.\r\n\r\nAfter reviewing [Multi Armed Bandits and Exploration Strategies](https://sudeepraja.github.io/Bandits/) I was interested in the mention of Thompson Sampling. It's an alternative to UCB that also has a logarithmic bound on regret and has been known since the 1930s, but the theoretical groundwork on it has only recently been finished in 2012 in the paper [Analysis of Thompson Sampling for the Multi-armed Bandit Problem](http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf). That paper also covers the stochastic case, which makes it more applicable for us by people like us.\r\n\r\nSo I searched around some more if anyone has used this with MCTS yet, and it turns out this is a pretty hot current research area. There's a 2014 paper [Thompson Sampling Based Monte-Carlo Planning in POMDPs](https://aijunbai.github.io/publications/ICAPS14-Bai.pdf), and two 2017 master's thesis I found, [Thompson Sampling for Monte Carlo Tree Search and Maxi-min Action Identification](https://www.universiteitleiden.nl/binaries/content/assets/science/mi/scripties/master/2017-2018/master-thesis_mingxi-li_12okt2017.pdf) and [Monte Carlo Tree Search with Thompson Sampling in the Settlers of Catan](http://eprints.fri.uni-lj.si/3504/1/63100285-Katja_Tuma-Drevesno_preiskovanje_Monte_Carlo_s_Thompsonovim_vzor%C4%8Denjem_pri_igri_Prebivalci_otoka_Catan_(3).pdf) (two languages). \r\n\r\nA recent paper following up on these things is [Enhancements in Monte Carlo Tree Search\r\nAlgorithms for Biased Game Trees](https://pdfs.semanticscholar.org/4526/21321d943c924553fc2ad2e8e12b2225d7ea.pdf). This paper discusses a way to deal with biases in game trees that might be useful for us, applying to 3 types of MCTS (UCT, TS, and KL-UCB). I hadn't heard of KL-UCB before, this paper mentioned that it performs better and has better theoretical bounds on regret than UCT does. The source for KL-UCB is the paper [KULLBACK–LEIBLER UPPER CONFIDENCE BOUNDS FOR OPTIMAL SEQUENTIAL ALLOCATION](https://pdfs.semanticscholar.org/4526/21321d943c924553fc2ad2e8e12b2225d7ea.pdf).\r\n\r\nSo for those interested in recent research, you might find some of these interesting. I don't know of any Go projects that use anything other than UCT for MCTS, I imagine most research effort goes into the neural network side of things and not improving the tree search side of things. Perhaps this is an area someone would like to do some original research into.\r\n\r\nEdit: @alreadydone [mentioned](https://github.com/gcp/leela-zero/issues/860#issuecomment-366450015) new paper [Memory-Augmented Monte Carlo Tree Search](http://webdocs.cs.ualberta.ca/~mmueller/ps/2018/Chenjun-Xiao-M-MCTS-aaai18-final.pdf)."},"comment":{"url":"https://api.github.com/repos/gcp/leela-zero/issues/comments/386850069","html_url":"https://github.com/gcp/leela-zero/issues/860#issuecomment-386850069","issue_url":"https://api.github.com/repos/gcp/leela-zero/issues/860","id":386850069,"user":{"login":"roy7","id":4165289,"avatar_url":"https://avatars0.githubusercontent.com/u/4165289?v=4","gravatar_id":"","url":"https://api.github.com/users/roy7","html_url":"https://github.com/roy7","followers_url":"https://api.github.com/users/roy7/followers","following_url":"https://api.github.com/users/roy7/following{/other_user}","gists_url":"https://api.github.com/users/roy7/gists{/gist_id}","starred_url":"https://api.github.com/users/roy7/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/roy7/subscriptions","organizations_url":"https://api.github.com/users/roy7/orgs","repos_url":"https://api.github.com/users/roy7/repos","events_url":"https://api.github.com/users/roy7/events{/privacy}","received_events_url":"https://api.github.com/users/roy7/received_events","type":"User","site_admin":false},"created_at":"2018-05-06T03:01:33Z","updated_at":"2018-05-06T03:01:33Z","author_association":"CONTRIBUTOR","body":"Speaking of which, here's a paper on UCBT with arms that have changing rewards and overcoming UCBT inertia (the whole point of max_lcb_root).\r\n\r\n[Change Point Detection and Meta-Bandits for Online Learning in Dynamic Environments](https://www.researchgate.net/publication/29646788_Change_Point_Detection_and_Meta-Bandits_for_Online_Learning_in_Dynamic_Environments).\r\n\r\nIt's the source paper for an algorithm called Adapt-EvE which is referred to in prior post I made.\r\n"}}
{"actor":{"display_login":"roy7"}}