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\}$ から均一に引き出されたランダムな行動である。

2020-05-18

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

Agent57

付録C.リトレースおよび変換されたリトレース

リトレースは、評価または制御のための方策オフのRLアルゴリズムである。
評価設定の目標は、行動方策 $\mu$ から引き出された軌跡からターゲット方策 $\pi$ の状態行動価値関数 $Q^\pi$ を推定することである。
制御設定では、 $Q^*$ を近似するために、一連のターゲット方策 $\pi_k$ および状態行動価値関数 $Q_k$ を作成することが目標である。

$\mu$ および $\pi$ に依存する評価リトレース演算子 $T^{\mu,\pi}_r$ は、すべての関数 $Q\in\mathbb{R}^{\mathcal{X}\times\mathcal{A}}$ およびすべての状態行動タプル $(x, a)\in \mathcal{X}\times\mathcal{A}$ について、次のように定義される。

$\displaystyle \begin{equation*} T^{\mu,\pi}_rQ(x,a) = \mathbb{E}_{\tau\sim T(x, a, \mu)}\left[Q(x,a) +\sum_{t\geq0}\gamma^t\left(\prod_{s=1}^tc_s\right)\delta_t \right] \end{equation*}$

ここで、TD誤差 $\delta_t$ は次のように定義される。

$\displaystyle \begin{equation*} \delta_t = r_t + \gamma \sum_{a\in A}\pi(a|X_{t+1})Q(X_{t+1},a)-Q(X_t, A_t) \end{equation*}$

およびトレース係数 $c_s$ は次のとおりである。

$\displaystyle \begin{equation*} c_s = \lambda\min\left(1, \frac{\pi(A_s|X_s)}{\mu(A_s|X_s)}\right) \end{equation*}$

ここで、 $\lambda$ は固定パラメータ $\in [0, 1$ ]である。
演算子 $T^{\mu,\pi}_r$ は、方策 $\pi$ を評価するために $\mu$ の動作を修正する多段階評価演算子である。
Munosらの定理1で、 $Q^\pi_r$ が $T^{\mu,\pi}_r$ の不動点であることが示されている。
さらに、Munosらの定理2は、リトレース価値反復スキーム：

$\displaystyle \forall k\geq0, \quad\left\{ \begin{array}{ll} \pi_k = \mathcal{G}\left(Q_k\right), &\\ Q_{k+1} = T^{\mu_k,\pi_k}_r Q_k,& \end{array} \right.$

がどの状態で最適な状態作用値関数 $Q^*$ に収束するかを説明している。

ここで、 $Q_0$ は任意に初期化され、 $\{\mu_k\}_{k\in\mathbb{N}}$ に依存する可能性のある方策の任意のシーケンスである。

ワンステップベルマン演算子の場合と同様に、リトレース演算子の変換された対になるものを定義することもできる。
より具体的には、すべての関数 $Q\in\mathbb{R}^{\mathcal{X}\times\mathcal{A}}$ およびすべての状態行動タプル $(x, a)\in \mathcal{X}\times\mathcal{A}$ に対して、変換されたリトレース演算子 $T^{\mu,\pi}_{r, h}$ を定義できる。

$\displaystyle \begin{equation*} T^{\mu,\pi}_{r, h}Q(x,a) = h\left(\mathbb{E}_{\tau\sim T(x, a, \mu)}\left[h^{-1}(Q(x,a)) +\sum_{t\geq0}\gamma^t\left(\prod_{s=1}^tc_s\right)\delta^h_t\right]\right) \end{equation*}$

ここで、TD誤差は次のように定義される。

$\displaystyle \begin{equation*} \delta^h_t = r_t + \gamma \sum_{a\in A}\pi(a|X_{t+1})h^{-1}(Q(X_{t+1},a))-h^{-1}(Q(X_t, A_t)) \end{equation*}$

リトレース演算子の場合と同様に、変換されたリトレース価値の反復スキームを定義できる。

$\displaystyle \forall k\geq0, \quad\left\{ \begin{array}{ll} \pi_k = \mathcal{G}\left(Q_k\right), &\\ Q_{k+1} = T^{\mu_k,\pi_k}_{r, h} Q_k,& \end{array} \right.$

ここで、 $Q_0$ は任意に初期化され、 $\{\mu_k\}_{k\in\mathbb{N}}$ は方策の任意のシーケンスである。

C.1. リトレースおよび変換されたリトレースのための外発的-内発的分解

付録Bと同じ方法論に従って、報酬が $r=r^e+\beta r^i$ の形式である場合、状態行動価値関数が、リトレースおよび変換されたリトレース価値反復スキームの外発的および内発的コンポーネントに分解できることを示すこともできる。
実際、次の離散スキームを定義すると、

$\displaystyle \forall k\geq0, \quad\left\{ \begin{array}{ll} \tilde{\pi}_k = \mathcal{G}\left(Q^e_k + \beta Q^i_k \right), &\\ Q^i_{k+1} = T_{r^i}^{\tilde{\mu}_k, \tilde{\pi}_k}Q^i_k,&\\ Q^e_{k+1} = T_{r^e}^{\tilde{\mu}_k, \tilde{\pi}_k}Q^e_k,& \end{array} \right.$

ここで、関数 $(Q^e_0, Q^i_0)$ は任意に初期化することができ、 $\{\tilde{\mu_k}\}_{k\in\mathbb{N}}$ は方策の任意のシーケンスである。
次に、線形結合 $\tilde{Q}_k$ であることを示すのは簡単である。

$\displaystyle \begin{equation*} \forall k\geq0, \tilde{Q}_k = Q^e_k + \beta Q^i_k \end{equation*}$

リトレース価値の反復スキームを検証する。

$\displaystyle \forall k\geq0, \quad\left\{ \begin{array}{ll} \tilde{\pi}_k = \mathcal{G}\left(\tilde{Q}_k\right), &\\ \tilde{Q}_{k+1} = T^{\tilde{\mu}_k, \tilde{\pi}_k}_r \tilde{Q}_k,& \end{array} \right.$

同様に、次の離散スキームを定義すると、

$\displaystyle \forall k\geq0, \quad\left\{ \begin{array}{ll} \tilde{\pi}_k = \mathcal{G}\left(h\left(h^{-1}(Q^e_k) + \beta h^{-1}(Q^i_k)\right) \right), &\\ Q^i_{k+1} = T_{r^i, h}^{\tilde{\mu}_k, \tilde{\pi}_k}Q^i_k,&\\ Q^e_{k+1} = T_{r^e, h}^{\tilde{\mu}_k, \tilde{\pi}_k}Q^e_k,& \end{array} \right.$

ここで、関数 $(Q^e_0, Q^i_0)$ は任意に初期化することができ、 $\{\tilde{\mu_k}\}_{k\in\mathbb{N}}$ は方策の任意のシーケンスである。
次に、 $\tilde{Q}_{k}$ が次のように定義されることを示すことも簡単である。

$\displaystyle \begin{equation*} \forall k\geq0,\quad \tilde{Q}_{k} = h\left(h^{-1}(Q^e_k) + \beta h^{-1}(Q^i_k)\right) \end{equation*}$

変換されたリトレース価値の反復スキームを検証する。

C.2. ニューラルネットのリトレースおよび変換リトレース損失

この節では、有限データとニューラルネットワークでリトレース価値反復スキームをどのように近似するかを説明する。
最初に、注目すべき重要なことの1つは、評価ステップを書き直すことができるということである。

$\displaystyle \begin{equation*} Q_{k+1} = T^{\mu_k, \pi_k}_r Q_k \end{equation*}$

から

$\displaystyle \begin{equation*} \label{eq:optimal} Q_{k+1} = argmin_{Q\in\mathbb{R}^{\mathcal{X}\times\mathcal{A}}} \|T^{\mu_k, \pi_k}_r Q_k-Q\| \end{equation*}$

ここで、 $\|.\|$ は関数空間 $\mathbb{R}^{\mathcal{X}\times\mathcal{A}}$ 上の任意のノルムである。
つまり、評価ステップは、関数空間上の最適化問題として見ることができ、ここで、最適化は、目標 $T^{\mu_k, \pi_k}_r Q_k$ に一致する関数 $Q$ を見つけることからなる。

実際には、2つの重要な問題に直面している。
探索空間 $\mathbb{R}^{\mathcal{X}\times\mathcal{A}}$ は大きすぎ、有限のデータセットがあるため、どこでも $T^{\mu_k, \pi_k}_r Q_k$ を評価できない。
前者に取り組むための可能な解決策は、ニューラルネットワークなどの関数近似を使用することである。
そこで、オンラインネットワークとも呼ばれる状態行動価値関数 $Q(x,a; \theta)$ （ここで $\theta$ はニューラルネットワークのパラメータの集合）をパラメータ化する。
後者については、 $T^{\mu_k, \pi_k}_r Q_k$ のサンプリングされた推定値を作成し、最適化問題の目標として使用する。
実際には、目標は、ニューラルネットワークの以前の固定セットのパラメーター $\theta^-$ から構築される。
$Q(x,a;\theta^-)$ はターゲットネットワークと呼ばれる。
ターゲットネットワークは、学習中に一定の頻度でオンラインネットワークの値に更新される。

より正確には、サイズ $H$ の有限サンプリングされたシーケンスのサイズ $B$ のバッチを考えてみよう： $D=\{(x^b_s, a^b_s, \mu^b_s=\mu(a^b_s|x^b_s), r^b_s, x^b_{s+1})_{s=t}^{t+H-1}\}_{b=0}^{B-1}$ から始まり、次に挙動方策 $\mu$ に従う。
すると、有限のサンプリングされたRetraceターゲットを次のように定義することができる。

$\displaystyle \begin{align*} \hat{T}^{\mu, \pi}_r Q(x^b_s, a^b_s; \theta^-)&= Q(x^b_s, a^b_s; \theta^-) + \sum_{j=s}^{t+H-1}\gamma^{j-s}\left(\prod_{i=s+1}^j c_{i,b}\right)\delta_{j, b} \\ c_{i, b} &= \lambda\min\left(1, \frac{\pi(a^b_i|x^b_i)}{\mu^b_i}\right), \\ \delta_{j, b}&= r^b_j + \gamma \sum_{a\in A}\pi(a|x^b_{j+1})Q(x^b_{j+1},a; \theta^-)-Q(x^b_j, a^b_j; \theta^-), \end{align*}$

ここで、 $\pi(a|x)$ はターゲット方策である。

ターゲットが計算されたら、次の損失関数を最小化することにより、それらのターゲットに適合するパラメーター $\theta$ を見つけることが目標である。

$\displaystyle \begin{equation*} L(D, \theta, \theta^-, \pi, \mu, r) = \sum_{b=0}^{B-1}\sum_{s=t}^{t+H-1}\left(Q(x^b_s, a^b_s;\theta)-\hat{T}^{\mu, \pi}_r Q(x^b_s, a^b_s; \theta^-)\right)^2. \end{equation*}$

これは、たとえば勾配降下法などのオプティマイザによって行われる。
オプティマイザによって $\theta$ が更新されると、新しいターゲットによる新しい損失が計算され、収束するまで最小化される。

したがって、実際には、リトレース価値反復スキームの評価ステップ $Q_{k+1} = T^{\mu_k, \pi_k}_r Q_k$ は、オプティマイザを使用して損失 $L(D, \theta, \pi, \mu)$ を最小化することによって概算される。
貪欲なステップ $\pi_k = \mathcal{G}\left(Q_k\right)$ は、オンラインネットワークに関して貪欲であり、次のようにターゲット方策を選択することによって実現される： $\pi = \mathcal{G}\left(Q(x,a;\theta)\right)$ 。

変換されたリトレース演算子の場合、次のターゲットがある。

$\displaystyle \begin{align*} \hat{T}^{\mu, \pi}_{r, h} Q(x^b_s, a^b_s; \theta^-)&=h\left( h^{-1}(Q(x^b_s, a^b_s; \theta^-)) + \sum_{j=s}^{t+H-1}\gamma^{j-t}\left(\prod_{i=s+1}^j c_{i,b}\right)\delta^h_{s, b}\right) \\ c_{i, b} &= \lambda\min\left(1, \frac{\pi(a^b_i|x^b_i)}{\mu^b_i}\right), \\ \delta_{j, b}&= r^b_j + \gamma \sum_{a\in A}\pi(a|x^b_{j+1})h^{-1}(Q(x^b_{j+1},a; \theta^-))-h^{-1}Q(x^b_j, a^b_j; \theta^-). \end{align*}$

そして、変換されたリトレース損失関数は次のとおりである。

$\displaystyle \begin{equation*} L(D, \theta, \theta^- \pi, \mu, r, h) = \sum_{b=0}^{B-1}\sum_{s=t}^{t+H-1}\left(Q(x^b_s,a^b_s;\theta)-\hat{T}^{\mu, \pi}_{r, h} Q(x^b_s, a^b_s; \theta^-)\right)^2 \end{equation*}$

2020-05-13

C++の再現性の低いバグを解析する

C++

先日、dlshogiをfloodgateでテストした際に、goコマンドに対して結果を返さずタイムアップするという事象が発生した。

再現性が低く、全く同じ局面を手動でコンソールからコマンドを入力して何度も探索させても再現しなかった。
スレッドプールの処理に問題がありそうだと予想して、atomic変数のメモリオーダーを設定してみたが、また再現してしまった。

C++のマルチスレッドに関連したバグは、再現性が低いと解析が難しい。
とにかく発生状況をつかまないと原因が解析できないので、なんとかして再現した際に解析できる方法を見つける必要がある。

原因にあたりが付けられる場合は、条件を指定してdebugbreakを仕込んで再現するまで待つということを行うことがある。
今回はあたりが付かなかったので、再現時にcoreダンプを出力するという方法をとった。

再現時に自動でcoreダンプを取得する

usiToCsa.rbを使用してfloodgateに接続していたので、usiToCsa.rbを修正して、サーバからTIME_UPを受信したときに、

`ps | grep usi | awk '{ print "kill -6", $1 }' | sh`

を実行して、子プロセスのusiコマンド(解析対象)にABORTシグナルを送るようにした。

usiコマンドは、ダンプ解析できるように"-g"をオプションを付けてコンパイルしておく。

coreダンプの解析

数日実行してようやく再現して、coreダンプを取得することができた。

coreダンプの解析は、WindowsであればVisual Studioを使うが、今回はLinux上で実行したので、gdbを使って解析した。

gdb usi core

のように引数に実行ファイルとcoreを指定してgdbを起動し、

info threads

で実行中のスレッドを確認して、

thread 1
bt

のように、スレッド番号を指定してスレッドを切り替えてスタックバックトレースを確認するということを、すべてのスレッドについて行う。
これで、想定外の箇所で止まっているスレッドを見つけることができる。

今回の事象は、予想した通りスレッドプールの処理で停止していた。

(探索スレッド)探索開始
(親スレッド)探索終了待機(wait)
(探索スレッド)探索終了
(探索スレッド)探索終了通知(notify_all)
(探索スレッド)スレッド待機(wait)

という流れでcondition_variableを使ってスレッドプールの処理を行っていたが、ゲーム木の状態によって探索が一瞬で終了して2.探索終了待機の前に、4.探索終了通知が行われていた。
そのため、notify_allを受け取れず、waitが解除されないままになっていた。

原因が分かれば修正は簡単で、waitの前に状態を調べてすでに探索が終了していればwaitしないという処理を入れればよかった。
（原因がわかればあらかじめ想定しておくべきことのようだが、コーディングしているときは気付かないものである。）

まとめ

マルチスレッド処理は、想定外の状態が起こりやすいのでバグを埋め込みやすい。
しかもバグの再現性が低く、解析が難しい。
そのような場合は、デバッグツールを使って発生時の状況を調べられると解析が進む。
この記事では、coreダンプを取得して調べる方法について紹介した。

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. マルチアームバンディット形式

付録C.リトレースおよび変換されたリトレース

C.1. リトレースおよび変換されたリトレースのための外発的-内発的分解

C.2. ニューラルネットのリトレースおよび変換リトレース損失

再現時に自動でcoreダンプを取得する

coreダンプの解析

まとめ

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

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