Q learning: overtraining and converagence

I'm working on a Q learning model to autopilot Flappy Bird (follow http://sarvagyavaish.github.io/FlappyBirdRL/): it manage to reach a good score like 500 after a while of training:

But after longer training time, it doesn't score any better:

Finally it converges terribly that the bird can barely fly through the 1st pipe.

pseudo code:

Initialize Q arbitrarily
Repeat (for each episode):
Initialize S
Repeat (for each frame of episode):
A ← f(Q, S) // compute action according to Q and current state
Q(S, A) ← (1-α)*Q(S,A) + α*[reward + γ*maxQ(S',a)] // update Q(S, A)
// reward = 1 for survival, reward = -100 for death
S ← S'
until S is terminal


Here's the key updating strategy:

Q(S, A) ← (1-α)*Q(S,A) + α*[reward + γ*maxQ(S',a)]


every frame, $Q(S, A)$ update according to itself, reward of current frame and maximum Q value of next possible state: -1000 if dead, 1 if alive.

Intuitively, I believe the problem is my strategy backpropagates too shallow (or too slow): for every frame $t$, only $Q(S_{t-1}, A)$ is updated. It would takes at least $t$ episode to backpropagate until $Q(S_0, A)$ is updated. Considering randomness and reproducibility it could only takes much longer.

I try comparing my code with deep Q learning paper:

They sample random minibatch of transitions from a replay memory but for mine, I update the 1-step previous state only. And this is confusing me: how do I update Q value for $S_t$ when $S_{t+x}$ is the terminal state, whose Q value is accessible?

I guess it's in this equation but I don't understand:

Yes my intuition was right: the Q-value updating is wrong.

I shouldn't update Q-value every frame. In fact it would never affect the whole action sequence this way.

The correct updating strategy: maintain a state-sequence to record (state, action) for every frame. When it's terminal, propagate backward to update Q-value for every (state, action):

Q ← {}
state-seq ← []

for each round:
for each frame:
S ← current state
if S in Q:
if Q(S, flap) > Q(S, do-nothing):
A ← flap
else:
A ← do-nothing
state-seq ← state-seq + [S, A]

if terminal:
for [S, A] in reversed(state-seq):
if S is the 1st (closest to terminal):
Q(S, A) ← (1 - α) * Q(S, A) + α * R
else:
S' ← next state of S
Q(S, A) ← (1 - α) * Q(S, A) + α * {R + γ * max[Q(S', flap), Q(S', do-nothing)]}
state-seq ← []

α: learning rate
γ: discount factor
R: reward
+1 for survival
-1000 for death


old strategy:

new strategy:

It converges much better and it scores higher than 10000 sometimes.