Search

'Episodic Backward Update'에 해당되는 글 1건

  1. 2019.12.24 2019 NeurIPS 논문 리뷰 - (Reinforcement Learning)
본 게시물은 필자가 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를 찾는 결과를 보여줍니다. 

 

uniform sampling 방식과 EBU 방식의 비교 

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

Tabular Q-learning Pesudo code

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

Deep Q Network pesudo code 

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

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

Atari 도메인에서의 기존 DQN 대비 EBU의 성능 개선