With Monte Carlo off-policy learning what do we correct by using importance sampling?

Question

I do not understand the link of importance sampling to Monte Carlo off-policy learning.

We estimate a value using sampling on whole episodes, and we take these values to construct the target policy.

So, it is possible that in the target policy, we could have state values (or state action values) coming from different trajectories.

If the above is true, and if the values depend on the subsequent actions (the behavior policy), there is something wrong there, or else, better, something I do not understand.

Linking this question with importance sampling, do we use this ro value to correct this inconsistency?

Any clarification is welcome.

Answer 1

Recall that the definition of a value function is $$v_\pi(s) = \mathbb{E}\left[G_t | S_t = s\right]\;.$$ That is, the expected future returns given from state $s$ at time $t$ when we follow our policy $\pi$ -- i.e. our trajectory is generated according to $\pi$.

Using Monte Carlo methods we typically will estimate our value function by looking at the empirical mean of rewards we see throughout many training episodes, i.e. we will generate many episodes, keep track of all the rewards we see from state $s$ onwards across all of our episodes (this may be the first visit method or the all visit methods) and use these to approximate the expectation that is our value function.

The key here is that to approximate the value function in this way, then the episodes must be generated according to our policy $\pi$. If we choose the actions in an episode according to some other policy $\beta$ then we cannot use these episodes to approximate the expectation directly. As an example, this would be like trying to approximate the mean of a Normal(0, 1) distribution with data drawn from a Normal(10, 1) distribution.

To account for the fact that the actions came from a different distribution, we have to reweight the returns according to an importance sampling ratio. To see why we need importance sampling, see this question/answer.

Answer 2

We estimate a value using sampling on whole episodes, and we take this values to construct the target policy.

The crucial bit that you are missing is that there is no single value of $V(s)$ (or $Q(s,a)$) of a state (or a state action pair). These value functions are always defined with respect to some policy $\pi(a|s)$ and is given the notation of $V^{\pi}(s)$ (or $Q^{\pi}(s,a)$).

The off-policy learning problems are arising when you have two policies: the generation policy $\mu(a|s)$ and the target policy $\pi(a|s)$. Your MC sampling data came from an agent following $\mu$, while you want to improve your target policy $\pi$. It is pretty straightforward from here that you'd need to weight your calculations with factors like $\frac{\pi(a_i|s_i)}{\mu(a_i|s_i)}$ - that's what importance sampling is.