みなさんこんにちは。
昔、こんな記事を書きました。
この記事では、Python+ChainerRLを用いて深層強化学習（DQN）を行いました。
記事中では、DQNの前段階として、普通の強化学習であるQ-Learnigのアルゴリズムも作ってみました。
今回は、そのQ-Learningについてまとめようと思います。
Q-Learningとは
強化学習についての説明は他に譲るとして、ここではQ-Learningについて説明します。
Q-Learningは、強化学習に使われるアルゴリズムの一つで、基本的なアルゴリズムといえます。強化学習に使われる基本的なアルゴリズムとしては、他にはSRASA、モンテカルロ法などがあります。
強化学習のアルゴリズムにおけるQ-Learningの立ち位置は、以下の図のような感じです。
Qiita：これから強化学習を勉強する人のための「強化学習アルゴリズム・マップ」と、実装例まとめ
https://qiita.com/sugulu/items/3c7d6cbe600d455e853b から引用
Q-Learningでは、「その状態 
に、行動 
をすることに、どれだけ価値があるか」を表した行動価値関数 
を行動しながら更新していくことで、学習を行います。
強化学習理論
Q-Learningについて述べる前に、強化学習の理論について触れておきます。
マルコフ決定過程（MDP）によるモデル化
マルコフ決定過程によって、強化学習をモデル化していきます（マルコフ決定過程に関しては、Wikipediaなどを参照してください）。
以下では、時刻 
における状態を 
、行動を 
、遷移確率を 
とし、方策を 
とします。
ここで、方策 
とは、状態が のとき、どのように行動 をとるか、という意味を表します。
利得
利得 
は、未来の報酬獲得にどの程度貢献したかを表し、割引率 
( は0から1の値をとり、よく大きな値（0.9~0.99）が使われる）を用いて、以下の式のように表します。
![\[R_(t )= r_{t+1}+\gamma r_{t+2}+\gamma^2 r_{t+3}+ \cdots =\sum_{k=0}^{\infty}{\gamma ^k r_{t+k+1}\]](https://atsblog.org/wp-content/ql-cache/quicklatex.com-21bb6a9d15c13d4c8882f914ff735ce5_l3.png "Rendered by QuickLaTeX.com")
これは、現在に近いときに得られた利益ほど、利得に対する寄与が大きく、それ以降は割り引いて考えていることになります。
状態価値関数
「方策 
をとったとき、その状態にどれだけ価値があるか？」を表す状態価値関数は、以下のようになります。
![\[V^{\pi}(s) = E\{R_t|s_t = s\} = \sum_{a} \pi(s,a) \sum_{s'} P_{s,s'}^{a}[ R_{s,s'}^{a}+\gamma V^{\pi}(s')]\]](https://atsblog.org/wp-content/ql-cache/quicklatex.com-e4a36eca8d38d4256b6ca9c57dafde48_l3.png "Rendered by QuickLaTeX.com")
ここで、
です。
この式の詳しい導出は、今さら聞けない強化学習（1）：状態価値関数とBellman方程式などをご覧ください。
行動価値関数
「方策 に従って、この状態でこの行動をとることにどれだけ価値があるか？」を表す行動価値関数は、以下のように表すことができます。
![\[Q^{\pi}(s, a) = \sum_{s'} P_{s,s'}^{a}[ R_{s,s'}^{a}+\gamma V^{\pi}(s')]\]](https://atsblog.org/wp-content/ql-cache/quicklatex.com-c86acc29146025a5cb015abc7ddca677_l3.png "Rendered by QuickLaTeX.com")
一方で、状態価値関数は、
![\[V^{\pi}(s) = \sum_{a} \pi(s,a) Q^{\pi}(s, a)\]](https://atsblog.org/wp-content/ql-cache/quicklatex.com-7751e95332234f247495d324043107dc_l3.png "Rendered by QuickLaTeX.com")
と表せるので、行動価値関数は、以下のように変形することができます。
![\[\therefore \quad Q^{\pi}(s, a) = \sum_{s'} P_{s,s'}^{a}[ R_{s,s'}^{a}+\gamma \sum_{a'} \pi(s',a') Q^{\pi}(s', a') ]\]](https://atsblog.org/wp-content/ql-cache/quicklatex.com-7c0fbc199b8dbdbf518d1842c046d7c9_l3.png "Rendered by QuickLaTeX.com")
これは、一種のBellman方程式となっています。
強化学習における行動価値関数
一般的には、強化学習で解きたい問題では、遷移確率 
が分りません。
それはそうですよね。次にどの状態に遷移するのか、わからない状況で学習するのが強化学習ですもんね。
ここで、方策について考えます。最も良い方策 
は、行動価値関数を最大にするような行動をすれば良いはずなので、
argmax
と表せます。
また、このとき、状態価値関数は
![\[V^{\ast}(s) = \max_{a} Q(s,a)\]](https://atsblog.org/wp-content/ql-cache/quicklatex.com-5dc6481e116e42994391c5ae0c53afa1_l3.png "Rendered by QuickLaTeX.com")
です。
これらより、最適（と思われる）行動価値関数は、以下のように変形することができます。
最適行動価値関数 
![\[Q^{\ast}(s, a) = \sum_{s'} P_{s,s'}^{a}[ R_{s,s'}^{a}+\gamma V^{\ast}(s')] = r_{t+1} + \gamma\max_{a'}Q(s',a')\]](https://atsblog.org/wp-content/ql-cache/quicklatex.com-276d9a08ac73825809318758a803408c_l3.png "Rendered by QuickLaTeX.com")
ここで、
と表記しています。
Q-Learningの更新式
Q-Learningでは、TD学習（時間差分学習）として、行動価値関数の更新式を考えます。
学習率を 
とすると、TD学習の更新式は目標関数（ここでは、最適行動価値関数 
）と現在の関数の差を重みを付けて更新すればよいので、
![\[Q(s,a) \leftarrow Q(s,a)+\alpha[Q^{\ast}(s,a)-Q(s,a)]\]](https://atsblog.org/wp-content/ql-cache/quicklatex.com-db23afb6c12a1f28623ba3dd96650e87_l3.png "Rendered by QuickLaTeX.com")
つまり、Q-Learningの更新式は、以下のようになります。
Q-Learningの更新式
![\[Q(s,a) \leftarrow Q(s,a)+\alpha[r'+\gamma \max _{}Q(s',a')-Q(s,a)]\]](https://atsblog.org/wp-content/ql-cache/quicklatex.com-fdcd63a4920e857e2b96806e0c9cafef_l3.png "Rendered by QuickLaTeX.com")
この関数は、 状態 と行動 の関数となっているので、Q-Learningは二次元の表（テーブル）の値を更新して学習していくと考えることができます。この表を、Qテーブルといいます。
直感的に学習の様子を理解したい方は、 https://s3.amazonaws.com/ml-class/notes/MDPIntro.pdf をみると良いかと思います。
次回は、学習結果と考察
長くなりましたので、ハイパーパラメータをいじったときの学習結果の変化については、次の記事【Part2】で考察します。
理系大学院生。
