DDQN(Double DQN)

Deep Reinforcement Learning with Double Q-learning

0. Abstract

▶ Q-learning algorithm(ex. DQN)은 특정 조건에서 action-value를 overestimate하는 것으로 알려짐

→ 그러나 실제로 그러한 overestimate가 일반적인지, performance에 해를 끼치지는 않는지, 예방은 가능한지는 이전에 알려지지 않은 상태

▶ DQN algorithm이 일부 game에서 상당한 overestimate를 겪고 있음

▶ 해당 논문은 tabular setting으로 도입된 Double Q-learning에 대한 아이디어가 large-scale fucntion approximation과 함께 작동하도록 일반화될 수 있음을 보여줌

→ DQN algorithm에 특정 adaptation을 제안하고 resulting algorithm이 가정된 대로 관찰된 overestimation를 줄일 뿐만 아니라 이것이 여러 game에서 훨씬 더 나은 성능으로 이어진다는 것을 보여줌

 

---

1. Introduction

(1) DQN problem

▶ RL의 목표는 cumulative future reward signal을 optimize하여 sequential decision problems에 대한 좋은 policy를 학습 하는 것

▶ Q-learning은 널리 사용되는 algorithm 이지만 underestimated values보다 overestimated values를 더 선호하는 경향이 있는 estimated action value에 대한 maximize 단계를 포함하기 때문에 때때로 비현실적으로 높은 action value를 학습하는 것으로 알려짐 

 

(2) open question about overestimation

▶ overestimate가 발생하면 실제로 성능에 부정적인 영향을 끼치는 지는 열린 질문

▶ 지나치게 낙관적인 value estimate가 반드시 그 자체로 문제가 되는 것은 아님

→ 모든 값이 균일하게 더 높으면 상대적인 action 설정이 유지되고 resulting policy가 더 나빠질 것으로 기대되진 않음

→ 또한 때로는 낙관적인 value estimate가 더 좋은 경우도 존재(ex. optimism in the face of uncertatinty)

▶ 그러나 overestimation가 균일하지 않고 더 배우고자 하는 state에 집중되지 않으면 resulting policy의 품질에 부정적인 영향을 미칠 수 있음 

 

(3) Double Q-learning

▶ tabular setting에서 처음 제안된 Double Q-learning algorithm의 아이디어가 neural network를 포함한 function apprixomation와 함께 작동하도록 일반화될 수 있음을 보여줌

▶ Double Q-learning algorithm은 더 정확한 value estimation을 산출할 뿐만 아니라 여러 게임에서 더 높은 성능을 보임

→ 이는 DQN의 overestimate가 실제로 더 나쁜 policy로 이어지며 이를 줄이는 것이 유익하는 것을 보임

 

---

2. Background

(1) action-value function

▶ sequential decision problem를 해결하기 위해 각 action의 optimal value에 대한 estimatation을 학습할 수 있으며, 이는 해당 action을 취하고 그 후 optimal policy를 따를 때 예상되는 sum of future reward로 정의

▶ 주어진 policy π에서 state s에서 action a의 true value of action은 다음과 같음

// γ ∈ [0, 1]: immediate & later rewards에 대한 중요성을 나타내는 discount factor

 

action-value function

 

▶ optimal policy로 각 state에서 max value의 action을 선택함으로써 도출되는 optimal value는 다음과 같음 

 

optimal action-value function

 

▶ optimal action values에 대한 estimate는 TD의 한 형태인 Q-learning을 사용하여 학습 가능

▶ 흥미로운 문제는 너무 크기 때문에 모든 states의 모든 action values를 개별적으로 학습할 수 없음

→ 대신 parameterized value function Q(s, a; θt)를 학습

▶ state s_t에서 action을 취하고 immediate reward r_(t+1)과 결과 state s_(t+1)을 관찰한 후, parameter에 대한 standard Q-learning update는 다음과 같다. 

 

standard Q-learning update

▶ 여기서 α는 scalar step size이고, target Y^Q_t는 다음과 같이 정의

 

target

 

▶ 이 update는 target value Y^Q_t를 향해 current value Q(S_t, A_t; θt)를 update하는 SGD와 유사

 

(2) Deep Q Network

▶ 주어진 state s에 대해 action-value Q(s, a; θ)의 vector를 출력하는 multi-layered neural network

// θ: network parameters

▶ n-dimensional state space & m개의 action을 포함하는 action space의 경우, neural network는 R^n부터 R^m까지의 함수

▶ DQN algorithm의 주요 오소는 target network와 experience replay의 사용

▶ parameter θ가 있는 target network는 online network에서 θ가 τ step마다 복사되어 θ^-_t = θ_t가 되고 다른 모든 step에서는 고정된다는 점을 제외하고 online network와 동일 

DQN target Y

 

2021.12.11 - [RL] - DQN(Deep Q-learning)

DQN(Deep Q-learning)

 

(3) Double Q-learning

▶ standard Q-learning & DQN에서의 max 연산자는 동일한 value를 사용하여 action을 선택하고 평가

이렇게 하면 oversetimated value를 선택할 가능성이 높아져 overestimated value가 과도하게 추정

▶ 이를 방지하기 위해 evaluation에서 selection을 분리하는 것이 아이디어

 

▶ 기존 Double Q-learning에는 두개의 set of weights θ & θ'이 있도록 두개의 value function 중 하나를 update하기 위해 각 experience를 무작위로 할당하여 두 value function을 학습

▶ 각 update에 대해 하나의 weight set는 greedy policy를 결정하는데 사용되고 다른 하나는 해당 value를 결정하는데 사용 

▶ 명확한 비교를 위해, 먼저 Q-learning에서 selection & evaluation를 풀어서, 방정식을 다음과 같이 다시 작성 가능

 

Q-learning target Y

Double Q-learning target Y

 

▶ argmax에서 action 선택은 여전히 online weight θ 때문

→ 이는 Q-learning에서와 같이 θ_t로 정의된 현재 value에 따라 greedy policy 값을 여전히 estimate 한다는 것을 의미

▶ 그러나 이 policy의 value를 공정하게 evaluate하기 위해 두번째 weight set θ'_t를 사용

→ 이 두번째 weight set는 θ와 θ'의 역할을 switching 하여 대칭적으로 update 가능 

 

(4) Overoptimism due to estimation errors

▶ Q-learning의 overestimation은 action value에 [-e, e] interval 내, 균일하게 random distributed errors가 포함되어 있으면 각 target이 최대 γ∈m-1/m+1까지 overestimate

// m: number of actions

- Thrun & Schwartz: overestimation이 sub-optimal policy로 이어지는 예를 제시하고 function approximation을 사용할 때 small problem에서 나타남을 보임

- van Hasslet: tabular representation을 사용하는 경우에도 environmental noise가 overestimate로 이어진다고 주장 

 

▶ 해당 논문에서는 overestimation이 environmental noise, function approximation, non-stationarity, or any other sources 여부에 관계 없이 모든 종류의 estimation errors가 상향 편향을 유발할 수 있음을 증명

→ 실제로, 어떤 방법이던 처음에는 true values를 알 수 없다는 사실 때문에 학습 중에 약간의 부정확성이 발생

 

---

3. Double DQN; DDQN

▶ Double Q-learning의 개념은 target의 max 연산을 action selection과 action evaluation으로 분해하여 overestimate를 줄이는 것

▶ 완전히 분리되지는 않았지만 DQN architecture의 target network는 추가 network를 대입하지 않고도 두번째 value function에 대한 후보를 제공

▶ 따라서 online network에 따라 greedy policy를 evaluate 하지만 target network를 사용하여 value를 estimate할 것을 제안 

▶ Double DQN = Double Q-learning + DQN

→ update는 DQN과 동일하지만 target Y^DQN_T를 다음으로 대체

 

DDQN target Y

 

▶ 현재 greedy policy의 evaluation를 위해 두번째 network θ'_t의 weight를 target network θ_t의 weight로 대체

▶ target network에 대한 update는 DQN에서 변경되지 않고, online network의 주기적 복사본으로 유지

 

---

4. Experiments

(1) empirical results

▶ DQN의 overestimate를 분석하고 DDQN이 value accuracy와 policy quality에서 더 향상됨

▶ research goal: 고정된 hyperparameter set가 있는 single algorithm이 interaction과 별도로 raw pixel만을 input으로 받아 각 game을 플레이하는 방법을 배우는 것 

→ input이 high-dimensional 할 뿐만 아니라, visual과 mechanics가 gmae마다 크게 다른 까다로운 환경

▶ 결국 좋은 solution은 learning algorithm에 크게 의존해야함

→ tuning에만 의존하여 domian을 overfit 하는 것은 실제로 실현 불가능

 

▶ network architecture은 3개의 convolution layer, fully-connected hidden layer로 구성된 CNN

▶ network는 마지막 4개의 frame을 input으로 받아 각 action의 action-value function을 출력

 

(2) results on overoptimism

▶ 6개의 Atari game에서 DQN(overestimate)와 DDQN metric

▶ averaged value estimates는 T = 125,000 steps의 full evaluation 단계를 사용하여 훈련 중 정기적으로 계산 

averaged value estimates

 

DQN vs DDQN

▶ ground truth averaged values(위 그래프에서 색칠된 선)는 여러 에피소드에 대해 가장 잘 학습된 policy를 실행하고 실제 cumulative rewards를 계산해 얻음 

→ 만약 overestimate가 없으면 이러한 값이 일치할 것으로 예상

▶ DDQN이 더 정확한 estimate를 생성할 뿐만 아니라 더 나은 policy를 생성한다는 의미

▶ DDQN을 사용하면 학습이 훨씬 더 안정적

→ Q-learning의 overoptimism 때문에 불안정이 발생

 

DQN < DDQN

 

(3) quality of the learned policies

▶ overoptimism이 학습된 policy quality에 항상 부정적인 영향을 미치지는 않음

→ DQN은 policy를 overestimate 했음에도 불구하고 Pong에서 optimal behavior로 동작

▶ 그럼에도 overestimate를 줄이는 것은 학습의 안정성에 상당한 이점이 될 수 있음 

▶ DDQN과 DQN의 유일한 차이점은 Y^DQN 대신 Y^DoubleDQN_t를 target으로 사용하는 것

 

(4) robustness to Human starts

▶ 이전 evaluation에서는 고유한 특정 starting point가 있는 deterministic games에서 학습자가 일반화할 필요 없이 sequences of action을 기억하는 방법을 잠재적으로 배울 수 있다는 우려가 존재

→ 성공적일지는 몰라도 solution이 특별히 강력하지는 않을 수 있음

▶ 따라 다양한 starting point에서 agent를 테스트함으로써 발견된 solution이 잘 일반화되는지 테스트 가능하며 학습된 policy에 대한 도전적인 testbed를 제공 가능 

→ 인간 전문가의 trajectory에서 각 game에 대해 sampling된 100개의 starting point를 획득하고 각각에서 evaluation episode를 시작

▶ 각 agent는 starting point 이후에 cumulative reward에 대해서만 evaluate

→ 이 evaluate를 위해 tuned version of DDQN(overestimate를 줄이기 위한 target network로의 복사 주기 증가, exploration과 evaluation에서의 e value 감소, network top layer에 있는 모든 action-value에 대해 single shared bias를 사용)을 포함

 

DQN < DDQN < DDQN(tuned)

▶ tuned version of DDQN은 더 좋은 performance와 result를 보임 

 

---

5. Discussion

(1) five contributions

▶ 첫번째, 학습의 고유한 estimation errors로 인해 Q-learning이 large-scale problem에서 overoptimistic함을 보임

▶ 두번째, Atari game에 대한 value estimates를 분석하여 이러한 overestimate가 이전에 인정된 것보다 실제로 더 일반적이고 심각하다는 것을 확인

▶ 세번째, Double Q-learning을 대규모로 사용하여 이러한 overoptimism을 성공적으로 줄여 더 안정적이고 신뢰할 수 있는 학습을 가져올 수 있음을 보임

▶ 네번째, 추가 network나 parameter 없이 DQN algorithm의 기존 architecture와 neural network을 사용하는 Double DQN이라는 특정 구현을 제안

▶ 마지막, Double DQN이 더 나은 policy를 찾아 Atari 2600 domain에서 더 좋은 결과를 보임