1
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

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)$

Improve this answer
$\endgroup$
4
  • $\begingroup$ That was clear explanation. But, could you show how the terms cancel? $\endgroup$
    – Zach Zhao
    Commented Dec 19, 2018 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
    Commented Dec 19, 2018 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
    Commented Dec 20, 2018 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
    Commented Dec 20, 2018 at 19:28
0
$\begingroup$

$\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 $

Improve this answer
$\endgroup$

You must log in to answer this question.

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