# Doubt in Deep-Q learning with sparse rewards

I am working on a deep reinforcement learning problem, when I got stuck at the following questions. They are rather general and not specific to my specific problem. The solution uses a sparse reward structure. Throughout the episode there is a small positive and negative reward for good or bad decisions. At the end there is a huge reward for completion of the episode.

This is my understanding of how DQN works. The neural network predicts quality values for each possible action that can be taken from a state (S1). Let us assume the predicted quality value for an action A is Q1 and this action allows the agent to reach S2.

We now need the target quality value Qt, so that using Q1 and Qt gradients can be calculated and updates can be made to the parameters of the network. Qt is calculated using the Bellman equation. For an arbitrary state the bellman equation consists of two parts. The immediate reward:R and the maximum quality value of the resulting state that this chosen action leaves us in (say Q_future).

Q_future is obtained by feeding the new state S2 into the neural network and choosing (from the list of quality values for each action) the maximum quality value.

We then apply a discount to this Q_future and add it to the reward R.

Now let us assume the agent is in the penultimate state (S1) and chooses the action (A) that leads him to completion state (S2) and gets him the huge final reward :Rmax. My question is how do we form the target value for this case? Do we still include the Q_future term? Or is it only the reward in this case?

The agent would not have seen states beyond the final state. So I am not sure if Q_future even has a meaning after reaching the final state. But if we still consider this Q_future mathematically, to be the output of the network when the final state is plugged in, then I would expect this to be comparable or greater than the predicted Q. So the target Q becomes a huge reward + (discount_factor*Q_future). This does not seem to converge as whatever this predicted Q is in the final step, the target Q is much bigger. So I feel for the final step, the target value must simply be the reward. Is this right?

• Hi pranav. Your first question is very confusing, and has 5 sub-questions, some of which don't make sense because you are not explaining why you think e.g. "Because the target value will be always approximately double the predicted value". I suggest reducing the number of questions and explaining your thinking so far, with some references to the equations and update rules you are using, because then answers can show where you are going wrong without needing to recap all the maths to setup the Q table update rules – Neil Slater Oct 15 '19 at 16:44
• HI. I have only 1 question now. I tried to make it as clear as possible. – pranav Oct 15 '19 at 17:21

Now let us assume the agent is in the penultimate state (S1) and chooses the action (A) that leads him to completion state (S2) and gets him the huge final reward :Rmax. My question is how do we form the target value for this case? Do we still include the Q_future term? Or is it only the reward in this case?

Your term "completion state" is commonly called "terminal state". In a terminal state, there are no more actions to take, no more time steps, and no possibility to take any action. So, by definition, in your state S2, the expected future reward is 0.

Mathematically, this is often noted like $$v(S_T) = 0$$ or $$q(S_T,\cdot) = 0$$ with the $$T$$ standing for last time step of the episode, and dot standing in for the fact that no action need to be supplied, or the specific action value is not relevant. So, therefore using your terms, $$Q_{future} = \text{max}_a Q(S_2, a) = 0$$

That makes the equations work in theory, but does not explain what to do in code. In practice in your code, you would do as you suggest and use just the reward when calculating the TD target for Q(S1, A1). This is typically done using an if block around the done condition e.g.

if done:
td_target = r
else:
td_target = r + gamma * np.max(q_future_values)
end


of course the details depend on how you have structured and named your variables. You will find code similar to this in most DQN implementations though

You should not really try to learn $$V(S_2)$$ or $$Q(S_2, A)$$, or calculate TD target starting from S2, because the result should be $$0$$ by definition.