【苦しみながら理解するReinforcement Learning】第7章 適格度トレース

さぁ、遂に第3部来ました!
第3部では、第2部で紹介された3種類(動的計画法、モンテカルロ法、TD法)の基本的な解法群の統一された見方を示す。

最初は、適格度トレース。このメカニズムはモンテカルロ法とTD法とを統合したものである。
次に、関数近似を取り入れ、状態と行動間の関係の一般化(generalization)を可能とする。
最後に、動的計画法とヒューリスティック探索の長所を取り入れるために環境モデルを再び導入する。

的確度トレース(eligibility trace)は強化学習の基本的なメカニズムの1つである。
TD法を適格度トレースによって補強すると、モンテカルロ法を一方の端、1ステップTD法を他方の端とした範囲にまたがる一連の手法が作り出される。
これらを両極端として、中間にはさらに良い手法を見出すことができる。

適格度トレースはさらに理論的には、前方観測的な見方(forward view)と呼ばれ、技術的な見方は後方観測的な見方(backward view)と呼ばれる。
前方観測的な見方は適格度トレースを用いた酒保王で何が計算されるのかを理解するのに最も有用である。
後方観測的な見方はアルゴリズムそれ自体の直感を発展させるのに適している。

これまで同様、最初に予測問題を、次に制御問題を考える。

nステップTD予測

モンテカルロ法とTD手法との中間に位置する手法はどのような空間を持つのであろうか?

モンテカルロ法では、当該状態から終端エピソードまで、観測された報酬の全ての系列に基づいてバックアップを遂行する。
他方、単純なTD手法のバックアップでは、1つ次の報酬だけに基づく。
したがって、中間的な手法の1つは、中間的な個数(1個よりも多く、終了までの全ての報酬の個数よりも少ない)の報酬に基づいてバックアップを遂行することになる。

V^πに対する一連のnステップ・バックアップ(n-step backup)を図式化したもが以下の通りである。

図7.1

nステップに時間的差分を拡張したものはnステップTD法(n-step TD method)と呼ばれる。

状態価値の更新方法は2つある。

  1. オンライン更新(on-line updating):推定値の増分が計算され次第、エピソード中で更新が行われる。
  2. オフライン更新(off-line updating):増分は累積されていくだけで、エピソードの終端に至るまで価値推定の変更に使われることはない。

推定値の増分は以下の式で表される。
$$ \Delta V_t(s_t) = \alpha [R_t^{(n)} – V_t(s_t)] $$

nステップTD手法は実装には不都合があるため、実際上はめったに使われない。
nステップ収益を計算するためには、結果として得られる報酬と状態を観測するまでnステップ待つことを必要とする。

TD(λ)の前方観測的な見方

TD(λ)アルゴリズムは、nステップ・バックアップを平均化する方法の1つである。
この平均にはnステップ分のバックアップ全てが含まれており、その各々はλ^{n-1}(0≦λ≦1)に比例して重み付けされる。

結果として得られるバックアップは、λ収益(λ-return)と呼ばれる収益に対するものとなり、次のように定義される。

$$ R_t^{\lambda} = (1 – \lambda ) \sum_{n=1}^∞ \lambda^{n-1} R_t^{(n)} $$

λ収益アルゴリズム(λ-return algorithm)は、λ収益を用いてバックアップを実行するアルゴリズムである。各時間ステップtで、そのときに発生する状態価値に対する増分を次のように計算する。

$$ \Delta V_t(s_t) = alpha [R_t^{\lambda} – V_t(s) ]

ある状態から前方を眺めて更新を行った後、次の状態に移動し、以前の状態を参照する必要はない。(前方観測的見方)

図7.5

TD(λ)の後方観測的な見方

後方観測的な見方は概念的にも計算上でも単純であるこという理由から有用である。

TD(λ)の後方観測的見方においては、各状態に関連する付加的なメモリ変数が存在し、それが適格度トレース(eligibility trace)である。
各ステップにおいて、この適格度トレース(e_t(s))は、全ての状態に対してΓλだけ減衰し、そのステップで訪問された1個の状態の適格度トレースは、全てのsに対して次式のように1だけ増加する。

Γ:割引率
λ:トレース減衰パラメータ(trace-decay parameter)

この種類の適格度トレースは、累積トレース(accumulationg trace)と呼ばれる。
そう呼ばれる理由は、ある状態が訪問されると累積され、その状態が訪問されないと減衰するからである。

図7.7

どの時点でも、適格度トレースでは最近訪問された状態が記録される。
ここで「最近」はΓλで定義され、適格度トレースは強化事象が発生した時に、学習上の変化を受けることが適格であることの度合いを示している。

対象としている強化事象は、時々刻々の1ステップTD誤差である。

$$ \delta_t = r_{t+1} + \gamma V_t ( s_{t+1} ) – V_t (s_t) $$

全体的なTD誤差信号は、最近訪問した非ゼロトレース信号(恐らく非ゼロなe_t)を持つ全ての状態に対して、比例分配的な更新を生じさせる。

$$ \Delta_t \alpha \delta_t e_t (s) $$

TD(λ)の後方観測は、時間をさかのぼる向きに行われる。
自分たちが状態の流れの上に乗ってTD誤差を計算し、以前に訪問した状態の方に向かってその誤差の値を叫ぶことを想像しよう。

図7.8

もしλ=1であるなら、以前に訪問した状態群に与えられる信用は、1ステップあたりΓの割合で低下する。
これはモンテカルロ法を実行するために必要なことをしているだけであることがわかる。

TD(1)は、これまでに示したものよりも一般的な形でモンテカルロ法を実装する方法で、適用範囲もかなり広がる。
TD(1)はオンラインで漸進的な実装が可能である。
モンテカルロ法のようにエピソードが終わるまで何も学習しないということがなくなる。

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

上記において技術的であると定義されたオフラインTD(λ)の重み更新、オフラインλ収益アルゴリズムの重み更新とが同じであることを示す。
TD(λ)の前方観測的(理論的)な見方と、後方観測的(技法的)な見方を比べる。

$$ \sum_{t=0}^{T-1} \Delta V_t^{TD} (s) = \sum_{t=0}^{T-1} \Delta V_t^λ (s_t) I_{ss_t} $$

I_{ss_t}は一致関数(identity-indicator function)であり、s = s_tならばその値は1に等しく、それ以外では0である。
オフラインの場合には、以下のようになる。

$$ \sum_{t=0}^{T-1} \Delta V_t^{λ} (s_t) I_{ss_t} = \sum_{t=0}^{T-1} \alpha I_{ss_t} \sum_{k=t}^{T-1} (λ\gamma)^{k-t} \delta_k $$

Sarsa(λ)

予測だけではなく制御においても適格度トレースを使うにはどうすればよいだろうか。
これまで同様、よく出てくる考え方は状態価値V_t(s)ではなく、行動価値Q_t(s, a)を学習することである。

どのようにして適格度トレースが、直接的なやり方でSarsaと組み合わされて方策オン型TD制御手法を作り上げるかを示す。
Sarsa(λ)の考え方は、TD(λ)予測手法を状態ではなく、状態行動対に対して適用することにある。

各状態に対するトレースではなく、状態行動対に対するトレースを行うことが必要となる。

$$ Q_{t+1} (s, a) = Q_t(s, a) + \alpha \delta_t e_t (s, a) $$

$$ \delta_t = r_{t+1} + \gamma Q_t(s_{t+1}, a_{t+1}) – Q_t(s_t, a_t) $$

式7.10参照。
※ wordpressのlatexで複数行ができない…

図7.11

Q(λ)

適格度トレースとQ学習の組み合わせた異なる2つの手法がある。
それは、WatkinsのQ(λ)とPengのQ(λ)。

Watkinsの!(λ)は、行動価値の知識に基づき、最初の探査後に取られた行動1個を見ている。
オフライン更新を仮定したバックアップ線図は次の通り。

図7.13

196ページ式参照

探査的行動が取られる度にトレースを切り離すことで、適格度トレースを使うことの利点がかなり失われる。
PengのQ(λ)は、WatkinsのQ(λ)の代わりに、この問題を解決することを意図したQ(λ)である。
PengのQ(λ)は、Sarsa(λ)とWatkinsのQ(λ)の混合型と考えることができる。

PengのQ(λ)は、Q学習と異なり、探索的行動とグリーディ行動との間の区別はない。
各要素バックアップは広いステップ数の行動にまたがっているが、最後の部分で行動群に関する最大化を行って完成する。
要素バックアップは方策オン型でも、方策オフ型でもない。

一方で、PengのQ(λ)は、WatkinsのQ(λ)ほど単純に実装することができない。

アクター・クリティック手法における適格度トレース

アクター・クリティック手法のクリティックの部分は単にV^πに関する方策オン型学習である。
これを行うために、TD(λ)アルゴリズムを使うことが出来、各状態に対して1この適格度トレースを用いる。

アクター部分では、各状態行動対に対して適格度トレースを用いることが必要になる。
したがって、2組(各状態と各状態行動対)のトレースを使う必要がある。

式7.12参照

入替え更新トレース

入替え更新トレースを(replacing trace)を用いることによって、性能が改善されうることがある。

最初の訪問によるトレースが完全にゼロに減衰する前に再訪問されたと仮定する。
累積トレースでは、再訪問によってトレースはさらに増加し、1よりも大きな値に向かうが、入替え更新ではトレースは1に再設定される。

このアルゴリズムを入替え更新トレース手法と呼ぶ。
累積トレースとの違いはわずかだが、学習速度はかなり改善される。

ここの例題がわかりやすい。

実装上の問題

単純化実装ではすべての状態(あるいは状態行動対)において、あらゆる時間ステップで価値推定と適格度トレースの両者を更新することが要求される。

幸いなことに、ほとんどすべての状態の適格度トレースは常にゼロに近い値であり、最近訪問された状態群のみが0よりかなり大きなトレース値を持つ。
他の状態群における更新は本質的には影響を及ぼさないので、これら少数の状態のみが更新を要する。

λ可変更新

λの値をステップごとに変化させることを許せば、これまでに記述してきた内容からさらにλ収益を一般化することができる。
この場合、トレースの更新を次のようにする。

205ページ式参照。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です