Answers.Body: <p>In Tabular Q-learning the update is as follows </p>
  
  <p><span class="math-container">$$Q(s,a) = Q(s,a) + \alpha \left[R_{t+1} + \gamma \max_aQ(s',a) - Q(s,a) \right]\;.$$</span></p>
  
  <p>Now, as we are interested in learning about the optimal policy, this would correspond to the <span class="math-container">$\max_aQ(s',a)$</span> term in the TD target because that is how the optimal policy chooses its actions - i.e. <span class="math-container">$\pi_*(a|s) = \arg\max_aQ_*(s,a)$</span>, 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. </p>
  
  <p>The action <span class="math-container">$a$</span> in the update rule, i.e. the action we chose in state <span class="math-container">$s$</span> to receive the reward <span class="math-container">$R_{t+1}$</span>, was chosen according to some non-optimal policy, e.g. <span class="math-container">$\epsilon$</span>-greedy. However, as the <span class="math-container">$Q$</span> function is defined as the expected returns assuming we are in state <span class="math-container">$s$</span> and <em>have taken action <span class="math-container">$a$</span></em> -- we thus don't need an importance sampling ratio for the <span class="math-container">$R_{t+1}$</span> term, even though it was generated from an action that the optimal policy might not have taken, because we are only updating the <span class="math-container">$Q$</span> function for state <span class="math-container">$s$</span> and action <span class="math-container">$a$</span>, and by the definition of a <span class="math-container">$Q$</span> function it is assumed that we have taken action <span class="math-container">$a$</span> as we condition on this. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-14T16:25:56.797Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-14T16:21:39.347Z
Answers.LastActivityDate: 2020-06-14T16:21:39.347Z
Answers.UserDisplayName: David
Body: <p>Why don't we use an importance sampling ratio in Q-Learning, even though Q-Learning is an off-policy method? </p>
  
  <p>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 <span class="math-container">$\mathbb{E}[X]$</span>. </p>
  
  <p>Mathematically an expectation is defined as 
  <span class="math-container">$$\mathbb{E}_{x \sim p(x)}[X] = \sum_{x = \infty}^\infty x p(x)\;;$$</span>
  where <span class="math-container">$p(x)$</span> denotes our probability mass function, and we can approximate this by
  <span class="math-container">$$\mathbb{E}_{x \sim p(x)}[X] \approx \frac{1}{n} \sum_{i=1}^nx_i\;;$$</span>
  where <span class="math-container">$x_i$</span> were simulated from <span class="math-container">$p(x)$</span>. </p>
  
  <p>Now, we can re-write the expectation from earlier as </p>
  
  <p><span class="math-container">$$\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]\;;$$</span>
  and so we can calculate the expectation using Monte Carlo averaging 
  <span class="math-container">$$\mathbb{E}_{x \sim p(x)}[X] \approx \frac{1}{n} \sum_{i=1}^nx_i \frac{p(x)}{q(x)}\;;$$</span>
  where the data <span class="math-container">$x_i$</span> are now simulated from <span class="math-container">$q(x)$</span>. </p>
  
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-13T20:37:44.630Z
Comments.Text: 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
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-13T20:41:05.417Z
Comments.Text: I was asking for clarification as to whether my line of reasoning is correct, if it is then I can answer my own question.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-13T20:53:11.390Z
Comments.Text: 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).
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-14T09:13:56.433Z
Comments.Text: Yes, will answer next time I am on my laptop. Thanks for the comments Neil.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-14T09:48:14.470Z
Comments.Text: Also see: https://stats.stackexchange.com/q/335396/144483
Comments.UserDisplayName: Dennis Soemers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-14T13:17:28.187Z
Comments.Text: I found that answer but unfortunately didn’t find the answer very useful to me, it was what confused me in the first place.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-13T18:21:43.257Z
Comments.Text: @NeilSlater 3 years later of being in the field of DRL and nothing sums it up better than "although often in _insert DRL algorithm_ this is ignored"
Comments.UserDisplayName: David
Tags: <reinforcement-learning><q-learning><importance-sampling><bellman-equations>
Title: Why we don't use importance sampling in tabular Q-Learning?
UserDisplayName: David
ThreadText: # Why we don't use importance sampling in tabular Q-Learning?
  
  (Asked by: username_0 on 2020-06-13)
  
  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?
  
  **Tags:** reinforcement-learning, q-learning, importance-sampling, bellman-equations
  > **Comments:**
  > **username_1**: 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  
  > **username_0**: I was asking for clarification as to whether my line of reasoning is correct, if it is then I can answer my own question.  
  > **username_1**: 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).  
  > **username_0**: Yes, will answer next time I am on my laptop. Thanks for the comments Neil.  
  > **username_2**: Also see: https://stats.stackexchange.com/q/335396/144483  
  > **username_0**: I found that answer but unfortunately didn’t find the answer very useful to me, it was what confused me in the first place.  
  > **username_0**: @NeilSlater 3 years later of being in the field of DRL and nothing sums it up better than "although often in _insert DRL algorithm_ this is ignored"  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-06-14. Score: 3 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_3**: 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.  
  
  ---
  
  