2020-05-31

dlshogiの学習則

dlshogi

dlshogiを改造して遊びたい方のために、dlshogiの学習則についてちゃんと書いてなかったので書いておく。

主に、学習部のソースtrain_rl_policy_with_value_using_hcpe_bootstrap.pyの解説になっている。

AlphaZeroの学習則

AlphaZeroの学習則は、
$\displaystyle l(\theta)=(z-v)^2 - \boldsymbol{\pi}^T \log \boldsymbol{p} + c \|\theta\|^2$
となっている。
dlshogiではこれとは異なる学習則を使用している。

ルートノードの分布の使用有無

まず、AlphaZeroでは、MCTSのシミュレーション結果のルートの子ノードの訪問回数の分布（上式の $\boldsymbol{\pi}$ ）を使用しているが、dlshogiでは分布ではなく指し手を使用している。
これは、学習に分布を使用すると学習データのサイズが大幅に増えてしまうので、データサイズを抑えたいという理由による。

Actor-Critic

dlshogiでは、方策をActor-Criticで学習している。

一般的な方策勾配法では、目的関数の勾配に報酬zを使用する。
$\displaystyle \nabla_\theta J(\theta) = \mathbb{E}[\nabla_\theta \log \pi_\theta(a|s)z_t^m]$
Actor-Criticでは、分散を低下させる（過剰適合を避ける）ために、ベースラインとして価値関数の値を報酬zから引く。
$\displaystyle \nabla_\theta J(\theta) = \mathbb{E}[\nabla_\theta \log \pi_\theta(a|s)(z_t^m - V^\pi(s))]$
ベースラインを追加しても、 $\nabla_\theta J(\theta)$ の期待値自体は変わらないが、推定分散を小さくする効果がある。
$z_t^m - V^\pi(s)$ の項はアドバンテージと呼ばれる。

なお、期待値が変わらないというのは、期待値を行動aの積分で表すと、以下の式展開で確かめられる。
$\displaystyle \int \nabla_\theta \log \pi(a) \pi(a) da = \int \nabla_\theta \pi(a) da = \nabla_\theta \int \pi(a) da = 0$
式展開では微分の連鎖則を利用している。
$\displaystyle \begin{eqnarray} \frac{\partial}{\partial x} \log f(x) &=& \frac{\partial \log f(x)}{\partial f(x)} \frac{\partial f(x)}{\partial x} \\ &=& \frac{1}{f(x)} \frac{\partial f(x)}{\partial x} \end{eqnarray}$

dlshogiでは、この式をそのまま適用してもうまく学習ができなかった。
そこで、ベースラインにさらに0.5を加えている。
$\displaystyle \nabla_\theta J(\theta) = \mathbb{E}[\nabla_\theta \log \pi_\theta(a|s)(z_t^m - V^\pi(s) + 0.5)]$
この意味は、負けた対局でも探索した指し手はある程度信用できるので、半分は信用してあげようという気持ちである。
特に理論的な背景があるわけではない。

参考までに、OpenAIのbaselinesのPPOの実装では、アドバンテージの正規化を行っている。
$\displaystyle \mathcal{A}_{normalized} = \frac{\mathcal{A} - \bar{\mathcal{A}}}{\sigma(\mathcal{A}) + \epsilon}$
なぜ、正規化が必要かについて不思議だったので、ネットで検索したらいくつかの議論が見つかった。

引用されていた資料（4.1.2 Advantage Normalization）によると、推定量の分散を小さくすることにより、通常、経験的パフォーマンスを向上させることが知られているトリックだそうだ。
dlshogiの学習でも効果があるかもしれない。

エントロピー 正則化

dlshogiの方策は指し手を学習しているため、方策が決定論的に偏りやすい。
そのため、A3Cでも行われているエントロピー正則化を行っている。

方策 $p$ のエントロピーは以下の式で与えられる。
$\displaystyle H(p) = -\sum_j p_j \log p_j$

エントロピーは、方策の分布が均一の場合に最大になり、どれか一つの行動の確率が1（決定論的）になったときに最小となる。
$-\beta H(p)$ を正則化項として損失に加えることで、決定論的になる方向にペナルティが加えられる。

価値関数の学習

AlphaZeroでは、価値の損失には平均二乗誤差(MSE)を使用している。
dlshogiでは、方策の損失が交差エントロピーなので、価値の損失もエントロピーの方が自然と考えて、シグモイド交差エントロピーを使用している。
価値関数の出力の範囲は、勝率を表す $[0,1]$ となっている（AlphaZeroでは、勝ちを1、負けを-1として、出力範囲は $[-1,1]$ となっている）。

価値の学習のブートストラップ

強化学習では、報酬そのものを学習する代わりに、Nステップ後の推定収益を学習することで、学習を加速するということが行われる。
この手法は、ブートストラップと呼ばれる。
なお、ブートストラップとは、OSのブートとかでも使われている語であるが、語源は靴のかかとについているタグのことだそうだ。タグをつまむと靴が履きやすくなることのアナロジーである。

コンピュータ将棋では、elmoが報酬のシグモイド交差エントロピーと、深さNの評価関数の出力とルートの評価関数の2つの確率変数の交差エントロピーの加重平均を損失にするという手法を導入して成功している。

dlshogiもこれに倣い、MCTSシミュレーションを行った結果のルートノードの指し手のQ値と、ルートノードの状態価値の2つの確率変数の交差エントロピーを価値の損失に加え、報酬の損失と按分している。
$\displaystyle l_{value}(\theta)= (1 - \lambda) H(v, z) + \lambda H(v, q)$

正則化

AlphaZeroでは、損失にL2正則化項 $c \|\theta\|^2$ を加えている。
dlshogiも同様にL2正則化を行っている（実装上はPyTorchのWeightDecayを使っている）。

SWA

SWA(Stochastic Weight Averaging)は、一定間隔での重みを平均化することで、ニューラルネットワークのテスト精度を改善するテクニックである。
一般的なアンサンブルの手法では予測の結果を平均化するが、SWAでは重みを平均化することで実現する。
Leela Chess ZeroでもSWAを導入している。
dlshogiでも効果があったため導入した。

学習則まとめ

以上の学習則を式で表すと以下のようになる。

$\displaystyle l(\theta)=- \boldsymbol{\pi}^T \log \boldsymbol{p} (z - v + 0.5) - \beta H(p) + (1 - \lambda) H(v, z) + \lambda H(v, q) + c \|\theta\|^2$

$\boldsymbol{\pi}$ は指し手のone-hotベクトルを表す。

2020-05-27

Agent57: Outperforming the Atari Human Benchmarkを読むその１５

Agent57

付録H. 実験結果

H.1. Atari 10：アブレーションのスコア表

f:id:TadaoYamaoka:20200527091029p:plain

H.2. Backpropウィンドウの長さの比較

図12. 難易度の高い10ゲームのセットでの、Backpropウィンドウの長さが短い場合と長い場合のパフォーマンスの比較

f:id:TadaoYamaoka:20200527091407p:plain

H.3. アイデンティティとh変換の組み合わせの比較

図13. 挑戦的な10ゲームのセットでのアイデンティティとh変換ミックスのパフォーマンス比較

f:id:TadaoYamaoka:20200527092158p:plain

図H.3に示すように、アイデンティティまたはh変換ミックスを選択しても、パフォーマンスの点で違いはないようである。
唯一重要なことは、外発的と内発的の組み合わせが線形かどうかに関係なく発生することである。
さらに、βの極値（ $\beta = 0$ , $\beta>>1$ ）の場合、量 $Q^e_k(x, a) + \beta Q^i_k(x, a)$ と $h^{-1}(Q^e_k(x, a)) + \beta h^{-1}(Q^i_k(x, a))$ は同じ $argmax_{a\in\mathcal{A}}$ になることに注意してほしい。これは、 $h^{-1}$ が厳密に増加しているためである。
したがって、これは、βの極値で、変換と通常の値の反復スキームが同じ方策に向かって収束することを意味する。
βの値の間では、これは当てはまらない。
しかし、変換演算子とアイデンティティミックスが使用される場合、価値反復スキームは、内発的報酬と外発的報酬 $r^i, r^e$ の非線形の組み合わせに関してそれぞれ最適な状態行動価値関数を近似すると推測できる。

H.4. Atari 57のスコア表

f:id:TadaoYamaoka:20200527093243p:plain
f:id:TadaoYamaoka:20200527093309p:plain

H.5. Atari 57の学習曲線

図14. Atari57でのAgent57の学習曲線

f:id:TadaoYamaoka:20200527093359p:plain

H.6. ビデオ

https://sites.google.com/corp/view/agent57にいくつかの動画を掲載している。
以下を示している。
- 57のすべてのゲームでのAgent57：Agent57が人間のベースラインを超えるAtari 57スイープの各ゲームのサンプルビデオを提供する。
- 状態行動価値関数のパラメーター化：価値関数のパラメーター化の重要性を示すために、アイスホッケーとサラウンドの2つのゲームのビデオを示す。 NGUとAgent57の両方の活用的および探索的方策のビデオを示す。アイスホッケーでは、探索的および活用的な方策は非常に異なるスコアを達成している。具体的には、探索的な方策はゴールを目指すのではなく、新しい構成を探索しながらコートの周りを移動することを好む。一方、単一のアーキテクチャのNGUは両方の方策を同時に学習することはできないが、Agent57は非常に多様なパフォーマンスを示す。サラウンドの場合NGUはまたしても学ぶことができない。探索的方策は、観察の多様性を新たに増大させるために、新たに開始するためにポイントを失うことを選択したと推測する。 Agent57はこの問題を克服でき、活用的方策と探索的方策の両方で、人間のベースラインを超えるスコアを取得できる。
- 適応的割引率：ゲームJames BondのR2D2（bandit）とR2D2（retrace）のビデオ例を示す。 R2D2（retrace）は、30,000ポイント程度の最終スコアでゲームをクリアすることを学ぶ。対照的に、R2D2（bandit）は、ゲームの終了を遅らせて、スコアが約140,000ポイントで、大幅に多くの報酬を集めることを学ぶ。これを実現するために、メタコントローラーの適応メカニズムは、非常に高い割引率を持つ方策を選択する。
- Backprop Through Timeのウィンドウサイズ：SolarisのゲームでのNGUおよびAgent57のエピソードの例を示すビデオを提供する。ハイスコアを達成するために、エージェントはグリッド画面内を移動して敵を探すことを学ぶ必要がある。エージェントはグリッド画面で実行されたアクションを後で多くのタイムステップで達成された報酬にバインドする必要があるため、これは長期的なクレジット割り当ての問題である。

2020-05-26

ONNX Runtimeを使ってみる

dlshogiはCUDAに対応したNvidiaのGPUが必須になっているが、AMDのGPUやCPUのみでも動かせるようにしたいと思っている。

Microsoftがオープンソースで公開しているONNX Runtimeを使うと、様々なデバイスでONNXモデルの推論を行うことができる。
TensorRT対応で、ONNXのモデルを読み込めるようになったので、ONNX Runtimeに対応すれば同じモデルを使いまわせる。

ONNX Runtimeは、PythonやC#など複数の言語のインターフェースが提供されている。
dlshogiに組み込むにはC++のインターフェースが必要だが、C++も提供されている。

推論に使うデバイスは、CPUやCUDA、TensorRT、DirectX、MKL-DNNなど複数のデバイスを切り替えられるようになっている。
DirectXに対応すれば、AMDのGPUでも高速に推論が可能になる。

ということで、練習のためにONNX RuntimeをC++から使って、MNISTの推論を行ってみた。
今回は、Linux(Ubuntu 18.04)でCPUのみで動かした。

ONNX Runtimeのインストール

GitHubのReleaseからバイナリをダウンロードする。
Linux向けに、onnxruntime-linux-x64-1.3.0.tgzをダウンロードし、適当なディレクトリに展開する。

LD_LIBRARY_PATHの設定

export LD_LIBRARY_PATH=/xxxx/onnxruntime-linux-x64-1.3.0/lib:$LD_LIBRARY_PATH

サンプルコード

公式のリポジトリで、C++のMNISTの推論のサンプルが提供されている。
しかし、これはWindowsのWin32APIを使ったGUIプログラムになっている。
（クロスプラットフォームのオープンソースのサンプルコードがWin32プログラムとかやめてほしい・・・）

Win32のコードを削除して、コンソールプログラムにした。

#include <onnxruntime_cxx_api.h>
#include <algorithm>
#include <iostream>

struct MNIST {
	MNIST() {
		auto memory_info = Ort::MemoryInfo::CreateCpu(OrtDeviceAllocator, OrtMemTypeCPU);
		input_tensor_ = Ort::Value::CreateTensor<float>(memory_info, input_image_.data(), input_image_.size(), input_shape_.data(), input_shape_.size());
		output_tensor_ = Ort::Value::CreateTensor<float>(memory_info, results_.data(), results_.size(), output_shape_.data(), output_shape_.size());
	}

	std::ptrdiff_t Run() {
		const char* input_names[] = {"Input3"};
		const char* output_names[] = {"Plus214_Output_0"};

		session_.Run(Ort::RunOptions{nullptr}, input_names, &input_tensor_, 1, output_names, &output_tensor_, 1);

		result_ = std::distance(results_.begin(), std::max_element(results_.begin(), results_.end()));
		return result_;
	}

	static constexpr const int width_ = 28;
	static constexpr const int height_ = 28;

	std::array<float, width_ * height_> input_image_{};
	std::array<float, 10> results_{};
	int64_t result_{0};

private:
	Ort::Env env;
	Ort::Session session_{env, "model.onnx", Ort::SessionOptions{nullptr}};

	Ort::Value input_tensor_{nullptr};
	std::array<int64_t, 4> input_shape_{1, 1, width_, height_};

	Ort::Value output_tensor_{nullptr};
	std::array<int64_t, 2> output_shape_{1, 10};
};

std::unique_ptr<MNIST> mnist_;

int main()
{
	try {
		mnist_ = std::make_unique<MNIST>();
	} catch (const Ort::Exception& exception) {
		std::cerr << exception.what() << std::endl;
		return 1;
	}

	mnist_->input_image_ = {
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	};
	mnist_->Run();
	std::cout << mnist_->result_ << std::endl;

	return 0;
}

Makefile

ビルドのためにMakefileを作成する。

CC = g++
CFLAGS = -std=c++14 -msse4.2 -mbmi2
LDFLAGS = -lonnxruntime
INCLUDE = -I../onnxruntime-linux-x64-1.3.0/include
LIB = -L../onnxruntime-linux-x64-1.3.0/lib

target = mnist
sources = mnist.cpp
objects = $(addprefix obj/, $(sources:.cpp=.o))

$(target): $(objects)
	$(CC) -o $@ $^ $(LIB) $(LDFLAGS) $(CFLAGS)

obj/%.o: %.cpp
	@[ -d obj ] || mkdir -p obj
	$(CC) $(CFLAGS) $(INCLUDE) -o $@ -c $<

all: $(target)

clean:
	rm -f $(objects) $(target)

ビルド

make

モデルダウンロード

サンプルの説明にあるMNISTのONNXモデルをダウンロードする。
https://github.com/onnx/models/tree/master/vision/classification/mnist

ONNX version 1.3のモデルをダウンロードした。
展開して、model.onnxを実行ファイルと同じディレクトリに配置する。

実行

./mnist

結果：

まとめ

ONNX RuntimeをC++から使用してMNISTの推論を行うことができた。

ONNX Runtimeは計算グラフの最適化を行う機能があるが、今回のサンプルでは試していない。
GPUと比較した場合のパフォーマンスも気になるところなので、別途比較してみたい。

2020-05-25

Agent57: Outperforming the Atari Human Benchmarkを読むその１４

Agent57

付録G. ハイパーパラメータ

G.1. $\beta$ と $\gamma$ の値

セット $\{(\beta_j, \gamma_j)\}_{j=0}^{N-1}$ の選択の間の直感は次のとおりです。
$\beta_j$ については、非常に活用的である方策と探索的である方策を奨励したいので、図11(a)に示すようにシグモイドを選択する。
$\gamma_j$ については、活用方策（ $\beta_j$ の値が小さい）には長期的な視野（ $\gamma_j$ の値が高い）、探索的方策（ $\beta_j$ の値が高い）には短期的な視野（ $\gamma_j$ の値が小さい）を考慮する。
これは主に、外発的報酬の希薄さと内発的報酬の密集した性質によるものである。
これは、図11(b)で行われた選択の動機になる。

図11. N = 32とβ= 0.3の $\{\beta_i\}_{i=0}^{N-1}$ と $\{\gamma_i\}_{i=0}^{N-1}$ の値

(a) $\{\beta_i\}_{i=0}^{N-1}$ が取る値

f:id:TadaoYamaoka:20200525092616p:plain

(b) $\{\gamma_i\}_{i=0}^{N-1}$ が取る値

f:id:TadaoYamaoka:20200525092624p:plain

$\displaystyle \beta_j = \left\{ \begin{array}{ll} 0 & \mbox{if }\ j = 0 \\ \beta=0.3 & \mbox{if }\ j = N-1 \\ \beta \cdot \sigma(10\frac{2j - (N-2)}{N-2}) & otherwise \\ \end{array} \right.$

$\displaystyle \quad\gamma_j = \left\{ \begin{array}{ll} \gamma_0 & \mbox{if }\ j = 0 \\ \gamma_1 + (\gamma_0-\gamma_1)\sigma(10\frac{2i - 6}{6}) & \mbox{if }\ j\in\{1, \dots, 6\} \\ \gamma_1 & \mbox{if }\ j = 7 \\ 1 - \exp\bigg(\frac{(N-9)\log(1-\gamma_{1}) + (j-8)\log(1-\gamma_{2})}{N-9}\bigg) & otherwise \\ \end{array} \right.$

G.2. Atariの前処理ハイパーパラメータ

この節では、Arcade学習環境から受け取った環境フレームを前処理するために使用するハイパーパラメータについて詳しく説明する。
表2で、そのようなハイパーパラメータについて詳しく説明する。
ALEはhttps://github.com/mgbellemare/Arcade-Learning-Environmentで公開されている。

表2. Atariの前処理ハイパーパラメータ

Hyperparameter	Value
Max episode length	30 min
Num. action repeats	4
Num. stacked frames	1
Zero discount on life loss	false
Random noops range	30
Sticky actions	false
Frames max pooled	3 and 4
Grayscaled/RGB	Grayscaled
Action set	Full

G.3. 使用されたハイパーパラメータ

すべての実験で使用したハイパーパラメータは、NGUのハイパーパラメータとまったく同じである。
ただし、完全を期すため、表3で詳しく説明する。
また、ウィンドウ化されたUCBバンディットに使用するハイパーパラメータも含める。

表3. Agent57のハイパーパラメータ

f:id:TadaoYamaoka:20200525094616p:plain

G.4. ハイパーパラメータ探索範囲

Agent57のハイパーパラメータを選択するために使用した範囲を表4に示す。

表4. ハイパーパラメータのスイープ範囲

f:id:TadaoYamaoka:20200525094746p:plain

2020-05-22

Agent57: Outperforming the Atari Human Benchmarkを読むその１３

Agent57

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

図9. Agent57のスケッチ

f:id:TadaoYamaoka:20200522094703p:plain

図10. Agent57の詳細

f:id:TadaoYamaoka:20200522094729p:plain

2020-05-22

Agent57: Outperforming the Atari Human Benchmarkを読むその１２

Agent57

付録E. 分散設定の実装の詳細

リプレイバッファー

固定長の遷移 $\xi=(\omega_s)_{s=t}^{t+H-1}$ のシーケンスと優先度 $p_\xi$ を格納する。
遷移は $\omega_s=(r^e_{s-1}, r^i_{s-1}, a_{s-1}, h_{s-1}, x_s, a_s, h_s, \mu_s, j_s, r^e_{s}, r^i_{s}, x_{s+1})$ の形式である。
このような遷移はタイムステップとも呼ばれ、シーケンスHの長さはトレース長と呼ばれる。
さらに、リプレイバッファー内の隣接するシーケンスは、リプレイ期間と呼ばれるいくつかのタイムステップでオーバーラップし、シーケンスがエピソードの境界を越えることはない。
遷移の各要素について説明する。
- $r^e_{s-1}$ ：前回の外発的報酬
- $r^i_{s-1}$ ：前回の内発的報酬
- $a_{s-1}$ ：前回エージェントが行った行動
- $h_{s-1}$ ：前回のリカレント状態（この場合はLSTMの隠れ状態）
- $x_s$ ：現在の環境によって提供される観測
- $a_s$ ：エージェントが現在行っている行動
- $h_{s}$ ：現時点でのリカレント状態（この場合はLSTMの隠れ状態）
- $\mu_s$ ：行動 $a_s$ を選択する確率
- $j_s=j$ ：マルチアームバンディットアルゴリズム（シーケンス全体で固定）によって各アクターのエピソードの開始時に選択されたペア $(\gamma_{j}, \beta_{j})$ のインデックス
- $r^e_s$ ：現在の外発的報酬
- $r^i_s$ ：現時点での内発的報酬
- $x_{s+1}$ ：次回の環境によって提供される観測

私たちの実験では、再生期間80のトレース長160または再生期間40のトレース長80を選択する。
トレードオフの詳細な実験については、（Kapturowski et al., 2018）を参照してほしい。
最後に、優先度に関して、優先度指数 $\eta= 0.9$ のシーケンスのTD誤差の最大値と平均値の混合を使用して、Kapturowskiらによって提案された同じ優先順位付けスキームに従った。

アクター

L個の各アクターは、ラーナーと同じネットワークアーキテクチャを共有するが、重み $\theta_l$ が異なり、 $0 \leq l \leq L-1$ である。
l番目のアクターは、ラーナーの重みをコピーして、400フレームごとに重み $\theta_l$ を更新する。
各エピソードの初めに、各アクターは、マルチアームバンディットアルゴリズムを介して、ペア $(\{\beta_j, \gamma_j)\}_{j=0}^{N-1}$ のファミリーのペア $(\gamma_j, \beta_j)$ を表すインデックスjを選択する。
また、リカレント状態はゼロに初期化される。
行動するために、アクターは、 $Q(x_t, ., j; \theta_l)$ で示されるすべての行動の状態行動価値を計算するために、ネットワークでフォワードパスを実行する必要がある。
これを行うには、ネットワークの入力は次のとおりです。
- $x_t$ ：時間tの観測
- $r^e_{t-1}$ ： $r^e_{-1}=0$ で初期化された、前回の外発的報酬
- $r^i_{t-1}$ ： $r^i_{-1}=0$ で初期化された、前回の内発的報酬
- $a_{t-1}$ ：前回の行動、 $a_{-1}$ はランダムに初期化される
- $h_{t-1}$ ：前回のリカレント状態、 $h_{-1}=0$ で初期化される
- $j_{t-1}=j$ ：マルチアームバンディットアルゴリズムによって選択されたペア $(\beta_j, \gamma_j)$ のインデックス（すべてのエピソードで固定）

時間tで、l番目のアクターは $Q(x_t, ., j; \theta_l)$ に関して $\epsilon_l$ -greedyに行動する。

$\displaystyle \left\{ \begin{array}{ll} \text{If: } U_t< \epsilon_l, a_t = Y_t, &\\ \text{Else: } a_t = argmax_{a\in\mathcal{A}} Q(x_t, a, j; \theta_l),& \end{array} \right.$

ここで、 $U_t$ は $[0, 1$ ]から均一に引き出されたランダムな値であり、 $Y_t$ は $\mathcal{A}$ から均一に引き出されたランダムな行動である。
したがって、 $a_t$ に関連する確率 $\mu_t$ は次のとおりである。

$\displaystyle \left\{ \begin{array}{ll} \text{If: } U_t< \epsilon_l, \mu_t = \frac{\epsilon_l}{|\mathcal{A}|}, &\\ \text{Else: } \mu_t = 1 - \epsilon_l\frac{|\mathcal{A}|-1}{|\mathcal{A}|},& \end{array} \right.$

ここで $|\mathcal{A}|$ は行動空間の基数で、アタリゲームの場合は18である。
次に、アクターは行動 $a_t$ を実行し、内発的報酬 $r^i_t$ を計算し、環境は次の観測 $x_{t+1}$ と外発的報酬 $r^e_t$ を生成する。
このプロセスは、エピソードの最後まで続く。

ノイズ $\epsilon_l$ の値は、Horganらによって確立された同じ式に従って選択される。

$\displaystyle \begin{equation*} \epsilon_l = \epsilon^{1+\alpha\frac{l}{L-1}} \end{equation*}$

ここで、 $\epsilon=0.4$ で、 $\alpha=8$ である。
この実験では、アクターの数を $L=256$ に固定する。
最後に、アクターは収集されたデータを優先順位と共にリプレイに送信する。

エバリュエーター

エバリュエーターは、ラーナーと同じネットワークアーキテクチャを共有するが、重み $\theta_e$ が異なる。
エバリュエーターは、ラーナーの重みをコピーして、5エピソードフレームごとに重み $\theta_l$ を更新する。
アクターとは異なり、エバリュエーターによって生成されたエクスペリエンスはリプレイバッファーに送信されない。
エバリュエーターは、5エピソードごとに次の状態を交互に切り替える。
- トレーニングバンディットアルゴリズム：エバリュエーターは、マルチアームバンディットアルゴリズムを介して、ペア $(\{\beta_j, \gamma_j)\}_{j=0}^{N-1}$ のファミリーのペア $(\gamma_j, \beta_j)$ を表すインデックスjを選択する。次に、前述のアクターと同じように動作する。エピソードの最後に、割引されていないリターンを使用して、マルチアームバンディットアルゴリズムを訓練する。
- 評価：エバリュエーターは、インデックスjの貪欲な選択 $argmax_{1\leq a \leq N} \hat{\mu}_{k-1}(a)$ を選択するため、 $(\gamma_j, \beta_j)$ で動作する。次に、前述のアクターと同じように動作する。 5つのエピソードの最後で、他のモードに切り替える前に、それらの5つのエピソードの結果は平均で報告される。

ラーナー

ラーナーには、それぞれ異なる重み $\theta$ と $\theta^-$ を持つオンラインネットワークとターゲットネットワークと呼ばれる2つの同一のネットワークが含まれている。
ターゲットネットワークの重み $\theta^-$ は、1500の最適化ステップごとに $\theta$ に更新される。
私たちの特定のアーキテクチャでは、重み $\theta=\theta^e\cup\theta^i$ は、同じアーキテクチャを持つ固有の重み $\theta^e$ と\theta^i]のセットに分解できる。
同様に、 $\theta^-=\theta^{-,e}\cup\theta^{-, i}$ がある。
内発的重みと外発的重みは、変換された独自のリトレース損失によって更新される。
と\theta^i]は、次の一連の命令を実行することによって更新される。
- 最初に、ラーナーは、サイズがBのバッチの固定長の遷移シーケンスDをリプレイバッファーからサンプリングする。
- 次に、状態行動価値 $\{(Q(x^b_s,.,j^b; \theta^e), Q(x^b_s,.,j^b; \theta^{-,e}), Q(x^b_s,.,j^b; \theta^{i}), Q(x^b_s,.,j^b; \theta^{-,i}))_{s=t}^{t+H}\}_{b=0}^{B-1}$ を取得するために、オンラインネットワークと入力 $\{(x^b_s, r^{e, b}_{s-1}, r^{i, b}_{s-1}, j^b, a^b_{s-1}, h^b_{s-1})_{s=t}^{t+H}\}_{b=0}^{B-1}$ を持つターゲットでフォワードパスが実行される。
- 付録Cに示すように、状態行動価値が計算されると、重み $\theta^e$ と\theta^i]の各セットの変換されたリトレース損失 $L(D, \theta^e, \theta^{-, e}, \pi, \mu, r^e, h)$ と $L(D, \theta^i, \theta^{-, i}, \pi, \mu, r^i, h)$ を簡単に計算できるようになる。ターゲットポリシー $\pi$ は、内発的状態行動価値関数と外発的状態行動価値関数の混合に変換 $h\left(h^{-1}(Q(x^b_s,.,j^b; \theta^e)) + \beta_{j^b_s}h^{-1}(Q(x^b_s,.,j^b; \theta^{i}))\right)$ を適用する場合、 $Q(x^b_s,.,j^b; \theta^e) + \beta_{j^b_s}Q(x^b_s,.,j^b; \theta^{i})$ に関して貪欲である。
- 変換されたリトレース損失は、Adamオプティマイザーで最適化される。
- NGUと同様に、内発的報酬の計算に必要な逆ダイナミクスモデルとランダムネットワーク蒸留損失は、Adamオプティマイザーで最適化される。
- 最後に、サンプリングされた遷移のシーケンス $\xi^b$ ごとに優先度が計算され、再生バッファーで更新される。

使用される計算資源

ハードウェアの観点から、1つのGPUベースのラーナーを使用してエージェントを訓練し、1秒あたり約5つのネットワーク更新を実行する（長さ160の64シーケンスのミニバッチでそれぞれ更新）。私たちは256のアクターを使用し、各アクターはAtariで毎秒約260環境ステップを実行する。

2020-05-19

Agent57: Outperforming the Atari Human Benchmarkを読むその１１

Agent57

付録D. マルチアームバンディット形式

この節では、マルチアームバンディット（MAB）パラダイム、上限信頼限界（UCB）アルゴリズム、およびスライディングウィンドウUCBアルゴリズムについて簡潔に説明する。
より完全な説明と分析については、Garivier & Moulines (2008)を参照してほしい。

各時間 $k\in\mathbb{N}$ で、MABアルゴリズムは、前の行動と報酬のシーケンスを条件とする方策 $\pi$ に従って、可能なアーム $\{0,\dots, N-1\}$ からアーム $A_k$ を選択する。
そうすることで、報酬 $R_k(A_k)\in\mathbb{R}$ を受け取る。
定常の場合、与えられたアームの報酬 $\{R_k(a)\}_{k\geq0}$ は、 i.i.d.確率変数のシーケンスによってモデル化される。
非定常の場合、報酬 $\{R_k(a)\}_{k\geq0}$ は、一連の独立確率変数によってモデル化されるが、その分布は時間とともに変化する可能性がある。

MABアルゴリズムの目標は、特定の範囲 $K$ の予想累積報酬を最大化する方策 $\pi$ を見つけることである。

$\displaystyle \begin{equation*} \mathbb{E}_\pi\left[\sum_{k=0}^{K-1} R_k(A_k)\right] \end{equation*}$

定常的なケースでは、UCBアルゴリズムはよく研究されており、一般的に使用されている。
kステップ後にアームaがプレイされた回数を次のように定義する。

$\displaystyle \begin{equation*} N_k(a) = \sum_{m=0}^{k-1}\mathbf{1}_{\{A_m=a\}} \end{equation*}$

また、kステップ後の腕aの経験的平均を次のように定義する。

$\displaystyle \begin{equation*} \hat{\mu}_k(a) = \frac{1}{N_k(a)} \sum_{m=0}^{k-1} R_k(a)\mathbf{1}_{\{A_m=a\}}. \end{equation*}$

そして、UCBアルゴリズムは次のように定義される。

$\displaystyle \left\{ \begin{array}{ll} \forall 0\leq k\leq N-1,\quad A_k=k &\\ \forall N\leq k\leq K-1,\quad A_k =argmax_{1\leq a \leq N} \hat{\mu}_{k-1}(a) + \beta\sqrt{\frac{\log{(k-1)}}{N_{k-1}(a)}} & \end{array} \right.$

非定常の場合、UCBアルゴリズムは報酬分布の変化に適応できず、その場合はスライディングウィンドウUCBを使用できる。
ウィンドウの長さ $\tau\in\mathbb{N}^*$ は、地平線Kよりもはるかに小さくなければならないことが一般的に理解されている。
長さτのウィンドウに対して、kステップ後にアームaが再生された回数を次のように定義する。

$\displaystyle \begin{equation*} N_k(a, \tau) = \sum_{m=0\vee k-\tau}^{k-1}\mathbf{1}_{\{A_m=a\}} \end{equation*}$

ここで、 $0\vee k-\tau$ は $\max(0,k-\tau)$ を意味する。
長さτのウィンドウに対するkステップ後のアームaの経験的平均を定義する。

$\displaystyle \begin{equation*} \hat{\mu}_k(a, \tau) = \frac{1}{N_k(a, \tau)} \sum_{m=0\vee k-\tau}^{k-1} R_k(a)\mathbf{1}_{\{A_m=a\}} \end{equation*}$

そして、スライディングウィンドウUCBは次のように定義できます。

$\displaystyle \left\{ \begin{array}{ll} \forall 0\leq k\leq N-1,\quad A_k=k &\\ \forall N\leq k\leq K-1,\quad A_k =argmax_{1\leq a \leq N} \hat{\mu}_{k-1}(a, \tau) + \beta\sqrt{\frac{\log{(k-1\wedge\tau)}}{N_{k-1}(a, \tau)}} & \end{array} \right.$

ここで、 $k-1\wedge\tau$ は $\min(k-1,\tau)$ を意味する。

私たちの実験では、 $\epsilon_{\texttt{UCB}}$ -greedy探索を使用した簡略化されたスライディングウィンドウUCBを使用する。

$\displaystyle \left\{ \begin{array}{ll} \forall 0\leq k\leq N-1,\quad A_k=k &\\ \forall N\leq k\leq K-1 \text{ and } U_k\geq \epsilon_{\texttt{UCB}},\quad A_k =argmax_{0\leq a \leq N-1} \hat{\mu}_{k-1}(a, \tau) + \beta\sqrt{\frac{1}{N_{k-1}(a, \tau)}} &\\ \forall N\leq k\leq K-1 \text{ and } U_k< \epsilon_{\texttt{UCB}},\quad A_k = Y_k & \end{array} \right.$

ここで、 $U_k$ は $[0, 1]$ から均一に引き出されたランダムな値であり、 $Y_k$ は $\{0, \dots, N-1\}$ から均一に引き出されたランダムな行動である。

AlphaZeroの学習則

ルートノードの分布の使用有無

Actor-Critic

価値関数の学習

価値の学習のブートストラップ

SWA

学習則まとめ

付録H. 実験結果

H.1. Atari 10：アブレーションのスコア表

H.2. Backpropウィンドウの長さの比較

図12. 難易度の高い10ゲームのセットでの、Backpropウィンドウの長さが短い場合と長い場合のパフォーマンスの比較

H.3. アイデンティティとh変換の組み合わせの比較

図13. 挑戦的な10ゲームのセットでのアイデンティティとh変換ミックスのパフォーマンス比較

H.4. Atari 57のスコア表

H.5. Atari 57の学習曲線

図14. Atari57でのAgent57の学習曲線

H.6. ビデオ

ONNX Runtimeのインストール

LD_LIBRARY_PATHの設定

サンプルコード

ビルド

モデルダウンロード

実行

まとめ

付録G. ハイパーパラメータ

G.1. との値

図11. N = 32とβ= 0.3のとの値

G.2. Atariの前処理ハイパーパラメータ

表2. Atariの前処理ハイパーパラメータ

G.3. 使用されたハイパーパラメータ

表3. Agent57のハイパーパラメータ

G.4. ハイパーパラメータ探索範囲

表4. ハイパーパラメータのスイープ範囲

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

図9. Agent57のスケッチ

図10. Agent57の詳細

付録E. 分散設定の実装の詳細

リプレイバッファー

アクター

エバリュエーター

ラーナー

使用される計算資源

付録D. マルチアームバンディット形式

G.1. $\beta$ と $\gamma$ の値

図11. N = 32とβ= 0.3の $\{\beta_i\}_{i=0}^{N-1}$ と $\{\gamma_i\}_{i=0}^{N-1}$ の値