はじめに
先の記事でベルマン最適方程式について書いた。今回は、この方程式とQ-Learningとを関連づけてみたい。最後にDQNについて少し言及する。
ベルマン最適方程式
行動価値関数に対するベルマン最適方程式は次式で与えられた。 \begin{equation} Q^{*}(s,a)=\sum_{s^{\prime}} P(s^{\prime}|s,a)\left[r(s,a,s^{\prime})+\gamma \max_{a^{\prime}}Q^{*}(s^{\prime},a^{\prime})\right] \label{eq1} \end{equation} ここで、Q^{*}(s,a)は最適行動価値関数、sとaはそれぞれ状態と行動を表す観測値を表す。P(s^{\prime}|s,a)は(s,a)が実現しているときs^{\prime}が起こる確率、r(s,a,s^{\prime})は(s,a,s^{\prime})が実現するときの報酬を表す。\gammaは収益を定義するときに導入した割引率である。
Q-Learningとの関係
Q-Learningでは行動価値関数Q(s,a)を次式で更新していく。 \begin{equation} Q(s,a) \leftarrow (1-\alpha)Q(s,a)+\alpha\left[r(s,a,s^{\prime})+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})\right] \label{eq3} \end{equation} ここで、\alphaは学習率である。現在の状態sとこの状態の下で選択した行動aから次の状態s^{\prime} を決定論的に決めたあと、上式を用いてQ(s,a)を更新することに注意する。上式右辺を変形すると次式を得る。 \begin{equation} Q(s,a) \leftarrow Q(s,a)+\alpha\left[r(s,a,s^{\prime})+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})-Q(s,a)\right] \end{equation} 更新を繰り返しQ(s,a)が収束したとき、上式右辺の第2項は0になるはずである。 \begin{equation} r(s,a,s^{\prime})+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})-Q(s,a)=0 \end{equation} これより \begin{equation} Q(s,a)=r(s,a,s^{\prime})+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime}) \label{eq2} \end{equation} を得る。ここで、式(\ref{eq1})と式(\ref{eq2})を見比べて見ると、とても良く似ていることに気づく。違いは、式(\ref{eq1})では遷移確率P(s^{\prime}|s,a)が考慮されており、sの次に取り得る状態s^{\prime}について期待値が取られていることである。一方、式(\ref{eq2})では状態s^{\prime}は決定論的に決められる。
Deep Q Network（DQN）
Q-Learningでは式(\ref{eq3})を用いてQを更新する。アルゴリズムの手順は以下のようなる。
- 現在の状態sが与えられる。
- 現在までに確定しているQ値の表を見て、sのときQ値を最大にする行動aを求める。ただし、ランダムに行動を選択する仕組みも取り入れ、他にあるかしれないより良い行動が見つかるようにする。
- (s,a)の下で次の状態s^{\prime}を決める。
- 現在までに確定しているQ値の表を見て、s^{\prime}のとき最大となるQ値を求め、式(\ref{eq3})を用いてQ値を更新する。
