1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much for this detailed explanation. I think the missing puzzle piece for me was the concept of "expected return". There is still something I couldn't figure out however. The "reward" we are getting in each step, is it the cumulative reward up to that point, or is it the reward gained with the action we took in that particular state? If the reward is what we have gained with our last action in that particular state, how can expected return eventually converge to the sum of the rewards? Because there is no input in the system which refers to the sum of all rewards. $\endgroup$ – SercioSoydanov Apr 5 '18 at 16:22
  • 1
    $\begingroup$ @SercioSoydanov: The input "R", is the individual reward after taking a single step. The Q value converges to the total return, because it is updated based on the Bellman equation which relates the before and after action state values, so that $Q(s,a) = \mathbb{E}[R_{t+1} + \gamma Q(S_{t+1},A_{t+1})| S_t = s, A_t=a]$ is the equilibrium point of the updates. This is provable from the basic theory of MDPs. Essentially you are squeezing "real" data in between two estimates in order to improve one of the estimates. $\endgroup$ – Neil Slater Apr 5 '18 at 17:17
  • $\begingroup$ Ok, that makes it all clear. Great explanation. Thank you very much. $\endgroup$ – SercioSoydanov Apr 5 '18 at 18:00
  • $\begingroup$ Nice explaination $\endgroup$ – Aditya Apr 5 '18 at 18:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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