Exercise 5.5.4
Maximization bias: when overestimation helps, bias parameter mu
It is well-known that Q-learning is prone to overestimation as it uses its own estimate in the update rule. However, overestimation can be helpful in certain environments. For example, consider the simple transition diagram in Figure 1, starting from state \(A\) and having only two actions – left and right. The rewards for both actions are deterministic. The left action transitions to state \(B\) where there are two transitions to the terminal state (grey square) with a random reward, selected at random. The two possible rewards are drawn from either a uniform distribution \(\mathcal{U}(-1, 1)\) plus a bias parameter \(\mu\) or a normal distribution \(\mathcal{N}(0,1)\) plus the same bias parameter \(\mu\) as for the other reward. There is no discount (\(\gamma = 1\)). The right action from state \(A\) also terminates the environment, with a reward of 0.
-
(a) What is \(Q(A, \text{left})\)?
-
(b) For what values of \(\mu\) is the overestimation from Q-learning helpful in solving this environment? For what values is it hurtful? For what values does it make no difference?
Based on Sutton & Barto (2018), Reinforcement Learning: An Introduction, 2nd ed., Example 6.7. Licensed CC BY-NC-ND 2.0.