[RND] Exploration by Random Network Distillation

• Link: https://arxiv.org/abs/1810.12894
• Blog: https://openai.com/blog/reinforcement-learning-with-prediction-based-rewards/
• Official Code: https://github.com/openai/random-network-distillation

1. Abstract

• 구현이 쉽고 최소한의 추가 계산만 요구되는 exploration bonus 기법 소개
• Bonus → Neural Network (NN)에 의해 예측된 observation의 feature와 임의로 초기화 된 후 고정된 neural network를 통해 얻은 observation feature의 차이
• intrinsic과 extrinsic reward를 유연하게 결합하는 방식도 소개
• Random Network Distillation (RND) 기법을 통해 Atari game에서 hard exploration 문제 해결
  • 특히 DRL 기법으로 풀기 어려웠던 Montezuma's Revenge에서 state-of-the-art (SOTA) 성능
  • Demonstration을 사용하지 않고 평균적인 사람의 성능보다 우수한 성능을 보인 첫번째 기법

2. Introduction

• Reinforcement Learning (RL)은 policy의 expected return을 최대화 하는 것이 목표
• 환경에 보상이 sparse하여 보상을 받기 어려운 경우 학습이 잘 안됨 → 환경을 탐험하는 방법이 중요!
• 본 논문에서는 쉽게 구현할 수 있는 exploration bonus 기법을 소개
  • 고차원의 관측에서도 잘 작동
  • Policy optimization 기법에 사용
  • Experience의 batch를 NN에 한번 feed forward 연산만 하면 되기 떄문에 계산량이 적음
  • 본 논문의 bonus는 학습에 많이 사용된 관측에 낮은 예측 에러를 도출하게 되고 낮은 experience bonus를 도출하여 새로운 관측을 탐색하도록 유도
• 이렇게 예측 오차를 최대화하는 에이전트의 경우 확률적인 transition이 발생하는 곳으로만 이동하게 될 수 있음 → 예를 들어 랜덤하게 noise가 발생하는 TV가 있다면 그 TV 앞으로만 가게 되는 것
• 이에 따라 absolute error가 아닌 예측의 상대적인 발전을 정량화 하고 이를 유도하는 관측을 사용해야함
• 본 논문에서는 원치않는 확률성 (undesirable stochasticity)에 대한 해법을 제안
  • Prediction problem을 exploration bonus로 정의하지만 이때 정답이 입력에 대한 deterministic function
  • 이 정답은 랜덤하게 초기화된 NN을 고정하고 현재 observation을 입력으로 하여 도출된 결과
• Atari 환경에서 성능 검증하며 sparse reward 환경인 hard exploration 문제들에서 성능 검증
  • Freeway, Gravitar, Montezuma's revenge, Pitfall!, Private eye, Solaris, Venture
  • 일반적인 강화학습 환경들은 이런 환경들에서 한번도 양의 보상의 받지 못하는 경우도 있음
  • 특히 Montezuma's revenge는 RL agent에게 가장 어려운 문제로 알려짐
• RND는 extrinsic reward를 무시한 경우에도 exploration bonus만으로 Montezuma's revenge에서 절반 이상의 방을 탐색
• Exploration bonus를 extrinsic reward와 결합하기 위해 Proximal Policy Optimization (PPO)의 변형을 소개 → two value head for two reward streams
• 서로 다른 보상에 서로 다른 discount rate을 사용하여 episodic과 non-episodic return을 결합
• 이런 추가적인 flexibility 덕분에 best agent는 Montezuma's revenge에서 24개의 방들 중 22개를 방문하며 첫번째 레벨을 통과하기도 함
• 또한 Venture나 Gravitar에서도 SOTA 성능을 보임

3. Method

3.1 Exploration Bonuses

• Exploration bonus는 환경의 보상 $e_t$ 가 sparse한 경우에도 에이전트가 탐험할 수 있도록 유도하는 기법
• 이에 따라 새로운 보상을 정의 → $r_t = e_t + i_t$ ($i_t$: exploration bonus at time t)
• 에이전트가 새로운 상태를 방문하도록 유도하기 위해 $i_t$는 자주 방문한 상태보다 새로운 상태일 때 더 커야함

3.2 Random Network Distillation

• 본 논문은 prediction problem이 랜덤하게 생성되는 다른 접근을 소개
• 두개의 NN으로 구성
  • Target network ($f$): 랜덤하게 초기화되며 고정됨 → prediction problem으로 설정
  • Predictor network ($\hat{f}$): 에이전트에 의해 수집된 데이터를 통해 학습
• 두 네트워크 모두 k 차원의 feature 도출
• predictor NN은 expected MSE $|| \hat{f}(x;\theta) - f(x)||^2$ 를 최소화하도록 gradient descent를 통해 parameter $\theta_{\hat{f}}$ 에 대해 학습
• 예측 에러는 기존에 학습에 많이 사용한 상태보다 새로운 상태에서 더 높은 값이 도출될 것
  
  
• MNIST를 이용한 토이 모델을 만들어서 실험 수행
  • 처음에는 class 0인 데이터만 가지고 학습 수행
  • 다른 숫자들을 통해 테스트 했을 때 처음에는 MSE가 크게 나오지만 다른 class들도 학습에 사용하면 점점 익숙해지기 때문에 MSE가 작아짐

 

• Figure 1은 Montezuma's revenge에서 한 에피소드 동안 새로운 state에서 높은 intrinsic reward를 받은 상태들을 보여줌

 

 

• 영상
  • https://youtu.be/40VZeFppDEM

 

3.2.1 Sources of Prediction Errors

• 일반적으로 prediction error는 다음의 요소들에 영향을 받음
  1. 학습 데이터의 양: predictor가 관측한 example 중 유사한 것이 적으면 prediction error가 큼 (Epistemic uncertainty)
  2. 확률성: target function이 확률적이면 (aleatoric uncertainty) prediction error가 큼, stochastic transition은 forward dynamics prediction에서 이런 에러의 원인이 됨
  3. Model misspecification: 필요한 정보가 없거나 model class가 target function의 complexity에 딱 맞게 제한되어 있을 떄 Prediction error가 높음
  4. Learning dynamics: 최적화 과정 중 target function을 잘 근사하는 predictor를 찾지 못하면 Prediction error가 높음
• Factor 1은 exploration bonus 로서 prediction error를 사용하는 것이 가능
• Prediction error는 이런 모든 요소들의 조합으로 발생할 수 모든 요소들이 다 좋은 것은 아님
• Factor 2는 noisy TV 문제를 일으킬 수 있음
• RND는 factor 2와 3을 피하기 위해 target network가 deterministic하게 선택

3.2.2 Relation to Uncertainty Quantification

• RND prediction error는 Osband et al. (2018)이 소개한 uncertainty quantification 기법과 관련있음
• Data distribution $D=\{x_i, y_i\}_i$를 가지는 regression problem을 생각해보자
• Bayesian setting에서 우리는 prior $p(\theta^* )$에 대한 mapping $f_{\theta^*}$의 파라미터를 고려하고 evidence에 대해 update 후 posterior를 계산
• $F$는 function $g_{\theta} = f_{\theta} + f_{\theta^}$에 대한 distribution, $\theta^$은 $p(\theta^*)$로부터 도출되고 $\theta$는 expected prediction error를 최소화하도록 도출
  • $\theta = \argmin_{\theta}E_{(x_i , y_i) \sim D} ||f_{\theta}(x_i) + f_{\theta^*} (x_i) - y_i||^2 + R(\theta)$
  • $R(\theta)$는 prior로부터 오는 regularization term (Osband et al, 2018의 Lemma 3 참고)
  • Osband et al은 ensemble $F$ 는 posterior의 approximation으로 주장
• 만약 우리가 regression target $y_i$를 0으로 하면 최적화 문제 $\argmin_{\theta}E_{(x_i , y_i) \sim D} ||f_{\theta}(x_i) + f_{\theta^*} (x_i)||^2$ 는 prior로부터 랜덤하게 도출된 function을 distilling하는 것과 동일
• 이런 관점에서 보았을 때 predictor와 target networks의 출력은 ensemble의 멤버에 해당함 (with parameter sharing amongst the ensemble)
• MSE는 이 ensemble의 예측 분포의 추정이 될 수 있음 (ensemble이 unbiased 되었다는 가정 필요)
• 즉 distillation error는 constant zero function을 예측하는 uncertainty의 quantification으로 생각할 수 있음

3.3 Combining Intrinsic and Extrinsic Returns

• Intrinsic reward만 사용하는 경우 non-episodic 문제로 설정하는 것이 더 좋은 exploration 수행
• 원문: In that setting the return is not truncated at "game over". We argue that this is a natural way to do exploration in simulated environments, since the agent's intrinsic return should be related to all the novel states that is could find in the future, regardless of whether they all occur in one episode or are spread over several.
• Burda et al., 2018 논문에도 episodic intrinsic reward를 사용하는 것은 에이전트가 task에 대한 정보를 잃을 수 있다고 언급
• 이것이 사람이 게임에서 탐험을 수행하는 것과 더 가까움
  • 만약 게임 오버의 위험을 감수하고 수행해야하는 동작이 있을 때 이를 성공하면 curiosity가 높아짐
  • 하지만 episodic RL의 경우 죽어버리면 return이 0이 되어버리므로 risk averse하게만 행동을 선택
• 하지만 extrinsic reward에 non-episodic reward를 쓰면 게임이 시작했을 떄 가까운 reward로만 exploit할 수 있음
• 이에 따라 intrinsic reward $i_t$의 non-episodic stream과 extrinsic reward $e_t$의 episodic stream의 가치를 결합하여 추정해야함
  • 이에 대한 방법으로 return이나 value head를 extrinsic과 intrinsic에 대해 나눠줌
    • $R=R_E + R_I$
    • $V=V_E + V_I$
• Reward stream을 더할때 서로 다른 discount factor 적용하는 방법도 사용할 수 있음
• 위의 이유 외에도 extrinsic reward function은 stationary하고 intrinsic reward function은 non-stationay하다는 측면에서도 exploration bonus를 위해 value function을 분리하는 것이 좋음

3.4 Reward and Observation Normalization

• Prediction error를 exploration bonus로 사용하는 경우 환경이나 시점에 따라 값이 크게 달라질 수 있음
• intrinsic return의 추정된 표준편차로 intrinsic reward를 나눠서 intrinsic reward를 normalize
• Random network를 target으로 사용하는 경우 observation normalization이 굉장히 중요함
  • parameter가 frozen 되어있으므로 다른 dataset의 scale을 조절할 수 없음
  • normalization을 수행하지 않으면 embedding의 분산이 극도로 낮아져서 입력에 대해 적은 정보만 알 수 있음
  • 이 문제 해결을 위해 normalization을 수행하고 -5 ~ 5로 clip 수행
  • 동일한 observation normalization을 predictor와 target network에 적용하지만 policy network에는 적용하지 않음

4. Experiments

4.1 Pure Exploration

• Extrinsic reward 없이 RND의 성능을 확인
• Pure exploration의 성능을 episodic과 non-episodic으로 비교

• Figure 3에서 2가지 measure로 성능 측정
  • Mean episodic return
  • training 동안에 에이전트가 찾은 방의 수
• 외부 보상이 없지만 새로운 방을 찾는 것으로 많은 내부 보상을 얻음 → extrinsic reward도 늘어나게 됨
• Object와 상호작용하는 경우 많은 return을 받고 해당 행동을 반복하는 경우 incentive가 감소하여 항상 return이 높게 유지되지는 않음
• 결과
  • Non-episodic agent가 좋은 성능을 보임
  • Non-episodic setting with $\gamma_I =0.999$가 $\gamma_I =0.99$보다 더 많은 방을 탐험

4.2 Combining Episodic and Non-Episodic Returns

• Intrinsic과 extrinsic reward를 결합 → two value head가 필요
• 두 value head가 episodic 일때의 성능도 함께 비교
• Figure 4에서는 episodic intrinsic reward와 non-episodic intrinsic reward를 episodic extrinsic reward와 결합한 결과를 비교
• 또한 two value head와 one value head를 episodic case에서 비교
• Discount factor $\gamma_I = \gamma_E = 0.99$
• Non-episodic intrinsic reward steam을 사용하는 경우 CNN과 RNN policies 모두에서 탐험하는 방의 수가 증가
• 예상과 다르게 episodic setting에서 two value head가 single head에 비해서 딱히 장점을 보이지 않음
• 하지만 서로 다른 특성을 가진 reward stream을 결합할 때는 two value head가 필요 → 앞으로의 실험에서는 two value head 사용 예정

4.3 Discount Factors

• 다수의 demonstration을 이용해서 Montezuma's revenge를 푼 논문들 (Salimans & Chen, 2018; Pohlen et al., 2018; Garmulewicz et al., 2018)은 높은 discount factor를 설정하여 best performance 달성
• 본 논문에서도 RND agent의 성능을 $\gamma_E \in \{0.99, 0.999\}$, $\gamma_I = 0.99$ 를 사용하여 결과 비교
• 또한 $\gamma_I = 0.999$의 결과도 살펴봄
• 결과
  • Figure 5를 보았을 때 $\gamma_E = 0.999, \gamma_I = 0.99$로 하는 것이 가장 좋은 성능을 보임
  • $\gamma_I = 0.999$로 하는 경우 성능이 좋지 못함

4.4 Scaling up Training

• 학습의 scale을 증가시켰을 때 성능 확인 ($\gamma_I = 0.99, \gamma_E = 0.999$)
• 많은 수의 환경을 사용하면 policy 학습에 있어 더 큰 batch를 사용하는 것이 가능함
• 반면 predictor network 학습에는 동일한 수의 batch size를 사용
• intrinsic reward가 시간이 지남에 따라 사라지므로 policy를 학습하고 transitionary reward를 exploit 하는 것이 중요 → novel state 쪽으로 행동하도록
• Figure 6을 통해 더 많은 병렬 환경을 통해 더 큰 batch를 사용하는 것이 더 높은 mean episodic return을 도출하는 것을 확인
• RNN policy 보다 CNN policy가 먼저 saturate 되는 것으로 보임
• RNN experiment with 32 parallel environment를 더 돌려보았을 때의 결과
  • 1.6 billion frames over 1.6 million parameter update → mean return: 7,570
  • 이 결과들 중 하나는 모든 24개의 방 방문, 첫번째 레벨 통과하며 17,500 return 달성
  • 1024 parallel env → mean return: 10,070

4.5 Recurrence

• Montezuma's Revenge는 partially observable 환경
  • ex) 열쇠가 어디서부터 왔는지, 얼마나 많은 키가 과거에 사용되었는지, 어떤 문이 열렸는지,...
• 이런 partial observability를 다루기 위해 에이전트는 과거의 state summarizing을 유지해야함 → ex. the state of a recurrent policy
• 이에 따라 recurrent policy를 사용한 에이전트가 더 좋은 성능을 보일 것으로 기대할 수 있음
• 하지만 기대와는 다르게 Figure 4에서 $\gamma_E = 0.99$일 때 recurrent policy가 non-recurrent policy 보다 좋지 못한 성능을 보임
• 하지만 Figure 6에서 RNN policy ($\gamma_E = 0.999$)가 CNN의 성능을 뛰어넘음
• 이후 확인할 Figure 7이나 9에서도 RNN policy가 CNN policy를 자주 능가하는 것을 확인할 수 있음

4.6 Comparison to Baselines

• RND를 2개의 baseline 과 성능 비교
  • PPO without exploration bonus
  • alternative exploration bonus based on forward dynamics error
• 6개의 hard exploration Atari 환경에서 검증
  • Gravitar, Montezuma's Revenge, Pitfall!, Private Eye, Solaris, Venture
• RND의 intrinsic reward는 non-episodic ($\gamma_R = 0.99, \gamma_E = 0.999$)
• Figure 7은 RNN policy의 결과, Table 1, Figure 9는 CNN policy

• Gravitar에서 RND가 PPO의 성능을 능가하지 못하지만 둘다 평균 사람의 성능은 뛰어넘음
• Montezuma's revenge와 Venture에서는 PPO의 성능을 능가, SOTA 성능과 사람의 성능도 뛰어넘음
• Pitfall! 에서는 두 알고리즘 모두 양의 보상을 얻는데 실패 → extrinsic reward가 매우 sparse
• Private Eye에서는 RND가 PPO의 성능을 능가
• Solaris에서는 RND와 PPO의 성능이 비슷함
• Forward dynamics error
  • Predictor network가 현재 관측과 행동을 통해 다음 관측을 예측 → 실제 다음 관측과의 차이를 exploration bonus로 사용
  • dual value heads, non-episodic intrinsic returns, normalization 등을 RND와 똑같이 고정
  • Figure 7에서 dynamics based exploration은 RND보다 Montezuma's revenge, PrivateEye, Solaris에서 더 나쁜 성능을 보임
  • Venture, Pitfall, Gravitar에서는 RND와 유사한 성능을 보임
  • 수렴했을 때 Montezuma's Revenge에서 두 방 사이의 경계에서 두 방을 왔다갔다 하는 경향을 보임 → prediction error가 크게 발생 (Noisy TV problem과 유사)

4.7 Qualitative Analysis

• RND 에이전트를 관측했을 때 지속적으로 위험한 object와 상호작용 하려는 경향을 보임
  • Montezuma's revenge에서 해골의 앞뒤로 뛰어다님, 레이저 문 사이로 지나다님, 사라지는 다리 위로 올라갔다 내려옴
  • Pitfall!에서도 유사한 모습을 보임
• 이런 위험한 상태는 달성하기가 어려움 → 안전한 상태보다 에이전트의 과거 경험에서 희소하게 등장 → intrinsic reward가 커짐

5. Discussion

• Random network distillation에 기반한 탐험 기법 제시
• 매우 sparse reward 환경인 몇몇의 아타리 게임에서 좋은 성능을 보임
• RND exploration이 지역적인 탐험을 다룰때 좋다는 것을 확인
  • short-term decision의 결과를 탐험
  • 특정 오브젝트와 상호작용하거나 이를 피하기
• 그러나 긴 time horizon을 가지는 global exploration은 본 기법을 통해 다루기 어려움
• High level exploration을 푸는 것이 future work의 방향

A. Appendix

A.1 Reinforcement Learning Algorithm

• Exploration bonus는 어떤 RL 알고리즘에도 보상을 $r_t = i_t + e_t$의 형태로 변경하여 사용 가능
• 본 논문에서는 baseline RL 알고리즘으로 PPO 사용

A.2 RND Pseudo-code

• 공식 코드: https://github.com/openai/random-network-distillation

A.3 Preprocessing Details

• 실험을 위한 환경의 preprocessing 방법: Table 2

• Policy와 Value network를 위한 추가적인 preprocessing Detail: Table 3

• Predictor와 Target network를 위한 추가적인 preprocessing detail: Table 4

A.4 PPO and RND Hyperparameters

• PPO 알고리즘과 RND를 위해 추가된 hyperparameters

• 32 parallel environment를 통해 RND 실행
• 병렬적인 환경의 수가 늘어나면 policy가 더 빠르게 transient intrinsic reward에 도달하도록 할 수 있음
• This effect could have been mitigated however if the predictor network also learned more quickly
• 이런 상황을 피하기 위해서 환경을 32 → 128로 하는 경우 predictor network의 batch size를 동일하게 유지 → batch의 element를 keep probability 0.25로 랜덤하게 dropping
• 환경이 256, 1024인 경우도 keep probability를 0.125와 0.03125로 사용하여 랜덤 dropping

A.5 Architectures

• 본 논문에서 두개의 policy architecture 사용 → RNN, CNN
• 두 기법 모두 DQN과 동일한 구조의 CNN을 encoder로 사용
• RNN architecture는 여기에 GRU를 추가로 사용하여 더 긴 context를 capture
• Target과 predictor network도 DQN과 동일한 구조의 convolutional encoder 사용

A.6 Additional Experimental Results

• Figure 8의 결과는 동일한 RND를 사용하지만 하나는 exploration bonus를 autoencoder의 reconstruction error로 사용
• Autoencoding task도 RND과 유사함 → 실험 결과 autoencoding task로도 성공적으로 exploration 수행
• Figure 9는 RND, PPO, dynamics prediction-based baseline을 CNN policy에 적용한 결과를 보여줌

A.7 Additional Experiment Details

• Table 6은 각 실험에 사용한 seed를 보여줌