shugo's kitchen

コンピュータサイエンスを美味しく調理していきたい

トップ > 強化学習 > 強化学習 Sutton本8章 一般化と関数近似

強化学習 Sutton本8章 一般化と関数近似

強化学習 読書メモ

[tex: ]

Sutton本の第8章の内容のメモです

関数近似の背景

  • これまでの章ではテーブル形式の推定価値関数を用いてきた
    • それぞれの状態(行動対)について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) $$

  • 時刻$t$における状態$s_t$に対して、目標出力$v_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な推定値とはならず、収束する保証はない
適格度トレース
  • TD($\lambda$)の後方観測的な更新式

$$ \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)$をどれだけ更新するか

  • とりあえずこれで最適化手法は手に入った。では具体的な関数形はどうするか？

線形手法

  • 各状態において特徴量ベクトル$\vec{\phi_{s}}$とパラメータの内積を取る。線形回帰と一緒(p217(8.8式))
  • 当然線形モデルでは表せない状況はいっぱいある → 色々と工夫があるらしい
    • 円による荒いコード化
    • タイルコーディング
    • 動径基底関数(粗いコード化を連続値に一般化)
      • ただし以上の三つは目的関数の複雑さではなく問題の次元に左右される
    • Kanervaコーディング
      • 特徴量をバイナリ空間で表現(バイナリ特徴)し、その距離を比較
        • k近傍法的な？

関数近似を用いた制御

  • ここまで状態価値関数についてやったことを行動価値予測に拡張する
  • 今まで通り$P \to Q$, $s \to (s,a)$とするだけ！
  • 図8.8, 8.9について
    • 特徴集合$F_a$は今までの文脈からいくと全ての$(s,a)$について同じものであるはず
      • 状況によって特徴量が変わってくるタスクを考慮している？
    • 前回の復習
      • Sarsaは方策オンで、εグリーディに従って行動していく
      • Q学習は方策オフで、実際に取る行動はSarsaと同じだが、更新に用いるのはgreedyな行動

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

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

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

  • 上述のように非ブートストラップ手法は、関数近似と組み合わせた場合に信頼性が高い
  • ただ、ブートストラップの方がこれまた経験的にはるかに性能がいいらしい(p240図8.15)
    • より高速に学習するとのこと

まとめ

  • これまでのテーブル型の価値関数を軽くする方法としての関数近似
  • 関数形としてはナウでヤングなNNの他に線形手法なるものがある
    • 粗いコード化や基底関数といった工夫がある
  • ブートストラップは収束の保証はないが、経験的に強い

参考

線形手法についての記事 https://qiita.com/triwave33/items/78780ec37babf154137d