MCTSnetの解説は他にもある
ので、そちらも参照されたし。この記事では損失計算部分にだけ注目して記述する。
arXiv版とOpenReview版は式番号が異なるので注意。OpenReview(ICLR2018)で一回Rejectになって、ICML2018に通っていて、arXivの最新版はそのICMLにある版のと近そうなので、とりあえずこの記事では基本的にarXiv版に準拠する。
3.5 MCTSnetの訓練
MCTSnetの読み出しネットワークは、最終的に探索全体を考慮した行動決定および評価を出力する。 この最終出力は、基本的に値ベースの学習や方策勾配法などの損失関数に従って(つまり強化学習によって)訓練できるが、簡単のため以下では各状態で教師行動が決まっているもとで教師あり学習でMCTSnetを学習することを考える。
記号の定義
- : 回目のシミュレーションで確率的にサンプリングされた行動系列
- : 回目までのシミュレーションで確率的にサンプリングされた行動系列の系列
- : 確率変数としての
- : 総シミュレーション回数
基本的には回シミュレーションを行った後の最終的な出力方策について、教師行動について交差エントロピーを計算する。
上式は周辺分布についての対数尤度の下限としても解釈できる(※ここはよくわからない)。
そして現実的に全てについて計算できるわけはないので、一つのサンプルについて勾配の推定を行う。(Schulman et al., 2015が引用されているのでちらっと見てみたがよくわからなかった)
(この式中のはの間違いである気もするが、とりあえず論文通りの記述にしておく)
最初の項は単純に上の損失をそのまま微分したもの。
2番目の項はシミュレーション分布に関する勾配に対応し、REINFORCEアルゴリズムあるいはActor-Criticのようなやり方によって学習する。この項においてが報酬信号の役割を果たす。これが大きくなるようなシミュレーション系列は良いシミュレーション系列だったと見なすことができるため。
(式としては記述がないが?)シミュレーション方策に負のエントロピー正則化項を追加する。
3.6 信頼割り当ての工夫
REINFORCE勾配は不偏だが分散が大きい。最終的な行動を決定するまでに回のシミュレーションが寄与していて、各シミュレーション中でもどのノードを選択していくかという問題があるため計からほどの行動決定があり、信頼の割り当てが難しい。これに対処するため一つの逐次的決定問題のサンプルからBias-Varianceのトレードオフを調整できる手法を提案する。
回のシミュレーションを行うとして、のいつでも最終的な行動決定分布を考え、損失を計算することはできる。回時点での損失をと定義する。
最終目標はの最大化である。としたとき、この最終的な損失は次のように変形できる。
と置くと、これは回目のシミュレーションで損失が減少した量であると見なせる。ここで、回目以降のこの量の累積和をと置くと、最終的に求めたい量はである。
式(9)のREINFORCE項についてと置くと、
(次の式以降そうなるのだが、ここも多分ではなくだと思われる。まぁ自明なものとして省略しているのか)
ここでにおける確率変数は以降の部分にしか影響を及ぼさないことからの部分はに置き換えることができ、
とすることができる。つまり、回目のシミュレーション終了時点では、最終損失をそのまま強化信号として使うのではなく、最終損失と回目時点での差分を使用する。これによってバイアスは生じないまま分散は小さくなる。
さらに割引率を導入してバイアスと分散のトレードオフを行う。回目のシミュレーションは回目に続く近いところで多く貢献していると考え、遠い未来についての貢献は多少考慮する量を減らすという意味合いがある。と置いて、MCTSnetの最終的な勾配計算は