I have implemented DQN algorithm and wonder why during testing, the best performance is achieved by a policy from about 300 episode, when mean Q values converge at about 800 episode?

• Mean Q-values are calculated on a fixed set of states by taking mean of max Q-values for each state.
• By convergence I mean that the plot of mean Q-values converge to some level (those values does not increase to infinity).

It can be seen in here (page 7) that mean Q-values converge and average rewards plot is quite noisy. I get similar results and in tests, the best policy is where the peaks are during training (average reward plot). I don't understand why don't I get better average scores over time (and better policies) when Q-values converge.

More concretely, suppose that you can take one of two actions $$\{ a_1, a_2\} = \mathcal{A}$$ in each state $$s \in \mathcal{S}$$. Let's say that you pick $$s_1, s_2$$ to calculate the average of the maximum Q-value. Without loss of generality, suppose that the action associated with the highest Q-value in these states is $$a_2$$. If your policy is the greedy policy with respect to the state-action value function, then your policy will choose $$a_2$$ in $$s_1$$ and $$s_2$$. If all Q-values $$\hat{q}(s_1, a_1)$$, $$\hat{q}(s_1, a_2)$$, $$\hat{q}(s_2, a_1)$$ and $$\hat{q}(s_2, a_2)$$ increase (or even decrease) but their relative order remains the same (i.e. $$\hat{q}(s_1, a_2) > \hat{q}(s_1, a_1)$$ and $$\hat{q}(s_2, a_2) > \hat{q}(s_2, a_1)$$, from episode 300 onwards), the greedy policy also remains the same.