状態あるいは状態行動対の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の推定価値をｖに向かってわずかに変更するという簡単な方法を用いていましたが、ここでは関数近似手法を導入してバックアップを実現する方法を考えてみます。関数近似手法では近似しようとする関数の目標入出力動作の実例を入力します。そこで各バックアップのs->vを訓練例として渡すことで、関数近似手法を価値予測として利用し、生成された近似関数を推定価値関数として扱います。
強化学習に向いている関数近似手法は大きく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^π(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種類あります。
- 誤差逆伝播法(error backpropagation)を用いた多層ニューラル・ネットワーク
- 線形形式
線形手法
最急効果関数近似の重要な例の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法と同様にブートストラップを行いますがモンテカルロ法では行われません。ブートストラップ手法への関数近似の導入は、非ブートストラップ手法よりかなり困難です。
ブートストラップを行うべきか
なぜブートストラップ手法にこだわるのでしょうか？
非ブートストラップ手法は、関数近似と組み合わせた場合に信頼性が高く、またブートストラップ手法よりも幅広い対象に適用できます。これにも関わらず、実際にはブートストラップ手法が使われる場合がほとんどです。経験的比較では、ブートストラップ手法は非ブートストラップ手法より、はるかに性能が良いためです。