Answers.Body: <p>By definition of <span class="math-container">$V_{n+1}$</span>, we have:</p>
  
  <p><span class="math-container">$V_{n+1} = \frac{\sum_{k=1}^{n} W_{k} G_{k}}{\sum_{k=1}^{n} W_{k}} \; \tag{1}$</span></p>
  
  <p>Then, taking the <span class="math-container">$n^{th}$</span> term out of the sum in the numerator, we have:</p>
  
  <p><span class="math-container">$V_{n+1} = \frac{W_{n}G_{n} \; + \; \sum_{k=1}^{n-1} W_{k} G_{k}}{\sum_{k=1}^{n} W_{k}} \; \tag{2}$</span></p>
  
  <p>Then, from the definition of <span class="math-container">$V_n$</span>, <span class="math-container">$V_{n} = \frac{\sum_{k=1}^{n-1} W_{k} G_{k}}{\sum_{k=1}^{n-1} W_{k}}$</span>, we have:</p>
  
  <p><span class="math-container">$\sum_{k=1}^{n-1} W_{k} G_{k} = V_{n}*\sum_{k=1}^{n-1} W_{k} \; \tag{3}$</span></p>
  
  <p>Then, substituting <span class="math-container">$(3)$</span> in the numerator of <span class="math-container">$(2)$</span>, we get: </p>
  
  <p><span class="math-container">$V_{n+1} = \frac{W_{n}G_{n} \; + \; V_{n}*\sum_{k=1}^{n-1} W_{k}}{\sum_{k=1}^{n} W_{k}} \; \tag{4}$</span></p>
  
  <p>Then, adding and subtracting <span class="math-container">$V_{n}W_{n}$</span> in the numerator of <span class="math-container">$(4)$</span>, we obtain:</p>
  
  <p><span class="math-container">$V_{n+1} = \frac{W_{n}G_{n} \; + \; V_{n}*\sum_{k=1}^{n-1} W_{k} \; + \; V_n W_n \; - \; V_n W_n}{\sum_{k=1}^{n} W_{k}} \; \tag{5}$</span></p>
  
  <p>We factor <span class="math-container">$V_n$</span> in the numerator of <span class="math-container">$(5)$</span>:</p>
  
  <p><span class="math-container">$V_{n+1} = \frac{W_{n}G_{n} \; + \; V_{n}(W_n \; + \; \sum_{k=1}^{n-1} W_{k}) \; - \; V_n W_n}{\sum_{k=1}^{n} W_{k}} \; \tag{6}$</span></p>
  
  <p>We simplify, taking into account that the denominator <span class="math-container">$\sum_{k=1}^{n} W_{k} = W_n + \sum_{k=1}^{n-1} W_{k}$</span>, we get:</p>
  
  <p><span class="math-container">$V_{n+1} = V_n + \frac{W_n G_n - W_n V_n}{\sum_{k=1}^{n} W_{k}} \; \tag{7} $</span></p>
  
  <p>Further rearrangements of the terms give us:
  <span class="math-container">$V_{n+1} = V_n + \frac{W_n}{\sum_{k=1}^{n} W_{k}}[G_n - V_n] \; \tag{8}$</span></p>
  
  <p>Finally, by definition of <span class="math-container">$C_n$</span> as the cumulative sum of the weights up to time <span class="math-container">$n$</span>, we get the desired incremental update equation:
  <span class="math-container">$V_{n+1} = V_n + \frac{W_n}{C_n}[G_n - V_n] \; \tag{9}$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-16T22:09:16.120Z
Answers.LastActivityDate: 2020-05-16T22:09:16.120Z
Answers.UserDisplayName: user5093249
Body: <p>Here's the approximated value using weighted importance sampling</p>
  
  <p><span class="math-container">$$
  V_{n} \doteq \frac{\sum_{k=1}^{n-1} W_{k} G_{k}}{\sum_{k=1}^{n-1} W_{k}}, \quad n \geq 2
  $$</span></p>
  
  <p>Here's the incremental update rule for the approximated value</p>
  
  <p><span class="math-container">$$V_{n+1} \doteq V_{n}+\frac{W_{n}}{C_{n}}\left[G_{n}-V_{n}\right], \quad n \geq 1$$</span></p>
  
  <p>How is the second equation derived from the first? </p>
  
  <p>These are used for the weighted importance sampling method of off-policy Monte Carlo control.</p>
  
Tags: <reinforcement-learning><monte-carlo-methods><value-functions><importance-sampling>
Title: How is the incremental update rule derived from the weighted importance sampling in off-policy Monte Carlo control?
UserDisplayName: ExplorationExploitation
ThreadText: # How is the incremental update rule derived from the weighted importance sampling in off-policy Monte Carlo control?
  
  (Asked by: username_0 on 2020-05-16)
  
  Here's the approximated value using weighted importance sampling
  
  $$
  V\_{n} \doteq \frac{\sum\_{k=1}^{n-1} W\_{k} G\_{k}}{\sum\_{k=1}^{n-1} W\_{k}}, \quad n \geq 2
  $$
  
  Here's the incremental update rule for the approximated value
  
  $$V\_{n+1} \doteq V\_{n}+\frac{W\_{n}}{C\_{n}}\left[G\_{n}-V\_{n}\right], \quad n \geq 1$$
  
  How is the second equation derived from the first?
  
  These are used for the weighted importance sampling method of off-policy Monte Carlo control.
  
  **Tags:** reinforcement-learning, monte-carlo-methods, value-functions, importance-sampling
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-05-16. Score: 2 | Accepted answer
  
  By definition of $V\_{n+1}$, we have:
  
  $V\_{n+1} = \frac{\sum\_{k=1}^{n} W\_{k} G\_{k}}{\sum\_{k=1}^{n} W\_{k}} \; \tag{1}$
  
  Then, taking the $n^{th}$ term out of the sum in the numerator, we have:
  
  $V\_{n+1} = \frac{W\_{n}G\_{n} \; + \; \sum\_{k=1}^{n-1} W\_{k} G\_{k}}{\sum\_{k=1}^{n} W\_{k}} \; \tag{2}$
  
  Then, from the definition of $V\_n$, $V\_{n} = \frac{\sum\_{k=1}^{n-1} W\_{k} G\_{k}}{\sum\_{k=1}^{n-1} W\_{k}}$, we have:
  
  $\sum\_{k=1}^{n-1} W\_{k} G\_{k} = V\_{n}\*\sum\_{k=1}^{n-1} W\_{k} \; \tag{3}$
  
  Then, substituting $(3)$ in the numerator of $(2)$, we get:
  
  $V\_{n+1} = \frac{W\_{n}G\_{n} \; + \; V\_{n}\*\sum\_{k=1}^{n-1} W\_{k}}{\sum\_{k=1}^{n} W\_{k}} \; \tag{4}$
  
  Then, adding and subtracting $V\_{n}W\_{n}$ in the numerator of $(4)$, we obtain:
  
  $V\_{n+1} = \frac{W\_{n}G\_{n} \; + \; V\_{n}\*\sum\_{k=1}^{n-1} W\_{k} \; + \; V\_n W\_n \; - \; V\_n W\_n}{\sum\_{k=1}^{n} W\_{k}} \; \tag{5}$
  
  We factor $V\_n$ in the numerator of $(5)$:
  
  $V\_{n+1} = \frac{W\_{n}G\_{n} \; + \; V\_{n}(W\_n \; + \; \sum\_{k=1}^{n-1} W\_{k}) \; - \; V\_n W\_n}{\sum\_{k=1}^{n} W\_{k}} \; \tag{6}$
  
  We simplify, taking into account that the denominator $\sum\_{k=1}^{n} W\_{k} = W\_n + \sum\_{k=1}^{n-1} W\_{k}$, we get:
  
  $V\_{n+1} = V\_n + \frac{W\_n G\_n - W\_n V\_n}{\sum\_{k=1}^{n} W\_{k}} \; \tag{7} $
  
  Further rearrangements of the terms give us:
  $V\_{n+1} = V\_n + \frac{W\_n}{\sum\_{k=1}^{n} W\_{k}}[G\_n - V\_n] \; \tag{8}$
  
  Finally, by definition of $C\_n$ as the cumulative sum of the weights up to time $n$, we get the desired incremental update equation:
  $V\_{n+1} = V\_n + \frac{W\_n}{C\_n}[G\_n - V\_n] \; \tag{9}$
  
  
  ---
  
  