適格度トレース

※内容が合っている保証は全くありません。

\displaystyle \newcommand{\bs}{\boldsymbol}

前方観測

価値関数が重みベクトル \bs{w} \in \mathbb{R} ^ d で関数近似されているものとする。

n ステップ収益を考える。

\displaystyle \begin{align} G _ {t:t+n} = R _ {t + 1} + \gamma R _ {t + 2} + \dots + \gamma ^ {n - 1} R _ {t + n} + \gamma ^ n \hat{v}(S _ {t + n}, \bs{w} _ {t + n - 1}) \end{align}

これらを \lambda \in [0, 1] を使って重み付けして足し合わせた \lambda 収益を考える。

\displaystyle \begin{align} G _ t ^ \lambda = (1 - \lambda) \sum _ {n=1} ^ \infty \lambda ^ {n-1} G _ {t:t+n} \end{align}

これをターゲットとして重みの更新を考えると、更新される量は以下のようになる。

\displaystyle \begin{align} \Delta ^ {F} _ t := \alpha \left\lbrack G _ t ^ \lambda - \hat{v} (S _ t, \bs{w} _ t) \right\rbrack \nabla \hat{v}(S _ t, \bs{w} _ t) \end{align}

後方観測

重みベクトル \bs{w} \in \mathbb{R} ^ d に対応した適格度トレース \bs{z} \in \mathbb{R} ^ d を考える。 \bs{w} _ t の構成要素が推定価値の出力に寄与したとき、それに対応する \bs{z} _ t が大きくなり、その後は徐々に小さくなっていく。

\displaystyle \begin{align} z _ 0 &:= \bs{0} \\ z _ t &:= \gamma \lambda z _ {t - 1} + \nabla \hat{v}(S _ t, \bs{w} _ t) \end{align}

かつ、1ステップTD誤差

\displaystyle \begin{align} \delta _ t := R _ {t+1} + \gamma \hat{v}(S _ {t+1}, \bs{w} _ t) - \hat{v}(S _ t, \bs{w} _ t) \end{align}

を考えたときに、更新が以下のようになる。

\displaystyle \begin{align} \Delta ^ B _ t := \alpha \delta _ t \bs{z} _ t \end{align}

等価性の確認

前方観測と後方観測は一致するらしいが、上手く証明を見つけられなかった。時刻 t の更新量そのもので一致するとは思えないので(見ているものが違うため)、重みを固定したときの1エピソード分の更新量の和が一致するのではないか？

\displaystyle \begin{align} \sum _ t \Delta ^ F _ t = \sum _ t \Delta ^ B _ t \end{align}

以下、重みは固定として \bs{w} _ t などは時刻に依存せず \bs{w} とする。

前方観測の更新量 \Delta ^ {F} _ t := \alpha \left\lbrack G _ t ^ \lambda - \hat{v} (S _ t, \bs{w}) \right\rbrack \nabla \hat{v}(S _ t, \bs{w}) を変形していく。

一般に初項 a 、公比 r(\lt 1) 、項数 n の等比数列の和を S _ n とすると S _ n = \frac{a(r ^ n - 1)}{r - 1} なので、 \lambda \lt 1として

\displaystyle \begin{align} \sum _ {n = 1} ^ \infty \lambda ^ {n - 1} \hat{v}(S _ t, \bs{w}) = \frac{\hat{v}(S _ t, \bs{w})}{1 - \lambda} \end{align}

である。これを使うと以下のようにターゲットを \lambda 収益との差ではなく n ステップ収益との差で表現できる。

\displaystyle \begin{align} G _ t ^ \lambda - \hat{v}(S _ t, \bs{w}) &= (1 - \lambda) \left( \sum _ {n=1} ^ \infty \lambda ^ {n-1} G _ {t:t+n} \right) - \hat{v}(S _ t, \bs{w}) \\ &= (1 - \lambda)\sum _ {n=1} ^ \infty \lambda ^ {n - 1} \left\lbrack G _ {t:t+n} - \hat{v}(S _ t, \bs{w}) \right\rbrack \end{align}

次は G _ {t:t+n} - \hat{v}(S _ t, \bs{w}) に着目する。これを1ステップTD誤差 \delta _ t で表したい。

\displaystyle \begin{align} G _ {t:t+n} &= R _ {t+1} + \gamma R _ {t+2} + ... + \gamma ^ {n-1} R _ {t+n} + \gamma ^ n \hat{v}(S _ {t+n}, \bs{w})\\ \delta _ t &= R _ {t+1} + \gamma \hat{v}(S _ {t+1}, \bs{w}) - \hat{v}(S _ t, \bs{w}) \end{align}

の両式から G _ {t:t+n} を展開していくと、以下のように変形できることがわかる。

\displaystyle \begin{align} G_{t:t+n} &= R _ {t+1} + \gamma \hat{v}(S _ {t+1}, \bs{w}) - \hat{v}(S _ t, \bs{w}) \\ &+ \gamma R _ {t + 2} + \gamma ^ 2 \hat{v}(S _ {t + 2}, \bs{w}) - \gamma \hat{v}(S _ {t+1}, \bs{w}) \\ &+ \gamma^2 R _ {t + 3} + \gamma ^ 3 \hat{v}(S _ {t + 3}, \bs{w}) - \gamma ^ 2 \hat{v}(S _ {t + 2}, \bs{w}) \\ &\dots \\ &+ \gamma ^ {n - 1} R _ {t + n} + \gamma ^ {n} \hat{v} (S _ {t + n}, \bs{w}) - \gamma ^ {n - 1} \hat{v}(S _ {t + n - 1}, \bs{w}) \\ &+ \gamma ^ n \hat{v}(S _ {t+n}, \bs{w}) \, (G_{t:t+n}にもともとある項)\\ &+\hat{v}(S _ t, \bs{w}) \, (先頭の消えないものを打ち消す項)\\ &-\gamma ^ {n} \hat{v}(S _ {t + n}, \bs{w}) \, (末尾の消えないものを打ち消す項)\\ &= \left(\sum _ {k = t} ^ {t + n - 1} \gamma ^ {k - t} \delta _ k \right) + \hat{v}(S _ t, \bs{w}) \end{align}

よって

\displaystyle \begin{align} \Delta ^ F _ t &= \alpha \left\lbrack G _ t ^ \lambda - \hat{v} (S _ t, \bs{w}) \right\rbrack \nabla \hat{v}(S _ t, \bs{w}) \\ &= \alpha (1 - \lambda) \sum _ {n=1} ^ \infty \lambda ^ {n - 1} \left\lbrack G _ {t:t+n} - \hat{v}(S _ t, \bs{w}) \right\rbrack \nabla \hat{v}(S _ t, \bs{w}) \\ &= \alpha (1 - \lambda) \nabla \hat{v}(S _ t, \bs{w}) \sum _ {n=1} ^ \infty \lambda ^ {n - 1} \left\lbrack \sum _ {k = t} ^ {t + n - 1} \gamma ^ {k - t} \delta _ k \right\rbrack \\ &= \alpha (1 - \lambda) \nabla \hat{v}(S _ t, \bs{w}) \sum _ {k=t} ^ \infty \gamma ^ {k-t} \delta _ k \sum _ {n = k - t + 1} ^ \infty \lambda ^ {n - 1} \\ &= \alpha (1 - \lambda) \nabla \hat{v}(S _ t, \bs{w}) \sum _ {k=t} ^ \infty \gamma ^ {k-t} \delta _ k \frac{\lambda ^ {k-t}}{1 - \lambda} \\ &= \alpha \nabla \hat{v}(S _ t, \bs{w}) \sum _ {k=t} ^ \infty \gamma ^ {k-t} \delta _ k \lambda ^ {k-t} \\ &= \alpha \nabla \hat{v}(S _ t, \bs{w}) \sum _ {k=t} ^ \infty (\gamma \lambda) ^ {k-t} \delta _ k \\ \end{align}

であり、

\displaystyle \begin{align} \sum _ t \Delta ^ F _ t &= \sum _ t \alpha \nabla \hat{v}(S _ t, \bs{w}) \sum _ {k=t} ^ \infty (\gamma \lambda) ^ {k-t} \delta _ k \\ &= \sum _ k \alpha \delta _ k \sum _ {t=0} ^ k (\gamma \lambda) ^ {k-t} \nabla \hat{v}(S _ t, \bs{w}) \\ &= \sum _ k \alpha \delta _ k \sum _ {m=0} ^ k (\gamma \lambda) ^ m \nabla \hat{v}(S _ {k-m}, \bs{w}) \\ &= \sum _ k \alpha \delta _ k \bs{z} _ k \\ &= \sum _ k \Delta _ k ^ B \\ \end{align}

よって一致した。