A (Long) Peek into Reinforcement Learning -Part6

 

Part5에서는 Q-learning에 대해서 마지막으로 보았다. 이걸 다시 잠깐 recap 해보면,

 

 

 

타겟을 구성할 때 가장 큰 값을 가지는 (max) 다음 action을 현재 policy에 관계없이 따르는 것이었다. 그런데 당연히, 하나 의문점이 들 만하다. 아니 가능한 다음 action이 많을텐데, 그러면 수많은 Q값들이 있을텐데, 그게 뭔지 알고? 그걸 다 계산해보고 거기서 가장 max를 취하는건가?

 

라는 의문이다. Tabular Q-learning은 Q값들의 table로 관리하면서 업데이트 하는 방식이다. 문제는 이게 state와 action space가 커질수록 당연히 table로 관리하기가 힘들어진다. 그래서 드디어 Deep Neural Net이 나오는데, 이 Q값을 어떤 parameterized 된 function으로 approximation 하겠다는 전략이 나온다. 그리고 그 parameterized function은 NN이다 (NN은 어떤 non-linear 함수를 배우는데에 선수이다). 

 

from tabular Q-learning to Large (S, A) space

 

---

 

 

DQN (Deep Q-Networks)

 

 

위와 같은 motivation의 결과물이 바로 아래의 논문이다!

 

 

 

 

DeepMind의 연구진들이 이를 이용해 Atari를 정복한 논문이 바로 DQN이다. 그래서 이번 DQN에 대해서는, policy gradient 내용을 들어가기 전, state-action value function을 학습하고 거기서 action을 선택하는 방법의 마지막 하이라이트로써 약간의 논문리뷰 형식으로 DQN을 다뤄보도록 하겠다.

 

---

 

DQN Function Approximation

 

 

저자들은 기존의 Bellman Equation을 이용한 iterative update는, totally impractical이라고 말한다.

 

그래서 마지막에 action-value function을 approximate하는 function approximator를 하나 쓰겠다고 하는데, 당연히 이게 Neural Network이다.

 

제시된 Q-Network는, 다음과 같은 loss를 minimize하도록 훈련시킬 수 있다.

 

 

간단하게 설명하자면, sampling된 experience에 대한 Expectation 식이고, 뒤는 Q-Network의 타겟인 y에서 현재의 Q 추정치를 빼준 것이다.

 

Gradient를 위해 theta에 대해서 미분해주면,

 

 

다음과 같은 gradient를 얻게 된다. 논문에 나오는 수식은 이게 전부이다. 식을 잘 들여다보면, 약간 이상해보이는 부분이 두 개 있다. Expectation 아래에 붙은 p(.) 이랑, max 안에 있는 theta_(i-1) 부분이다.  

 

여기서 DQN의 핵심 개념 두 개가 나오는데, Experience Replay와 Frozen target network이다.

 

 

---

 

 

Experience Replay

 

위의 식에서 이 부분은 무엇에 대한 Expectation일까? 저 p는 empirical distribution 이다. experience들을 모아놓은 finite replay buffer에서 draw 하겠다는 것이다. 

 

우리의 replay buffer는,

 

 

그러면 우리의 empirical distribution p는,

 

 

이렇게 될 것이다. 

 

그러면 아까의 loss minimization objective를 experience replay를 통해 다음과 같이 approximation 할 수 있다.

타겟인 y는 위의 식과 같다.

 

 

 

Breaking Correlation and going i.i.d

 

Experience Replay를 왜 하냐면, Neural Network이기 때문에 stochastic gradient descent를 쓰고 싶은데, sgd를 쓰려면 i.i.d 여야하는 assumption이 필요하다.

 

 

그런데 online sampling을 하면 (agent가 연속적으로 environment와 상호작용해서 경험을 얻어나가면), 이 i.i.d가 깨질 수 있다. 아래를 보자.

 

어차피 계속 그 나물에 그 밥으로 계속 조금씩 조금씩 경험해나아가는거라서 highly correlated 될 수 있다는 것이다. 그래서 이 correlation을 깨고, 이 experience들을 여러 개 replay buffer에 넣어놓고, 뽑아서 쓰겠다는 것이다. 

 

 

Reusing Experience

 

당연하겠지만 replay가 없으면 각 state transition을 한 번 업데이트할 때 딱 한 번만 쓰고 더 이상 사용하지 않게 된다. 하지만 실제로는 agent가 environment와 상호작용하는 비용이 클 수도 있기 마련이다. Replay는 이에 대비해 experience를 buffer에 저장해놓고 여러 번 사용할 수 있게 해준다.

 

 

 

Frozen Target Network

 

 

식을 잘 보면, max가 있는 target 부분에는 theta_(i-1)을 쓰고, 현재 Q estimate에는 theta_i 를 쓴다. 타겟 네트워크는 업데이트 이전의 네트워크 파라미터를 사용하는 것이다. 

 

 

Problem: Moving Target

 

그냥 일반적인 Q-learning인데, Q-function만 Neural Network (NN이라고 하겠다 앞으로) 로 대체했다고 생각해보자. 그러면 Q 뒤에 given theta term만 넣어주면 된다.

 

우리의 1-step target은

 

이렇게 될 것이고, theta update는 gradient를 사용해서,

 

 

이렇게 될 것이다. 이 부분을 잘 보면, max 부분인 target이, 지금 업데이트 되고 있는 theta와 동일하다. 다시말해, gradient update에서 theta가 조금 움직이면, target도 동일한 theta에 의존하기 때문에 같이 움직여버린다. 

 

이렇게 되면 high variance를 가지는, 굉장히 noisy한 gradient를 가지게 될 것이고, 학습이 느려지고, diverge 해버릴 수도 있고, gradient descent에서 gradient들이 계속 여러 다양한 방향을 가리킬 수도 있고, unstable하고 unsafe한 policy들이 나오며, 온갖 안 좋은 효과들은 다 나오게 된다.

 

 

 

Frozen Target Network

 

그래서 몇 스텝 이전의 theta를 사용할 것이다. 가장 최근의 업데이트 되는 theta를 바로바로 쓰는게 아니라. 약간 이전의 parameter인 점을 나타내기 위해서 theta- 라고 표기한다.

 

이 과정은 periodically 하게 진행된다. 그래서 정해진 몇 스텝이 있다.

 

---

 

 

DQN Pseudocode

 

위의 두 개념이 DQN의 핵심 잡기술 개념이다. pseudocode를 보고 마무리하도록 하자.

---

ETC

 

얘도 epsilon-greedy로 action을 샘플링 한다.

 

epsilon-greedy에 따라 고른 친구들을 replay buffer에 넣어주면, 아래와 같은 distribution이 생긴다.

 

여기서 uniform sampling을 시행하는 것이다.