理系リアルタイム

大学院生の情報ブログ

テクノロジー 人工知能・機械学習

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

投稿日:8月 26, 2019 更新日:

みなさんこんにちは。

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

この記事では、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】で考察します。

-テクノロジー, 人工知能・機械学習

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

【機械学習】何でもかんでも深層学習、機械学習を使えば良いってもんじゃない

現代はAI(artificial intelligence,人工知能)ブームです。 ニュースでも「人工知能を使った、、、」、「教育にもAIが、、、」などと、頻繁にこの言葉を聞くようになりました。 今回 …

趣味でやるのはいいが、機械学習を本業にするのは過酷な理由 3選

どうもこんにちは。 題名通りですが、今回は機械学習にばかり目を向けていると痛い目に合う理由を述べたいと思います。 最近、本当に多くのひとが機械学習とか、深層学習に参加しています。 Twitterなどを …

【Google AdSense】【ブログ】初の申請後、たった5時間でGoogeleアドセンス審査が通ったブログの条件

Googleユーザーのみなさんこんばんは!ATSです!! みなさん、ググってますか?? 世の中で使われてる検索エンジンはGoogleかBingのほぼ2択ですし、Googleエンジンが圧倒してますから、 …

プログラミングできるお手軽(安い)トイドローンTelloがおすすめ!

みなさんこんにちは。 最近、ドローンを飛ばそうと思い立ちました。 ちょうど友達が小型のドローンを持っていたので、遊ばせていただくことにしました。 そこで今回は、プログラミングできて、かつ航空法にも引っ …

【機械学習初心者】機械学習(特に強化学習)を勉強中の僕が今読んでいる参考書まとめ 3選

みなさん、こんにちは!

理系リアルタイム 管理人

理系大学院生。

名古屋大学大学院工学研究科。

いつか人工衛星を打ち上げたいと夢見ている。生息地は度々変わるので不明。興味があること→物理/laser/機械学習/backpacker/ドローン/海外移住

理系リアルタイムでは、大学生・大学院院生に知ってもらいたい情報、体験を発信しています!!気になることがあれば、お気軽にご連絡ください。

管理人のTwitter もよろしくお願いします!!