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

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.

### Short explanation

The bias converges asymptotically to zero with more visits of the state $$s$$. The value function is estimated in the following way: $$$$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}}$$$$ 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: $$$$v_{\pi}(s) = \frac{\rho_{1:T-1}G_{t}}{\rho_{1:T-1}} = G_{t}$$$$ 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$$: $$$$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}$$$$ 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$$): $$$$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}$$$$ First the analytical expected values for both policies without any importance sampling: $$$$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$$$$ Now, let's consider importance sampling. Since our environment just has one relevant state the factors for importance sampling are $$$$\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}$$$$ The value function including weighted importance sampling ratios is given by $$$$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}$$$$ 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.

• Excellent answer, thank you! I'm updating the question with a clarification of what exactly I was missing. Feb 17, 2023 at 5:02