動的計画法を使った計画 - Google DeepMind の David Silver 氏による強化学習コース 講義3

Posted on 2018-09-03(月) in Reinforcement Learning

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

  • はじめに

    • 動的計画法
      • 「動的」: 逐次的、時間
      • 「計画」≒ 方策
    • 動的計画法がいつ使えるか
      • 最適なサブ構造に分解し、そこから最適解が求められる場合
        • 例: グラフの最短経路問題
      • サブ問題がお互いに関係しており、何回も現れる場合 → キャッシュできる
      • MDPはこの両方を満たす
        • ベルマン方程式
        • 問題の再帰的な分解
      • スケジュール
      • 文字列アルゴリズム
      • グラフアルゴリズム
      • グラフィカルアルゴリズム
      • 生物情報学
  • 動的計画法を使った計画

    • MDP の情報が全て分かっている前提
    • 予測: MDP と方策 \( \pi \) が分かっている時に、価値関数 \( v_\pi \) を求める
    • 操作: MDP が分かっている時に、最適方策 \( \pi_* \) を求める
  • 方策反復

    • MDP を解くための仕組みの一つ
    • 方策 \( \pi \) を評価する
    • ベルマン方程式を逆向きに繰り返し適用
    • 任意の \( v_1 \) からスタート。ベルマン方程式を適用し、\( v_2 \) を得る。
    • \( v_{k+1}(s) \) を計算するためには
      • 1ステップ先読みする。\( v_{k+1}(s) = \sum_{a \in A} \pi(a|s)( R^a_s + \gamma \sum_{s' \in S} P^a_{ss'} v_k(s') ) \)
    • これを繰り返すと、\( v_* \) に収束する
  • 方策をどう改善するか

    • 方策 \( \pi \) が与えられた時、
      • まず、方策 \( \pi \) を評価し、\( v_\pi(s) \) を得る
      • \( v_\pi(s) \) に従い、貪欲に行動し、方策 \( \pi' \) を得る
      • 「格子世界」の例では、\( \pi' \) が最適方策 \( \pi_* \)
      • 一般的には、これを繰り返すと、最適方策に収束する
    • 決定的な方策 \( \pi \) からスタート
      • 貪欲に行動することで、この方策を改善できる。 \( \pi'(s) = \arg\max_{a \in A} q_\pi(s, a) \)
      • → 価値関数も改善する
    • この繰り返し的な改善がストップする時 → ベルマン最適方程式を満たす → 方策は最適である \( v_\pi(s) = v_*(s) \)
    • 方策評価が収束するまで繰り返す必要があるか? \( k \) 回繰り返せば十分。ただし \( k = 1 \) ではだめ。
  • 価値反復

    • MDP を解くためのもう一つの仕組み
    • 最適原則
      • 方策 \( \pi(a|s) \) は、以下の条件を満たす時、またその時に限って、最適価値関数 \( v_\pi(s) = v_*(s) \) を満たす。
        • 任意の状態 \( s' \) が \( s \) から到達可能
        • 状態 \( s' \) が、最適価値関数を満たす \( v_\pi(s') = v_*(s') \)
    • もし、部分問題に対して最適解が分かっている時、\( v_*(s') \)
      • 1ステップ先読みする: \( v_*(s) \leftarrow \max_{a \in A} R^a_s + \gamma \sum_{s' \in S} P^a_{ss'}v_*(s') \)
    • 最適方策 \( \pi \) を探す
      • \( v_1 \to v_2 \to ... \to v_* \)
      • \( v_{k+1}(s) \) から \( v_k(s') \) を更新
      • 方策反復とは違い、方策を明示的に使わない
  • まとめ

    • 予測 → ベルマン期待値方程式 - 反復方策評価
    • 操作 → ベルマン期待値方程式+貪欲的方策更新 - 方策反復
    • 操作 → ベルマン最適方程式 - 価値反復
  • 拡張

    • 非同期動的計画法
      • 他の状態の更新が終わるまで待たない。最適値に収束する
      • In-place 動的計画法 
        • 価値関数の表を直接書き換える
      • 優先度付き sweeping
        • どの状態を次に更新するか優先度をつける
      • リアルタイム 動的計画法
        • エージェントに関係のある状態だけ更新する
    • ベルマン方程式は、状態数が多い時に効率が悪い
      • サンプリング