Re: Monte-Carlo Tree Search as Regularized Policy Optimization
Daniel <[email protected]> Sun, 19 Jul 2020 11:31:56 -0600
| Newsgroups | gmane.games.devel.go |
|---|---|
| Message-ID | <CAN8pvoTCbu1CEqKw5zHVGnoxx9S0JhFe1Wdu9mLKRa4EdFqu7g@mail.gmail.com> |
--===============2641267652199427059== Content-Type: multipart/alternative; boundary="000000000000e8a99505aacec482" --000000000000e8a99505aacec482 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable @Kensuke I suppose all the proposed algorithms ACT, SEARCH and LEARN are meant to be used during training, no? I think I understand ACT and LEARN but I am not sure about SEARCH for which they say this: > During search, we propose to stochastically sample actions according to =CF=80=C2=AF instead of the deterministic action selection rule of Eq. 1. This sounds much like the random selection done at the root with temperature, but this time applied at internal nodes. Does it mean the pUCT formula is not used? Why does the selection have to be stochastic now? On selection, you compute =CF=80_bar every time from (q, =CF=80_theta, n_vi= sits) so I suppose =CF=80_bar has everything it needs to balance exploration and exploitation. On Sun, Jul 19, 2020 at 8:10 AM David Wu <[email protected]> wrote: > I imagine that at low visits at least, "ACT" behaves similarly to Leela > Zero's "LCB" move selection, which also has the effect of sometimes > selecting a move that is not the max-visits move, if its value estimate h= as > recently been found to be sufficiently larger to balance the fact that it > is lower prior and lower visits (at least, typically, this is why the mov= e > wouldn't have been the max visits move in the first place). It also scale= s > in an interesting way with empirical observed playout-by-playout variance > of moves, but I think by far the important part is that it can use > sufficiently confident high value to override max-visits. > > The gain from "LCB" in match play I recall is on the very very rough orde= r > of 100 Elo, although it could be less or more depending on match conditio= ns > and what neural net is used and other things. So for LZ at least, > "ACT"-like behavior at low visits is not new. > > > On Sun, Jul 19, 2020 at 5:39 AM Kensuke Matsuzaki <[email protected]> > wrote: > >> Hi, >> >> I couldn't improve leela zero's strength by implementing SEARCH and ACT. >> https://github.com/zakki/leela-zero/commits/regularized_policy >> >> 2020=E5=B9=B47=E6=9C=8817=E6=97=A5(=E9=87=91) 2:47 R=C3=A9mi Coulom <rem= [email protected]>: >> > >> > This looks very interesting. >> > >> > From a quick glance, it seems the improvement is mainly when the numbe= r >> of playouts is small. Also they don't test on the game of Go. Has anybod= y >> tried it? >> > >> > I will take a deeper look later. >> > >> > On Thu, Jul 16, 2020 at 9:49 AM Ray Tayek <[email protected]> wrote: >> >> >> >> >> https://old.reddit.com/r/MachineLearning/comments/hrzooh/r_montecarlo_tr= ee_search_as_regularized_policy/ >> >> >> >> >> >> -- >> >> Honesty is a very expensive gift. So, don't expect it from cheap >> people - Warren Buffett=EF=BB=BF >> >> http://tayek.com/ >> >> >> >> _______________________________________________ >> >> Computer-go mailing list >> >> [email protected] >> >> http://computer-go.org/mailman/listinfo/computer-go >> > >> > _______________________________________________ >> > Computer-go mailing list >> > [email protected] >> > http://computer-go.org/mailman/listinfo/computer-go >> >> >> >> -- >> Kensuke Matsuzaki >> _______________________________________________ >> Computer-go mailing list >> [email protected] >> http://computer-go.org/mailman/listinfo/computer-go >> > _______________________________________________ > Computer-go mailing list > [email protected] > http://computer-go.org/mailman/listinfo/computer-go > --000000000000e8a99505aacec482 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">@Kensuke I suppose all the proposed algorithms ACT, SEARCH= and LEARN are meant to be used during training, no?<br>I think I understan= d ACT and LEARN but I am not sure about SEARCH for which they say this:<br>= <br>>=C2=A0During search, we propose to stochastically sample actions according to =CF=80=C2=AF instead of the deterministic action selection rule of Eq. 1.<br><br>This sounds much l= ike the random selection done at the root with temperature, but this time a= pplied at internal nodes.<br>Does it mean the pUCT formula is not used? Why= does the selection have to be stochastic now?<div>On selection, you comput= e =CF=80_bar every time from (q,=C2=A0=CF=80_theta, n_visits) so I suppose = =CF=80_bar has everything it needs to balance exploration and exploitation.= <br><br></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class= =3D"gmail_attr">On Sun, Jul 19, 2020 at 8:10 AM David Wu <<a href=3D"mai= lto:[email protected]">[email protected]</a>> wrote:<br></div><b= lockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-le= ft:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr">I imagine = that at low visits at least, "ACT" behaves similarly to Leela Zer= o's "LCB" move selection, which also has the effect of someti= mes selecting a move that is not the max-visits move, if its=C2=A0value est= imate has recently been found to be sufficiently larger to balance the fact= that it is lower prior and lower visits (at least, typically, this is why = the move wouldn't have been the max visits move in the first place). It= also scales in an interesting way with empirical observed playout-by-playo= ut variance of moves, but I think by far the important part is that it can = use sufficiently confident high value to override max-visits.<div><br></div= ><div>The gain from "LCB" in match play I recall is on the very v= ery rough order of 100 Elo, although it could be less or more depending on = match conditions and what neural net is used and other things. So for LZ at= least, "ACT"-like behavior at low visits is not new.</div><div><= br></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gma= il_attr">On Sun, Jul 19, 2020 at 5:39 AM Kensuke Matsuzaki <<a href=3D"m= ailto:[email protected]" target=3D"_blank">[email protected]</a>> wr= ote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px= 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi,<br> <br> I couldn't improve leela zero's strength by implementing SEARCH and= ACT.<br> <a href=3D"https://github.com/zakki/leela-zero/commits/regularized_policy" = rel=3D"noreferrer" target=3D"_blank">https://github.com/zakki/leela-zero/co= mmits/regularized_policy</a><br> <br> 2020=E5=B9=B47=E6=9C=8817=E6=97=A5(=E9=87=91) 2:47 R=C3=A9mi Coulom <<a = href=3D"mailto:[email protected]" target=3D"_blank">[email protected]= om</a>>:<br> ><br> > This looks very interesting.<br> ><br> > From a quick glance, it seems the improvement is mainly when the numbe= r of playouts is small. Also they don't test on the game of Go. Has any= body tried it?<br> ><br> > I will take a deeper look later.<br> ><br> > On Thu, Jul 16, 2020 at 9:49 AM Ray Tayek <<a href=3D"mailto:rtayek= @ca.rr.com" target=3D"_blank">[email protected]</a>> wrote:<br> >><br> >> <a href=3D"https://old.reddit.com/r/MachineLearning/comments/hrzoo= h/r_montecarlo_tree_search_as_regularized_policy/" rel=3D"noreferrer" targe= t=3D"_blank">https://old.reddit.com/r/MachineLearning/comments/hrzooh/r_mon= tecarlo_tree_search_as_regularized_policy/</a><br> >><br> >><br> >> --<br> >> Honesty is a very expensive gift. So, don't expect it from che= ap people - Warren Buffett=EF=BB=BF<br> >> <a href=3D"http://tayek.com/" rel=3D"noreferrer" target=3D"_blank"= >http://tayek.com/</a><br> >><br> >> _______________________________________________<br> >> Computer-go mailing list<br> >> <a href=3D"mailto:[email protected]" target=3D"_blank">C= [email protected]</a><br> >> <a href=3D"http://computer-go.org/mailman/listinfo/computer-go" re= l=3D"noreferrer" target=3D"_blank">http://computer-go.org/mailman/listinfo/= computer-go</a><br> ><br> > _______________________________________________<br> > Computer-go mailing list<br> > <a href=3D"mailto:[email protected]" target=3D"_blank">Compu= [email protected]</a><br> > <a href=3D"http://computer-go.org/mailman/listinfo/computer-go" rel=3D= "noreferrer" target=3D"_blank">http://computer-go.org/mailman/listinfo/comp= uter-go</a><br> <br> <br> <br> -- <br> Kensuke Matsuzaki<br> _______________________________________________<br> Computer-go mailing list<br> <a href=3D"mailto:[email protected]" target=3D"_blank">Computer-g= [email protected]</a><br> <a href=3D"http://computer-go.org/mailman/listinfo/computer-go" rel=3D"nore= ferrer" target=3D"_blank">http://computer-go.org/mailman/listinfo/computer-= go</a><br> </blockquote></div> _______________________________________________<br> Computer-go mailing list<br> <a href=3D"mailto:[email protected]" target=3D"_blank">Computer-g= [email protected]</a><br> <a href=3D"http://computer-go.org/mailman/listinfo/computer-go" rel=3D"nore= ferrer" target=3D"_blank">http://computer-go.org/mailman/listinfo/computer-= go</a><br> </blockquote></div> --000000000000e8a99505aacec482-- --===============2641267652199427059== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ Computer-go mailing list [email protected] http://computer-go.org/mailman/listinfo/computer-go --===============2641267652199427059==--