走る作曲家のAIカフェ

目次

Overview

深層強化学習とは、強化学習と深層学習を組み合わせた手法です。ニューラルネットワークを使用して、エージェントが環境から得られる観測値をもとに価値関数や方策を近似します。
このページでは、深層強化学習について基礎から学んでいきます。

Source

以下の講義・書籍を参考にしました。

NN & Q-Learning

「3×4のグリッドワールド」程度の問題なら、Q関数をテーブルとして保持できる。しかし、現実はより複雑で、状態も行動も膨大になる可能性がある。テーブルとして保持するのが難しくなるほか、莫大な数をすべて経験することも現実的ではない。 この問題を解決するために、Q関数をコンパクトな関数で近似することを考える。そのための最も有力な手法が、ディープラーニングである。

ニューラルネットワークの代表的な構造は2通り考えられる。1つ目は、状態と行動の2つを入力とするネットワークである。この場合、出力はQ関数の値を1つだけ出力する。 もう1つの構造は、状態だけを入力として、行動の候補の数の分だけQ関数の値を出力するネットワークである。 ただし、1つ目のネットワーク構造には計算コストの点で問題がある。具体的には、ある状態においてQ関数の最大値を求める計算コスト（\(\max_a Q(s, a)\)の計算コスト）が大きくなる。よって、2つ目のネットワーク構造を用いる。

Q学習では次の式によってQ関数を更新する。

\begin{align} Q'(S_t, A_t) = Q(S_t, A_t) + \alpha \{R_t + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)\} \end{align}
この式によって、\(Q(S_t, A_t)\)の値は、ターゲットである\(R_t + \gamma \max_a Q(S_{t+1}, a)\)の方向へと更新される。このとき、\(\alpha\)によってどれだけターゲットの方向へ進むかが調整される。 ここで、ターゲットである\(R_t + \gamma \max_a Q(S_{t+1}, a)\)を\(T\)で表すことにする。そうすると、上式は以下のように表される。
\begin{align} Q'(S_t, A_t) = Q(S_t, A_t) + \alpha \{T - Q(S_t, A_t)\} \end{align}
この式は、入力が\(S_t, A_t\)のとき出力が\(T\)になるようにQ関数を更新すると解釈できる。これをニューラルネットワークの文脈に当てはめると、入力が\(S_t, A_t\)で、出力が\(T\)となるように学習させることと同じである。 つまり、\(T\)は正解ラベルとみなせる。また、\(T\)はスカラ値なので、これは回帰問題と考えることができる。

DQN

Q学習では、推定値を使って推定値を更新する（ブートストラッピング）。まだ正確ではない推定値を使って、今ある推定値を更新するため、Q学習は不安定になりやすい性質がある。 そこにニューラルネットワークのような表現能力の高い関数近似手法が加わると、結果はさらに不安定になる。ニューラルネットワークの学習を安定させるために、経験再生とターゲットネットワークという技術が使われている。

経験再生

教師あり学習を復習する。ここでは、MNISTを例に扱う。MNISTは主に、クラス分類の問題に使われ、データセットの中身は、画像データと正解ラベルがペアで与えられる。MNISTを使ってニューラルネットワークで学習する流れは次の通りである。

  1. 訓練用のデータセットから一部のデータをランダムに取り出す（この取り出したデータはミニバッチと呼ぶ）。
  2. そのミニバッチを使ってニューラルネットワークのパラメータを更新する。
ここで、ミニバッチを作るときには、データに偏りがないように気をつける必要がある。ニューラルネットワークの学習では、データの偏りを防ぐために、データセットからランダムに取り出すのが一般的である。

次に、Q学習である。Q学習では、エージェントが環境に対して行動するたびにデータが生成される。具体的には、ある時間\(t\)において得られた\(E_t = (S_t, A_t, R_t, S_{t+1})\)を使ってQ関数を更新する。 ここでは\(E_t\)を「経験データ」と呼ぶ。この経験データは時間\(t\)が進むに従い得られるが、経験データ間には強い相関がある。つまりQ学習では、相関の強い（偏りのある）データを使って学習を行なっていることになる。 これが教師あり学習とQ学習の1つ目の違いである。この違いを埋めるテクニックに経験再生がある。まずエージェントが経験したデータ\(E_t = (S_t, A_t, R_t, S_{t+1})\)を一度「バッファ」に保存する（バッファとは、一時的にデータを蓄えておく記憶装置のこと）。 そして、Q関数を更新する際には、そのバッファから経験データをランダムに取り出して使う。経験再生によって、経験データ間の相関が弱まり、偏りの少ないデータが得られる。さらに、経験データを繰り返し使うことができるため、データ効率が良くなる。 経験再生は、Q学習に限らず、他の強化学習のアルゴリズムでも使うことができるが、経験再生を使えるのは方策オフ型のアルゴリズムに限られる。方策オン型は、現時点の方策から得たデータだけしか使えないため（過去に集めた経験データを使えないため）、経験再生を使うことはできない。

ターゲットネットワーク

教師あり学習では、学習データに正解ラベルが付与される。このとき、入力に対する正解ラベルは不変である。Q学習では、\(Q(S_t, A_t)\)の値が\(R_t + \gamma \max_a Q(S_{t + 1}, a)\)（TDターゲット）となるようにQ関数を更新する。 TDターゲットは、教師あり学習における正解ラベルに相当する。しかしTDターゲットの値は、Q関数が更新されると変動する。ここが教師あり学習とQ学習の違いである。この違いを埋めるために、ターゲットネットワークという、TDターゲットを固定するテクニックを使う。 まず、Q関数を表すオリジナルのネットワーク（これをqnetと呼ぶ）を用意する。そして、それとは別に、もう一つ同じ構造のネットワーク（これをqnet_targetと呼ぶ）を用意する。qnetは通常のQ学習によって更新を行う。 一方、qnet_targetは定期的にqnetの重みと同期するようにして、それ以外の重みパラメータを固定したままにする。あとは、qnet_targetを使ってTDターゲットの値を計算すれば、教師ラベルであるTDターゲットの変動が抑えられる。 これによって教師ラベルであるTDターゲットが（常には）変動しないので、ニューラルネットワークの学習が安定することが期待できる。つまり、ターゲットネットワークはTDターゲットの値を固定するためのテクニックである。 ただし、TDターゲットが全く更新されないとQ関数の学習は進まないため、間をあけて定期的に（例えば100エピソードごとに）ターゲットネットワークの更新を行うようにしている。

POMDP

Atariの「Pong」では、MDPを満たさない。なぜなら、ゲーム画面の画像1枚だけを見ても、ボールがどの方向に進んでいるかがわからないからである。もちろん、ボールの進行方向が不明の状態では最適な行動は行えない。このような問題はPOMDP（部分観測マルコフ決定過程）という。 「Pong」のようなテレビゲームの場合、POMDPをMDPに変換することは簡単である。その方法は、連続するフレームを使うことである。DQNの論文では、4フレームの連続する画像を重ね合わせ、それを１つの「状態」として扱う。 連続する画像を使うことで、状態の遷移が分かる。これで今まで通りのMDPとして扱うことができる。POMDPでは、現在の観測だけでは不十分であるため、過去の観測も考慮して行動を決める必要がある。POMDPで有力な手法は、RNNを使った方法である。RNNを用いると、過去に入力されたデータを引き継いで計算することができる。

その他の工夫

εの調整

強化学習では、活用と探索のバランスが重要である。エージェントの経験が増えるにしたがって価値関数の信頼性が上がることを考えると、エピソード数に比例して探索の割合を減らすことは理にかなっている。 つまり、初期の段階ではエージェントに多く探索を行わせ、学習が進むにつれて探索を減らす（活用を増やす）ということである。ε-greedy法でこのアイデアを実現するには、エージェントが行動を重ねるにしたがってεを減らすことが考えられる。 DQNの論文では、最初の100万ステップはεを1.0から0.1まで線形に減少させ、それ以降はε=0.1で固定するという方式が採用されている。

報酬のクリッピング

DQNの論文では、報酬を-1.0から1.0の範囲に収まるように調整し、報酬のスケールをそろえることで学習を円滑化している。

Double DQN

DQNでは、「ターゲットネットワーク」というテクニックが使われる。これは、メインとなるネットワークの他に、パラメータが異なるネットワーク（＝ターゲットネットワーク）を使う手法である。 ここでは２つのネットワークのパラメータをそれぞれ\(\theta\)と\(\theta '\)で表すことにして、その２つのネットワークによって表現されるQ関数を\(Q_{\theta} (s,a)\)、\(Q_{\theta '} (s,a)\)で表すことにする。 このとき、Q関数の更新で用いるターゲットは次の式で表される。

\begin{align} R_t + \gamma \max_a Q_{\theta '} (S_{t+1}, a) \end{align}
DQNでは、\(Q_{\theta} (s,a)\)の値を上式の値（TDターゲット）に近づけるように学習する。ここで問題になるのが、\(\max_a Q_{\theta '} (S_{t+1}, a)\)である。 具体的には、誤差が含まれる推定値\(Q_{\theta '}\)に対してmax演算子を使うと、真のQ関数を使って計算する場合に比べて過大に評価されてしまう。この問題を解決したのがDouble DQNである。Double DQNでは、次の式をTDターゲットとする。
\begin{align} R_t + \gamma Q_{\theta '} (S_{t+1}, argmax_a Q_{\theta} (S_{t+1}, a)) \end{align}
ポイントは、\(Q_{\theta}(s,a)\)を使って最大となる行動を選び、実際の値は\(Q_{\theta '}(s,a)\)から取得することである。このように２つのQ関数を使いわけることで、過大評価が解消され、学習がより安定する。

優先度付き経験再生

DQNで使われる経験再生では、経験\(E_t = (S_t, A_t, R_t, S_{t+1})\)をバッファに保存し、学習時にはバッファから経験データをランダムに取り出して使う。これをさらに進化させたのが、優先度付き経験再生である。 その言葉どおり、経験データをランダムに選ぶのではなく、優先度に応じて選ばれやすくする。優先度の決め方として、自然に考えられるのは次の式である。

\begin{align} \delta_t = |R_t + \gamma \max_a Q_{\theta '} (S_{t+1}, a) - Q_{\theta}(S_t, A_t)| \end{align}
上式のとおり、TDターゲットである\(R_t + \gamma \max_a Q_{\theta '} (S_{t+1}, a)\)と\(Q_{\theta}(S_t, A_t)\)の差分をとり、その絶対値を求めて\(\delta_t\)とする。この値が大きければ、それだけ修正すべきことが大きい、つまりは、学ぶべきことが大きいということである。 逆にこの値が小さければ、すでに良いパラメータであり、学ぶべきことは少ないということになる。優先度付き経験再生では、経験データをバッファに保存するときに\(\delta_t\)も計算する。そして、\(\delta_t\)も経験データに含めた\(S_t, A_t, R_t, S_{t+1}, \delta_t\)をバッファに追加する。 バッファから経験データを取り出すときは、\(\delta_t\)を使って各経験データが選ばれる確率を計算する。仮に\(N\)個の経験データがバッファに含まれる場合、\(i\)番目の経験データが選ばれる確率は次の式で表される。
\begin{align} p_i = \frac{\delta_i}{\sum_{k=0}^{N} \delta_k} \end{align}
この確率\(p_i\)に応じて、バッファから経験データを選び出す。優先度付き経験再生を使うことで、学ぶべきことが多いデータほど優先して使用されるため、学習がより早く進むことが期待できる。

Dueling DQN

Dueling DQNは、ニューラルネットワークの構造を工夫した手法である。この手法でキーとなるのが、アドバンテージ関数である。アドバンテージ関数は、Q関数と価値関数の差分で定義される。つまり、次の式で表される。

\begin{align} A_{\pi}(s,a) = Q_{\pi} (s, a) - V_{\pi} (s) \end{align}
アドバンテージ関数は、\(a\)という行動が方策\(\pi\)に比べてどれだけ良いか（もしくは悪いか）を表す。その理由は次の点から明らかである。

つまり、\(Q_{\pi}(s,a)\)と\(V_{\pi})(s)\)の違いは、状態\(s\)において行動\(a\)を行うか、それとも方策\(\pi\)に従って行動を選ぶかの違いである。 そのため、アドバンテージ関数は、「\(a\)という行動」が「方策\(\pi\)で選ばれる行動」に比べてどれだけ良いかを示す指標として解釈できる。また、上式のアドバンテージ関数をもとに、Q関数を求めることもできる。

\begin{align} Q_{\pi} (s, a) = A_{\pi}(s,a) + V_{\pi} (s) \end{align}
Dueling DQNは、この式をニューラルネットワークで実現する。ネットワークとして途中まで計算を共有して、アドバンテージ関数と価値関数に枝分かれするように分離する。そして最後にその2つを加算して\(Q(s,a)\)を出力する。この構造がDueling DQNの特徴である。 これは主に、どのような行動を行っても結果がほとんど変わらないような状態において利点があると考えられる。例えば、「Pong」において、どのような行動を取っても結果は負け（マイナスの報酬）になる場面を考える。 DQNの場合、ある状態\(s\)で実際に行った行動\(a\)に対して\(Q(s, a)\)を学習する。行動に関わらず結果が決まっている状態であっても、すべての行動を試さなければ\(Q(s,a)\)は学習されない。 一方のDueling DQNでは、価値関数\(V(s)\)を経由する。価値関数はある状態\(s\)における価値である。そのため、今回の場面を経験すれば\(V(s)\)が学習され、それによって他の行動を試さなくても\(Q(s, a)\)の近似性能が改善する。これにより、学習が促進することが期待できる。

Policy Gradient Method

Q学習やSARSA、モンテカルロ法などは、大別すれば価値ベースの手法に分類される。価値ベースの手法は、価値関数をモデル化し、価値関数を学習する。そして、価値関数を経由して方策を得る。 価値ベースの手法では、一般化方策反復というアイデアに基づいて最適方策を見つけることが多く行われる。具体的には、価値関数の評価と方策を改善するというプロセスを繰り返すことで、徐々に最適方策に近づく。 価値ベースの手法の他に、価値関数を経由せずに方策を直接表す手法も考えられる。これが方策ベースの手法である。中でも、方策をニューラルネットワークなどでモデル化し、勾配を使って方策を最適化する手法は方策勾配法と呼ばれる。 方策勾配法に基づくアルゴリズムは様々な手法が提案されている。

確率的な方策は数式で\(\pi (a|s)\)と表される。\(\pi (a|s)\)は、状態\(s\)において、\(a\)という行動を取る確率である。ここでは、方策をニューラルネットワークでモデル化する。 それにあたり、ニューラルネットワークのすべての重みパラメータを\(\theta\)で表す（\(\theta\)は、すべてのパラメータの要素を一列に並べたベクトルとする）。そして、ニューラルネットワークによる方策を\(\pi_{\theta} (a|s)\)で表す。

方策\(\pi_{\theta}\)を使って目的関数を設定する。まず、次のような「状態、行動、報酬」からなる時系列データが得られたと仮定する。

\begin{align} \tau = (S_0, A_0, R_0, S_1, A_1, R_1, \cdots, S_{T+1}) \end{align}
\(\tau\)は軌道と呼ばれる。このとき、収益は以下のように設定できる。
\begin{align} G(\tau) = R_0 + \gamma R_1 + \gamma^2 R_2 + \cdots + \gamma^T R_T \end{align}
このとき、目的関数は次の式で表される。
\begin{align} J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} [G(\tau)] \end{align}
収益は確率的に変動するため、その期待値が目的関数となる。\(\tau \sim \pi_\theta\)は、\(\tau\)が\(\pi_\theta\)によって生成されることを示している。 目的関数が決まれば、次はその勾配を求める。ここではパラメータ\(\theta\)に関する勾配を\(\nabla_{\theta}\)で表す。ここでの目標は、\(\nabla_{\theta} J(\theta)\)を求めることである。この結果は以下のようになる。
\begin{align} \nabla_{\theta} J(\theta) &= \nabla_{\theta} \mathbb{E}_{\tau \sim \pi_\theta} [G(\tau)] \\ &= \mathbb{E}_{\tau~\pi_\theta} [\sum_{t=0}^{T} G(\tau) \nabla_{\theta} \log \pi_{\theta} (A_t | S_t)] \end{align}
この式で注目したい点は、\(\nabla_{\theta}\)が\(\mathbb{E}\)の中にあることである。これが求まれば、続いてニューラルネットワークのパラメータを更新する。単純な最適化の方法は次の式で表される。
\begin{align} \theta \leftarrow \theta + \alpha \nabla_{\theta} J(\theta) \end{align}

\(\nabla_{\theta} J(\theta)\)は上で示したように、期待値として表される。この期待値はモンテカルロ法によって求めることができる。モンテカルロ法は、サンプリングをいくつか行って、その平均を取る。 今回の場合、方策\(\pi_{\theta}\)のエージェントに実際に行動させ、軌道\(\tau\)を\(n\)個得たとする。その場合、各\(\tau\)において上式における期待値の中身を計算して、その平均を求めることで\(\nabla_{\theta} J(\theta)\)を近似できる。

REINFORCE

REINFORCE(REward Increment = Nonnegative Factor × Offset Reinforcement × Characteristic × Eligibility)は、方策勾配法を改善した手法である。 最も単純な方策勾配法は、次の式に基づいて実装される。

\begin{align} \nabla_{\theta} J(\theta) = \mathbb{E}_{\tau~\pi_\theta} [\sum_{t=0}^{T} G(\tau) \nabla_{\theta} \log \pi_{\theta} (A_t | S_t)] \end{align}
この式における\(G(\tau)\)は、これまでに得られたすべての報酬の総和である。ここで考えたい問題は、どの時刻\(t\)においても\(G(\tau) \nabla_{\theta} \log \pi_{\theta} (A_t | S_t)\)のように、常に一定の重み\(G(\tau)\)を使って行動\(A_t\)の取る確率を大きくしている（もしくは小さくしている）点である。 エージェントの行動の善し悪しは、その行動の後に得られた報酬の総和によって評価される。逆に言えば、ある行動を起こす前に得られた報酬は、その行動の善し悪しとは関係がない。 例えば、ある時刻\(t\)に取った行動\(A_t\)を評価するにあたっては、それ以前に何を行い、どのような報酬を得たかはどうでもよいことである。 行動\(A_t\)を取って、それ以降どのような結果になるかということによって、つまり、時刻\(t\)以降に得られる報酬の総和によって行動\(A_t\)の善し悪しが決まる。

上式を見ると分かるように、行動\(A_t\)に対する重みは\(G(\tau)\)である。この重み\(G(\tau)\)には、時刻\(t\)よりも前の報酬も含まれる。つまり、本来関係のない報酬がノイズとして含まれることになる。 これを改善するには、重み\(G(\tau)\)を次のように変更することが考えられる。

\begin{align} \nabla_{\theta} J(\theta) &= \mathbb{E}_{\tau~\pi_\theta} [\sum_{t=0}^{T} G_t \nabla_{\theta} \log \pi_{\theta} (A_t | S_t)] \\ G_t &= R_t + \gamma R_{t+1} + \cdots + \gamma^{T-t} R_T \end{align}
上のように重みを\(G_t\)に変更する。重み\(G_t\)は、時刻\(t \sim T\)までの間に得られる報酬の総和である。これで、行動\(A_t\)の選ばれる確率は、時刻\(t\)より前の報酬を含まない重み\(G_t\)によって強められる。 これが方策勾配法を改善するアイデアである。REINFORCEは、分散が小さくなるため、データのサンプル数が少なくても精度良く近似できる。

ベースライン

REINFORCEを改善するための技術に、ベースラインというものがある。これは、ある結果に対して予測値を引くことで分散を小さくするというものである。REINFORCEにベースラインを適用すると、以下の式になる。

\begin{align} \nabla_{\theta} J(\theta) = \mathbb{E}_{\tau~\pi_\theta} [\sum_{t=0}^{T} (G_t - b(S_t)) \nabla_{\theta} \log \pi_{\theta} (A_t | S_t)] \end{align}
\(b(S_t)\)は任意の関数であり、これがベースラインである。例えば、状態\(S_t\)においてこれまで得られた報酬の平均を\(b(S_t)\)として使うことが考えられる。 また、実践的によく用いられるのは、価値関数である。数式で書くと、\(b(S_t) = V_{\pi_{\theta}}(S_t)\)となる。ベースラインを使って分散を小さくすることができれば、サンプル効率の良い学習が行える。 なお、ベースラインとして価値関数を使う場合、真の価値関数\(v_{\pi_{\theta}}(S_t)\)を知ることはできない。その場合は、価値関数についても学習する必要がある。

Actor-Critic

強化学習のアルゴリズムは、価値ベースの手法と方策ベースの手法があるが、その両方を使った手法も考えられる。上述の、ベースライン付きのREINFORCEは、ベースラインに価値関数を用いるのであれば、「価値ベースかつ方策ベース」と考えられる。 ここでは、ベースライン付きのREINFORCEをさらに推し進めて、Actor-Criticというアルゴリズムを導出する。

ベースライン付きのREINFORCEでは、目的関数の勾配は以下の式で表される。

\begin{align} \nabla_{\theta} J(\theta) = \mathbb{E}_{\tau~\pi_\theta} [\sum_{t=0}^{T} (G_t - b(S_t)) \nabla_{\theta} \log \pi_{\theta} (A_t | S_t)] \end{align}
ここで、ベースラインとして、ニューラルネットワークでモデル化した価値関数を使う。 この場合の目的関数の勾配は以下の式で表される。
\begin{align} \nabla_{\theta} J(\theta) = \mathbb{E}_{\tau~\pi_\theta} [\sum_{t=0}^{T} (G_t - V_w (S_t)) \nabla_{\theta} \log \pi_{\theta} (A_t | S_t)] \end{align}
この式には、収益\(G_t\)はゴールに達しないと値が定まらないという問題がある。つまり、ゴールに達するまでは、方策や価値関数の更新ができない。これは、モンテカルロ法に基づく方法であれば、どれもが持つ欠点である。 この欠点を解消した方法が、TD法である。TD法で価値関数を学習する場合、1ステップ後の結果を使って更新することができる。 価値関数\(V_w (S_t)\)を学習する場合、モンテカルロ法では収益\(G_t\)を使う。一方、TD法では\(R_t + \gamma V_w (S_{t+1})\)を使う。 価値関数をニューラルネットワークでモデル化する場合、\(V_w (S_t)\)の値が\(R_t + \gamma V_w (S_{t+1})\)に近づくように学習する。TD法を用いる場合、以下の式が得られる。
\begin{align} \nabla_{\theta} J(\theta) = \mathbb{E}_{\tau~\pi_\theta} [\sum_{t=0}^{T} (R_t + \gamma V_w (S_{t+1}) - V_w (S_t)) \nabla_{\theta} \log \pi_{\theta} (A_t | S_t)] \end{align}
この式に基づく方法が、Actor-Criticである。方策\(\pi_{\theta}\)と価値関数\(V_w\)はニューラルネットワークであり、その2つのニューラルネットワークを並行して学習する。 具体的には、方策\(\pi_{\theta}\)は上式に基づいて学習する。そして、価値関数\(V_w\)はTD法によって\(V_w (S_t)\)の値が\(R_t + \gamma V_w (S_{t+1})\)に近づくように学習する。

方策ベースの手法の利点

1. 方策を直接モデル化するので効率的

問題によっては、価値関数は複雑な形状をしながらも、最適方策は単純な場合も考えられる。そのような場合、方策ベースの方がより速く学習できる。

2. 連続的な行動空間でも使える

価値ベースの手法は、行動空間が連続的になると適用が難しくなる。対策方法としては、連続的な行動空間を離散化する「量子化」があるが、難しい問題である。 一方、方策ベースの手法であれば、連続的な行動空間にもシンプルに対応できる。たとえば、ニューラルネットワークの出力が正規分布を想定した場合、ニューラルネットワークは正規分布の平均と分散を出力することが考えられ、その平均と分散をサンプリングすることで連続値が得られる。

3. 行動の選択確率がスムーズに変化する

価値ベースの手法では、基本的にはQ関数の一番大きい行動が選ばれる。このとき、Q関数の更新により最大値となる行動が変わると、行動の取り方が急に変わることになる。 一方、方策ベースの手法は、ソフトマックス関数によって各行動の確率が決まるため、方策のパラメータを更新していく過程で各行動の確率はスムーズに変わる。このおかげで、方策勾配法の学習は安定しやすくなる。

Advanced Topics

深層強化学習の分類

まず、環境のモデル（状態遷移関数\(p(s'|s,a)\)と報酬関数\(r(s,a,s')\)）を使用するかどうかで大きく分かれる。環境のモデルを使用しない場合をモデルフリーの手法、使用する場合をモデルベースの手法と呼ぶ。 モデルベースの手法は、環境のモデルが与えられる場合と環境のモデルを学習する場合の2つに分類できる。環境のモデルが与えられる場合、エージェントは行動を起こさずに動的計画法などのプランニングによって問題を解くことができる。 将棋や囲碁などのボードゲームでは、環境のモデルが既知の問題設定として取り組むことができ、この場合も、環境のモデルを使った手法を使うことができる。有名なアルゴリズムはAlphaGoやAlphaZeroである。 環境のモデルが与えられない場合、環境から得た経験によって環境のモデルを学習することが考えられる。学習した環境のモデルはプランニングに使える他、方策の評価や改善にも活用することができる。 この分野に属する手法には、World Modelsや、MBVE（Model-Based Value Estimaion）などがある。この分野は現在活発に研究が行われていて、これから先、人間の持つような汎用的な知能を実現する上でも有効になることが期待されている。 ただし、環境のモデルを学習する手法にはいくつか問題がある。最大の問題は、エージェントが環境のモデルの生成するサンプルデータの一部しか得られないことである。これにより、学習した環境のモデルと実際の環境との間にズレ（偏り）が生じる場合がある。 環境のモデルを学習するというアプローチは大きな可能性を秘めているが、現時点ではモデルフリーの手法の方が成果を上げている。モデルフリーの手法は、方策ベースの手法と、価値ベースの手法、またその両方を併せ持つ手法に分類できる。 方策ベースの手法は、方策勾配法やREINFORCEなどが該当する。Actor-Criticは「方策ベースかつ価値ベース」の手法である。価値ベースの手法は、価値関数をモデル化して学習する手法である。その中で、最も重要な手法はDQNである。

方策勾配法系列の発展アルゴリズム

A3C、A2C

A3Cは「Asynchronous Advantage Actor-Critic」の略である。複数のエージェントが並列に動き、非同期でパラメータが更新される。A3Cはニューラルネットワークでモデル化したActor-Criticを使って方策を学習し、1つのグローバルネットワークと複数のローカルネットワークを使う。 ローカルネットワークは、それぞれの環境で独立にプレイし、学習を行なう。グローバルネットワークは、複数のローカルネットワークから送られてくる勾配を使って重みパラメータを非同期に更新する。 そのようにしてグローバルネットワークの重みパラメータを更新しながら、定期的にグローバルネットワークとローカルネットワークの重みパラメータを同期する。 A3Cの利点は、複数のエージェントが並列に動くことによって学習を高速化できることである。さらに、エージェントが並列に独立して行動（探索）するため、多様なデータが得られる。これによって、全体で得られる学習データの相関を減らすことができ、学習がより安定する。 並列処理は、方策オン型の手法でも使うことができる汎用的なアイデアである。また、A3CのActor-Criticでは、ニューラルネットワークの重みの共有を行う。1つのニューラルネットワークで重みを共有し、方策と価値関数を出力する。 方策も価値関数も入力に近い層は似たような重みになることが期待できるため、このようなパラメータ共有型のネットワーク構造が有効に働く。

A2Cはパラメータの更新を非同期でなく、同期的に更新する手法である。エージェントはそれぞれの環境で独立に動作するため、時刻\(t\)における各環境での状態は（同期して）バッチとしてまとめて、ニューラルネットワークの学習を行なう。 このとき、ニューラルネットワークの出力（方策の確率分布）から次の行動をサンプリングして、各環境にサンプリングした行動を渡す。実験によって、A2Cによる同期更新であっても、A3Cと比べてパフォーマンスが下がらないことが分かっている。 さらに、A2Cの方が実装が容易であり、GPUなどの計算リソースを効率的に利用できる。その点から、実践ではA2Cの方が多く使われる。

DDPG

DDPGは「Deep Deterministic Policy Gradient method」の略である。連続的な行動空間の問題に対して設計されたアルゴリズムである。ニューラルネットワークは、行動を連続値として直接出力する。 DDPGの方策は、ある状態\(s\)を入力すると行動\(a\)が一意に決まるため、決定論的な方策である。DDPGでは、この決定論的方策をDQNの中に組み込む。ここでは、方策を表すニューラルネットワークを\(\mu_{\theta}(s)\)、DQNのQ関数を表すニューラルネットワークを\(Q_{\phi}(s,a)\)で表す。 \(\theta, \phi\)はそれぞれのニューラルネットワークのパラメータとする。このとき、DDPGは次の2つのプロセスによってパラメータを更新する。

  1. Q関数の出力が大きくなるように方策\(\mu_{\theta}(s)\)のパラメータ\(\theta\)を更新
  2. DQNで行うQ学習によってQ関数の\(Q_{\phi} (s,a)\)のパラメータ\(\phi\)を更新

まず、1つ目の学習について、これは2つのニューラルネットワークを組み合わせて使い、Q関数の出力が最大になるように決定論的方策\(\mu_{\theta}(s)\)のパラメータ\(\theta\)を更新する。 ここで重要な点は、\(\mu_{\theta}(s)\)の出力する行動\(a\)が連続値であり、その出力\(a\)がそのまま\(Q_{\phi}(s,a)\)の入力となっていることである。 これにより、2つのニューラルネットワークを通してバックプロパゲーションが行える。そのバックプロパゲーションによって勾配\(\nabla_{\theta} q\)が求まる（\(q\)はQ関数の出力とする）。 そうすれば、勾配\(\nabla_{\theta} q\)を使ってパラメータ\(\theta\)を更新することができる。 仮に確率的方策によって行動をサンプリングした場合、バックプロパゲーションはサンプリングを行っている箇所で止まる（それより先は勾配が0しか伝わらない）。その場合、方策のパラメータを更新することはできない。

2つ目の学習は、DQNで行うQ学習である。今回の場合は、決定論的方策\(\mu_{\theta}(s)\)を使うことで効率的な計算ができる。 DQNで行うQ関数の更新は、\(Q_{\phi}(S_t,A_t)\)の値が\(R_t + \gamma \max_a Q_{\phi} (S_{t+1}, a)\)となるようにすることだった。ここでは1つ目の学習により、方策\(\mu_{\theta}(s)\)はQ関数が大きくなるような行動を出力する。 そのため、以下の近似を使うことができる。

\begin{align} \max_a Q_{phi} (s,a) \simeq Q_{phi} (s, \mu_{\theta} (s)) \end{align}
\(\max_a\)という最大値を求める計算は、一般的に多くの計算が必要になる。特に行動空間が連続的な場合、複雑な最適化問題を解かなければならない。 DDPGでは\(\max_a Q_{phi} (s,a)\)を\(Q_{phi} (s, \mu_{\theta} (s))\)という2つのニューラルネットワークの順伝播に置き換える。これにより計算を簡略化でき、効率的な学習が期待できる。 DDPGには、さらに、「ソフトターゲット」「探索ノイズ」という工夫も取り入れられている。

TRPO, PPO

方策勾配法の問題点は、勾配によってパラメータの更新する「方向」はわかるが、どれだけ進むのが良いかという「ステップ幅」が不明なことである。これを解決したのがTRPO（Trust Region Policy Optimization）である。 信頼できる領域の中で、適切なステップ幅で方策を最適化することができる。TRPOではほうさく　の更新前後のKLダイバージェンスを指標として、その値が閾値を超えないという制約を課す。 つまり、KLダイバージェンスの制約がある中で目的関数を最大化する問題と捉える。TRPOで制約付きの最適化問題を解くには、ヘッセ行列という二階微分の計算が必要になる。 ヘッセ行列は多くの計算が必要であり、計算量の多さがボトルネックになる。この問題を解決したのがPPO（Proximal Policy Optimization）である。PPOはTRPOをよりシンプルにした手法であり、計算量を削減しながら性能はTRPOと同程度であるため、実践においてはこちらがよく用いられる。

DQN系列の発展アルゴリズム

カテゴリカルDQN

Q関数は数式で

\begin{align} Q_{\pi} (s, a) = \mathbb{E}_{\pi} [G_t | S_t = s, A_t = a] \end{align}
と表される。収益という確率的な事象に対して、期待値という1つの値で表されるのが、Q関数の特徴である。DQNでは、Q関数という期待値で表される値を学習する。これを発展させて、Q関数という期待値を学習するのではなく、「分布」を学習させようというアイデアがある。 このアイデアは分布強化学習と呼ばれる。分布強化学習では\(Z_{\pi} (s, a)\)という収益の確率分布を学習する。カテゴリカルDQNは、分布強化学習に基づいて、収益をカテゴリカル分布としてモデル化し、その分布の形状を学習する。 そのためには、カテゴリカル分布版のベルマン方程式を導き、それをもとにカテゴリカル分布を更新する。

Noisy Network

Noisy Networkはニューラルネットワークの中にランダム性を組み込むことで、ε-greedy法ではなく、greedy法に従って行動を選ぶことができるようにした。具体的には、出力側にある全結合層で、「ノイズが入った全結合層」を使う。

Rainbow

Rainbowは、オリジナルのDQNに対して、次の手法をすべて合わせて使用する。

Rainbowは、他の手法と比べて飛躍的に性能が向上している。

Rainbow以降の発展アルゴリズム

複数のCPU/GPUを使った分散並列化された学習が大きな成果を上げた。これは分散強化学習と呼ばれ、複数の実行環境で学習を行なう。分散強化学習で有名なのがApe-Xという手法である。 Ape-XはRainbowをベースとして、さらに複数のエージェントを別のCPUで独立に行動させ、経験データを集めながら学習を行なう。 分散並列化されたエージェントにはすべて異なる探索率εが設定されていて、それによって多様な経験データを集めることができる。分散並列化によって学習が速く進むと同時に、多様な経験データによって性能が向上した。

Ape-Xをさらに改善した手法がR2D2である。R2D2はApe-Xにプラスして、時系列データを処理するRNNを用いた。これをさらに進化させたのがNGUである。これは「Never Give Up」の略で、困難なタスクでも、特に、報酬が疎かなタスクでも、あきらめずに探索を行うことができる。 NGUはR2D2をベースに、内発的報酬という仕組みを追加している。内発的報酬とは、状態遷移が予想と異なれば異なるほど、どれだけ「驚いたか」によって、自分自身で報酬をプラスして与える。内発的報酬により、好奇心に基づいて行動するように促すことができる。 さらにNGUを発展させて、内発的報酬の仕組みを改良し、「メタコントローラ」と呼ばれる仕組みを使って、エージェントへの方策割り当てに柔軟性をもたらしたAgent57という手法がある。