かざんぶろぐ

だらだらと備忘録とってます

強化学習,DQNについて自分なりにまとめてみた

強化学習に関連するキーワードや手法についてのメモ。
最終的にはDeep Q-Learning、いわゆるDQNにも触れていこうと思う。

参考にさせていただいた記事、書籍

DQNの生い立ち + Deep Q-NetworkをChainerで書いた - Qiita
ゼロからDeepまで学ぶ強化学習 - Qiita
これからの強化学習 | 森北出版株式会社
正直参考記事、書籍を読めばこの記事はいらないくらいめちゃくちゃ詳しく書いてあるので、ぜひ参考にしてほしい。

強化学習

強化学習とは何かを簡潔にまとめると、「環境に置かれたエージェントが、環境との相互作用を通して、環境に応じた最適な方策を学習する手法」である。

エージェントが環境に行う作用を行動(action)といい、エージェントの行動によって変化する環境の要素を状態(state)という。

エージェントは環境から状態を受け取り、行動を決定し、環境がその行動に応じて変化。
さらに新しい状態をエージェントが受け取る。
このような環境とエージェントの相互作用を繰り返していく。

f:id:okuya-KAZAN:20171019134826p:plain


強化学習は他の機械学習と異なり、教師による答えがない。
その代わり、行動に対する「報酬」というものが存在する。
例えば、ある状態Sで行動A1をとったら報酬+1pt、行動A2をとったら報酬-1ptといった具合だ。

強化学習のキーワード

強化学習を勉強する上で欠かせないキーワードをまとめておく。

エージェント

行動する主体。環境から得られた観測結果をもとに行動を決定する。

環境

エージェントが決定した行動を受けて、次なる状態と報酬を決定し、エージェントに引き渡す。
環境の挙動は設計者の設計対象外。
ただし、報酬に関しては問題設定の一部として設計者が与える必要がある。

時間ステップとエピソード

時間ステップ

エージェントと環境の相互作用における基本的時間単位。1時間ステップの間に、エージェントは環境から状態や報酬を受け取り、それをもとに行動を決定して環境に引き渡す。

エピソード

タスクの開始から終了までの時間。
囲碁であれば碁盤に石がない状態から、試合が終了するまでがエピソードである。

マルコフ性

t+1ステップ目における状態は、tステップ目での状態と行動を使って、
P\bigl(S_{t+1}\mid S_t,A_t\bigr)で定められる。この時S_{t+1}は、S_{t-1}A_{t-1}などには依存せず、S_{t}A_{t}のみに依存して定まる。このように直前の状態のみで遷移確率が決まる性質をマルコフ性と呼ぶ。

方策

状態を入力として、行動を出力する行動決定のための関数。
方策は\piで表し、方策\piのもとである状態sにおけるある行動aが選択される確率を\pi\bigl(a\mid s\bigr)と表す。

最終目標は、エージェントが置かれた状態において、できるだけ多くの報酬得られるよう方策を設計していくこと。
もっと詳しく言うと、環境から得られる「報酬」「状態」から方策を改善していくこと(DQNでは方策の改善 -> NNのパラメータのチューニング)。

報酬、収益

ここでいう報酬というのは、ある行動を取った直後に得られる報酬(即時報酬)のことであるが、即時報酬の大きさだけを行動の指標にしてしまうと局所解に落ち込んでしまう危険性がある。

例えば、無人島に漂着した場合、周囲を探索するより、じっと座り込んでいる方が、体力の消耗が少ないので即時報酬は高い。
しかし、体力を使うという負の即時報酬を得ながらも探索を続けることで、食料を見つけ、結果的にじっと座ってるよりも大きな報酬を得られる可能性がある。

つまり、即時的には小さな報酬しか得られない行動でも、後にとても大きな報酬を得ることに繋がれば、その行動は全体としてみれば良い行動とみなせる。

よって、即時報酬だけでなく、その後に得られる全ての報酬の累積である収益を考える必要があり、強化学習においてエージェントは、「行動の選択を通して得られる収益の総和の最大化」を目的として学習していく。

収益にはそのまま報酬を足し合わせて定義されるものも存在するが、主には、未来にいくに従って割引されて定義されていく割引報酬和で収益が多く採用されているらしい。
割引報酬和とは、報酬を足し合わせる際に、未来の報酬ほど減衰させることで未来の不確実性を表現したものであり、時間ステップtでの収益G_tを、

G_t = \sum_{\tau=0}^{\infty} \gamma^{\tau}R_{t+1+\tau}=R_{t+1}+\gamma R_{t+2}+\gamma^{2}R_{t+3}+\cdots
のように定義する。
ここで\gamma\left(0\le\gamma\leq1\right)は割引率と呼ばれ、どれだけ未来を割引くかを表す定数である。

価値,行動価値関数

エージェントと環境との相互作用の中身は確率的に決定されてしまうため、収益も確率的に変動してしまう値となってしまう。
そのため収益は、方策を設計する際の行動の評価指標としては扱いづらい。

そこで、ある状態sから方策に従って行動を決定していった時に得られる収益の期待値を求め、それを価値と呼び、良い方策を設計する際の指標とする。

期待値をとることで、確率的に変動する報酬の平均的な値を算出することができる。
価値の中でも、ある状態sで行動aを選択した場合の収益の期待値を状態sにおける、行動aの行動価値と呼び、さらに行動価値を求める関数を行動価値関数をとし、

Q^\pi \left(s,a\right)
のように定義する。

行動価値を求める手法

ベルマン方程式

実際に行動価値関数を推定していくためのアルゴリズムの1つである、ベルマン最適方程式について述べていく。

この方程式では、未来の収益の期待値である行動価値関数を算出するために、異なる時刻における行動価値関数の間に成り立つ再帰的な関係を利用している。

ある方策\piの元での行動価値関数Q^\pi \left(s,a\right)は、ある状態sで行動aを選択した場合の収益の期待値であるので、

Q^\pi \left(s,a\right)=\mathbb{E}^\pi\left[G_t|S_t=s,A_t=a \right]
と表せる。
ここで収益は、

G_t = \sum_{\tau=0}^{\infty} \gamma^{\tau}R_{t+1+\tau}=R_{t+1}+\gamma R_{t+2}+\gamma^{2}R_{t+3}+\cdots
と表せるので、

\begin{eqnarray}
Q^\pi \left(s,a\right)&=&\mathbb{E}^\pi\left[\sum_{\tau=0}^{\infty}\gamma^{\tau}R_{t+1+\tau}\mid S_t=s,A_t=a \right] \\
&=&\mathbb{E}^\pi\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2}R_{t+3}+\cdots\mid S_t=s,A_t=a \right]
\end{eqnarray}
となる。

\mathbb{E}^\pi\left[\cdot\right]は線形な演算なので、

Q^\pi \left(s,a\right)=\mathbb{E}^\pi\left[R_{t+1}\mid S_t=s,A_t=a \right]+\gamma\mathbb{E}^\pi\left[R_{t+2}+\gamma R_{t+3}+\cdots\mid S_t=s,A_t=a \right]
とすることができる。

右辺の第一項については、

\mathbb{E}^\pi\left[R_{t+1}\mid S_t=s,A_t=a \right]=\sum_{s'}P\left(s'\mid s,a\right)r\left(s,a,s'\right)
となる。
P\left(s'\mid s,a\right)は状態sで行動aを選択した際に状態s’に遷移する確率を表す状態遷移確率であり、r\left(s,a,s'\right)はその時に得られる報酬である。

続いて第二項は、

\begin{eqnarray}
&\gamma&\mathbb{E}^\pi\left[R_{t+2}+\gamma R_{t+3}+\cdots\mid S_t=s,A_t=a \right]\\
=&\gamma&\sum_{s'}P\left(s'\mid s,a\right)\sum_{a'}\pi\left(a'\mid s'\right)\mathbb{E}^\pi\left[R_{t+2}+\gamma R_{t+3}+\cdots\mid S_{t+1}=s',A_{t+1}=a'\right]
\end{eqnarray}
となる。
このうち\mathbb{E}^\pi\left[R_{t+2}+\gamma R_{t+3}+\cdots\mid S_{t+1}=s',A_{t+1}=a'\right]の部分はQ^\pi\left(s',a'\right)とみることができるので、
第二項については、

\gamma\sum_{s'}P\left(s'\mid s,a\right)\sum_{a'}\pi\left(a'\mid s'\right)Q^\pi\left(s',a'\right)
となる。

これらをまとめると、

Q^\pi\left(s,a\right)=\sum_{s'}P\left(s'\mid s,a\right)\Bigl(r\bigl(s,a,s'\bigr)+\gamma\sum_{a'}\pi\bigl(a'\mid s'\bigr)Q^\pi\bigl(s',a'\bigr)\Bigr)
を得る。この方程式をベルマン方程式という。

ここで\sum_{a'}\pi\bigl(a'\mid s'\bigr)Q^\pi\bigl(s',a'\bigr)を見ると、状態s’にて、選択できる全ての行動a'から期待値を求めていることがわかる。

ベルマン最適方程式

状態s’での行動を方策で選択する代わりに、価値関数の値が最大となる行動a’を選択した場合の期待値を求めると、ベルマン方程式は、

Q\left(s,a\right)=\sum_{s'}P\left(s'\mid s,a\right)\Bigl(r\bigl(s,a,s'\bigr)+\gamma\max_{a'}Q^\pi\bigl(s',a'\bigr)\Bigr)
となる。この方程式をベルマン最適方程式という。

この方程式にはベルマン方程式とは違い、計算に直接的に行動選択確率が含まれていない。
実際にこのような問題を解く際には、全ての状態に対する行動価値関数の表を用意し、表の全ての要素をベルマン最適方程式で計算していく。

Q-Learning

ベルマン最適方程式を使って最適行動価値関数を求める方法は、状態遷移確率が既知であれば最も効率良く最適価値関数を計算することができる。
しかし、強化学習において、エージェントは環境に関して事前の知識を持っていない。
よって、不完全な知識の上で、知識を収集しながら最適な行動を学習していかなくてはならない。
Q-Learningとは、このような不完全な知識の中での探索結果から行動価値関数を近似し、最適方策を学習していく学習手法である。

例えば状態sで行動aを選択して状態s'に遷移した場合、
遷移時に得た即時報酬と、状態s'からずっと最適な行動を選び続けた時に得ることのできる収益の期待値の和を教師(target)として、Q\bigl(s,a\bigl)とtargetの誤差から新たにQ\bigl(s,a\bigl)を更新していく。
ちなみにこのQ\bigl(s,a\bigl)とtargetの誤差をTD誤差という。



\begin{align*}
&target=r\bigl(s,a,s'\bigr)+\gamma\max_{a'}Q^\pi\bigl(s',a'\bigr)\\
&loss=target-Q\bigl(s,a\bigr)\\
&Q\bigl(s,a\bigr)\leftarrow Q\bigl(s,a\bigr)+\alpha\times loss
\end{align*}


行動aによってエピソードが終了した場合、
targetはただ単にr\bigl(s,a,s'\bigr)となる。

エージェントが行動を選択する方法(方策)

先ほどのQ-Learningの説明で、「状態sで行動aを選択」と書いたが、
実際にどのように行動を選択していくか(方策)について述べる。

greedy

まず、これまでの相互作用の結果から、最も価値の高い行動を選択していくという方策がある。これをgreedy方策という。

ε-greedy

greedy方策は際的行動価値観数が既知であれば最適な方策となる。しかし、現実には最適行動価値観数は始めからわかっておらず、最適な行動価値を探索して推定していく必要がある。
その際に、これまでで得られた最も価値の高い行動を選択するだけでは、他の選択肢がどのくらい良い結果をもたらすか知ることができない。

そこで、今までの学習結果を利用するだけでなく、たまにランダムに探索する必要がある。
このように利用と探索を織り交ぜていく手法としてε-greedy方策が存在する。
確率εでランダムに行動し、確率1-εでgreedy方策をとる。

行動価値関数の近似

状態数が少なければ、テーブル関数Q\bigl(s,a\bigr)を作ることができるが、
例えばカメラの画像などを状態として扱うと、状態数が莫大になり、テーブル関数では表現できなくなってしまう。
そこでQ関数をパラメータ\thetaで近似する。

DQN(Deep Q-Network)

以上の手法にDeep Learningの技術を適用したもの。
関数近似ニューラルネットワークを用いて、Q関数を学習させていく。
ひと昔前までの関数近似は人手で構築された特徴を用いるて性能を向上させてきたが、Deep Q-Network(以下DQN)は入力として画面のデータなどの状態のみを用いて、同じ学習アルゴリズムを適用するだけで、囲碁やチェス、昔の家庭用ゲームなど様々なゲームにおいて人間以上の強さを発揮できるようになったことで注目を集めた。

DQNのネットワーク構造

DQNは行動価値関数を推定するための多層ニューラルネットワークである。
エージェントの視界や画面データなど画素情報を入力とするため、ただの多層ニューラルネットワークでなく畳み込みニューラルネットワークが利用されることが多い。
畳み込みニューラルネットワークの詳しい説明は今回省略する。

DQNの出力は行動価値関数Q\bigl(s,a\bigl)である。
つまり行動aの取りうる種類がN通りの場合、DQNはN通りの出力をもつニューラルネットワークとなる。

DQNの学習におけるテクニック

DQNディープラーニングを用いてネットワークのパラメータを更新していくのだが、上手く学習されるよう下記の工夫がなされている。

  • ターゲットの固定化(neural fitted Q)
  • 学習に用いるサンプルの偏りの抑制(Experience Replay)
neural fitted Q

先ほどQ-Learningの説明のところでも述べたが、
DQNのパラメータを更新してくには、TD誤差r_{t+1}+\gamma\max_{a_{t+1}}Q\bigl(s_{t+1},a_{t+1}:\theta_t\bigr)-Q\bigl(s_t,a_t:\theta_t\bigr)を求める必要がある。

第一項のr_{t+1}+\gamma\max_{a_{t+1}}Q\bigl(s_{t+1},a_{t+1}:\theta_t\bigr)ディープラーニングでいうtargetにあたるのだが、
このtargetはパラメータ\thetaに依存するため収束が安定しないとのこと。

そこでtargetにおけるパラメータ\thetaをある時点でのパラメータ\theta^-で固定し、
r_{t+1}+\gamma\max_{a_{t+1}}Q\bigl(s_{t+1},a_{t+1}:\theta^-\bigr)とする。
そしてある程度学習を繰り返した後に、targetとなるQ関数のパラメータ\theta^-を更新する。

Experience Replay

関数近似に多層ニューラルネットワークなどを用いた場合、
「サンプル取得 -> 学習 -> サンプル取得 -> 学習」という学習法だと、どうしても学習が遅くなってしまう。
そこで、サンプル\bigl(s,a,r,s'\bigr)が無限回得られるなら、それらをどのような順番で学習しても最適な価値関数が得られるという特徴を生かして、経験したサンプルを全てメモリーとして記録しておき、学習を行う際はそこからランダムサンプリングして利用するExperience Replayという手法を使う。
この手法は、時系列的に連続であるサンプル間の相関をバラすというメリットもある。

もっと噛み砕いて書くと、
「ある状態でどう行動をとったら、どんな結果を得て、次にどんな状態になった」という経験をエージェントは蓄積していく。
そしてたまった経験から「あの時、右に曲がればぶつからずに済んだんだな」といった風に、ディープラーニングで最適な行動を学習し、ニューラルネットワークをチューニングしていく。

f:id:okuya-KAZAN:20171019135101p:plain


まとめ

強化学習のキーワードをまとめ、最適な行動価値関数を求める手法についてまとめた。
実際にPythonのChainerでDQNの実装もしたので今度改めてブログにまとめようと思う。