公式早見表

　 　
収益 \(G_t = \sum_{k=0}^{\inf} \gamma^k R_{t + k+ 1}\)
\(G_t = R_{t+1} + \gamma G_{t+1}\)
状態価値関数 \(V^{\pi}(s) = E_{\pi}[G_t|S_t = s]\)
行動価値関数 \(Q^{\pi}(s, a) = E_{\pi}[G_t|S_t = s, A_t = a]\)
状態と行動価値観数の関係 \(V^{\pi}(s) = \sum_{a} \pi(a|s) Q^{\pi}(s, a)\)
ベルマン方程式,価値関数 \(v_{\pi}(s) = \sum_{a, s'}\pi(a|s)p(s'|s, a)\{r(s, a, s') + \gamma v_{\pi}(s')\}\)
ベルマン方程式,行動価値関数 \(q_{\pi}(s, a) = \sum_{s'}p(s'|s, a)\{r(s, a, s') + \gamma \sum_{a'} \pi(a'|s') q_{\pi}(s', a')\}\)
ベルマン最適方程式,価値関数 \(v_{*}(s) = \max_a \sum_{s'}p(s'|s, a)\{r(s, a, s') + \gamma v_{*}(s')\}\)
ベルマン最適方程式,行動価値関数 \(q_{*}(s, a) = \sum_{s'}p(s'|s, a)\{r(s, a, s') + \gamma \max_{a'} q_{*}(s', a')\}\)
最適方策 \(mu_{*}(s) = argmax_a q_{*}(s, a) = argmax_a \sum_{s'}p(s'|s, a)\{r(s, a, s') + \gamma v_{*}(s')\}\)

強化学習

強化学習は、機械学習の一種であり、エージェントと呼ばれるものが行動を行い、その結果として報酬を得ることで学習を進めていく手法。
エージェントは状態を観測し、その状態に応じてアクションを選択する。
そのアクションによって状態が変化し、報酬が与えられる。
この報酬によって、エージェントは良い行動と悪い行動を判断し、良い行動を取るように学習を進める。
強化学習は、様々な分野で活用されている。例えば、ゲームのAI、ロボットの制御、自動運転車の開発などが挙げられる。
強化学習は、人間が行うような制御や意思決定を自律的に行うことができる。

マルコフ決定過程

マルコフ決定過程(Markov Decision Process, MDP)は、強化学習における数理モデル。
MDPは、エージェントがある状態から別の状態に移行するためのアクションを選択することで得られる報酬を最大化するように学習する問題を表現している。
MDPは、状態、アクション、報酬、遷移確率、割引率といった要素から構成されている。

状態

エージェントが存在する環境の状態を表す。
例えば、迷路の中でエージェントがどの位置にいるか、といった情報が状態。
MDPでは、状態は離散的な値で表現される。

アクション

エージェントがとることのできる行動を表す。
例えば、迷路の中でエージェントが上下左右に動くことができる場合、上、下、左、右の4つのアクションが存在する。
MDPでは、アクションも離散的な値で表現される。

報酬

報酬(reward)とは、エージェントがアクションを実行した結果として得られる値を表す。
MDPでは、報酬は状態とアクションに依存する値であり、エージェントが目指すべき目的を表すとも言える。

遷移確率

遷移確率は、現在の状態とアクションによって、次の状態に遷移する確率を表す。
MDPでは、遷移確率は状態とアクションに依存する確率分布で表現される。

割引率

割引率(discount factor)とは、将来得られる報酬の重要度を表す値。
MDPでは、時間の経過に伴って報酬が減衰することがあるため、割引率を用いて将来の報酬を現在の価値に換算する。

価値観数の更新方法

  • 方策反復法（方策評価ごとに更新するので計算量が多くなる）
  • 価値反復法（価値関数だけで学習状態を表現できるため、簡潔な実装になる）

実装は、ゼロから作るディープラーニング 4 の 4 章、 policy_iter や value_iter を参照。

動的計画法（DP 法）

動的計画法は、状態価値関数を用いて、最適な行動を選択するための手法。
動的計画法は、状態数が限られている場合に有効な手法。
しかし、状態数が膨大な場合には計算量が膨大になるため、実用的ではない。

モンテカルロ法

モンテカルロ法は、エージェントがエピソードを繰り返しながら、報酬を得ることで問題を解決する手法。
エピソードとは、ある状態から始まり、終了条件が満たされるまで行動を繰り返し、最終的に報酬を得るまでの一連の流れのこと。
モンテカルロ法は、エピソードの集合から状態価値関数を推定する。
モンテカルロ法は、動的計画法と比較して、状態数が膨大な場合でも適用できるため、実用的な手法として広く使われている。

TD学習

TD学習は、エージェントが報酬を得ながら、状態価値関数を更新する手法。
TD学習は、モンテカルロ法と動的計画法の両方の長所を取り入れた手法であり、エピソードが不要でありながら、状態数が膨大な場合でも適用できるため、実用的な手法として広く使われている。

参考

SarsaとQ学習の違い

SarsaとQ学習は、強化学習のアルゴリズムの一種であり、状態行動価値関数を求めるために用いられる。
今さら聞けない強化学習（10）: SarsaとQ学習の違い - Qiita

Sarsa

  • Sarsa は、ペアワイズで学習を行う
  • Q 学習に比べて行動価値の小さい探索結果が反映されやすい。計算が不安定になりやすい。
  • 現在の状態と行動に対する価値を更新する際に、次の行動を決定するために、ε-greedy方策を採用している。つまり、εの確率でランダムな行動をとり、1-εの確率で最適な行動をとる。
  • 探索と利用のバランスを取りながら、最適解に収束することができる。
  • 方策オン型の手法で、行動を決定する方策と行動価値関数の更新に利用される方策は同一。

Sarsa における行動価値関数の更新式

\[Q(S_t, A_t) ← Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]\]

Q 学習

  • Q 学習は、ベストな行動（ベルマン最適関数）に基づいて学習を行う
  • Q学習は、現在の状態において、最大の行動価値を持つ行動をとる。つまり、常に最適な行動をとることを目指す。
  • そのため、探索に偏った学習を行うことができず、最適解に収束するまでに時間がかかることがある。ただし、基本的には Sarsa よりも収束が早い傾向がある。
  • ただ、最終的には最適解を得ることができる。
  • 行動価値関数 Q の更新が行動の決定方法に依存しない。
  • Q 学習は方策オフ型の手法で、行動を決定する方策と行動価値関数の更新に利用される方策が異なる。
  • メモリの使用量が大きくなるため、通常は関数近似をする。

Q 学習における行動価値関数の更新式

\[Q(S_t, A_t) ← Q(S_t, A_t) + \alpha [R_{t+1} + \gamma max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t)]\]

DQN(Deep Q-Network)

報酬、TD誤差のクリッピング

「報酬のスケールが与えられたタスクによって大きく異なる」という問題に対して、報酬の値を -1, 0, 1 の 3 通りに制限することで学習を安定させる。

体験再生

「入力データが時系列であり、入力データ間に独立性がない」という問題に対する対応。
各タイムステップ t におけるエージェントの経験 \(e_t = (s_t, a_t, r_t, s_{t+1})\) をデータ集合 D に蓄積する。
これをリプレイ記憶と呼ぶ。
学習時には、蓄積されたサンプルの中からランダムに経験のサンプルを選ぶ。

目標 Q ネットワークの固定

「価値関数が小さく更新されただけでも選ばれる行動が大きく変わってしまう」という問題に対して、 DQN では目標値の計算に用いる行動価値関数ネットワークのパラメータを固定している。
一定期間の学習の間、目標 Q ネットワークのパラメータを固定し、決められた周期でこれを更新することで学習を安定させる。

方策勾配法

方策勾配法（Policy Gradient Method）は、強化学習における方策関数の最適化手法。
方策関数は、現在の状態に応じて、エージェントがどのような行動を取るかを決定する関数。
方策勾配法は、方策関数を微小に変更し、報酬を最大化するように更新していく。
方策勾配に基づく強化学習では、パラメータベクトルによってパラメタライズされた方策に基づいた行動を取るため、行動価値関数は直接的には用いられない。

勾配は、報酬と方策関数の微分によって計算される。
方策勾配に基づく強化学習のアルゴリズムは、期待収益を目的関数 \(J(\theta)\) とし、最大化する確率的方策 \(\pi_\theta\) のパラメータ \(\theta\) を求める。

\[\theta^{t+1} = \theta^{t} + \eta \nabla_\theta J(\theta)\]

勾配は、

\[\nabla_\theta J(\theta) = \sum_{s \in S}d^{\pi_\theta}(s)\sum_{a \in A}\nabla_\theta \pi_\theta(a|s;\theta)Q^{\pi_\theta}(s,a)\]

これを変形すると、以下のようにも表せる。

\[\nabla_\theta J(\theta) = \mathbb{E}_{\pi\theta} \left[ \frac{\partial \pi_{\theta}(a|s)}{\partial \theta} \frac{1}{\pi_\theta (a|s)} Q^{\pi_\theta}(s,a) \right]\] \[\nabla_\theta J(\theta) = \mathbb{E}_{\pi\theta} \left[ \nabla_\theta \log \pi_\theta (s,a) Q^{\pi_\theta}(s,a) \right]\]

ここで、 \(J(\theta)\) は期待収益を表す関数、 \(\theta\) は方策関数のパラメータ、 \(\pi_\theta\) はパラメータ \(\theta\) に依存する方策関数、 \(Q^{\pi_\theta}(s,a)\) は状態 s で行動 a をとった場合の報酬の期待値を表す関数。
REINFORCE アルゴリズムでは、 \(Q^{\pi\theta}\) を収益 G で近似する。

参考

A3C

Actorと呼ばれる機構を用いて方策 \(π_θ\) に基づいて行動を選択し、Criticと呼ばれる機構にて選択された行動を評価する。
DQNを卒業してA3Cで途中挫折しないための7Tips - Qiita