KDST

본 게시물은 필자가 2019년 12월 8일부터 진행되었던 NeurIPS 논문중에서 인상깊었던 논문 및 아이디어를 포스팅 한 것입니다. 본 포스팅은 논문에 첨부된 그림을 첨부했으며 문제가 될 시 삭제하도록 하겠습니다. 또한 본 포스팅은 Deep Q Network에 대한 기본 지식을 가지고 있다는 전제하에 작상된 포스팅입니다. Deep Q-Network에 대한 내용은 아래의 링크를 참조하시길 바랍니다. 논문 링크는 이곳을 클릭해주세요.

Sample-Efficient Deep Reinforcement Learning via Episodic Backward Update

강화학습을 실제 환경에 적용하기에는 쉽지 않습니다. Aracade Learning 환경에서 Deep Q-Network를 사용하여 학습을 시킬 시 2억개의 프레임을 사용하며 이는 실제로 39일동안 이루어집니다. 이는 사람이 실제로 게임에서 높은 점수를 받기까지와의 시간차이가 많음을 의미합니다. 본 논문에서는  Deep Q-Network에서 랜덤하게 한스텝 이동에 대한 샘플을 추출하는 샘플링 방법에 효율성이 떨어지는 이유를 다음과 같이 2가지 제시했습니다.  

• sparsity하게 보상을 갖는 환경에서 의미있는 reward 값을 가지는 한 스텝에 대한 샘플을 뽑을 확률이 적습니다. 
• 학습 초기에는 학습이 되지 않아 모든 reward의 값이 0이므로 한스텝 이동으로 Q 값을 업데이트 하는것으로는 학습을 할 수 없습니다. 따라서 0이 아닌 reward 값이 나올때까지 전혀 학습이 되지 않는 현상을 가지게 됩니다. 

위의 문제를 아래의 간단한 예시를 통해 표현할 수 있습니다. 현재 agent가 s1에서 시작하여 s4에 도착하기까지 총 5번의 step을 가지게 됩니다. 이때 5번째 스텝이 agent의 목표인 terminal state에 도달했으므로 reward 1점을 얻고 한번의 에피소드가 끝나게 됩니다. 기존의 Deep Q Network는 에피소드가 끝난 후 얻어진 5개의 샘플을 replay memory에 저장한 후 uniform random 샘플링을 수행합니다. 이 과정에서 가장 최대의 값을 가지는 reward에 해당하는 샘플이 우선적으로 샘플링 되지 않습니다. 또한 모든 terminal state를 제외한 모든 state의 reward 값이 0이므로 한스텝으로 학습이 불가능합니다. 따라서 본 논문에서는 하나의 에피소드가 끝나면 terminal state에서부터 순차적으로 backward 하며 샘플링 하는 방식을 사용하여 학습 시 최적의 path를 찾는것을 목표로 Episodic Backward Update 방식을 제안했습니다.  아래의 b 그래프에서는 Uniform random하게 샘플링 하는 방식보다는 EBU 방시을 사용하였을때 바로 최적의 path를 찾는 결과를 보여줍니다. 

본 논문에서는 Episodic Backward Update (EBU) 방식을 제안했습니다. EBU 방식은 기존 Deep Q Network에서 사용하는 replay memory로부터 전체 에피소드를 샘플링하고 샘플링 된 에피소드 전체를 backward 방식으로 순차적으로 전파합니다. EBU 방식을 사용하면 에피소드 내 모든 트랜지션을 업데이트함으로써 reward 전파 속도를 높일 수 있습니다. 위의 예시에서는 오직 5번의 업데이트 후에 최적의 path를 찾게 됩니다. 아래는 Q table을 사용하는 Q-learning 방식에 EBU를 적용한 수도코드 입니다. 

하지만 실제상황에서는 state와 action의 수가 많으므로 Q table을 사용하는 방식을 사용하는 데 한계가 있습니다. 따라서 신경망을 사용하여 Q value를 근사하는 Deep Q Network를 사용하고 있으며 DQN에 EBU를 적용한 수도코드는 아래와 같습니다. 코드의  beta 파라미터는 (0,1) 값을 가지며 "backwardness' 의 정도를 의미합니다. beta 0으로 설정할 시 아무런 값도 전파하지 않겠다는 뜻이 되며 1로 설정하면 리워드를 전파 하겠다는 의미로 해석할 수 있습니다. 

아래의 그림은 replay memory를 시각화 하여 EBU의 원리를 보여주는 그림입니다. 계산 효율적인 재귀 알고리즘을 통해, sparsitiy한 reward가 샘플링된 에피소드의 모든 스텝에 직접 전달되는 것을 알 수 있습니다. 

EBU를 적용했을때 기존의 DQN 대비 성능개선이 얼마나 되었는지를 보여주는 결과를 아래에 제시했습니다. 49개의 Atari 게임 도메인에서 39개의 게임에서 기존 DQN보다 좋은 성능을 보였습니다. 또한 약 20배 적은 수의 샘플 수 (200M -> 10M)로 기존 DQN의 성능과 유사한 성능을 보임을 알 수 있었습니다. 

본 게시물은 김성훈 교수님의 모두의 강화학습 https://hunkim.github.io/ml/ 을 참고하였으며 "Playing Atari with Deep Reinforcement Leraning" , "Human-level control through deep reinforcement learning" 논문을 기반으로 제작했음을 알립니다.

Q-learning

Q-learning은 에이전트(agent)가 주어진 상태 (state) 에서 행동(action)을 취했을 경우 받을 수 있는 보상(reward)의 기댓값을 예측하는 Q 함수를 사용하여 최적의 정책(policy)을 학습하는 강화학습 기법입니다.

   1. agent는 현재 환경(environment) 에서 특정 state s에 존재합니다. 

   2. agent가 action의 집합 A의 모든 action을 취했을 때의 rewards를 Q 함수로 구할 수 있습니다. 

   3. reward가 가장 높은 action인 policy를 취하고 agent의 state는 새로운 state로 업데이트 됩니다. 

Q- learning에서 쓰이는 Q 함수는 다음과 같이 정의 할 수 있습니다.

learned value는 agent가 현재 state에서 다음 state로 가기 위해 action을 취할때 얻을 수 있는 보상을 나타내는 식입니다. 하지만 미래에 agent가 받을수 있는 reward를 100% 신뢰하는것이 아닌 discount factor로 제한을 두고, 그만큼 현재 state에서 받았던 reward도 고려하여 최종적인 reward 값을 계산하게 됩니다. 이것이 바로 old value가 식에 포함된 이유입니다. 이때 계산한 reward 값은 "Q-table"에 저장됩니다. Q table을 점진적으로 수정해나가는 반복절차를 통해 agent의 행동을 학습시킬 수 있습니다. 

하지만 이러한 Q-learning은 실제로 실행시켜보면 잘 동작하지 않는 경우가 빈번합니다. 

   1. agent가 취할 수 있는 state의 수가 많은 경우, Q-table 구축에 한계를 가지게 됩니다.

   2. 순차적인 sample data 간의 corelation으로 인해 학습이 어렵습니다. 

   3. 예측값 (target Y)이 제대로 예측을 수행한것인지의 여부를 비교하기 위한 정답(Y)이 변합니다. 

위와 같은 이유로 Q-learning은 잘 동작 하지 않습니다. 이러한 Q-learning의 단점을 보완하기 위해 Q-learning 기반의 DQN (Deep Q Network)이 출현했습니다. 

DQN

DQN은 CNN (Convolutional Neural Net) 을 이용하여 Q 함수를 learning 하는 강화학습 기법입니다. 이때 CNN layer를 깊게 하여 training을 할 때 Q value의 accuracy를 증대시키는 것을 목표로 하고있습니다. 

DQN은 Q-learning의 한계점을 극복하기위해 다음과 같은 기법을 사용합니다. 

   1. Experience Replay buffer를 사용합니다. 

   2. Target Neural Net과 Predict Neural Net으로 네트워크를 분리합니다. 

Experience Replay buffer를 사용하는 이유는 순차적인 sample data 간의 corelation을 해결하기 위함입니다. agent의 state가 변경된 즉시 훈련시키지 않고 일정 수의 sample이 수집 될 동안 기다리게 됩니다. 나중에 일정 수의 sample이 buffer에 쌓이게 되면 랜덤하게 sample을 추출하여 미니배치를 활용해 학습합니다. 이 때 하나의 sample에는 state, action, reward, next state가 저장됩니다. 여러개의 sample로 training을 수행한 결과들을 모두 수렴하여 결과를 내므로 corelation 문제를 해결 할 수 있습니다. 

하나의 네트워크를 사용하면 계속 Target Q-value 값이 변경되므로 Target값이 변함을 막기 위해 Target을 output으로 도출하는 Target Neural Net과 Q-value값을 예측하는 Neural Net을 분리합니다. 이 때 2개의 네트워크는 weight parameter를 제외한 모든 것이 같은 네트워크로 정의합니다. 예측한 Q-value의 안정된 수렴을 위해 target Network는 계속 update 되는것이 아닌 주기적으로 한번 update를 시키는 것이 특징입니다. 

아래는 DQN의 pseudo code 입니다. 

training을 수행할 때의 Loss function으로는 아래와 같은 MSE를 사용합니다. 아래의 loss function와 psuedo code에서 볼 수 있듯이, 두개의 네트워크가 분리되어 있으므로 각 네트워크에서 사용되는 파라미터 $\theta$ 의 표기가 다른것을 확인할 수 있습니다. 

기술한 내용을 바탕으로 한 ppt 자료를 업로드 합니다.