차근차근 Spinning Up 톺아보기 Key Paper : DQN

Model Free RL > Deep Q-learning > DQN

DQN은 2013 NIPS에 처음 발표되고, 2015 NATURE에 개선된 알고리즘으로 발표된 논문이다.

사실 DQN 발표 이후로 강화학습이 주목받기 시작했다고 말할 수 있다.

 

 

Spinning Up에 실린 논문을 기준으로 포스팅하겠다.

2013 NIPS 버전이다.

제목부터 살펴보면 심층 강화학습으로 Atari 게임을 플레이하는 것을 알 수 있다.

DeepMind에서 제안한 논문이다.

---

<초록>

강화학습을 사용한 고차원의 감각적 입력으로부터 직접 제어 정책들을 성공적으로 학습하기 위한 딥러닝 모델을 제안한다.

이 딥러닝 모델은 Q-learning의 변형으로 학습된 Convolutional neural network(CNN)이다.

입력이 이미지 raw pixels이고 output은 미래 보상을 추정하는 value function이다.

학습 알고리즘이나 뉴럴넷 구조를 바꾸지 않고 7개의 Atari 2600 게임에 적용해보았다.

게임 중 6개는 이전보다 모두 좋은 결과를 보였으며 그 중 3개는 사람 전문가를 능가하는 결과를 보였다.

---

<Introduction>

Vision이나 speech같은 고차원의 감각 입력으로부터 에이전트를 조정하기 위해 학습하는 것은 강화학습의 오랜 도전들 중 하나이다.

대부분 성공적인 강화학습 애플리케이션들은 손으로 적은 특징들에 의존한 도메인들이 선형 value function또는 policy와 결합하여 계산된 것들이다.

분명히, 이러한 시스템들은 feature를 얼마나 잘 표현하냐에 의존해서 성능이 나타나게 된다.

최근 딥러닝의 장점들은 raw sensory data로부터 높은 레벨의 features들을 추출해내는것이 가능하다는 것이다.

이러한 방법들은 컨볼루셔널 네트워크, 다층퍼셉트론, restricted Boltzmann machines, RNN 같은 다양한 뉴럴 네트워크 구조를 활용한다.

sensory data를 사용한 강화학습을 위해 도움이 될 수 있는지 아닌지 질문하는 것은 자연스럽다.

그러나 강화학습은 딥러닝의 관점으로부터 몇 가지 문제점을 가지고 있다.

첫 번째, 대부분 성공적인 deep learning 애플리케이션은 굉장히 많은 양의 라벨링된 학습 데이터를 필요로 한다.

반면에 강화학습은 자주 희소하고 노이즈가 있고 지연되는 scalar reward로부터 학습을 할 수 있다.

action과 결과 reward 사이의 지연은 수천 시간에 달할 수 있지만 지도 학습에서 발견되는 input과 target 간의 직접적인 연관과 비교할 때 특히 어렵다.

다른 문제점은 대부분 딥러닝 알고리즘들은 data sample들이 독립적임을 가정한다. 그러나 강화학습은 일반적으로 state들끼리 매우 상관된 일련의 시퀀스로 나타난다. 게다가 강화학습에서 데이터 분포는 새로운 행동을 학습하는 알고리즘에 의해 바뀌게된다. 고정된 분포를 가정하는 딥러닝에서는 데이터 분포가 바뀌는 것이 문제가 될 수 있다.

이 논문에서는 CNN이 복잡한 강화학습 환경에서 raw video data로부터 성공적으로 control policies를 학습하기위해 이러한 문제를 극복해내는 것을 입증한다.

네트워크는 weight를 업데이트하기 위해 Stochastic Gradient Descent(SGD)를 사용한 Q-learning 알고리즘으로 학습된다.

고정되지 않은 분포들과 데이터의 상관관계 문제를 덜기 위해 "experience replay"를 사용한다.

experience replay를 사용하여 무작위로 이전의 transition들을 샘플링하고 따라서 과거의 많은 행동들에 대한 학습 분포를 smooth하게 한다.

시스템을 Arcade Learning Environment가 구현된 Atari 2600 게임에 적용하였다. Atari 2600은 도전적인 RL testbed로, 에이전트에게 고차원 시각적 입력(210*160 RGB video at 60Hz)와 사람이 하기 어렵게 디자인된 다양하고 흥미로운 task들의 집합을 제공한다.

이 시스템의 목표는 가능한 많은 게임들을 플레이하도록 성공적으로 학습할 수 있는 single nural network agent를 만드는 것이다.

네트워크는 어떠한 게임의 구체적인 정보나 인위적으로 만든 시각적 features를 제공받지 않는다. 그리고 에뮬레이터의 내부 상태에 대한 특권이 없다. video input, reward, terminal signal, 가능한 action 집합으로만 학습한다.

즉, 게임 내부에 조작하거나 뭔가 특정 정보를 받는다거나 하지 않고 사람처럼 시각적으로 보이는 input과 게임이 끝났는지 여부, 할 수 있는 action 집합을 가지고 학습하는 것이다.

게다가 네트워크 구조와 모든 하이퍼파라미터는 어떤 게임에 적용하든 다 똑같이 유지해서 사용한다.

네트워크는 7개의 게임 중 6개에서 모든 이전의 RL 알고리즘들 보다 우수했다. 그 중 3개는 사람보다도 잘했다.

Firgure 1은 학습을 위해 사용한 게임들 중 5개의 샘플 스크린샷이다.

---

<Background>

agent는 environment와 상호작용한다. 여기서는 Atari emulator가 환경이 된다.

그리고 각 액션, 관찰, 보상의 시퀀스를 받는다.

각 time-step에서 agent는 액션 집합에서 action을 선택한다 액션은 에뮬레이터로 전달되고 내부 state와 게임 점수가 변경된다. 일반적인 환경은 확률적이다.

에뮬레이터의 내부 state는 agent로부터 관찰될 수 없다. 대신에 에뮬레이터로부터 image를 관찰한다.

image는 현재 화면에 나타난 raw pixel 값으로 이루어진 vector이다.

game score에서 변한 점수를 reward로 agent에 전달한다.

일반적으로 게임 점수는 이전의 전체적인 행동과 관찰의 순서에 의존할 것이다.

action에 대한 피드백은 수 천번의 time steps 이후에 받을 수 있다.

 

에이전트는 오직 현재 스크린 이미지만 관찰하기 때문에, task가 부분적으로 관찰되고 많은 에뮬레이터 상태들은 지각적으로 별칭이 지정된다. 오로지 현재 화면인 x_t로부터 현재 상황을 완전히 이해하는 것은 불가능하다. 그래서 actions과 observations의 시퀀스(s_t=x_1, a_1, x_2, ..., a_t-1, x_t)를 고려한다. 그리고 이러한 시퀀스들에 의존해서 게임 전략을 학습한다.

에뮬레이터에서의 모든 시퀀스들은 유한한 time-stpes에서 종료된다고 가정한다.

이런 형식은 각 시퀀스가 별개인 state인 크고 유한한 MDP를 만들어낸다.

결과적으로 time t에서 나타나는 state인 완전한 시퀀스 s_t를 사용함으로써 MDPs를 위한 표준 강화학습 방법을 적용할 수 있다.

 

에이전트의 목적은 액션을 선택해서 에뮬레이터와 상호작용해서 미래 보상을 최대화하는 것이다.

매 timestep마다 discount factor를 사용해서 미래 보상을 가감한다.

time t부터 terminal T까지 누적 보상 합(return)은 위 식으로 표현할 수 있다.

optimal action-value function Q*(s,a)는 어떠한 policy를 따라서 행동했을 때 받는 예상 return을 최대화하는 것으로 정의할 수 있다.

policy pi는 시퀀스를 action에 매핑한다.(또는 actions에 대한 분포로 매핑)

optimal action value function은 bellman equation으로 알려진 중요한 정의를 갖는다.

이것은 다음과 같은 직관을 따른다. 만약 next time-step s'의 시퀀스의 최적의 value Q*(s',a')가 모든 가능한 액션 a'에 대해 알려졌다면, 최적의 전략은 action a'를 선택해서 r+gamma*maxQ(s',a')예상 값을 최대화하는 것이다.

많은 강화학습 알고리즘 뒤의 기초 아이디어는 bellman equation을 iterative update 식으로 사용하여 action-value function을 추정하는 것이다.

value iteration 알고리즘은 optimal action-value function으로 수렴한다.

실제로 이 기본적인 접근법은 완전히 비실용적이다. 왜냐하면 action value function은 각 시퀀스에 대해 분리해서 추정될 수 있다. action-value function을 추정하기 위해 function approximator를 흔히 사용한다.

강화학습에서 일반적으로 함수근사는 선형을 사용한다. 그러나 때로 뉴럴넷과 같은 비선형 함수근사를 사용한다.

Q-network의 파라미터로 theta를 두고 함수 근사를 한다.

Q-network는 loss function L_i(theta_i)를 최소화한다.

y는 i-1(직전) 파라미터의 Q max값과 실제로 액션을 해서 받은 reward의 합의 expectation을 target으로 둔다.

Q network의 파라미터 theta를 학습시키기 위해 gradient 계산을 하면 다음 식과 같다.

만약 weight가 매 스텝이후 업데이트되고 expectations가 행동 분포와 에뮬레이터로부터 샘플링된 샘플들에 의해 대체된다면, 우리는 익숙한 Q-learning 알고리즘을 볼 수 있게된다.

 

이 알고리즘은 model-free RL이다. 이것은 강화학습 task를 직접 에뮬레이터로부터 샘플링한 샘플들을 사용하여 해결한다. 또한 이것은 off policy이다. greedy 전략을 학습하면서 state 공간을 적절하게 탐험하는 행동 분포를 따른다.

실제로 behaviour distribution은 자주 e-greedy 전략을 사용한다. 1-e로는 greedy 전략을 따르고 나머지 e의 확률로는 랜덤하게 액션을 선택하는 것이다.

---

<Deep Reinforcement Learning>

 

최근 컴퓨터 비전과 음성 인식 분야의 돌파구는 효율적으로 매우 큰 학습데이터셋을 학습하는 심층신경망에 의존했다.

성공적인 접근법들은 stochastic gradient descent를 기반으로 lightweight updates를 사용하여 직접적으로 raw inputs으로부터 학습되었다.

심층신경망에 충분한 데이터를 제공함으로써 handcrafted한 방법보다 훨씬 나은 표현을 학습하는 것이 가능하다.

이러한 성공들이 강화학습에서의 우리의 접근법에 동기부여가 됐다.

이 연구의 목표는 직접 RGB 이미지들을 연산하고 stochastic gradient updates를 사용함에 의해 학습된 데이터를 효율적으로 처리하는 심층신경망을 강화학습 알고리즘에 연결하는 것이다.

Tesauro의 TD-Gammon 구조는 이러한 접근법을 위한 시작점을 제공한다. 이 아키텍처는 알고리즘이 환경과 상호 작용 (또는 Backgammon의 경우 자체 재생)을 통해 얻은 on-policy의 경험 샘플에서 직접 value function을 추정하는 네트워크의 매개 변수를 업데이트합니다.

이러한 접근법이 20년전 최고의 사람 backgammon players보다 더 좋은 결과를 낼 수 있었기 때문에 20년이란 기간의 하드웨어 개선때문인지 현대 심층신경망구조 및 확장가능한 RL 알고리즘과 결합하여 진전을 이룰 수 있을지 궁금한 것이 자연스럽다.

TD-Gammon과 유사한 online 접근법들과 대조적으로, expreince replay라고 알려진 기술을 사용한다.

각 time step마다 에이전트의 경험을 저장한다.

replay memory에 많은 에피소드들이 모인다.

알고리즘의 내부 루프에서는 저장된 샘플 풀로부터 랜덤으로 샘플링된 샘플로 Q-learning update를 적용하거나 minibatch update를 한다.

expreience replay 수행한 후에 에이전트는 e-greedy 정책을 따라서 액션을 선택하고 수행한다.

임의의 길이의 histories를 사용하면 신경망의 input으로 이것을 사용하기 어려울 수 있다.

그래서 Q-function은 대신에 함수 φ에 의해 생성된 histories의 고정된 길이 표현에서 작동한다.

전체 알고리즘을 우리는 deep Q-learning이라고 부른다.

이러한 방법은 기존 online Q-learning에 비해 몇가지 장점들이 있다.

첫 번째, 경혐의 각 스텝은 많은 weight update들에서 잠재적으로 사용된다. 즉 이것은 좋은 data 효율성을 보인다.

두 번째, 연속된 샘플들로부터 직접 학습하는 것은 비효율적이다. 왜냐하면 샘플들간의 강한 상관관계때문이다. 랜덤한 샘플들은 이러한 상관관계를 깨기 때문에 update의 variacne를 줄인다.

세 번째, on-policy 학습에서 현재 파라미터들은 학습이 되고서 다음 샘플을 결정한다.

예를 들어, 최대화된 액션이 왼쪽으로 움직이는 것이라면, 학습 샘플들은 왼쪽 샘플들로 지배될 것이다. 이것은 원치않는 피드백 루프가 발생할 수 있는 방법을 쉽게 알 수 있고, 파라미터가 local minimum에 못 미치거나 치명적으로 확산될 수 있다.

experience replay를 사용함에 의한 행동 분포가 이전 상태들의 많은 행동분포들의 평균이 된다. 이것은 파라미터의 진동, 발산을 피하고 학습이 부드러워진다.

experience replay를 사용해서 학습할 때 off-policy로 학습할 필요가 있다.(왜냐하면 현재 파라미터들이 샘플들을 생성하기 위해 사용되는 파라미터와 다르기때문에)

 

실제로 알고리즘에서 오직 replay memory에서 마지막(최근) N개의 경험만 저장한다. 그리고 업데이트 수행할 때 메모리에서 균등하게 랜덤 추출한다.

메모리 버퍼가 중요한 transition을 구별하지 않고 유한한 메모리 사이즈 N때문에 최근 transition으로 덮어쓰기 때문에 이러한 방법은 일부 측면에서 제한적이다.

유사하게, unifrom sampling은 replay memory에 있는 모든 transition에 중요도가 전부 같음을 의미한다. 더 복잡한 샘플링 전략은 우선 순위가 지정된 스위핑과 같이 가장 많이 배울 수 있는 transitions를 강조할 수 있다.

---

<전처리와 모델 구조>

128 color를 사용하는 210*160 pixel images인 raw Atari frames에서 직접 동작하는 것은 계산적으로 부담이 될 수 있다. 그래서 기초 전처리 단계로 input 차원을 감소시킨다. 먼저 RGB를 gray-scale로 바꾼다. 그리고 110x84로 다운샘플링한다. 최종적으로 input은 플레이 영역을 캡처한 이미지를 84x84로 crop한 이미지로 얻게 된다. 마지막 크롭은 Imagenet classification with deep convolutional neural networks로부터 2D convolutions GPU 구현을 사용하기 때문에 필요하다.(정사각형 입력이 필요하기 때문에)

이 논문에서 실험을 위해, 알고리즘 1의 함수 φ은 history의 마지막 4개의 프레임으로 전처리하고 Q-function의 입력으로 생성하려고 이 프레임들을 쌓는다.

 

뉴럴 네트워크를 사용한 파라미터화된 Q의 가능한 몇가지 방법들이 있다.

Q는 history-action 쌍들을 Q-value의 scalar 추정값으로 매핑한다. 이전에 나왔던 방법들에 의해 history와 action은 inputs으로 사용되었다.

이 구조의 유형의 주요한 단점은 별도의 forward pass가 각 액션들의 q-value를 계산하기 위해 요구된다. 결과적으로 액션의 수에 따라 선형적으로 비용이 커진다. 우리는 대신에 각 가능한 액션들에 대해 별도의 output 단위가 있는 아키텍처를 사용하며 state 표현만 신경망에 대한 입력이 된다.

output들은 input state에서 각 action에 대해 예상된 Q-value이다. 이러한 구조의 유형의 주요 장점은 단지 하나의 입력으로 state가 주어지면 모든 가능한 액션에 대한 Q-value를 계산할 수 있다는 것이다.

7개의 Atari games에 사용된 정확한 구조에 대해서 설명해보면, 뉴럴넷의 input은 φ에 의해 생성된 84*84*4 image이다. 첫 번째 히든레이어는 16개의 8*8 필터(stride 4)를 적용한 convolution layer이다. activaion function으로는 ReLU를 사용한다. 두 번째 히든레이어는 4*4 32개 필터(stride 2) Conv layer, actionvation function은 ReLU이다. 마지막 히든 레이어는 fully-connected, 256개 rectifier units으로 구성된 레이어를 가진다. output layer는 fc linear layer로 각 action의 output(Q-value)을 나타낸다. 가능한 actions의 수는 4개에서 18개 사이다.

---

<실험>

7개의 유명한 Atari 게임에서 수행했다. Beam Rider, Breakout, Enduro, Pong, Q*bert, Seaquest, Space Invaders.

우리는 모든 게임에서 같은 네트워크 구조를 사용하였고 학습 알고리즘, 하이퍼파라미터 값 모두 유지하였다.

게임 별 정보를 통합하지 않아도 다양한 게임에서 작동한다.

학습하는 동안에만 게임의 보상 구조를 변경했다. 게임마다 점수 스케일이 달라서 모두 양수 보상은 1, 음수 보상은 -1로 고정했다. 0 reward는 바꾸지 않았다.

리워드를 클리핑하면 error 미분의 스케일이 제한되고 쉽게 여러 게임에서 동일한 learning rate를 사용할 수 있다.

동시에 다른 규모의 보상을 구별할 수 없어서 에이전트의 성과에 영향을 줄 수 있다.

optimization algorithm으로 RMSProp을 사용하였고 32크기의 minibatch를 사용하였다.

행동 policy는 e-greedy로 학습한다. 1부터 0.1까지 첫 백만 프레임까지는 epsilon이 선형적으로 줄어드는데 그 이후에는 0.1로 고정된다.(decaying e-greedy). 총 천만 프레임으로 학습했고 가장 최근의 백만 프레임의 replay memory가 사용된다.

Atari 게임에 대한 이전의 접근 방식에 따라 간단한 프레임을 건너뛰는 테크닉을 사용한다. 즉 에이전트는 모든 프레임 대신에 k개의 프레임을 보고 액션을 선택한다. 그리고 마지막 액션이 건너뛴 프레임 앞에서 반복된다. 에뮬레이터를 한단계 앞으로 실행하고서 에이전트가 액션을 선택하는 것보다 훨씬 적은 계산이 필요하기때문에 이 테크닉을 사용해서 실행시간을 늘리지 않고 k배 더 많은 게임을 할 수 있게 된다.

space invaders 제외한 나머지 게임에 k=4로 사용하였다. k=4를 사용하면 깜빡거리는 레이저 시간때문에 레이저가 보이지가 않는다. 레이저 시각화를 위해서 k=3을 사용한다. 이것이 하이퍼 파라미터의 유일한 차이이다.

---