How does off-policy Monte Carlo weighted importance sampling bias converge to zero (Sutton & Barto Section 5.5)

Question

On Section 5.5 (page 105) of Sutton & Barto's "Reinforcement Learning: An Introduction", 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.

Answer 1

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()

You can see the bias towards $b$ in the beginning while it decreases with more and more coin flips.