1
$\begingroup$

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:

beginning of the training

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

longer training

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

enter image description here

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:

enter image description here

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: enter image description here

$\endgroup$
1
$\begingroup$

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:

enter image description here

enter image description here

enter image description here

enter image description here

new strategy:

enter image description here

enter image description here

enter image description here

enter image description here

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

https://github.com/wentaocn/q-bird

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.