強化学習における「好奇心」についての論文を読んでみた

強化学習における「好奇心」について論文を2本読んだので、ここで紹介したいなと思います。今回は、シンプルかつ効果的な提案である、という観点で論文を選んでみました。

#強化学習とは？
論文を紹介する前に、そもそも強化学習とは？という部分を軽く述べておこうと思います。
強化学習とは、「何らかの状態にある環境において、エージェントが行動によって報酬、および行動によって変化した環境の『次の状態』を獲得し、それに基づき、エージェントが状態に応じた最適な行動を学習していく」というものです。
この文面だけだと分かりにくいので、図を以下に載せます。

![RL_outline (for media) - コピー.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/418323/1b68fbd5-49e8-0190-af50-f4321c40a159.jpeg)
Fig. 1. 強化学習の概要

**※** 論文によっては、状態 (state) を"observation"、環境 (environment) を"observational space"としています。

$\mathcal{A}$はエージェントがとり得る行動の集合です。
なお、エージェントがとる行動は「方策 (policy)」に基づいて決定されるものとします。有名な方策としては「ε-greedy法」が挙げられます。概要は以下の通り。

1. $\varepsilon$の値を$0<\varepsilon<1$の範囲で一意に定める。
2. 一様分布$U[0,1]$に従う乱数$u$を生成する。
3. 乱数$u$の値が$\varepsilon$以下の場合、エージェントはランダムに行動を選択する (探索する) 。
4. 乱数$u$の値が$\varepsilon$より大きい場合、学習によって得た最善の行動を選択する (利用する) 。

#論文での問題意識
今回読んだ2本の論文では、強化学習に関して共通の問題意識を持っています。
一般的な強化学習手法では、事前に指定された目標状態 (pre-specified goal state) に到達しなければ、方策を更新するための強化、即ち報酬を得ることができません。しかし、現実の多くのタスクは報酬が疎であり、目標状態への到達が起きにくくなっています。

タスクの例としては、「動物が食べ物を探すための行動を学習するとき、食べ物を見つける (報酬を獲得する) までに何マイルも歩かなければならない」(Savinov et al., 2019) という感じです。このようなタスクでは、偶然に目標状態に到達することへの期待 (ランダムな探索) は無駄になり得ます。

そこで、論文では新しい状態への「**好奇心 (curiosity)** 」、即ち**内発的報酬 (intrinsic reward)** を導入することで、報酬が密になり、探索が容易になると述べています。

#Curiosity-driven Exploration by Self-supervised Prediction (Pathak et al., 2017)

本論文では、好奇心を「**エージェントにとっての、自身の行動結果の予測し辛さ**」として扱っています。ここで重要なのは、環境変化の内、「**エージェントの行動による、或いはエージェントに影響し得る環境変化のみを扱う**」という点です。これは、「エージェントの制御外にあり、エージェントに影響を与えない要素」を取り除くためです。具体的な手法としては、「知覚空間」そのものではなく、「知覚空間」を特徴空間に変換したものを行動結果の予測に用いています。

特徴空間の学習には"**self-supervision**"を用います。流れは下記の通りです。

1. 「現在の状態$s_t$」・「次の状態$s_{t+1}$」の特徴表現 (feature encoding) である$\phi(s_t)$、$\phi(s_{t+1})$を入力とし、エージェントの行動$\hat{a_t}$を出力とするニューラルネットワークを訓練し、行動を予測する (proxy inverse dynamics task)
2. 1.の特徴空間を用いて、「現在の状態」の特徴表現$\phi(s_t)$・「行動$a_t$」を入力とし、次の状態の特徴表現$\hat{\phi}(s_{t+1})$を出力するforward dynamics modelを訓練する
3. 2.のforward dynamics modelの予測誤差を内発的報酬$r_t^i$としてエージェントに与え、エージェントの好奇心を促す

1.により、エージェント自身に影響を与えない環境変動要因が特徴空間から除かれるような学習になっています。流れの図解を論文から引用します。

![media_figure1 - コピー.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/418323/ca2a5b82-275c-4a4f-b5c7-2912ccbe1fb3.png)
Fig. 2. 提案の構成 (Pathak et al., 2017)

$r_t^i$が内発的報酬ですね。**Intrinsic Curiosity Module (ICM)** によって$r_t^i$が算出され、外発的報酬$r_t^e$に足し合わされます。
また、ICM内の流れをgifでアニメーション化したものも示します。

![media_makegif_1.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/418323/4539a0a4-64d8-aec7-5d56-42867d28093a.gif)
Fig. 3. 提案の流れ

Inverse model、Forward model、Policy (方策$\pi$) はそれぞれパラメータを持ち、また先の2つは損失関数 (loss function) が定義されています。これらを図中に示すと以下の通りです。

![スライド1.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/418323/c14f61ea-a79b-55a4-a6fa-59d8df67cb19.png)
Fig. 4. ICM内の詳細

![スライド2.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/418323/f18000bf-0df0-bfa2-df55-8d781a9038da.jpeg)
Fig. 5. ICM外の詳細

Policiy (方策$\pi$) については、報酬の和の期待値を最大化するように$\theta_P$を最適化します。

```math
\max_{\theta_P} \mathbb{E}_{\pi(s_t;\theta_P)} \left[\sum_{t}r_t
\right] \tag{1}
```

また、Inverse model、Forward modelについては、損失関数を最小化するように$\theta_I$、$\theta_F$を最適化します。

```math
\min_{\theta_I} L_I(\hat{a}_t,a_t) \tag{2}
```

```math
\min_{\theta_F}L_F\left(\phi(s_t),\hat{\phi}
(s_{t+1})
\right) \tag{3}
```

以上をまとめると、本論文での学習は下記の最適化問題を解くことになります。

```math
\min_{\theta_P, \theta_I, \theta_F}\left[-\lambda \mathbb{E}_{\pi(s_t; \theta_P)}\left[\sum_{t}r_t \right]+(1-\beta)L_I+\beta L_F
\right] \tag{4}
```

ここで、$\beta\ (0\leq \beta \leq 1)$、$\lambda\ (\lambda>0)$はパラメータです。

##実験結果

今回は手法に焦点を当てた記事なので、実験結果は概略のみを示します。
これは、_VizDoom_ (Kempka et al., 2016) というゲームでの実験結果です。本論文で提案された"ICM"、前述のICMからInverse modelを除いた"ICM-pixels"を強化学習アルゴリズムA3C (Mnih et al., 2016) と組み合わせた際の実験結果 (エピソード毎の外発的報酬の推移) は下図の通りです。今回は、報酬について"dense"、"sparse"、"very-sparse"という3つのケースで実験を行っています。

![スライド1.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/418323/bd4bcdb9-c5be-6008-0629-40b483e61c12.png)

Fig. 6. _VizDoom_ (Kempka et al., 2016) での実験結果 (Pathak et al., 2017)

上図において、暗い線は平均、網掛け部分は平均±標準誤差を示しています。
上図より、概して"ICM + A3C"が良好な結果を出していることが分かります。

一方で、スーパーマリオブラザーズでの実験により、内発的報酬のみでは学習が適切に進行しない場合があることも示されています。

#Episodic Curiosity through Reachability (Savinov et al., 2019)

本論文では、新しい観測に対する「驚き」だけでは、新しい観測を得ることに終始してしまい将来を予測できない場合があるとして、**「到達にいくらかの努力を要する観測」に対してのみ報酬ボーナスを与える**、と定式化しています。これにより、1ステップで到達できるような観測に対して報酬ボーナスを与え、エージェントが簡単な行動に終始してしまうことを避けられます。これを実現するために、探索済みの観測を保存する「**エピソード記憶 (episodic memory)** 」を導入します。まとめると、ある観測に対し、エピソード記憶内の観測を起点として「閾値より多くのステップ数」を経なければ到達できないと判断した場合、ボーナス報酬を与えることになります。
上記を図示したものを論文中より以下に引用します。$k$は閾値です。

![formedia_4.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/418323/16a4056e-ed95-b4ad-7842-d2e16a14e429.png)

Fig. 7. 観測の新しさについて (Savinov et al., 2019)

ここからは具体的な手法の話になります。
まず、報酬 (augmented reward) を下記のように定めます。

```math
\hat{r}_t=r_t+b_t \tag{5}
```
$r_t$がtask reward、$b_t$がreward bonusです。これにより、報酬が密になります。

##Episodic Curiosity Module
観測$o$を入力とし、報酬ボーナス$b$を出力とするモジュールを構築します。ここで、2つのパラメトリックな構成要素である"**Embedding network**"と"**Comparator network**"が登場します。Embedding networkは観測の埋め込みを行い、Comparator networkは2つの埋め込みを比較して$k$ステップ以内での到達可能性の出力を行います。
また、「エピソード記憶」を保持するための"**Memory buffer**"、エピソード記憶と現在の観測の埋め込みを比較した際の結果を保持する"**Reachability buffer**"、Reachability buffer内のデータから報酬ボーナスを決定する"**Reward bonus estimation module**"を用意します。最終的なモジュール内の構成とボーナス計算の流れは下図の通りです。
論文中から引用した図と、こちらで数式等を書き加えた図を載せます。

![figure_formedia_5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/418323/6ad31b0d-e5ed-99f0-0a83-81085db03f7e.png)

Fig. 8. モジュールの構成 (Savinov et al., 2019)

![media_figure_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/418323/6ff42e0b-9ee3-9907-67bc-f7daf6c3cb55.png)

Fig. 9. モジュールの詳細

また流れをアニメーション化してみました。

![media_figure_3.5.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/418323/d3d0f97b-459a-ab35-5f62-3b983b3c0674.gif)
Fig. 10. モジュール内の流れ

##実験結果
本論文では、1本目の論文 (Pathak et al., 2017) と同様に_VizDoom_・3種類の報酬設定 ("dense"、"sparse"、"very-sparse") を用いながら、強化学習アルゴリズムPPO (Schulman et al., 2017) を用い、"PPO"、"PPO + ICM"、"Ours" (proposed method) を用いて実験を行っています。結果の図を論文中から以下に引用します。

![スライド3.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/418323/14c56be6-5ba4-e163-7d66-d80498c6fb15.png)

Fig. 11. _VizDoom_ (Kempka et al., 2016) での実験結果 (Savinov et al., 2019)

上図より、"Ours"が"PPO"・"PPO + ICM"に比べて良好な結果を示していることが分かります。
また、_DMLab_ (Beattie et al., 2016)でも実験が行われ、良好な結果が出ています。

#2本の論文を比較して

ここまで、強化学習における内発的報酬について提案した2本の論文を紹介してきました。1本目の論文では、環境変化を下記の3つに大別し、1.と2.のみをモデル化しているのが特徴的です。

1. エージェントの行動による環境変化
2. エージェントによるものではないが、エージェントに影響し得る環境変化
3. エージェントによるものではなく、エージェントに影響しない環境変化

これにより、エージェントにおける好奇心のターゲットが適切なものとなり、最適化が進行します。
一方、2本目の論文は、エージェントの好奇心を「到達にいくらかの努力を要する観測」に向かわせており、1本目の論文から更に発展していると言えます。これにより、簡単な試行への拘泥を回避しており、1本目の論文よりも良好な結果を出しています。しかし、1本目の論文の手法についても後に大規模実験が行われており (Burda et al., 2018) 、訓練の倍加やPPOの使用、またバッチサイズの拡大を行うことによりエージェントのパフォーマンスが向上することが示されています。これを踏まえると、1本目の論文の手法も更なる発展が期待出来ると言えるでしょう。

これらの論文での提案手法は、様々な強化学習アルゴリズムと組み合わせられるという点でも優れていると言えます。事実、2本目の論文のOpenReviewではその点が評価されています (https://openreview.net/forum?id=SkeK3s0qKQ, AnonReviewer2のレビューを参照) 。

なお、1本目の論文では内発的報酬の定式化について、先行研究では以下の2つのアプローチが多く用いられていると述べています。

**<アプローチ1>** エージェントに「新しい」状態への探索を促す
**<アプローチ2>** エージェントによる自身の行動結果の予測においてエラー／不確実性を減少させるような行動をとるよう、エージェントに促す

今回紹介した2本の論文は、共にアプローチ1に該当するものでした。一方、先程紹介した「2本目の論文のOpenReview」におけるAnonReviewer3のレビューでは、アプローチ2への言及がなされ、また提案手法が確率的環境 (stochastic environment) に適用できるのかという点が指摘されています。これについては、2本目の論文は確率的環境に焦点を当てておらず、一方で"all the states provide stochastic next state"の場合には提案手法が適用可能である、と著者が返答しています。

#参考文献
Charles Beattie, Joel Z. Leibo, Denis Teplyashin, Tom Ward, Marcus Wainwright, Heinrich Küttler, Andrew Lefrancq, Simon Green, Víctor Valdés, Amir Sadik, Julian Schrittwieser, Keith Anderson, Sarah York, Max Cant, Adam Cain, Adrian Bolton, Stephen Gaffney, Helen King, Demis Hassabis, Shane Legg, and Stig Petersen. DeepMind Lab. In _arXiv:1612.03801_, 2016.

Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven Exploration by Self-supervised Prediction. In _ICML_, 2017.

John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy
optimization algorithms. In _arXiv:1707.06347_, 2017.

Michał Kempka, Marek Wydmuch, Grzegorz Runc, Jakub Toczek, and Wojciech Jaśkowski. Vizdoom: A doom-based ai research platform for visual reinforcement learning. In _arXiv:1605.02097_, 2016.

Nikolay Savinov, Anton Raichuk, Raphaël Marinier, Damien Vincent, Marc Pollefeys, Timothy Lillicrap, and Sylvain Gelly. Episodic Curiosity through Reachability. In _ICLR_, 2019.

Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous Methods for Deep Reinforcement Learning. In _ICML_, 2016.

Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A. Efros. Large-Scale Study of Curiosity-Driven Learning. In _arXiv:1808.04355_, 2018.

Episodic Curiosity through Reachability | OpenReview,
https://openreview.net/forum?id=SkeK3s0qKQ, 2020年7月26日アクセス.