TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

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

付録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*}

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