How does a Q algorithm consider future rewards?

Question

I am trying to understand the underlying logic of Q learning (deep Q learning to be precise). At the moment I am stuck at the notion of future rewards.

To understand the logic, I am reviewing some of the present code samples. This one seemed quite interesting, so I went through it:

https://github.com/keon/deep-q-learning/blob/master/dqn.py

Here is the gist of the code that does the actual training of the underlying deep neural network:

def replay(self, batch_size):
    minibatch = random.sample(self.memory, batch_size)
    for state, action, reward, next_state, done in minibatch:
        target = reward
        if not done:
            target = (reward + self.gamma *
                      np.amax(self.model.predict(next_state)[0]))
        target_f = self.model.predict(state)
        target_f[0][action] = target
        self.model.fit(state, target_f, epochs=1, verbose=0)
    if self.epsilon > self.epsilon_min:
        self.epsilon *= self.epsilon_decay

In the 5th line of the code, (after the if not done line) we are adding the discounted reward of the next step, to the present step, and setting it as the target reward of the executed action to be trained. So, the way I see it, we have the reward of the executed action, and discounted possible reward of the following action, combined.

As far as I understand, in each iteration, Q-learning algorithm predicts the future reward of next step (and next step only) using the machine learning technique in use (be it the CNN, DNN etc.). And we are multiplying the reward of next step (and that specific next step only) with discount rate, to make it less important than the immediate reward (with the ratio we specified). So, my question is, how does the algorithm takes even further steps (say, 5 steps) ahead into account?

Answer 1

As far as I understand, in each iteration, Q-learning algorithm predicts the future reward of next step (and next step only) using the machine learning technique in use (be it the CNN, DNN etc.).

The Q values should eventually converge to the expected sum, future, discounted reward when taking action A in state S and following the optimal policy. Breaking it down:

• Expected sum is not exactly the same as "predicted", but close enough for our purposes. And it really does mean sum of the rewards, not a single reward. To differentiate, this is often called the "return" or "utility"

• Future -> from the step being evaluated onwards until end of episode, or the limit as time goes to infinity for continuous tasks with discounting.

• Discounted -> a discount factor is only necessary for continuous tasks.

And we are multiplying the reward of next step (and that specific next step only) with discount rate, to make it less important than the immediate reward (with the ratio we specified).

No, there is no multiplication of the reward. Let's take a look at the line:

target = (reward + self.gamma *
                  np.amax(self.model.predict(next_state)[0]))

The reward is not being multiplied by anything.

What is being multiplied by $\gamma$ is the Q value of the next state. That value represents the total sum of all rewards following on from that point - not a single reward value at all.

So, my question is, how does the algorithm takes even further steps (say, 5 steps) ahead into account?

It is in the Q values. The pseudocode for the code you are looking at is not:

target_for_Q(s,a) = next_step_reward * gamma

It is:

target_for_Q(s,a) = next_reward + gamma * current_value_of_Q(s',a')

Or:

target_for_Q(s,a) = next_reward + gamma * estimate_all_future_return

This is closely related to the Bellman function for policy evaluation.

Intuitively what is happening is that you start with (really poor) estimates for expected return (not expected reward), and update them by inserting observed values of next_reward, s' and a' into the update rule above. The values always represent a learned estimate of total expected return.