引き続き強化学習の復習用の記事です。（以前の記事 : #1 #2）
強化学習の本でよく出てくるベルマン方程式とQ Learningについて復習します。
ベルマン方程式（Bellman equation）
まずは強化学習でよく出てくるベルマン方程式に関して触れます。発展的な内容でもずっと出てくる大切な内容になります。
強化学習の目的として、報酬を最大化する、というものがあります。
前回扱ったCartPoleのように単純な環境であれば、シンプルにAgentが取った行動から獲得できた報酬を積み上げていくだけでも何とかなりますが、現実の問題ではそこまでシンプルなものはあまりありません。
たとえば、ダンジョンに宝箱があり、それを取る判断をして報酬を獲得したとします。直近の行動による報酬だけ考えれば、報酬を獲得できたのでこれは好ましい判断となります。
しかしながら、もしかしたらその宝箱の部屋には実はトラップが仕掛けてあって、次の行動として部屋から出ようとした際にトラップが発動して手痛い損害を受ける可能性があります。トータルで見ると損害の方が多くなるかもしれません。
そういった際に人間ならどうするのか。例えば、以下のようなことが考えられます。
- 状況からトラップが仕掛けられていそうかどうかを予測して、宝箱を取るべきか取らないべきかを判断する。
- 仮にトラップなどがあったとしても、状況から予測して少ない損害で獲得できそうか判断する。
このように、普通は行動の際には将来に対する予測（推論）を挟んで、リスクとリターンを省みて、どうすれば一番利益を最大化できるかを考えるはずです。
この推論部分の最適化を担うのがベルマン方程式です。
ベルマン方程式を使うことで、各状況でAgentが利益をなるべく大きくするためにどのように行動すべきかのかが分かります。
数式で表すと以下のようになります。
\tag{式1}
V(s) = \underset{a}{\textrm{max}}
(R(s, a) + \gamma\ V(s'))
- $s$はstate、つまり現在の状態を表します。
- $a$はaction、つまり選択する行動を表します。
- $V(s)$は、推論結果を加味した、想定される報酬値です。
- $R(s, a)$は現在の状態（$s$）における行動($a$)における報酬値、つまりその行動ですぐに獲得できる報酬値を表します。
- $s'$は将来の状態を表します。
- $V(s')$は将来の状態に対する、獲得できる報酬値の予測値です。将来の値の推論値なので、算出した時点では100％合っている、という値ではありません。
- $\gamma$はハイパーパラメーターです。discounting factorとも言われ、将来の報酬値に対する減退率として使われます。通常は0.9や0.99といった小さな値が設定されます。
- 前述の内容を加味して、$\underset{a}{\textrm{max}}(R(s, a) + \gamma\ V(s'))$という式を見ると、「直近で得られた報酬」 + 「将来得られる報酬の推論値（減退率を加味）」した値が最大(max)になるように行動を取る、という意味になります。
$\gamma$に関してもう少し補足しておきます。
この値は将来になればなるほど、報酬値が小さくなるように設定されます。
たとえば、$\gamma$が0.9として、余分なステップが1個あるたびに0.9が乗算されるので、未来の報酬が100として、90、81、72.9...といった具合に未来の報酬の貢献度が低くなっていきます。
ダンジョンの例で考えてみましょう。
宝箱があって、トラップもないとします。その状況では、なるべく短時間でその宝箱まで到達した方が好ましいと言えます。迷って何度も何度も行ったり来たりしてから宝箱に到達するよりも、さっさとそこまで到達して次の宝箱の探索に移るなり、ダンジョンから脱出するなりした方が、時間当たりの稼ぎが良くなります。
$\gamma$を設けることで、Agentになるべく短時間で高い報酬を獲得するように学習させることができます。これがないと、Agentがダンジョンで迷っていても最終的に獲得できる報酬が一緒になるため、「迷っても迷わなくても変わらない」と学習してしまいます。
ダンジョンで例を上げましたが、現実問題でも色々当てはまります。例えば株取引であれば、1年で10万円のリターンを得られるのと、5年で10万円のリターンを得られるのでは、1年で獲得できた方が好ましいのは自明です。最終的に得られる報酬が一緒なので、どちらでも変わらないとAgentに学習されてしまうのでは困ります。
このベルマン方程式を踏まえ、DQN（Deep Q-Learning）などでよく聞くQに関して深掘りします。
ダンジョンで例えるQとQ Learning
※理解が浅いので、誤解している点などはコメントなどでご指摘ください。
※ダンジョンで例える理由は何となくです。深い意味はありません。
そもそもQとは何なのか？
What is Qのビデオによると、以下のような式で表されています。
\tag{式2}
Q[s, a] = \textrm{Immediate reward + Discounted reward}
sやaの定義はベルマン方程式のところで出てきたものと同じです。Discounted rewardのところも、前述の$\gamma$が絡むところと同じ定義となります。
つまり、Qは対象の状況(s)における選択した行動(a)における、即時で獲得できる報酬(Immediate reward) + 減退率を加味した将来の報酬の推論値（Discounted reward）となります。
このQをどのように使っていくのか？という点を考えてみます。
まず前提として、Agentの行動の原則となる、強化学習におけるポリシーを考慮します。
ポリシーは、状況(s)が〇〇だったら××(行動:a)をする、といったものです。
たとえば、ダンジョンで宝箱を見つけた時(状況)に、「ほぼほぼ罠が無さそうなので、宝箱を取りに行く」とか「罠の確率も結構ありそうだから安全を取って宝箱は見送る」といったような行動に対する条件がポリシーです。
この状況sにおけるQを使ったポリシーを$\pi(s)$とします。
$\pi(s)$は以下のような式で表されます。
\tag{式3}
\pi(s) = \textrm{argmax}_a (Q[s, a])
つまり、その状況(s)においてQが最大になる行動を取る、ということです。
Qが即時の報酬と減退率を加味した将来の報酬の合計値なので、このポリシーは即時の報酬 + なるべく短い期間での将来の報酬を最大化する行動を選択する、ということになります。
このQですが、もちろん確率に依存した将来の値の推論などが必要になりますし、将来の報酬をなるべく短くする、といっても様々な状況が分からないと良いポリシーにすることはできません。
ダンジョンに初めて挑戦した際に、そもそも地図や罠の情報などがなければ最短のルートや宝箱の位置が分からず、期間をなるべく短くするというのはできない、且つどうすれば報酬が最大化できるのか分からない、ということになります。
この点を解決するため、ポリシーを好ましいものにするため、学習（Q Learning）を挟みます。
Q Learning
Qの更新（学習・最適化）のためのQ Learningは以下の式で表されます。
\tag{式4}
Q(s_t, a_t) +=
\alpha\
[r_{t + 1} + \gamma V(s_{t + 1}) - Q(s_t, a_t)]
- 学習のために、何度も何度も次のステップに進んだりを繰り返すことになります。$t$の値は、そのステップ番号と考えてください。
- $Q(s_t, a_t)$は、とあるステップにおける、状況sでの行動aのQの値です。
- $r_{t + 1}$は次のステップにおける即時の報酬です。$t + 1$となっていることから分かるように、次のステップが対象となっていることに注意してください。
- $\gamma V(s_{t + 1})$は次のステップにおける、減退率を加味した将来獲得できると思われる報酬のQです。もちろん、将来の段階では取れる行動が多くあるので、その中でもQが最大になる選択肢を選択した際の値となります。
- $Q(s_t, a_t)$は、現在のステップにおけるQです。Qの更新で 加算（+=）となっているので、差分だけ加算したいので、減算する形で設定されています。
- []の括弧の前にある$\alpha$は学習率です。行動の$a$と紛らわしいですが別ものなので注意してください。一度の更新量を低くすることで学習がうまくいくように設定されるハイパーパラメーターです。通常は0に近い値（0.xなど）が指定されます。学習率に関しては通常のディープラーニングと似たようなものなので割愛します。
これだけだと式のイメージが付きにくいので、以下のように2×2の部屋を持つマップで考えてみましょう。相互に隣接する位置に通路が繫がっているダンジョンのマップだと考えてください。
|
【$s_1$】 $a_2$→
↓$a_3$ |
←$a_4$ 【$s_2$】
↓$a_3$ |
|
↑$a_1$
【$s_3$】 $a_2$→ |
↑$a_1$
←$a_4$ 【$s_4$】 |
それぞれ4つの部屋が状況(s)、つまり$s_1$～$s_4$です。
各部屋への移動が行動(a)で、上への移動が$a_1$、右が$a_2$、下が$a_3$、左が$a_4$としています。部屋(s)によっては移動できない方向が存在します（＝選択できない$a$がある）。
Qはそれぞれの状況(s)、選択できる行動(a)ごとに存在するので、Qをマップ上に記載すると以下のようになります。
|
【$s_1$】 $Q(s_1, a_2)$→
↓$Q(s_1, a_3)$ |
←$Q(s_2, a_4)$ 【$s_2$】
↓$Q(s_2, a_3)$ |
|
↑$Q(s_3, a_1)$
【$s_3$】 $Q(s_3, a_2)$→ |
↑$Q(s_4, a_1)$
←$Q(s_4, a_4)$ 【$s_4$】 |
ゲームのキャラクター（Agent）が$s_1$の部屋に居るとしましょう。
右に進むべきでしょうか？それとも下に進むべきでしょうか？
前述した通り、QはAgentの行動を決定するポリシーとして使われると述べました。
そのため、キャラクターがどちらの移動を選択するかはそれぞれのQによって決まります。
仮に右の部屋への移動のQが10、下の部屋への移動のQが12だとします。そうするとキャラクター(Agent)は下の部屋への移動を選択するようになります。
|
【$s_1$】 $Q(s_1, a_2) = 10$→
Agent（Qが高い下への移動を選択） ↓$Q(s_1, a_3) = 12$ |
←$Q(s_2, a_4)$ 【$s_2$】
↓$Q(s_2, a_3)$ |
|
↑$Q(s_3, a_1)$
【$s_3$】 $Q(s_3, a_2)$→ |
↑$Q(s_4, a_1)$
←$Q(s_4, a_4)$ 【$s_4$】 |
式4でいうと、この時の$Q(s_1, a_3)$が$Q(s_t, a_t)$に該当します。
つまり、式4に準じて、このタイミングでQ Learningで$Q(s_1, a_3)$の値が加算（更新）されることになります。
仮に移動先の$s_3$に宝箱があったとします。報酬(r)を5としましょう。
|
【$s_1$】 $Q(s_1, a_2) = 10$→
キャラクター（Qが高い下への移動を選択） ↓$Q(s_1, a_3) = 12$ |
←$Q(s_2, a_4)$ 【$s_2$】
↓$Q(s_2, a_3)$ |
|
↑$Q(s_3, a_1)$
宝箱（$r=5$） 【$s_3$】 $Q(s_3, a_2)$→ |
↑$Q(s_4, a_1)$
←$Q(s_4, a_4)$ 【$s_4$】 |
この宝箱は「次のステップにおける即時の報酬」に該当します。
式4だと、$r_{t + 1}$の個所が該当します。
Qの値の更新時には、次のステップ（$t + 1$）の値を見ると前述していた点はこういった参照となります。
今回は宝箱なので$Q(s_1, a_3)$がプラスになる形で更新されますが、仮に左下の$s_3$の部屋に罠しかなかったとします。
そうすると即時の報酬(r)がマイナスとなるため、$Q(s_1, a_3)$の値が減少します。
減少するということは、次回の探索時に左上の$s_1$の部屋から下の部屋には移動しにくくなる、ということを意味します。（右への移動のQの方が高くなれば、右が選択されるようになります）
加えて、右下の$s_4$の部屋にもう一つ宝箱があったとしましょう。
また、左下の部屋($s_3$)から右下の部屋($s_4$)への移動のQの値（$Q(s_3, a_2)$）が14だとします。（14という値は適当ですが、基本的に減退率などを加味すると$Q(s_1, a_3)$よりも少し大きな値になったりする・・筈。）
|
【$s_1$】 $Q(s_1, a_2) = 10$→
キャラクター（Qが高い下への移動を選択） ↓$Q(s_1, a_3) = 12$ |
←$Q(s_2, a_4)$ 【$s_2$】
↓$Q(s_2, a_3)$ |
|
↑$Q(s_3, a_1)$
宝箱（r=5） 【$s_3$】 $Q(s_3, a_2) = 14$→ |
↑$Q(s_4, a_1)$
宝箱（$r=3$） ←$Q(s_4, a_4)$ 【$s_4$】 |
他に宝箱は存在しないと推論した際に、この値は「下に進むことによって将来得られる報酬の最大値」の部分が該当します。
式4の中では、$\gamma V(s_{t + 1})$の部分が該当します。
$\gamma$は減退率であり、未来になればなるほど、将来の報酬によるQの更新量が小さくなるので、「最大値を選択する」という計算の都合、そういった行動(a)は取られなくなります。
たとえば、$\gamma$に0.9を設定したとして、左上の$s_1$の部屋と左下の$s_3$の部屋を2回ずつほど行ったり来たりしてから右下の$s_4$の部屋に移動したとしましょう。
そうすると、$s_1 → s_3 → s_1 → s_3 → s_4$という流れになり、獲得できる将来の報酬は0.9 * 0.9 * 0.9 * 14(将来の報酬のQ)となります。
$s_1 → s_3 → s_4$とストレートに移動した場合には0.9 * 14となり、こちらの方が大きな値となるのでこちらの行動が選択されます。
改めて、この流れを式4に当てはめてみましょう。学習率$α$は0.1とします。
\tag{式5}
\begin{array}{ll}
\underset{s_1の部屋の下への移動a_3のQ}{Q(s_1, a_3)}
+= &
\underset{学習率\alpha}{0.1}
\\
& ×\ [
\ \ \underset{次のステップの即時の報酬r_{t + 1}}{5}
\\ &
\ \ \ + \underset{将来の1ステップ分の報酬減退率\gamma}{0.9}
\\ &
\ \ \ ×\underset{次のステップにおける将来の報酬の最大のQの値V(s_{t + 1})}{14}
\\ &
\ \ \ - \underset{s_1の部屋の下への移動a_3のQ}{12}
\\ &
\ \ \ ]\\ &
= 12.56
\end{array}
0.56だけ、$Q(s_1, a_3)$の値が更新となりました。増加したので、このルートは好ましい、と学習したことになります。
このようなステップを何度も何度も繰り返し実行していくことで、「最適な行動はどうするべきなのか」というポリシーが好ましい値に更新されていきます。
（今回の例では一つの行動のQのみを取り上げましたが、実際に学習する際には様々な状態(s)、行動(a)に対してのQの更新が実行されます）
ランダム性の担保のためのエプシロン
前述した更新処理の過程で、AgentはQが高い行動を取る、と述べました。
しかしこれにはAgentが決まりきった行動ばかり取るようになる、という問題点があります。
たとえば、前述の例で言えば、右上の$s_2$の部屋を探索する前に、左下・そして右下に移動するポリシーが好ましいと判断して、学習中ずっと右上に移動しないパターンが発生するかもしれません。
もし右上の部屋($s_2$)にとても良い内容の宝箱があったとすると、探索せずに学習が終わってしまうのは好ましくありません。
そこで、$\epsilon$（エプシロン）というパラメーターが使われます。
0.0～1.0で設定され、たとえば$\epsilon$が0.2であれば20％はランダムな移動を選択し、80％はQに応じた移動を選択する、といった振る舞いになります。
ダンジョンで、報酬をある程度しっかり効率よく宝箱を取りつつ、もしかしたら新しい発見があるかもしれないので、たまには知らないルートを通ってみる、といった具合でしょうか。
この方法は、Epsilon-Greedy法などと呼ばれます。
また、この$\epsilon$は、初期の方は高い値で、後半になるほど0に近づけていく、という方法が取られたりもします（最初は1からスタートし、最終的に0.02辺りまで小さくするなど）。
ダンジョンで例えると、最初は未踏のダンジョンなので色々ランダムに探索して調べて、ある程度慣れて効率よく探索できるようになったらランダム性を薄める（Qに依存するポリシーで探索する）、といった具合です。
※次回は、恐らくこれらの手法をPyTorchでコードで表現する記事など書けたらと思います。
※デザイン方面の非理系出身の人間なので突っ込みどころがあっても許してください。