TadaoYamaokaの開発日記

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

WindowsでPyTorchをC++(Visual C++)で動かす【更新】

以前にWindowsでLibTorchをC++から使う方法について記事を書いたが、内容が古くなったので書き直す。

基本的な手順は以前と同じだが、リリースビルドとデバッグビルドの使い分けができるようになっている。

最新のLibTorch 1.3は、Release用のバイナリと、Debug用のバイナリが別々に配布されている。
以前は、Release用のバイナリのみだったため、Debugビルドで動かすことができなかった。

LibTorchのインストール

https://pytorch.orgのQUICK START LOCALLYから、Stable/Windows/LibTorch/C++/10.1(CUDAのバージョンが10.1の場合)を選んでlibtorch-win-shared-with-deps-1.3.1.zipをダウンロードする。
適当な場所に解凍する。
以下、C:\に解凍したとして説明する(zipのルートフォルダがlibtorchなので、C:\libtorchが作成される)。

デバッグ用モジュール

デバッグビルドを行う場合は、「Download here (Debug version):」のリンクからlibtorch-win-shared-with-deps-debug-1.3.1.zipをダウンロードする。

リリース用モジュールとは別の場所に展開する。
以下、C:\libtorch\debugに、zipのlibtorch配下のフォルダを展開したとして説明する。

cmakeインストール

cmakeをVisual Studioのインストール時のオプションでインストールする。

最も単純なサンプルをビルドして実行

Installing C++ Distributions of PyTorch — PyTorch master documentation
の説明の通り、適当な場所に

  • CMakeLists.txt
  • example-app.cpp

を作成して、上記のページの内容の通り内容を記述する。

ビルド

スタートメニューから「x64 Native Tools Command Prompt for VS 2019」※を起動する。
Visual Studio 2019の場合。Visual Studio 2017でも可。
サンプルコードを配置したディレクトリに移動して、以下のコマンドを実行する。

mkdir build
cd build
cmake -DCMAKE_PREFIX_PATH=C:\libtorch ..

buildディレクトリに「example-app.sln」が作成されるので、Visual Studioで開いて、スタートアッププロジェクトを「example-app」に設定し、ソリューションの構成を「Release」に設定しビルドする。

ビルド成功し実行すれば、以下のように表示される。

 0.3171  0.7950  0.6067
 0.1094  0.7421  0.8496
[ Variable[CPUType]{2,3} ]

なお、ソリューションの構成を「Release」以外でビルドした場合、

エラー	LNK1104	ファイル 'torch-NOTFOUND.obj' を開くことができません。

というエラーが出力される。対処方法は後述する。

コマンドラインからビルドする場合

コマンドラインからビルドする場合、以下のコマンドでビルドする。

cmake --build . --config Release

デバッグビルド

上記の方法では、Debugでビルドすることができないため、自作のC++のプログラムをデバッグする際に困る。
cmakeのオプションを

cmake -DCMAKE_PREFIX_PATH=C:\libtorch\debug ..

として、別のプロジェクトを作成することで、Debugでビルドできるようになる。

しかし、Release用とプロジェクトが分かれてしまうので、不便である。
そこで、cmakeで生成された「example-app.vcxproj」を直接編集する。

<ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">

から、対応する閉じタグの

</ItemDefinitionGroup>

までの間の、「C:\libtorch」を「C:\libtorch\debug」に置換する。

また、「torch-NOTFOUND」を「C:\libtorch\debug\lib\torch.lib」に置換する。

これで、Debug構成でもビルドできるようになる。

なお、CMakeLists.txtを編集して、cmakeを再構成した場合は、上書きされてしまうので注意が必要である。

その他のソリューション構成の場合

cmakeが生成するVisual Studioのプロジェクトには、「Release」と「Debug」以外に、「MinSizeRel」と「RelWithDebInfo」が含まれる。
これらの構成でビルドしたい場合は、上記と同様のビルドエラーが発生するため、対応するItemDefinitionGroupタグ内の「torch-NOTFOUND」を「C:\libtorch\lib\torch.lib」に置換すると良い。

デバッグビルドでのCUDAが使用できない問題

現在のバージョンでは、デバッグビルドでのCUDAが使用でいないという問題が発生している。
LibTorch crashes in debug mode: DispatchStub: missing CUDA kernel · Issue #22681 · pytorch/pytorch · GitHub

バグフィックスが行われているようなので、次のバージョンで修正されると思われる。

MuZeroの論文を読む その8(ネットワーク)

付録E ネットワーク入力

表現関数

ボードゲーム
  • 囲碁、チェス、将棋の表現関数への入力として使用されるボード状態の履歴は、AlphaZeroと同様に表される。
  • 囲碁および将棋では、AlphaZeroのように最後の8つのボード状態をエンコードする。
  • チェスでは、引き分けの正確な予測を可能にするために、過去100のボード状態に履歴を増やした。
Atrari
  • Atariの場合、表現関数の入力には、解像度96x96の最後の32個のRGBフレームと、それらの各フレームにつながった最後の32個の行動が含まれる。
  • ボードゲームとは異なり、Atariの行動は必ずしも観測に目に見える影響を与えないため、行動の履歴をエンコードする。
  • RGBフレームは、色ごとに1つの面としてエンコードされ、それぞれ赤、緑、青の範囲[0,1]に再スケーリングされる。
  • RGB入力のその他の正規化、ホワイトニング、またはその他の前処理は行わない。
  • 行動履歴は、𝑎 / 18にスケーリングされた単純なバイアス面としてエンコードされる(Atariには合計18アクションがある)。

ダイナミクス関数

  • ダイナミクス関数への入力は、表現関数またはダイナミクス関数の以前の適用によって生成された隠れ状態であり、遷移の行動の表現と連結される。
  • 行動は、隠れ状態と同じ解像度の面で空間的にエンコードされる。
  • Atariでは、この解像度は6x6である(ネットワークアーキテクチャの節のダウンサンプリングの説明を参照)。
  • ボードゲームでは、これはボードサイズと同じである(囲碁では19x19、チェスでは8x8、将棋では9x9)。
囲碁の行動のエンコード
  • 囲碁では、通常の行動(盤上に石を打つ)は、すべて0の面としてエンコードされ、1つの1が着手された石の位置にある。
  • パスは、すべて0の面としてエンコードされる。
チェスの行動のエンコード
  • チェスでは、行動をエンコードするために8つの面が使用される。
  • 最初のワンホットプレーンは、駒の移動元の位置をエンコードする。
  • 次の2つの面は、駒が移動された位置をエンコードする:ボード上にある場合、ターゲット位置をエンコードするワンホットプレーン、およびターゲットが(ボード上で)有効かどうかを示す2番目のバイナリプレーン。
  • これは、簡単にするために方策の行動空間がすべての有効な行動(すべてが合法ではない)のスーパーセットを列挙するために必要である。 また、方策予測とダイナミクス関数入力をエンコードするために同じ行動空間を使用する。
  • 残りの5つのバイナリプレーンは、プロモーションのタイプ(クイーン、ナイト、ビショップ、ルーク、なし)を示すために使用される。
将棋の行動のエンコード
  • 将棋のエンコードも同様で、合計11面である。
  • 最初の8つの面を使用して、駒の移動元を示しす。盤の位置(最初のワンホットプレーン)または7種類の持ち駒(残りの7つのバイナリプレーン)のいずれかである。
  • 次の2つの面は、チェスのようにターゲットをエンコードするために使用される。
  • 残りのバイナリプレーンは、移動が成りであったかどうかを示す。
Atariの行動のエンコード
  • Atariでは、行動は面に適切に割り当てられたワンホットベクトルとしてエンコードされる。

付録F ネットワークアーキテクチャ

予測関数
  • 予測関数\mathbf{p}^k, v^k = f_\theta(s^k)は、AlphaZeroと同じアーキテクチャを使用する。
    • 1つまたは2つの畳み込み層で、解像度を維持しながら面の数を減らし、出力のサイズの全結合層が続く。
Atariでの価値と報酬の予測
  • Atariでの価値と報酬の予測では、すべての実験において\epsilon = 0.001の可逆変換h(x) = sign(x)(\sqrt{|x| + 1} - 1 + \epsilon x)を使用してターゲットをスケーリングする。
  • 次に、同等のカテゴリ表現を取得するために、スカラー報酬および価値ターゲットに変換\phiを適用する。
  • サイズ601の個別サポート(関数の台)セットを使用し、-300〜300の整数ごとに1つのサポートを使用する。
  • この変換では、各スカラーは2つの隣接するサポートの線形結合として表されるため、元の値はx = x_{low} * p_{low} + x_{high} * p_{high}によって復元できる。
  • 例として、3.7のターゲットは、3のサポートでは0.3の重み、4のサポートでは0.7の重みとして表される。
  • ネットワークの価値と報酬の出力も、サイズ601のsoftmax出力を使用してモデル化される。
  • 推論中、実際の価値と報酬は、それぞれのsoftmax分布の下で最初に期待値を計算し、その後スケーリング変換を逆変換することによって取得される。
  • 価値と報酬のスケーリングと変換はネットワーク側で透過的に行われ、アルゴリズムの残りの部分には見えない。
表現関数とダイナミクス関数
Atariの観測
  • 観測の空間分解能が大きいAtariの場合、表現関数は、空間分解能を下げるためにストライド2の畳み込みのシーケンスから始める。
  • 具体的には、解像度96x96および128の面(それぞれ3つのカラーチャネルの32の履歴フレーム、面にブロードキャストされる対応する32の行動と連結)の入力観測から始めて、次のようにダウンサンプリングする。
    • ストライド2および128の出力面で1回の畳み込み、出力解像度48x48
    • 128面の2つの残差ブロック
    • ストライド2および256の出力面を使用した1つの畳み込み、出力解像度24x24
    • 256面の3つの残差ブロック
    • ストライド2、出力解像度12x12の平均プーリング
    • 256面の3つの残差ブロック
    • ストライド2、出力解像度6x6での平均プーリング
  • ダイナミクス関数(常に6x6のダウンサンプリング解像度で動作する)の場合、行動は最初に画像としてエンコードされ、次に平面次元に従って前のステップの隠れ状態を使ってスタックされる。
感想

AlphaZeroでは、8つの履歴局面を入力としていましたが、囲碁、将棋はAlphaZeroと同じで、チェスでは履歴局面の数が100に増やされています。
理由としては、引き分けを正確に予測するためと説明されています。

AlphaZeroでは、チェス、将棋では、繰り返し数が入力特徴量にありましたが、MuZeroではシミュレーション中の局面は、埋め込み表現に変換されるため正確に繰り返しを判断することができません。
そのため、必要な処置だったと推測できます。
将棋でも千日手があるので、履歴が8つでは足りないように思いますが、チェスの方がより引き分けにする戦略を多用するゲームのようなのでチェスだけ増やしたのではないかと思います。


チェス、将棋の移動先のエンコードで、移動元と移動先の組み合わせが合法かどうかを示すフラグが表現されています。
あまり詳細に書かれていないので推測ですが、MuZeroでは合法手の判断を行わないため、方策はすべての組み合わせを列挙するため、学習時に合法手を覚えさせるために必要だったと思われます。


ネットワーク構成は、ボードゲームではAlphaZeroと同じアーキテクチャとなっています。
Atariでは、ゲームによって価値と報酬の分布が異なるため、スケーリングしてカテゴリ化を行っています。
変換の説明にsupportという用語がでてきて、何かと思いましたが、数学の用語で日本語では「関数の台」というようです。
値をスカラではなくカテゴリ化してsoftmaxで出力するようにしています。
予測を容易にするために、値の解像度を落とすような操作をしていると理解できます。


次回は、訓練についてです。
(続く)

リバーシ(オセロ)で深層強化学習 その6(Dueling Network)

前回リバーシでDDQNを試したが、今回は同じくDQNの発展形であるDueling Networkを試す。

Dueling Network

[1511.06581] Dueling Network Architectures for Deep Reinforcement Learning

DQNでは行動価値を行動価値関数Qで推定するが、Dueling Networkでは、行動価値関数Qを状態価値関数Vとアドバンテージ関数Aに分解する。
DQNの以前の研究で、状態価値関数とアドバンテージ関数の2つに分解することで、Q学習とよりも速く収束することが示されている。

アドバンテージ関数は、以下の式で定義される。
\displaystyle
A^{\pi}(s,a) = Q^{\pi}(s,a) - V^{\pi}(s)
行動価値関数Qから状態価値関数Vを減算することで、各行動aの重要度の相対的な尺度を取得している。

この定義を使用すると、DDQNのターゲット
\displaystyle
y_i^{DDQN} =  r + \gamma Q(s',argmax_{a'} Q(s',a';\theta_i)   ;\theta^{-})
の行動価値関数Qを、2つのモジュールに分解できる。
\displaystyle
Q(s,a;\theta,\alpha,\beta) =  {V}(s;\theta,\beta) + {A}(s,a;\theta,\alpha)


ここで、VとAへの分解は、一意には定まらないことに注意する必要がある。
例えば、Vに定数を足して、Aからその値を引いてもQの値は同じになるということが起きる。
この性質のため、この式を直接使用するとパフォーマンスの低下を招く。


対処として、選択した行動で、Aが0になるように、次のように式を変形する。
\displaystyle
Q(s,a;\theta,\alpha,\beta) =  {V}(s;\theta,\beta)~+
\left({A}(s,a;\theta,\alpha) - \max_{a' \in |\mathcal{A}|}  {A}(s, a' ;\theta,\alpha) \right)


論文では、最大値の代わりに、平均を使用することで、学習の安定性を向上できると述べられている。
\displaystyle
Q(s,a;\theta,\alpha,\beta) =  {V}(s;\theta,\beta)~+
\left({A}(s,a;\theta,\alpha) - \frac{1}{|\mathcal{A}|} \sum_{a'} {A}(s, a' ;\theta,\alpha) \right)

実装方法

Dueling Networkは、DQNのネットワークの出力を、一旦VとAに分けた後、上記式の結果を出力することで実現する。
ネットワークの変更のみで実装でき、DQNの学習部分はそのまま適用できる。

論文では、学習部分はDDQNを使用しているので、DDQNを使用する。

実装

前回までのDQNのネットワークを以下のように変更した。
fcl2を、fcl2_advとfcl2_vに分けている。
forwardの最後で、fcl2_advとfcl2_vから出力のQを計算している。

class DQN(nn.Module):

    def __init__(self):
        super(DQN, self).__init__()
        self.conv1 = nn.Conv2d(2, k, kernel_size=3, padding=1)
        self.bn1 = nn.BatchNorm2d(k)
        # 省略
        self.conv10 = nn.Conv2d(k, k, kernel_size=3, padding=1)
        self.bn10 = nn.BatchNorm2d(k)
        self.fcl1 = nn.Linear(k * 64, fcl_units)
        self.fcl2_adv = nn.Linear(fcl_units, 65)
        self.fcl2_v = nn.Linear(fcl_units, 1)

    def forward(self, x):
        x = F.relu(self.bn1(self.conv1(x)))
        # 省略
        x = F.relu(self.bn10(self.conv10(x)))
        x = F.relu(self.fcl1(x.view(-1, k * 64)))

        adv = self.fcl2_adv(x)
        val = self.fcl2_v(x).expand(-1, 65)

        out = val + adv - adv.mean(1, keepdim=True).expand(-1, 65)

        return out.tanh()

実行結果

1万イテレーション学習した結果は以下のようになった。

損失

f:id:TadaoYamaoka:20191218225242p:plain
2000イテレーションまでは安定していないが、それ以降は、DQNやDDQNよりも安定して損失が低下している。

強さ

ランダムと1000局対局した結果は以下の通り。

結果 勝率 信頼区間95%
DQN 833勝152敗15分 84.57% 86.7~82.2%
DDQN 847勝131敗22分 86.61% 88.6~84.3%
Dueling 935勝58敗7分 94.16% 95.5~92.5%

DQNとDuelingの勝率に有意差があるか検定するための統計量zは、-6.92となった。
z<−1.96であるため、DQNとDuelingの勝率は等しいという帰無仮説は棄却され、Duelingの方が有意に強いと言える。


DQNと直接対局した結果は、

先手 後手 結果 勝率(信頼区間95%)
Dueling DQN 498勝462敗40分 55.0~48.7%
DQN Dueling 412勝562敗26分 45.42~39.20%
計(DDQN-DQN) 1060勝874敗66 57.0~52.6%

直接対局でも、有意に強くなっている。

まとめ

Dueling Networkでリバーシの学習を行った。
DQNと比較して、同じイテレーション数で有意に強くなることが確認できた。
Dueling Networkは、リバーシに有効な手法と言えそうだ。

論文では、Prioritized Replayと組み合わせることでさらに効果があると述べられているので、次は、Prioritized Replayを試してみたい。

(続く)

2つのプログラムの勝率に違いがあるか検定する

昨日書いた記事で、DQNとDDQNのランダムに対する勝率の違いについて、統計的に違いがあると言えるのか検証してみた。

昨日の結果
結果 勝率
DQN 833勝152敗15分 84.57%
DDQN 847勝131敗22分 86.61%

※勝率は引き分けを無効として計算した。

仮説検定

以下のように帰無仮説と対立仮説を設定する。

帰無仮説 DQNとDDQNの勝率は等しい
対立仮説 DDQNの方が勝率が高い

統計量

2つの母比率の差を検定する際には、下記の統計量zを使用する。
この統計量は、標準正規分布N(0, 1)に従う。
\displaystyle
z=\frac{\widehat{p}_{1}-\widehat{p}_{2}}{\sqrt{\widehat{p}(1-\widehat{p})\left(\frac{1}{n_{1}}+\frac{1}{n_{2}}\right)}}

勝敗の結果を当てはめると、
\displaystyle
\widehat{p}_{1} = 0.8457 \\
\widehat{p}_{2} = 0.8661 \\
\widehat{p} = (833+847)/(1000-15+1000-22) = 0.8558 \\
n_1 = 985 \\
n_2 = 978
なので、統計量zは、
\displaystyle
z = -1.2845
となる。

棄却ルール

DDQNの方が勝率が高いことを示したいので、片側検定を用いる。
有意水準は、5%の半分=2.5%とする。

下側の棄却域は、Pythonを使って計算すると、

from scipy.stats import norm
norm.ppf(0.025)
Out: -1.9599639845400545

と算出できる。

z > -1.96であるため、zは、棄却域に入っていない。

結論

帰無仮説は、棄却できない。
よって、前回のランダムとの対局結果からは、DDQNは、DQNよりも勝率が高いとは言えない。

リバーシ(オセロ)で深層強化学習 その5(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を試します。
(続く)

MuZeroの論文を読む その7(ハイパーパラメータ、データ生成)

付録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のゲームに対応するために探索的な行動がある程度必要だったのではないかと思います。

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

MuZeroの論文を読む その6(探索)

付録B 探索

  • 探索木のすべてのノードは、内部状態𝑠に関連付けられている。
  • 𝑠からの各行動𝑎には、一連の統計\{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の疑似コードにあった式と同じです。

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