強化学習の基本的な考え方

# この記事の目的
近年、注目されている強化学習の効果をイメージするため、基礎となる考え方とについて説明します。また簡単ながら、代表的な応用例であるAlphaGoにおける強化学習の使われ方について説明します。

# 機械で学習するとは？

機械学習とは、何でしょう？

>機械学習（きかいがくしゅう、英: machine learning）とは、人工知能における研究課題の一つで、人間が自然に行っている学習能力と同様の機能をコンピュータで実現しようとする技術・手法のことである。(Wikipediaより)

## 機械学習には多くの種類がある

機械学習には多くの種類があります。代表的な物として、教師あり学習 (supervised learning) 、
教師なし学習 (unsupervised learning)、そして、強化学習 (reinforcement learning)があります。


| カテゴリ     | 学習対象 | 応用分野 | 
|:----------- |:------------|:------------:|
| 教師あり学習 (supervised learning)  | 入力と出力の「関係」 | 分類、予測 |     
| 教師なし学習 (unsupervised learning)| 入力の「構造」 | クラスタリング、次元削減 |
| 強化学習 (reinforcement learning)    | エージェントがとる良い「行動」| ゲーム攻略、株売買 |

この中で、最近、強化学習が注目されています。


# 強化学習がなぜ注目されているのか

## 強化学習では機械が試行錯誤を行い、自ら良い行動を学習する

教師あり学習が典型例となりますが、従来の機械学習では「まずデータを収集しましょう」からスタートとなります。データを持っていないと機械に学習させることができず、多くの企業、団体、個人にとって参入障壁になります。そのため、「データを持っていること」がビジネス上の重要な価値となっていました。

一方で、強化学習は**「十分なデータの収集が困難な状況において、どのようにデータを収集するか」**を対象とした学問体系です。データを持っていない場合においても、ビジネスチャンスを掴むことができるかもしれず、また従来の機械学習よりも良い性能が実現できるケースあり、近年、注目されています。

- どういう問題を解決するか？
	- 一つ一つの行動の正解値は不明
	- 最終的な正解は判別可能
- 例えば
	- ゲーム
		- 将棋（最終的な正解=王手)
	- ロボット制御
		- 倒立制御(最終的な正解=外乱を受けても倒れない)  

# 強化学習の考え方

## 目先の報酬ではなく、長期的報酬(価値)に着目する

強化学習では、各局面においてエージェントがとる『良い「行動」』を学習します。ここで、これを達成するために、「良い」の定義が必要となります。数学的に「良さ」を扱うため、強化学習では**「報酬(Reword)」**という概念が登場します。
$$r(s,a,s')=ある状態(局面)sで行動aをとり次の局面s'に移った時に得る報酬$$

強化学習では、各局面において、エージェントは行動を起こすたびに、この「報酬」を得続けます。これは例えば、将棋教室で将棋を指していて、一手打つごとに、先生から「今のはいい手だ」(プラスの報酬)とか、「その手はないな」(マイナスの報酬)とかアドバイスをもらう状況に相当します。

ここでいう報酬は、行動を取った時にすぐに得られる「即時報酬」になります。しかし、例えば将棋においても、目先の即時報酬だけを考えていても必ずしも勝てるわけではありません。各局面において、あえて一時的にマイナスになる手を打ってでも、最終的に勝利を掴めることは往々にしてあります。

強化学習では、云わばこの**「長期的報酬」を最大化する一連の行動を学習する**ことができます。さらに、強化学習では、各局面における個々の行動について、いちいち教師データを与える必要はありません。そのため、一般に将棋のようなゲームや、ロボットの倒立制御など複雑な課題を取り扱うことができます。

**状態価値関数**

　この長期的報酬を時間制限なく学習させた場合、非常に低リスクな行動を永遠にとり続けるケースが発生します。（例えば、ゲームの学習で、永遠に敵から逃げ続ける行動が選択されるかもしれません）。そのため、ある局面から長期的報酬を評価する際に、将来に得られる報酬に対して、一定の割合で減衰させる**「割引率γ」**を導入します。これにより、同じ行動でも将来では評価が異なり、いろいろな行動を学習することができるようになります。（数学的に報酬和の発散を防ぐことができます）。
　このある状態において、この先得られる可能性のある長期的報酬の期待値を**「状態価値関数」**と呼び、v(s)で表します。

$$ 状態価値関数v(s) := E[\sum_{t=0}^{\infty}\gamma^t r(s_{t},a_{t},s_{t+1}) | s_{0}=s]$$

　この数式の意味は、「ある状態sにおいて、今後なんらかの戦略（後述）で行動し続けた場合に、最終的に得られる報酬総和の期待値」を表しています。初期値として設定されているのは状態sだけであることに注意してください。この関数のざっくりとしたイメージは、「ある状態sがどれくらい良い状態なのか」を表しているものとなり、この関数をなんらかの方法で計算できるようになると、状態を見ただけで、先読みせずとも良い/悪いを判断できるようになります。
　強化学習ではこの「状態価値関数v(s)を最大化」を目指して、これを達成する「なんらかの戦略」を決定することが目的となります。

## 強化学習のモデル化

　強化学習のモデル化はマルコフ決定過程(Markov Decision Process: MDP)によって行われます。マルコフ過程とは、数学的には以下のように定義されます。

$$P(s_{t}|s_{t-1},s_{t-2} ... s_{0}) = P(s_{t} | s_{t-1})$$

　これはある状態への遷移条件が、その直前の状態s_{t-1}にのみ依存し、それ以前にどのように遷移してきたかには無関係である、ということを意味しています。強化学習ではこの条件を元にしてモデル化します。
　強化学習で先ほど説明した「状態価値関数の最大化」を達成するために必要なパラメータを定義していきます。

- 状態(State)：局面を表す変数
$$S = [ s_{0}, s_{1}, ... , s_{N} ]$$

- 行動(Action)：局面sでとれる行動を与える関数
$$A(s) = [ a_{0}, a_{1}, ... , a_{N} ]$$

- 報酬：局面sにおいて行動aを取って局面s'に遷移した時に得られる報酬を与える関数
$$r(s,a,s')$$

- モデル：局面sにおいて行動aを取った時に次の局面s'へ遷移する確率
$$P(s'|s,a)$$

- 方策/戦略(Policy)：局面sにおいて、ある戦略に基づいて行動aを起こす確率
$$\pi(a | s)$$

## 最善の戦略を教えてくれるQ関数(行動価値関数)を導入する

　方策π(a|s)は局面sである戦略に基づいて行動aを起こす確率でした。ここで、「状態価値関数(ある状態で取りうる長期的報酬)を最大にする」戦略、すなわち「最善の戦略」をなんらかの形で手に入れたとします。どうやって入手するかは後回しにして、ひとまず、この「最善の戦略」を手に入れると、局面sで取るべき行動aを決定することができ、常に最善の局面へ遷移し続けることができます。これにより、最終的に得られる長期的報酬を最大化することができます。


　この最善の戦略を手に入れる準備として、以下で定義される関数Q(s,a)を導入します。

$$Q(s,a)=E[\sum_{t=0}^{\infty}\gamma^t r(s_{t},a_{t},s_{t+1}) | s_{0}=s, a_{0}=a ]$$


　この式の意味は、「局面sで行動aを取り、その後、最善の戦略に基づき行動し続けた結果、最終的に得られる長期的報酬の期待値」を表しています。　このQ(s,a)は**行動価値関数**と呼ばれます。先に示した状態価値関数v(s)との違いは、状態sで行動aを取ることが決まっているところです。
　数ある戦略πの中から、言わば、神のみぞ知る最善の戦略を手に入れる事ができれば、この行動価値関数の値を最大にすることができます。最善の戦略を手に入れれば、前述の通り、局面sで次にすべき行動aが分かり、長期的報酬を最大化できる局面sへ次々に遷移しつづけることができます。これを式で表すと以下の様になります。

$$Q(s,a) = max_{\pi}Q^\pi(s,a)$$

maxはその中で最大の数値となるものを選ぶという意味です。Q(s,a)を最大にする戦略πに基づく行動aは、最終的に状態価値関数v(s)を最大にするファクターとなります。

## 強化学習の目的は行動価値関数を最大にする戦略の発見
　強化学習で目指す目標は、「状態価値関数の最大化」を達成する最善の戦略を得る事でした。最善の戦略を知ることで、局面sで行動aをとり、より高い状態価値を持つ局面へ遷移し続けることができます。すなわち、強化学習の目的は、この行動価値関数を最大化する戦略を得る事と言い換えることができます。状態価値関数と行動価値関数は以下のような関係で結ばれます。

$$v(s)=\sum_{a}\pi(a|s)Q(s,a)$$

　π(a|s)Q(s,a)は局面sで行動aを取って得られる長期的報酬です。この式は、局面sで取りうるすべての行動A=[a0,a1…]に対してπ(a|s)Q(s,a)の総和を取るとその局面sの状態価値関数が得られるということを表しています。

 ここで、ある局面sにおいて、行動aを取った時の価値を具体的に考えます。局面sにおいて行動aを取る確率はπ(a|s)でした。また、局面sで行動aを取った場合に、次の局面s'に遷移する確率はP(s'|s,a)でした。さらに、それにより得られる報酬はr(s,a,s')でした。そのため、局面sから行動aを取り、その後ある戦略πによる戦略で進んでいった場合に得られる長期的報酬Qπ(s,a)は以下の様に計算することができます。

$$Q^\pi(s,a)=\pi(s'|a)P(s'|s,a)r(s,a,s')+\gamma\pi(s''|a')P(s''|s',a')r(s',a',s'')+…$$

　これを計算することで、ある戦略πに基づいて得られる長期的報酬Qπ(s,a)を得ることができます。これをさらにすべての(s,a)に対して計算していき、最終的に得られた長期的報酬Q(s,a)の中から最大となった戦略πを最善の戦略とすることで、神のみぞ知るはずであった局面sにおける最善の行動aを決定することができます。状態数が少ない場合は、動的計画法などで、実際にこの計算を実行することができます。

　ただし、将棋や囲碁など取りうる状態数が多い課題を解く場合には、この方法でQ(s,a)を計算し、最善の戦略πを得ることはとてつもなく大変な作業となり、実質計算ができない量となってしまいます。

## 行動価値関数を如何に近似するかが鍵となる
行動価値関数をすべての状態について計算することは、とてつもなく大変な作業でした。そのため、行動価値関数をさまざまな方法で推定する方法が提案されています。代表的なものとして以下があります。

- モンテカルロ法
- TD法
- SARSA
- Q学習

### モンテカルロ法
モンテカルロ法は乱数を使って適当にサンプリングする方法の総称です。行動価値関数の推定では、適当な遷移パスを何個かピックアップしてQ(s,a)を計算し、その平均を行動価値関数の真値と推定する、という方法で使われます。要するに、いずれ真値に近づくことを期待して、膨大な一連の行動パスから、適当にサンプリングして平均を算出することで、ある局所解に陥ることなく真値に近づけるという考え方がこの手法となります。

## 探索と知識の利用を適度に織り交ぜて戦略を改善する
さまざまな方法により、行動価値関数を推定することができました。この行動価値関数から導かれる「推定される最善の戦略」のみを学習すると、まだ未学習のさらに良い戦略を見逃してしまう可能性があります。これを**探索と知識のトレードオフ**と呼びます。強化学習でまだ発見していない未知の戦略を探索し、知識（現在までで推定された最善の戦略）を改善するため、**ε-greedy法**などが使われます。

$$
\pi(a|s) =
\left\\{ 
\begin{array}{}
a & \( x > 1-ε) \\\
otherwise & \( x \leq ε)
\end{array}
\right.
$$

# AlphaGoでの応用

　AlphaGoは強化学習を応用して世界最強となったGoogle/DeepMindが開発した囲碁プログラムです。ここでは、非常に簡単にですが、AlphaGoの中でどのように強化学習が使われているか説明します。

　AlphaGoでは計算量を削減しながら最善手を算出するため、大きく先読みを行うため、盤面の優劣を評価する「評価関数(value network)」と、有力な指し手を検索するための「方策関数(Policy network)」が組み込まれています。それぞれの関数は、譜面画像を入力とした13層のCNNによって表現されています。ここでは、Policy Networkの学習方法の概要を説明します。

## 教師あり学習でプロ棋士の指し方を学習
　AlphaGoでは、まずPolicy Networkについて、プロ棋士の対戦データベース（約16万局/3000万譜面)を教師データとして用いて学習させています。これにより、上級者の指し手を模倣したPolicy Networkが作成されます。


## 強化学習で学習モデルを強化
　教師あり学習だけでは、人間を超える性能を出すことはできません。そのため、AlphaGoでは教師あり学習で学習させたモデル同士を対戦させてPolicy Networkの性能を向上させています。まず初めに、強化学習で用いるモデルを教師あり学習で学習させたモデルの重みで初期化します。その後、教師あり学習のモデルと、強化学習で作成したモデルをランダムに選択し対戦させます。ランダムに選択する理由は、これまで最強と思っていた戦略以外の新たな戦略を発見させるためです。この学習で手に入れたPolicy Networkを使うことで、先読みすることなく次の最善の一手(行動a)を算出しています。これはモンテカルロ法と同じ考え方です。

　このように、囲碁のような状態が爆発的に多い課題に対しても強化学習が効率的に収束するように、教師あり学習による手法とブレンドしながら学習を行い性能を安定的に向上させています。この結果、AlphaGoは世界最強であったイ・セドル九段を打ち負かし、現在では人間では勝つ事ができないと言われるまでに性能向上することができています。