強化学習入門 - Google DeepMind の David Silver 氏による強化学習コース

Posted on 2018-09-01(土) in Reinforcement Learning

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

講義1: 強化学習入門

  • 教科書

    • An Introduction to Reinforcement Learning
      • 直感的, このコースで参照
    • Algorithms for Reinforcement Learning
      • 理論, 厳密
  • 強化学習とは

    • 様々な分野と関係
    • 工学、機械学習、神経科学(脳の報酬システムと関係)
    • 機械学習の3つの分類
      • 教師あり学習、教師なし学習、強化学習
  • 他の機械学習アルゴリズムとの違い

    • 教師の代わりに、報酬信号しかない
    • 報酬がすぐに得られるとは限らない
    • 時間の概念が重要。iid (独立同分布)データではない
    • エージェントが環境に影響を及ぼす→データも変わる
  • 強化学習の例

    • ヘリコプターの曲芸を学習
    • バックギャモンで世界チャンピオンに勝つ
    • 投資ポートフォリオの管理
    • 発電所の制御
    • 人間型ロボットを歩かせる
    • Atari の複数のゲームをプレイする
    • Q:強化学習アルゴリズムは、人間の反応時間に比べて速く操作ができるので有利ではないか? → A: 人間の反応時間に合わせてあるので、公平なはず
  • 強化学習問題

    • 報酬 \( R_t \) --> スカラー値のフィードバック信号。時刻 t においてどのぐらい「うまく行っているか」
    • 報酬の合計の期待値を最大化させるのが目的
    • 報酬に関する仮定:全てのゴールは、累積報酬の期待値を最大化させる問題に帰着できる
  • 継続的な意思決定

    • 目的:将来の報酬の合計を最大化させる行動を選択する
    • 貪欲的に行動するべきではない → 行動が長期にわかって効果を残す。報酬がすぐ得られるとは限らない。
  • エージェントと環境

    • エージェントが環境を観察 \( O_t \)
    • 行動 \( A_t \)
    • 報酬 \( R_t \)
  • 履歴と状態

    • 履歴 \( H_t = A_1, O_1, R_1, ..., A_t, O_t, R_t \)
    • 状態 \( S_t = f(H_t) \)
    • 環境状態 \( S^e_t \) → エージェントからは見えない
    • エージェント状態 \( S^a_t \)
    • マルコフ性: \( P[S_{t+1} | S_t] = P[S_{t+1} | S_1, ..., S_t] \)
      • 次の状態は、現在の状態だけに依存する
      • 現在の状態が分かれば、履歴は不要
      • 状態は、未来の十分統計量
      • ヘリコプターの例:現在の位置、速度、角度、各速度 etc. 位置だけではマルコフ性が成立しない
    • 完全に観察可能な環境
      • \( O_t = S^a_t = S^e_t \) → マルコフ決定過程 (Markov Decision Process; MDP)
    • 部分的に観察可能な環境
      • 部分観測マルコフ決定過程 (Partially Observable MDP; POMDP)
      • エージェント状態を、環境状態とは独立に構築する必要がある
        • 方法1: 状態に対する信念(確率分布)を維持する
        • 方法2: 前の状態と、現在の観察から、次の状態を予測する RNN を構築する
  • エージェント

    • 方策: エージェントがどのように意思決定するか
      • 状態 s から行動 a への関数
      • 決定的な方策: \( a = \pi(s) \)
      • 確率的な方策: \( \pi(a | s) = P[A = a | S = s]\)
    • 価値関数: それぞれの状態/行動がどのぐらい良いか
      • 将来の報酬に対する予測
      • 方策に依存
      • \( v_\pi(s) = E_\pi[R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + ... | S_t = s] \)
      • 時間による割引 \( \gamma \) → 遠い未来より近い未来の報酬を優先
    • モデル: エージェントによる環境の表現(「エージェントが環境がどういう仕組みで動いていると思っているか」)
      • 遷移モデル: 次の状態を予想する
      • 報酬モデル: 次の報酬を予想する
  • エージェントの分類

    • 価値ベース: 価値関数を使う
    • 方策ベース: 方策を使う
    • Actor Critic: 価値関数と方策の両方を使う
    • モデル無し: 価値関数・方策のどちらかもしくは両方、モデル無し
    • モデル有り: 価値関数・方策のどちらかもしくは両方、モデル有り
  • 学習とプランニング

    • 強化学習: 環境が未知の状態からスタート、エージェントが環境と相互作用し、方策を改善する
    • プランニング: 環境のモデルが与えられる、相互作用せずにモデルを使って計算、方策を改善する
  • 探索と搾取

    • 探索: 報酬をあきらめてでも、環境に関する情報を得る
    • 搾取: 既に知っている情報を使い、報酬を最大化する

講義2: マルコフ決定過程

  • マルコフ決定過程 (MDP)

    • 環境が完全に観察可能
    • 状態が、過程を完全に規定する
    • 多くの強化学習問題が、MDP として定式化可能
    • 部分観測マルコフ決定過程 (POMDP) も、MDP に変換可能
    • バンディットアルゴリズムも、状態が一つしかない MDP
  • マルコフ性

    • 次に何が起こるかは、今の状態だけに依存
    • Lecture 1 参照
    • 状態遷移確率 \( P_{ss'} = P[S_{t+1} = s' | S_t = s] \) 行列で表現可能
  • マルコフ過程

    • 状態列 \( S_1, S_2, ... \) がマルコフ性を満たすとき → マルコフ過程
  • マルコフ報酬過程 (Markov Reward Process; MRP)

    • R: 報酬関数 \( R_s = E[ R_{t+1} | S_t = s] \)
    • 利得 \( G_t = \sum_{k=0}^\infty \gamma^k R_{t+k+1} \)
    • なぜ割引率 \( \gamma \) を使うか → 数学的に便利。報酬が発散するのを防ぐ。未来に行くほど不確定。直近の未来の報酬を優先。
  • 価値関数

    • 状態 s に居るときの利得の期待値 \( v(s) = E[G_t | S_t = s] \)
  • ベルマン方程式

    • \( v(s) = E[R_{t+1} + \gamma v(S_{t+1}) | S_t = s] \)
    • 価値観数は、1) すぐ次の報酬、2) 次の状態の価値(+割り引き)の2つに分解できる
    • 行列表現: \( v = R + \gamma Pv \)
      • v: \( v = (v(1), ..., v(n))^T \)
      • R: \( R = (R(1), ..., R(n))^T \)
      • P: 状態 i から j への遷移確率行列
    • 解析的に解ける: \( v = (I - \gamma P)^{-1}R \)
      • 小さい MDP にしか適用できない。
  • マルコフ決定過程

    • マルコフ報酬過程 + 行動
    • 報酬 R: \( R^a_s = E[R_{t+1} | S_t = s, A_t = a] \)
    • 方策

      • \( \pi(a | s) = P[A_t = a | S_t = s] \) → エージェントの振る舞いを完全に規定
        • 時間 \( t \) に依存しない
      • MDP と方策 \( \pi \) が与えられたとき、状態系列 \( S_1, S_2, ... \) はマルコフ過程 → マルコフ決定過程を「平ら」にする
    • 価値関数

      • 状態価値関数は、方策 \( \pi \) に依存: \( v_\pi(s) = E_\pi[G_t | S_t = s] \)
      • 行動価値関数: \( q(s, a) = E[G_t | S_t = s, A_t = a] \)
      • ベルマン方程式を使って、直近の報酬と次の状態の価値に分解できる
        • 状態価値関数: \( v_\pi(s) = \sum_{a \in A} \pi(a|s) q_\pi(a, s) \)
        • 行動価値関数: \( q(s, a) = R^a_s + \gamma \sum_{s' \in S}P^a_{ss'} v_\pi(s') \)
      • ベルマン方程式の再帰適用: \( v_\pi(s) = \sum_{a \in A} \pi(a|s)( R^a_s + \gamma \sum_{s' \in S} P^a_{ss'} v_\pi(s') ) \)
      • \( q_\pi \) にも同じことができる
    • 最適状態価値関数
      • 全ての方策の中で、価値関数が最大となるもの: \( v_*(s) = \max_\pi v_\pi(s) \)
    • 最適行動価値関数
      • \( q_{*}(s, a) = \max_\pi q_\pi(s, a) \) → これがあれば、MDP は「解けた」(各状態において、どう行動すべきかが分かる)
    • 最適方策
      • ある方策が他の方策より良いとは? \( \pi \ge \pi' if v_\pi(s) \ge v_\pi'(s), \forall s \)
      • 定理: 他のあらゆる方策よりも良い最適方策 \( \pi_* \) が存在する。複数存在する場合もある
      • \( q_*(s, a) \) を最大化する行動を取ることで、最適方策が得られる
      • \( v_* \) と \( q_* \) についても、上記のベルマン方程式が適用できる
        • ただし、\( \sum_{a \in A} \) は \( \max_a \) に置き換わる
      • 非線形 (max が入る) → 閉じた形での解は存在しない
      • 繰り返し
        • 価値反復 (Value Iteration)
        • 方策反復 (Policy Iteration)
        • Q 学習
        • Sarsa
    • MDP の拡張
    • 無限 / 連続 MDP
    • 部分観測マルコフ決定過程 (POMDP)
    • 割り引きの無い, 平均報酬 MDP

講義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
        • どの状態を次に更新するか優先度をつける
      • リアルタイム 動的計画法
        • エージェントに関係のある状態だけ更新する
    • ベルマン方程式は、状態数が多い時に効率が悪い
      • サンプリング

講義4: モデルフリー予測

モデルフリー予測 = 未知の MDP の価値関数を推定する

  • モンテカルロ (MC) 学習

    • 経験のエピソードから直接学習する
    • エピソードが終了する必要あり
    • 方策 \( \pi \) の下で、経験のエピソード \( S_1, A_1, R_2, ..., S_k \sim \pi \) から \( v_\pi \) を学習
    • 復習: 利得 \( G_t = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{T-1}R_T \)
    • 復習: 価値関数 \( v_\pi(s) = E_\pi[G_t | S_t = s] \)
    • モンテカルロ方策評価:各エピソードについて、状態 \( s \) を最初に訪問した時に
      • カウンターと利得の合計を更新。
      • \( V(s) \) → 利得の合計 / 訪問回数
      • 十分多くの \( N(s) \) を観察すると、\( V(s) \) は \( v_\pi(s) \) に収束
    • 各訪問ごとに更新する場合
      • 訪問回数を、各訪問ごとに更新
      • これでも、\( V(s) \to v_\pi(s) \)
    • 「差分」を使った系列の平均計算
      • 系列 \( x_1, x_2, ... \) を全て観測し終わらなくても、それまでの平均 \( \mu_k \) を計算することができる
      • \( \mu_k = \mu_{k-1} + \frac{1}{k} (x_k - \mu_{k-1}) \)
      • 直感的な説明: 新しい値を観測した時、それまでの推定値と大きくことなる場合は、推定値を大きく更新する。
      • \( \mu_{k-1} \) →.それまでの推定値。\( x_k - \mu_{k-1} \) → 新しい値を観測した時の「驚き」。\( \frac{1}{k} \) → 学習率
    • 差分モンテカルロ更新
      • エピソード毎に更新(全てのエピソードの「和」を保持しない)
      • \( N(S_t) \leftarrow N(S_t) + 1 \)
      • \( V(S_t) \leftarrow V(S_t) + \frac{1}{N(S_t)}(G_t - V(S_t)) \)
      • 注:エピソードが終わるまで待つ必要あり
  • 時間差分 (Temporal Difference) 学習

    • 経験のエピソードから直接学習する (モンテカルロ法と同じ)
    • エピソードが終了してなくても良い → ブートストラップ法 (モンテカルロ法との差異)
    • MC と TD の違い
      • MC: 実際の利得 \( G_t \) を使って更新: \( V(S_t) \leftarrow V(S_t) + \alpha(G_t - V(S_t)) \)
      • TD: 利得の予測値を使って更新: \( V(S_t) \leftarrow V(S_t) + \alpha(R_{t+1} + \gamma V(S_{t+1}) - V(S_t)) \)
        • \( R_{t+1} + \gamma V(S_{t+1}) \) は TD ターゲットと呼ばれる
        • \( \delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \) は TD 誤差と呼ばれる
    • TD の長所・欠点
      • 最終結果を見る前に学習できる。最終結果の無いエピソードでも学習できる
      • 偏り (Bias) と分散 (Variance) のトレードオフ
        • 真の TD ターゲット \( R_{t+1} + \gamma v_\pi(S_{t+1}) \) は \( v_\pi(S_t) \)の 不偏推定量
        • TD ターケット \( R_{t+1} + \gamma V(S_{t+1}) \) は、偏りのある推定量 
        • ただし、TD ターゲットは、利得よりも分散が小さい
      • MC は分散大、偏りゼロ。TD は分散小、偏りあり。
      • TD(0) は \( v_\pi(s) \) に収束。初期値に敏感
      • MC は、観察された利得との平均二乗誤差を最小化する解に収束する
      • TD は、データに対して尤度最大の MDPを学習し、それを解く
    • ブートストラップとサンプリング
      • MC → ブートストラップ無し
      • DP → ブートストラップ有り
      • TD → ブートストラップ有り
      • MC → サンプリング有り
      • DP → サンプリング無し
      • TD → サンプリング無し
  • TD(λ)

    • TD ターゲットを計算するときに、nステップ先読みする
      • 例:\( G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 V(S_{t+2}) \)
      • n を大きくすると、MC 法に収束する
    • nステップ先読みを平均する
      • 例:\( \frac{1}{2} G_t^{(2)} + \frac{1}{2} G_t^{(4)} \)
    • γ利得 → 全てのnステップ利得の幾何平均
      • \( G_t^\lambda = (1-\lambda) \sum_{n=1}^\infty \lambda^{n-1} G_t^n \)
      • なぜ幾何平均? 前の値を保持しなくて良いので、計算コストが低い。TD(0) と同じコストで計算できる。
    • TD(λ) の「前向き」観点
      • \( V(S_t) \leftarrow V(S_t) + \alpha (G^\lambda_t - V(S_t)) \)
    • MC と同じように、エピソードが収束するまで待つ必要がある
    • TD(λ) の「後ろ向き」観点
      • Eligibility Trace
        • 最近性と、頻度を両方考慮する量
        • \( E_0(s) = 0, E_t(s) = \gamma E_{t-1}(s) + {\mathbf 1}(S_t = s) \)
      • \( V(s) \leftarrow V(s) + \alpha \delta_t E_t(s) \)
      • \( \lambda = 0 \) の時 → TD(0) と等価
      • \( \lambda = 1 \) の時 → 更新の合計は MC と同じ

講義5: モデルフリー制御

  • はじめに

    • 非常に多くの問題が、MDP としてモデル化できる
    • On-policy (方策オン型)
      • 「行動しながら学ぶ」
      • 学習している方策と、サンプルを生成する方策が同じ
    • Off-policy (方策オフ型)
      • 「他の人の行動から学ぶ」
      • 学習している方策と、サンプルを生成する方策が違う
  • 方策オン型 MC 制御

    • 復習: 方策反復:1) 方策評価 \( v_\pi \) の推定 と、2) 方策改善 (貪欲的方策改善) を繰り返す
    • ここに、MC 法による方策評価を組み込むことはできるか?
      • 問題点:\( V(s) \) に従って貪欲に行動しようとしても、MDP の完全な情報が必要 → 解法: 代わりに \( Q(s, a) \) を使う
    • \( Q = q_\pi \) を MC で評価する
      • 問題点:探索問題。貪欲的に行動すると、必要な状態に到達することができない
    • 探索
      • ε-貪欲探索
        • 確率εでランダムな行動を(一様分布に従って)取る
        • ε-貪欲探索に従う新しい方策 \( \pi' \) は、前の方策 \( \pi \) よりも良い
      • MC で方策を評価し、ε-貪欲探索をすると?
        • 最適方策 \( \pi_* \) に到達する。どのぐらいかかるか分からない
      • モンテカルロ制御
        • エピソードの完了 → Q を更新
    • GLIE (Greedy in the Limit with Infinite Exploration)
      • 全ての状態-行動ペアを、無限回探索する 
      • 方策が貪欲方策に収束する
      • GLIE モンテカルロ制御
        • 各状態-行動ペアについて、\( G_t \) の平均を \( Q(S_t, A_t) \) として保持
        • 新しいQ値に従い、ε-貪欲方策を更新
        • 最適な行動価値関数 \( q_*(s, a) \) に収束
  • 方策オン型 TD 学習

    • アイデア:MC の代わりに TD を制御ループの時に使う
      • TD を \( Q(S, A) \) の推定に使う
      • Sarsa: なぜ Sarsa? (S, A) → R → S' → A'
      • 更新式: \( Q(S, A) \leftarrow Q(S, A) + \alpha( R + \gamma Q(S', A') - Q(S, A) ) \)
      • 方策改善には、ε貪欲探索を使う
    • Sarsa は、\( Q(s, a) \to q_*(s, a) \) に収束する (条件付きだが、ほとんどの場合成り立つ)
    • nステップ Sarsa
      • nステップ先までの報酬を考慮。例: \( q_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 Q(S_{t+2}) \)
      • \( Q(S_t, A) \leftarrow Q(S_t, A) + \alpha (q_t^{(n)} - Q(S_t, A)) \)
    • Sarsa(λ) の前向き観点
      • \( q^\lambda_t = (1 - \lambda) \sum_{n=1}^\infty \lambda^{n-1}q_t^{(n)} \)
      • \( Q(S_t, A) \leftarrow Q(S_t, A) + \alpha (q^\lambda_t - Q(S_t, A)) \)
      • 問題点:時間軸上で先読みしている。エピソードの最後まで待ちたくない
    • Sarsa(λ) の後ろ向き観点
      • Eligibility Trace \( E_t(s, a) \) を定義 (TD(λ) と違い、状態と行動のペアに対して定義)
      • \( \delta_t = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \)
      • \( Q(s, a) \leftarrow Q(s, a) + \alpha \delta_t E_t(s, a) \)
  • 方策オフ型

    • 別の方策 \( \mu \) に従いながら、対象の方策 \( \pi \) を評価
    • なぜこれが重要か
      • 人間や他のエージェントから学ぶ
      • 古い方策によって作られた経験から学習
      • 探索的な方策から、最適な方策を学習
      • 一つの方策から、複数の方策を学習
    • 重要サンプリング
      • 異なる分布の期待値を予測する
    • 方策オフ型のモンテカルロ法に重要サンプリングを適用する
      • 非常に大きい分散。ほとんど使えない。
      • TD 学習を使うことが必須
    • Q-Learning
      • 振る舞いを規定する方策 \( \mu \) によって取られた(実際の)行動 \( A_{t+1} \)
      • 学習中の方策によって取られた(仮想的な)行動 \( A' \)
      • \( Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1}, A') - Q(S^t, A)) \)
      • 方策オフ型 Q-Learning → 学習したい方策が貪欲的な場合 (SarsaMax)
        • 最適価値関数に収束

講義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)
      • 収束性が向上

講義7: 方策勾配法

  • はじめに

    • これまでは、価値関数から (例えば、ε貪欲法を使って) 方策を直接生成した
    • 価値関数をモデル化する代わりに、方策を直接モデル化する
      • \( \pi_\theta(s, a) = P[a | s, \theta] \)
    • 長所
      • 良い収束性
      • 高次元もしくは行動が連続空間の場合
      • 確率的な方策を学べる
    • 確率的な方策が良い場合
      • じゃんけん
        • もし、方策が決定的なら、相手にそのことを利用されてしまう
        • 最適な方策は、確率的にランダムな手を出すこと
      • Aliasing (偽信号 -> 2つ以上の状態がお互いに見分けられない場合) が起こる場合
        • 確率的に行動するのが最適
        • 素性のせいで、環境の表現が制限される場合も、これに相当
    • 方策の目的関数
      • 1) 開始状態の値を使う 2) 状態の平均値を使う 3) 1ステップ毎の平均報酬
      • どれを使っても同じ手法 (方策勾配) になる
    • 方策最適化
      • \( J(\theta) \) を最小化する \( \theta \) を見つける
      • 様々な手法が使える
        • 勾配を使わない手法
        • 勾配を使う手法 (例: 勾配降下法)
  • Finite Difference 方策勾配法

    • 勾配の方向に登り、極大解を探す \( \Delta \theta = \alpha_\theta J(\theta) \)
    • Finite Differences
      • 各次元について、少し ε だけ値を変えて、\( J(\theta) \) がどう変化するか見る → 勾配の近似
      • 高次元の場合、非効率的
  • モンテカルロ方策勾配法

    • 尤度比
      • 方策勾配を解析的に計算する
      • \( \pi_\theta \) が微分可能で、勾配 \( \nabla_\theta \pi_\theta(s, a) \) が分かっているとすると
      • \( \nabla_\theta \pi_\theta(s, a) = \pi_\theta(s, a) \nabla_\theta \log \pi_\theta(s, a) \)
      • スコア関数 \( \nabla_\theta \log \pi_\theta(s, a) \)
      • これに従うと、尤度最大化 (MLE)
      • Softmax 方策
        • \( \pi_\theta(s, a) \propto \exp{ \phi(s, a)^T \theta )} \)
      • ガウシアン方策
        • 平均を、特徴量の線形和で表現 \( \mu(s) = \phi(s)^T \theta \)
    • One-Step MDP
      • 尤度比トリックを使う: \( \nabla_\theta J(\theta) = E_{\pi_\theta}[\nabla_\theta \log \pi_\theta(s, a)r] \)
    • 方策勾配定理
      • どの方策目的関数に対しても、\( \nabla_\theta J(\theta) = E_{\pi_\theta}[\nabla_\theta \log \pi_\theta(s, a) Q^{\theta_\pi}(s, a)] \)
    • Monte-Carlo Policy Gradient (REINFORCE)
      • パラメータを勾配降下(上昇)法で更新
      • \( Q^{\pi_\theta} \) の不偏サンプルとして、\( v_t \) (t から最後までの報酬和) を使う
  • Actor-Critic 方策勾配法

    • モンテカルロ方策は、分散がまだ大きい
    • Critic を使って、行動価値関数を近似
    • Critic: パラメータ w を使う、Actor: パラメータ θ を使う
    • Critic: \( Q_w(s, a) \) → 前回の講義と同様に推定
    • 分散を減らすトリック:ベースラインを使う
      • 期待値を変えずに、ベースラインを減らせる
      • 方策勾配から \( B(s) \) を引く
      • 状態価値関数 \( V^{\pi_\theta} \) をベースラインとして使うと良い
      • Advantage Function \( A^{\pi_\theta}(s, a) = Q^{\pi_\theta}(s, a) - V^{\pi_\theta}(s) \)
        • → 方策勾配に組み込む
    • どうやって Advantage Function を推定するか
      • 方法1. 2つの異なるパラメータを使う
      • 方法2. TD 誤差を使う (期待値が Advantage Function と同じになる)
        • \( V(s) \) だけを推定すれば良い
    • Critic の変種 (異なる時間スケール、ターゲット)
      • MC, TD(0), 前向き観点 TD(λ), 後ろ向き観点 TD(λ)
    • Actor の変種 (異なる時間スケール、ターゲット)
      • MC → 利得 \( v_t \)
      • TD → TD誤差 \( r + \gamma V_v(s_{t+1}) \)
      • Eligibility Trace
    • 全く偏りの無い方策勾配を求めることも可能 → Compatible function approximator