# How is the incremental update rule derived from the weighted importance sampling in off-policy Monte Carlo control?

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