1
$\begingroup$

I asked a question a while ago here and since then I've been solving the issues within my code but I have just one question... This is the formula for updating the Q-Matrix in Q-Learning:

$$Q(s_t, a_t) = Q(s_t, a_t) + \alpha \times (R+Q(s_{t+1}, max_a)-Q(s_t, a_t))$$

However, I saw a Q-Learning example that uses a different formula, which I'm applying to my own problem and I'm getting good results:

$$Q(s_t, a_t) = R(s_t,a_t) + \alpha \times Q(s_{t+1}, max_a)$$

Is this valid?

$\endgroup$
  • $\begingroup$ Where did you see the second implementation? Perhaps there is a context being missed. $\endgroup$ – SeeDerekEngineer Feb 18 '19 at 15:36
  • $\begingroup$ @SeeDerekEngineer it was to solve the basic problem where there's 7 nodes and you wanna go from 2 to 5 or something equivalent. Does that make it different? $\endgroup$ – Sergio Feb 18 '19 at 15:55
3
$\begingroup$

No, your second statement does not correctly implement the Q-learning update rule, which the first statement correctly implements.

| improve this answer | |
$\endgroup$
1
$\begingroup$

Your second code snippet is equivalent to this:

$$Q_{k+1}(s,a) \leftarrow r + \alpha \text{max}_{a'} Q_k(s', a')$$

This looks like a simplified Value Iteration update to me, where you have incorrectly switched $\alpha$ (the learning rate) for $\gamma$ (the discount rate).

The full Value Iteration update based on action values looks like this:

$$Q_{k+1}(s,a) \leftarrow \sum_{r,s'} p(r,s'|s,a)(r + \gamma \text{max}_{a'} Q_k(s', a'))$$

This is almost the same as your equation when you have a deterministic environment (so you can directly predict single values $r$ and $s'$ from $s, a$)

As such, it will sort of work with certain assumptions:

  • You want a specific discount rate, or don't particularly care about predicting values, just finding a close-to-optimal policy

  • The environment is deterministic

The further away you are from those assumptions, the worse fit the simpler update method will be to your problem. It is definitely not Q-learning either way.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Oh, ok. Not sure why they use this formula in the example though. Either way, don't understand why I get good results using this formula but the actually correct one doesn't work! Guess I'll have to keep trying to find out some more, thanks! $\endgroup$ – Sergio Feb 18 '19 at 15:48
  • 1
    $\begingroup$ @Sergio A discount factor of 1 means that you're valuing the future rewards in the same way that you're valuing the immediate reward (the one you received after having taken the action at the current step). You often don't want this behaviour, in general, because, intuitively, the future is uncertain, so you want to give less weight to those future rewards. See also: stats.stackexchange.com/q/221402/82135. $\endgroup$ – nbro Feb 18 '19 at 16:10
  • 1
    $\begingroup$ @Sergio A discount factor of $0.1$ seems awefully low though. Much more common choices are like... $\gamma = 0.99$ or $\gamma = 0.9$. $\endgroup$ – Dennis Soemers Feb 18 '19 at 20:50
  • 1
    $\begingroup$ I think he's mixing up discount factor with step size parameter $\endgroup$ – Brale Feb 18 '19 at 22:45
  • 1
    $\begingroup$ @Sergio It's not necessarily wrong... in theory, anything that is between $0$ and $1$ is fine. It's so low though that you get very close to only caring about immediate one-step rewards, and almost ignore any future rewards (even if they're very close in the future, only a couple of steps away). But yeah sure, if it works, it works. $\endgroup$ – Dennis Soemers Feb 20 '19 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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