【強化学習】Q-Learningの更新式から結果考察まで。ハイパーパラメータ依存性【Part1】

テクノロジー

みなさんこんにちは。

昔、こんな記事を書きました。

【機械学習】機械学習のプログラミング実装だけなら誰でもすぐ出来るので理論を学びたいと思いました。
はい、どうも、おはようございます。
atsblog.org
2019.01.17

この記事では、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では、「その状態 s に、行動 a をすることに、どれだけ価値があるか」を表した行動価値関数 Q(s,a) を行動しながら更新していくことで、学習を行います。

強化学習理論

Q-Learningについて述べる前に、強化学習の理論について触れておきます。

マルコフ決定過程（MDP）によるモデル化

マルコフ決定過程によって、強化学習をモデル化していきます（マルコフ決定過程に関しては、Wikipediaなどを参照してください）。

以下では、時刻 t における状態を s_t 、行動を a_t 、遷移確率を P_{s,s'}^{a} = P(s'|s_t = s,a_t = a) とし、方策を \pi(s,a) = P(a|s_t = s)とします。

ここで、方策 \pi(s,a) とは、状態が s のとき、どのように行動 a をとるか、という意味を表します。

利得

利得 R_(t ) は、未来の報酬獲得にどの程度貢献したかを表し、割引率 \gamma ( \gamma は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}\]

これは、現在に近いときに得られた利益ほど、利得に対する寄与が大きく、それ以降は割り引いて考えていることになります。

状態価値関数

「方策 \pi をとったとき、その状態にどれだけ価値があるか？」を表す状態価値関数は、以下のようになります。

    \[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')]\]

ここで、 R_{s,s'}^{a} = E\{r_{t+1}|s_t = s, a_t= a, s_{t+1} = s'\} です。

この式の詳しい導出は、今さら聞けない強化学習（1）：状態価値関数とBellman方程式などをご覧ください。

行動価値関数

「方策 \pi に従って、この状態でこの行動をとることにどれだけ価値があるか？」を表す行動価値関数は、以下のように表すことができます。

    \[Q^{\pi}(s, a) = \sum_{s'} P_{s,s'}^{a}[ R_{s,s'}^{a}+\gamma V^{\pi}(s')]\]

一方で、状態価値関数は、

    \[V^{\pi}(s) = \sum_{a} \pi(s,a) Q^{\pi}(s, a)\]

と表せるので、行動価値関数は、以下のように変形することができます。

    \[\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') ]\]

これは、一種のBellman方程式となっています。

強化学習における行動価値関数

一般的には、強化学習で解きたい問題では、遷移確率 P_{s,s'}^{a} が分りません。

それはそうですよね。次にどの状態に遷移するのか、わからない状況で学習するのが強化学習ですもんね。

ここで、方策について考えます。最も良い方策 \pi^{\ast}(s) は、行動価値関数を最大にするような行動をすれば良いはずなので、

\pi^{\ast}(s) = argmax Q(s,a)

と表せます。

また、このとき、状態価値関数は

    \[V^{\ast}(s) = \max_{a} Q(s,a)\]

です。

これらより、最適（と思われる）行動価値関数は、以下のように変形することができます。

最適行動価値関数 Q^{\ast}(s, a)

    \[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')\]

ここで、r_{t+1} = r' と表記しています。

Q-Learningの更新式

Q-Learningでは、TD学習（時間差分学習）として、行動価値関数の更新式を考えます。

学習率を \alpha とすると、TD学習の更新式は目標関数（ここでは、最適行動価値関数 Q^{\ast}(s,a) ）と現在の関数の差を重みを付けて更新すればよいので、

    \[Q(s,a) \leftarrow Q(s,a)+\alpha[Q^{\ast}(s,a)-Q(s,a)]\]

つまり、Q-Learningの更新式は、以下のようになります。

Q-Learningの更新式

    \[Q(s,a) \leftarrow Q(s,a)+\alpha[r'+\gamma \max _{}Q(s',a')-Q(s,a)]\]

この関数は、 状態 s と行動 a の関数となっているので、Q-Learningは二次元の表（テーブル）の値を更新して学習していくと考えることができます。この表を、Qテーブルといいます。

直感的に学習の様子を理解したい方は、 https://s3.amazonaws.com/ml-class/notes/MDPIntro.pdf をみると良いかと思います。

次回は、学習結果と考察

長くなりましたので、ハイパーパラメータをいじったときの学習結果の変化については、次の記事【Part2】で考察します。

【強化学習】Q-Learningの更新式から結果考察まで。ハイパーパラメータ依存性【Part2】
前回の記事で、Q-Learningの更新式の説明を行いました。そして、今回は、実際にQ-Learningで学習した結果をまとめたいと思います。設定学習する環境は、...
atsblog.org
2019.08.29

コメント

タイトルとURLをコピーしました