本当にただのメモだし意味もわからないままに式を写しているだけなので注意。特に数学の専門用語など誤訳も多そう。力のある人は自分で読んで。
出典
ICML2019に採択
概要
- 状態表現空間の中でのMDPとしてDeepMDPを定式化
- 報酬予測と次状態表現予測について適切に損失を設定しそれらを最小化すると、状態空間としての質と環境モデルとしての質を理論的に保証可能
- Atariゲームにおいて補助タスクとして組み込むことでモデルフリー手法強化学習のパフォーマンスが改善
2. 背景:DeepMDPの定義
2.1 マルコフ決定過程(Markov Decision Process : MDP)
マルコフ決定過程
: 定常方策
の集合
: 状態
から方策に従って得られる期待収益
: 状態で行動
を取った以降方策に従って得られる期待収益
: 行動によらない遷移確率
: 行動によらない報酬
: 
における最適方策
: 方策の下での状態の定常分布
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距離
を空間
における二つの分布
のWasserstein距離とする。これは
から
へ輸送する最小コストと一致する。ここである粒子を
から
へと移動させるコストは距離関数
で測られるとする。
定義1. 距離空間
における間のWasserstein-1距離
は
$$ W_d(P, Q) = \inf_{\lambda \in \Gamma(P, Q)} \int_{\chi \times \chi} d(x,y)\lambda(x,y) dxdy $$
である。ここで
はとの全てのカップリングの集合である。
距離関数に曖昧性がないとするとを簡単に表現することができる。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) | $$
と表せる。ここで
は、距離関数における1-リプシッツ関数の集合
である。
2.4 価値関数のリプシッツノルム
方策
に対する価値関数がリプシッツであるとき、この方策をLipschitz-valuedな方策と書くことにする。
定義2. 
は
を距離関数とするDeepMDPとする。方策が
-Lipshitz-valuedであるとは、全ての状態
について
$$ |\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) $$
であり、全ての行動
について
$$ |\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. は
を距離関数とするDeepMDPとする。二つの状態
について収益、遷移分布の距離がそれぞれ
で抑えられるとき、
-リプシッツであると言う。
$$ |\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. 遷移関数のリプシッツ制約
は
未満であるとする。
厳しめの制約ではあるが、この前提は十分条件であるし、エピソードが有限時間内に終わるときは不要。
補題1. を-リプシッツであるとする。このとき以下が成り立つ。
- 最適方策は
-リプシッツである。
- 全ての
である方策は
-リプシッツである。
3. Global DeepMDP Bounds
行動空間、状態空間全てについてのWasserstein距離を利用した損失を考えたときに成り立つ諸性質。よくわからなかったが良い性質が成り立つのだろうなと思った。
4.Local DeepMDP Bounds
実際の問題設定では行動空間、状態空間を網羅できる場合は少ない。期待値でも諸性質が同様に成り立つことを示すことでサンプリングによる近似が可能であることを証明。よくわからなかったが良い性質が成り立つのだろうなと思った。
5. 双模倣(Bisimulation)
5.1 双模倣関係
定義4. MDP
について、状態同士についての同値関係
は、について同値である全ての状態
と全ての行動次が成り立つとき双模倣的関係であると言う。
$$ 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 $$
ここで
は関係の下で分割された
を示し、
となる。
双模倣関係は一意ではない。たとえば＝は常に双模倣関係になる。特に関心があるのはが少ない要素数となるような関係を見つけること(上の意味で"同じ"状態をたくさんまとめられる関係をこそ見つけたい)。
双模倣関係の意味的な解釈は
- 全ての行動に対して同じ即時報酬がある
- 次の状態に対する分布が類似
たとえばAtariゲームだとオブジェクトの色が違うだけというような状態がまとめられると嬉しい。
5.2 双模倣距離
双模倣関係は二つの状態に関して同一かそうでないかの2値で分けてしまう。少しでも報酬が異なると完全に異なると判定されるのは不便であり、もう少し緩く類似性を評価したい。既存研究としてWasserstein距離を用いて双模倣距離を導入した例がある(Fern 2004)。
導入する疑似距離は「
」以外の距離の公理を満たす必要がある。そうであれば
として同値関係の定義に用いることができる。Wasserstein距離はそれを満たしているので疑似距離として用いるのも自然である。こうすると異なる
でも、輸送コストが0であるならば同値と判断することがでいる。
定義5. をMDPとし、空間において
を疑似距離集合とする。つまり
。オペレータ
を次のように定義する。
$$ 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) $$
このとき
- オペレータ
は
を固定点とする縮約となる
- のカーネルは最大双模倣関係になる。
双模倣距離の利点は、最適価値関数における2状態の価値の差が上から抑えられる点にある。
$$ |V^{*}(s_1) - V^{*}(s_2)| \le \frac{\tilde{d}(s_1, s_2)}{1-\gamma} $$
このような双模倣距離を用いた既存研究もあるが、計算コストがかかるため深層学習との組み合わせは行われてきていない。
5.3 DeepMDPとの連結
Wasserstein距離を用いて大域的なＤｅｅｐＭＤＰ損失によって学習された表現
は、双模倣距離に関連付けることができる。
定理3. 双模倣距離の上限はWasserstein距離と損失とリプシッツ係数から計算できる。（式略）
5.4 
の特徴
双模倣関係を持つ二つの状態について同じ方策を示す方策の集合について考える。DeepMDPでの方策が損失を大域損失を最小化しているとき、だいたい双模倣関係内の方策と一致するようなものが得られる。
定理4. 大域の損失値を用いて方策の差分の絶対値が抑えられる（式略）
6. Wassersteinを超えて
補題2,3などにおいて確率距離の選び方はWasserstein距離に限らず他のものも可能。関数のノルムを介して定義される最大平均不一致（MMD)距離族に一般化する。値の差の境界におけるLipschitzノルムの役割は、Wasserstein距離を使用した結果出てくるものであり、違う距離を使えば違う上限が得られる。
たとえば非常に非Lipschitzの遷移がある環境では、小さいLipschitzノルムを持つ関数で正確なDeepMDPを学ぶことは不可能かもしれない。よって距離関数の選び方を工夫することによってより良い近似ができるかもしれない。またWasserstein距離は計算コストが大きいのでもっと軽いコストの距離で十分ならそれも利点になる。しかしなんだかんだ議論した結果としてはWasserstein距離であることが重要だったりする？ あまりよくわからなかった。
7. 表現学習における関連研究
略
8. 評価実験
大域最適化から期待値最適化に落とさないと深層学習に適用できないが、課題が2つある。
- Wassersteinの最小化→既存研究としてはWasserstein GANやQuantile regressionを用いた手法がある。推定にバイアスが生じるが、決定的な遷移を持つ環境を考えることで回避する。
- リプシッツ定数
,
の制御→Wasserstein GANの改良版の考え方を採用
8.1 ドーナツ世界の実験
円から小さい円をくり抜いた帯状のトラックを車で走るタスク。時計回りに走ると報酬が得られ、中心に近いほど速度が上がる。グレースケール化した32×32ピクセルの画像が入力として与えられ、表現として2次元に落とし込む。
- 上から実際の位置(白い点)
- Autoencoderでの白い点と近い表現を得る位置のヒートマップ
- DeepMDPの表現について白い点と近い表現を得る位置のヒートマップ
を描画した結果(画像の左半分)。
AutoencoderよりもDeepMDPの方がより位置情報を明確に取れている。また画像右側は少し難しいタスクとして、最初に車が4つのトラックのどれかにランダムに配置されるような場合の結果。より顕著に差が出ている。
損失推移は
報酬損失と遷移損失は相反することもあるので両方下がるとは限らない。スケールが違うので大きい方を優先して下げるということになっている。
8.2 Atari2600実験
C51をベースに、DeepMDPの損失を補助タスクとして入れることで性能向上。
コード
著者の実装が公開されている。
結局は決定的環境でやっているので予測と実際の遷移したものとのノルムを考えるだけだと思ったが、コードを読むとなんか違う。謎。
