GA将?開発日記~王の理とは~

ネタ勢最強を目指して絶賛開発中。

「Combining policy gradient and Q-learning」を読んで、実装する為に最低限必要な知識をまとめてみた。

arxiv.org

前提

 二人零和有限確定完全情報ゲームで、自己対局の結果からPGQ(論文の提案アルゴリズム)を用いて評価関数パラメータの学習を行う事を目的とします。

 報酬は「勝ち:+1、引き分け:0、負け:-1」と設定し、終局後に報酬を与えるものとします。

 方策勾配法やQ学習に関しては本エントリでは解説しませんので、適当なリソースに当たって下さい。

論文の重要な部分

 まず、エントロピー正則化ありの方策勾配法を考えます。方策π・状態sに対するエントロピーHは次式です。

  H^\pi\left(s\right)=-\sum_a\pi\left(s,a\right)\log\pi\left(s,a\right)

 この時、方策勾配法の停留点*1における状況から、「方策π・エントロピーH・状態価値Vを元に行動価値Qを計算出来る」というのが最大のポイントです。

 具体的には、論文の式(5)です。(一部省略して記載します。)

  \tilde{Q}^\pi\left(s,a\right)=\alpha\left(\log\pi\left(s,a\right)+H^\pi\left(s\right)\right)+V^\pi\left(s\right)

 なお、αはエントロピー正則化係数で、通常は0.01とか0.1が使用される様です。

パラメータ更新則

 方策πはパラメータθを、状態価値関数Vはパラメータwを持ちます。この時、パラメータ更新則は次式の通りです。(論文の式(14)。)

  \Delta\theta \propto \left( 1 - \eta \right) E_{s,a} \left(Q^\pi-\tilde{Q}^\pi\right)\nabla_\theta\log\pi + \eta E_{s,a} \left(T^*\tilde{Q}^\pi-\tilde{Q}^\pi\right)\nabla_\theta\log\pi
  \Delta w \propto \left( 1 - \eta \right) E_{s,a} \left(Q^\pi-\tilde{Q}^\pi\right)\nabla_w + \eta E_{s,a} \left(T^*\tilde{Q}^\pi-\tilde{Q}^\pi\right)w

 ηは第一項と第二項のバランスを取る為のパラメータで、0~1の値を設定します。Q^\piは方策πに従って得られた報酬を用いれば良い様です。

 E_{s,a}で期待値を取る計算が出て来ますが、これはREINFORCEの様にサンプリング結果から計算すればOKかと。

 また、T^*は最適ベルマンオペレータで、論文中では3ページ目に記載があります。

  T^*Q\left(s,a\right)=\underset{s',r'}{E}\left(r\left(s,a\right) + \gamma \underset{b}{max} Q\left(s', b\right)\right)

 まー要するに、通常のQ学習の目標値を求めるやり方ですね。

GA将?の実装にあたって

 ここからは論文に書いてない事で、「私はこうしました」って話です。

 まず、論文ではパラメータθとwは別個に持っている様でしたが、わざわざ2つに分ける必要性を感じませんでしたので、θのみにしてあります。

 具体的には、方策πと状態価値関数Vは下記の通りです。

  \pi\left(s,a|\theta\right)=\frac{\exp\left(evl\left(s,a|\theta\right)/T\right)}{\sum_x\exp\left(evl\left(s,x|\theta\right)/T\right)}
  V\left(s|\theta\right)=2 \cdot sigmoid\left(evl\_qui\left(s|\theta\right)\right) - 1

 evl(s,a|θ)は「パラメータθを用いて、局面sから手aを指した後の探索結果(評価値)」、evl_qui(s|θ)は「パラメータθを用いて、局面sから静止探索をして得られた探索結果(評価値)」です。Vに関しては、報酬が-1~+1なのでVの値もその範囲に収まる様にしています*2

 メタパラメータですが、α=0.1・η=0.5が三目並べでの実験結果では最適でしたので、本将棋モードでも同様の値を使用しています。

実験結果

 5五将棋モードでの結果ですが、従来のGA将?の学習則(PGLeafとMCの勾配を個別に計算し、適当に加算して最終的な勾配とする)よりも、収束後のレーティングが60程度向上しました。やっぱり、理論的にきちんと考えられているアルゴリズムは優秀ですね。

*1:局所最適解…だと思います。間違っていたらご指摘お願いします。

*2:実験的に、この方が性能が良かった為。