Answers.Body: <p>The weighting calculation ignores how the <em>current</em> action <span class="math-container">$A_t$</span> was chosen.</p>
  <p>The action being evaluated does not need its probability adjusted by importance sampling, only future actions. This is because you have &quot;already decided&quot; to evaluate/update a particular <span class="math-container">$Q(s,a)$</span> and any probabilities of being in that part of the trajectory do not come into play (they do affect approximators such as neural nets, but that is a secondary effect that is often ignored). More formally, updating <span class="math-container">$Q(s,a)$</span> is <em>conditional</em> on you having a record <span class="math-container">$S_t = s, A_t = a$</span>, so you do not take into account the probabilities of that happening. Whilst the return from that point on is a sample from a distribution including all the probabilities for observing <span class="math-container">$A_{t+1}$</span> to <span class="math-container">$A_{T-1}$</span> which you do need to adjust for if you are observing results from a different policy to the one you want to update.</p>
  <p>An off-by-one relationship where you only weight for future actions is maintained simply by having the <span class="math-container">$W$</span> update at the end of the loop, after the Q update for the same timestep. In fact <span class="math-container">$W$</span> is being updated ready for calculating the weightings to apply to the previous timestep (previous because the loop is decrementing <span class="math-container">$t$</span>). At <span class="math-container">$t = T-1$</span> there are no future actions, and you have not been around the loop even once yet.</p>
  <p>When you get to the subject of off-policy TD control later on, you can also ignore how the last action in the partial trajectory was chosen, because you will use the target policy's action instead. Which means single-step Q learning doesn't use importance sampling at all.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-04T14:20:25.280Z
Answers.LastActivityDate: 2022-02-04T14:28:36.270Z
Answers.LastEditDate: 2022-02-04T14:28:36.270Z
Answers.UserDisplayName: Neil Slater
Body: <p>Below is  the off-policy every visit MC prediction algorithm for estimating <span class="math-container">$V\approx v_{\pi}$</span>,
  which I took from coursera. <a href="https://i.sstatic.net/5CzzP.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5CzzP.png" alt="enter image description here" /></a></p>
  <p>It seems to me that this algorithm is not correct. Let me explain why. Assume that <span class="math-container">$t=T-1$</span> and let <span class="math-container">$\pi(A_{T-1}|S_{T-1})=0$</span>,
  which means there is no possibility for target policy <span class="math-container">$\pi$</span> to go from <span class="math-container">$S_{T-1}$</span> to terminal state
  via action <span class="math-container">$A_{T-1}$</span>. Hence, based on this observation we should have <span class="math-container">$V(S_{T-1}) \approx v_{\pi}(S_{T-1})=0$</span>. However, the algorithm in the pseudoce returns <span class="math-container">$V(S_{T-1}) \approx v_{\pi}(S_{T-1})=R_{T}$</span>. What do you think?</p>
  
Tags: <reinforcement-learning>
Title: Off-policy every visit MC prediction algorithm for estimating $V\approx v_{\pi}$: is this algorithm correct?
UserDisplayName: user3489173
ThreadText: # Off-policy every visit MC prediction algorithm for estimating $V\approx v_{\pi}$: is this algorithm correct?
  
  (Asked by: username_0 on 2022-02-04)
  
  Below is the off-policy every visit MC prediction algorithm for estimating $V\approx v\_{\pi}$,
  which I took from coursera. [![enter image description here](https://i.sstatic.net/5CzzP.png)](https://i.sstatic.net/5CzzP.png)
  
  It seems to me that this algorithm is not correct. Let me explain why. Assume that $t=T-1$ and let $\pi(A\_{T-1}|S\_{T-1})=0$,
  which means there is no possibility for target policy $\pi$ to go from $S\_{T-1}$ to terminal state
  via action $A\_{T-1}$. Hence, based on this observation we should have $V(S\_{T-1}) \approx v\_{\pi}(S\_{T-1})=0$. However, the algorithm in the pseudoce returns $V(S\_{T-1}) \approx v\_{\pi}(S\_{T-1})=R\_{T}$. What do you think?
  
  **Tags:** reinforcement-learning
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-02-04. Score: 1 | Accepted answer
  
  The weighting calculation ignores how the *current* action $A\_t$ was chosen.
  
  The action being evaluated does not need its probability adjusted by importance sampling, only future actions. This is because you have "already decided" to evaluate/update a particular $Q(s,a)$ and any probabilities of being in that part of the trajectory do not come into play (they do affect approximators such as neural nets, but that is a secondary effect that is often ignored). More formally, updating $Q(s,a)$ is *conditional* on you having a record $S\_t = s, A\_t = a$, so you do not take into account the probabilities of that happening. Whilst the return from that point on is a sample from a distribution including all the probabilities for observing $A\_{t+1}$ to $A\_{T-1}$ which you do need to adjust for if you are observing results from a different policy to the one you want to update.
  
  An off-by-one relationship where you only weight for future actions is maintained simply by having the $W$ update at the end of the loop, after the Q update for the same timestep. In fact $W$ is being updated ready for calculating the weightings to apply to the previous timestep (previous because the loop is decrementing $t$). At $t = T-1$ there are no future actions, and you have not been around the loop even once yet.
  
  When you get to the subject of off-policy TD control later on, you can also ignore how the last action in the partial trajectory was chosen, because you will use the target policy's action instead. Which means single-step Q learning doesn't use importance sampling at all.
  
  
  ---
  
  