1
$\begingroup$

From "Reinforcement Learning: An introduction (2nd ed.)" by Richard S. Sutton and Andrew G. Barto, on page 107 and 108:

We can verify that the variance of the importance-sampling scaled returns is infinite in this last example. The variance of a random variable X is the expected value of the deviation from its mean X¯:

\begin{align} \mathrm{Var}[X] \doteq \mathbb{E} \Big[ (X - \bar{X})^2\Big] = \mathbb{E} \Big[ X^2 - 2X\bar{X} + \bar{X}^2 \Big] = \mathbb{E} \Big[ X^2\Big] - \bar{X}^2 \end{align}

If the mean of the random variable is finite (as in the example), having an infinite variance means that the expectation of the square of the random variable is infinite. Thus, we need only show that the expected square of the importance-sampling scaled return is infinite:

\begin{align} \mathbb{E}\_b \Bigg[(\prod_{t=0}^{T-1} \frac{\pi(A_t|S_t)}{b(A_t|S_t)}G_0 )^2\Bigg] \end{align}

Question is following: why we calculate expected return for policy $b$ instead of $\pi$? If we approximate returns for $\pi$ using importance sampling aren't we supposed to calculate $\mathbb{E}\_\pi$?

$\endgroup$

1 Answer 1

2
$\begingroup$

why we calculate expected return for policy $b$ instead of $\pi$?

The expected return for policy $b$ is not being calculated here:

\begin{align} \mathbb{E}_b \Bigg[(\prod_{t=0}^{T-1} \frac{\pi(A_t|S_t)}{b(A_t|S_t)}G_0 )^2\Bigg] \end{align}

This expression is part of the variance of the importance-sampled expected return for $\pi$, given that your observations of $G_0$ are all made following $b$. The expectation of this value is shown as expected following policy $b$, because that is what you directly observe.

If you were instead observing returns from following the policy $\pi$, you wouldn't have the problem with possible unbound variance when trying to convert it.

The proof is showing a problem inherent to the conversion maths. The importance sampling is still approximating $\mathbb{E}_{\pi} \Big[G_0\Big]$, but the proof needs to look at the conversion in detail to show the possibility of infinite variance.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .