When reading the book by Sutton and Barto, I came across the importance sampling ratio.

The first equation, I believe, describes the probability a particular sequence is obtained given the current state, and the policy.

\begin{align} &\operatorname{Pr}\left\{A_{t}, S_{t+1}, A_{t+1}, \ldots, S_{T} | S_{t}, A_{t: T-1} \sim \pi\right\} \\ &=\pi\left(A_{t} | S_{t}\right) p\left(S_{t+1} | S_{t}, A_{t}\right) \pi\left(A_{t+1} | S_{t+1}\right) \cdots p\left(S_{T} | S_{T-1}, A_{T-1}\right) \\ &=\prod_{k=t}^{T-1} \pi\left(A_{k} | S_{k}\right) p\left(S_{k+1} | S_{k}, A_{k}\right) \end{align}

The next part takes the ratio between the probabilities of the two trajectories:

$$\rho_{t: T-1} \doteq \frac{\prod_{k=t}^{T-1} \pi\left(A_{k} | S_{k}\right) p\left(S_{k+1} | S_{k}, A_{k}\right)}{\prod_{k=t}^{T-1} b\left(A_{k} | S_{k}\right) p\left(S_{k+1} | S_{k}, A_{k}\right)}=\prod_{k=t}^{T-1} \frac{\pi\left(A_{k} | S_{k}\right)}{b\left(A_{k} | S_{k}\right)}$$

I don't understand how this ratio could lead to this:

$$\mathbb{E}\left[\rho_{t: T-1} G_{t} | S_{t}=s\right]=v_{\pi}(s)$$

The $G_t$ rewards are obtained through the $b$ policy, not the $\pi$ policy.

I think there is something to do with Bayes rule, but I could not derive it. Could someone guide me through the derivation?


It has nothing to do with Bayes rule, like you said, $G_t$ is the return we get by following the policy $b$ , so the value of the state we get that return in is equal to the expected value of that return. On page 59 of the book, equation 3.14 derives the value of the state as expected value of the return but in this case we are following the behaviour policy $b$ so you would replace $\pi (a \mid s)$ with $b (a \mid s)$ and $v_\pi (s')$ with $v_b (s')$ and you would get the value of the state following the policy $b$, that is $v_b (s)$.
We are actually interested in the value of the state when we follow target policy $\pi$ , but we got the value by following behaviour policy, so we will multiply that expression with importance sampling ratio. If we do that $b (a \mid s)$ terms will cancel out and you are only left with term $\pi (a \mid s)$ from importance sampling ratio so we will get the value by following the target policy $\pi$ that is $v_\pi (s)$

  • $\begingroup$ That was clear explanation. But, could you show how the terms cancel? $\endgroup$ – Zach Zhao Dec 19 '18 at 16:44
  • $\begingroup$ importance sampling ratio for state $s$ is $\pi (a \mid s) / b (a \mid s)$ and $b (a \mid s)$ term in that ratio will cancel out with term $b (a \mid s)$ from first sum in expression 3.14 (the modified one as I described above). Notice that expression 3.14 is recursive so same would apply for value $v_b (s')$ which you would write out the same way as $v_b (s)$ is written out in 3.14, but in that state (state $s'$ ) importance sampling ratio would be $\pi (a \mid s') / b (a \mid s')$ and now terms $b (a \mid s')$ would cancel out and so on, you would keep writing out next states until the end $\endgroup$ – Brale Dec 19 '18 at 20:22
  • $\begingroup$ I see how the value terms could recursively cancel out with the sampling ratio, but would the reward terms be affected unequally when expanding? $\endgroup$ – Zach Zhao Dec 20 '18 at 17:02
  • $\begingroup$ sorry, I think I expressed myself incorrectly. You wouldn't actually calculate expected value and then multiply it with importance sampling ratio (notice how ratio is "inside" the expectation term that is shown in the picture you posted), you would consider importance sampling ratio while calculating expected value, so terms of total importance sampling ratio would "distribute" themselves across the states and then terms would cancel out like I described in previous comment so rewards wouldn't be affected by multiple policy probabilities (if that is what you meant), hopefully this is clear now $\endgroup$ – Brale Dec 20 '18 at 19:28

$\mathbb{E}_{X\thicksim P}[f(X)] = \sum P(X)f(X) = \sum Q(X)\frac{P(X)}{Q(X)}f(X) = \mathbb{E}_{X\thicksim Q}\left[\frac{P(X)}{Q(X)}f(X)\right]$

Here $P = \pi, Q = b ,f = G_t|S_t $


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.