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

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