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

付録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.$