# Do we have two Q-learning update formulas?

I have seen two deep Q-learning formulas:

$$Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a\right)-Q\left(S_{t}, A_{t}\right)\right]$$

and this one

$$Q(s, a)=r(s, a)+\gamma \max _{a} Q\left(s^{\prime}, a\right)$$

Which one is correct?

• Both are correct. The second one however is used in the deterministic case because applying the second one to stochastic environments with probabilistic state transitions will not cause the Q values to converge. – calveeen May 22 '20 at 9:42
• @calveeen It's not just about stochastic environments. It's also about the fact that the $Q(S_{t+1}, a)$ values being used for bootstrapping may be inaccurate even in deterministic environments (they're our own estimates which are probably not 100% accurate). Stochastic environments do make this worse though, yes. – Dennis Soemers May 22 '20 at 9:53

The first one is the update rule that we use in the $$Q$$-learning algorithm.

The second one is the "definition" of $$Q(s, a)$$ values, although I would personally write it as follows, with an expectation around the reward, to also support cases where rewards might be non-deterministic;

$$Q(s, a) \doteq \mathbb{E} \left[ r(s, a) \right] + \gamma \max_a Q(s', a)$$

Here, the $$Q(s', a)$$ itself would also be similarly defined, and again that one is also assumed to be a "ground-truth" value.

In practice, when learning, we do not actually know what any of these $$Q$$-values exactly are; that's why we're doing learning in the first place, we're trying to learn what these values are! More precisely, when we wish to assign a new value to $$Q(s, a)$$, the definition tells us that we should use $$Q(s', a)$$ for that, but we can't because we don't know exactly what the correct $$Q(s', a$$) value is either.

We do generally have some $$Q(S_{t+1}, a)$$ values, but they're generally going to be only approximations, resulting from the previous steps of our own learning process (or maybe even randomly initialised values if we only just started training!). There may also be an additional approximation error in stochastic environments, where the true $$Q(s', a)$$ value may be a weighted average over multiple different possible successor states $$s'$$, but during the training we only observed a single concrete successor state $$S_{t+1}$$.

So, we can follow the definition and use $$Q(S_{t+1}, a)$$ as an approximation of $$Q(s', a)$$, but we know that it's just an approximation and not entirely reliable. Therefore, instead of fully applying the definition and completely replacing our $$Q(s, a)$$ value based on it, we interpolate between our current estimate $$Q(s, a)$$ and the new one that we should have according to the definition + our approximations. We only slightly shift towards it. The learning rate $$\alpha$$ determines how much we shift towards it. Normally we use a learning rate $$0 < \alpha < 1$$. Note that if you were to use $$\alpha = 1$$, you would actually recover the definition for $$Q$$-values again (except it would still use some observations to estimate unknown quantities).

• I think that the definition of the $Q(s,a)$ as you have defined them would only hold if we were following the optimal policy. I don't think for a general policy $\pi$ that you definition would hold - it should be $Q_\pi(s,a) = \mathbb{E}[r + V_\pi(s') | s, a]$ – David Ireland May 22 '20 at 10:00
• @DavidIreland I left the policy that I'm defining it for off yeah, implicitly assuming that it would be for the optimal policy. But the definition would actually work for any greedy policy. In the context of $Q$-learning we do always try to learn about greedy policies. – Dennis Soemers May 22 '20 at 10:07
• I agree that it would hold for any greedy policy, but generally we want to learn an $\epsilon$-greedy policy to make sure we are exploring sufficiently. I guess once it is considered to be performing optimally (or close to) and you want to use it (e.g. playing Atari games) you could then just always choose the greedy action. – David Ireland May 22 '20 at 10:13
• @DavidIreland Normally you'd use an $\epsilon$-greedy policy (or some other form of exploratory policy) to generate experience for training, yes. But in $Q$-learning, you do not aim to learn anything about that policy. You just use it to generate experience, which you then use to learn about a completely different policy (a policy that's greedy with respect to your $Q$-values). This is why $Q$-learning is an off-policy algorithm; it learns about a policy that's different from the one used to generate experience. – Dennis Soemers May 22 '20 at 10:18
• Ah sorry, in your answer I thought you were talking about the general definition of $Q(s,a)$ - not specifically in the context of Q-learning. My bad. – David Ireland May 22 '20 at 10:27