More than 5 years have passed since last update.

Sutton本第8章一般化と関数近似まとめ

Last updated at 2019-08-23Posted at 2019-08-23

##関数近似の背景

これまでの章ではテーブル形式の推定価値関数を用いてきた
- それぞれの状態(行動対)について1つの推定値を持っておかねばならない
- 表を保持するためのメモリや、表を埋め尽くすための計算量が膨れ上がる
限定された部分状態集合での経験をうまく一般化することで、より広い状態空間に対する良い近似を作りたい
- 推定価値関数の関数近似(教師あり学習)

##関数近似による価値予測

価値関数$V_t$をパラメータベクトル$\vec{\theta_t}$に完全に依存するものとして定義し直す
- $\vec{\theta_t}$だけを計算して保持すれば良いので、計算量、メモリの節約
- ただし当然ながら$len(\vec{\theta_t}) \ll (状態数)$
$\vec{\theta_t}$の一つの要素パラメータをいじることが多くの推定値の変更を意味する

#####MSE

MSE(\vec{\theta_t}) = \sum_{s\in S}P(s)[V^{\pi}(s) - V_t(s)]^2

教師ありの回帰モデルと同様に平均二乗誤差(MSE)の最適化問題をといて$\vec{\theta_t}$を計算する
上述のように$V_t(s)$の自由度は状態数と比べて極めて少ない(希少資源)
- 全ての状態において誤差を0とすることは不可能
- 分布$P(s)$によりどの状態を犠牲にするかを決める(バックアップの分布)
- この$P$を方策$\pi$による$s$の訪問回数を用いて定めたのが方策オン型分布
  - $\pi$によって生じない状態は気にしない

##最急降下法

\vec{\theta_{t+1}} = \vec{\theta_{t}} + \alpha[v_t - V_t(s_t)]\nabla_{\vec{\theta_{t}}}V_t(s_t)

おなじみの更新式
$E[v_t] = V^{\pi}(s_t)$(真の価値)である場合$v_t$はunbiasedな推定値と呼び、この時$\vec{\theta_{t}}$を局所最適解へ収束させることができる
- 逆にTD($\lambda$)における$\lambda$収益$R^\lambda_t$やDP目標$r_{t+1}+\gamma V_t$のようなブートストラップ手法ではunbiasedな推定値とはならず、収束する保証はない

#####適格度トレース

\vec{\theta_{t+1}} = \vec{\theta_{t}} + \alpha\delta_t\vec{e_{t}}

$\delta_t$は目標値との差分に対応(p215(8.6))し、適格度ベクトル$\vec{e_{t}}$は(8.7)式のように更新される
前章では
- $e$は各状態$s$について定まる
- 状態$s$への最近の訪問が多いほど$e(s)$が大きくなる
- $e(s_t)$は$V(s_t)$をどれだけ更新するか
ここでは
- $e$は$\vec{\theta_{t}}$のそれぞれの要素$\theta_t(i)$について定まる
- 最近の$V(s)$の$\theta_t(i)$に対する勾配が大きいほど$e_t(i)$は大きくなる
- $e_t(i)$は$V_t(s)$のうちの$\theta_t(i)$をどれだけ更新するか
とりあえずこれで最適化手法は手に入った。では具体的な関数形はどうするか？
- 誤差逆伝播法を用いた多層NN
- 線形手法

##線形手法

##関数近似を用いた制御

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

ブートストラップ手法は方策オン型分布に対してしか収束性を示せない
- 方策オフ型(Q学習,DPなど)では推定方策に従って訪問される状態の分布と、実際にバックアップされる状態の分布が異なる
ただし、例えばQ学習などで挙動方策と推定方策が十分近い場合はきちんと収束してくれるという経験的事実はあるようだ

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

##まとめ

Sutton本 第8章 一般化と関数近似 まとめ