💪🏻

Double DQN

생성일

2024/07/22 02:59

태그

강화학습

작성자

Double DQN

1. Double DQN

•

Q-learning에서의 Target

◦

r+γmax⁡aQ(s′,a)r + \gamma \displaystyle \max_{a} Q(s',a)r+γamax​Q(s′,a)

▪

max⁡aQ(s′,a)\displaystyle\max_{a} Q(s', a)amax​Q(s′,a) 에서 Q(s′,a)Q(s',a)Q(s′,a)는 추정값

▪

 이 값이 실제로 가장 좋은 행동이기 때문에 높은 값을 가지는 것이 아니라, 우연히 높은 값을 가질 수 있다.

•

Q-value의 overestimation bias를 해결

◦

 target에서 action을 선택하는 부분과 선택된 action에 대해 Q-value를 구하는 과정을 별도의 Network를 사용하여 진행

•

Double DQN의 loss function

L(\theta) = [r_{t+1}+\gamma \hat Q(s_{t+1}, \displaystyle\argmax_a Q(s_{t+1}, a ; \theta) ; \hat \theta) - Q(s_t,a_t ;\theta)]^2

◦

Target에서 action 선택

▪

 θ\thetaθ를 parameter로 가지는 network

◦

Q-value 계산

▪

θ^\hat \thetaθ^을 parameter로 가지는 network

◦

동일한 행동이 두 네트워크에서 동시에 가장 큰 Q-value를 갖게 될 가능성이 낮기 때문에 overestimation 문제가 완화됨

2. Overestimation

•

Jensen의 부등식

\displaystyle E[\max_{a}Q(s',a)] \geq \max_{a}E[Q(s',a)]

•

E[Q(s′,a)]E[Q(s',a)]E[Q(s′,a)]는 무수히 많은 sample에 대해 수행한다면 실제 Q-value에 근사함.

•

즉 Jensen의 부등식에 의해 완전히 update 되지 않은 Q-value에 max 연산자를 먼저 적용하는 것은 overestimation 문제를 발생시킬 수 있음을 의미

•

s′s's′에서 가능한 행동이 총 3개가 존재하고 5개의 sample을 얻었다고 가정

◦

a1:[1.25,0.88,1.38,1.77,0.84]a2:[2.47,1.91,2.06,2.38,1.79]a3:[3.03,3.54,2.65,3.40,2.86]a_1: [1.25, 0.88, 1.38, 1.77, 0.84]  \\
a_2: [2.47, 1.91, 2.06, 2.38, 1.79] \\
a_3: [3.03, 3.54, 2.65, 3.40, 2.86]a1​:[1.25,0.88,1.38,1.77,0.84]a2​:[2.47,1.91,2.06,2.38,1.79]a3​:[3.03,3.54,2.65,3.40,2.86]

◦

max 연산자를 먼저 적용하고 mean 연산을 적용 시

▪

max:[3.03,3.54,2.65,3.40,2.86]max: [3.03, 3.54, 2.65, 3.40, 2.86]max:[3.03,3.54,2.65,3.40,2.86] 

▪

mean:3.096mean : 3.096mean:3.096

◦

mean 연산자를 먼저 적용하고 max 연산 적용 시

▪

a1:1.22,a2:2.12,a3:3.10a_1: 1.22, a_2: 2.12, a_3: 3.10a1​:1.22,a2​:2.12,a3​:3.10

▪

max:3.10max : 3.10max:3.10

3. Prioritized Replay

•

Online RL

◦

연속된 transition 사이의 temporal correlation 문제 유발

◦

드물게 발생하는 experience에 대해 그 가치가 높더라도 폐기

◦

DQN에서 replay buffer를 사용하여 문제 완화

•

Replay buffer

◦

중요한 sample과 그렇지 않은 sample이 추출될 확률이 동일

◦

중요한 sample에 가중치를 부여하여 더 자주 sampling 되도록 조치할 필요가 있음

•

Sample의 중요성?

◦

TD error의 크기로 평가

3. Prioritizing with TD error

•

Model-based

◦

Value iteration

▪

Value 변화량이 큰 상태부터 먼저 update

▪

중요한 변화가 다른 state value 계산에 즉시 반영

▪

비동기적 방식에서 효과적

•

Model-free

◦

성공에 대한 transition보다 실패에 대한 transition이 더 많이 등장

◦

특정 시도에 대해 성공적인 결과로 이어진다면 value 차이가 매우 커짐

•

TD-error 기반 가중치 계산

•

문제점

◦

Replay buffer의 전체 transition을 update 하는 것은 비효율적이므로 mini batch로 sampling된 transition에 대해서만 priority update

▪

초기 sampling 된 transition 중 TD-error가 큰 transition이 자주 선택되고 나머지는 무시될 가능성 존재

▪

Sample 다양성의 감소로 인해 과적합 가능

◦

Priority가 계속 변화하기 때문에, transition sampling을 진행하는 분포가 계속 변화하여 bias 발생

•

Sample 다양성에 관한 문제 해결

◦

Stochastic sampling prioritization을 사용

◦

Prioritization 확률

▪

 P(i)=pα∑kpkαP(i) = \frac {p^\alpha}{\sum_k p^{\alpha} _{k}}P(i)=∑k​pkα​pα​

▪

α\alphaα의 값이 1에 가까울수록 TD-error를 바탕으로 선택될 비율을 높임 

▪

α\alphaα=0이라면 prioritization을 전혀 고려하지 않는 경우임 

◦

α\alphaα : 얼마나 prioritization을 사용할 것인지에 대한 hyperparameter

•

Sampling 분포 문제 해결

◦

Importance sampling weights 사용

◦

importancee sampling weights

▪

wi=(1N 1P(i))βw_i = (\frac{1}{N} \ \frac{1}{P(i)})^\betawi​=(N1​ P(i)1​)β

▪

 β=1\beta=1β=1 : 완벽한 보정

▪

Stability를 위해 weight에 1max⁡kwk\frac{1}{\displaystyle \max_{k} w_k}kmax​wk​1​을 곱하여 진행

◦

Update 시 자주 sampling 되는 sample의 영향력을 줄인다.

Double DQN

Double DQN

1. Double DQN

2. Overestimation

3. Prioritized Replay

3. Prioritizing with TD error

4. Double DQN with prioritized replay pseudo code