第五夜は、第四夜の疑問、たくさんあったがまず基本的な理論？を取り上げたい。
やったこと
（１）ちょっと理論
（２）何を学習しているのか
（１）ちょっと理論
DQNの理論ってみんなが同じようなこと書いているが、どうもしっくりこないのでウワンなりに大切と思われることだけ端折りつつ書きたいと思う。何か見えてくることを期待して。
※ということでこの項は全て参考の記載をよく読んで自己責任でご利用ください
【参考】
①DQNの生い立ち ＋ Deep Q-NetworkをChainerで書いた
②強化学習入門 ～これから強化学習を学びたい人のための基礎知識～
③人工知能概論 7
④ベルマン方程式@Wikipedia
⑤DQNからRainbowまで 〜深層強化学習の最新動向〜
⑥マルコフ決定過程@Wikipedia
⑦急いで学ぶDQN
基本的な考え方
dqnの基本という意味では、以下のベルマン方程式が基礎になっています。
Wikipediaより
決定過程(MDP) において、ベルマン方程式は期待報酬（expected reward）に関する再帰的な関係を表現する。例えば、特定の状態 s において方策 π を適用した際の期待報酬は以下のベルマン方程式を満たす:
{\displaystyle V^{\pi }(s)=R(s,\pi (s))+\gamma \sum _{s'}P(s'|s,\pi (s))V^{\pi }(s').\ }
この方程式は、ある方策 π のもとで得られる期待報酬を表している。
最適な方策を採用した場合の方程式が最適ベルマン方程式である:
{\displaystyle V^{*}(s)=\max _{a}{\Big \{}R(s,a)+\gamma \sum _{s'}P(s'|s,a)V^{*}(s'){\Big \}}.}
この式は、最適な行動をとった場合に得られる期待報酬を表す。
なお、決定過程(MDP)とはMarkov Decision Processについて参考⑥から引用
「マルコフ決定過程は離散時間における確率制御過程 (stochastic control process) である。 各時刻において過程 (process) はある状態 (state) を取り、意思決定者 (decision maker) はその状態において利用可能な行動 (action) を任意に選択する。 その後過程はランダムに新しい状態へと遷移し、その際に意思決定者は状態遷移に対応した報酬 (reward) を受けとる。 」
強化学習については以下のとおり記載されている
任意の $π ′$ および $s ∈ S$ に対し$ V^{\pi ^* }(s)\geq V^{\pi '}(s)$ を満たす政策 $\pi ^*$ を最適政策 (optimal policy) と呼ぶ。
$\pi ^* $を採用したときの状態価値関数の最大値$V^{*}(s)=\max _{\pi }V^{\pi }(s)$ は次のベルマン方程式を満たす[3]．
V^{*}(s)=\max _{a\in A}\sum _{s'\in S}T(s,a,s'){\Big (}R(s,a,s')+\gamma V^{*}(s'){\Big )}
「状態遷移確率 $ {\displaystyle T(s,a,s')} $や報酬関数 $ {\displaystyle R(s,a,s')} $が未知の場合，環境との相互作用を通じてこれらの情報を得ながら行動を決定する必要がしばしば生じる．このような問題は強化学習の枠組みで議論される[6]．
強化学習における代表的な学習アルゴリズムはQ学習と呼ばれるものである。 Q学習では、行動価値関数 (action-value function) と呼ばれる関数 $ {\displaystyle Q^{\pi }(s,a)} $ に着目する。ここで $ {\displaystyle Q^{\pi }(s,a)} $は次のように定義される:
Q^{\pi }(s,a)=\mathbb {E} _{\pi }[\sum _{t=0}^{\infty }\gamma ^{t}r_{t+1}|s_{0}=s,a_{0}=a]
いま，最適政策のもとでの行動価値関数
{\displaystyle Q^{*}(s,a)=\max _{\pi }Q^{\pi }(s,a)}
は
{\displaystyle V^{*}(s)=\max _{a}Q^{*}(s,a)}
を満たす。 すなわち、$ {\displaystyle Q^{*}} $を学習することができれば（モデルのパラメータを直接求めることなく）最適政策を獲得することができる。 Q学習では、各試行における遷移前後の状態と入力、および試行で得られる即時報酬の実現値をもとに $ {\displaystyle Q(s,a)} $の値を逐次更新する。 実際の学習プロセスでは、すべての状態を十分サンプリングするため確率的なゆらぎを含むよう学習時の行動が選択される。 」
参考②から
（ちょっと文言端折っています）
「価値を最大化させるようにエージェントを学習させる
ある状態 s においてある行動 a を取った時の価値」の一番高い行動を選択すればよい
Q値は「報酬」ではなく「価値」である。つまり、Q値とは短期的な報酬ではなく、長期的な意味での価値を値として持っている関数です。」
Q値 を Q(s,a) と書く。
Q学習の基本方程式は以下のようなものです。
Q(s_t ,a_t )←(1-α)Q(s_t ,a_t )+α(r_{t+1} +γmax_{a_{t+1}} Q(s_{t+1} ,a_{ t+1} ))
ここで$r_{t+1} +γmax_{a_{t+1}} Q(s_{t+1} ,a_{ t+1} )$は試行錯誤により推定する最大価値である。
つまり、時刻tにおける状態 $ s_t $ ,行動 $ a_t $ のときの価値Qは、次の時刻t+1における(報酬＋次の時刻の価値の最大値＊割引率)との重み付き平均で得られる。
そして、式変形すると
Q(s_t ,a_t )←Q(s_t ,a_t )+α(r_{t+1} +γmax_{a_{t+1}} Q(s_{t+1} ,a_{ t+1} )-Q(s_t ,a_t ))
そして、参考⑥によれば、以下がDQNにおける勾配降下法の式となります。
※ノーテーションや議論詳細については、参考⑦をみてください
($η ⇒ α$であり、また、$E^{(i)}(w (i) )$は$w(i)$をパラメータとする誤差関数）
w^{(i+1)} ←w^{(i)} −ηE(s,a,r,s^′ )[(r+γmax_{a^′} Q(s^′ ,a^′ ;w^{(i−1)} )−Q(s,a;w^{(i)} ))∇_{w^{(i)}} Q(s,a;w^{(i)} )]
Sarsaの基本方程式
参考②より
「Q学習では、期待値の見積もりを現在推定されている値の最大値で置き換えましたが、Sarsa の場合、実際に行動してみたらどうなったかを使って期待値の見積もりを置き換えます。」
Q(s_t ,a_t )←Q(s_t ,a_t )+α(r_{t+1} +γQ(s_{t+1} ,a_{t+1})−Q(s_t ,a_t ))
モンテカルロ法
参考②より
「モンテカルロ法はQ学習やSarsaとは違い、Q値の更新のときに「次の時点のQ値」を用いません。
代わりに、とにかく何らかの報酬が得られるまで行動をしてみて、その報酬値を知ってから、辿ってきた状態と行動に対してその報酬を分配していきます。」
※なんとなく、将棋AIのMCTSと似たような考え方で安心する。
つまり表現は以下のとおり、
Returns(s,a)←append(Returns(s,a),r) \\
Q(s,a)←average(Returns(s,a))
まとめ
・強化学習とdqnの理論的な基礎をちょっと見てみた
・具体的なコードと合わせてみようと思う
・何を学習しているのかは依然不明だけど、どうやら行動価値関数のようだ（笑）
ベルマン方程式を基礎として、状態遷移確率 $ {\displaystyle T(s,a,s')} $や報酬関数 $ {\displaystyle R(s,a,s')} $が未知の場合，環境との相互作用を通じてこれらの情報を得ながら行動を決定するのが強化学習