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

CC BY-SA 4.0
2020-05-16T22:09:16.120Z
2020-05-16T22:09:16.120Z
user5093249
<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>

<reinforcement-learning><monte-carlo-methods><value-functions><importance-sampling>
How is the incremental update rule derived from the weighted importance sampling in off-policy Monte Carlo control?
ExplorationExploitation
# 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}$


---

