[논문리뷰]Playing Atari with Deep Reinforcement Learning

Abstract 

• 이 논문은 강화 학습을 이용해서 고차원 sensory를 입력으로 받아 성공적으로 control policy를 학습하는 최초의 딥러닝 모델을 소개한다.
• 모델은 Q-learning으로 학습한 CNN이고 input은 raw pixel이고 output은 미래의 reward를 추정하는 value function이다.
• 저자는 해당 논문의 방법을 7개의 Atari 2600게임을 Arcade Learning environment에서 적용했다.
• 결과적으로 6개의 게임에서 이전의 모든 접근법의 결과를 상회하는 성능을 보여주었고 3개의 게임에서는 게임 전문가의 결과 보다 더 나은 결과를 보였다.

1. Introduction

vision과 speech와 같은 고차원의 sensory input으로부터 agent를 통제하는 것을 직접적으로 학습하는 것은 강화 학습 분야에서 오랜 연구 주제이다. 이러한 도메인에 서 활용되는 대부분의 성공적인 강화 학습은 linear value function과 policy representation이 결합된 hand-crafted features 들에 의존해왔다. 그런 체계의 성능은 feature representation에 크게 영향을 받는다.

 

딥러닝의 발전에 따라 raw sensory data로부터 vision과 speech recognition의 한계점을 돌파할 수 있는 높은 수준의 feature를 추출할 수 있게 되었다. 이러한 방법들은 convolution network, 다층 퍼셉트론, restricted Boltzman machine과 RNN을 포함한 신경망 모델들을 사용하고, 지도학습과 비지도 학습 둘 다 활용한다. 하지만 딥러닝의 관점에서 강화 학습은 여러 가지 과제가 남아있다. 지금까지의 딥러닝의 활용은 많은 양의 직접 라벨링을 한 학습 데이터를 필요로 했다. 하지만 강화 학습 알고리즘은 희소하거나, 잡음이 있거나, 지연된 scalar reward signal로부터 학습할 수 있어야 한다. 강화 학습에서 action과 결과로 얻은 보상 간의 delay는 지도학습에서의 input과 target의 관계와 비교했을 때 특히 더 심각해 보인다 문제가 있다. 또한 대부분의 딥러닝 알고리즘은 데이터 샘플들이 독립적이라고 가정하지만, 강화 학습의 데이터는 전형적으로 높은 상관관계를 띄는 상태의 sequence를 받아들인다. 더 나아가 강화 학습의 데이터 분포는 알고리즘이 새로운 행동을 배울 때마다 바뀌는데 이는 고정된 데이터 분포를 가정하는 딥러닝 알고리즘에 대해선 문제가 될 수도 있다.

 

이 논문은 CNN을 이용해 복잡한 강화 학습 환경에서 raw video로부터 control policy를 학습하여 앞서 언급한 문제들을 극복할 수 있다고 말한다. 이 논문의 모델을 SGD를 이용하여 가중치를 update 하고 variant Q-learning 알고리즘을 이용해 학습했다. 앞서 언급된 독립적이지 않은 데이터와 계속 변경되는 분포를 해결하기 위해 저자는 이전의 전환을 무작위로 sampling 하는 experience replay mechanism을 이용한다. 그래서 이전의 여러 행동 동안 학습 분포를 평활한다. Atari 2600게임은 고차원 visual input과 인간 player들에게 어렵게 고안된 다양하고 흥미로운 task를 제공하는 RL의 어려운 테스트 베드이다.

 

이 논문의 목표는 단일 신경망 agent 최대한 많은 게임을 하도록 성공적으로 학습하는 것이다. 신경망은 게임에 대한 세부정보나, 직접 만든 시각적인 feature 그리고 emulator 내의 어떤 정보도 제공되지 않다. 신경망은 video 입력, 보상, 최종 신호, 가능한 action set으로만 학습한다. 학습을 위한 모델 아키텍처와 하이퍼 파라미터는 게임이 진행되는 동안 일정하게 유지했다.

 

 2. Background

agent가 환경($\varepsilon$, 이 경우, Atari emulator)과 상호작용하는 상황을 생각해 보자. 매 tme-step마다 action인 $a_t$을 선택하고 이 action은 emulator로 보내지고 internal state와 게임 점수를 수정한다. emulator의 내부는 agent는 참고하지 않는다 대신 대신 현재 스크린을 나타내는 raw pixel 값의 벡터인 이미지 $x_t$만 참고한다. 거기에 게임 스코어의 변경된 값인 $r_t$를 받아온다. 일반적으로 게임 스코어는 이전 sequence of action과 observation에 영향을 받는다. (action에 대한 feedback은 수천 번의 time-step이 지난 후에 얻을 수도 있다.)

 

agent가 현재 스크린의 이미지만 관측하기 때문에, 부분적으로 이해하기 때문에 전체에 대한 이해를 하기는 어렵다.
그래서 일련의 action과 observation을 기반으로 게임 전략을 학습한다. emulator의 모든 sequence는 유한한 time-step 내에서 종료될 것이라고 가정한다. 이러한 형식이 각각의 sequece가 구분된 상태인 크지만 유한한 MDP(Markov decision process)를 제공한다. 결과적으로 단순히 $t$ 시점의 상태를 나타내는 $s_t$를 이용해 MDP를 학습한 표준 강화 학습을 적용할 수 있다.

 

agent의 목표는 미래의 보상을 최대화하는 action을 선택하면서 emulator와 상호작용하는 것이다. 저자는 매 time-step마다 미래 보상이 점점 감소하도록 discount factor $\gamma$를 정의한다. 특정 시점 $t$에서 discount factor $\gamma$가 반영된 보상을 $R_t$라고 정의하기 위해 다음과 같은 식을 사용한다.

$T$ : 게임이 종료되는 시점

또 어떤 일련의 $s$를 파악하고 취한 action을 통해 얻을 수 있는 최대 기댓값을 반환하는 최적의 action-value function $Q^*(s, a)$을 아래와 같이 정의했다.

$\pi$는 action에 policy를 매핑하는 sequence이다. 최적의 action-value function은 Bellman Equation이라고 알려진 중요한 정체성을 따른다. 이는 다음과 같은 직관을 기반한다. 이 식은 만약 sequence $s'$의 다음 time-step에서 최적의 값인 $Q^*(s', a')$ 가 모든 행동 $a'$에 알려져 있으면, 최적의 전략은 $r + \gamma Q^*(s', a;)$의 기댓값을 최대화하는 것이다. 이것을 식으로 나타내면 아래와 같다.

 

많은 강화 학습의 기본 아이디어는 Bellman equation을 iterative update로 이용하면서 action-value funtion을 estimate 하는 것이다. 이러한 value iteration은 아래와 같이 최적의 action value function으로 수렴한다.

하지만 이 기본적인 접근법은 실용적이지 못하다. 왜냐하면 action-value function은 어떤 일반화 없이 각 sequence마다 따로 추정하기 때문이다. 이것은 전형적으로 선형 함수 approximator이다, 하지만 가끔은 비선형 함수 approximator가 사용되기도 한다. 가중치 $\theta$를 가진 신경망 함수 approximator를 Q-network라고 한다. Q-network는 각 iteration에서 변경되는 loss fuction $L-i(\theta_i)$의 sequence를 최소화하면서 학습을 한다.

$y_i$는 target이고 $p(s, a)$는 sequene $s$과 action $a$를 아우르는 behaviour distribution이라고 칭하는 확률분포이다. loss function을 최적화할 때에는 이전 iteration의 파라미터들은 고정비 된다. target은 network의 가중치에 의해 결정되는데, 이는 지도학습에서 학습자에 고정되는 target과 상반되는 것이다. 가중치에 대해 loss function을 미분하면 아래와 같은 gradient를 얻을 수 있다.

 

위의 gradient에서 모든 기댓값을 계산하는 대신 SGD를 이용해 loss function을 최적화하는 것이 더 편리하다. 가중치가 매 time-stpe마다 업데이트가 되고 기대값들이 behaviour distribution의 단일 샘플로 대체하면 익숙한 Q-learning 알고리즘을 얻을 수 있다.

 

주목해야 할 것은 이 알고리즘이 model free 하다는 것이다. 이는 명시적으로 $\varepsilon$의 추정 값 없이 emulator의 샘플을 이용해 직접적으로 강화 학습 문제를 해결할 수 있다.
이 알고리즘은 또한 policy free 하다. 이는 greedy strategt $a = max_aQ(s, a;\theta)$를 학습한다. 이는 state space를 충분히 보장하는 behaviour distribution을 따른다. 실전에서는 behaviour distribution은 확률 1-$\varepsilon$을 가지는 greedy strategy를 따르는 $\varepsilon$-greedy에 의해 결정되고 확률 $\varepsilon$을 가지는 임의의 action을 선택한다.

 

3. Related Work

가장 성공적인 강화 학습의 예로는 TD-gammon이 있다. 이는 완전히 강화 학습과 self-play로 학습한 backgammon-playing 프로그램으로 인간의 play 능력을 뛰어넘는 성능을 보였다. TD-gammon은 model-free 한 구조로 Q-learning과 유사한 강화 학습 알고리즘으로서 하나의 hidden layer를 가진 multi-layer perceptron을 이용해 value function을 추정한다.

하지만 TD-gammon은 Go와 checker에 같은 방법을 적용하는 초기 TD-gammon의 후속 연구 시도들은 성공적이지 못했다. 그래서 이러한 접근은 backgammon에만 적용되는 특별한 경우라고 인식을 하게 되었고 이는 아마도 주사위의 확률의 우연성이 state space를 탐색하고 value function을 smooth 하게 만들기 때문이다.

 

Q-learning과 같이 model-free 한 강화 학습 알고리즘과 비선형 function approximator를 결합하거나, off-policy learning은 Q-network를 발산하게 할 수도 있다. 이후에는 대부분의 강화 학습은 수렴을 보장하는 linear function approximaor에 초점을 두게 되었다. 최근이 되어서야 딥러닝과 강화 학습의 결합에 대한 관심이 늘었다. Deep neural network는 환경 $\varepsilon$을 추정하고 restricted Boltzman machine은 value function 혹은 policy를 추정하는 데 사용되어 왔다.

 

그리고 Q-learning의 발산 문제는 gradient temporal-difference 방법들을 통해 부분적으로 해결했다. 이러한 방법들은 non linear function approximator를 이용하는 fixed policy 평가할 때나, restricted variant Q-learning이 적용된 linear function approximation 을 이용하는 control policy를 학습할 때에 수렴한다고 증명됐다. 하지만 이러한 방법들이 non-linear control로 확장되지는 않았다.

이 논문의 접근법과 가장 유사한 이전 연구는 neural fitted Q-learning(NFQ)이다. NFQ는 Q-network의 파라미터를 갱신하기 위해 RPROP 알고리즘을 이용해 2번 방정식의 loss function을 최적화했다.

2번 방정식

하지만 NFQ는 iteration마다 데이터 셋 크기의 비율에 따른 연산 비용을 가진 batch update를 사용한다. 반면에 이 논문의 접근법은 stochastic gradient update를 이용해 iteration마다 low constant cost를 유지하고 큰 데이터 셋에 척도를 맞추었다. NFQ는 먼저 받아 deep autoencoder를 이용해 저차원으로 표현된 task를 학습하고 그 representation에 NFQ를 적용하여 순수하게 visual input을 이용하는 현실에서의 간단한 task에 성공적으로 적용했습니다. 반면 이 논문의 접근법은 visual input을 바로 받아 end-to-end 강화 학습에 적용했다. 그 결과, action-value를 판별하는 것과 직접적으로 관련된 feature들이 학습하도록 했다.

 

Atari 2600 emulator는 linear function approximation과 generic visual feature를 standard RL에 적용한 연구에서 사용하기 시작했다. 이후, 많은 양의 feature와 tug-of-war hashing을 이용해 feature들을 저차원 공간에 무작위로 사영(project) 하여 성능을 개선했다.

 

4. Deep Reinforcement Leanrning 

최근의 computer vision과 speech recognition은 매우 큰 데이터 셋을 이용하여 신경망을 학습하여 비약적으로 발전했다.
가장 성곡적인 접근법은 SGD에 기반한 가중치 갱신을 경량화하여 DNN을 효율적으로 학습하는 것이었다. 충분한 데이터를 DNN에 입력하여 hand-crafted feature보다 더 나은 representation을 학습할 수 있게 했다. 이 논문의 목표는 RL 알고리즘과 DNN을 연결하여 RGB 이미지를 직접 다루고 stochastic gradient update를 이용해 학습 데이터를 효율적으로 처리하는 것이다.

 

TD-gammon은 이러한 접근법의 시작점이 된다. 이 모델은 주어진 환경과 알고리즘의 상호작용으로부터 얻은 experience의 on-policy sample로부터 직접적으로 value function을 추정하는 network의 파라미터를 갱신한다. 이 접근법이 20년 전의 최고의 backgammon(게임의 한 종류) player 보다 더 뛰어난 결과를 내었기 때문에, 20년 동안의 하드웨어의 개선, 현대 DNN과 가변적인 RL 알고리즘의 결합이 이러한 진전을 냈을지 의문을 가지는 것은 자연스럽다.

 

TD-Gammnon과 유사한 online 접근법들과 달리 이 논문의 연구팀은 experience replay라는 기법을 이용한다. 이는 매 time-step마다 agent의 경험을 dataset에 저장하고 많은 에피소드들이 replay memory에 쌓인다. experience replay 이후에 agent는 $\varepsilon$-greedy policy에 따라서 action을 선택하고 실행한다. 무작위 한 길이의 기록들을 신경망의 input으로 쓰는 것이 어렵기 때문에 저자들은 function $\phi$에 의해 생성된 고정된 길이의 기록들에 Q-function에 적용한다. 이 알고리즘을 deep Q-learning이라고 부르고 다음과 같이 설명할 수 있다.

이 알고리즘은 표준 online Q-learning 보다 더 나은 점이 있다.
첫째, 각 단계의 experience는 잠재적으로 많은 가중치 갱신에 사용되고, 이는 더 큰 데이터 효율성에 기여한다.
둘째, sample 간의 높은 상관관계 때문에 연속적인 sample로부터 학습하는 것은 비효율 적이다. 그래서 무작위 샘플링을 통해 이러한 상관관계 문제를 해결할 수 있고 그리하여 가중치 갱신의 변동성을 감소시킨다.

셋째, on-policy를 학습할 때, 현재의 파라미터는 파라미터가 학습되는 다음 데이터 샘플을 결정한다. experience replay를 이용함으로써 behaviour distribution 이전의 여러 state에 걸쳐 평균화되고 이는 학습을 평활하고, 파라미터의 요동이나 발산을 피할 수 있게 한다. experience replay로 학습할 때, 반드시 Q-learning의 choice를 원활하게 하는 off-policy를 학습해야 한다. 왜냐하면, 현재의 파라미터들은 sample을 생성하는 파라미터들과 다르기 때문이다.

 

이 알고리즘은 replay memory의 마지막 N 개의 experience를 저장한다. 그리고 갱신을 할 때, dataset $D$로부터 균등하게 sampling을 한다. 이 접근법은 어떤 관점에서는 제한되는데, 이는 memory buffer가 중요한 전환을 미분하지 않고 또 정해진 memory size N 때문에 최근의 trantion으로 덮어쓰기 때문이다. 유사하게, 균등 sampling은 replay memory 내의 모든 transition의 중요도를 동일하게 한다. 더 복잡한 sampling 전략은 priortized sweeping 과 유사하게 학습을 가장 잘할 수 있는 transtion에 더 큰 무게를 두는 것이다.

 

4.1 Preprocessing and Model Architecture

1) Preprocessing

128의 color pallette를 가진 210 x 160 크기의 pixel 이미지의 Atari 프레임을 처리하는 것은 연산적으로 벅찰 수 있다. 그래서 저자는 input의 차원을 줄이는 기초적인 전처리 과정을 적용했다. raw frame들은 RGB에서 grayscale로 변경하고 110 x 84크기로 사이즈를 줄였다. 최종 input은 대략적으로 게임을 하는 구역을 84 x 84 크기로 자른 이미지이다. 이 과정은 이 연구에서 GPU를 이용해 2D convolution을 사용하는데 이는 square input을 받아들이기 때문에 필요한 과정이다. 이 논문의 실험을 위해, 위의 deep Q-learning의 $\phi$ 함수는 이 전처리 과정을 마지막 4개의 프레임에 적용하고 이를 쌓아
Q-function의 input 을 생성한다. (1개의 화면이 4개의 프레임으로 구성되었기 때문에 4개를 기준으로 처리하는 것)

 

2) Model Architecture

Q가 history-action pair들이 Q-value를 예측하기 때문에, 이전의 몇 가지 접근법을 통해 history와 action을 신경망의 입력값으로 받는다.
이 방법의 단점은 각각의 action Q-value를 예측하기 위해 분리된 forward pass가 필요하다는 것이다. 이는 연산의 양도 선형적으로 늘어나는 문제가 있다.

 

연구팀은 각각의 가능한 action마다 분리된 output unit이 있고 신경망의 input으로는 state representation만 사용하는 아키텍처를 이용한다.
output은 input state에 대한 개별 action에 대한 예측된 Q-value와 상응한다. 이 아키텍처의 장점은 주어진 state에서 모든 가능한 action의 Q-value의 연산을 한 번의 single forward pass로 처리해서 연산량을 줄일 수 있는 점이다.

 

7개의 Atari 게임에 쓰인 정확한 아키텍처는 다음과 같다. 

• 신경망의 input은 $\phi$를 통해 전처리된  84 x 84 x 4 크기의 이미지이다.
• 첫 번째 hidden layer는 input image에 stride=4로 설정하고 16개의 8 x 8 filter로 합성곱 연산을 하고, relu를 적용했다.
• 두 번째 hidden layer는 stride = 2로 설정하고 32개의 4 x 4 filter로 합성곱 연산을 하고, relu를 적용했다.
• 마지막 hidden layer는 fully-connected 되고, 256개의 rectifier 유닛으로 구성했다.
• 최종적으로 output layer는 각각의 수행 가능한 action에 대해 single output을 가지는 fully-connected linear layer이다.
• 수행 가능한 action은 연구팀이 고려한 게임에 따라 4 - 18개이다.
• 이 접근법으로 학습한 convolutional network를 Deep Q-Networks(DQN)으로 부른다. 

5. Experiments

지금까지, 총 7개의 ATARI 게임에 실험을 진행했다. 모든 게임에 동일한 아키텍처, 학습 알고리즘, hyperparameter를 사용했다. 이는 이 연구의 접근법이 각 게임의 특성을 통합하지 않아도 충분히 강건한 것을 보여준다.
이 연구의 agent를 실제 게임에서 평가를 하면서, 학습을 하는 동안 reward 구조에 한 가지 변화를 주었다.
게임마다 점수의 범위가 다르기 때문에, positive reward는 +1, negative reward는 -1, 변화가 없을 시 0으로 reward를 고정시켰다. 이러한 방식으로 보상을 고정하면, error derivatives의 범위를 제한하고 여러 게임에 똑같은 learning rate를 적용하기 더 쉽게 만든다. 또한 agent가 다른 크기의 보상 간의 차이를 구별하지 못하기 때문에 agent의 성능에도 영향을 끼친다.

 

실험에서, RMSProp 알고리즘을 이용했고 mini-batch의 크기는 32로 설정했다. 학습을 하는 동안 behavior policy는 $\varepsilon$가 1에서 0.1의 범위에서 처음 100만 프레임에 걸쳐 강화되는 $\varepsilon$-greedy를 이용했다.
이 실험에서 총 1,000만 개의 프레임을 학습했고 가장 마지막 100만 개의 프레임을 이용하는 replay memory를 구성했다.

 

이전의 Atari 게임을 하는 접근법을 유지하면서 간단한 frame-skipping 기법을 이용했다. 정확히 말하자면, agent가 프레임마다 action을 선택하는 것 대신에 $k^th$마다 action을 선택하게 하는 것이다. 그리고 agent의 마지막 action은 skip된 프레임에서 반복한다.
1 스텝을 forward 하는 것이 agent가 action을 선택하는 것보다 연산 냥이 적기 때문에, 이 방법이 agent로 하여금 실행 시간이 크게 늘어나지는 않지만 대략 $k$배 더 많은 게임을 할 수 있다.
실험에는 Space Invader를 제외한 모든 게임에서 $k$를 4로 설정했다. Space Invader에서는 $k$를 4로 설정하면 레이저가 보이지 않은 현상이 발생하여 $k$를 3으로 설정했고 이것이 게임 간의 hyperparameter의 유일한 차이점이다.

 

5.1 Training  and Stability

지도학습에선 training과 validation set을 평가하면 모델의 성능을 쉽게 확인할 수 있다. 하지만 강화 학습에선, 학습 중에 agent의 성능을 정확히 확인하기는 어렵다. 이 연구의 성능 평가 지표가 하나의 에피소드에서 수집한 총 보상이거나, 여러 게임에서 평균을 낸 점수이기 때문에 학습 중에 주기적으로 성능을 평가한다.

 

average total reward metric은 잡음이 많은 경향이 있는데 이는 policy 가중치의 작은 변화가 state의 distribution에 큰 변화를 야기할 수 있기 때문이다.
아래의 맨 왼쪽 두 개의 플롯은 Breakour과 Seaquest 게임에서 average total reward 가 학습 중에 변화하는 모습이다. 보이는 것과 같이 둘 보상 모두 잡음이 심하다는 것을 확인할 수 있으면 이는 학습 알고리즘이 안정적인 학습을 하지 못한다는 것을 의미한다.

또 다른 안정적인 평가 지표는 policy의 estimated action-value function Q이다. 이는 주어진 어떤 state에서 policy를 따르면서 agent가 얼마나 감소된 reward를 얻을 수 있는지를 예측한다. 연구팀은 학습 전에 random policy를 실행하고 예측된 $Q$의 최댓값의 평균을 확인하며 고정된 set of state을 수집했다. 위의 나 맨 오른쪽 두 플롯은 average predicted $Q$가 average total reward보다 훨씬 더 부드럽게 증가하는 것을 확인할 수 있다. 또한 이 과정에서 발산하는 경우가 없었다.
이는 이론적으로 수렴을 보장할 수 없음에도 불구하고, 이 방법이 강화 학습 신호와 SGD를 안정적인 방법으로 사용하면서 큰 신경망을 학습할 수 있다.

 

5.2 Visualizing  the  Value  Function

위에서 가장 왼쪽 플롯은 Seaquest 게임의 30개 프레임 동안 predicted value function을 보여준다. 3개의 스크린숏은 차례대로 A, B, C로 정한다. 스크린숏 A의 왼쪽에 적이 나타났을 때 point A처럼 예측 값이 크게 증가한다. 스크린숏 B에서는 적이 어뢰를 맞기 직전에 point B처럼 한 번 더 예측 값이 증가한다. 스크린숏 C에서 다시 대략적으로 원래의 예측값으로 감소하는 것을 확인할 수 있다. 이것은 이 연구에서의 방법이 꽤 복잡한 연속적인 상황에서 value funciton이 어떻게 변화하는지 잘 학습하는 것을 의미한다.

 

5.3  Main  Evaluation

DQN을 Random, Sarsa, Contingency, Human, HNeat Best, HNeat Pixel의 각각의 성능을 비교하여 평가했다.  위의 표처럼 DQN은 Human performance를 제외한 다른 모든 모델들의 성능을 뛰어넘었다. 그리고 Breakout, Enduro, Pong 게임에서는 DQN이 Human performance를 상회하는 놀라운 성능을 확인할 수 있다.

 

6. Conclusion

이 논문은 강화 학습을 위한 새로운 딥러닝 모델을 소개한다. 그리고 raw pixel 데이터만 이용하여 Atari 2600 게임을 위한 어려운 control policy를 학습하는 것을 증명했다. 또한 variant of online Q-learning을 소개했는데, 이것은 강화 학습을 위한 deep network를 학습하는 것을 replay memory를 적용한 stochastic minibatch updates 통해 쉽게 하는 방법이다. 이 연구의 접근법으로 7개 게임 중 6개의 게임에서 아키텍처와 hyperparameter를 조정하지 않고 SOTA 한 성능을 보였다.