\gdef\argmax{\mathop{\rm argmax}\limits}
\gdef\argmin{\mathop{\rm argmin}\limits}
本記事は東京大学の村山裕和（https://www.linkedin.com/in/裕和-村山-9b42252b1/ ）による寄稿です。
はじめに
強化学習は様々なアルゴリズムがありますが、離散状態、離散入力を前提としたものが多く、連続状態、連続入力には適用しにくい手法も多いです。今回紹介するのは、強化学習における行動選択にDDP（Differential Dynamic Programming/モデル予測制御の一種）のアルゴリズムを組み込み、連続空間、連続入力での学習を可能とした手法です。元論文でも強化学習の学習部分は既存の物の流用なので、行動選択の部分に絞って解説します。
理論的背景
ベルマン方程式
強化学習とDDPはどちらもベルマン方程式と言う数式を元にしています。導出は割愛しますが（どこかの記事できちんと説明しようとは思います）、実際に書くと次のようになります（今回は強化学習の文脈に合わせて\maxバージョンを使いますが、\minバージョンでも以降の議論の中身は同じです）。
Q_{t}(x_{t},u_{t}) = r_{t}(x_{t},u_{t}) + V_{t+1}(f(x_{t},u_{t}))\\
V_{t}(x_{t}) = \max_{u_{t}} Q_{t}(x_{t},u_{t})
x_{t} は時刻 t における状態変数、u_{t} は時刻 t における行動（制御問題で言う制御入力の事）です。f(x,u) は
なる状態方程式です。r_{t}(x_{t},u_{t}) は強化学習の文脈では「報酬」、DDP含むモデル予測制御の文脈では「ステージコスト」と呼ばれる関数で、「時刻 t に状態（変数）が x_{t} で、その時行動 u_{t} を選択した時に貰えるポイント」です。それらを踏まえて説明すると、Q_{t}(x_{t},u_{t}) は「時刻 t に状態（変数）x_{t} で、その時に行動 u_{t} を選択した場合、将来的にもらえる合計ポイントの最大値」を表す関数です。モデル予測制御も強化学習もこの「ポイント」を「将来貰う分も含めて」上手く最大化（もしくは最小化）する様に行動 u_{t} を決定する為の手法です。
DDP（iLQR）での行動決定
主題では無いので大まかな説明に留めます。
（自分担当の）次回の記事でDDP/iLQRをきちんと解説します。どうかそれまでお待ちいただければと思います。ですが、もし今すぐ細かい説明が欲しいという方がいらっしゃいましたら、以下のqiita記事が参考になるかと思います。ちなみに、DDPとiLQRはアルゴリズム上はほぼ（と言うか99%）同じです。
DDPでは、行動価値関数を二次形式で近似し、最適化して行きます。まず、何かしらの初期解 \bar{u}\_{t}, \bar{x}\_{t} があるとします（複雑な問題でない限り初期解は大体どんな値でも大丈夫です）。二次形式で近似すると次のようになります。偏微分やヘッシアンは微分した変数を添え字に加える事で表現しています（例えば、Q_{t,uu} は Q_{t} を u_{t} で二階微分したヘッシアンです）。
Q_{t}(x_{t},u_{t}) \cong Q_{t}(\bar{x}_{t},\bar{u}_{t}) + \frac{1}{2} \delta u_{t}^{T} Q_{t,uu} \delta u_{t} + Q_{t,u} \delta u_{t} + \frac{1}{2} \delta x_{t}^{T} Q_{t,xx} \delta x_{t} + Q_{t,x} \delta x_{t} + \delta x_{t}^{T} Q_{t,xu} \delta u_{t}\\
Q_{t,uu} = r_{t,uu} + \left(\frac{\partial f}{\partial u}\right)^{T} V_{t+1,xx} \left(\frac{\partial f}{\partial u}\right)\\
Q_{t,u} = r_{t,u} + V_{t+1,x} \left(\frac{\partial f}{\partial u}\right)\\
Q_{t,xx} = r_{t,xx} + \left(\frac{\partial f}{\partial x}\right)^{T} V_{t+1,xx} \left(\frac{\partial f}{\partial x}\right)\\
Q_{t,x} = r_{t,x} + V_{t+1,x} \left(\frac{\partial f}{\partial x}\right)\\
Q_{t,xu} = r_{t,xu} + \left(\frac{\partial f}{\partial x}\right)^{T} V_{t+1,xx} \left(\frac{\partial f}{\partial u}\right)\\
\delta u_{t} \triangleq u_{t} - \bar{u}_{t}, \ \delta x_{t} \triangleq x_{t} - \bar{x}_{t}
Q_{t}(x_{t},u_{t}) が最大値を取る u_{t} を考える代わりに、この二次形式で近似した形が最大値を取る \delta u_{t} を考えます。二次形式ですから、\partial Q_{t} / \partial \delta u_{t} = 0 となる \delta u_{t} を求めれば良いわけです。
\begin{align}
\frac{\partial Q_{t}}{\partial \delta u_{t}} &= \delta u_{t}^{T} Q_{t,uu} + Q_{t,u} + \delta x_{t}^{T} Q_{t,xu}\\
&= 0 \\
\therefore \delta u_{t}^{*} &= - Q_{t,uu}^{-1} Q_{t,ux} \delta x_{t} - Q_{t,uu}^{-1} Q_{t,u}^{T}
\end{align}
最適解はこのようになります（*は最適解を表すマークとして使っています）。\delta x_{t} は前の時刻の入力に依存するので、すぐには求まりません。なので \delta x_{t} の係数と定数項である -Q_{t,uu}^{-1} Q_{t,ux} と - Q_{t,uu}^{-1} Q_{t,u}^{T} の値を記録しておきます。また、説明は省いていますが、求まった \delta u_{t}^{*} から V_{t,xx} と V_{t,x} を計算しておきます（ここら辺の流れは先ほど挙げたqiita記事を参照して頂ければと思います）。この V_{t,xx},V_{t,x} は \delta u_{t-1}^{*} を求めるのに使います。これを未来から過去に向かって、つまり t が大きい方から小さい方に向かって現在時刻（t=0とします）まで解き、係数 -Q_{t,uu}^{-1} Q_{t,ux} と 定数項 - Q_{t,uu}^{-1} Q_{t,u}^{T} を記録して行きます。この流れを Backward Pass と言います。続けて行くと t=0 に到達しますが、\delta x_{0} は現在の状態変数の微小変化なわけですが、現在の状態は変えられないので、当然 \delta x_{0} = 0 となります。なので、
\begin{align}
\delta u_{0}^{*} &= - Q_{0,uu}^{-1} Q_{0,ux} \delta x_{0} - Q_{0,uu}^{-1} Q_{0,u}^{T}\\
&= - Q_{0,uu}^{-1} Q_{0,u}^{T}\\
\delta x_{1} &= \frac{\partial f}{\partial x} \delta x_{0} + \frac{\partial f}{\partial u} \delta u_{0}^{*}\\
&= \frac{\partial f}{\partial u} \delta u_{0}^{*}
\end{align}
と求める事が出来ます。\delta x_{1} が求まったので、同じ様に \delta u_{1}^{*} や \delta x_{2} も求まります。この流れを未来に向かって、つまり t が大きくなる方に向かって行えば、\delta u_{t}^{*} と \delta x_{t} を求めて行くことが出来ます。この未来に向かって解を求めて行く流れを Forward Pass と言います。この Backward Pass と Forward Pass を何回も繰り返す事で最適な u_{t} を求めるのがDDPの手法です。
今回の記事においては「数式的な最適化手法を使ってベルマン方程式を解いている」「価値関数を二次形式で局所的に近似して最小化するのを繰り返している」と理解して頂ければ大丈夫です。
強化学習での行動決定
強化学習にも色々あるのですが、良く知られているであろう手法を説明します。まず、u_{t} を離散化、有限個数の飛び飛びの値にします。例えば、自動車運転でハンドルを切る角度を行動とするなら、左30°、20°、10°、真正面（0°）、右10°、20°、30°の7通りにする言う感じです。その上で、行動価値関数 Q_{t}(x_{t},u_{t}) をニューラルネットで近似します。強化学習ではこのニューラルネットに学習させ、真の行動価値関数の値に近づけさせていきます。学習中の行動決定では、全ての有限個の行動に対してニューラルネットで Q_{t}(x_{t},u_{t}) を計算し、値が一番大きかった行動を最適な行動として選択します。本当はε-greedy法など、探索のためのランダム性を残す場合が多いのですが、ここではその説明は割愛します。ただ、この「行動価値関数を計算して、一番値の大きくなる行動を選ぶ」と言うやり方だと、連続した値を行動にとる事が出来ません。先ほどの自動車運転のたとえで言うなら「右に15°」と言う行動はとれなくなります。
連続した行動を取れるように改良する研究は今回紹介するものだけではありません。その中でもActor-Critic法など、既によく知られているものもあります。この記事で紹介するのはあくまで数あるそうした研究の中の一つです。
Deep Differential Dynamic Programming（D3P）
強化学習での行動決定において、DDPのアルゴリズムを使う事で連続行動を取れるようにしたのが今回紹介するD3Pです。行動価値関数 Q_{t}(x_{t},u_{t}) をニューラルネット学習する場合に使える手法の様です。最初に書いた通り、学習部分は既存の手法を流用しているので、行動決定の部分に絞って説明します。
DDPの定式化の変更
DDPの計算において、ヘッシアン Q_{t,uu} や Q_{t,xx} が登場しました。理由は良く分からないのですが、元論文ではヘッシアンの計算を避けるためにDDPの定式化を少し変更しています。恐らくヘッシアンの計算負荷が重いためかと思われます。
Pytorchのドキュメントも確認してみたのですが、一応下記にある通り、ニューラルネットからヤコビアンもヘッシアンも計算可能な様です。
まず、Q_{t}(x_{t},u_{t}) を二次形式で近似するのではなく、次の様に一次までのテーラー展開で近似します。
Q_{t}(x_{t},u_{t}) \cong Q_{t}(\bar{x}_{t},\bar{u}_{t}) + Q_{t,x} \delta x_{t} + Q_{t,u} \delta u_{t}
そして、これを直接最大化するのではなく、次の様に最適化問題を変形します。
\delta u_{t} = \argmin_{\delta u_{t}} \ \left( V_{max} - Q_{t}(\bar{x}_{t},\bar{u}_{t}) - Q_{t,x} \delta x_{t} - Q_{t,u} \delta u_{t} \right)^{2}
V_{max} は人間が決める定数で、Q_{t}(\bar{x}\_{t},\bar{u}\_{t}) の値以下にならないように設定します。元のDDP同様、\delta u_{t} で偏微分して0になる時を考えます。
\begin{align}
\frac{\partial}{\partial \delta u_{t}} \left( V_{max} - Q_{t}(\bar{x}_{t},\bar{u}_{t}) - Q_{t,x} \delta x_{t} - Q_{t,u} \delta u_{t} \right)^{2} &= 2 \left( V_{max} - Q_{t}(\bar{x}_{t},\bar{u}_{t}) - Q_{t,x} \delta x_{t} - Q_{t,u} \delta u_{t} \right) (-Q_{t,u})\\
&= 0
\end{align}\\
\therefore \delta u_{t}^{*} =
\begin{cases}
-Q_{t,u}^{-1}Q_{t,x} \delta x_{t} - Q_{t,u}^{-1} \left( Q_{t}(\bar{x}_{t},\bar{u}_{t}) - V_{max} \right) & (u_{t}が一次元の時)\\
-\left( Q_{t,u}^{T} Q_{t,u} \right)^{-1} Q_{t,u}^{T} Q_{t,x} \delta x_{t} - \left( Q_{t,u}^{T} Q_{t,u} \right)^{-1} Q_{t,u}^{T} \left( Q_{t}(\bar{x}_{t},\bar{u}_{t}) - V_{max} \right) & (u_{t}が多次元の時)
\end{cases}
\*はここでも最適解を表すマークとして使っています。ここで、u_{t} が多次元の場合は Q_{t,u} がベクトルとなり逆行列が定義できないので、代わりに最小二乗型一般化逆行列を使っています。
次に、この\delta u_{t}^{*}からV_{t,x}を考えます。ここではV_{t}(x_{t}) の一次のテイラー展開を考えます（以下、\delta u_{t}^{\*} = -K \delta x_{t} - d と略記します）。まず、普通にテイラー展開すれば、
V_{t}(\bar{x}_{t}+\delta x_{t}) \cong V_{t}(\bar{x}_{t}) + V_{t,x} \delta x_{t}
となります。また、次の様にも式変形できます。
\begin{align}
V_{t}(\bar{x}_{t}+\delta x_{t}) &= Q_{t} (\bar{x}_{t}+\delta x_{t},\bar{u}_{t}+\delta u_{t}^{*})\\
&\cong Q_{t}(\bar{x}_{t},\bar{u}_{t}) + Q_{t,x} \delta x_{t} + Q_{t,u} \delta u_{t}^{*}\\
&= \left( Q_{t}(\bar{x}_{t},\bar{u}_{t}) - Q_{t,u} d \right) + \left( Q_{t,x} - Q_{t,u}K \right) \delta x_{t}
\end{align}
両者の \delta x_{t} の係数は等しくなるはずです。つまり、
V_{t,x} \cong Q_{t,x} - Q_{t,u}K
と求められます。後は元の DDP の Backward Pass の様に未来から過去に向かって K と d を計算して行きます。Forward Pass の流れは元のDDPと同じです。
ニューラルネットによる行動価値関数の計算
DDPの改良アルゴリズムに出てくる Q_{t,u} 等の偏微分やヘッシアンの値はニューラルネットで計算されます。ただ、偏微分ごとに新しいニューラルネットを作るのではなく、行動価値関数 Q_{t}(x_{t},u_{t}) を近似するニューラルネットから求められます。元論文では以下の関数を使っているようです。
使っている関数が少し違いますが、以下のqiita記事も参考になるかと思います。
最後に
強化学習とMPCを組み合わせると言う意味では弊社が以前解説記事を出したTD-MPCと似ているかなと思います。DDPでヘッシアンの計算を省略する定式化は他の場面でも使えそうな気がします。
参考文献
最後に参考文献をまとめておきます。
元論文
その他参考文献
Discussion