Deep Q Learning for Simple Game Not Effective
Your implementation of single-step Q-learning with neural network and experience replay is basically correct.

There are a few blocking issues preventing you seeing it working correctly.

Your main problem is a bug in your feature scaling routine. That is a Python issue, not really an AI one. In short, you scale the input features in-place multiple times, including an effective double-scaling of next_state (when it gets copied to state you scale it in place a second time in the next loop) so that all the states that you store in the experience replay table never match to any input states. You need to change your definition of scale to not do this. A very simple re-write of your routine would be:

def scale(s):
    return [s[0]/500, s[1]/500, s[2]/300, s[3]/3]


In addition, you need to change random action selection to:

np.random.randint(0, 3)


because the end of range is never output (this matches behaviour of other range values and operators in Python). Not including the "do nothing" action during exploration means that the agent will test it less, and have less data to work with to assess whether it is the best action. This is a minor issue for this environment, but you should fix it nonetheless.


  What is happening is that training is super slow (more than an hour for 20 episodes (or 400 seconds of actual game play)). 


I cannot replicate this fault and can train 20 episodes in around 2.5 minutes - that's over 20 times faster than you report. I am not using a GPU. Possibly in your case, Theano and Pygame are fighting for control of the GPU, or you may have a GPU configuration issue with Theano. Try turning GPU acceleraton off to verify whether it helps. You don't benefit much from a GPU for this environment (most time is spent in Python running the Q-learning and the environment), so can afford to put solving that issue to one side for now.


  Also, it does not seem to get much better. The paddle (after 20 episodes) moves left and right but without any obvious pattern


Sadly, I cannot see the output at all on my MacBook pro, but I was able to use feedback of the expected score. A random agent gets a mean score of ~5.5 per episode. With the scale function corrected, and a rough guess at working hyperparameters, I can get an average score of ~17 per episode consistently after 60 episodes of training. After 150 episodes - taking 20 minutes to train - the agent was scoring ~20 per episode and I stopped there. It is possible that an expected score around 20 is already optimal, as it is a very simple environment, but I don't know.

Once you have a working system, there are lots of hyperparameters you could play with to try and improve this. I got my results by making the following changes after fixing the scale function:


Starting epsilon of 1.0
Repay memory size 10,000
Only start learning when replay memory has greater than 1,000 entries
Discount factor $\gamma$ 0.99
Neural network with 20 neurons per layer with tanh activation instead of relu


There is quite a lot else you could change that might make the agent learn more effectively or perhaps aim for a more optimal policy. Have fun experimenting!