Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 35

The maximisation bias of Q-learning

State A offers right (reward 0, the episode ends) and left (reward 0, then state B). From B every one of \(n\) actions ends the episode with a random reward \(\mathcal N(\mu,\sigma^2)\) with \(\mu=-0.1\), so going left is worth \(-0.1\) and is a mistake. Q-learning bootstraps from \(\max_bQ(B,b)\), the maximum of \(n\) noisy estimates, which is above the true \(-0.1\) on average (\(\mathbb E\max\ge\max\mathbb E\)); so it prefers left for a long time. Double Q-learning keeps two tables and evaluates the action chosen by one with the other, which removes the bias. The upper plot is the fraction of runs that go left; the lower plot is the value each method assigns to state B (the true value is \(-0.1\)).

Actions at B n

Reward noise σ

Step size η

Exploration ε

Episodes

Runs averaged

Try these

Both methods use \(\gamma=1\), tables initialised at 0, \(\epsilon\)-greedy actions with random tie-breaking, and the same random rewards in each run. The double Q-learning agent acts greedily on \(Q_1+Q_2\) and updates one of the two tables, chosen by a fair coin, with the other table evaluating the action chosen by the first. With only two actions at \(A\), \(\epsilon\)-greedy takes the wrong action with probability \(\epsilon/2\) even when the values are right (the dashed line).

In the lecture notes