Why we don't use importance sampling in tabular Q-Learning?

Why don't we use an importance sampling ratio in Q-Learning, even though Q-Learning is an off-policy method?

Importance sampling is used to calculate expectation of a random variable by using data not drawn from the distribution. Consider taking a Monte Carlo average to calculate $$\mathbb{E}[X]$$.

Mathematically an expectation is defined as $$\mathbb{E}_{x \sim p(x)}[X] = \sum_{x = \infty}^\infty x p(x)\;;$$ where $$p(x)$$ denotes our probability mass function, and we can approximate this by $$\mathbb{E}_{x \sim p(x)}[X] \approx \frac{1}{n} \sum_{i=1}^nx_i\;;$$ where $$x_i$$ were simulated from $$p(x)$$.

Now, we can re-write the expectation from earlier as

$$\mathbb{E}_{x \sim p(x)}[X] = \sum_{x = \infty}^\infty x p(x) = \sum_{x = \infty}^\infty x \frac{p(x)}{q(x)} q(x) = \mathbb{E}_{x\sim q(x)}\left[ X\frac{p(X)}{q(X)}\right]\;;$$ and so we can calculate the expectation using Monte Carlo averaging $$\mathbb{E}_{x \sim p(x)}[X] \approx \frac{1}{n} \sum_{i=1}^nx_i \frac{p(x)}{q(x)}\;;$$ where the data $$x_i$$ are now simulated from $$q(x)$$.

Typically importance sampling is used in RL when we use off-policy methods, i.e. the policy we use to calculate our actions is different from the policy we want to evaluate. Thus, I wonder why we don't use the importance sampling ratio in Q-learning, even though it is considered to be an off-policy method?

• Are you are laying out arguments for not using importance sampling in single-step Q-learning that you think apply, and would like to know if you are correct? It is not clear, but I don't see any argument here for using importance sampling . . . could you maybe make it clearer. "I'm in need of a sanity check" implies it I think, but needs to be more direct IMO – Neil Slater Jun 13 '20 at 20:37
• I was asking for clarification as to whether my line of reasoning is correct, if it is then I can answer my own question. – David Ireland Jun 13 '20 at 20:41
• So you intend to answer this question yourself? OK, then it is roughly correct IMO. More correctly the TD update is estimating a greedy target policy (which eventually becomes the optimal policy). As you suggest though, none of the variables used in the update equation vary depending on the behaviour policy, therefore no sample weighting is required. If you use n-step updates then it gets more complicated, and if you use approximation then the distribution of $(s,a)$ pairs that get updated can also play a part (although often in DQN this is ignored). – Neil Slater Jun 13 '20 at 20:53
• Yes, will answer next time I am on my laptop. Thanks for the comments Neil. – David Ireland Jun 14 '20 at 9:13
• I found that answer but unfortunately didn’t find the answer very useful to me, it was what confused me in the first place. – David Ireland Jun 14 '20 at 13:17

$$Q(s,a) = Q(s,a) + \alpha \left[R_{t+1} + \gamma \max_aQ(s',a) - Q(s,a) \right]\;.$$
Now, as we are interested in learning about the optimal policy, this would correspond to the $$\max_aQ(s',a)$$ term in the TD target because that is how the optimal policy chooses its actions - i.e. $$\pi_*(a|s) = \arg\max_aQ_*(s,a)$$, so eventually the greedy TD update would be greedy with respect to the optimal state-action value function due to the guaranteed convergence of Q-learning.
The action $$a$$ in the update rule, i.e. the action we chose in state $$s$$ to receive the reward $$R_{t+1}$$, was chosen according to some non-optimal policy, e.g. $$\epsilon$$-greedy. However, as the $$Q$$ function is defined as the expected returns assuming we are in state $$s$$ and have taken action $$a$$ -- we thus don't need an importance sampling ratio for the $$R_{t+1}$$ term, even though it was generated from an action that the optimal policy might not have taken, because we are only updating the $$Q$$ function for state $$s$$ and action $$a$$, and by the definition of a $$Q$$ function it is assumed that we have taken action $$a$$ as we condition on this.