いものやま。

雑多な知識の寄せ集め

強化学習について学んでみた。（その26）

技術 AI 強化学習

昨日は、適格度トレースについて説明した。

ただ、元々の前方観測的見方と、適格度トレースを使った後方観測的見方が等価であるかどうか、という問題が残った。
今日はそれについて。

前方観測的見方と後方観測的見方の等価性

さて、正直、この説明は本来なら飛ばして、本を読んでね、としたかったんだけど、そう出来なかったのが、本の数式の展開が途中をすっ飛ばしすぎていて、自力で計算するとかなり大変じゃないかな、と思ったから。

じっくり式展開していくよ・・・

なお、ここでは本と同じように、行動価値ではなく状態価値について言及して、記法も本に従うけど、簡単に読み替えられるはず。

前方観測的見方である \lambda収益 R^{\lambda}_{t}による時刻 tでの状態価値 Vの増分を \Delta V^{\lambda}_tで表すとしたとき、これは

 {
\Delta V^{\lambda}_t (s) = \left\{ \begin{array}{ll}
\alpha \left( R^{\lambda}_t -  V_t(s) \right) & (s = s_t) \\
0 & (\mbox{otherwise})
\end{array} \right.
}

となる。

そして、エピソード全体での増分の合計は、各状態 s \in \mathcal{S}ごとに、

 { \displaystyle
\sum_{t=0}^{T-1} \Delta V^{\lambda}_t (s_t) \mathcal{I}_{ss_t}, \: \mbox{where} \: \mathcal{I}_{ss_t} = \left\{
\begin{array}{ll}
1 & (s = s_t) \\
0 & (\mbox{otherwise})
\end{array} \right.
}

となる。
（※ここ、本だと記述が混乱していて、 \Delta V^{\lambda}_tが2つ前の式の意味で使われている場合もあるし、 \Delta V^{\lambda}_t = \alpha ( R^{\lambda}_t - V_t(s) )の意味で使われている場合もある。以下では \mathcal{I}_{ss_t}を使うので、後者の意味で捉えること）

一方、後方観測的見方である適格度トレースによる時刻 tでの状態価値 Vの増分を \Delta V^{TD}_t (s)で表すとしたとき、これは

 {
\Delta V^{TD}_t (s) = \alpha \delta_t e_t(s)
}

となる。

そして、エピソード全体での増分の合計は、各状態 s \in \mathcal{S}ごとに、

 { \displaystyle
\sum_{t=0}^{T-1} \Delta V^{TD}_t (s)
}

となる。

したがって、任意の状態 s \in \mathcal{S}について、

 { \displaystyle
\sum_{t=0}^{T-1} \Delta V^{TD}_t (s) = \sum_{t=0}^{T-1} \Delta V^{\lambda}_t (s_t) \mathcal{I}_{ss_t}
}

であることを示せれば、前方観測的見方による状態価値の更新量と、後方観測的見方による状態価値の更新量が等しいことが分かるので、すなわち、前方観測的見方と後方観測的見方が等価であることが示されることになる。

まず、左辺について。

適格度トレース e_t(s)は、

 { \displaystyle
e_t(s) = \sum_{k=0}^t (\gamma \lambda)^{t-k} \mathcal{I}_{ss_k}
}

と書くことが出来るので、左辺は、

 { \displaystyle
\begin{align}
\sum_{t=0}^{T-1} \Delta V^{TD}_t (s) &= \sum_{t=0}^{T-1} \alpha \delta_t e_t(s) \\
&= \sum_{t=0}^{T-1} \alpha \delta_t \left( \sum_{k=0}^t (\gamma \lambda)^{t-k} \mathcal{I}_{ss_k} \right) \\
&= \alpha \delta_0 \left( (\gamma \lambda)^0 \mathcal{I}_{ss_0} \right) \\
& \quad + \alpha \delta_1 \left( (\gamma \lambda)^1 \mathcal{I}_{ss_0} + (\gamma \lambda)^0 \mathcal{I}_{ss_1} \right) \\
& \quad + \alpha \delta_2 \left( (\gamma \lambda)^2 \mathcal{I}_{ss_0} + (\gamma \lambda)^1 \mathcal{I}_{ss_1} + (\gamma \lambda)^0 \mathcal{I}_{ss_2} \right) \\
& \quad + \cdots \\
& \quad + \alpha \delta_{T-1} \left( (\gamma \lambda)^{T-1} \mathcal{I}_{ss_0} + (\gamma \lambda)^1 \mathcal{I}_{ss_1} + \cdots + (\gamma \lambda)^0 \mathcal{I}_{ss_{T-1}} \right) \\
&= \alpha \mathcal{I}_{ss_0} \left( \delta_0 (\gamma \lambda)^0 + \delta_1 (\gamma \lambda)^1 + \cdots + \delta_{T-1} (\gamma \lambda)^{T-1} \right) \\
& \quad + \alpha \mathcal{I}_{ss_1} \left( \quad \quad \quad \delta_1 (\gamma \lambda)^0 + \cdots + \delta_{T-1} (\gamma \lambda)^{T-2} \right) \\
& \quad + \cdots \\
& \quad + \alpha \mathcal{I}_{ss_{T-1}} \left( \quad \quad \quad \quad \quad \quad \quad \quad \delta_{T-1}(\gamma \lambda)^0 \right) \\
&= \sum_{t=0}^{T-1} \alpha \mathcal{I}_{ss_t} \left( \sum_{k=t}^{T-1} \delta_k (\gamma \lambda)^{k-t} \right)
\end{align}
}

と表すことが出来る。

次に、右辺について。

 { \displaystyle
\begin{align}
\frac{1}{\alpha} \Delta V^{\lambda}_t (s_t) &= R^{\lambda}_t - V_t(s_t) \\
&= - V_t(s_t) + (1 - \lambda) \lambda^0 (r_{t+1} + \gamma V_t (s_{t+1}) ) \\
& \quad \quad \quad \quad + (1 - \lambda) \lambda^1 (r_{t+1} + \gamma r_{t+2} + \gamma^2 V_t(s_{t+2}) ) \\
& \quad \quad \quad \quad + (1 - \lambda) \lambda^2 (r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \gamma^3 V_t(s_{t+3}) ) \\
& \quad \quad \quad \quad + \cdots \\
&= -V_t(s_t) \\
& \quad + (1 - \lambda) ( \lambda^0 + \lambda^1 + \cdots ) r_{t+1} \\
& \quad + (1 - \lambda) ( \gamma \lambda^1 + \gamma \lambda^2 + \cdots ) r_{t+2} \\
& \quad + (1 - \lambda) ( \gamma^2 \lambda^2 + \gamma^2 \lambda^3 + \cdots ) r_{t+3} \\
& \quad + \cdots \\
& \quad \quad + (1 - \lambda) \gamma \lambda^0 V_t(s_{t+1}) \\
& \quad \quad + (1 - \lambda) \gamma^2 \lambda^1 V_t(s_{t+2}) \\
& \quad \quad + (1 - \lambda) \gamma^3 \lambda^2 V_t(s_{t+3}) \\
& \quad \quad + \cdots \\
&= - V_t(s_t) \\
& \quad + r_{t+1} \quad \quad + \gamma \lambda r_{t+2} \quad \quad + \gamma^2 \lambda^2 r_{t+3} \quad + \cdots \\
& \quad + \gamma V_t(s_{t+1}) - \gamma \lambda V_t(s_{t+1}) \\
& \quad \quad \quad \quad \quad + \gamma^2 \lambda V_t(s_{t+2})  - \gamma^2 \lambda^2 V_t(s_{t+2}) \\
& \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad + \gamma^3 \lambda^2 V_t(s_{t+3}) - \gamma^3 \lambda^3 V_t(s_{t+3}) \\
& \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad + \ddots \\
&= (r_{t+1} + \gamma V_t(s_{t+1}) - V_t(s_t)) \\
& \quad + \gamma \lambda (r_{t+2} + \gamma V_t(s_{t+2}) - V_t(s_{t+1})) \\
& \quad + \gamma^2 \lambda^2 (r_{t+3} + \gamma V_t(s_{t+3}) - V_t(s_{t+2})) \\
& \quad + \cdots \\
&= (\gamma \lambda)^0 \delta_t + (\gamma \lambda)^1 \delta_{t+1} + (\gamma \lambda)^2 \delta_{t+2} + \cdots \\
&\approx \sum_{k=t}^{T-1} (\gamma \lambda)^{k-t} \delta_k
\end{align}
}

と計算できるので、右辺は、

 { \displaystyle
\sum_{t=0}^{T-1} \Delta V^{\lambda}_t (s_t) \mathcal{I}_{ss_t} =  \sum_{t=0}^{T-1} \alpha \mathcal{I}_{ss_t} \left( \sum_{k=t}^{T-1} (\gamma \lambda)^{k-t} \delta_k \right)
}

と表すことが出来る。

以上より、任意の状態 s \in \mathcal{S}について、示したい等式が成り立つことが示された。

この計算、辛かった・・・（ \TeXでの数式の打ち込みも辛かった・・・）

今日はここまで！

強化学習

強化学習

  • 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
  • 出版社/メーカー: 森北出版
  • 発売日: 2000/12/01
  • メディア: 単行本（ソフトカバー）
  • 購入: 5人 クリック: 76回
  • この商品を含むブログ (29件) を見る