Double Q-Learning

Topics: Reinforcement Learning

Concept

Double Q-Learning is an improvement of the Q-Learning algorithm. The main motivation behind the idea of Double Q-Learning is the problem of Overestimation in Q-Learning. In the update equation of Q-Learning, the maximum over all actions is taken. This maximization leads to the overestimation of Q-values, and since Q-Learning is a boot-strapping algorithm (learns estimates from estimates), this overestimation causes the agent to learn a poor policy.

The Double Q-Learning algorithm uses 2 tables of Q-value estimates $Q_{A}$ and $Q_{B}$. The idea is that, the table that is being updated is used to select the maximizing action, while the other table is used to evaluate the action. The tables are updated interchangeably ($0.5$ probability).
In other words, in order to update $Q_{A}$, the maximizing action is selected from $Q_{A}$ and is evaluated using $Q_{B}$. On the other hand, in order to update $Q_{B}$, the maximizing action is selected from $Q_{B}$ and is evaluated using $Q_{A}$.

After training, $Q_{A}$ is used as the unbiased estimator.

Pseudocode

Below is the pseudocode of the Double Q-Learning algorithm (1).

References

1. https://medium.com/data-science/double-deep-q-networks-905dd8325412