【苦しみながら理解するReinforcement Learning】第8章 一般化と関数近似

状態あるいは状態行動対の1つに対して1つのエントリーが対応するようなテーブル形式の推定価値関数を扱ってきた。
しかし、実際には状態数と行動数が小さいタスクでの利用に限られる。
その理由は、単に大きなテーブルを核の王するためのメモリの問題だけでなく、テーブルを正確に埋め尽くすために必要な時間とデータ量の問題にある。

つまり一般化(generalization)をどう行うかが問題の中心となる。
状態空間中の限定された部分集合での経験を、うまく一般化してより広い状態空間の部分集合鬼対する良い近似を作り出したい。

強化学習のタスクは同じ状態での同一の経験を得ることは、ほとんどあり得ない。
そのため、何かを学習するための唯一の手段は、以前に経験した状態から、まだ経験していない状態へと一般化する手法になる。

これは殆どの場合、強化学習手法を既存の一般化手法と組み合わせるだけで良い。
ここでは、一般化手法は関数近似(function approximation)と呼ばれ、目標関数(例えば価値関数)から実例を取り出し、そこから関数全体の近似を作り出すように一般化を試みる。

関数近似による価値予測

この章では時刻tの価値関数V_tを、テーブルではなく、θ_t^→をパラメータベクトルとするパラメータ関数の形で新しく表現する。
これは価値関数V_tがθ_t^→に完全に依存し、その変化がθ_t^→の時間ステップでの変化に依存することを意味する。

一般にパラメータ数(θ_t^→の要素数)は状態数に比べてはるかに小さく、パラメータを1つ変更することで、多くの状態の推定値が変更される。
したがって、ある状態がバックアップを受ける場合、その状態からの一般化によって、他の多くの状態の価値がその変化量の影響を受けることになる。

sをバックアップを受ける状態とし、vをバックアップされる価値とする。
1回のバックアップをs->vという記法で表す。

$$ DPバックアップ:s -> E_{\pi} {r_{t+1} + \gamma V_t (s_{t+1}) | s_t = s } $$

$$ モンテカルロ・バックアップ:s_t -> R_t $$

$$ TD(0)バックアップ:s_t -> r_{t+1} + \gamma V_t (s_{t+1} ) $$

$$ 一般的なTD(λ)バックアップ:s_t -> R_t^λ $$

DPは任意のバックアップを受けるが、他の方法は経験中に遭遇した状態s_tのみがバックアップを受ける。

sの推定価値をvに向かってわずかに変更するという簡単な方法を用いていたが、ここでは関数近似手法を導入してバックアップを実現する方法を考える。
関数近似手法では、近似しようとする関数の目標入出力動作の実例を入力する。
そこで各バックアップのs->vを訓練例として渡すことで、関数近似手法おを価値予測として利用し、生成された近似関数を推定価値関数として扱う。

強化学習に向いている関数近似手法は大きく2つある。

  1. 漸進的にデータを獲得して効率的に学習できる方法
  2. 非定常目標関数(時間と共に変化する目標関数; nonstationary target function)を扱う関数近似手法が使える方法

関数近似手法を評価する適切な性能尺度は、入力の分布P上の平均二乗誤差(MSE)を最小化するように動作する。

$$ MSE( \vec{θ}t) = \sum{s \in S } P(s) [V^{\pi} (s) – V_t (s) ]^2 $$

Pは異なる状態の誤差を重み付けするような分布を表す。

ある状態分布上での誤差を最小化するためには、同じ分布から取り出した実例を用いて関数近似器を訓練することが合理的である。
例えば、状態集合全体で均一な誤差レベルを維持したい場合、DP方の完全スイープ操作などのように、状態集合全体に一様に分布するバックアップを用いて訓練することが合理的である。

経験によって遭遇する状態の頻度を表す分布はバックアップの分布に相当し方策オン型分布(on-policy distribution)と呼ぶ。
方策オン型分布で誤差を最小化するには、方策に従って実際に生じた状態のみに関数近似の処理を集中させ、生じない状態は扱わないようにすれば良い。
方策オン型分布は他の分布よりも顕著な収束結果が得られる。

MSEの意味での理想目標は大域最適解(global optimum)、つまり全ての可能な\vec{θ}に対してMSE(\vec{θ^}) < MSE(\vec{θ}) となるようなパラメータ・ベクトル\vec{θ^}を見つけることである。
複雑な関数近似器は、代わりに局所最適解(local optimum)のパラメータ・ベクトル\vec{θ^*}へ収束するように動作する。

最急降下法

最急降下法は、あらゆる関数近似手法でもっとも広く使われている手法で、特に強化学習に適している。
パラメータ・ベクトルは限られた個数の実数値の要素をもつ列ベクトル

$$ \vec{θ_t} = (θ_t(1), θ_t(2), …, θ_t(n))^T $$

で表現され、V_t(s)はすべてのs∈Sに対して連続で微分可能な\vec{θ_t}の関数を表す。

最急降下法では、実例を得る度に、それに対する誤差をもっとも減少させる方向にパラメータ・ベクトルを修正して、以上の戦略を実現している。

\begin{align}
\vec{θ_{t+1}} & = \vec{θ_t} – \frac{1}{2} \alpha \nabla \vec{θ_t} [V^{\pi} (s_t) – V_t (s_t) ]^2
& = \vec{θ_t} – \alpha [V^{\pi} (s_t) – V_t (s_t) ] \nabla \vec{θ_t}
\end{align}

V_t(s):すべてのs∈Sに対して連続で微分可能な\vec(θ_t)の値。
V^π(s_t):stに対して正確で誤りのない価値
α:正のステップサイズ・パラメータ

V^π(s_t)は微分できないから消えて、V_t(s)は微分可能だから残って且つ、1/2を消したのか…?

任意の関数fは以下の通り

$$ \nabla \vec{θ_t} f \vec{θ_t} = ( \frac{\partial f (\vec{θ_t})}{\partial \vec{θ_t} (1) }, \frac{\partial f (\vec{θ_t})}{\partial \vec{θ_t} (2) }, …, \frac{\partial f (\vec{θ_t})}{\partial \vec{θ_t} (n) } )^T $$

次に、t番目の訓練例 s_t -> v_t に対する目標出力v_tが真の価値V^π(s_t)ではなく、その近似である場合について。
v_tの例としてはV^π(s_t)にノイズが加わったものだが、置き換えると最急降下法の一般形が得られる。

$$ \vec{θ_{t+1}} = \vec{θ_t} – \alpha [ v_t – V_t (s_t) ] \nabla \vec{θ_t} $$

nステップTD収益や、その平均もv_tとして利用できる。
最急降下法を用いたTD(λ)で、λ収益v_t=R_t^λをV^π(s_t)に近似として用いると、次のような前方観測型の更新式が得られる。

$$ \vec{θ_{t+1}} = \vec{θ_t} – \alpha [ R_t^λ – V_t (s_t) ] \nabla \vec{θ_t} $$

残念ながらλ<1に対してR_t^λはV^π(s_t)の偏りのない推定値にはならない。
しかしこのようなブートストラップ手法はきわめて効果的で、後に述べるように特別な場合に対し、これとは異なる種類の性能保証を得られている。

最急降下法の後方観測的見方は次式。

$$ \vec{θ_{t+1}} = \vec{θ_t} + \alpha \delta_t \vec{e_t} $$

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

$$ \vec{e_t} = \gamma λ \vec{e_{t-1}} + \nabla \vec{θt} V_t (s{t+1}) $$

本書図8.1を参照。

勾配法に基づく関数近似の中で、強化学習に広く使われる方法は2種類ある。

  1. 誤差逆伝播法(error backpropagation)を用いた多層ニューラル・ネットワーク
  2. 線形形式

線形手法

最急効果関数近似の重要な例の1つは、近似関数V_tがパラメータ・ベクトル\vec{θ_t}の線形関数でアワラされる場合である。
この場合、各状態sに対して\vec{θ_t}の成分数と同じ数の特徴(feature)による列ベクトル

$$ \vec{\phi_s} = (\phi_s(1), \phi_s(2), … , \phi_s(n) )^T $$

が対応する。
近似状態価値観数は、用いる特徴に依存しない形で次式で表される。

$$ V_t (s) = \vec{θt^T} \vec{\phi_s} = \sum{t=1}^n θ_t (i) \phi_s (i) $$

この場合、近似価値関数は「パラメータに関して線形」、または単に「線形」であるという。
線形関数近似に対しては最急降下法を用いるのが自然で、近似価値観数の\vec{θ_t}に関する勾配は次のように表される。

$$ \nabla \vec{θ_t} V_t (s) = \vec{\phi_s} $$

線形学習手法は、理論的な麺だけでなく、データ量と計算量の両面においても、とても効果的な実用手法であるため、関心を集めている。

特徴jが存在したにときのみ、特徴iの価値が高いというような状況を、線形形式では表現できない。
そのため、特徴の値それぞれを連結した特徴を用いる必要がある。
この結合手法鬼ついて、以下で一般的な方法をいくつか検討してゆく。

粗いコード化

1-0値による特徴尾は、バイナリ特徴(binary feature)と呼ばれる。
オーバーラップするような特徴を使って状態を表現する方法は、荒いコード化(coarse coding)として知られている。
例がわかりやすく、本書を見てほしい。

タイルコーディング

タイルコーディング(tile coding)は、逐次型デジタル計算機での効果的なオンライン学習に特に適した荒いコード化手法の1つである。

各タイリングに特徴が1つ存在するので、特徴総数は常にタイリングの数に等しいことになる。
これにより、ステップサイズ・パラメータαが直感的に、簡単に設定できる。

一般化や目標出力の確率的変動を考慮して、ゆっくり変化させるように設計する。
例えば、α=1/10m(mはタイル数)として、1回の更新で目標値の10分の1だけ変化させる。

また、次元の呪いを解決する手段としてハッシュ法が用いられる。

動径基底関数

動径基底関数(Radial basis function; RDF)は、粗いコード化を連続値特徴に一般化する自然な方法である。
この方法は0と1に限らず[0, 1]区間内の任意の値を特徴として利用できる。
典型的なRBF特徴iは、(つりがね形の)ガウス応答Φ_s(i)を持つ。

$$ \phi_s (i) = exp ( \frac{||s-c_i||^2}{2\sigma_i^2}) $$

Kanervaコーディング

高次元のタスクでも実用的なものいくつかあり、特に、存在特徴のリストを用いて状態を表現し、その特徴を線形に写像する方法は、大きなタスクにも十分に拡張できる。

次元数と複雑さは別のこと。
そのため、あるタスクに対して、例えば新しいセンサーや新しい特徴などを加えることで、次元をいくつか追加したとしても、使われる近似の複雑さが同じなら、結果はほとんど変わらない。
もし、追加した次元によって目標関数が簡単に表現できるのなら、次元の追加は一層の助けになる。

この考えに合う簡単なアプローチの1つは、特定のプロトタイプ状態群(proto-type states)と一致するバイナリ特徴群を選択するもので、Kanervaコーディング(Kanerva coding)と呼ばれている。

関数近似を用いた制御

関数近似を用いた予測手法を、GPI的な方法で制御手法へと拡張する。
まず、状態価値予測手法を、行動価値予測手法へと拡張し、その後、方策改善、および行動選択手法を組み合わせる。

$$ \vec θ_{t+1} = \vec{θ_t} + \alpha [ v_t – Q_t (s_t, a_t )] \nabla \vec{θ_t} Q_t(s_t, a_t) $$

TD(λ)と同様な、行動価値手法に対する後方観測的な見方は次式のようになる。

$$ \vec θ_{t+1} = \vec{θ_t} \alpha \delta_t \vec{e_t} $$

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

$$ e_t = \gamma λ \vec{e_{t+1}} + \nabla \vec{θ_t}Q_t ( s_t, a_t) $$

  • 方策オン型制御手法の例(Sansa(λ))

本書図8.8を参照。

  • 方策オフ型制御手法の例(WatkinsのQ(λ))

本書図8.9を参照。

上で議論してきた手法は、すべて累積適格度トレースを用いている。

方策オフ型ブートストラップ

ブートストラップは、他の予測価値に基づいて、ある予測価値を更新することを意味する。
TD法はDP法と同様にブートストラップを行うが、モンテカルロ法では行われない。

ブートストラップ手法への関数近似の導入は、非ブートストラップ手法よりかなり困難である。

ブートストラップを行うべきか

なぜブートストラップ手法にこだわるのか?
非ブートストラップ手法は、関数近似と組み合わせた場合に信頼性が高く、またブートストラップ手法よりも幅広い対象に適用できる。
これにも関わらず、実際にはブートストラップ手法が使われる場合がほとんどである。

経験的比較では、ブートストラップ手法は非ブートストラップ手法より、はるかに性能が良い。

その他

式8.2

これどうやって展開してるんですか?
ベクトル微分とかなんでしょうか?
正確にはわからず…

\begin{align}
\vec{θ_{t+1}} & = \vec{θ_t} – \frac{1}{2} \alpha \nabla \vec{θ_t} [V^{\pi} (s_t) – V_t (s_t) ]^2
& = \vec{θ_t} – \alpha [V^{\pi} (s_t) – V_t (s_t) ] \nabla \vec{θ_t}
\end{align}

コメントを残す

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