# In the context of importance sampling ratio, how is the equation $\mathbb{E}\left[\rho_{t: T-1} G_{t} | S_{t}=s\right]=v_{\pi}(s)$ derived?

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)$$
• 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 Dec 19 '18 at 20:22
$$\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$$