DeepMDP: Learning Continuous Latent Space Models for Representation Learningを読んだ際のメモ

　本当にただのメモだし意味もわからないままに式を写しているだけなので注意。特に数学の専門用語など誤訳も多そう。力のある人は自分で読んで。

出典

　ICML2019に採択

概要

状態表現空間の中でのMDPとしてDeepMDPを定式化
報酬予測と次状態表現予測について適切に損失を設定しそれらを最小化すると、状態空間としての質と環境モデルとしての質を理論的に保証可能
Atariゲームにおいて補助タスクとして組み込むことでモデルフリー手法強化学習のパフォーマンスが改善

f:id:tokumini:20190914162648p:plain

2. 背景:DeepMDPの定義

2.1 マルコフ決定過程(Markov Decision Process : MDP)

マルコフ決定過程 $\mathcal{M} = \langle \mathcal{S}, \mathcal{A}, \mathcal{R}, \mathcal{P}, \gamma \rangle$

$\Pi$ : 定常方策 $\pi$ の集合
$V^{\pi}(s)$ : 状態 $s$ から方策 $\pi$ に従って得られる期待収益
$Q^{\pi}(s, a)$ : 状態 $s$ で行動 $a$ を取った以降方策 $\pi$ に従って得られる期待収益
$\mathcal{P}_{\bar{\pi}}$ : 行動によらない遷移確率
$\mathcal{P}_{\bar{\pi}}(s'|s) = \sum_{a\in\mathcal{A}} \mathcal{P}(s'|s, a)\pi(a|s)$
$\mathcal{R}_{\bar{\pi}}$ : 行動によらない報酬
$\pi^{*}$ : $\mathcal{M}$ における最適方策
$\varepsilon_{\pi}(s)$ : 方策 $\pi$ の下での状態の定常分布
$\varepsilon_{\pi}(s, a) = \varepsilon(s)\pi(a|s)$

2.2 隠れ空間モデル

　次の二つを損失とする。

$$ L_{\bar{\mathcal{R}}}(s, a) = |\mathcal{R}(s, a) - \bar{\mathcal{R}}\left(\phi(s), a \right)| $$

$$ L_{\bar{\mathcal{P}}}(s, a) = \mathcal{D}\left(\phi\mathcal{P}(\cdot|s, a), \bar{\mathcal{P}}(\cdot|\phi(s), a) \right) $$

2.3 Wasserstein距離

　 $W_d(P,Q)$ を空間 $d$ における二つの分布 $P, Q$ のWasserstein距離とする。これは $P$ から $Q$ へ輸送する最小コストと一致する。ここである粒子を $x$ から $y$ へと移動させるコストは距離関数 $d(x, y)$ で測られるとする。

　定義1. 距離空間 $\langle \chi, d \rangle$ における $P, Q$ 間のWasserstein-1距離 $W$ は $$ W_d(P, Q) = \inf_{\lambda \in \Gamma(P, Q)} \int_{\chi \times \chi} d(x,y)\lambda(x,y) dxdy $$ である。ここで $\Gamma(P,Q)$ は $P$ と $Q$ の全てのカップリングの集合である。

　距離関数 $d$ に曖昧性がないとすると $W$ を簡単に表現することができる。Monge-Kantorovich dualityより双対形式として $$ W_d(P, Q) = \sup_{f\in\mathcal{F}_d} | \mathbb{E}_{x \sim P} f(x) - \mathbb{E}_{y \sim Q} f(y) | $$ と表せる。ここで $\mathcal{F}_d$ は、距離関数 $d$ における1-リプシッツ関数の集合 $\mathcal{F}_d = \{ f: |f(x) - f(y)| \le d(x,y) \}$ である。

2.4 価値関数のリプシッツノルム

　方策 $\bar{\pi} \in \bar{\Pi}$ に対する価値関数がリプシッツであるとき、この方策をLipschitz-valuedな方策と書くことにする。

　定義2. $\bar{\mathcal{M}}$ は $d_{\bar{\mathcal{S}}}$ を距離関数とするDeepMDPとする。方策 $\bar{\pi} \in \bar{\Pi}$ が $K_{\bar{V}}$ -Lipshitz-valuedであるとは、全ての状態 $\bar{s}_1, \bar{s}_2 \in \mathcal{S}$ について $$ |\bar{V}^{\bar{\pi}}(\bar{s}_1) - \bar{V}^{\bar{\pi}}(\bar{s}_2)| \le K_{\bar{V}} d_{\bar{\mathcal{S}}}(\bar{s}_1, \bar{s}_2) $$ であり、全ての行動 $a \in \mathcal{A}$ について $$ |\bar{Q}^{\bar{\pi}}(\bar{s}_1, a) - \bar{Q}^{\bar{\pi}}(\bar{s}_2, a)| \le K_{\bar{V}} d_{\bar{\mathcal{S}}}(\bar{s}_1, \bar{s}_2) $$

　定義3. $\bar{\mathcal{M}}$ は $d_{\bar{\mathcal{S}}}$ を距離関数とするDeepMDPとする。二つの状態 $\bar{s_1}, \bar{s_2}$ について収益、遷移分布の距離がそれぞれ $K_{\bar{\mathcal{R}}}, K_{\bar{\mathcal{P}}}$ で抑えられるとき、 $(K_{\bar{\mathcal{R}}}, K_{\bar{\mathcal{P}}})$ -リプシッツであると言う。

$$ |\mathcal{R}(\bar{s_1}, a) - \bar{\mathcal{R}}\left(\bar{s_2}, a \right)| \le K_{\bar{\mathcal{R}}} d_{\bar{\mathcal{S}}}(\bar{s_1}, \bar{s_2}) $$ $$ W \left (\phi \mathcal{P}(\cdot | \bar{s_1}, a), \bar{\mathcal{P}}(\cdot|\bar{s_2}, a) \right) \le K_{\bar{\mathcal{P}}} d_{\bar{\mathcal{S}}}(\bar{s_1}, \bar{s_2}) $$

　前提1. 遷移関数のリプシッツ制約 $K_{\bar{\mathcal{P}}}$ は $\frac{1}{\gamma}$ 未満であるとする。

　厳しめの制約ではあるが、この前提は十分条件であるし、エピソードが有限時間内に終わるときは不要。

　補題1. $\bar{\mathcal{M}}$ を $(K_{\bar{\mathcal{R}}}, K_{\bar{\mathcal{P}}})$ -リプシッツであるとする。このとき以下が成り立つ。

最適方策は $\frac{K_{\bar{\mathcal{R}}}}{1 - \gamma \bar{\mathcal{P}}}$ -リプシッツである。
全ての $K_{\bar{\mathcal{P}}} \le \frac{1}{\gamma}$ である方策は $\frac{K_{\bar{\mathcal{R}}}}{1 - \gamma \bar{\mathcal{P}_{\bar{\pi}}}}$ -リプシッツである。

3. Global DeepMDP Bounds

　行動空間、状態空間全てについてのWasserstein距離を利用した損失を考えたときに成り立つ諸性質。よくわからなかったが良い性質が成り立つのだろうなと思った。

4.Local DeepMDP Bounds

　実際の問題設定では行動空間、状態空間を網羅できる場合は少ない。期待値でも諸性質が同様に成り立つことを示すことでサンプリングによる近似が可能であることを証明。よくわからなかったが良い性質が成り立つのだろうなと思った。

5. 双模倣(Bisimulation)

5.1 双模倣関係

　定義4. MDP $M$ について、状態同士についての同値関係 $B$ は、 $B$ について同値である全ての状態 $s_1, s_2 \in \mathcal{S}$ と全ての行動 $a \in \mathcal{A}$ 次が成り立つとき双模倣的関係であると言う。

$$ R(s_1, a) = R(s_2, a) $$ $$ \mathcal{P}(G|s_1, a) = \mathcal{P}(G|s_2, a), \forall G \in \mathcal{S} / B $$ ここで $\mathcal{S} / B$ は関係 $B$ の下で分割された $\mathcal{S}$ を示し、 $\mathcal{P}(G|s, a) = \sum_{s'\in G}\mathcal{P}(s'|s, a)$ となる。

　双模倣関係は一意ではない。たとえば＝は常に双模倣関係になる。特に関心があるのは $\mathcal{S} / B$ が少ない要素数となるような関係 $B$ を見つけること(上の意味で"同じ"状態をたくさんまとめられる関係をこそ見つけたい)。

　双模倣関係の意味的な解釈は

全ての行動に対して同じ即時報酬がある
次の状態に対する分布が類似

　たとえばAtariゲームだとオブジェクトの色が違うだけというような状態がまとめられると嬉しい。

5.2 双模倣距離

　双模倣関係は二つの状態に関して同一かそうでないかの2値で分けてしまう。少しでも報酬が異なると完全に異なると判定されるのは不便であり、もう少し緩く類似性を評価したい。既存研究としてWasserstein距離を用いて双模倣距離を導入した例がある(Fern 2004)。

　導入する疑似距離は「 $d(x, y) = 0 \Leftrightarrow x = y$ 」以外の距離の公理を満たす必要がある。そうであれば $d(x, y) = 0 ⇒ x B y$ として同値関係の定義に用いることができる。Wasserstein距離はそれを満たしているので疑似距離として用いるのも自然である。こうすると異なる $(x, y)$ でも、輸送コストが0であるならば同値と判断することがでいる。

　定義5. $M$ をMDPとし、空間 $\mathcal{S}$ において $Z$ を疑似距離集合とする。つまり $d(s_1, s_2) \in [0, \infty) \, for \, d \in Z$ 。オペレータ $F:Z \to Z$ を次のように定義する。

$$ F_d(s_1, s_2) = \max_{a}(1 - \gamma)|\mathcal{R}(s, a) - \bar{\mathcal{R}}\left(\phi(s), a \right)| + \gamma\mathcal{D}\left(\phi\mathcal{P}(\cdot|s, a), \bar{\mathcal{P}}(\cdot|\phi(s), a) \right) $$

　このとき

オペレータ $F$ は $\tilde{d}$ を固定点とする縮約となる
$\tilde{d}$ のカーネルは最大双模倣関係になる。

　双模倣距離の利点は、最適価値関数における2状態の価値の差が上から抑えられる点にある。

$$ |V^{*}(s_1) - V^{*}(s_2)| \le \frac{\tilde{d}(s_1, s_2)}{1-\gamma} $$

　このような双模倣距離を用いた既存研究もあるが、計算コストがかかるため深層学習との組み合わせは行われてきていない。

5.3 DeepMDPとの連結

　Wasserstein距離を用いて大域的なＤｅｅｐＭＤＰ損失によって学習された表現 $\phi$ は、双模倣距離に関連付けることができる。

　定理3. 双模倣距離の上限はWasserstein距離と損失とリプシッツ係数から計算できる。（式略）

5.4 $\bar{\Pi}$ の特徴

　双模倣関係を持つ二つの状態について同じ方策を示す方策の集合について考える。DeepMDPでの方策が損失を大域損失を最小化しているとき、だいたい双模倣関係内の方策と一致するようなものが得られる。

　定理4. 大域の損失値を用いて方策の差分の絶対値が抑えられる（式略）

6. Wassersteinを超えて

　補題2,3などにおいて確率距離の選び方はWasserstein距離に限らず他のものも可能。関数のノルムを介して定義される最大平均不一致（MMD)距離族に一般化する。値の差の境界におけるLipschitzノルムの役割は、Wasserstein距離を使用した結果出てくるものであり、違う距離を使えば違う上限が得られる。

　たとえば非常に非Lipschitzの遷移がある環境では、小さいLipschitzノルムを持つ関数で正確なDeepMDPを学ぶことは不可能かもしれない。よって距離関数の選び方を工夫することによってより良い近似ができるかもしれない。またWasserstein距離は計算コストが大きいのでもっと軽いコストの距離で十分ならそれも利点になる。しかしなんだかんだ議論した結果としてはWasserstein距離であることが重要だったりする？あまりよくわからなかった。

7. 表現学習における関連研究

　略

8. 評価実験

　大域最適化から期待値最適化に落とさないと深層学習に適用できないが、課題が2つある。

Wassersteinの最小化→既存研究としてはWasserstein GANやQuantile regressionを用いた手法がある。推定にバイアスが生じるが、決定的な遷移を持つ環境を考えることで回避する。
リプシッツ定数 $K_{\bar{\mathcal{R}}}$ , $K_{\bar{\mathcal{P}}}$ の制御→Wasserstein GANの改良版の考え方を採用