Answers.Body: <h3>Short explanation</h3>
  <p>The bias converges asymptotically to zero with more visits of the state <span class="math-container">$s$</span>. The value function is estimated in the following way:
  <span class="math-container">\begin{equation}
  v_{\pi}(s) = \frac{\sum_{t \in \tau(s)} \rho_{t:T(t)-1}G_{t}}{\sum_{t \in \tau(s)} \rho_{t:T(t)-1}}
  \end{equation}</span>
  where <span class="math-container">$\tau(s)$</span> is a set of timestamps at which <span class="math-container">$s$</span> is visited, <span class="math-container">$G_{t}$</span> is the return following state <span class="math-container">$s$</span> at the given timestep <span class="math-container">$t$</span>. If we now consider only the first visit to <span class="math-container">$s$</span> (at timestep 1 to the end of the episode at timestep <span class="math-container">$T$</span>, the equation simplifies to:
  <span class="math-container">\begin{equation}
  v_{\pi}(s) = \frac{\rho_{1:T-1}G_{t}}{\rho_{1:T-1}} = G_{t}
  \end{equation}</span>
  But we get this return by following the behavioral policy <span class="math-container">$b$</span>, so the estimated value function is totally biased towards <span class="math-container">$b$</span>. The bias of the probability of a single return <span class="math-container">$\frac{\rho_{t:T-1} G_{t}}{\sum_{t \in \tau(s)} \rho_{t:T(t)-1}}$</span> decreases the larger <span class="math-container">$\tau(s)$</span> (the more often we visit <span class="math-container">$s$</span>) gets.</p>
  <h3>Detailed example</h3>
  <p>To show an example let's consider a biased coin flip with the probability for heads <span class="math-container">$p(H)=60\%$</span> and tails <span class="math-container">$p(T)=40\%$</span> and the policy tries to predict the outcome of the coin flip. If the outcome is guessed correctly the reward is <span class="math-container">$1$</span> else <span class="math-container">$0$</span>.
  This environment has just two states: the start <span class="math-container">$s_{\text{start}}$</span>, before the coin flip, and the terminal state <span class="math-container">$s_{\text{terminal}}$</span> after the flip. There are also just two possible actions which we call <span class="math-container">$\text{bet-on-H}$</span> and <span class="math-container">$\text{bet-on-T}$</span>, hence the definition of our action space <span class="math-container">$A = \{\text{bet-on-H}, \text{bet-on-T}\}$</span>.
  Now we have the behavioral policy <span class="math-container">$b$</span>:
  <span class="math-container">\begin{equation}
  b(a|s_{\text{start}}) = \begin{cases} 
  0.5 &amp; \text{for } a = \text{bet-on-H} \\
  0.5 &amp; \text{for } a = \text{bet-on-T} \\
  \end{cases}
  \end{equation}</span>
  So the behavioral policy does not take the bias into account. We want to evaluate the target policy which is closer to the optimal (optimal would mean always betting on <span class="math-container">$H$</span>):
  <span class="math-container">\begin{equation}
  v(a|s_{\text{start}}) = \begin{cases} 
  0.9 &amp; \text{for } a = \text{bet-on-H} \\
  0.1 &amp; \text{for } a = \text{bet-on-T} \\
  \end{cases}
  \end{equation}</span>
  First the analytical expected values for both policies without any importance sampling:
  <span class="math-container">\begin{equation}
  v_{b}(s_{\text{start}}) = 0.5 \cdot 0.6 \cdot 1 + 0.5 \cdot 0.4 \cdot 0 + 0.5 \cdot 0.4 \cdot 1 + 0.5 \cdot 0.6 \cdot 0 = 0.5 \\
  v_{\pi}(s_{\text{start}}) =  0.9 \cdot 0.6 \cdot 1 + 0.9 \cdot 0.4 \cdot 0 + 0.1 \cdot 0.6 \cdot 0 + 0.1 \cdot 0.4 \cdot 1 = 0.58
  \end{equation}</span>
  Now, let's consider importance sampling. Since our environment just has one relevant state the factors for importance sampling are
  <span class="math-container">\begin{equation}
  \rho_{t:T-1} = \rho = \frac{\pi(a | s_{\text{start}})}{b(a | s_{\text{start}})} = \begin{cases} 
  \frac{0.9}{0.5} = 1.8 &amp; \text{if } a = \text{bet-on-H} \\
  \frac{0.1}{0.5} = 0.2 &amp; \text{if } a = \text{bet-on-T}
   \end{cases}
  \end{equation}</span>
  The value function including weighted importance sampling ratios is given by
  <span class="math-container">\begin{equation}
  v_{\pi} = \frac{\sum_{t \in \tau(s)} \rho_{t:T(t)-1}G_{t}}{\sum_{t \in \tau(s)} \rho_{t:T-1}} = \frac{\sum_{t \in \tau(s_{\text{start}})} \rho G_{t}}{\sum_{t \in \tau(s_{\text{start}})} \rho}
  \end{equation}</span>
  where <span class="math-container">$\tau(s)$</span> is the the set of all visits to <span class="math-container">$s$</span>, this reduces in our environment to <span class="math-container">$\tau(s_{\text{start}})$</span>.
  I wrote a little python script showing the bias just implementing all the information outlined above</p>
  <pre><code>import numpy as np
  import matplotlib.pyplot as plt
  
  probas_experiment = [0.6, 0.4]
  probas_b = [0.5, 0.5]
  probas_pi = [0.9, 0.1]
  sampling_factors = [ppi/pb for (ppi, pb) in zip(probabilities_pi, probabilities_b)]
  
  no_flips = 10000
  
  coin_flips = [np.random.choice([0, 1], p=probas_experiment) for _ in range(no_flips)]
  predicted_coin_flips = [np.random.choice([0, 1], p=probas_b) for _ in range(no_flips)]
  weighted_returns = [(c == p) * sampling_factors[p] for (c,p) in 
  zip(coin_flips, predicted_coin_flips)]
  plt.plot(range(1, no_flips + 1), np.cumsum(weighted_returns) / np.arange(1, no_flips + 1), label=&quot;imp. sampled returns&quot;)
  plt.plot(range(1, no_flips + 1), np.cumsum(weighted_returns) / np.arange(1, no_flips + 1), label=&quot;simulation&quot;)
  plt.plot(range(1, no_flips + 1), 0.5*np.ones(no_flips), label=&quot;expected returns b&quot;)
  plt.plot(range(1, no_flips + 1), 0.58*np.ones(no_flips), label=&quot;expected returns pi&quot;)
  plt.xlabel(&quot;number of executed coin flips&quot;)
  plt.ylabel(&quot;averaged returns&quot;)
  plt.legend()
  </code></pre>
  <p><a href="https://i.sstatic.net/5Qjy5.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5Qjy5.png" alt="enter image description here" /></a>
  You can see the bias towards <span class="math-container">$b$</span> in the beginning while it decreases with more and more coin flips.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-17T05:02:02.833Z
Answers.Text: Excellent answer, thank you! I'm updating the question with a clarification of what exactly I was missing.
Answers.UserDisplayName: user118967
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-16T11:09:21.327Z
Answers.LastActivityDate: 2023-02-16T11:09:21.327Z
Answers.UserDisplayName: pythonic833
Body: <p>On Section 5.5 (page 105) of Sutton &amp; Barto's <a href="http://www.incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">&quot;Reinforcement Learning: An Introduction&quot;</a>, they discuss the off-policy Monte Carlo method for learning the value function of a target policy <span class="math-container">$\pi$</span> from a behavior policy <span class="math-container">$b$</span> using ordinary importance sampling and weighted importance sampling.</p>
  <p>At some point they say the weighted importance sampling estimator for <span class="math-container">$v_\pi(s)$</span> (the target policy value) has an expectation equal to the <em>behavior</em> policy value <span class="math-container">$v_b(s)$</span>, and is therefore biased. So far, so good.</p>
  <p>However, they then say that <em>the bias asymptotically converges to zero</em>. I am confused by this, since in this scenario (value estimation) the policies are fixed and <span class="math-container">$v_\pi(s)$</span> is distinct from <span class="math-container">$v_b(s)$</span> (more precisely, they are not required to be the same and in most cases will not be). If the estimator's expectation is always <span class="math-container">$v_b(s)$</span>, then it is <em>asymptotically</em> equal to <span class="math-container">$v_b(s)$</span>, which means it is <em>asymptotically distinct</em> (in principle) from <span class="math-container">$v_\pi(s)$</span>, and therefore the bias would not asymptotically go to zero.</p>
  <p>What am I missing?</p>
  <p><strong>Update after answer</strong>: what I was missing is that I was interpreting &quot;asymptotically the estimator converges to <span class="math-container">$v_b$</span>&quot; incorrectly. If we interpret &quot;asymptotically&quot; in the (incorrect) sense of &quot;obtaining infinitely many estimations over a fixed number of <span class="math-container">$n$</span> episodes and averaging the returns&quot;, then indeed that is going to be biased towards <span class="math-container">$v_b$</span> (and in fact, the expectation will be exactly <span class="math-container">$v_b$</span> if we estimate using <span class="math-container">$n = 1$</span>). The correct interpretation of &quot;asymptotic&quot; is doing a single estimation using an increasingly larger number of <span class="math-container">$m$</span> episodes. The expectation of that estimation converges to <span class="math-container">$v_\pi$</span> as <span class="math-container">$m$</span> goes to infinity.</p>
  
Tags: <reinforcement-learning><sutton-barto><monte-carlo-methods><off-policy-methods><importance-sampling>
Title: How does off-policy Monte Carlo weighted importance sampling bias converge to zero (Sutton & Barto Section 5.5)
UserDisplayName: user118967
ThreadText: # How does off-policy Monte Carlo weighted importance sampling bias converge to zero (Sutton & Barto Section 5.5)
  
  (Asked by: username_0 on 2023-01-26)
  
  On Section 5.5 (page 105) of Sutton & Barto's ["Reinforcement Learning: An Introduction"](http://www.incompleteideas.net/book/the-book-2nd.html), they discuss the off-policy Monte Carlo method for learning the value function of a target policy $\pi$ from a behavior policy $b$ using ordinary importance sampling and weighted importance sampling.
  
  At some point they say the weighted importance sampling estimator for $v\_\pi(s)$ (the target policy value) has an expectation equal to the *behavior* policy value $v\_b(s)$, and is therefore biased. So far, so good.
  
  However, they then say that *the bias asymptotically converges to zero*. I am confused by this, since in this scenario (value estimation) the policies are fixed and $v\_\pi(s)$ is distinct from $v\_b(s)$ (more precisely, they are not required to be the same and in most cases will not be). If the estimator's expectation is always $v\_b(s)$, then it is *asymptotically* equal to $v\_b(s)$, which means it is *asymptotically distinct* (in principle) from $v\_\pi(s)$, and therefore the bias would not asymptotically go to zero.
  
  What am I missing?
  
  **Update after answer**: what I was missing is that I was interpreting "asymptotically the estimator converges to $v\_b$" incorrectly. If we interpret "asymptotically" in the (incorrect) sense of "obtaining infinitely many estimations over a fixed number of $n$ episodes and averaging the returns", then indeed that is going to be biased towards $v\_b$ (and in fact, the expectation will be exactly $v\_b$ if we estimate using $n = 1$). The correct interpretation of "asymptotic" is doing a single estimation using an increasingly larger number of $m$ episodes. The expectation of that estimation converges to $v\_\pi$ as $m$ goes to infinity.
  
  **Tags:** reinforcement-learning, sutton-barto, monte-carlo-methods, off-policy-methods, importance-sampling
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-02-16. Score: 2 | Accepted answer
  
  ### Short explanation
  
  The bias converges asymptotically to zero with more visits of the state $s$. The value function is estimated in the following way:
  \begin{equation}
  v\_{\pi}(s) = \frac{\sum\_{t \in \tau(s)} \rho\_{t:T(t)-1}G\_{t}}{\sum\_{t \in \tau(s)} \rho\_{t:T(t)-1}}
  \end{equation}
  where $\tau(s)$ is a set of timestamps at which $s$ is visited, $G\_{t}$ is the return following state $s$ at the given timestep $t$. If we now consider only the first visit to $s$ (at timestep 1 to the end of the episode at timestep $T$, the equation simplifies to:
  \begin{equation}
  v\_{\pi}(s) = \frac{\rho\_{1:T-1}G\_{t}}{\rho\_{1:T-1}} = G\_{t}
  \end{equation}
  But we get this return by following the behavioral policy $b$, so the estimated value function is totally biased towards $b$. The bias of the probability of a single return $\frac{\rho\_{t:T-1} G\_{t}}{\sum\_{t \in \tau(s)} \rho\_{t:T(t)-1}}$ decreases the larger $\tau(s)$ (the more often we visit $s$) gets.
  
  ### Detailed example
  
  To show an example let's consider a biased coin flip with the probability for heads $p(H)=60\%$ and tails $p(T)=40\%$ and the policy tries to predict the outcome of the coin flip. If the outcome is guessed correctly the reward is $1$ else $0$.
  This environment has just two states: the start $s\_{\text{start}}$, before the coin flip, and the terminal state $s\_{\text{terminal}}$ after the flip. There are also just two possible actions which we call $\text{bet-on-H}$ and $\text{bet-on-T}$, hence the definition of our action space $A = \{\text{bet-on-H}, \text{bet-on-T}\}$.
  Now we have the behavioral policy $b$:
  \begin{equation}
  b(a|s\_{\text{start}}) = \begin{cases}
  0.5 & \text{for } a = \text{bet-on-H} \\
  0.5 & \text{for } a = \text{bet-on-T} \\
  \end{cases}
  \end{equation}
  So the behavioral policy does not take the bias into account. We want to evaluate the target policy which is closer to the optimal (optimal would mean always betting on $H$):
  \begin{equation}
  v(a|s\_{\text{start}}) = \begin{cases}
  0.9 & \text{for } a = \text{bet-on-H} \\
  0.1 & \text{for } a = \text{bet-on-T} \\
  \end{cases}
  \end{equation}
  First the analytical expected values for both policies without any importance sampling:
  \begin{equation}
  v\_{b}(s\_{\text{start}}) = 0.5 \cdot 0.6 \cdot 1 + 0.5 \cdot 0.4 \cdot 0 + 0.5 \cdot 0.4 \cdot 1 + 0.5 \cdot 0.6 \cdot 0 = 0.5 \\
  v\_{\pi}(s\_{\text{start}}) = 0.9 \cdot 0.6 \cdot 1 + 0.9 \cdot 0.4 \cdot 0 + 0.1 \cdot 0.6 \cdot 0 + 0.1 \cdot 0.4 \cdot 1 = 0.58
  \end{equation}
  Now, let's consider importance sampling. Since our environment just has one relevant state the factors for importance sampling are
  \begin{equation}
  \rho\_{t:T-1} = \rho = \frac{\pi(a | s\_{\text{start}})}{b(a | s\_{\text{start}})} = \begin{cases}
  \frac{0.9}{0.5} = 1.8 & \text{if } a = \text{bet-on-H} \\
  \frac{0.1}{0.5} = 0.2 & \text{if } a = \text{bet-on-T}
  \end{cases}
  \end{equation}
  The value function including weighted importance sampling ratios is given by
  \begin{equation}
  v\_{\pi} = \frac{\sum\_{t \in \tau(s)} \rho\_{t:T(t)-1}G\_{t}}{\sum\_{t \in \tau(s)} \rho\_{t:T-1}} = \frac{\sum\_{t \in \tau(s\_{\text{start}})} \rho G\_{t}}{\sum\_{t \in \tau(s\_{\text{start}})} \rho}
  \end{equation}
  where $\tau(s)$ is the the set of all visits to $s$, this reduces in our environment to $\tau(s\_{\text{start}})$.
  I wrote a little python script showing the bias just implementing all the information outlined above
  
  ```
  import numpy as np
  import matplotlib.pyplot as plt
  
  probas_experiment = [0.6, 0.4]
  probas_b = [0.5, 0.5]
  probas_pi = [0.9, 0.1]
  sampling_factors = [ppi/pb for (ppi, pb) in zip(probabilities_pi, probabilities_b)]
  
  no_flips = 10000
  
  coin_flips = [np.random.choice([0, 1], p=probas_experiment) for _ in range(no_flips)]
  predicted_coin_flips = [np.random.choice([0, 1], p=probas_b) for _ in range(no_flips)]
  weighted_returns = [(c == p) * sampling_factors[p] for (c,p) in 
  zip(coin_flips, predicted_coin_flips)]
  plt.plot(range(1, no_flips + 1), np.cumsum(weighted_returns) / np.arange(1, no_flips + 1), label="imp. sampled returns")
  plt.plot(range(1, no_flips + 1), np.cumsum(weighted_returns) / np.arange(1, no_flips + 1), label="simulation")
  plt.plot(range(1, no_flips + 1), 0.5*np.ones(no_flips), label="expected returns b")
  plt.plot(range(1, no_flips + 1), 0.58*np.ones(no_flips), label="expected returns pi")
  plt.xlabel("number of executed coin flips")
  plt.ylabel("averaged returns")
  plt.legend()
  
  ```
  
  [![enter image description here](https://i.sstatic.net/5Qjy5.png)](https://i.sstatic.net/5Qjy5.png)
  You can see the bias towards $b$ in the beginning while it decreases with more and more coin flips.
  
  > **Comments:**
  > **username_0**: Excellent answer, thank you! I'm updating the question with a clarification of what exactly I was missing.  
  
  ---
  
  