sfex tistory blog

https://velog.io/@nawnoes/10.-RNDExploration-by-Random-Network-Distillation

​

RND (Exploration by Random Network Distillation)

​

OpenAI에서 발표한 Exploration에 대한 논문. 18년도까지 여러 강화학습 알고리즘이 있었지만 Reward가 Sparse 한 환경인 몬테주마의 복수에서 인간의 성능을 최초로 넘은 방법이다.

​

Abstract

​

이 논문에서 강화학습을 휘한 Exploration bonus를 소개한다.

이 Exploration bonus는 적용하기 쉽고, 동작하는데 최소의 오버헤드가 든다.

이때 bonus는 고정되고 랜덤하게 초기화된 네트워크로부터 얻은 관측(observations)의 특징(feature)을 예측하는 신경망의 에러를 말한다.

intrinsic and extrinsic reward를 적절하게 결합하여 사용한 flexibility에 대한 method를 소개한다

이 알고리즘을 통해 몬테주마의 복수에서 SOTA를 달성하였고 인간의 성능을 뛰어넘게 된 첫 번째 방법으로 의의를 가진다.

​

1. Introduction

​

기존의 제한 사항들

강화학습은 Policy의 반환값(return)의 기댓값을 극대화하도록 동작한다. 보상(reward)가 밀집된(dense) 한 경우, 대체적으로 잘 학습한다. 하지만 보상이 뜨문뜨문한(sparse) 경우, 학습시키기 어렵다.

실제 세계에서도 모든 보상들이 밀집된 경우는 드물다. 따라서 보상이 드문 경우에도 잘 학습하기 위한 방법이 필요하다.

18년 당시 RL에서는 어려운 문제들을 풀기 위해 환경을 병렬적으로 크게 만들고 경험들을 샘플링하여 얻었지만 이러한 방법은 당시에 소개된 exploration 방법들에 대해서는 적용하는데 어려움이 있었다.

​

제시하는 것

​

간단하고 고차원의 관측에서도 잘 동작하는 Exploration bonus를 소개한다.

이 알고리즘은 policy optimization과 함께 적용할 수도 있고, 계산 효율적이기도 하다.

​

아이디어

유의미한 이벤트가 발생할 때 내부 보상이 높은 것을 볼 수 있다. (2, 8, 10, 21) 은 life를 잃을 때, (3, 5, 6, 11, 12, 13, 14, 15)는 적을 아슬아슬하게 피할 때, (7, 9, 18) 은 어려운 장애물을 피할 때, 그리고 (19, 20, 21) 은 아이템을 습득할 때

​

이 논문에서 제시된 Exploration bonus는 신경망에서 학습된 것들과 유사한 예들에 대해서 prediction error가 현저하게 낮은 것에서 아이디어를 얻었다.

새로운 경험들의 참신함을 측정하기 위해, 에이전트의 과거 경험들에 대해 학습한 네트워크의 prediction error를 사용하였다.

​

prediction error를 극대화하는 것의 문제 이전에 많은 저자들이 지적했듯이 prediction error를 최대화하는 에이전트의 경우는 prediction problem의 답이 입력의 확률적 함수인 transition 들에 대해 끌리게 된다.

​

예를 들어 Noise TV 와 같은 예가 있다. 현재 obsevation에서 다음 observation을 예측하는 prediction problem이 있고, 이때 에이전트가 prediction error를 극대화하도록 행동한다면, 확률적 전환(stochastic transitions)을 찾도록 하는 경향이 있다.

그 예로 무작위로 변하는 아래와 같은 화면인 Noise TV와 무작위로 동전을 던지는 이벤트와 같은 것들이 있다.

​

​

문제를 극복하기 위한 대안

논문의 저자들은 적절하지 않은 stochasticity에 대한 대안을 제시한다. 답이 그것의 입력에 deterministic function인 prediction problem을 exploration bonus으로 정의하면서 대안으로 제안한다.

대안으로는, 현재 Observation에 대해서 output을 fixed randomly initialized network를 사용해서 예측한다는 것이다.

​

강화학습에서 어려운 게임들 🤦‍♂️

Bellemare의 2016년 논문에서 보상이 드물고 탐색이 어려운 게임들을 확인했다. 그 게임들로는 Freeway, Gravitar, Montezuma's Revenge, Pitfall, Private Eye, Solaris, Venture 들이 있고, 어떤 경우에서는 단 하나의 긍정보상도 찾지 못했다.

​

그중에서도 어려운 몬테주마의 복수

​

몬테주마의 복수는 강화학습에서 어려운 게임으로 여겨진다. 게임에서 치명적인 장애물을 피하기 위해 다양한 게임 스킬들에 대한 조합들이 필요하고, 최적의 플레이를 하면서도 보상이 수백 스텝 이상 떨어져 있기 때문에, 보상을 찾기에 어려운 과제로 여겨진다.

몇 논문들에서 꽤 좋은 성과를 거두었지만, expert demonstrations와 emulator state에 대한 접근 없이는 가장 좋은 성과가 전체 방의 절반만 찾아내었다.

​

논문에서 발견한 것 🔍

​

extrinsic reward 없는 경우

extrinsic reward를 무시하여도 agent가 RND exploration bonus를 극대화하도록 한다면 일관되게 몬테주마의 복수 게임에서 절반 이상의 방을 찾았다.

​

extrinsic reward와 exploration bonus 결합

exploration bonus와 extrinsic reward를 결합하기 위해서 수정된 PPO(Poximal Policy Optimization)을 제안한다.

수정된 PPO는 2개의 보상을 위해 2개의 value head를 사용한다.

서로 다른 보상(reward)에 대해 서로 다른 discount rate를 사용하고, episodic과 non-episodic 반환값(return)을 결합한다.

​

성과

first level에서 종종 몬테주마 게임에서 24개의 방 중에서 22개를 찾았고, 이따금씩 클리어하기도 했다. 그리고 같은 방법으로 Venture와 Gravitar에서 SOTA를 달성하였다.

​

​

​

2. Method

​

2.1 Exploration Bonuses

​

1) Count-Based

​

2.2 Random Network Distillation

​

2.2.1 Source of Prediction Errors

일반적으로 prediction error 들은 아래 요소들로부터 나온다.

1. Amount of training data

predictor가 전에 학습한 example 들과 다를수록 prediction error가 높다

2. Stochasticity

target function이 확률적이기 때문에 prediction error가 크다. stochastic transition들은 forward dynamic prediction과 같은 에러들의 원인이다.

3. Model misspecification

필요한 정보가 부족하거나 모델이 target funtion의 복잡도에 맞추기 위해 제한적인 경우

4. Learning dynamics

predictor가 target funtion을 근사하는 과정에서 최적화를 실패했을 때,

2번째 요소는 noisy TV 문제를 야기하고 3번째 요소도 적절하지 않기 때문에 RND에서는 요소 2,3을 제거한다. 3 since the target network can be chosen to be deterministic and inside

the model-class of the predictor network.

​

2.2.2 Relation to Uncertaionty Quantification

RND의 prediction errror는 불확실한 것을 수량화하는 것과 관련이 있다.

​

2.3 Combining Intrrinsic and Extrinsic Return

​

2.4 Reward and Observation Normalization

​

reward

prediction error를 exploration bonus로 사용하는 것이 보상의 크기가 환경에 따라, 시간에 따라 크게 다르기 때문에 모든 환경에서 동작하는 하이퍼파라미터를 찾는 것은 어려운 부분이 있다.

일정한 크기의 reward를 유지하기 위해서 intrinsic reward를 intrinsic reward의 표준편차들에 대한 추정치로 나누어 주어 normalization 과정을 거친다.

​

observation

랜덤 신경망을 사용할 때는 파라미터들이 고정되고 다른 데이터 셋들에 대해서도 조정되면 안 되기 때문에 observation normalization이 중요하다. normalization이 부족하면 임베딩의 분산이 극단적으로 낮아지고 입력에 대한 정보가 조금만 전달되는 결과가 발생할 수 있다.

이러한 문제를 해결하기 위해 continuous control 문제에서 사용하는 observation normalization scheme을 사용하고, 각 dimension에 running mean을 빼고 running standard deviation을 나누어 값을 normalization.

그 후 값이 -5와 5사이에 오도록 잘라준다.

predictor와 target network는 동일한 obsevation nomalization, policy network에 대해서는 사용하지 않는다.

​

References

https://arxiv.org/pdf/1810.12894.pdf

https://kr.endtoend.ai/slowpapers/rnd

https://bluediary8.tistory.com/37

https://seolhokim.github.io/deeplearning/2019/10/11/Exploration-by-random-network-distillation-review/

https://openai.com/blog/reinforcement-learning-with-prediction-based-rewards/

https://bluediary8.tistory.com/37

​

Random Network Distillation 방법은 다음과 같습니다.

​

1. State의 feature를 뽑기 위한 Network를 랜덤으로 초기화 시키고 고정시킵니다. (Target Network, 이 네트워크는 학습하지 않습니다)

​

2. Target Network와 똑같은 구조를 가지는 네트워크를 초기화 시키고 (Predictor Network), Target network에서 나온 state의 feature와 이 predictor network에서 나온 feature의 차이가 최소화 되도록 학습시킵니다.

​

즉, predictor network를 Target Network 화 시키는 거죠. 그리고 그때 state의 차이를 Intrinsic reward로 정의합니다. 결국 다음 state의 feature space가 predictor network가 잘 예측하지 못한 state라면 더 많은 reward를 주게 되는 것이죠.

​

예측한 다음 state와 실제 다음 state의 차이를 intrinsic reward로 정의하는 것은 일반적인 curiosity 모델의 컨셉과 같습니다.

그러나 기존의 curiosity 모델은 현재 state와 action을 통해 다음 state를 "예측해야만" 했다면, RND는 실제 다음 state를 가지고 "feature만을 추출"합니다. 즉, 예측을 잘 해야 할 필요가 없는 것이죠.

​

그러므로 RND의 predictor model을 stochastic 한 게 아니라 deterministic 하게 되는 것입니다.

랜덤으로 초기화시키고 고정시킨 target network 또한, feature를 예측하는 것이 아니라, 추출의 목적이 있기 때문에 굳이 학습 시킬 필요가 없습니다.

어차피 비슷한 state에 대해서는 비슷한 output feature를 내뱉게 됩니다.

Target network의 output을 predictor network로 학습을 시키면 결국 predictor network는 target network와 비슷한 모델이 되어갑니다.

​

하지만 episode 과정 중에 계속 보았던 state에 대해 학습이 되기 때문에, 이전에 보았던 state에 대해서 overfitting 되게 되고, 보지 않았던 새로운 state를 보게 된다면, target network의 output 과는 조금 다른 output을 내게 됩니다.

즉, 새로운 state를 찾아가면서 하는 행동에 대해서는 reward를 많이 줄 수 있게 되는 것이죠.

이때, predictor network와 target network가 완전히 동일하게 돼서 무조건 같은 output을 내지 않을까 하는 의문이 들 수도 있습니다만, MNIST 데이터를 학습시키는 CNN 모델만 생각해도 완전히 overfitting 되는 열 개의 모델을 만들어도 각기 NN의 weight는 다르다는 것을 생각해 보면 직관적으로 절대 같아질 수 없다는 것을 이해할 수 있습니다.

https://medium.com/data-from-the-trenches/curiosity-driven-learning-through-random-network-distillation-488ffd8e5938

Predictor: A series of 3 convolutional layers and 3 fully connected layers that predict the feature representation of s(t+1).

Target: A series of 3 convolutional layers and 1 fully connected layer that outputs a feature representation of s(t+1).

Combining Intrinsic and Extrinsic Returns

In ICM, we used only IR — treating the problem as non-episodic resulted in better exploration because it is closer to how humans explore games. Our agent will be less risk averse since it wants to do things that will drive it into secret elements.

Two Value Heads

Our new PPO model needs to have two value function heads: because extrinsic rewards (ER) are stationary whereas intrinsic reward (IR) are non-stationary, it’s not obvious to estimate the combined value of the non-episodic stream of IR and episodic stream of ER.

The solution is to observe that the return is linear i.e R = IR + ER. Hence, we can fit two value heads VE and VI and combine them to give the value function V = VE + VI. Furthermore, the paper explains that it’s better to have two different discount factors for each type of reward.

DQN

1. 더 깊은 네트워크

2. experience replay

데이터를 버퍼에 모았다가 랜덤 샘플링해서 학습

3. 두 개의 네트워크(train main)로 한쪽을 고정하고 학습 후 고정된 쪽 update

https://youtu.be/S1Y9eys2bdg

https://youtu.be/Fbf9YUyDFww

https://youtu.be/ByB49iDMiZE

https://github.com/hunkim/ReinforcementZeroToAll

hunkim/ReinforcementZeroToAll

Contribute to hunkim/ReinforcementZeroToAll development by creating an account on GitHub.

github.com

몬테카를로 방법 vs 시간차학습(Temporal Difference Learning)

몬테카를로 방법은 종료 상태 sT에 도달해야 가치함수의 갱신이 일어나지만,

시간차 학습(temporal difference learning)은 다음 상태로 진입할 때 곧바로 갱신이 가능합니다.

​

시간차학습 종류

1.Sarsa(onpolicy)

- 출력 : 최적 상태-행동 가치함수

2.Q-Learning(offpolicy)

- 출력 : 최적 정책, 최적 상태-행동 가치함수

3.DQN(CNN + Q-Learning)

https://wordbe.tistory.com/entry/RL-%EA%B0%95%ED%99%94%ED%95%99%EC%8A%B5-part3-Temporal-Difference-Learning-RL-application

​

[RL] 강화학습 part3 - Temporal Difference Learning, RL application

​

5. 시간차 학습(Temporal difference learning)

가장 혁신적인 알고리즘입니다.

동적 프로그래밍과 몬테카를로 방법의 장점을 겸비하였습니다.

​

1) 정책 평가

에피소드 e = [s0,r0]a0[s1,r1]a1⋯[sT,rT] 에서 샘플 zt를 처리한다면

몬테카를로 방법은 Z(st)에 이 샘플을 추가한 다음 아래 식으로 가치함수를 갱신합니다.

​

​

샘플 zt가 k번째로 추가되었다면, 추가된 순서를 고려하여 다음 식을 세울 수 있습니다.

​

​

v(old)π(st)vπ(old)(st)는 직전까지의 가치함숫값, 즉 먼저 추가된 k-1개의 샘플 평균이고,

r(zt)는 k번째 추가된 샘플의 누적 보상액 입니다.

위 식은 아래와 같은 형식으로 바꿀 수 있습니다. 아래 식은 덧셈 두번과, 곱셈 한번만으로 평균을 갱신하므로 효율적입니다.

​

​

몬테카를로 방법은 종료 상태 sT에 도달해야 가치함수의 갱신이 일어나지만,

시간차 학습(temporal difference learning)은 다음 상태로 진입할 때 곧바로 갱신이 가능합니다.

이것이 시간차 학습의 핵심 아이디어입니다.

특별히 시간차 학습에서는 상태 가치함수를 구할 때 위와 같이 새로운 보상을 구하여 식을 재정의 합니다.

γ는 할인율입니다.

​

상태-행동 가치함수를 추정하려면 아래의 식을 사용합니다.

정책평가

1) 모든 상태에 대해 가치함수vπ(s)를 0으로 초기화한다.

2) 에피소드 e를 생성한다.

3) 위 상태 가치함수 식을 이용하여 각 상태별로 (t=0부터 t= T까지) 가치함수를 갱신한다.

4) 2~3을 반복하여, 멈춤조건에서 멈춘다.

​

다른 상태가치함수의 값을 이용해서 현재의 상태가치함수를 갱신한다는 점에서 부트스트랩과 유사한 점이 있고(즉, 동적프로그래밍와 유사하다.),

에피소드 e를 생성하여 학습한다는 측면에서는 몬테카를로 방법과 유사합니다. 따라서 시간차 학습은 둘의 장점을 취하는 알고리즘으로 평가할 수 있습니다.

​

2) Sarsa

최적 정책을 찾는 알고리즘

시간차를 이용하여 최적 정책을 탐색하는 알고리즘으로 Sarsa, Q-learning 두가지가 있습니다.

​

Sarsa는 상태-행동 버전 식을 사용합니다.

알고리즘은 반복할 때마다 st,at,rt+1,st+1,at+1 라는 정보를 처리하므로 앞글자를 따서 Sarsa라고 합니다.

line 7에서 볼 수 있듯이 Sarsa는 다음 행동을 정책에 따라 결정합니다.

line 8에서는 결정된 행동에 따라 가치함수를 갱신합니다.(즉, 정책을 갱신합니다.)

이러한 방식을 on-policy라고 합니다.

​

3) Q-Learning

Watkins, 1992

Q-learning은 가치함수 갱신을 정책이 아닌 max 연산자로 결정합니다.

Q-learning은 off-policy를 사용한다고 말합니다.

​

Sarsa와 다른 점은 qπ(st+1,at+1)이 maxqqπ(st+1,a)로 바뀐 것입니다.

TD Learning 중 Q-learning을 사용하여 최적 정책을 구하는 방식은 강화학습에서 가장 혁신적이라고 평가하고 있습니다.

6. 근사 방법

위에서 언급한 알고리즘의 출력은 π^ 또는 최적 가치함수 v^ 또는 q^입니다.

π^을 구하기 위해서는 모든 상태와 모든 행동 확률을 표현하기 위해 |S|x|A| 크기의 배열이 필요합니다.

v^는 |S|,

q^는 |S|x|A|

크기의 배열이 필요합니다.

이 배열을 한 번 구하면, 배열을 참조하여 값을 읽으면 되므로, 배열을 참조표(lookup table)라고 합니다.

그런데 |S|,|A|가 크면 메모리 문제가 발생합니다. 모든 배열 요소의 확률을 구하기도 불가능해집니다.

강화학습은 이러한 종류의 문제를 풀기 위해 lookup table을 버리고, 근사 방법을 이용합니다.

선형방정식을 통해 근사하는 방법이 있습니다.

​

가치함수 v는 k개의 매개변수 θ로 표현됩니다.

보통 k<<|S|입니다.

πi(s)는 기저함수로, 서로다른 기저함수가 매개변수만큼 있습니다.

기저함수는 사람이 설계하여 훈련집합으로 최적의 매개변수를 찾는 일은 학습 알고리즘이 담당합니다.

하지만 현재 강화학습은 위 식보다 신경망을 주로 사용합니다.

입력으로는 상태(state), 출력은 보상(reward)입니다.

훈련집합은 에피소드(episode)를 수집하여 구성하고,

학습시 역전파 알고리즘(backpropagation)을 이용합니다. (Sutton, 2017)

​

7. Application Example

TD-gammon은 MLP를, DQN은 딥러닝 기술을 사용하여 가치함수를 근사합니다.

​

1) TD-gammon

Backgammon 게임입니다.

검은 말은 낮은 번호로, 빨간 말은 높은 번호로 이동합니다.

15개의 검은 말이 모두 16번으로 이동한 후 빠져나오면 검은 말이 이기고, 빨간 말이 1924로 이동한 후 먼저 빠져나와면 빨간 말이 이깁니다.

주사위를 굴려 나온 수만큼 한 개의 말을 이동시킬 수 있습니다. 주사위는 2번 던져 서로 다른 말에 적용시킵니다. 하지만 24번의 검은말 하나가 주사위 5가 나와 빨간말로 꽉 찬 19번으로 이동할 수 없습니다. 막는 것이 일종의 전략이 될 수 있습니다.

또한 빨간말이 하나뿐이라면 검은 말이 빨간 말을 잡을 수 있습니다.

잡은 말은 바깥에 두었다가 처음 위치에서 다시 시작해야 합니다.

서로 다른 상태가 10^20개 이상 있으므로 근사 가치함수를 사용합니다.

​

은닉층이 하나인 MLP를 사용하였고,

검은 말, 빨간 말이 놓인 위치를 표현하기 위해 24개 위치 각각에 노드를 4개씩 배정하였습니다.

2 * 24 * 4 = 192개의 노드가 사용됩니다.

또한 시간차 알고리즘을 사용해서 TD-gammon이라 불립니다.(Tesauro, 1995)

​

TD-gammon은 사람의 전략을 가르쳐 주지 않은 채 프로그램 2개가 겨루는 과정에서 학습하는 self-play 방식입니다.

승패의 여부에 따라 상태에 +1, -1 보상을 부여하고 보상이 TDL 알고리즘을 통해 이전 상태로 파급됩니다.

TD-gammon은 지도학습을 전혀 이용하지 않고 자가 플레이로 세계 챔피언 수준에 도달하였습니다.

​

강화학습과 보드게임

틱택토(tic-tac-toe), checkers, 체스, 장기, 바둑입니다.

보드게임을 가장 잘하기 위한 강화학습 연구가 진행되었고 가장 어려운 바둑에서 세계 챔피언 수준의 이세돌을 4:1로 이기는 성과를 기록합니다.

틱택토는 상태의 수가 3^9=19,6833^9=19,683 정도로 근사 가치함수를 사용하지 않더라도 쉽게 최적 정책을 알아낼 수 있습니다.

틱택토는 새로운 프로그램을 테스트하는 용도로 자주 쓰입니다.

checkers는 열약한 하드웨어에서도 체커 게임을 해결하는 시도를 하였습니다.(Samuel, 1959)

체스는 Deepblue라는 프로그램이 세계 챔피언을 이겼습니다.(Campbell, 2002)

당시 VLSI칩은 딥블루라는 슈퍼컴퓨터로 발전하였고, 당시에는 기계 학습 알고리즘보다 하드웨어 속도를 향상시켜 높은 수준을 달성하였습니다. 장기도 이와 마찬가지입니다.

바둑은 훨씬 탐색 공간이 커서 고성능 하드웨어에도 한계가 있었습니다. alphago는 몬테카를로 트리탐색, 프로기사들의 기보를 활용한 지도학습, self-play를 활용한 강화학습, CNN 적용, 고성능 하드웨어와 결합하여 세계 챔피언을 이길 수 있었습니다.(Silver, 2016)

​

2) DQN: Atari video game

므니 등은 Atari 2600 게임 49종에서 자동으로 플레이하는 프로그램을 개발하였습니다. (Mnih et al., 2015)

다양한 게임 해서 동일한 입력, 신경망 구조, 하이퍼 파라미터를 사용하여 전문 플레이어 수준을 달성하였습니다. 29종에서 좋은 성능을 보였습니다.

CNN과 Q-Learning을 결합한 DQN으로 상태를 입력하고, 게임 종류마다 필요한 만큼 출력 노드를 정합니다.