機械学習 学習まとめ: 強化学習

強化学習

• 長期的に報酬を最大化できるように環境のなかで行動を選択できるエージェントを作ることを目標とする機械学習の一分野
  • マルコフ決定過程を前提とした学習サイクル
    • マルコフ決定過程: 次の状態が現在の状態と、採った行動によって確定するシステム
  • 行動の結果として与えられる利益(報酬)をもとに、行動を決定する原理を改善していく仕組み
    1. エージェントは時刻$t$において環境から状態$s_t$を受け取る
    2. エージェントは状態$s_t$から、方策($ π $、正確には条件付き確率である$ π(a \vert s) $)に基づき行動$a_t$を選択して実行する
    3. 環境が新しい状態$s_{t+1}$に遷移する
    4. エージェントは遷移で生じた価値$V$に応じた報酬$r_{t+1}$を獲得する
    5. エージェントは得られた報酬をもとに、選択した行動の良し悪しを学習する
    6. ステップ1へ
  • 状態$ s_t $において選択した行動$ a_t $によって状態が$ s_{t+1} $に遷移し、報酬$ r_{t+1} $が得られる確率を$ P(s_{t+1}, r_{t+1} \vert s, a) $と表す
  • 数学的に表される二つの関数(関数近似法)の最適化を目指す
    • 方策関数$ π(s, a) $
    • 行動価値関数$ Q(s, a) $
• 方策関数
  • エージェントがある状態でどのような行動をとるのかの確率を与える関数
    • $ π(s) = a $
    • 行動価値関数が最大化されるように方策関数を学習する
  • エージェントは方策に基づいて行動する
    • $ π(s, a) $: $ V $や$ Q $を元にどういう行動をとるか
      • $ π(s, a \vert θ) $: 方策関数をNNで表現する際の重みを$θ$とする
• 価値関数には2種類存在する
  • 状態価値関数(state-value function): ある状態$ s $において、今後方策$ π $に従って行動していった場合の期待収益
    • $ V^π(s) = \mathbb{E}_π[G_t \vert S_t = s] $
    • $ G_t $は将来に渡る報酬$ r $を割引率$ γ $で割引いた収益
      • $ G_t = R_{t+1} + γR_{t+2} + γ^2R_{t+3} + \cdots $
      • $ G_t = \displaystyle \sum_{k = 0}^{\infty}γ^k r_{t+k+1} $
      • 割引率$ γ $は$ 0 \lt γ \leq 1 $なので、$ γ $を掛ける
        • 金利のように1を足したもので割るわけではない
      • 将来からの割引なので、漸化式は$ G_t = R_{t+1} + γG_{t+1} $となることに注意
  • 行動価値関数(action-value function): ある状態$ s $において行動$ a $をとり、その後に方策$ π $に従って行動していった場合の期待収益
    • $ Q^π(s, a) = \mathbb{E}_π[G_t \vert S_t = s, A_t = a] $
  • 行動価値関数$ Q^π(s, a) $を、時刻$ t $において選択可能なすべての行動$ a $に関する期待値をとると、状態価値関数$ V^π(s) $となる
    • $ V^π(s)　= \displaystyle \sum_a π(a \vert s) Q^π(s, a) $
  • 最近の主流は行動価値関数
    • 行動価値関数、すなわちQ値の最適化を目指すのがQ学習

強化学習の二つのアプローチ

1. 方策反復法
   • パラメータ$ θ $を用いて確率的方策$ π $をモデル化し、収益の期待値$ J(θ) $ を最大化するような$ θ $を勾配法により求める
2. 価値反復法
   • ベルマン方程式に従って行動価値関数$ Q^π(s, a) $をモデル化して、最適行動価値関数を求める

方策勾配法

• $ θ^{(t+1)} = θ^{(t)} + ε∇J(θ) $
  • $J$とは、方策の良さ
    • 方策から得られる期待収益
    • NNでは誤差関数であり目指すのは最小化だったが、強化学習では期待収益であり、目指すのは最大化(だからマイナスではなく、プラスする)
• 方策勾配定理
  • $ ∇_θJ(θ) = \mathbb{E}_{π_θ}[( ∇_θ \log π_θ (a \vert s)Q^{π_θ}(s, a))] $
  • 展開する元は以下の通り
    • $ ∇_θJ(θ) = ∇_θ \displaystyle \sum_{a \in A} π_θ (a \vert s)Q^{π_θ}(s, a) $
      • ここで$ π_θ (a \vert s)Q^π(s, a) $はある行動をとる時の報酬

動的計画法

• 環境の完全なモデルがマルコフ決定過程として与えられている場合に適用できる
• 実際の問題で環境の完全なモデルが明らかになっていることはほとんどないため、適用できる場面は限定的
  • 代表的な手法としては、方策反復法と価値反復法

モンテカルロ法

• 遷移のサンプルを取得し、得られた収益を平均化することで価値関数を推定する
  • $ V(S_t) ← V(S_t) + α((r_{t+1} + γr_{t+2} + γ^2r_{t+3} + \cdots + γ^{T-1}r_T) - V(s_t)) $
• 価値関数の改善または方策の改善は行動一回ごとではなく、エピソード終了後に行う
  • 行動の修正は実績に基づいて行うため、修正の妥当性は得られるが、修正スピードは遅くなる

TD学習(Temporal Difference Learning)

• 目標の価値と現在の価値のずれ(TD誤差)を修正していくことによって価値関数を推定する
• モンテカルロ法と異なり、価値関数の改善または方策の改善は行動ごとに行うため、エピソード終了を待つ必要がない
• TD学習の具体的な手法として、SarsaとQ学習がある
• Sarsa
  • Sarsaにおける行動価値関数$ Q(s, a)$の更新式
    • $ Q(S_t, A_t) ← Q(S_t, A_t) + α[R_{t+1} + γQ(S_{t+1}, A_{t+1}) - Q(S_t, A_t)] $
      • $ α[\cdots] $のカッコ内がTD誤差(行動前の評価値と行動後の評価値の誤差)であり、最適化によってTD誤差を0に近づけることを目指す
  • 方策オン型の手法であり、行動を決定する方策と行動価値関数の更新に利用される方策が同じ
    • $ ε $-Greedy法で行動を決定し、その方策($ ε $-Greedy法)で価値関数を更新する
  • 行動価値関数を更新する際、Q学習に比べ行動価値の小さい探索結果が反映されやすい
    • 反面、計算が不安定になりやすいという面もある
• Q学習
  • Q学習における行動価値関数$ Q(s, a)$の更新式
    • $ Q(S_t, A_t) ← Q(S_t, A_t) + α[R_{t+1} + γ\underset{a'}{max}Q(S_{t+1}, a') - Q(S_t, A_t)] $
      • $ α[\cdots] $のカッコ内がTD誤差であり、最適化によってTD誤差を0に近づけることを目指す
  • Sarsaと異なり方策オフ型の手法であり、行動価値関数$ Q $の更新が行動の決定方法に依存しない
    • 行動を決定する方策と行動価値関数の更新に利用される方策が異なる
    • $ ε $-Greedy法で行動を決定するが、max関数を用いて、最も価値の高い行動をとる状態行動対を用いて価値関数を更新する
  • 行動価値関数を更新する際、Sarsaに比べ行動価値の小さい探索結果が反映されにくい
  • Sarsaよりも行動価値関数の収束が早くなることが多いが、保証されているわけではない