MC: rollout, compute returns, average
episode i
s_0 --a_0--> s_1 --a_1--> s_2 --a_2--> ... --a_{T-1}--> s_T (terminal)
rewards: r_1 r_2 r_3 r_T
backward pass: compute returns
G_t = r_{t+1} + gamma * G_{t+1} (one pass, O(T))
the return G_t is the sampled realization of the expected return V^pi(s_t)
first-visit MC
for t where s_t first visited:
N(s_t) += 1
V(s_t) += (G_t - V(s_t)) / N(s_t)
unbiased, iid samples
every-visit MC
for every t in trajectory:
N(s_t) += 1
V(s_t) += (G_t - V(s_t)) / N(s_t)
lower variance, slightly biased
no model, no bootstrap — just sample trajectories and average the returns