# Is the following the correct implementation of the Q learning algorithm for a neural network?

I just wanted to confirm that my understanding of Q learning was correct (with respect to a neural network).

The network, Q, is initialised randomly.
for n "episodes":
The state, s1, is initialised randomly
while s1 != terminal state:
s1 is fed into Q to get action vector q1
action a1 is chosen based off the max of q1 (or randomly)
state s2 is found by progressing s1 based on a1

s2 is fed into Q to get action vector q2

The expected output for Q at q1, y, is found by:
{If s2 is terminal, it is the reward at s2
{Otherwise: reward at s2 + gamm*max(q2)
(The "otherwise" doesn't match bellmans equation as α=1)

Do gradient step where error = (y - max(q1))^2, only the max of q1 gets any gradient
s1 = s2


This does not directly follow equations found by searching Q-learning as I find them rather ambiguous.

I am also not taking into account storing network states (in this case, the network is called Q) for proper learning to avoid catastrophic forgetting, as I'm more concerned on getting the specifics right before good practice.

Your pseudocode is fairly close to something that could be implemented. There are a couple of omissions, where it is not clear whether your implementation would do the right thing. There are a few non-general assumptions that are worth noting - they don't prevent you implementing for a specific purpose, but do prevent you writing the most generic DQN that you could. There is one mistake that prevents it working at all.

Do gradient step where error = (y - max(q1))^2, only the max of q1 gets any gradient

The loss function and gradient must be applied to the state/action pair s1, a1, i.e. the action that was taken. This is an important distinction for when the agent takes exploratory (non-greedy) actions, as it must if it is going to learn about their values.

A corrected statement might read: Do gradient step where error = (y - Q(s1,a1))^2, only the output for a1 gets any gradient.

Regarding the rest of the pseudocode I could make the following observations:

The state, s1, is initialised randomly

This is fine if it is possible. However, it is more usual in Q learning to initialise the state to whatever the normal start of the episode would be. That might be from some randomised starting rules, but that is not quite the same as picking a random state from all possible states.

action a1 is chosen based off the max of q1 (or randomly)

It is not quite clear what you mean by "or randomly". For Q learning - and most RL - exploration is important. So this is not a design time choice for your algorithm, but a runtime choice that must itself be made so that all actions can be tried. Typically you would use an $$\epsilon$$-greedy policy here that took the argmax action by default, but with probability $$\epsilon$$ took a random sample from actions with same chance of each possible action.

state s2 is found by progressing s1 based on a1

This is one of a few places where you have not quite captured the nature of a time step in a general MDP. You appear to have made the assumption that rewards are directly associated with states (with language like "reward at s2"). Whilst some MDPs are like that, it is not true in general.

A better, more general statement might be:

s2, reward, done are found by taking a step from s1, using a1 as the action

Typically the environment (or a wrapper for it that establishes state representations and rewards) will provide a step method that returns the tuple $$s_{t+1}, r_{t+1}, (s_{t+1} = s_T)$$, although you could also hold these values in the environment model for the current time step and return them as required.

This statement:

(The "otherwise" doesn't match bellmans equation as α=1)

I don't know which Bellman equation you are referring to, but they don't include a learning rate, $$\alpha$$ in any version I have seen. Perhaps you are referring to a tabular Q learning update? In any case, it doesn't seem relevant, as whatever learning rate you are using is now inside the gradient step, and does not need to be part of the pseuodcode.

Finally, regarding this:

I am also not taking into account storing network states (in this case, the network is called Q) for proper learning to avoid catastrophic forgetting, as I'm more concerned on getting the specifics right before good practice.

DQN will very likely not work at all, for most environments, unless you implement experience replay i.e. training the neural network on a random sample of stored s1,a1,r,s2,done taken from a table that you build up on each time step. Usually you cannot simply use the latest data from the current step. This is not just "good practice", but an almost-always necessary stability improvement.

• Thank you so much for addressing each point with such detail. It is to my knowledge that for each state (for example s1), it is fed through the neural network, and the network then returns the Q values for every action possible at that state, in my case I referred to this array as q1. Is this correct? – Recessive Dec 9 '19 at 14:31
• @Recessive yes that is a common approach, as it is more efficient to use and train than the alternative which is a NN that directly implements Q(s,a) with both s and a as inputs with a single value output. However, the latter approach is also viable and correct in theory. – Neil Slater Dec 9 '19 at 14:33
• as for state s2 is found by progressing s1 based on a1, I am still a little bit confused. In order to find the Q values for each action that could be taken at the state that would follow after taking action a1, isn't it necessary to feed the new state into the neural network in order to get these values (or q2)? So would this not mean you have to progress the state forward? And I think I understand what you mean about my misconception of a state having an associated reward. Am I correct in saying that, it is instead rather a specific action at a state is what has the associated reward? – Recessive Dec 9 '19 at 14:35
• @Recessive: All of current state, action, next state and a random factor may influence reward. Which of these are used depends on your problem. That is why the most general approach to capturing the results of an action is to have something like next_state, reward, done = env.step(action) – Neil Slater Dec 9 '19 at 14:38
• Just a flag as to whether s2 is a terminal state. It is possible that the state features don't include whether or not the state is terminal (this is never going to be used to drive any approximation, as will always be False when you feed to a NN - when True then $Q(s_2,\cdot) = 0$ by definition), so it is a matter of convenience. You may be able to avoid it in your case, but if you want to work with Open AI gym for instance, it uses this convention – Neil Slater Dec 9 '19 at 14:41