# How is Importance-Sampling Used in Off-Policy Monte Carlo Prediction?

In the section, "Off-Policy Prediction via Importance Sampling", found in the chapter on monte carlo methods of the second edition of Sutton and Barto's, "Reinforcement Learning: An Introduction", the importance-sampling ratio $\rho_{t:T-1}$ of a sequence of action-state transitions $S_t, A_t, S_{t+1}, A_{t+1}, ..., A_{T-1}, S_T$ (where $T$ is the final time step, that is, $S_T$ is the terminal state of the episodic task) is defined as the ratio of the probability of that particular sequence of state-action transitions occurring under the target policy $\pi$ to the probability of that sequence occurring under the behavior policy $b$:

where $p$ is the state-transition probability. The author introduces the importance-sampling ratio as a means of obtaining the state-value function of the target policy $v_{\pi}(s)$ from an episode generated according to $b$, as explained in the following excerpt from the text.

My question is this: how exactly does multiplying the return under the behavior policy by the importance-sampling ratio in equation 5.4 produce the correct expectation for the state value function of the target policy? It is unclear to me how the ratio "transforms the returns to have the right expected value".

After some head-scratching, I think I was able to make sense of the "transformation" that the author uses in equation 5.4 to yield the correct expectation for $v_{\pi}(s)$. I've introduced some notation to help clarify what's going on. In particular, let $G_t^{(\pi)}$ denote the return after time step $t$ by following policy $\pi$. Then our goal is to estimate $v_{\pi}(s)$ for the target policy $\pi$ from an episode generated under behaviour policy $b$. Note that the state-value function for $b$ is defined as

$$v_b(s) = E[G_t^{(b)} | S_t = s]$$

We now apply the multiplication by the importance-sampling ratio proposed in equation 5.4 and expand using the definition of the expected value of $G_t^{(b)}$ as follows.

$$E[\rho_{t:T-1}G_t^{(b)} | S_t = s] = \sum_{g \in supp(G_t^{(b)})} \rho_{t:T-1} \cdot p_{G_t^{(b)}}(g) \cdot g$$

However, note that the probability of a particular return occurring under $b$ is just the probability of its sequence of state-action transitions (called the "trajectory" of a return in the text) occurring under $b$. Thus $p_{G_t^{(b)}}(g)$ is simply the probability of a particular trajectory occurring under $b$, as given in the following excerpt from the text for the example of an arbitrary policy $\pi$.

Recall $p$ here is the state-transition probability. We now substitute this expression for $p_{G_t^{(b)}}(g)$ into our expanded version of equation 5.4, and substitute the definition of $\rho_{t:T-1}$ to obtain:

$$E[\rho_{t:T-1}G_t^{(b)} | S_t = s] = \sum_{g \in supp(G_t^{(b)})} \left(\frac{\prod_{k=t}^{T-1}\pi(A_k|S_k) \cdot p(S_{k+1} | S_k, A_k)}{\prod_{k=t}^{T-1}b(A_k|S_k) \cdot p(S_{k+1} | S_k, A_k)} \cdot \prod_{k=t}^{T-1}[b(A_k|S_k) \cdot p(S_{k+1} | S_k, A_k)] \cdot g \right)$$

Canceling like terms gives us

$$= \sum_{g \in supp(G_t^{(b)})} \prod_{k=t}^{T-1}[\pi(A_k|S_k) \cdot p(S_{k+1} | S_k, A_k)] \cdot g$$

Note that, as discussed earlier, $\prod_{k=t}^{T-1}[\pi(A_k|S_k) \cdot p(S_{k+1} | S_k, A_k)]$ is the probability of a given return trajectory occurring under the target policy $\pi$. In other words, we have:

$$= \sum_{g \in supp(G_t^{(b)})} p_{G_t^{(\pi)}}(g) \cdot g$$

The support of $G_t^{(\pi)}$ is the same as the support of $G_t^{(b)}$: the support of either random variable is the set of all state-action sequences (trajectories) possible after a particular time step t. We conclude that

$$E[\rho_{t:T-1}G_t^{(b)} | S_t = s] = \sum_{g \in supp(G_t^{(\pi)})} p_{G_t^{(\pi)}}(g) \cdot g = E[G_t^{(\pi)} | S_t = s] = v_{\pi}(s)$$