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

https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

이 블로그는 개인의 공부 목적으로 작성된 블로그입니다. 왜곡된 정보가 포함되어 있을 수 있습니다

Beginning

학부 수업때 강화학습 관련 수업을 듣던 와중, 논문 리뷰에 필요성을 느끼게 되었다. 그래서 가장 유명한 강화학습 논문중 하나인 DeepMind에서 발표한 "Playing Atari with Deep Reinforcement Learning" 논문에 대해 리뷰하려 한다. 실제로 구글링해보면 여러 한글 리뷰 블로그들이 검색될 정도로 유명한 논문이다.

Abstract

high-dimensional senory input을 control하는 정책을 성공적으로 학습하는 deep learning model 에 대해 말하고 있다. model은 convolutional neural network(CNN)을 사용하고, Q-learning을 통해 input값을 픽셀값을 넣으면 ouput으로 미래의 reward를 추정 할수 있는 value function을 산출한다. 실제로 저자는 위 방법을 사용하여 2600개의 Atari game을 적용하여 6가지의 게임에 대해서 이전에 시도해봤던 모든 접근방법보다 좋은 결과를 만들었고, 그중에 3개의 게임에서 인간의 수준을 능가했다고 말하고 있다.

 

 

Introduction

RL(reinforcement learning)에 대해서 vision 과 speech 같은 high-dimensional senory input을 학습하는 것은 큰 난제 였다고 한다. 대부분에 성공적인 RL의 경우, hand-crafted feature와 결합된 linear value function 에 의존하였다고 한다. 결국 성능은 어떻게 feature 묘사하는지에 따라 달라진다는 것이다. 

최근의 deep learning의 발전으로 인해 이러한 high-dimensional senory input의 feature를 정의하는것이 가능해졌다. neural network architecture와 convolutional network와 같이 다양한 범위의 network들로 활용되면서 RL에게도 이러한 network을 적용해보자는 생각이 자연스럽게 이어져왔다.

그러나 RL에 deep learning을 적용하는 것은 몇가지 문제가 있었는데 대부분의 성공적인 deep learning model은 대량의 hand-labelled training data가 필요했다는 것이고, RL이 deep learning으로 나온 스칼라 값을 통해 학습되어야한다는 것이다. 그리고, deep learning 는 sample들이 독립이여야한다는 가정이 존재하는데 RL의 경우 각각의 state가 서로에게 관여한다는 문제와 RL가 새로운 동작을 학습하는 경우, 고정된 기본 형태를 변화시킨다는 문제(이해하지 못함)가 있었다.

이 논문에서는 CNN이 RL의 환경중 하나인 raw video에서 위의 문제를 성공적으로 극복하여 control을 학습한다는 것을 시사한다

출처: 해당 논문

저자는 위와 같은 게임에 적용하여 최종적으로 여러게임을 성공적으로 진행할 수 있는 하나의 network를 만드는 것이고, 이때 network는 게임에 관한 어떠한 부가정보를 알지 못한채로 게임 내부의 어떠한 state관한 정보를 알지 못한채, 인간의 실행 환경과 동일한 환경에서 진행된다는 것이다.

Background

환경 $ \varepsilon $ (Atari emulator)에 대해서 time-step 마다 agent는 action 집합 $ A=\{ 1,....,K\}$ 중 하나의 action $a_t$을 선택한다. action을 선택한 후에는 게임 내부에서 state가 변경되고, game score가 변경된다. 게임 내부(emulator)에서의 state는 agent가 알수 없고, agent는 단지 게임 환경이 제공하는 image $x_t \in R^d$ 만 할수 있다. reward에 해당하는 값은 game score로 반영된다. 

agent는 screen만 확인할 수 있기 때문에 task가 부분적으로 관찰되고, 시각적으로 인지된 state만 별칭이 붙게되고,(사용자 입장에서는 정의할수 있는 state의 범위) $x_t $로부터 현재의 상황을 전부 이해하는 것은 불가능한 상황이다. 우리가 해볼만한 시도는 $s_t=x_1,a_1,x_2....,a_{t-1},x_t$ 와 같이 우리가 선택한 action과 observation의 sequence 형태로 접근하는 것이다.  모든 sequence는 유한시간과 step안에 종료되는 것이 보장된다. 따라서 우리는 finite Markov decision process(MDP) 을 사용할 수 있게 된다.

agent의 최종 목표는 future rewards를 최대로 하도록 action을 선택하는 것이고, 이때 standard assumprtion 가정한다. rewards는 time-step 마다$r$씩 감소된다는 것인데, 우리는 미래의 감소된 return 을 $ R_t= \sum_{T}^{t'=t} \gamma^{t'=t}r_{t'} $ 으로 정의할수 있다. $T$는 종료 시점(기존에 잘알려진 MDP). action-value function $Q*(s,a)$ 가 return 의 기댓값을 최대로 하는 action를 가지도록 하는  $Q*(s,a)=max_\pi E[R_t|s_t=s,a_t=a,\pi]$을 정의한다.

optimal action-value function는 벨만 최적 방정식을 따르고 있는데 optimal value $Q*(s'.a') $에서 sequnce $s'$ 에 대해 $a' $ 의 기댓값을 최대로 하는 $r+\gamma Q*(s'.a')$을 선택한다.

$Q*(s,a)=E_{s'~ \varepsilon }[r+\gamma max_{ a'} Q*(s',a')|s,a]$

이는 $Q_{i+1}(s,a)=E_{s'~ \varepsilon }[r+\gamma max_{ a'} Q_i(s',a')|s,a]$ 라는 벨만 최적 방정식에서 value iteration 방식은 결국 optical value function으로 수렴하여 $Q_i->Q*$ 이 된다. 이러한 접근이 옳지 못하다고 생각할 수 있는데, action value function이 초기화 되지도 않은채로 추측하기 때문이다. 대신에 action value function을 함수로 근사해보겠다는 것이다.($Q(s,a;\theta  \approx Q*(s,a)$) 만약 비선형 함수가 필요하다면 neural network와 같은 방법을 사용하면 된다. Loss 함수는 다음과 같이 정의할 수 있다.

$L_i(\approx_i)=E_{s,a~}[(y_i-Q(s,a;\approx_i)^2]$ 

이 알고리즘은 model-free 이고, off-policy이다. 

 

Related Work

--------------------------------------------------------------------

Deep Reinforcement Learning

computer vision과 speech recognition는 deep neural networks을 대량의 training set으로 학습해왔다. 가장 성공적인 접근 방법은 raw input으로 부터 조금식 경사하강법으로 update하는 방식이다. 충분한 데이터를 주는 것이 handcrafted된 data를 주는 것 보다 더나은 성능을 보여줬다. 이러한 방법을 우리는 강화학습에도 적용해 볼 것인데, 우리의 목표는 강화학습 알고리즘을 deep neural network와 연결하여 image에 작동하고, 경사하강법을 사용하여 효과적으로 학습하는 것이다.

Tesauro의 TD-Gammon architecture가 이러한 접근을 가능하게 해주는데, 해당 architecture에서는 networkd의 parameter 값이 value function으로 업데이트되기 때문이다. 

TD-Gammon 방식과 다르게 experience replay라는 것을 활용해볼 건데, 각각의 step마다 $e_t=(s_t,a_t,r_t,s_{t+1})$data set를 생성하여 $D=e_1,....,d_N$ 와같이 저장되면 수많은 episode가 replay memory에 모을수 있다. 알고리즘은 Q-learning update와, minibatch update를 $e ~ D$에서 랜덤하게 추출하여 진행한다. experience replay를 수행하면 agent는 action는 $\epsilon$-greed policy로 action을 수행한다. neural network의 input으로 임의의 history(experience replay)를 사용하는 것이 힘들어 보이는데, Q-function이 function \phi 에의해 생성된 history를 사용함으로서 고정된 길이의 data를 사용할수 있다고 한다. 이것을 deep Q-learning으로 정의한다. 

deep Q-learning

이 방법이 online Q-learning 보다 좋은 점이 몇가지 가 있는데, 첫번째로 각각의 step마다의 experience가 다양한 weight update로 사용될수 있다는 점에서 데이터를 효율적으로 사용할 수 있고,  두번째로 random 하게 추출된 sample을 통해 학습함으로써 연속적인 sample을 학습할 때 발생할 수 있는 비효율적인 문제를 예방할 수 있고, (각각의 state가 서로에게 영향을 주는 문제) update의 분산을 줄일 수 있다. 세번째로 on-policy 방식으로 학습할 경우, 학습되고 있는 train data가 다음의 state를 결정하기 때문에(학습됨과 동시에 다음 state에 직접적인 영향을 주게됨) parameter가 부실한 local minimum에 빠질수 있고 이외에도 많은 문제가 발생할 수 있다. experience replay을 사용할 경우, off-policy 방법으로 분포를 평균화 하고, 진동 또는 발산하는 경우를 예방할 수 있다.

 

Preprocessing and Model Architecture

Ateri frame 내에서 210*160 pixel의 image에 대해 $\phi$ 함수를 적용하여 학습하기 적당한 크기로 만들수 있다

 

-(중략)-

 

neural network을 이용하여 Q함수를 구현하는 방법에 대해 생각해보자, Q함수는 Q-value추정할수 있어야 하는데 history와 action을 input으로 사용한다. 이 architecture의 문제는 forward pass하기 위해 Q-value를 매 action 마다 계산해야한다는 것이다. 대신에 우리는 output unit을 추가해서 state를 input으로 넣으면 가능한 action을 제공할 수 있게 한다. 이때 output는 예측된 Q-value에 대응하고, 이러면 forward하는 것만으로 가능한 action과 Q-value를 알 수 있다는 이점이 있다.

우리는 7개의 Atari game에 적용해볼건데, neural network는 $\phi$함수에 의해 $84\times 84\times 4$가 input으로 들어간다. 은닉층은 $168*8$ 형태로 stride는 $4$를 가진다. 두번째 은닉층은 $324*4$의 filter를 stride $2$ 값을 가진다. 최종 은닉층은 $256$개의 fully connected unit을 가지게 된다. 

 

Experiments