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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.