逆強化学習【線形計画】

1. はじめに

逆強化学習について勉強したので、備忘録として残します。
強化学習、逆強化学習、模倣学習に分類することができます。

技術名	入力	出力	アルゴリズム
強化学習	報酬とシミュレーター	最適方策	DQN
逆強化学習	最適方策とシミュレーター	報酬	線形計画
逆強化学習	エキスパートの行動履歴とシミュレーター	報酬	Maximum Entoropy
模倣学習	エキスパートの行動履歴とシミュレーター	最適方策・報酬	GAIL

本記事では、逆強化学習の中のNg and RusselのAlgorithms for Inverse Reinforcement Learningをもとに説明します。以下の流れで説明します。

• 離散的な状態空間において、最適な方策が与えられたときの逆強化学習
• 連続的な状態空間において、最適な方策が与えられたときの逆強化学習

2. 線形計画

線形計画の標準形は下式で定義されます。

\begin{eqnarray}
\min &  &c^Tx \\

s.t. & &Ax=b\\
     & &x\geq 0
\end{eqnarray}

数値解析手法には、主に単体法と内点法があります。単体法は、代数的な構造に着目した数値解析です。実行可能領域の境界を移動することで最適解を求めます。内点法は、非線形計画法の考え方を援用し、実行可能解領域に内点を生成し最適解を求める数値解析です。

詳細は以下をお読みください。

3. 線形計画による逆強化学習

線形計画の標準形式に落とし込むことで、最適方策とシミュレーターから報酬を推定します。

3.1 マルコフ決定過程とベルマン方程式

マルコフ決定過程とベルマン方程式は、強化学習の定式化と同じです。

強化学習と定式化が少し異なるので、そこだけ説明します。

マルコフ決定過程(Markov Decision Process: MDP)を$M=(S,A,P(s^\prime|s,a),\gamma,R)$とし、方策$\pi:S\rightarrow A$について考えます。

方策が$\pi$のとき$\pi(s)=a_1$としたとき、状態価値関数$V^\pi$と行動価値関数$Q^\pi$は以下の式を満足します。

V^\pi (s)=R(s)+\gamma \sum_{s^\prime\in S}p(s^\prime|s,a_1)V^\pi (s^\prime)\\
Q^\pi (s,a)=R(s)+\gamma \sum_{s^\prime\in S}p(s^\prime|s,a)V^\pi (s^\prime)

状態$s$にたどりつけたことへの報酬として$R(s)$が与えられます。ニュアンスとしては、現在地が状態$s$とわかっているため、報酬が決定論的に定まり、報酬の計算に期待値を用いる必要がない点に注意してください。

このときの、最適方策は以下の式で表されます。

\pi(s)\in \arg \max_{a\in A}Q^\pi (s,a)

3.2 離散的な状態空間における逆強化学習（その１）

最適方策$\pi$が与えらたとき、報酬としてあるべき姿を式で表現してみましょう。

3.2.1 1つ目の制約式

状態$s_i$のときの報酬$R(s_i)$の上限値を$R_{\max}$とします。

3.2.2 2つ目の制約式

最適方策$\pi$が与えらたとき、$\pi(s)=a_1$とします。また、$a\in A\backslash a_1$とします。このとき、以下が成り立ちます。

(\mathbf{P}_{a_1}-\mathbf{P}_{a})(\mathbf{I}-\gamma \mathbf{P}_{a_1})^{-1}\mathbf{R} \geq 0
\tag{1}

ただし、

(\mathbf{P}_{a})_{ij}=p(s_j|s_i,a)\\
(\mathbf{P}_{a_1})_{ij}=p(s_j|s_i,a_1)\\
\mathbf{R}=[R(s_1),R(s_2),\cdots,R(s_n)]^T\\
i = 1,2,\cdots,n\\
j = 1,2,\cdots,n

これは、状態価値関数$V^\pi$をもとに少し式展開すれば得ることが出来ます。
簡単に説明してみます。

V^\pi(s_1)=R(s_1)+\gamma [p(s_1|s_1,a_1), p(s_2|s_1,a_1),\cdots,p(s_n|s_1,a_1)][V^\pi(s_1),V^\pi(s_2),\cdots,V^\pi(s_n)]^T\\
V^\pi(s_2)=R(s_2)+\gamma [p(s_1|s_2,a_1), p(s_2|s_2,a_1),\cdots,p(s_n|s_2,a_1)][V^\pi(s_1),V^\pi(s_2),\cdots,V^\pi(s_n)]^T\\
\vdots\\
V^\pi(s_n)=R(s_n)+\gamma [p(s_1|s_n,a_1), p(s_2|s_n,a_1),\cdots,p(s_n|s_n,a_1)][V^\pi(s_1),V^\pi(s_2),\cdots,V^\pi(s_n)]^T

これを行列表示すれば、

\mathbf{V}^\pi=\mathbf{R}+\gamma \mathbf{P}_{a_1}\mathbf{V}^\pi

式を整理すれば、

\mathbf{V}^\pi=(\mathbf{I}-\gamma \mathbf{P}_{a_1})^{-1}\mathbf{R}
\tag{2}

ここで、$a_1=\pi(s)$の行動価値関数$Q^{\pi}$と、$a\in A\backslash a_1$の行動価値関数$Q^{\pi}$を比較してみます。任意の状態$s_i$において、

Q^{\pi}(s_i,a_1) \geq Q^{\pi}(s_i,a)

R(s_i)+\gamma \sum_{s^\prime\in S}p(s^\prime|s_i,a_1)V^\pi (s^\prime)
\geq
R(s_i)+\gamma \sum_{s^\prime\in S}p(s^\prime|s_i,a)V^\pi (s^\prime)

式を整理すれば

\mathbf{R}+ \gamma\mathbf{P}_{a_1}\mathbf{V}^\pi\geq 
\mathbf{R}+ \gamma\mathbf{P}_{a}\mathbf{V}^\pi

式を整理して、式(2)を代入すれば

\mathbf{P}_{a_1}(\mathbf{I}-\gamma \mathbf{P}_{a_1})^{-1}\mathbf{R}
\geq
\mathbf{P}_{a}(\mathbf{I}-\gamma \mathbf{P}_{a_1})^{-1}\mathbf{R}

よって、式(1)を得ることが出来ます。

(\mathbf{P}_{a_1}-\mathbf{P}_{a})(\mathbf{I}-\gamma \mathbf{P}_{a_1})^{-1}\mathbf{R} \geq 0
\tag{1}

3.2.3 目的関数

報酬はどうあるべきでしょうか。
二番手の報酬の総和より、一番手の報酬の総和が大きくなるように報酬を定めたほうがよさそうです。

最適方策$\pi$に基づいて行動$a_1=\pi(s)$した場合の行動価値関数$Q^\pi$と、行動$a\in A\backslash a_1$した場合の行動価値関数$Q^\pi$の最大値の差分が最大となるように報酬を設計すればよさそうです。

\max _{\mathbf{R}}
\sum_{s\in S}\left(Q^\pi (s,a_1) -\max_{a\in A\backslash a_1}Q^\pi(s,a)\right)

さて、行動価値関数と状態価値観数は下式で与えられているのでした。

\mathbf{Q}^\pi_a=\mathbf{R}+ \mathbf{P}_{a}\mathbf{V}^\pi\\
\mathbf{V}^\pi = (\mathbf{I}-\gamma \mathbf{P}_a)^{-1}\mathbf{R}

代入して整理していきます。$\max$演算子は各行毎に実行されていることに注意してください。

\max _{\mathbf{R}}
\mathbf{1}^T\left(\mathbf{Q}^\pi_{a_1}-\max_{a\in A\backslash a_1}\mathbf{Q}^\pi_{a}\right)

よって、

\max _{\mathbf{R}}
\mathbf{1}^T\left(\mathbf{R} + \mathbf{P}_{a_1}\mathbf{V}^\pi - \mathbf{R}- \max_{a\in A\backslash a_1}\mathbf{P}_{a}\mathbf{V}^\pi\right)

よって、

\max _{\mathbf{R}}
\mathbf{1}^T\left(\mathbf{P}_{a_1}- \max_{a\in A\backslash a_1}\mathbf{P}_{a}\right)\mathbf{V}^\pi

よって、

\max _{\mathbf{R}}
\mathbf{1}^T\left(\mathbf{P}_{a_1}- \max_{a\in A\backslash a_1}\mathbf{P}_{a}\right)(\mathbf{I}-\gamma \mathbf{P}_a)^{-1}\mathbf{R}
\tag{3}

式(3)だけでもよいのですが、報酬は出来るだけスパースであってほしいです。式(3)に正則化項を追加します。

\max _{\mathbf{R}}
\mathbf{1}^T\left(\mathbf{P}_{a_1}- \max_{a\in A\backslash a_1}\mathbf{P}_{a}\right)(\mathbf{I}-\gamma \mathbf{P}_a)^{-1}\mathbf{R} - \lambda \|\mathbf{R}\|_1
\tag{4}

3.2.4 まとめ

\begin{eqnarray}
\max_{\mathbf{R}} &  &\mathbf{1}^T\left(\mathbf{P}_{a_1}- \max_{a\in A\backslash a_1}\mathbf{P}_{a}\right)(\mathbf{I}-\gamma \mathbf{P}_a)^{-1}\mathbf{R} - \lambda \|\mathbf{R}\|_1 \\

s.t. & &
(\mathbf{P}_{a_1}-\mathbf{P}_{a})(\mathbf{I}-\gamma \mathbf{P}_{a_1})^{-1}\mathbf{R} \geq 0 , \ \forall a\in A\backslash a_1\\
     & &|R_i|\leq R_{\max}
\end{eqnarray}
\tag{5}

3.3 連続な状態空間における逆強化学習（その２）

この節は、論文には即しておりませんので、ご承知おきください。

3.3.1 報酬を関数近似で表現する。

報酬を関数近似で表現すれば、連続な状態空間でも逆強化学習ができます。

R(s)=\alpha_1\phi_1(s)+\alpha_2\phi_2(s)+\cdots+\alpha_d\phi_d(s)\\
    = \boldsymbol{\phi}(s)^T\boldsymbol{\alpha} 

つまり、

\mathbf{R}_i=\boldsymbol{\phi}(s_i)^T\boldsymbol{\alpha} 

よって、

\mathbf{R}=\boldsymbol{\Phi}\boldsymbol{\alpha} \\
\mathbf{\Phi}=[\boldsymbol{\phi}(s_1),\boldsymbol{\phi}(s_2),\cdots,\boldsymbol{\phi}(s_n)]^T

これを式(5)に代入してあげれば終わりです。

\begin{eqnarray}
\max_{\boldsymbol{\alpha},\epsilon} &  &\mathbf{1}^T\left(\mathbf{P}_{a_1}- \max_{a\in A\backslash a_1}\mathbf{P}_{a}\right)(\mathbf{I}-\gamma \mathbf{P}_a)^{-1}\boldsymbol{\Phi}\boldsymbol{\alpha}  - \lambda \|\boldsymbol{\alpha} \|_1+\epsilon\\

s.t. & &
(\mathbf{P}_{a_1}-\mathbf{P}_{a})(\mathbf{I}+\gamma \mathbf{P}_{a_1})^{-1}\boldsymbol{\Phi}\boldsymbol{\alpha} \geq \epsilon , \ \forall a\in A\backslash a_1\\
     & &|\alpha_i|\leq 1\\

&&
\epsilon\leq 0
\end{eqnarray}
\tag{6}

参考文献

• 機械学習スタートアップシリーズ Pythonで学ぶ強化学習 [改訂第2版] 入門から実践まで、久保隆宏
• 高校数学で理解する逆強化学習（その１）
• 高校数学で理解する逆強化学習（その2）