2019-12-15

リバーシ(オセロ)で深層強化学習その５（DDQN）

前回は、環境を並列実行することでDQNの高速化を行った。

今回は、DQNの派生形である、Double DQN(DDQN)を試す。

Double DQN(DDQN)

一般的にQ学習は、 $\max _{a} Q\left(s_{t+1}, a\right)$ の項が行動価値を過大評価する傾向があり、それを抑制する手法としてDouble Q学習という手法がDQN以前からあった。
Double DQNは、Double Q学習の手法をDQNに適用したアルゴリズムになる。
[1509.06461] Deep Reinforcement Learning with Double Q-learning

具体的には、DQNでは行動価値の評価に単一のネットワークを使用していたが、DDQNではパラメータ $\theta$ と $\theta'$ の2つのネットワークを使用して、以下の式で行動価値を評価する。

$\displaystyle \begin{equation}\label{TDDQ} Y^{\text{DoubleQ}}_t \equiv R_{t+1} + \gamma Q(S_{t+1}, argmax_a Q(S_{t+1}, a; \theta_t); \theta'_t ) \,. \end{equation}$

この式は、パラメータ $\theta$ のネットワークが行動価値の最大となる行動を選択し、パラメータ $\theta'$ のネットワークがその行動の行動価値を評価することを意味している。

学習方法

オリジナルのDouble Q学習では、2つのネットワークをランダムに割り当て、どちらかを一方を学習することで学習を行っている。
DDQNでは、ネットワークを完全に分離するのではなく、ネットワークのパラメータを定期的にコピーすることで、2つのネットワークを実現している。
これは、DQNでも行っていたことで、DQNの自然な発展となっている。

パラメータ $\theta$ のネットワークの部分を、DQNの挙動方策に使用していたネットワーク(policy_net)を使用することで簡単に実現できる。

実装

DQNのコードとほとんど同じため、実行時引数によって、学習処理を条件分岐するようにして実装した。

if args.ddqn:
    max_a = policy_net(non_final_next_states).gather(1, non_final_next_actions).max(1)[1].unsqueeze(1)
    target_q = target_net(non_final_next_states).gather(1, non_final_next_actions)
    next_state_values[non_final_mask] = -target_q.gather(1, max_a).squeeze().detach()
else:
    target_q = target_net(non_final_next_states)
    next_state_values[non_final_mask] = -target_q.gather(1, non_final_next_actions).max(1)[0].detach()

DQNでは、target_netの出力の最大値(合法手のみ)を直接使用して、next_state_valuesを算出していたところを、DDQNでは、一旦policy_netで出力したQ値が最大(合法手のみ)となる手を選択した後、その手をtarget_netで評価している。

学習結果

学習結果は以下のようになった。

損失

損失のグラフ(1000イテレーションの移動平均)は以下の通りになった。
比較のためにDQNのグラフも載せている。
f:id:TadaoYamaoka:20191215175448p:plain

6000イテレーションくらいまでは、DQNよりも速く学習できている。
それ以降は、だいたい同じになっている。

強さ

ランダムプレイヤーと1000局対局を行った結果は以下の通りになった。

	結果	勝率(信頼区間95%)
DQN	833勝152敗15分	86.7～82.2%
DDQN	847勝131敗22分	88.6～84.3%

DDQNの方が勝率が少し高くなっている。

DDQNとDQNの対局結果は以下の通りとなった。
先後入れ替えてそれぞれ1000局対局した。
グリーディー戦略では、勝敗が決定的になるため、ソフトマックス戦略で温度は0.1とした。

先手	後手	結果	勝率(信頼区間95%)
DDQN	DQN	451勝523敗26分	49.4～43.2%
DQN	DDQN	474勝491敗35分	52.2～46.0%
計(DDQN-DQN)		942勝997敗61	52.2～50.8%

直接対局では、顕著な差ではないが、DQNの方がわずかに強いという結果になった。

Atariの結果でも、ゲームよっては悪化していたり、ほとんど差がないものもある。
f:id:TadaoYamaoka:20191215183933p:plain:w400
リバーシは差が出にくいようだ。

まとめ

DDQNでリバーシの学習を行った。
DQNと比較して、損失が速く低下するが、学習が進むと同じになることが確かめられた。
DQNと強さに明確な差はなかった。

次回は、Dueling Networkを試します。
(続く)

2019-12-15

MuZeroの論文を読むその７（ハイパーパラメータ、データ生成）

MuZero 強化学習

付録C ハイパーパラメータ

簡単にするために、以前の研究と同じアーキテクチャの選択とハイパーパラメータを優先的に使用する。
具体的には、AlphaZeroのネットワークアーキテクチャと探索の選択肢から始めた。
ボードゲームでは、AlphaZeroと同じUCB定数、ディリクレ探索ノイズ、および探索ごとに同じ800のシミュレーションを使用する。

Atariのシミュレーション回数

Atariの分岐因子がはるかに小さく、方策が単純であるため、探索を高速化するために探索ごとに50のシミュレーションのみを使用した。
図3Bに示すように、アルゴリズムはこの選択にあまり敏感ではなかった。
また、R2D2 *1と同じ割引（0.997）と価値の変換（ネットワークアーキテクチャの節を参照）を使用する。

f:id:TadaoYamaoka:20191126233406p:plain

ハイパーパラメータの詳細

本文に記載されていないパラメーター値については、擬似コードを参照。

付録D データ生成

訓練データを生成するには、ネットワークの最新のチェックポイント（1000訓練ステップごとに更新）を使用して、MCTSでゲームをプレイする。
ボードゲームの囲碁、チェス、将棋では、行動を選択するために、1回の動きにつき800回のシミュレーションが探索される。
Atariでは、行動空間がはるかに小さいため、1回の動きにつき50回のシミュレーションで十分である。

リプレイバッファ

ボードゲームの場合、ゲームが終了するとすぐに訓練ジョブに送信される。
Atariゲームの長さははるかに長い（最大30分または108,000フレーム）ため、200移動ごとに中間シーケンスが送信される。
ボードゲームでは、訓練ジョブは受信した最新の100万ゲームをメモリ内のリプレイバッファに保持する。
Atariでは、視覚的観測がより大きく、長さ200の最新の125,000シーケンスが保持される。

経験生成

ボードゲームドメインでの経験の生成中には、AlphaZeroで説明されているものと同じ探索スキームが使用される。
このスキームのバリエーションを使用して、Atari ドメインでは、最初のk回の移動だけでなく、各ゲームの期間中の訪問カウント分布から行動がサンプリングされる。
さらに、訪問数の分布は、温度パラメーターTを使用して以下の通りパラメーター化される。

$\displaystyle \begin{equation} p_{\alpha} = \frac{N(\alpha)^{1 / T}}{\sum_{b} N(b)^{1 / T}} \end{equation} \tag{6}$

温度パラメータ

Tは、ネットワークの訓練ステップ数の関数として減衰する。
具体的には、最初の500k訓練ステップでは1の温度が使用され、次の250kステップでは0.5の温度が使用され、残りの250kのステップでは0.25の温度が使用される。
これにより、訓練の進行に合わせて行動の選択が貪欲になる。

感想

ボードゲームのハイパーパラメータは、AlphaZeroに合わせています。
Atariは行動空間の大きさに合わせて、シミュレーション回数を小さくしています。
リプレイバッファのサイズは、Atariの方が多く取られています。

AlphaZeroの自己対局では、30手までは訪問数に応じたボルツマン分布から手をサンプリングして、それ以降はグリーディーに手を選択していました。
MuZeroでもボードゲームでは同じですが、Atariでは、ゲームの終了までボルツマン分布から行動をサンプリングしています。
ただし、ゲームの進行に合わせて温度パラメータを小さくしています。
理由は述べられていませんが、多様なAtariのゲームに対応するために探索的な行動がある程度必要だったのではないかと思います。

次回はネットワークについてです。
(続く)

*1:Recurrent Experience Replay in Distributed Reinforcement Learning | OpenReview

2019-12-14

MuZeroの論文を読むその６（探索）

MuZero 強化学習

付録B 探索

MuZeroで使用される探索アルゴリズムについて説明する。
私たちのアプローチは、信頼区間の上限(UCB; upper confidence bounds)のあるモンテカルロ木探索、単一エージェントドメインの最適な方策とゼロサムゲームのミニマックス価値関数に漸近的に収束するプランニングアプローチに基づいている*1。

探索木のすべてのノードは、内部状態𝑠に関連付けられている。
𝑠からの各行動𝑎には、一連の統計 $\{N(s,a), Q(s,a), P(s,a), R(s,a), S(s,a) \}$ を保存するエッジ $(s,a)$ がある。それぞれ訪問数N、平均価値Q、方策P、報酬R、および状態遷移Sを表す。

AlphaZeroと同様に、探索は3つの段階に分割され、多くのシミュレーションで繰り返される。

選択

各シミュレーションは内部ルート状態 $s^0$ から始まり、シミュレーションがリーフノード $s^l$ に到達すると終了する。
シミュレーションの各仮想時間ステップ $k = 1 \dots l$ に対して、信頼区間の上限を最大化することにより、内部状態 $s^{k-1}$ の保存された統計量に従って行動 $a^k$ が選択される*2 *3。

$\displaystyle \begin{equation} a^{k} = \\ \arg\max_{a}\bigg[ Q(s, a) + P(s, a) \cdot \frac{\sqrt{\sum_b N(s, b)}}{1 + N(s, a)} \bigg(c_1 + \log\Big(\frac{\sum_b N(s, b) + c_2 + 1}{c_2}\Big)\bigg) \bigg] \end{equation}$
$\displaystyle\tag{2}$

定数 $c_1$ および $c_2$ は、ノードがより頻繁にアクセスされるときに、価値 $Q(s, a)$ に対する事前分布 $P(s, a)$ の影響を制御するために使用される。
私たちの実験では、 $c_1 = 1.25$ および $c_2 = 19652$ である。

$k \lt l$ の場合、次の状態と報酬は、状態遷移と報酬テーブル $s^{k} = S(s^{k-1}, a^{k})$ , $r^{k} = R(s^{k-1}, a^{k})$ で検索される。

展開

シミュレーションの最後のタイムステップlで、報酬と状態がダイナミクス関数 $r^l, s^l = g_\theta(s^{l-1}, a^{l})$ によって計算され、対応するテーブル $R(s^{l-1}, a^{l}) = r^l, S(s^{l-1}, a^{l}) = s^l$ に格納される。
方策と価値は、予測関数 $\mathbf{p}^l, v^l = f_\theta(s^l)$ によって計算される。
状態 $s^l$ に対応する新しいノードが探索木に追加される。
新しく展開されたノードの各エッジ $(s^l, a)$ は、 $\{ N(s^l, a)=0, Q(s^l, a)=0, P(s^l, a)=\mathbf{p}^l \}$ に初期化される。
探索アルゴリズムは、シミュレーションごとにダイナミクス関数と予測関数をそれぞれ最大で1回呼び出すことに注意する。
計算コストはAlphaZeroと同じオーダーである。

バックアップ

シミュレーションの最後に、軌跡に沿った統計が更新される。
バックアップは、環境が(1とは異なる割引γを持っている)中間報酬を出すことができる場合に一般化されており、価値の見積もりには制限がない(ボードゲームでは、割引は1と想定されており、中間報酬はない)。
$k= l ... 0$ の場合、以下の(価値関数 $v^l$ からブートストラップされる)累積割引報酬の $l − k$ ステップ推定値を形成する。

$\displaystyle G^k = \sum_{\tau=0}^{l-1-k}{\gamma ^ \tau r_{k+ 1 +\tau}} + \gamma^{l - k} v^l \tag{3}$

$k = l ... 1$ の場合、シミュレーションパスの各エッジ $(s^{k-1}, a^{k})$ の統計を次のように更新する。

$\displaystyle \begin{equation} \begin{aligned} Q(s^{k-1},a^k) & := \frac{N(s^{k-1},a^k) \cdot Q(s^{k-1},a^k) + G^k}{N(s^{k-1},a^k) + 1} \\ N(s^{k-1},a^k) & := N(s^{k-1},a^k) + 1 \end{aligned} \end{equation} \tag{4}$

2人ゼロサムゲームでは、価値関数は[0,1]の間に制限されると想定される。
この選択により、pUCTルール（式2）を使用して、価値の推定値と確率を組み合わせることができる。
ただし、多くの環境では価値に制限がないため、pUCTルールを調整する必要がある。
簡単な解決策は、環境で観察できる最大スコアを使用して、価値を再スケーリングするか、pUCT定数を適切に設定することである*4。
ただし、どちらのソリューションもゲーム固有であり、MuZeroアルゴリズムに事前知識を追加する必要がある。
これを回避するために、MuZeroは、その時点までに探索木で観測された最小値と最大値を使用して、正規化されたQ値推定値 $\overline{Q} \in [0, 1$ ]を計算する。
選択の段階でノードに到達すると、アルゴリズムは、以下の式を使用してpUCTルールで使用されるエッジの正規化されたQ値を計算する。

$\displaystyle \begin{equation} \overline{Q}(s^{k-1}, a^k) = \frac{Q(s^{k-1}, a^k) - \min_{s, a \in Tree}Q(s, a)}{\max_{s,a \in Tree} Q(s, a) - \min_{s,a \in Tree} Q(s, a)} \end{equation} \tag{5}$

感想

学習した環境のモデルを使用してシミュレーションを行う際のアルゴリズムの詳細について述べられています。
AlphaZeroのpUCTを使用したMCTSシミュレーションとほとんど同じですが、バックアップする際の報酬に割引が適用されています。また、即時報酬にも対応しています。
これにより、ボードゲーム以外のAtariなどにも適用できるアルゴリズムになっています。
pUCTの式は、AlphaZeroの疑似コードにあった式と同じです。

次回は、ハイパーパラメータについてです。
(続く)

*1:http://ggp.stanford.edu/readings/uct.pdf

*2:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.172.9450&rep=rep1&type=pdf

*3:Science | AAAS

*4:https://dke.maastrichtuniversity.nl/m.winands/documents/CGSameGame.pdf

2019-12-08

リバーシ(オセロ)で深層強化学習その４（並列実行）

DQN リバーシオセロ強化学習高速化

前回、DQNでリバーシ(オセロ)の強化学習を試して、ランダムより強くなることを確認した。
しかし、シングルステッドでシングルゲームを繰り返しているため1万イテレーションの実行に約14時間かかった。

方策勾配法のアルゴリズムであるA2Cでは、環境を並列実行して効率を高めるという工夫がされている。
AlphaStarでも並列対戦が実装されている。

私が作成しているdlshogiでもゲームを並列で実行することで、GPUの使用効率を高めている。

DQNでも、同様にゲームを並列実行することで、効率を高めることができる。
Pythonでは、GILの制約によりマルチスレッドにしても効率がそれほど上がらない問題があるので、シングルスレッドで複数ゲームを並列で実行して、方策の計算を複数ゲームをまとめてミニバッチで処理することでGPUによる並列化を行い高速化を行うことにする。

環境の並列実行

OpenAIのbaselinesでは、環境を並列実行のためにVecEnvクラスが実装されている。
そこで、VecEnvクラスを参考にして環境の並列処理を実装した。

baselinesではマルチプロセスで環境を並列化しているが、リバーシの1ステップの処理は、creversiではSIMDを使って高速化しているため、マルチプロセスのオーバヘッドの方が大きくなる。
そこで、シングルステッドで繰り返しで処理することにした。

DQNの並列処理の実装

学習の間隔

前回のシングルスレッド、シングルゲームでの実装では、エピソード終了の区切りで学習を行っていたが、環境を並列実行するとエピソードの終了のタイミングが環境ごと異なる。
そのため、エピソードの終了ではなく一定のステップごとに学習するようにする。
ただし、ステップ数の間隔は、前回の16エピソード終了ごととだいたい同じになるように調整した。

1ステップの間に、ミニバッチサイズ分のゲームが1ステップ進行するため、

OPTIMIZE_PER_STEPS = (60 * 16 + BATCH_SIZE - 1) // BATCH_SIZE

という式で、1ゲーム60手として16エピソードごとになるようにした。

ミニバッチサイズは256とした。

方策オフについて

前回はエピソード区切りで学習していたため、1ゲームの間に方策が変わることはない。
上記のように一定のステップ間隔で学習した場合、ゲームの途中で方策が変わることになる。

方策勾配法などの方策オンの学習では、ゲームの途中で方策を変えることはできない。
一方、DQNで使用されているQ学習は、方策オフ型であり、挙動方策と推定方策を分けることができる。
よって、ゲームの途中で方策を変更しても問題がない。

学習結果

DQNを並列実行して、1万イテレーション学習した結果は以下のようになった。

損失

損失のグラフは以下のようになった。
f:id:TadaoYamaoka:20191208213014p:plain

3000イテレーションくらいまでは、前回のシングルゲームと比べて、損失が上昇している。
この違いは、並列実行することで、ミニバッチサイズ分のゲームが同じ方策を使って経験データを蓄積するため、序盤のランダムに近い方策によって生成されたデータをより多く学習するためと思われる。
3000イテレーション以降は、比較的安定して学習できている。

強さ

ランダムと1000局対局した結果は、833勝152敗15分となった。
信頼区間95%の勝率は、86.7～82.2%となった。

前回のシングルゲームの64.9～58.8%と比べて、高くなっている。
学習間隔の計算で小数点の繰り上げを行っているので、生成した局面は多くなっているのでそのままは比較できないが、実行時間に対して効率よく学習できている。

学習時間

並列実行することで、前回は1万イテレーションで、約14時間かかったが、約1時間30分に短縮された。

まとめ

環境を並列実行することで、DQNの学習を効率化できた。
マルチスレッドやマルチプロセスにしないでも、シングルスレッドで環境を並列化することでGPUを効率的に利用できる。

次回は、強化学習の他のアルゴリズムを試していきたい。

ソース

DQNの並列実行のソースはこちら。
creversi_gym/dqn_parallel.py at master · TadaoYamaoka/creversi_gym · GitHub

2019-12-08

リバーシ(オセロ)で深層強化学習その３（DQN）

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

前回、DQNのネットワークを教師ありでQ学習で学習した。
今回は、DQNを強化学習で学習する。

実装するアルゴリズムは、Nature に掲載された論文「Human-level control through deep reinforcement learning」に基づく。
DeepMindによる公式の実装は、TensorFlowもPyTorchもない時期なので、LuaJITとTorch 7.0で実装されている。

今ではTensorFlowかPyTorchで実装する方がよいので、分かりやすいチュートリアルが提供されているPyTorchの実装を参考にすることにした。

OpenAI Gymについて

PyTorchのチュートリアルは、OpenAI GymのCartPoleをDQNで学習するサンプルになっている。
強化学習は、環境とエージェントの相互作用で学習を行うが、環境とエージェントのインターフェースを統一することで、それぞれ差し替えて実験するのが容易になる。
そのために、OpenAIがインターフェースを定義して、CartPoleやその他の強化学習の研究で使用される代表的な環境を提供している。

リバーシのOpenAI Gymインターフェース

残念ながら、OpenAIではリバーシの環境は提供されていない。
そこで、リバーシのOpenAI Gymインターフェースを、creversiに実装した。

リバーシに合わせた変更

PyTorchのチュートリアルは、OpenAI GymのCartPole向けになっているので、リバーシに合わせて変更が必要になる。

エピソード完了後に学習

CartPoleでは、ステップごとに報酬が得られるが、リバーシではゲームの終了まで報酬が得られない。
リバーシでもステップごとに学習を行うことも可能だが、効率が悪いためエピソード終了の区切りで学習を行うことにする。
1回ごとに学習するよりも、数エピソードごとに学習した方が学習が安定するため、16エピソードごとに学習することした。

DQNでは、方策に使用するネットワーク(policy_net)と、価値を推定する際の使用するネットワーク(target_net)が分かれている。
policy_netは毎回学習し、target_netは一定間隔ごとにpolicy_netからパラメータがコピーされる。

CartPoleのサンプルでは、10ステップごとにコピーを行っているが、64エピソードごととした。

学習間隔とpolicy_netからtarget_netへのコピーの間隔は、チューニングが必要なハイパーパラメータになるが、今回は適当に決めている。

ミニマックスを考慮した行動価値

DQNで使用されるQ学習は、1ステップ後の行動価値の最大値を使用するが、リバーシでは1ステップ後は相手の手番のため、行動価値の符号を反転する必要がある。

割引率

DQNでは、1ステップ後の行動価値に対して割引を使用するが、ボードゲームでは割引を使用しないで学習することが多い。
AlphaZeroでも、終端の報酬を割引なしで学習している。
そのため、割引率は高めの0.99とした。

εグリーディー

DQNの方策には、εグリーディー戦略が用いられる。
基本は、policy_netで行動価値が最大となる行動が選択されるが、一定の割合εでランダムに行動が選択される。
強化学習では、すでに価値が高いとわかった行動を優先して探索するが、まだ探索していない行動の方がより価値の高い可能性があるため、未知の行動の探索も必要である。
εグリーディー戦略では、一定の割合εでランダムな行動を選択すること、探索と活用のバランスをとる。

εは、はじめに高めで、徐々に小さくしていくと良いことが知られている。
チュートリアルでは、
$\displaystyle \varepsilon_{end} + (\varepsilon_{start} - \varepsilon_{end}) \cdot \exp(-\text{steps_done} / \varepsilon_{decay})$
という式が使用されている。
ここで、 $\varepsilon_{start}$ 、 $\varepsilon_{end}$ 、 $\varepsilon_{decay}$ は定数で、それぞれ
$\varepsilon_{start} = 0.9 \\ \varepsilon_{end} = 0.05 \\ \varepsilon_{decay} = 200$
という値が使用されている。

グラフにすると、

のようになり、 $\varepsilon_{start}$ から徐々に小さくなり、 $\varepsilon_{end}$ で一定になる。
$\varepsilon_{decay}$ は、小さくする速度を制御している。

リバーシでは、ステップ数をエピソード数に置き換えて、 $\varepsilon_{start}$ と $\varepsilon_{end}$ は、同じ値を使用し、 $\varepsilon_{decay}$ は2000とした。

学習結果

教師ありのQ学習では、1万ステップ学習してもランダムよりも強くならなかった。
そのため、最低でも1万ステップ以上は学習する必要があると思われる。
そこで、一旦1万ステップ(16万エピソード)の学習を試すことにした。

損失

損失のグラフは以下のようになった。

はじめ順調に下がった後、上昇してまた下がっている。
まったく学習できていないわけでもなさそうである。

強さ

ランダムと1000局対局して強さを測定した。
597勝368敗35分という結果になった。
信頼区間95%の勝率は、64.9～58.8%で、ランダムより有意に強くなっている。

学習時間

16万エピソードの学習にはGeForce 2080Tiを使用して、約14時間かかった。

まとめ

リバーシで、DQNを用いて強化学習することで、ランダムより強くできることが確認できた。

リバーシは、ルールがシンプルで60手で必ず勝負がつくので強化学習の勉強題材としては良いのではないかと思う。
将棋ではDQNがまった学習できなかったので、とりあえずランダムより強くなるという結果がでて良かった。

シングルスレッドでシングルゲームを繰り返しているので、ゲームを並列実行することで学習時間は短くできるはずである。
他のアルゴリズムを試す前に、並列実行を実装したい。

その後、DDQNなど他のアルゴリズムも試したい。
あと、GUIソフトと連携させて人間とも対局できるように、プロトコルも実装するつもりである。

ソース

実装したDQNのソースは、こちら。
creversi_gym/dqn.py at master · TadaoYamaoka/creversi_gym · GitHub

2019-12-07

MuZeroの論文を読むその５（AlphaZeroとの比較）

MuZero

付録A AlphaZeroとの比較

MuZeroは、AlphaGo Zero *1やAlphaZero*2よりも一般的な設定向けに設計されている。

AlphaZeroのプランニング

AlphaGo ZeroとAlphaZeroでは、プランニングプロセスは2つの別個のコンポーネントを使用する。
シミュレーターは、ゲームのルールを実装する。これは、探索木を走査しながらゲームの状態を更新するために使用される。
また、ニューラルネットワークは、シミュレータによって生成された局面の対応する方策と価値を合わせて予測する（図1 Aを参照）。

f:id:TadaoYamaoka:20191121214604p:plain

AlphaZeroとの比較の詳細

具体的には、AlphaGo ZeroおよびAlphaZeroは、（1）探索木の状態遷移、（2）探索木の各ノードで利用可能な行動、（3）探索木内のエピソード終了の3つの場所でゲームのルールの知識を使用する。
MuZeroでは、これらのすべてが、ニューラルネットワークによって学習された単一の暗黙的なモデルの使用に置き換えられた（図1 Bを参照）。

1) 状態遷移
- AlphaZeroは、真のダイナミクスプロセスの完璧なシミュレータにアクセスできた。
- 対照的に、MuZeroは探索内で学習したダイナミクスモデルを採用している。
- このモデルでは、木内の各ノードは対応する隠れ状態で表される。
- 隠れ状態 $s_{k-1}$ とアクション $a_k$ をモデルに提供することにより、探索アルゴリズムは新しいノード $s_{k} = g(s_{k-1}, a_k)$ に遷移できる。

2) 利用可能な行動
- AlphaZeroは、シミュレーターから取得した一連の合法な行動を使用して、探索木のあらゆる場所でネットワークによって生成された事前分布をマスクした。
- MuZeroは、環境のクエリが可能な探索木のルートでのみ合法な行動をマスクしますが、探索木内ではマスキングを実行しない。
- これは、ネットワークが訓練された軌跡で決して発生しない行動を予測しないことを急速に学習するために可能である。

3) 終端ノード
- AlphaZeroは、終端の状態を表すノードで探索を停止し、ネットワークによって生成された価値の代わりに、シミュレータによって提供された終端の価値を使用した。
- MuZeroは終端ノードに特別な処理を行わず、ネットワークによって予測された価値を常に使用する。
- 木内で、探索は終端ノードを通過できる。この場合、ネットワークは常に同じ価値を予測することが期待される。
- これは、訓練中に終端状態を吸収状態として扱うことで実現されます。

AlphaZeroより一般的な設定

さらに、MuZeroは一般的な強化学習設定（任意の大きさの割引された中間報酬を持つシングルエージェントドメイン）で動作するように設計されている。
対照的に、AlphaGo ZeroとAlphaZeroは、±1の割引なしの終端報酬で2プレイヤーゲームで動作するように設計されている。

感想

AlphaZeroではMCTSのシミュレーションでは探索中の局面で着手を合法手でマスキングするためにゲームのルールを使用していましたが、MuZeroではマスキングを行わないことが述べられています。
ニューラルネットワークを訓練することで、常に合法手が出力されることを期待しています。

また、AlphaZeroでは探索中にゲームの終了をチェックして、ゲームの結果を価値としてバックアップを行っていましたが、MuZeroでは終了のチェックは行わず常にネットワークが予測する価値を使用しています。
この仕組みだと探索中にゲームの終了を認識できないので、終端状態を通過して探索を続けてしまう問題があります。
対策として、訓練中に終了状態からは同じ終了状態に遷移するように訓練されています。マルコフ連鎖の用語で吸収状態(absorbing states)というようです。

将棋では、詰みの状態はいくら駒損しても詰めばよいため序盤中盤の局面とは性質が違うため、ゲームルールを使用した探索の支援なしにニューラルネットワークのみで学習するのは難しそうですが、MuZeroで学習できているのはすごいことのように思います。

MuZeroの一般性については、AlphaZeroは中間報酬のない2人ボードゲームに特化していましたが、中間報酬と割引ありシングルエージェントに適用できると述べられています。
それによって、AtariにもAlphaZeroライクな探索が導入可能になっています。

(続く)

*1:Mastering the game of Go without human knowledge | Nature

*2:A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play | DeepMind

2019-12-05

リバーシ(オセロ)で深層強化学習その２（教師ありQ学習）

リバーシ強化学習

前回、オセロの棋譜の終端の報酬を使用して(TD(1))、教師ありで学習することでランダムより強くなることを確認した。

今回は、教師ありでQ学習を試す。

Q学習

Q学習の学習則は以下の式で表される。
$\displaystyle \delta=Q(s, a)-\left(r+\gamma \max _{a} Q\left(s^{\prime}, a\right)\right)$

$r$ は、遷移に対応する即時報酬で、リバーシ(オセロ)の場合、終端以外では0になる。
$\max _{a} Q\left(s^{\prime}, a\right)$ は、1ステップ先の局面での行動価値が最大となる手の行動価値である。

よって、学習の開始時は、ほとんどの局面で、ランダムで初期化されたニューラルネットワークの出力のうち、偶然最大になった値を教師として学習することになる。
学習が進むにつれ、徐々に終端の報酬が序盤の局面にも伝播していく。

棋譜の偏り

前回使用した棋譜を調べたところ、引き分けのゲームが8割以上含まれていた。
GGSの棋譜だけの傾向かもしれないが、オセロは引き分けが多いゲームのようだ。
そのまま使用すると終端の報酬の多くが0になってしまい学習が進まないことが予想される。
そこで、引き分けのゲームが1割以下になるように間引いて使用することにした。

ミニマックス対応

1ステップ後の行動価値は、相手局面になるため、 $Q\left(s^{\prime}, a\right)$ は、ニューラルネットワークの出力の符号を反転する必要がある。

パス対応

前回の終端の報酬を使った学習では、パスした局面は除外して学習を行った。
そのため、ニューラルネットワークの出力でもパスは考慮していなかった。

Q学習の場合、1ステップ後がパスとなる局面を考慮する必要があるため、ニューラルネットワークの出力にパスを加えた。
そのため、出力層は1×1の畳み込みから、全結合層に変更した。

学習結果

1万ステップ学習した結果は以下の通り。
f:id:TadaoYamaoka:20191205220744p:plain
前回に比べて損失の値の桁が一つ小さい。

強さの測定

ランダムとの対局した結果は、453勝500敗47分となった。
1万ステップではほとんど学習できていない。

終端の報酬で学習した場合との比較

同じネットワーク構成と教師局面で、終端の報酬で学習した場合は、同じ1万ステップで675勝281敗44分となった。
明らかに、Q学習の方が学習速度が遅い。

10万ステップ学習した結果

ステップ数を増やせば学習できるか確認するため、10万ステップ学習した。
f:id:TadaoYamaoka:20191205221328p:plain
前回は途中で横ばいになったが、Q学習の場合横ばいにならずに学習が進んでいる。

ランダムとの対局結果は、757勝214敗29分となった。
終端の報酬で10万ステップ学習した場合は、639勝330敗31分となった。
学習が進むと、Q学習の方が逆転して強くなっている。

まとめ

DQNのネットワークをQ学習でも学習できることが確認できた。
また、学習の初期は終端の報酬を使用した方が学習が早く進み、学習が進むと、終端の報酬よりQ学習の方がパフォーマンスが良くなることがわかった。

次は、強化学習でDQNを学習させてみたい。

学習に使用したソースはこちら。
creversi_gym/train_from_training_data.py at master · TadaoYamaoka/creversi_gym · GitHub
creversiもちょくちょく改良しています。