TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。

リバーシ(オセロ)で深層強化学習 その７（Prioritized Experience Replay）

強化学習 オセロ PyTorch リバーシ

リバーシ(オセロ)で深層強化学習を試すシリーズ、前回からしばらく空いたが、今回はPrioritized Experience Replayを試す。

Prioritized Experience Replay

強化学習では、サンプルの時間依存の相関を弱めるために、サンプルを乱択する経験再生（experience peplay）をいうヒューリスティックが用いられる。
DQNでは、さらにリプレイメモリを用いて、過去の経験からもサンプリングすることで、過去の経験を一定期間忘れないようにする。
リプレイメモリは、基本的には方策オフ型の強化学習で使用される。

DQNでは、リプレイメモリから均一にサンプリングされるが、Prioritized Experience Replay（優先順位付き経験再生）では、重要なサンプルをより頻繁に再生し、より効率的に学習できるようにする。

優先順位

TD誤差を優先順位の尺度とする。
現在のネットワークの予測結果と、1ステップ後の\max _{a} Q\left(s^{\prime}, a\right)の差が大きいほど優先的に再生する。
すでに予測の誤差が少ない遷移については、学ぶ必要が少ないため、再生する頻度を減らす。

遷移iをサンプリングする確率は、以下の式で決定する。
\displaystyle P(i) = \frac{p_i^{\alpha}}{\sum_k p_k^{\alpha}}
p_iは、遷移iの優先度を表し、指数\alphaは優先度がどれだけ使用されるかを決定する。
\alpha=1の場合、一様にサンプルされる。

論文では、p_iの決め方は、proportionalとrank-basedの2種類が提案されている。

1つ目のproportionalでは、以下の式で優先度を決める。
\displaystyle p_i = |\delta_i| + \epsilon
ここで、|\delta_i|はTD誤差の絶対値、\epsilonは正の小さな定数で誤差が0の場合にまったく再生されなくなることを防ぐ。

2つ目のrank-basedでは、以下の式で優先度を決める。
\displaystyle p_i = \frac{1}{\operatorname{rank}(i)}
ここで、rank(i)は、リプレイメモリが|\delta_i|に従ってソートされたときの遷移iのランクである。

毎イテレーションで、各サンプルのp_iを計算するのは、O(N)の計算が必要でリプレイメモリのサイズが大きい場合重たい処理である。
proportionalは、sum-treeを使うことで効率的に実装することができる。
sum-treeを使うことで計算量は、O(log N)になる。

sum-treeについては、以前に記事にしたので参考にしてほしい。

論文に記載されているproportionalとrank-basedのAtariのスコアを、以下に示す。どちらかが一方的に良いというわけではないようだ。
f:id:TadaoYamaoka:20200126174201p:plain

優先度の初期値

優先度に使用するTD誤差は、DQNではリプレイメモリからサンプリングしてネットワークを更新するタイミングでバッチで計算を行う。
一方、リプレイメモリに遷移を格納するタイミングは、エピソードを作成するタイミングになる。
このタイミングでTD誤差を計算するのは効率が悪い。
そこで、これまでの優先度の最大値で初期化して、サンプリングされたタイミングで実際のTD誤差に更新を行う。

重要度サンプリング

確率的勾配法は、サンプルの分布に依存した更新が行われる。
優先度の高い遷移が頻繁に再生されると分布に偏りが起きるため、バイアスがかかる。

このバイアスを修正するために、重要度サンプリングを使い、以下の式で更新を重み付けする。
\displaystyle w_i = \left(\frac{1}{N} \cdot \frac{1}{P(i)}\right)^{\beta}
ここで、\betaはどれだけ補正を行うかを制御する。\beta=1の場合、サンプルの偏りを完全に補正する。
安定性の理由から、w_iを1/\max_i w_iで正規化する。

proportionalの場合、実装上\max_i w_iを効率的に計算するために、min P(i)をmin-treeを使って探索する。

実装

効率的な実装が可能なため、優先度にはproportionalを使用して実装を行う。

前回までのDQNの実装と変更になるのは、リプレイメモリの実装のみである。

sum-treeとmin-treeの実装は、少々複雑である。
以下のPyTorchによるチュートリアルの実装を参考にさせてもらった。
GitHub - qfettes/DeepRL-Tutorials: Contains high quality implementations of Deep Reinforcement Learning algorithms written in PyTorch

ソース

creversi_gym/dqn_per.py at master · TadaoYamaoka/creversi_gym · GitHub
※リプレイメモリの実装は、class PrioritizedReplayMemoryの部分

sum-treeとmin-treeの実装（上記チュートリアルから流用）
creversi_gym/data_structures.py at master · TadaoYamaoka/creversi_gym · GitHub

結果

バニラDQNとDDQN、DDQN+Dueling Networkの3パターンをPrioritized Experience Replayありで学習した。
1万イテレーション学習した結果は以下のようになった。

損失

f:id:TadaoYamaoka:20200126181810p:plain

比較のために、Prioritized Experience Replayなしの結果も記載する。
前回の結果は今回とリプレイメモリのサイズが異なるため再測定した（Prioritized Experience Replayはsum-treeの実装上、2の累乗にする必要がある）。
f:id:TadaoYamaoka:20200127211747p:plain

重要度により重みづけされている影響で、損失がPrioritized Experience Replayありの方は、なしの場合と比べて一桁小さくなっている。
Prioritized Experience Replayありの方が、より早く安定して損失が減少し始めているように見える。

強さ

Prioritized Experience Replayありで学習したモデルのランダムに対して1000局対局した結果は以下の通り。

結果 勝率 信頼区間95%
DQN 906勝78敗16分 92.07% 90.22%-93.6%
DDQN 880勝107敗13分 89.16% 87.07%-90.95%
DDQN+Dueling 909勝72敗19分 92.66% 90.86%-94.13%

Prioritized Experience Replayなしの結果は以下の通り。

結果 勝率 信頼区間95%
DQN 867勝111敗22分 88.65% 86.51%-90.49%
DDQN 861勝116敗23分 88.13% 85.95%-90.01%
DDQN+Dueling 901勝80敗19分 91.85% 89.96%-93.4%

Prioritized Experience Replayありで強化学習することで、DQN、DDQN、Duelingすべての場合で勝率が上がっている。
DDQN+DuelingをPrioritized Experience Replayあり学習した場合が、一番勝率が高くなった（しかし、統計量zは-0.67558>-1.96 のため有意差があるとは言えない）。

Prioritized Experience Replayありなしによらず、DDQNよりDQNの方が勝率が高いのは、以前の結果と同じである。

まとめ

Prioritized Experience Replayありで学習することで、勝率が高くなることが確認できた。
Duelingと組み合わせた場合が、一番勝率が高くなる。


次は、Distributional DQNを試したいが、次の技術書典向けの本を書くのでしばらくお休みします。
技術書典のネタは、このリバーシ(オセロ)で深層強化学習を試した内容を丁寧に解説したものにしようと思っています。