Answers.Body: <blockquote>
  <p>Since <span class="math-container">$A_t$</span> is already determined (because we are calculating <span class="math-container">$Q(S_t,A_t)$</span>), I think <span class="math-container">$\pi(A_t|S_t)$</span> is definitely 1. But what about <span class="math-container">$\mu (A_t|S_t)$</span>? Is it 1 or not?</p>
  </blockquote>
  <p>You could assign values of 1 to each to get the right answer, but the situation is different. You can see that more clearly in the definition of action value, <span class="math-container">$q(s,a)$</span>:</p>
  <p><span class="math-container">$$q_{\pi}(s,a) = \mathbb{E}_{\pi}[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1}|S_t=s, A_t=a]$$</span></p>
  <p>The condition on the expectation <span class="math-container">$|S_t=s, A_t=a$</span> means that the value of <span class="math-container">$A_t$</span> is already assumed. There is no need to know or use the associated probability, and no need to adjust between probabilities of different policies when estimating returns for the first action choice.</p>
  <p>In addition, the last action choice used to bootstrap in Q learning is always the maximising action over current Q values. That is an <em>on-policy</em> choice with respect to the target policy <span class="math-container">$\pi$</span>, so does not need to be adjusted for.</p>
  <p>For single-step Q learning, there is no need to use importance sampling to adjust for policy differences between behaviour and target policies. The correct update equation rule is:</p>
  <p><span class="math-container">$$ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left( R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t) \right). $$</span></p>
  <p>This does change for n-step updates, where you do need to take account of differences in action choice between target and behaviour policies for <span class="math-container">$A_{t+1}, A_{t+2}$</span> up to <span class="math-container">$A_{t+n-1}$</span>. However, you should bear in mind that <span class="math-container">$\pi(a|s)$</span> is zero for any non-maximising action - if you use weighted importance sampling then any trajectory with an exploring action before calculating the TD update contributes zero update.</p>
  <p>So, if you are calculating over longer trajectories, in e.g. Q(<span class="math-container">$\lambda$</span>), it is common to see this simplified to a logical test and some kind of shortcut update. You rarely see explicit use of importance sampling - with probability calculations and ratios - in Q learning.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-21T07:14:54.710Z
Answers.LastActivityDate: 2021-04-21T15:08:05.907Z
Answers.LastEditDate: 2021-04-21T15:08:05.907Z
Answers.UserDisplayName: Neil Slater
Body: <p>The off-policy TD learning control using state value function from <a href="https://www.davidsilver.uk/wp-content/uploads/2020/03/control.pdf#page=34" rel="nofollow noreferrer">page 34 of David Silver's RL lecture</a> is:
  <span class="math-container">$$ V(S_t) \leftarrow V(S_t) + \alpha \left( \frac{ \pi(A_t|S_t)}{\mu (A_t|S_t)} (R_{t+1} + \gamma V(S_{t+1})) - V(S_t) \right). $$</span></p>
  <p>I'd like to change this update rule to action value function Q, something like:</p>
  <p><span class="math-container">$$ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left( \frac{ \pi(A_t|S_t)}{\mu (A_t|S_t)} (R_{t+1} + \gamma Q(S_{t+1},A_{t+1})) - Q(S_t,A_t) \right). $$</span></p>
  <p>Then what is the corresponding importance sampling ratio?</p>
  <p>Since <span class="math-container">$A_t$</span> is already determined (because we are calculating <span class="math-container">$Q(S_t,A_t)$</span>), I think <span class="math-container">$\pi(A_t|S_t)$</span> is definitely 1. But what about <span class="math-container">$\mu (A_t|S_t)$</span>? Is it 1 or not?</p>
  
Tags: <machine-learning><reinforcement-learning><temporal-difference-methods><importance-sampling>
Title: What would be the importance sampling ratio for off-policy TD learning control using Q values?
UserDisplayName: Cauchy
ThreadText: # What would be the importance sampling ratio for off-policy TD learning control using Q values?
  
  (Asked by: username_0 on 2021-04-21)
  
  The off-policy TD learning control using state value function from [page 34 of David Silver's RL lecture](https://www.davidsilver.uk/wp-content/uploads/2020/03/control.pdf#page=34) is:
  $$ V(S\_t) \leftarrow V(S\_t) + \alpha \left( \frac{ \pi(A\_t|S\_t)}{\mu (A\_t|S\_t)} (R\_{t+1} + \gamma V(S\_{t+1})) - V(S\_t) \right). $$
  
  I'd like to change this update rule to action value function Q, something like:
  
  $$ Q(S\_t,A\_t) \leftarrow Q(S\_t,A\_t) + \alpha \left( \frac{ \pi(A\_t|S\_t)}{\mu (A\_t|S\_t)} (R\_{t+1} + \gamma Q(S\_{t+1},A\_{t+1})) - Q(S\_t,A\_t) \right). $$
  
  Then what is the corresponding importance sampling ratio?
  
  Since $A\_t$ is already determined (because we are calculating $Q(S\_t,A\_t)$), I think $\pi(A\_t|S\_t)$ is definitely 1. But what about $\mu (A\_t|S\_t)$? Is it 1 or not?
  
  **Tags:** machine-learning, reinforcement-learning, temporal-difference-methods, importance-sampling
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-04-21. Score: 2 | Accepted answer
  
  > Since $A\_t$ is already determined (because we are calculating $Q(S\_t,A\_t)$), I think $\pi(A\_t|S\_t)$ is definitely 1. But what about $\mu (A\_t|S\_t)$? Is it 1 or not?
  
  You could assign values of 1 to each to get the right answer, but the situation is different. You can see that more clearly in the definition of action value, $q(s,a)$:
  
  $$q\_{\pi}(s,a) = \mathbb{E}\_{\pi}[\sum\_{k=0}^{\infty} \gamma^k R\_{t+k+1}|S\_t=s, A\_t=a]$$
  
  The condition on the expectation $|S\_t=s, A\_t=a$ means that the value of $A\_t$ is already assumed. There is no need to know or use the associated probability, and no need to adjust between probabilities of different policies when estimating returns for the first action choice.
  
  In addition, the last action choice used to bootstrap in Q learning is always the maximising action over current Q values. That is an *on-policy* choice with respect to the target policy $\pi$, so does not need to be adjusted for.
  
  For single-step Q learning, there is no need to use importance sampling to adjust for policy differences between behaviour and target policies. The correct update equation rule is:
  
  $$ Q(S\_t,A\_t) \leftarrow Q(S\_t,A\_t) + \alpha \left( R\_{t+1} + \gamma Q(S\_{t+1},A\_{t+1}) - Q(S\_t,A\_t) \right). $$
  
  This does change for n-step updates, where you do need to take account of differences in action choice between target and behaviour policies for $A\_{t+1}, A\_{t+2}$ up to $A\_{t+n-1}$. However, you should bear in mind that $\pi(a|s)$ is zero for any non-maximising action - if you use weighted importance sampling then any trajectory with an exploring action before calculating the TD update contributes zero update.
  
  So, if you are calculating over longer trajectories, in e.g. Q($\lambda$), it is common to see this simplified to a logical test and some kind of shortcut update. You rarely see explicit use of importance sampling - with probability calculations and ratios - in Q learning.
  
  
  ---
  
  