MPC/LQRと強化学習の方策勾配定理の比較

April 08, 2021 by Chachay
, , , ,

強化学習のPolicy Gradient法では、制御則をパラメータ\(\theta\)で表現される方策関数\(u = \pi_{\theta}(x) \)を最適化するコスト関数\(J\)のヤコビアンを使って最急降下法にて

\[ \theta \leftarrow \theta - \alpha \nabla_{\theta} J \]
を繰り返すことにより、最適な(非線形)状態フィードバック制御のパラメータを求める。

(上記は、1.コスト関数の最小化を行う 2. 方策関数はDeterministicとした前提を置いている)

OpenAI Spinning UpのPart 3やLil'LogのPolicy Gradient AlgorithmsにてPolicy Gradientの導出方法が紹介されているが、陽に制御対象のシステムがマルコフ決定過程に従うとしており状態遷移は確率的であるため、制御則\(\pi\)のもと状態\(s_0\)から状態\(s\)まで kステップで変化する遷移確率 \(\rho(s_0 \to s, k) \)をもちいて

\[ \nabla_\theta J = \sum_{s}\sum_{k=0}^\infty \rho^\pi(s_0 \to s, k) \sum_{a \in \mathcal{A}} \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) \]
Deterministic Policy Gradientのケースで、
\[ \nabla_\theta J(\pi_\theta) = \int_{\mathcal{S}} \rho^\pi (s) \nabla_\theta \pi_\theta (s) \nabla_a Q^\pi (s,a) \vert_{a=\pi_\theta (s)} \text{d}s \]
と整理される。以上の特殊な状態として、システムが \(x^+ = f(x, u) \)に従う場合について考えたい。 この場合、ナイーブに遷移確率として\(\delta(x^+ − f(x, a))\)を採用し、計算すればよいのだが、 よくわからなかったので元の定義に立ち返った。

問題設定

システムの違い

制御対象がMDPで遷移が確率的なStochastic Transition Dynamic Systemと、いわゆるシステム方程式で表されるDeterministic Dynamic Systemでの違い

Deterministic Stohacstic
\( x^+ = f(x, u) \) \( x^+ \sim p(x^+ \mid x, u) \)
\( V^\pi(f(x, \pi(x))) \) \(\displaystyle \int_{\mathcal{X}} p(x^+ \mid x, \pi(x)) V^\pi (x^+) \text{d} x^+\)

コスト関数等の定義

名前 数式 説明
初期コスト関数 \(C_{init}(x)\) RLとMPC/LQRのコスト関数を一致させるために定義. 初期値のみにより最適化の文脈では定数.
ステージ・コスト関数 \(C(u, x^+)\) 強化学習では\(R=-C\)として報酬で定義されることが一般的
終端コスト関数 \(C_f(x^+)\) 強化学習では\(R=-C\)として報酬で定義されることが一般的
制御入力列 \(\mathcal{U}_N = \{u_{0}, u_{1}, \cdots, u_{N-1} \} \) Time horizonをNとした
コスト関数 \( J_N(\mathcal{U}_N ) = \mathbb{E}_{x \sim \mathcal{D}} [C_{init}(x) + V_N^{\mathcal{U}_N}(x)] \) Time horizonをNとした
状態価値関数 \( V^{\mathcal{U}}_N(x) = \displaystyle \sum_{i=0}^{N-1} C(u_{i}, x_{i+1}) \\ \quad + C_f(x_{N}) - C(u_{N-1}, x_{N}) \) ただし、\(x_0=x\). \(x_{k+1} = f(x_k, u_k) \)または\(x_{k+1} \sim p(\cdot \mid x_k, u_k) \)に従う。
行動価値関数 \( Q^{\mathcal{U}}_N(x, u) = C(u, x^+) + V^{\mathcal{U}}_{N-1}(x^+) \)

補足: LQRの場合

LQRの場合、\(N \rightarrow \infty \)であって\(\pi_\theta(x)=\theta \cdot x\)の制御則に対して、正定行列 \(Q, R\)を用いたコスト関数を用いて (行動価値関数の\(Q\)と記号が被ってしまってごめんなさい)

\[ \begin{array}{ll} \displaystyle \min_{\theta} & J(\pi_\theta) = \mathbb{E}_{x_0 \sim \mathcal{D}} [C_{init}(x_0) + \displaystyle \sum_{i=0}^{\infty} C( \pi_{\theta}(x_i), x_{i+1})] \\ {\rm s.t.} & C(u, x) = \displaystyle \frac{1}{2} x^{\intercal} Q x + \displaystyle \frac{1}{2} u^{\intercal} R u \\ & x_{t+1} = A x_t + B u_t \\ \end{array} \]
を求める。こちらの方面の話では方策勾配法でLQRを解くを参照のこと。

補足: MPCの場合

MPCの場合、初期値が与えられ、オンラインで最適化問題を解く。終端コストの定数\(P\)について、LQRのリッカチ代数方程式のリッカチ行列と一致させると制約条件がない下記の問題設定ではLQRと同じ制御入力列が求まる[Mayne et al., 2000]。

\[ \begin{array}{ll} \displaystyle \min_{\mathcal{U}} & V^{\mathcal{U}}(x_0) + C_{init}(x_0) \\ {\rm s.t.} & C(u, x) = \displaystyle \frac{1}{2} x^{\intercal} Q x + \displaystyle \frac{1}{2} u^{\intercal} R u \\ & C_{init}(x) = \displaystyle \frac{1}{2} x^{\intercal} Q x \\ & C_f(x) = \displaystyle \frac{1}{2} x^{\intercal} P x \\ & x_{t+1} = A x_t + B u_t \\ \end{array} \]

方策勾配定理の導出

Step 1

以下はDeterministic Policy Gradient AlgorithmsのAppendix Bからの転記である。記号を先までのシステム方程式と揃えた。 \(\mathcal{U}^{\pi_\theta} = \{\pi_\theta(x_0), \pi_\theta(x_1), \cdots, \pi_\theta(x_{N-1})\}\)とし、 これを適用した状態価値関数を\(V^\pi \)と簡略表記して

\[ \begin{aligned} \nabla_\theta V^\pi &= \nabla_\theta Q^\pi(x, \pi(x)) \\ &= \nabla_\theta \left( \int_{\mathcal{X}} p(x^+ | x, \pi(x)) \left[C(\pi(x), x^+) +V^\pi (x^+) \right] \text{d} x^+ \right) \\ &= \int_{\mathcal{X}} \nabla_{u} p \nabla_{\theta} \pi \left[C(\cdot) + V^\pi(\cdot) \right] \text{d} x^+ + \int_{\mathcal{X}} p(\cdot) \nabla_{u} C(\cdot) \nabla_{\theta} \pi \, \text{d} x^+ + \int_{\mathcal{X}} p(\cdot) \nabla_{\theta} V^\pi \text{d} x^+ \\ &= \nabla_u \left( \int_{\mathcal{X}} p(\cdot) \left[C(\cdot) +V^\pi (\cdot) \right] \text{d} x^+ \right) \nabla_\theta \pi + \int_{\mathcal{X}} p(\cdot) \nabla_{\theta} V^\pi \text{d} x^+ \\ &= \nabla_u Q \cdot \nabla_{\theta} \pi + \int_{\mathcal{X}} p(x^+ | x, \pi(x)) \nabla_{\theta} V^\pi (x^+) \text{d} x^+ \\ \end{aligned} \]

同じことがシステムがDeterministicの場合については\(\nabla_u Q = \nabla_u C + \nabla_x C \cdot \nabla_u f + \nabla_x V \cdot \nabla_u f \)であって、

\[ \begin{aligned} \nabla_\theta V^\pi &= \nabla_\theta \left( C(\pi(x), f(x, \pi(x))) + V^\pi \left(f(x, \pi(x))\right) \right) \\ &= \nabla_u C \cdot \nabla_{\theta} \pi + \nabla_x C \cdot \nabla_{u} f \cdot \nabla_{\theta} \pi + \nabla_x V \cdot \nabla_u f \cdot \nabla_\theta \pi + \nabla_{\theta} V^\pi \left(f(x, \pi(x))\right) \\ &= \nabla_u Q \cdot \nabla_{\theta} \pi + \nabla_{\theta} V^\pi \left(f(x, \pi(x))\right) \\ \end{aligned} \]

ここまでについて一般にディラックのデルタ関数について

\[ \int_{-\infty}^\infty f(t) \delta(t-T) dt = f(T) \]
であるので[Wiki:EN]、\(p(x^+ \mid x, u) = \delta(x^+ − f(x, u)) \)とすると
\[ \int_{\mathcal{X}} p(\cdot) \nabla_{\theta} V^\pi (x^+) \text{d} x^+ = \nabla_{\theta} V^\pi \left(f(x, \pi(x))\right) \]
であって、両者は一致している。

Step 2

さて、この式を繰り返し適用して展開する。Stochasticモデルの場合は状態 \(x\)から\(x^+\)までtステップで遷移する遷移確率\(p(x \rightarrow x^+, t, \pi)\)を用いて

\[ \begin{array}{rcl} \nabla_\theta V^\pi &=& \nabla_u Q \cdot \nabla_{\theta} \pi \\ && + \displaystyle \int_{\mathcal{X}} p(x^+ \mid x, \pi(x)) \nabla_{\theta} V^\pi (x^+) \, \text{d} x^+ \\ &=& \nabla_u Q \cdot \nabla_{\theta} \pi \\ && + \displaystyle \int_{\mathcal{X}} p(x^+ \mid x, \pi(x)) \nabla_u Q \cdot \nabla_{\theta} \pi \, \text{d} x^+ \\ && + \displaystyle \int_{\mathcal{X}} p(x^+ \mid x, \pi(x)) \displaystyle \int_{\mathcal{X}} p(x^{++} \mid x^+, \pi(x^+)) \nabla_{\theta} V^\pi (x^{++}) \text{d} x^{++} \text{d} x^+ \\ &\vdots&\\ &=& \displaystyle \int_{\mathcal{X}} \displaystyle \sum_{t=0}^{N-1} p(x \rightarrow x^+, t, \pi) \nabla_u Q \cdot \nabla_{\theta} \pi \, \text{d} x^+ \\ \end{array} \]
この式の遷移確率をDeterministicなモデルに置き換えると、遷移が確定的に定まるので
\[ \begin{array}{rcl} \nabla_\theta V^\pi &=& \displaystyle \sum_{t=0}^{N-1} \nabla_u Q \vert_{x_k, u_k} \cdot \nabla_{\theta} \pi \vert_{x_k} \\ &=& \displaystyle \sum_{t=0}^{N-1} \left(\nabla_u C \vert_{u_k, x_{k+1}} + \nabla_x C \vert_{u_k, x_{k+1}} \cdot \nabla_u f \vert_{x_k, u_k} + \nabla_x V \vert_{x_{k+1}} \cdot \nabla_u f \vert_{x_k, u_k} \right) \nabla_{\theta} \pi \vert_{x_k} \\ s.t. && x_{k+1} = f(x_k, u_k) \\ && u_{k} = \pi_\theta(x_k) \\ \end{array} \]
となる。

参考

at
No comments: