Answers.Body: <p>The expected value notation <span class="math-container">$\mathbb{E}$</span> can easily cause mistakes, which I think is what happened here. It's not always clear what exact <em>group of things</em> and <em>probably distribution</em> 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 <span class="math-container">$X$</span> as a placeholder and <span class="math-container">$x$</span> as an action or even trajectory.</p>
  <p>Disentangling everything, we can write:</p>
  <p><span class="math-container">$$\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]$$</span></p>
  <p>with symbols defined as</p>
  <ul>
  <li><span class="math-container">$H$</span> for the set of possible trajectories</li>
  <li><span class="math-container">$X$</span> for any placeholder variable</li>
  <li><span class="math-container">$x(h)$</span> for the placeholder value for trajectory <span class="math-container">$h$</span></li>
  <li><span class="math-container">$P_\pi(h)$</span> and <span class="math-container">$P_b(h)$</span> for the respective on-policy probabilities for trajectory <span class="math-container">$h$</span></li>
  <li><span class="math-container">$\rho(h)$</span> the ratio between them</li>
  </ul>
  <p>Looking at things this way, there are no issues with multiple trajectories potentially yielding the same value, since we consider each possible trajectory separately.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-05T18:04:01.947Z
Answers.Text: I see now. Unfortunately, right before this calculation, there was no mention of trajectories, it seemed to come out of the blue.
Answers.UserDisplayName: ArminAshrafi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-04T17:45:03.613Z
Answers.LastActivityDate: 2022-10-05T20:42:28.050Z
Answers.LastEditDate: 2022-10-05T20:42:28.050Z
Answers.UserDisplayName: KarelPeeters
Body: <p>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 <span class="math-container">$G_t$</span>, given <span class="math-container">$S_t = s$</span> under our target policy: <span class="math-container">$$\mathbb{E}_{\pi}[G_t|S_t = s]$$</span></p>
  <p>So here, our random variable is <span class="math-container">$X = G_t$</span>, meaning returns of states in trajectories/episodes.</p>
  <p>Since we want to be able to explore, we use a behavior policy <span class="math-container">$b$</span>, and therefore sample trajectories(episodes) from it. Computing sample averages doesn't work, as it would converge to <span class="math-container">$$\mathbb{E}_{b}[G_t|S_t = s]$$</span> and not <span class="math-container">$$\mathbb{E}_{\pi}[G_t|S_t = s]$$</span>.</p>
  <p>Hence, we use Importance sampling, and here is my understanding of how it works:</p>
  <p><span class="math-container">$$ \mathbb{E}_{\pi}[X] = \sum_{x \in X} x\pi(x) = \sum_{x \in X} x\pi(x) \frac{b(x)}{b(x)} \implies $$</span></p>
  <p><span class="math-container">$$=\sum_{x \in X} x\frac{\pi(x)}{b(x)}b(x) = \sum_{x \in X} x\rho(x)b(x) $$</span></p>
  <p>and in this way, if we know <span class="math-container">$\rho(x)$</span>, we can do this: <span class="math-container">$$\frac{1}{n}\sum_{i=1}^{n}\rho(x)x_i \approx \mathbb{E}_{\pi}[X], x \sim b$$</span>.</p>
  <p>In Sutton &amp; Barto, in order to calculate this <span class="math-container">$\rho(x)$</span>, the ratio between the probabilities  of the occurrence of a specific trajectory is calculated: <span class="math-container">$$P(A_tS_{t+1}A_{t+1}...S_T|S_t,A_t)$$</span></p>
  <p>and then the ratio is calculated.</p>
  <p>How is this the same as <span class="math-container">$G_t$</span>? if we want to calculate the return of a specific return <span class="math-container">$G_t$</span>, 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.</p>
  <p>Where is my gap in understanding?</p>
  
Tags: <reinforcement-learning><sutton-barto><monte-carlo-methods><off-policy-methods><importance-sampling>
Title: In off-policy MC learning, why is the probability of sampling a trajectory the same as having a return?
UserDisplayName: ArminAshrafi
ThreadText: # In off-policy MC learning, why is the probability of sampling a trajectory the same as having a return?
  
  (Asked by: username_0 on 2022-10-02)
  
  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?
  
  **Tags:** reinforcement-learning, sutton-barto, monte-carlo-methods, off-policy-methods, importance-sampling
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-10-04. Score: 1 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_0**: I see now. Unfortunately, right before this calculation, there was no mention of trajectories, it seemed to come out of the blue.  
  
  ---
  
  