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 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. 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). Jun 13 '20 at 20:53
• Yes, will answer next time I am on my laptop. Thanks for the comments Neil. 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. Jun 14 '20 at 13:17

In Tabular Q-learning the update is as follows

$$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.

• For people that are not very familiar with IS, maybe you should explain how you would apply IS in Q-learning and why you had the question in the first place (i.e. maybe a brief introduction to IS would be nice). I am not very familiar with the details of IS, so I am not seeing exactly why and how you would apply IS in Q-learning, although I understand that there are two policies (like in IS). Anyway, maybe someone that is very familiar with IS will be satisfied with your answer.
– nbro
Jun 14 '20 at 16:25