2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thank you Neil! In this example, can we refer to the "weighted average" the same as "Running" or "exponential moving" average? $\endgroup$ – Kari Jan 29 '18 at 11:01
  • 1
    $\begingroup$ @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 $\endgroup$ – Neil Slater Jan 29 '18 at 11:06

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.