First Visit

We can improve the approximations by updating rewards of many states in each single run.

for each $s\in S$ :

1.

Run $\pi$ from s for m times, where the i-th run is T_i.

2.

For each run T_i and state s in it, let r(s,T_i) be the reward of $\pi$ in run T_i from the first appearance of s in T_i until the run ends (reaching state s₀).

3.

Let the reward of policy $\pi$ starting from s be : $\hat{V^{\pi}}(s) = Avg_{s \in T_{i}}(r(s,T_{i}))$

The random variables r(s,T_i) for a given state s and different T_i's, are independent since different runs are independent. The improvement is based on increasing the number of samples without increasing the number of runs, so we have a smaller estimation-error.