2
$\begingroup$

In the book "Reinforcement Learning: An Introduction" (2018) Sutton and Barto define the prediction objective ($\overline{VE}$) as follows (page 199): $$\overline{VE}\doteq\sum_{s\epsilon S} \mu(s)[v_{\pi}(s)-\hat{v}(s,w)]^2$$ Where $v_{\pi}(s)$ is the true value of $s$ and $\hat{v}(s,w)$ is the approximation of it. Furthermore it is stated that this is "often used in plots".

How do I get the true value $v_{\pi}(s)$? And if there is a way to obtain the value, why would I need to approximate it?

$\endgroup$
1
$\begingroup$

The true value $v_{\pi}(s)$ is a conceptual target for the $\overline{VE}$ in the book. You often do not know it in real problems. However, it is still used in two main ways in the book:

  • Theoretically for analysis of different aprpoximation schemes, which can be shown to converge to minimise the $\overline{VE}$ objective, or a related one.

  • In toy problems when exploring the nature of approximation in Reinforcement Learning (RL), it is possible to use tabular methods guranateed to get close to zero error, and then compare them to approximate methods. There are several plots of this type in the book.

The book shows derivation of gradient descent methods that start with minimising $\overline{VE}$ as an objective, and that use samples of $v_{\pi}(s)$ such as Monte Carlo return $G_t$ or the TD target) in place of the unknown $v_{\pi}(s)$ in the loss function. These also rely on the fact that the sample distribution will be weighted by $\mu(s)$ if they are taken naturally from the environment whilst the agent is following the policy $\pi$ so that $\mu(s)$ also does not need to be explicitly known.

Outside of toy problems deliberately constructed to demonstrate that this theory is correct, you will not know $v_{\pi}(s)$ or be able to calculate $\overline{VE}$. However, you will know from the theory that if you follow the update rules derived in the book for approximate gradient descent methods, that the process should find a local minimum for $\overline{VE}$, for whatever state approximation scheme you have chosen to use.

Usually you cannot even approximate $\overline{VE}$ from raw data, as the variance in returns will add noise to the signal, and there is no way to separate variance in returns from error in approximation in the general case. However there are a couple of scenarios that do lend themselves to measuring this objective, provided you already have your estimate $\hat{v}(s,w)$ and the policy remains fixed throughout:

  • Simple, fast (perhaps simulated), environments which can be solved to arbitrary accuracy using tabular methods. In this case, you first calculate $v_{\pi}(s)$ using a non-approximate method, then sample many approximations by running the environment using policy $\pi$ and treating that as your data set.

  • Fully deterministic environments where $\pi$ is also deterministic. These have a variance of $0$ for Monte Carlo returns, so each observed return from any given state is already the true value of $v_{\pi}(s)$. Again you can just run the environment many times to get your data set to calculate $v_{\pi}(s)$ and $\hat{v}(s,w)$ for the observed states in the correct frequencies, and thus have data to calculate $\overline{VE}$.

$\endgroup$
  • $\begingroup$ This is a great description, thank you for going through the documentation and fleshing this out. $\endgroup$ – Zakk Diaz Oct 7 at 16:53
0
$\begingroup$

I may be wrong about this but my best interpretation without having access to the book is that

How do I get the true value vπ(s)?

The True value I think is whatever the most correct answer is for the prediction. This should be training data. Some companies like facebook spend a lot of money to hire people to create hand-detailed data to fill in this value.

And if there is a way to obtain the value, why would I need to approximate it?

You are approximating it to test the accuracy of your model - your prediction. It seems to me this equation is only necessary when training the model.

The result of this is your total error between all your predictions. The lower the value, the better your model. https://en.wikipedia.org/wiki/Mean_squared_error

$\endgroup$
  • $\begingroup$ So the target (which from my understanding does not has to be the true value) is referenced there as "true" value? $\endgroup$ – F.M.F. May 28 at 19:09
  • $\begingroup$ It's hard to say without the book. The target value & true value seem like technical terms in which I would be wrong trying to assume their intention. $\endgroup$ – Zakk Diaz May 28 at 19:12
  • $\begingroup$ Okay. Thank you! You got my upvote but I will wait before accepting, if anyone has a more specific answer! $\endgroup$ – F.M.F. May 28 at 19:16
  • $\begingroup$ "Some companies like facebook spend a lot of money to hire people to create hand-detailed data to fill in this value" this is not something anyone can do for complex RL problems, even with the resources of Facebook. Instead proxy values are used and VE is unknown. Yet it can still be used as an objective, and analysed to create update rules. Also, you do have access to the book. It is freely available online as HTML and a PDF: incompleteideas.net/book/the-book.html $\endgroup$ – Neil Slater Oct 5 at 9:28

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.