【JDLA E資格】強化学習の基礎とアルゴリズムの分類

#はじめに
JDLA E資格試験で出題される強化学習の基礎とアルゴリズムの分類について解説した記事です。
E資格試験の機械学習パートでは、強化学習の用語やマルコフ決定過程について出題されます。

なお、他パートの具体的な解説については、下記をご覧ください。
[E資格試験に関する私の投稿記事リスト][link-1]
[link-1]:https://qiita.com/fridericusgauss/items/5a97f2645cdcefe15ce0

###目次

1. 機械学習の分類
2. 強化学習の基礎
3. 強化学習の用語
4. 強化学習アルゴリズムの分類
5. おわりに

#機械学習の分類
E資格試験で登場する機械学習モデル・アルゴリズムは下記表のように分類されます。

モデル	学習タイプ	タスク
線形回帰	教師あり	回帰
ロジスティック回帰	教師あり	分類
SVM	教師あり	分類
k-近傍法	教師あり	分類
k-means	教師なし	クラスタリング
k-means++	教師なし	クラスタリング
主成分分析	教師なし	次元削減
動的計画法	強化学習	ー
モンテカルロ法	強化学習	ー
Q-Learning	強化学習	ー
Sarsa	強化学習	ー

#強化学習の基礎
###概要
機械学習は教師あり学習、教師なし学習、強化学習に大別され、強化学習は、機械学習の一つのカテゴリです。
強化学習の目的は、ある意思決定を行う環境内で、目標を達成する意思決定則を得ること__です。
意思決定の主体となるエージェントが、ある環境（タスク）の中で目標を達成するために、どのように意思決定をして、行動すれば良いのかを定式化して学習します。
意思決定は、エージェントが環境から知覚する__状態__をもとに行われ、意思決定により環境に対して行った__行動__から、結果（成功信号である__報酬__と__次の状態）を知覚します。
これらを繰り返すことで意思決定則（方策）を学習します。

機械学習の定式化では、__エージェントが環境内で得る収益（報酬の総和）を最大化する方策を学習することが目的__です。
ある状態で行動を行う1ステップで得る即時報酬ではなく、長期的な行動を繰り返した後に得る報酬の価値を表現する価値関数を基準に方策を学習する。
このように、短期的な利益ではなく、__長期的な利益を最大化することを目指すのが特徴__です。

エージェントと環境との関係図式などは、ネットで検索すればすぐヒットするので、割愛します。

###データの集め方

• 学習に必要なデータは人間から与えられず、エージェント自身が環境で探索して集める必要がある
• 明確な教師データは存在せず、代わりに__環境から得られる報酬を教師信号__とする
• 得られるデータが方策に依存する（探索しながらデータを収集するため）

#強化学習の用語
###時間概念

• サイクル(ステップ)：エージェントがある状態から行動を行い、次の状態に移行するまでの単体のプロセス。
• エピソード：全サイクルのことで、行動の開始から終了までの期間。

現在のステップを$t$とし、$t=0,1,\cdots$とします。
エピソードが定められている場合、$t=0,1,\cdots, T$とします。

###タスク
強化学習のタスクは、大きくエピソード的タスクと連続タスクの二つがあります。

• エピソード的タスク：タスクの開始状態へリセットするタイミングが決められているタスク（囲碁やゲーム）
• 連続タスク：明確なリセットタイミングがなく、断続的に動作し続けるタスク（ロボットなど）

私のQiitaの記事では、主にエピソード的タスクを説明します。

###マルコフ決定過程
環境に対して、マルコフ性を仮定し、これを満たす__マルコフ決定過程（MDP）__を持つ問題で定式化します。

####【マルコフ性】
現在のステップを$t$としたとき、現在の状態$s(t)$、行動$a(t)$のみに依存し、次の状態$s(t+1)$（遷移確率）が決まる性質

####【MDPの構成要素】

• 状態集合：$S=\{s_{i}|i=1,2,\cdots,n_S\}$
• 行動集合：$A=\{a_{i}|i=1,2,\cdots,n_A\}$
• 状態遷移確率：$P(s(t+1)=s^{\prime}|s(t)=s,a(t)=a)=P(s^{\prime}|s,a)$
• 初期状態確率分布：$s(0)\sim P_0(s)$

ただし、$s,s^{\prime}\in S, a\in A$です。

###方策
方策$\pi$はエージェントの意思決定則で、ある状態$s\in S$でどのような行動$a\in A$を選択するのかを表す関数です。
方策は決定的方策と確率的方策に分類されます。

####【決定的方策】
決定的方策では、エージェントの状態$s$における行動$a$が、方策$\pi$によって一意に決定されます。
その方策は式(1)で表されます。

a=\pi(s)
\tag{1}

現在の状態で、最終的に多くの報酬が得られる行動を選択する際に利用します。

####【確率的方策】
確率的方策では、エージェントの状態$s$における行動$a$が、方策$\pi$の条件付き確率$P$によって確率的に決定されます。
その方策は式(2)で表されます。

\pi(a|s)=P(a(t)=a|s(t)=s)=P(a|s)
\tag{2}

ある状態における行動は一定の確率で選択されます。
ランダムに行動を選択する必要がある場合、例えばより多くの状態を探す際などに利用します。
基本的には確率的方策が使用されます。

###報酬
エージェントがある状態$s(t)$で、ある行動$a(t)$を行った結果、状態$s(t+1)$に移ったとき、環境から報酬$r(t+1)$を得ます。
この報酬関数は式(3)で表されます。

r(t+1)=r(s(t),a(t),s(t+1))=r(s,a,s^{\prime})
\tag{3}

特に、1ステップでエージェントが得る報酬関数$r(t+1)$は__即時報酬__と呼ばれます。
また、ステップ$t$以降の即時報酬の累積は__収益__（累積報酬）と呼ばれ、式(4)で表されます。

G(t)=\sum_{k=0}^{\infty}\gamma^kr(t+k+1)
\tag{4}

ただし、$\gamma\in [0,1]$は割引率です。

強化学習では、収益に関連する目的関数を最大化する方策を学習する問題に帰着されます。
このため、収益の期待値である__価値関数__を「方策の良さ」として使用することが多いです。

#強化学習アルゴリズムの分類
###強化学習アルゴリズムの分類
E資格試験の機械学習パートで出題される、強化学習アルゴリズムを大まかに分類すると下記表になります。
E資格試験の機械学習パートでは、Actor-Criticや価値ベースなどの用語は登場しませんが、体系的なことを考慮して表に追加しました。

モデル	学習方式	価値推定方式	方策オン/オフ	アルゴリズム
モデルベース	価値/方策ベース	―	―	動的計画法
モデルフリー	価値ベース	実績ベース	方策オン/オフ	MC法
モデルフリー	価値ベース	TD学習	方策オフ	Q-Learning
モデルフリー	価値ベース	TD学習	方策オン	Sarsa
モデルフリー	方策ベース	―	―	REINFORCE
モデルフリー	Actor-Critic	TD学習	―	A3C

下記では一応分類を解説しますが、価値関数のベルマン方程式や学習方法を一定以上理解しないと難しいです。
詳細は今後の記事について解説していきます。

###モデルベース/モデルフリー

• モデルベース：モデルあり。事前に環境を把握するためにモデルを構築し、どのような行動計画が最適かをあらかじめ決定する。ベルマン方程式を利用して、直接価値関数を計算する。
• モデルフリー：モデルなし。環境の構造や遷移を全て把握しようとするのではなく、サンプル（経験）を逐次得て、どのように環境が作用するかを学習する。

###価値ベース/方策ベース/Actor-Critic系

• 価値ベース：明示的な方策はなく、サンプルから学習し、最適な価値関数の値を逐次推定するアルゴリズム。「価値」を求めたうえでその「価値」を高めるような「方策」を選択する。（厳密には方策自身はあるが、価値関数が最大の方策を常に選択する）

• 方策ベース：明示的な方策があり、現在の方策を改善するアルゴリズム。価値関数は内部的に有するが、行動選択に影響を与えない。まず「方策」を決めてからその「方策」の「価値」を高めるように「方策」を改善していく。

• Actor-Critic：価値ベースと方策ベースの両方を備わったアルゴリズム。方策も価値関数もどちらも利用する。

###実績ベース/TD学習

• モンテカルロ法（MC法）：サンプルが実績ベースなので、1エピソードが完了したタイミングで、現在の方策からエピソードを生成して、価値関数を推定する。
• Temporal-Difference学習（TD学習）：サンプルが予測ベースなので、エピソード途中で、目標の価値と現在の価値のズレ（Temporal-Difference誤差：TD誤差）を修正していくことで、価値関数を推定する。

###方策オン型/方策オフ型

• 方策オン型：行動価値関数の更新に用いるターゲット方策が、実際の行動選択に用いる方策$π(a|s)$と一致している。
• 方策オフ型：行動価値関数の更新に用いるターゲット方策が、実際の行動選択に用いる方策$π(a|s)$と異なる。

価値関数の種類やベルマン方程式については、下記記事をご覧ください。
[強化学習の価値関数とベルマン方程式][link-2]
[link-2]:https://qiita.com/fridericusgauss/items/a2b868490eb809b19872

各代表的なアルゴリズムについては、別途記事で解説する予定です。
[強化学習の価値ベースのアルゴリズム（Q学習とSarsa）][link-3]
[強化学習の方策ベースのアルゴリズム（方策勾配法）][link-4]
[link-3]:https://qiita.com/fridericusgauss/items/f87984d4bcd0e143fef6
[link-4]:https://qiita.com/fridericusgauss/items/aa5215c29646963bda29

#おわりに
E資格向けの強化学習の基礎について解説しました。
なお、上記は、2021年2月時点における内容であることにご注意ください。

[E資格試験に関する私の投稿記事リスト][link-1]