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

昨日はTD( $\lambda$ )法について説明した。

今日は、これを実際に実装できるようにするために、適格度トレースについて考えていく。

TD( $\lambda$ )法のイメージ

まず、TD( $\lambda$ )法のイメージを確認しておくと、次のような感じ。

f:id:yamaimo0625:20151207234054p:plain

各段がそれぞれ $n$ ステップTD法になっていて、それぞれの $n$ ステップ収益と現在の推定価値との差分について、それぞれの重みで学習を行っている。

ただ、問題は、これだと $nステップ先$ にならないと現在の推定価値を更新できないということ。
それだと、更新が生じるまでにだいぶ待つ必要が出てくる。

そこで、視点を逆転させる。

今は、時間ステップ $t$ から見て、時間ステップ $t+n$ での推定価値との差分を、時間ステップ $t$ での価値の推定に使おうとしているけど、逆に、時間ステップ $t+n$ から見て、その推定価値との差分が、時間ステップ $t$ の時点の価値の推定にどれくらい影響を与えているのかを考えてみる。

まず、各ステップでの価値の差分が表現できるように、先ほどの図を次のように次のように書き換えてみる。

f:id:yamaimo0625:20151208004754p:plain

そして、これを縦に輪切り。
そうすると、各ステップの価値の差分が、どのように前の価値の推定に影響しているのかが見えてくる。

f:id:yamaimo0625:20151208010434p:plain

具体的には、例えば今 $t+1$ にいるとすると、その価値の差分は $t$ で観測された状態行動対の価値に、各 $n$ ステップTD法で $1-\lambda, (1-\lambda)\lambda, \cdots, (1-\lambda)\lambda^{n-1}, \cdots$ の重みで影響を与えるのだから、合計で1倍の影響を与えることになる。（ $(1-\lambda)(1+\lambda + \lambda^2 + \cdots) = 1$ だから）
同様に、今 $t+2$ にいるとすると、その価値の差分は $t$ で観測された状態行動対の価値に、1ステップTD法以外の各 $n$ ステップTD法で $(1- \lambda)\lambda, (1 - \lambda)\lambda^2, \cdots$ の重みで影響を与えるのだから、合計で $\lambda$ 倍の影響を与えることになる。

同様に考えていくことで、この図から、各ステップでの価値の差分は、 $n$ 個前の価値の推定に、 $\lambda^{n-1}$ の重みで影響を与えているということが分かる。

そこで、次のような、時間ステップ $t$ での適格度トレース $\boldsymbol{e}^{(t)} \in \mathbb{R}^{\mathcal{S} \times \mathcal{A}(s)}$ というものを考えてみる：

この適格度トレースの意味するところは、時間ステップ $t$ において、次の状態行動対 $(s_{t+1}, a_{t+1})$ を観測したときに、その価値の差分をどれくらいの重みで各状態行動対 $(s, a)$ の価値に反映させるのか、というもの。

実際、上記の式を観察してみると、

最初は0なので、状態行動対 $(s, a)$ が観測されるまでは、価値 $Q_{s, a}$ に各時間ステップでの価値の差分は反映させない
時間ステップ $t$ で状態行動対 $(s, a)$ が観測されたら、価値 $Q_{s, a}$ に時間ステップ $t+1$ での価値の差分を追加で反映させるようにする
時間ステップが離れていくごとに、観測された状態行動対 $(s, a)$ の価値 $Q_{s, a}$ に反映させる各時間ステップでの価値の差分は、 $\gamma \lambda$ 倍、 $\gamma^2 \lambda^2$ 倍、・・・と、減衰していく

となっている。

これによって、1つ前の状態行動対の価値には、価値の差分の1倍、2つ前の状態行動対の価値には、価値の差分の $\gamma \lambda$ 倍、・・・の重みで、価値の差分の反映を行うことが出来るようになる。

具体的には、次のように価値の更新を行う：

時間ステップ $t$ でのTD誤差 $\delta^{(t)}$ を

としたとき、すべての $s \in \mathcal{S}$ 、 $a \in \mathcal{A}(s)$ について、

と更新する。

ちなみに、このブログだと本とは違って、行動価値、適格度トレースをベクトルで定義してあるので、これは次のように書くことも出来る：

キレイw

ところで、ここではTD( $\lambda$ )法に対する、2つの見方を示したことになる。

一つは、時間ステップ $t$ から先の価値を見て、その価値と時間ステップ $t$ での価値との差分を使って、時間ステップ $t$ での価値を更新するという見方。
もう一つは、時間ステップ $t+n$ から前の状態行動対を見て、その価値に現在の差分がどれくらい影響を与えるのかを考え、反映させるという見方。

本では、前者の見方を前方観測的な見方、後者の見方を後方観測的な見方と呼んでいる。

上に示した適格度トレースを用いた更新方法は、この2つが等価であることを前提にしている。
もちろん、この2つが等価であろうということは、図を使ってざっくりと説明したけど、ちゃんとした証明にはなっていない。
なので、明日はこの2つが等価であることを示していきたいと思う。

今日はここまで！