強化学習の勉強 - ドラムと筋肉とプログラミング

はじめに

本記事は、機械学習の一つである「強化学習」について、勉強したことの結果をアウトプットとして残すことを目的とします。

強化学習とは？

概念

「機械学習（Machine Learning）」のうちの一つの手法になります。
機械学習とは、コンピュータが大量のデータからそこに潜む特徴やパターンを見つけそれを説明する「モデル」を作成し、そのモデルに基づいて高い正確性で予測を行うことになります。

この機械学習の種類には大きく三種類存在します。

「強化学習」では、学習するための「環境」を与える必要があります。

この環境には、「行動」、「状態」、「報酬」が定義されています。

「行動」を試行錯誤して行う中で「状態」が変わり、最終的にゴールに到達する事ができれば「報酬」をもらう事ができます。

強化学習の目的は、「最終的（1エピソード）に得られる報酬の総和の合計を最大化する」モデルを模索することになります。

囲碁プログラムのAlphaGoでは、この強化学習のノウハウにより囲碁で勝利するためのパターンを学習した結果、世界王者を4勝1敗で下すと言った結果になりました（2016年3月時点）。

オセロでの例

上記で「環境」、「行動」、「状態」、「報酬」という単語ができてきたので、オセロに喩えて説明してみます。

環境：オセロの盤（通常8×8）
行動：石を打つする
状態：プレイヤーが石を打つことにより、挟まれた石の色が変わる
報酬：ゲーム終了時に、プレイヤーの石が敵の石より多く置いてある場合に得られる

オセロの強化学習では、プログラミングによって実際に石を置いていき、すべての石を置き切った時点での（すべての石を置いた状態）最終的な報酬を算出します。
この最後まで石を置き切ると言った行為は、環境でいうところの最終的な「ゴールに到達する」という状態を表します。

ゴールまでに到達するまでの一連の流れを「エピソード」といい、強化学習ではこのエピソードを何度も繰り返し試行錯誤する中で報酬をもらえるパターンをモデル化します。

このオセロの例だと、報酬をもらえるケースはゲーム終了時にしかもらえないですが、環境によっては行動毎に報酬がもらえる（即時報酬）ケースがあります。

強化学習における問題設定 - MDP(Markoy Decision Process)

強化学習では、与えられた「環境」が「マルコフ性（Markov property）」というルールにしたがっていることを想定します。
このマルコフ性のルールに従うことで、上記で説明した「環境」の説明を数式で表現する事が可能となります。

数式を説明する前に、マルコフ性のルールと構成要素について説明します。

ルール

遷移先の状態は、直前の状態とそこでの行動飲みに依存する
報酬は、直前の状態と遷移先に依存する

構成要素

s(state)	状態
a(action)	行動
T(Transition function)	遷移関数
R(Reward function)	報酬関数（即時関数）

上記を基に、価値の総和を最大にする数式を解説していきます。

補足

上記のMDPでは、報酬関数、遷移関数が登場しますが、これは強化学習において、「モデルベース」の考えを適応していると言えます。
対に「モデルフリー」という概念も存在しますが、こちらでは報酬関数、遷移関数が存在しないケースになります。
→本記事では説明省略します

数式

報酬の総和（期待報酬（Expected reward）、価値（value））

ある時刻 $\displaystyle t$ からエピソード終了時刻 $\displaystyle T$ までの報酬を示します。
$\displaystyle G_t = r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{T-t-1}r_T = \sum_{k=0}^{T-t-1} {\gamma^k r_{t+k+1}}\\ \gamma: 割引率(Discount factor)、0-1$

報酬の総和は、エピソードが終了しないと計算できないため、「見積もり」としてその時点における状態を算出する必要があります。
見積もりはあくまで不確かな値であるため、この割引率により遠い将来の報酬ほど信頼の低い値として算出します。

報酬の総和の期待値

上記の記載した数式では、以下二つの問題点があります。

その1	将来の即時報酬の値（ $\displaystyle r_{t+1}, r_{t+2} + \cdots$ ）の合計を理解している必要がある
その2	将来の即時報酬が必ず得られる、と定義している

将来の即時報酬が「必ず登場する」ということを前提としています。実際は、行動してみないとその即時報酬がわからないという前提があるため、「期待値」として表現する事がふさわしいです。

「その1」に従い、「報酬の総和」を再帰的に表現すると以下のようになります。

$\displaystyle G_t = r_{t+1} + \gamma G_{t+1}$

次に、「その2」の期待値を算出するため、各時刻において「報酬を得られる確率」を掛け合わせます。

報酬の総和の期待値を $\displaystyle V$ と表します。
この時、戦略 $\displaystyle \pi$ によって状態 $\displaystyle s$ から $\displaystyle s'$ に移動する場合、行動 $\displaystyle a$ をとる確率は $\displaystyle \pi (a \mid s)$ 、遷移先 $\displaystyle s'$ へは遷移関数から導かられる確率は $\displaystyle T(s' \mid s, a)$ とします。