価値関数の近似 - Google DeepMind の David Silver 氏による強化学習コース 講義6

Posted on 2018-09-06(木) in Reinforcement Learning

「無料でアクセスできる最高の強化学習のコース」と名高い、Google DeepMind / University College London の David Silver 氏による強化学習のコース。こちらのページから、全ての講義スライドと講義ビデオが見られる。以下は、講義6 のメモです。

  • はじめに

    • 大規模な強化学習
      • バックギャモン: \( 10^{20} \) 個の状態
      • 囲碁: \( 10^{170} \) 個の状態
      • ヘリコプター: 連続的な状態 → もはや参照テーブルを作ることができない
    • 価値 \( V(s) \) もしくは \( Q(s, a) \)
      • テーブルが巨大になってメモリに載らない、もしくは載ったとしてもスパースすぎて学習が遅い
    • 関数近似
      • \( v_\pi(s) \) を \( \widehat{v} (s, {\bf w})\)で近似
      • \( q_\pi(s, a) \) を \( \widehat{q} (s, a, {\bf w}) \) で近似
    • 3つのタイプの関数近似
      • s → 関数 → \( \widehat{v} (s, {\bf w})\)
      • s, a → 関数 → \( \widehat{q} (s, a, {\bf w}) \)
      • s → 関数 → \( \widehat{q} (s, a_1, {\bf w}), ..., \widehat{q} (s, a_m, {\bf w}) \)
    • 関数の近似法
      • 特徴量の線形和 → 微分可能
      • ニューラル・ネットワーク → 微分可能
      • 決定木
      • 近傍法
      • フーリエ・ウェーブレット基底
    • 非定常、iid でない入力
  • 逐次的手法

    • 勾配降下法
      • \( J(w) \) パラメータ \( w \) の微分可能な関数
      • J の勾配 \( \nabla_w J(w) = (\frac{\partial J(w)}{\partial w_1}, .. )^T \)
      • \( \Delta w \) を、\( \nabla_w J(w) \) に比例して更新
    • 確率的勾配降下法による価値関数の近似
      • 価値関数の真の値(オラクル)が分かったとしたら、目的関数 (平均二乗誤差)は、
        • \( J(w) = E_\pi [ (v_\pi(S) - \widehat{v}(S, w))^2 ] \)
      • 期待値ではなく、インスタンス1つづつ更新する
        • \( \Delta W = \alpha(v_\pi(S) - \widehat{v}(S, w)) \nabla_w \widehat{v}(S, w) \)
      • 特殊な場合:関数が特徴量の線形和の場合
        • 目的関数は、パラメータ w の二次関数
        • 確率的勾配降下法によって、大域解が求まる
        • テーブル参照は、線形価値関数近似の特殊な場合
    • 逐次的予測アルゴリズム
      • オラクル \( v_\pi(s) \) の代わりに、ターゲット(予測値)を使う → ターゲットを使って教師あり学習をするのと同様
        • MC: \( G_t \)
        • TD(0): \( R_{t+1} + \gamma \widehat{v}(S_{t+1}, w) \)
        • TD(λ): \( G^\lambda_t \)
      • MC
        • \( (S_1, G_1), (S_2, G_2), ... \) を「訓練データ」として使うのと同等
        • 非線形価値関数を使っている時でも、(局所)最小解に収束する
      • TD(0)
        • \( R_{t+1} + \gamma \widehat{v}(S_{t+1}, w) \) は、偏りのあるサンプル
        • 線形TD(0) は、大域解(の近く)に収束する
      • TD(λ)
        • \( (S_1, G^\lambda_1), (S_2, G^\lambda_2), ... \) を訓練データとして使うのと同等
        • 前向き観点: \( G^\lambda_t \) を使う
        • 後向き観点
          • Eligibility Trace: \( \gamma \lambda E_{t-1} + x(S_t) \) → 各特徴量について計算
          • \( \Delta_w = \alpha \delta_t E_t \)
    • 価値関数近似による制御
      • 価値関数近似 \( \widehat{q}(s, a, w) \) + ε-貪欲方策
      • 例: ニューラル・ネットワークにより \( q \) を近似: \( \widehat{q}(S, A, w) = q_\pi(S, A) \)
      • 上と同じ議論:真の値(オラクル)を仮定し、それとの平均二乗誤差
      • 素性は、状態 S と行動 A の関数になる
      • MC, TD(0), TD(λ) を、上と同様に定義できる
    • ブートストラップ法を使うべきか?どう λ を設定するか?
      • 多くの問題において、\( \lambda = 0.9 \) あたりで性能が最高になる
    • 収束
      • 評価
        • TD は、方策オフ型の場合、モデルが線形でも非線形でも、収束しない(発散・振動)する場合がある
        • Gradient TD は、この問題を解決
      • 制御
        • 最適値に近づくにつれて、「ぶれ」(=最適値に近づいたり遠ざかったりする)の問題が起こる
        • 非線形では収束が保証されない
  • バッチ手法

    • 勾配降下法は、サンプル効率的ではない
    • 最小二乗予測
      • 経験 \( D = { (s_1, v_1^\pi), ..., (s_T, V_T^\pi) } \)
      • \( LS(w) = E_D[(v^\pi - \widehat{v}(s, w)^2] \)
    • 経験再生を使った確率的勾配降下法
      • 経験 D から \( (s, v^\pi) \) をサンプリング、確率的勾配降下法を適用
      • \( LS(w) \) に収束
    • 経験再生を使った DQN (Deep Q-Networks)
      • 行動は、ε貪欲方策に従う
      • 遷移 \( s_t, a_t, r_{t+1}, s_{t+1} \) を、全てメモリー D に保存しておく
      • D から、ミニバッチ (64個のインスタンス) を取り出す
      • Q-Learning ターゲットをこのミニバッチを使って計算
      • ターゲットとQ-network の最小二乗誤差を最小化
      • 安定化のためのテクニック
        • 経験再生を使うと、インスタンス間の相関が減る
        • 2つのネットワークを使う。片方をフリーズさせ、最新の予測を使うかわりにそのネットワークを使う
    • 線形最小二乗誤差予測
      • 線形モデルを使えば、閉じた形で解が求まる → 効率的
      • MC, TD, TD(λ) と組み合わせて、LSMC, LSTD, LSTD(λ) を得る
      • TD に比べて、収束性が向上
    • 線形最小二乗誤差制御 (LSPI)
      • 収束性が向上