Double Q-Learning

Definition

Q-Learning takes the action with the highest value, which tends to overestimate the value of actions (maximization bias) in the early stages of learning, slowing the convergence to $q_{\ast }(s,a)$.

Double Q-learning uses two Q-value functions to overcome this problem: one for action selection and another for value evaluation.

Algorithm

1. Initialize $\forall s\in \mathcal{S},a\in \mathcal{A}(S)$, $Q_1(s,a)$, and $Q_2(s,a)$ arbitrarily, and $Q_1(\text{terminal},\cdot )=0$ and $Q_2(\text{terminal},\cdot )=0$.
2. Repeat for each episode:
   1. Initialize $S$.
   2. Repeat for each step of an episode until $S$ is terminal:
      1. Choose an action $A$ from the initial state $S$ using policy derived from $Q_1$ and $Q_2$ (e.g. $ϵ$-greedy in $Q_1+Q_2$).
      2. Take the action $A$ and observe a reward $R$ and a next state $S^{\prime }$.
      3. With probability $0.5$: $Q_1(S,A)\leftarrow Q_1(S,A)+\alpha [R+\gamma Q_2(S^{\prime },\underset{a}{\mathrm{argmax}}{Q}_1(S^{\prime },a))-Q_1(S,A)]$ else: $Q_2(S,A)\leftarrow Q_2(S,A)+\alpha [R+\gamma Q_1(S^{\prime },\underset{a}{\mathrm{argmax}}{Q}_2(S^{\prime },a))-Q_2(S,A)]$
      4. Update $S\leftarrow S^{\prime }$

Examples

Q-Learning initially learns to take the left action much more often than the right action despite the lower true state-value of the left. Even at asymptote, it takes the left action more than optimal (5%). In contrast, double Q-learning is unaffected by maximization bias.