# Q-learning why do we subtract the Q(s, a) term during update?

I can't understand the meaning of $-Q(s_t, a_t)$ term in the Q-learning algorithm, and can't find explanation to it either.

Everything else makes sence. The q-learning algorithm is an off-policy algorithm, unlike SARSA. The Bellman equation describes q-learning as follows:

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\left[ r_t + \gamma \cdot argmax(Q(s'_t, a'_t)) - Q(s_t, a_t) \right]$$

"The q value for action $a$ taken in state $s$ at time $t$ becomes equal to: that same q-value plus small amount of: currently received reward (reward could be zero) with some amount $\gamma$ of the best Q-value available in the new state, minus our current value

To me, this $-Q(s_t, a_t)$ term at the very end is redundant. ...If we set gamma to $0.8$, the future rewards will decay anyway.

Yes, if instead we now set $\gamma=0$, then the $-Q(s_t, a_t)$ term will drag our value down - is there a case when it would be useful and what would the result be?

Edit:

wikipeda uses a slighly different form of the bellman equation

$$Q(s_t, a_t) \leftarrow (1-\alpha)\cdot Q(s_t, a_t) + \alpha\left[ r_t + \gamma \cdot argmax(Q(s'_t, a'_t)) \right]$$

It's the same equation as the one above, because we can multiply $Q(s_t, a_t)$ with an $\alpha$ and then factor it out, obtaining the first equation.

This representation makes me kind-off understand that we are linearly interpolating from current to newer Q-value, but I can't tie it to the original representation ...In the original representation (the first equation), it magically seems that gamma would be enough - can someone clear it up for me?

The wikipedia formulation does indeed show you a better view of how the update rule for action values is constructed:

$$Q(s_t, a_t) \leftarrow (1-\alpha)\cdot Q(s_t, a_t) + \alpha\left[ r_t + \gamma \cdot \text{max}_{a'}(Q(s_{t+1}, a')) \right]$$

. . . here you can see that you are taking a weighted average between $Q(s_t, a_t)$ and $r_t + \gamma \cdot \text{max}_{a'}(Q(s_{t+1}, a')$. An aside: In both cases you have written $\text{argmax}$, where the actual term is $\text{max}$.

The intuitive reason for the update is because the second term contains a new estimate of the true value of Q from the environment - the immediate reward $r_t$, and the actual state transition that occurred $s_{t+1}$ are observed data that are part of the new estimate. The term $r_t + \gamma \cdot \text{max}_{a'}(Q(s_{t+1}, a'))$ is usually called the Temporal Difference Target or just TD Target.

In the original representation (the first equation), it magically seems that gamma would be enough - can someone clear it up for me?

The $\gamma$ term is the discount rate, and nothing to do with convergence of Q-learning or SARSA. It is a term used to control preference for more immediate rewards (low values) or longer-term rewards (high values), and as such is part of the problem definition. It is not a learning parameter like $\alpha$, the learning rate. And in fact $\gamma = 0$ is possible (rarely used, but meaning that only next reward is important); $\gamma = 1$ is also possible and quite a common choice for episodic problems. Clearly when using $\gamma = 1$, there is no "decay of future rewards" happening.

What is actually happening is that the TD Target is a stochastic estimate for the correct Q action value (in fact with all TD learning such as SARSA and Q-learning, this is a biased estimate, although the bias should reduce as the system approaches convergence). If you rename $Q(s,a)$ as $Q_{so\_far}$ and $r_t + \gamma \cdot \text{max}_{a'}(Q(s_{t+1}, a'))$ as $Q_{latest\_estimate}$, you get the idea of the update:

$$Q_{updated} \leftarrow (1-\alpha)Q_{so\_far} + \alpha Q_{latest\_estimate}$$

which is the same as

$$Q_{updated} \leftarrow Q_{so\_far} + \alpha(Q_{latest\_estimate} - Q_{so\_far})$$

You might ask "Why is the TD Target an estimate of $Q(s_t, a_t)$?"

The answer can be derived from the definition of Q, and is called the Bellman equation - in this case the Bellman equation for action value under the optimal policy $\pi^*$ (anther aside: what you have called the Bellman equation is not, although it is related). I won't give the full derivation here, but in essence the definition of Q is "the expected total reward when starting with state $s_t$ and action $a_t$ then following the optimal policy form then on", or

$$q_{*}(s, a) = \mathbb{E}_{\pi^*}[\sum_{k=0}^{\infty}\gamma^k R_{t+k+1} | S_t = s, A_t = a]$$

and from this definition, you can extract the first reward term and write out $q_*(s_t, a_t)$ in terms of $q_*(s_{t+1}, a_{t+1})$.

$$q_{*}(s, a) = \sum_{r,s'} p(r,s'|s,a)(r + \gamma \text{max}_{a'} q_{*}(s', a'))$$

Where $p(r,s'|s,a)$ is the transition probability of getting reward $r$ and ending up in state $s'$ when starting in state $s$ and taking action $a$.

Note this is an equality, not an update rule. Q-learning and SARSA turn it into an update rule by sampling the right hand side, and using that sample to update the current best estimate of the left-hand term. Note that by taking a sample, you don't need to know $p(r,s'|s,a)$ . . . that is what is meant by "model free" learning, as if you knew $p(r,s'|s,a)$ then you would have a model of the underlying Markov Decision Process (MDP).

• Thank you Neil! In this example, can we refer to the "weighted average" the same as "Running" or "exponential moving" average? – Kari Jan 29 '18 at 11:01
• @Kari: Yes, sorry I was a bit loose with that term. A single iteration is a weighted average. Overall the Q values are updated according to the exponential moving average – Neil Slater Jan 29 '18 at 11:06