TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。

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

付録も読んでいきます。数式多めです。ほぼ自分のメモのために訳しています。

付録A MDPの背景

  • マルコフ決定プロセス(MDP)はタプル(\mathcal{X},\mathcal{A}, P, r, \gamma)であり、Xは状態空間、Aは行動空間、Pは各状態行動タプル(x, a)を状態上の確率分布(行動aを選択してxから状態yに遷移する確率をP(y|x,a)とする)にマッピングした状態遷移分布、報酬関数r\in\mathbb{R}^{\mathcal{X}\times\mathcal{A}}、割引率\gamma\in0, 1[]を持つ。
  • 確率的ポリシーπは、各状態を行動の分布にマッピングする(\pi(a|x)は、状態xでアクションaを選択する確率を示す)。 決定論的方策\pi_D\in\mathcal{X}^\mathcal{A}は、行動πの分布\pi(\pi_D(x)|x)=1で表すこともできる。コンテキストが明確な場合は、残りの部分で同じ表記法πを使用してどちらかの概念を使用する。


  • T(x, a, \pi)(X_0,A_0)=(x,a)$, $\forall t\geq1, A_t\sim\pi(.|X_t)$, $\forall t\geq0, R_t=r(X_t, A_t)\forall t\geq0, X_{t+1}\sim P(.|X_t, A_t)を使用して、方策\piによって生成された軌跡\tau=(X_t, A_t, R_t, X_{t+1})_{t\in\mathbb{N}}上の分布とする。
  • 次に、方策\piおよび状態行動タプル(x, a)の状態アクション値関数Q_r^{\pi}(x, a)は、次のように定義される。

\displaystyle
\begin{equation*}
    Q_r^{\pi}(x, a) = \mathbb{E}_{\tau\sim T(x, a, \pi)}\left[ \sum_{t\geq 0} R_t\right]
\end{equation*}

  • 最適な状態行動価値関数Q^*は、次のように定義される。

\displaystyle
\begin{equation*}
    Q_r^*(x, a) = \max_{\pi}Q_r^{\pi}(x, a)
\end{equation*}

  • ここで、最大値はすべての確率的方策よりも優先される。


  • すべての関数Q\in\mathbb{R}^{\mathcal{X}\times\mathcal{A}}およびすべての状態行動タプル(x, a)\in \mathcal{X}\times\mathcal{A}に対して、次のように1ステップの評価ベルマン作用素を定義する。

\displaystyle
\begin{equation*}
    T^\pi_r Q(x, a) = r(x, a) + \gamma \sum_{b\in\mathcal{A}}\sum_{x'\in\mathcal{X}}\pi(b|x)P(x'|x, a)Q(x', b)
\end{equation*}

  • 1ステップ評価のベルマン作用素は、ベクトル表記で書くこともできる。

\displaystyle
\begin{equation*}
    T^\pi_r Q = r + \gamma P^\pi Q
\end{equation*}

  • ここで、P^\piは、ダイナミクスPのMDPにおける\piに従って作用する効果を表す遷移行列である。
  • 評価ベルマン作用素は縮約であり、その固定点はQ^{\pi}_rである。


  • 最後に、すべての関数Q\in\mathbb{R}^{\mathcal{X}\times\mathcal{A}}およびすべての状態x\in \mathcal{X}について、次のように貪欲作用素\mathcal{G}を定義する。

\displaystyle
\begin{equation*}
     \mathcal{G}(Q)(x) = argmax_{a\in\mathcal{A}}Q(x,a)
\end{equation*}

  • 次に、固定点引数を介して、次の離散スキームのように(Puterman, 1990)を示すことができる。

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

  • ここで、Q_0は任意に初期化でき、Q^*_rに収束する。
  • この離散スキームは、1ステップ価値反復スキームと呼ばれる。


  • 記事全体を通して、変換されたベルマン作用素も使用している(C.2を参照)。
  • すべての関数Q\in\mathbb{R}^{\mathcal{X}\times\mathcal{A}}およびすべての状態行動タプル(x, a)\in \mathcal{X}\times\mathcal{A}の1ステップ変換評価ベルマン作用素T^\pi_{r, h}は、次のように定義できる。

\displaystyle
\begin{equation*}
    T^\pi_{r, h} Q(x, a) = h\left(r(x, a) + \gamma \sum_{b\in\mathcal{A}}\sum_{x'\in\mathcal{X}}\pi(b|x)P(x'|x, a)h^{-1}(Q(x', b))\right)
\end{equation*}

  • ここで、hは単調に増加する可逆のスカッシング関数であり、状態行動価値関数をスケーリングして、ニューラルネットワークの近似を容易にする。
  • 特に、関数hを使用する。

\displaystyle
\begin{align*}
\forall z\in\mathbb{R},\quad h(z)&=sign(z)(\sqrt{|z|+1}-1) + \epsilon z,
\\
\forall z\in\mathbb{R},\quad h^{-1}(z)&=sign(z)\left(\left(\frac{\sqrt{1+4\epsilon(|z|+1+\epsilon)}-1}{2\epsilon}\right)-1\right),
\end{align*}

  • ここで、\epsilonは小さい数である。
  • 1ステップ変換された評価ベルマン作用素は、ベクトル表記で書くこともできる。

\displaystyle
\begin{equation*}
    T^\pi_{r, h} Q = h\left(r + \gamma P^\pi h^{-1}(Q)\right)
\end{equation*}

  • h(Pohlen et al., 2018)に関するいくつかの条件下で、収縮引数を介して、変換された1ステップの価値反復スキームが次のように示される。

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

  • ここで、Q_0は任意に初期化でき、収束する。
  • この極限Q^*_{r, h}に注意してほしい。

(続く)