This is a proof of the per-decision importance sampling (theorem 1) from the appendix of:


enter image description here

I should give some background that this is deriving a Monte Carlo importance sampling theorem in reinforcement learning.

I am stuck at the step in brackets where the expectation is split into a product. I know this is possible for independent variables inside the expectation. Is it just that policies after the reward are independent of the reward and the policies are all independent by the Markov assumption and conditioning on state??? If so some insight as to this would be much appreciated because I don't understand how the earlier policies are not independent.

Or maybe it's something else.

Any insight much appreciated!

Many thanks.


1 Answer 1


Is it just that policies after the reward are independent of the reward and the policies are all independent by the Markov assumption and conditioning on state???

Yes, this is indeed the case.

In this paper, note that the $\pi_i$ and $b_i$ terms do not refer to different policies. As described right above Equation (3) in the paper, they are used as shorthand notation for $\pi(s_t, a_t)$ and $b(s_t, a_t)$, respectively, where $\pi$ is the target policy (the policy about which we wish to learn), and $b$ is the behaviour policy.

These equations are about the case where, using the behaviour policy $b$, we generate a complete trajectory of $T$ time steps (a complete episode). So, across the entire episode, the behaviour policy $b$ and the target policy $\pi$ are consistently the same. These policies are completely fixed and determined before we start the episode, so they cannot be dependent on any of the rewards observed during that episode.

For both of the policies, $\pi(s_t, a_t)$ and $b(s_t, a_t)$ denote the probability assigned to the action that we happened to select in practice ($a_t$) when presented with a state $s_t$. Such probabilities are typically only dependent on precisely the two things you see in parentheses; $s_t$ and $a_t$. We normally do not have policies that are also dependent on earlier history of states, actions or policies (this is indeed not necessary due to the assumption of the Markov property).

  • $\begingroup$ I see, but if the policies are dependent on as you say the things in parentheses s_t and a_t, I don't see why the second expectation I've highlighted keeps both policies from t+1 to t+k-1?? Surely these could be taken out as well and the reward at time t+k as shown in the equation would only need policies at t+k-1? I'm not clear why later policies are taken out and earlier ones are kept in the expectation rather than just the policies at the timestep before the reward? $\endgroup$
    – olliejday
    Commented Sep 7, 2018 at 15:59
  • $\begingroup$ @olliejday The expectation of a product of lots of terms can be split up in all kinds of ways. Here they split it up into two particular expectations of products. I think what you are suggesting would be possible too, but the particular way in which they split it up simply happened to be convenient / necessary for subsequent steps in the proof. $\endgroup$ Commented Sep 7, 2018 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.