Title:

Neural Episodic Control

Overview:

Neural network을 활용한 reinforcement learning (DQN)으로 유명한 DeepMind에서 최근 arXiv에 공개한 neural episodic control (NEC) 논문에 대해 소개합니다.

NN + RL = DQN 이라면, DQN + dictionary(memory) = NEC 라고 생각할 수 있습니다. DQN을 비롯한 다양한  deep reinforcement learning 연구들은, human-level performance에 도달하는데까지 걸리는 “학습시간” 및 학습에 필요한 “데이터 (experience)”의 양 측면에서 비효율적 인데요, 이 논문에서는 그러한 단점을 극복하기 위한 아이디어를 제안합니다.

key idea는 agent의 경험들을 memory”에 기록해두고, 이 memory에 기록된 과거 이력을 바탕으로 특정 state에서 취해야 할 action을 선택하도록 하자는 건데요, 다시 말해서, 각 experience를 network이 implicit하게 학습하도록 맡겨두는 것이 아니라, 각 experience를 그때그때 memory에 기록해 둠으로써, 이 후 비슷한 상황에서 취해야하는 action을 선택할 때 memory에 기록된 과거 이력을 참고할 수 있도록 해주는 거죠!

이 idea를 적용하면, 기존의 deep RL 연구들 대비 다양한 Atari game들에 대한 학습속도가 향상되는 것을 실험적으로 확인할 수 있습니다.

Introduction:

기존의 deep RL 연구들이 data-inefficient하며 학습속도가 느린 이유는,

  • SGD optimizer의 작은 learning rate (learning rate이 크면 loss가 발산하죠…),
  • sparse reward signal (게임이 끝나야 결과를 알 수 있으니, 그 과정에서의 reward는 대부분  zero가 되겠죠…)
  • one-step reward propagation at a time (이는 뒤에서 좀 더 자세히…)

이러한 단점을 극복하고자 NEC를 제안합니다.

“our agent is able to rapidly latch onto highly successful strategies as soon as they are experienced, instead of waiting for many steps of optimization as is the case with DQN”

즉, 각 experience를 그때그때 memory에 기록해두고 학습에 사용하는 방식입니다. 이 memory를 “semi-tabular representation” 라고 부릅니다. 이 memory는 기본적으로는 append-only memory이지만, 당연히 maximum size가 있고 max size에 도달하면 least recently used (LRU) 방식으로 update를 합니다.

DQN (Deep RL):

먼저  기반이 되는 DQN에 대해 간단히 살펴 볼 필요가 있겠습니다. 보통 RL agent의 action-value function Q^{\pi}(s, a) 는, initial state s 에서 agent가 선택한 action a 로부터 기대할 수 있는 reward 의 expectation Q^{\pi}(s, a) =\mathbb{E}_{\pi}[\sum_{t} \gamma^{t} r_{t} \vert s, a] 으로 정의할 수 있습니다. 여기서 \gamma \in (0,1) 는 long-term reward에 대한 discount factor 이구요.

DQN의 agent는 time-step t 의 state s_{t}에서 어떤 action a_{t} 가 best action인지를 판단하는 value function Q(s_{t}, a_{t}) 를 학습하기위해 Q-learning을 사용하는 network입니다. 이렇게 학습된 Q function으로 부터, state가 주어졌을 때 취해야할 action a_{t} = \arg\max_{a} Q(s_{t}, a) 을 선택할 수 있게 되겠죠.

DQN 에서 Q(s_{t}, a_{t}) 는 CNN 으로 구성되고 학습은 다음의 절차를 따릅니다.

  • agent가 transition을 목격할 때 마다, (s_{t}, a_{t}, r_{t}, s_{t+1}) tuple 형태의 데이터를 replay buffer” 에 저장해두고, tuple 단위의 학습을 진행합니다.
  • tuple들로 minibatch를 구성하는데, 각 tuple에 대해 network의 output과 Q-learning target y_{t} = r_{t} + \gamma \max_{a} \tilde{Q}(s_{t+1}, a) 사이의 L2 loss를 minimize하는 방식으로 학습을 수행하죠. 여기서 \tilde{Q} (s_{t+1}, a)는 현재시점 (즉, t+1 시점에서는 old version)의 value network 이지만, 학습이 진행됨에 따라 미래의 action을 점점 잘 예측하는 모델로 학습이 진행됩니다.
  • RL은 학습이 어렵다고들 하는데요, replay buffer로부터 randomly sampling한 uncorrelated tuple 단위의 학습이 안정된 학습에 큰 도움을 줍니다.

Neural Episodic Control:

그럼 이제 본론으로! NEC agent는 세 개의 파트로 구성됩니다.

  • pixel image (state s) 를 받아서 memory query key 를 생성하는 CNN
  • action 당 한 덩어리의 memory module
  • memory read-out을 Q-value (Q(s, a)) 로 변환하는 final network

그 중 먼저 memory에 대해 살펴보죠. 각 action a \in A 에 대해, memory는 M_a = (K_a, V_a)의 key-value pair 형태를 갖게되고, end-to-end learning시 gradient가 전파될 수 있도록 differentiable function으로 lookup process (바로 아래 설명이 있어요!)가 정의되기 때문에, differentiable neural dictionary (DND)라고 부릅니다.

  • DND lookup을 통해 출력되는 값은, DND value들에 대한 weighted-sum 형태로 정의되고 (o = \sum_i w_i v_i), 이 때의 weight는 DND query vector h와 DND key들과의 similarity로 정의가 됩니다. 즉, query와 비슷한 key에 대해서는 높은 weight를 갖게됩니다. 이렇게.. w_i = k (h, h_i) / \sum_j k (h, h_j). 여기서 k는 kernel function (e.g., Gaussian kernel)이구요.
  • DND query가 이뤄지고 나면, key-value pair가 하나 생성되죠. 이를 다시 DND memory에 write해야합니다. DND 는 기본적으로 append-only memory이기 때문에, query (h)와 동일한 key가 DND에 존재하지 않는다면 append하면 되고, 존재한다면 그 key에 해당하는 value를 새로 update하면 됩니다. (서론에서 언급했듯이, 실제로는 memory-size가 한정되어있기 때문에, 컴퓨터 시스템에서 한정된 memory 자원을 사용할 때 일반적으로 사용하는 LRU replacement방식을 채택했습니다.)

다음으로 DND를 포함하는 agent architecture 및 algorithm을 살펴봅시다.

  • agent가 현재 state s (pixel image) 를 받으면, CNN이 DND query에 사용될 latent vector h를 생성하고, 앞서 설명드린 방식에따라 h로부터 DND를 lookup 합니다. 각 key에 대해 계산되는 similarity에 따라 DND value들을 weighted-sum 하면, 이 값이 곧 output이 됩니다.
    NEC architecture.png
  • 알고리즘을 살펴보죠. 구성요소들을 간단히 설명 드리면, replay buffer D, per-action DND M_a, 그리고 (뒤에 설명드릴) N-step Q-function을 위한 step-size N이 있습니다. 각 time-step에 대해, state s로 부터 abstraction된 query h를 얻고, 모든 action에 대한 action-specific DND lookup을 수행해서, best action을 선택합니다. 여기서 \epsilon-greedy search를 하는데요, 이는 \epsilon의 확률로 action a_t을 random하게 취하고, 그 외의 확률로 best action을 취하는 방식입니다. action이 정해지면, 그에 대한 reward r_{t+1}가 정해지게 되죠. 이제DND 및 replay buffer를 update해야 합니다. (h, Q^{(N)}(s_t, a_t))를 해당 action a_t에 해당하는 DND M_{a_t}에 write (replace or append)하고, (s_t, a_t, Q^{(N)}(s_t, a_t))를 replay buffer D에 저장하면, single minibatch에 대한 single iteration이 끝납니다. 이를 모든 time-step, 모든 episode에 대해 반복하면서 loss를 줄여나가면, data-efficient agent가 학습됩니다!
    agent algorithm.png
  • N-step Q-function은, Q^{(N)}(s_t, a) = \sum_{j=0}^{N-1} \gamma^j r_{t+j} + \gamma^N \max_{a'} Q(s_{t+N}, a') 으로 표현됩니다. 즉, N개의 on-policy reward (왼쪽 term)와 나머지 trajectory에 대한 discounted reward (off-policy term에 대한 backup이라고 생각하시면 됩니다. 오른쪽 term)로 구성됩니다. 즉, 현재 state에서 취하는 action이 N-step 뒤 시점에 미치는 영향을 반영한 Q-function으로 생각하시면 됩니다.
  • 이제 similarity를 표현할 kernel function이 남았습니다. 저자들은, query h와 유사한 key가 DND의 key h_i안에 없을 경우, exponential function을 포함하는 Gaussian kernel을 사용하면, 특정 key 에 weight를 몰빵(?)하는 경우가 생기는 것을 방지하고 싶었다고 하구요,  결과적으로 k(h, h_i) = 1 / (||h - h_i||_2^2 + \delta) 와 같은 kernel function을 정의해서 사용했습니다.

이렇게 학습을 했더니, 기존의 deep reinforcement learning 방식들 대비 학습속도 및 평균 성능이 좋아지는 것을 확인할 수 있었습니다. 즉, DND를 써서 value interpolation하는 방식에 적합한 CNN embedding 을 잘 학습할 수 있도록, 제공된 reward signal들을 효율적으로 활용한 결과라고 볼 수 있겠죠. 몇몇 Atari game에 NEC방식을 적용해 봤더니 아래 그림들 처럼 학습속도 및 최종 성능이 두루두루 좋습니다. 결과가 더 많은데, 자세한 결과는 논문을 살펴보시면 됩니다.
스크린샷 2017-03-24 오후 2.31.16.png스크린샷 2017-03-24 오후 2.31.28.png

숫자로 성능을 한 번 볼까요? 보시다시피 다양한 previous work들 대비 NEC의 학습속도가 상당히 빠릅니다. 4M fame즈음에 이미 다른 방식들의 20M frame정도의 성능에 빠르게 도달하고 있죠. (40M frame에서는 prioritized replay 방식 대비 성능이 낮습니다. 최종 성능이 더 좋아지도록 하는 것을 future work으로 남겨둔다고 합니다.)
스크린샷 2017-03-24 오후 2.33.32.png

Discussion:

NEC는 environment와의 interaction을 효율적으로 학습하는 방식으로 생각할 수 있겠습니다. 즉, 적은 경험으로도 좋은 성능을 얻을 수 있는 것으로 보아, RL의 generalization performance 향상에 도움을 주는 방식이라고 볼 수 있습니다.

그런데, 논문을 읽다보니 Learning to remember rare events (ICLR2017 @ Google Brain)라는 논문에 대한 이야기를 언급합니다. NEC와 비슷한 방식을 사용하지만 supervised learning에만 한정적으로 적용했다는 것을 한계점으로 지적했는데요, 궁금해서 읽어보니, key idea가 거의(완전에 가까운 거의) 동일합니다;; NEC의 핵심은 append-only DND를 활용한 data-efficient RL 학습인데, 언급한 논문 역시 dictionary-type의 append-only memory를 사용한 supervised learning model 학습이더라구요;;

따라서 다음 포스트에서는, Learning to remember rare events (ICLR2017 @ Google Brain) 이 논문을 좀 자세히 다뤄보도록 할 예정입니다!

Posted by:Hyo-Eun Kim

research scientist @ Lunit

2 replies on “Neural Episodic Control

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s