3
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .