TadaoYamaokaの日記

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

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

付録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_rT^{\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*}

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

\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, h}Q_k,&
    \end{array}
\right.

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