07. Deep Q-Learning

• 참고: Model-free Control

Value Function Approximation

SARSA와 Q-learning과 같은 model-free prediction 기법은 model의 size가 작은 경우에는 비교적 잘 동작한다. 하지만, 만약 바둑과 같이 state-action pair가 셀수없이 많은 문제에는 어떨까? 기본적으로 SARSA와 Q-learning은 직접 방문한 state-action pair에 대해서만 value update가 이루어진다. 즉, 무수하게 많은 경험을 얻지 않는 한, action-value function이 모든 state-action에 대해 제대로 update되는 것은 불가능하다.

이러한 관점에서 등장한 방법론이 value function approximation이다. 이는 value function을 어떤 parameter의 함수로 가정하고, MC 또는 TD learning을 통해 적절한 parameter를 찾아나가는 것이다.

$$\hat{v}(s,\mathbf{w})\approx v_{\pi }(s)\text{or}\hat{q}(s,a,\mathbf{w})\approx q_{\pi }(s,a)$$

이러한 방법을 사용하면 우리가 일부의 경험만을 토대로 관찰하지 않은 state의 value function에 대해서도 어느정도 알아낼 수 있다.

핵심은 generalization이다. Table 방식은 직접 방문한 칸만 채울 수 있지만, 함수 근사는 비슷한 state끼리 parameter를 공유하기 때문에 한 번도 보지 못한 state에도 학습된 패턴을 적용할 수 있다. 바둑처럼 state가 사실상 무한한 문제에서도 RL이 동작하는 이유가 바로 이 일반화 능력에 있다.

Approximation 함수의 경우 다양한 알고리즘들이 가능하나, 가장 좋은 효과를 거둔 것은 deep learning 모델을 이용한 approximation 이다.

Deep Reinforcement Learning

Deep reinforcement learning은 deep learning 모델을 이용해 value function approximation을 하는 RL 알고리즘을 통칭한다.

일반적으로 value function, policy, model을 한꺼번에 optimize하는 end-to-end 방법론이며, 실제 value function(의 추정값)과 estimation의 차이를 이용해 parameter $w$를 업데이트하는 방식으로 학습이 진행된다.

Q-value에 대한 approximation model은 input이 (state, action) pair 또는 state만을 가질 수도 있다. 이 경우, output은 각각 input에 대한 Q-value (single output) 또는 해당 state에서 가질 수 있는 action들의 q-value들 (multi output)이 된다.

Approximate the Action-value Function

Action-value function에 대해 approximation을 진행한다고 하자.

$$\hat{q}(s,a,\mathbf{w})\approx q_{\pi }(s,a)$$

이 경우, SGD 등을 이용하여 parameter $w$에 대한 update가 필요하다. 이 때의 loss function $\mathcal{L}(w)$은 다음과 같이 정할 수 있다.

$$\mathcal{L}(w)={\mathbb{E}}_{\pi }[(q_{\pi }(s,a)-\hat{q}(s,a,w){)}^2]$$

위 식을 통해 gradient를 구하면 다음과 같다.

$$-\frac{1}{2}\frac{\partial \mathcal{L}(w)}{\partial w}=(q_{\pi }(s,a)-\hat{q}(s,a,w)){\nabla }_w\hat{q}(s,a,w)$$ $$\Rightarrow \Delta w=\alpha (q_{\pi }(s,a)-\hat{q}(s,a,w)){\nabla }_w\hat{q}(s,a,w)$$

그런데 위 update 식에는 결정적인 문제가 있다. 우변의 $q_{\pi }(s,a)$, 즉 우리가 정답으로 삼아야 할 true value를 실제로는 알지 못한다는 것이다. 만약 안다면 애초에 학습할 필요도 없다. 따라서 이 자리를 현재 추정값으로 직접 만들어낸 target으로 메워야 하는데, 여기서 supervised learning과 RL이 갈라진다.

Deep Q-learning

Deep Q-learning 모델은 우리가 알지 못하는 true Q-value $q_{\pi }(s,a)$를 Q-learning의 TD target으로 간주한 모델이다. 이 때, Q-value를 추정하는 모델을 Q-network라고 한다.

즉, 정답 자리에 Q-network 스스로가 만든 추정값($R+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime },w)$)을 끼워 넣는다. 이렇게 추정값으로 추정값을 학습시키는 것을 bootstrapping이라 한다. 학습 신호를 외부 정답 없이 자급자족할 수 있다는 점에서 강력하지만, 동시에 아래에서 볼 학습 불안정의 근본 원인이기도 하다.

$$\Delta w=\alpha (R+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime },w)-\hat{q}(s,a,w)){\nabla }_w\hat{q}(s,a,w)$$

Stability Issues with Deep RL

Deep Q-learning 모델에 대해서 위 식으로 바로 학습을 진행하면 학습이 무척 불안정하게 진행된다. 이러한 현상은 크게 세 가지 이유가 있다.

1. Input data가 non-iid하다.

   • Agent의 experience는 time-series data의 성격을 띄므로 input간 correlation이 매우 높다.

2. Q-value의 작은 변화에도 policy가 크게 바뀔 수 있다.

   • Q-network의 parameter가 update되면, 전체 Q-value가 바뀌는 효과가 나타난다. 이로 인해, policy가 수렴하지 못하거나, 또는 sample의 분포가 극단적으로 바뀔 수도 있다.

3. Reward 및 Q-value의 크기가 예상보다 클 수 있다.

   • 예상보다 큰 Q-value 또는 reward가 들어오게 되면, exploding gradient 현상이 발생하여 학습이 불안정해질 수 있다.

특히 1번과 2번이 결합되면 문제가 심각해진다. 함수 근사(generalization) + bootstrapping(추정값으로 target을 만듦) + off-policy(과거 경험으로 학습)의 세 요소가 동시에 작용하면 학습이 발산하기 쉬운데, 이를 deadly triad라 부른다. 아래의 세 가지 trick은 각각 이 불안정 요인을 하나씩 완화하는 처방으로 이해하면 좋다.

Experience Replay

우선 input data가 non-iid하여 생기는 학습의 불안정 및 local optimum 수렴을 방지하기 위해 replay memory $\mathcal{D}$에 agent의 experience를 저장해두고, 해당 replay memory에서 batchsize 만큼의 sample을 random하게 골라내어 학습에 사용한다. 이러한 방식을 experience replay라고 한다.

시간순으로 들어오는 연속된 경험은 서로 강하게 correlated 되어 있어, 그대로 학습하면 직전 몇 step의 상황에 과적합되기 쉽다. Random sampling은 이 시간적 상관관계를 끊어 mini-batch를 iid에 가깝게 만든다. 덤으로, 한 번 겪은 경험을 버리지 않고 여러 번 재사용하므로 sample efficiency도 크게 올라간다.

Experience replay는 off-policy 알고리즘에서만 사용할 수 있다.

1. Agent가 transition을 진행할 때마다, experience $(s_t,a_t,r_{t+1},s_{t+1})$를 replay memory $\mathcal{D}$에 저장

   • 만약 $\mathcal{D}$의 크기가 가득찬 경우, 가장 오래된 experience를 삭제

2. $\mathcal{D}$로부터 random sampling을 통해 mini-batch 구성

3. 아래와 같이 학습 진행

   $$\mathcal{L}(w)={\mathbb{E}}_{s,a,r,s^{\prime }\sim \mathcal{D}}\left[{\left(R+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime },w)-\hat{q}(s,a,w)\right)}^2\right]$$

Fixed Target Q-network

앞서 본 loss를 다시 보면, 정답 역할을 하는 TD target도 학습 대상인 prediction도 모두 같은 parameter $w$로 계산된다. 즉 $w$를 한 번 update할 때마다 쫓아가야 할 target 자체가 같이 움직인다. 자기 그림자를 밟으려 뛰는 것과 비슷해서, 학습이 진동하거나 발산하기 쉽다.

이를 막기 위해, TD target을 계산하는데 사용되는 target Q-network를 일정 학습 기간동안은 고정시켜놓는 방법을 사용한다. Target을 잠시 멈춰 세워 고정된 과녁으로 만든 뒤 그것을 향해 학습하고, 주기적으로만 과녁을 현재 위치로 옮기는 것이다.

1. Target Q-network의 parameter를 현재 Q-network의 값 $w$으로 고정한다. 고정된 parameter를 $w^{-}$라고 하자.

   $$R+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime },w^{-})$$

2. Fixed target Q-network를 true로 삼고 학습 진행

   $$\mathcal{L}(w)={\mathbb{E}}_{s,a,r,s^{\prime }\sim \mathcal{D}}\left[{\left(R+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime },w^{-})-\hat{q}(s,a,w)\right)}^2\right]$$

3. 주기적으로 $w^{-}$ update: $w^{-}\leftarrow w$

Reward Clipping

Q-value가 너무 커지지 않도록 reward를 $[-1,1]$과 같이 특정 범위 내로 제한하는 reward clipping 방법이 있다. 이를 통해 exploding gradient 현상을 방지할 수 있다.

하지만, 이는 reward의 크기를 제대로 구별하지 못해 학습이 제대로 진행되지 못할 가능성이 있으므로 tuning을 통해 적절한 범위를 찾는 것이 중요하다.

Double DQN

앞서 본 experience replay, fixed target, reward clipping은 모두 학습의 안정성을 다루는 처방이었다. 그런데 DQN에는 안정성과 별개로, target을 만드는 방식 자체에서 비롯되는 구조적인 편향(bias) 문제가 하나 더 있다. 이를 바로잡는 것이 Double DQN이다 (van Hasselt et al., 2015).

Maximization Bias

DQN의 TD target을 다시 보자.

$$Y^{\text{DQN}}=R+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime },w^{-})$$

여기서 $\max$ 연산이 문제의 핵심이다. Q-network의 추정값 $Q(s^{\prime },a^{\prime },w^{-})$는 참값 $q_{\pi }(s^{\prime },a^{\prime })$에 학습 도중의 noise가 더해진 값이다. 이 noisy한 추정값들 중 최댓값을 고르면, 우연히 위쪽으로 튄 추정값이 선택될 확률이 높아진다. 즉, 선택(어떤 action이 최선인가)과 평가(그 action의 값이 얼마인가)를 같은 추정값으로 한꺼번에 처리하기 때문에, 추정 오차가 0 평균이더라도 max를 거친 target은 체계적으로 참값보다 커지는 쪽으로 치우친다.

직관적인 예: 모든 action의 참 Q-value가 똑같이 0인 state를 생각하자. 추정값에 $+$, $-$ 방향의 noise가 무작위로 섞여 있어도, $\max$는 그중 가장 크게 양으로 튄 값을 골라낸다. 따라서 target은 0이 아니라 양수가 되고, 이 과대평가가 bootstrapping을 타고 이전 state들로 계속 전파된다.

이 현상을 maximization bias(또는 overestimation bias)라 한다. 단순히 값을 부풀리는 데 그치지 않고, action마다 부풀려지는 정도가 달라 잘못된 action을 최선으로 오인하게 만들 수 있어 policy의 질을 떨어뜨린다.

Decoupling Selection and Evaluation

해결의 아이디어는 action을 고르는 network와 그 action의 값을 평가하는 network를 분리하는 것이다. 한쪽이 어떤 action을 과대평가했더라도, 독립적인 다른 network가 그 action을 평가하면 같은 방향으로 똑같이 부풀려질 이유가 없으므로 bias가 상쇄된다. 이것이 원래 tabular 환경에서 제안된 double Q-learning의 핵심이다.

DQN은 이미 online network($w$)와 target network($w^{-}$)라는 두 개의 network를 가지고 있으므로, 별도의 network를 추가할 필요 없이 이 둘을 selection과 evaluation에 나눠 쓰면 된다.

기존 DQN target은 사실 다음과 같이 풀어쓸 수 있다. 선택도 평가도 모두 $w^{-}$가 담당한다.

$$Y^{\text{DQN}}=R+\gamma Q(s^{\prime },\arg \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime },w^{-}),w^{-})$$

Double DQN은 여기서 action 선택만 online network $w$로 넘긴다.

$$Y^{\text{DoubleDQN}}=R+\gamma Q(s^{\prime },\arg \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime },w),w^{-})$$

즉, “어떤 action이 최선인가”는 현재 학습 중인 online network $w$가 정하고, “그 action의 값이 얼마인가”는 고정된 target network $w^{-}$가 평가한다. 두 추정의 noise가 독립적이므로, 우연히 한 network에서 과대평가된 action이 다른 network에서도 똑같이 과대평가될 가능성이 낮아져 maximization bias가 완화된다.

정리

• 구현 부담이 거의 없다. Fixed target Q-network 구조를 그대로 쓰면서 target 계산의 한 줄, 즉 max를 취하는 부분만 위 식으로 바꾸면 된다. network 추가나 별도 hyperparameter도 필요 없다.
• DQN의 다른 trick들(experience replay, fixed target, reward clipping)이 학습의 불안정성을 다룬다면, Double DQN은 target의 편향을 다룬다. 서로 보완 관계이므로 함께 쓴다.
• 원 논문에서는 Atari 벤치마크에서 DQN의 Q-value 과대평가가 실제로 관찰되며, Double DQN이 이를 줄여 여러 게임에서 더 좋은 policy를 학습함을 보였다.