Exercise 5.5.4

Maximization bias: when overestimation helps, bias parameter mu

Reinforcement Learning › Exercises › Lecture 5 · Model-Free Control › 5.5 Maximization bias and double Q-learning
MediumWritten

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.

diagram
Figure 1: Transition diagram of a simple environment, which has to be solved by Q-learning. The agent starts in state \(A\) and can either go left or right. If they go left, they end up in state \(B\) where they do a random equiprobable transition to the terminal state and receive a biased reward drawn either from a normal or a uniform distribution.
  • (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.