Please help me understand constant-α Monte Carlo method

Question

This is my understanding thus far about Monte Carlo method for approximating value function:

Instead of using a recursive Bellman equations and knowledge of environment dynamics, Monte Carlo methods use statistics to evaluate a value function. For a given policy π and starting state S_t, multiple episodes are generated. The return for each of these episodes is calculated and averaged out. If the number of samples is large enough, the calculated value converges to the expected return.

But according to constant-α Monte Carlo, the value function is evaluated using following update rule:

where V(S_t) is current estimate of value function for state S_t and G_t is the return after time step t. I don't understand how this is in-line with the averaging method.

Answer 1

Say you have an estimate of $V(s_t)$ and you visited $s_t$ $\#s_t$ times, using the mean the update would be: $$ V'(s_t) = \frac{\#s_t \cdot V(s_t) + G_t}{\#s_t+1} $$ which can also be seen as: $$ V'(s_t) = \frac{\#s_t}{\#s_t+1} \cdot V(s_t) + \frac{1}{\#s_t+1}G_t $$ Where the sum of the two coefficients sum to 1, and they are strictly positive... in other words, is a linear combination of your current estimate, and your new estimate

Now, check the constant step size formula: $$ V'(s_t) = V(s_t) + \alpha[G_t - V(s_t)]\\ V'(s_t) = V(s_t) + \alpha G_t - \alpha V(s_t)\\ V'(s_t) = (1 - \alpha)V(s_t) + \alpha G_t $$ And again, you can see that you are taking a linear combination of your old estimate and the new estimate

Hence the similarity/being in-line