🦾

Double DQN

생성일

2024/07/22 02:59

최종 수정일

2025/11/11 05:42

태그

강화학습

작성자

1. Double DQN

•

Target in Q-learning

◦

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

▪

Since Q(s′,a)Q(s',a)Q(s′,a) is estimated value, a high value does not necessarily indicate the best action — it may simply be high by chance.

•

Addressing Q-value overestimation bias

◦

In the target calculation, the action selection and the Q-value evaluation for the selected action are calculated using separate networks.

•

Loss function

{\small 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}

◦

Action selection

▪

A network parameterized by θ\thetaθ

◦

Calculate Q-value 

▪

A network parameterized by θ^\hat \thetaθ^

◦

Since it is unlikely that the same action will simultaneously have the highest Q-value in both networks, the overestimation problem is alleviated.

2. Overestimation

•

Jensen’s inequality

\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)] approximates the true Q-value over an infinite number of samples

•

According to Jensen’s inequality, applying the max operator to Q-values that have not been fully updated can lead to overestimation.

3. Prioritized Replay

•

Online RL

◦

Causes temporal correlation problems between consecutive transitions.

◦

Even if a rare experience has high value, it may be discarded.

◦

DQN addresses this issue by using a replay buffer.

•

Replay Buffer

◦

All samples, whether important or not, have an equal probability of being selected.

◦

Therefore, it is necessary to assign higher sampling probabilities to more important samples by applying weights.

•

Importance of Samples

◦

The importance of each sample is evaluated based on the magnitude of its TD error.

3. Prioritizing with TD error

•

Model-based

◦

Value iteration

▪

Prioritize updates for states with large value changes.

▪

Important updates are immediately reflected in the value estimation of other states.

▪

Particularly effective in asynchronous methods.

•

Model-free

◦

Transitions corresponding to failures occur more frequently than those corresponding to successes.

◦

When a particular attempt leads to a successful outcome, the value difference becomes significantly large.

•

Calculate weight based on TD-error

P(i) = \frac{p_i^{\alpha}}{\sum_k p_k^{\alpha}} \quad \text{(probabilization process)}

p_i = \left| r_{i+1} + \gamma \max_a \hat{Q}(s_{i+1}, a; \hat{\theta}) - Q(s_{i}, a_{i}; \theta) \right| + \epsilon

•

Problems

◦

Updating all transitions in the replay buffer is inefficient, so priority updates only for the transitions sampled in a minibatch.

▪

Among the initially sampled transitions, those with large TD-errors are likely to be selected repeatedly, while others may be ignored.

▪

This can lead to overfitting due to a reduction in sample diversity.

◦

Since the priorities keep changing, the sampling distribution of transitions also changes over time, introducing bias.

•

Addressing Sample Diversity Issues

◦

Use stochastic sampling prioritization

◦

Prioritization probability

▪

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

▪

α\alphaα → 1 the probability of being selected increases based on the TD-error 

▪

When α\alphaα=0, prioritization is completely ignored 

◦

α\alphaα : A hyperparameter that controls how much prioritization is applied

•

Addressing Sampling Distribution Issues

◦

Use 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 : full correction

▪

For stability weights are normalized by multiplying 1max⁡kwk\frac{1}{\displaystyle \max_{k} w_k}kmax​wk​1​

◦

This reduces the influence of samples that are frequently selected during updates.

Double DQN

1. Double DQN

2. Overestimation

3. Prioritized Replay

3. Prioritizing with TD error

4. Double DQN with prioritized replay pseudo code