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

Question

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?

Answer 1

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.