# In off-policy MC learning, why is the probability of sampling a trajectory the same as having a return?

In Sutton and Barto's RL book, in the section for off-policy learning, we would like to find the expected value of the random variable $$G_t$$, given $$S_t = s$$ under our target policy: $$\mathbb{E}_{\pi}[G_t|S_t = s]$$

So here, our random variable is $$X = G_t$$, meaning returns of states in trajectories/episodes.

Since we want to be able to explore, we use a behavior policy $$b$$, and therefore sample trajectories(episodes) from it. Computing sample averages doesn't work, as it would converge to $$\mathbb{E}_{b}[G_t|S_t = s]$$ and not $$\mathbb{E}_{\pi}[G_t|S_t = s]$$.

Hence, we use Importance sampling, and here is my understanding of how it works:

$$\mathbb{E}_{\pi}[X] = \sum_{x \in X} x\pi(x) = \sum_{x \in X} x\pi(x) \frac{b(x)}{b(x)} \implies$$

$$=\sum_{x \in X} x\frac{\pi(x)}{b(x)}b(x) = \sum_{x \in X} x\rho(x)b(x)$$

and in this way, if we know $$\rho(x)$$, we can do this: $$\frac{1}{n}\sum_{i=1}^{n}\rho(x)x_i \approx \mathbb{E}_{\pi}[X], x \sim b$$.

In Sutton & Barto, in order to calculate this $$\rho(x)$$, the ratio between the probabilities of the occurrence of a specific trajectory is calculated: $$P(A_tS_{t+1}A_{t+1}...S_T|S_t,A_t)$$

and then the ratio is calculated.

How is this the same as $$G_t$$? if we want to calculate the return of a specific return $$G_t$$, we could have many trajectories that give the same return, so we would be underestimating the probability of that return if we find the probability of occurrence for a trajectory.

Where is my gap in understanding?

The expected value notation $$\mathbb{E}$$ can easily cause mistakes, which I think is what happened here. It's not always clear what exact group of things and probably distribution the expected value is taken over. Your section on importance sampling is wrong: here the expected value should be taken over all trajectories with their on-policy distribution. It seems like you're mixing usages of $$X$$ as a placeholder and $$x$$ as an action or even trajectory.

Disentangling everything, we can write:

$$\mathbb{E}_\pi[X] = \sum_{h\in H} x(h) P_\pi(h) = \sum_{h\in H} x(h) \frac{P_\pi(h)}{P_b(h)}P_b(h) = \sum_{h\in H} x(h) \rho(h) P_b(h) = \mathbb{E}_b[\rho X]$$

with symbols defined as

• $$H$$ for the set of possible trajectories
• $$X$$ for any placeholder variable
• $$x(h)$$ for the placeholder value for trajectory $$h$$
• $$P_\pi(h)$$ and $$P_b(h)$$ for the respective on-policy probabilities for trajectory $$h$$
• $$\rho(h)$$ the ratio between them

Looking at things this way, there are no issues with multiple trajectories potentially yielding the same value, since we consider each possible trajectory separately.

• I see now. Unfortunately, right before this calculation, there was no mention of trajectories, it seemed to come out of the blue. Oct 5, 2022 at 18:04