Q learning: overtraining and converagence

Question

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:

Answer 1

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.