3
$\begingroup$

I was going through Sutton's book and, using sample-based learning for estimating the expectations, we have this formula

$$ \text{new estimate} = \text{old estimate} + \alpha(\text{target} - \text{old estimate}) $$

What I don't quite understand is why it's called the target, because since it's the sample, it’s not the actual target value, so why are we moving towards a wrong value?

$\endgroup$
5
$\begingroup$

It is our "current" target. We assume that the value we get now is at least a closer approximation to the "true" target.

We're not so much moving towards a wrong value as we are moving away from a more wrong value.

Of course, it is all base on random trials, so saying anything definite (such as: "we are guaranteed to improve at each step") is hard to show without working probabilistically. The expectation of the error of the value function (as compared to the true value function) will decrease, that is all we can say.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Maybe to clarify your answer, you could add the formula of the "target" and why it represents an estimate of the "true" target. Anyway, welcome to Artificial Intelligence SE :) $\endgroup$ – nbro Aug 28 at 19:16
  • $\begingroup$ This isn’t clear to me, why is it closer to the true target? $\endgroup$ – Chukwudi Ogbonna Aug 28 at 20:02
  • $\begingroup$ I understand that we use a sample return as the target, but what I don’t get is how it moves closer to the true target, the sample return doesn’t get closer to the target, the mean of those samples is what gets Closer which is our value function, so why do we then call the it target $\endgroup$ – Chukwudi Ogbonna Aug 28 at 20:16
  • $\begingroup$ The new value is equal to $(1 - \alpha)(\mathrm{old estimate}) + \alpha(\mathrm{new estimate})$. We're gradually "forgetting" the old estimate with a decay rate of $(1 - \alpha)$. $\endgroup$ – Robby Goetschalckx Aug 28 at 23:13
1
$\begingroup$

It would be heplful for me if you specify the section and page number of the Sutton's book. But as far as I understand your question I will try explain this. Think of TD update. The sample contains $(s_t,a_t,r_{t+1},s_{t+1})$. Using incremental update we can write: $$ v_{t}(s) = \frac{1}{t} \sum_{j=1}^{t}(r_{t+1} + \gamma v_{s_{t+1}})$$ $$ v_{t}(s) = v_{t-1}(s) + \alpha (r_{t+1} + \gamma v_{t-1}(s_{t+1}) - v_{t-1}(s_t))$$ We are calling this $r_{t+1} + \gamma v_{t-1}(s_{t+1})$ as the TD target. From the above equation you can already see that $r_{t+1} + \gamma v_{t-1}(s_{t+1})$ is actually the unbaised estimate for $v(s)$. We are calling $r_{t+1} + \gamma v_{t-1}(s_{t+1})$ an unbiased estimate since $E[r_{t+1} + \gamma v_{t-1}(s_{t+1})] = v_t(s_t)$. That means expectation over $r_{t+1} + \gamma v_{t-1}(s_{t+1})$ lead us to true state value function, $v_t(s)$.

For the monte carlo update same explain will be applied. I hope that this answer your question.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I understand the unbiased estimate part, which means by law of large numbers it’ll eventually converge to the optimal value, what I don’t get is why it’s called the target , normally in supervised learning it’s the actual target value, not a sample return , we’re using a sample return as our target TD, which I do not understand $\endgroup$ – Chukwudi Ogbonna Aug 28 at 19:59
  • $\begingroup$ In RL targets are not fixed like supervised learning. Here we have moving targets. It is called target in the sense that it is an unbiased estimate of the true value. $\endgroup$ – Swakshar Deb Aug 28 at 20:08
  • $\begingroup$ Ok, so why do people say the target will eventually converge, isn’t it the mean of the target that actually converges to the optimal q value, I mean that’s what unbiased estimate means $\endgroup$ – Chukwudi Ogbonna Aug 28 at 20:20
  • $\begingroup$ People say this in the sense that initially what you get $r_{t+1} + \gamma v(s_{t+1})$ is not actually an unbiased estimate. We randomly initally all $v(s) = 0$. Then gradually they started to update. Initially, those values do not represent the unbiased estimate. But as time passes those estimate get close to the true unbiased estimate and converges to the unbiased estimate. For this reason they say target will eventually converge to the ubiased estimate. $\endgroup$ – Swakshar Deb Aug 28 at 20:34
  • $\begingroup$ Chill I think I get what you mean, we use the estimate r + yV(s’), the unbiased estimate is the formula with the optimal V(s) ie R +yV*(s’), but since we use an estimate instead of the actual value ,so as our V(s) estimate converges to the V*(s) we can then say the target now becomes the unbiased estimate of our true value function ? $\endgroup$ – Chukwudi Ogbonna Aug 28 at 20:42

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.