PUCT (Polynomial Upper Confidence Tree)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 02:35 UTC 版)
「モンテカルロ木探索」の記事における「PUCT (Polynomial Upper Confidence Tree)」の解説
PUCT は David Auger, Adrien Couetoux, Olivier Teytaud が2013年に発表した手法。 木は根は決断ノードとし、決断ノードとランダムノードを交互に繰り返す形で構築する。決断ノードで行為 a を選択し、ランダムノードに遷移する。 決断ノード z を選択した場合、 ⌊ n ( z ) α ⌋ > ⌊ ( n ( z ) − 1 ) α ⌋ {\displaystyle \lfloor n(z)^{\alpha }\rfloor >\lfloor (n(z)-1)^{\alpha }\rfloor } ならば、そのノードでシミュレーションを行う さもなければ V ^ ( z , a ) + n ( z ) e ( d ) n ( z , a ) {\displaystyle {\hat {V}}(z,a)+{\sqrt {\frac {n(z)^{e(d)}}{n(z,a)}}}} が最大となる子ノードを選択する ランダムノード w を選択した場合、 ⌊ n ( w ) α ⌋ = ⌊ ( n ( w ) − 1 ) α ⌋ {\displaystyle \lfloor n(w)^{\alpha }\rfloor =\lfloor (n(w)-1)^{\alpha }\rfloor } ならば、最も訪れていない子ノードを選択する さもなければ、新しい子ノードを作成する 関数は以下の通り。 V ^ ( z , a ) {\displaystyle {\hat {V}}(z,a)} - 決断ノード z で行為 a を選択した際のランダムノードでの平均報酬（勝率など） n ( z ) {\displaystyle n(z)} - 決断ノード z の訪問回数 n ( z , a ) {\displaystyle n(z,a)} - 決断ノード z で行為 a を選択した際のランダムノードの訪問回数 α ( d ) {\displaystyle \alpha (d)} - 深さ d に対して定めた progressive widening 係数（定数） e ( d ) {\displaystyle e(d)} - 深さ d に対して定めた探索係数（定数）
※この「PUCT (Polynomial Upper Confidence Tree)」の解説は、「モンテカルロ木探索」の解説の一部です。
「PUCT (Polynomial Upper Confidence Tree)」を含む「モンテカルロ木探索」の記事については、「モンテカルロ木探索」の概要を参照ください。
- PUCTのページへのリンク
