Monte Carlo Methods in RL

Monte Carlo (MC) methods learn value functions from complete episodes of experience — no model needed.

Key idea: estimate $V^\pi(s)$ as the average return observed after visiting state $s$ :

V^\pi(s) \approx \frac{1}{N(s)}\sum_{\text{visits to } s} G_t

where $G_t = R_{t+1} + \gamma R_{t+2} + \dots$ is the actual return from that visit.

First-visit MC: average returns only from the first time $s$ is visited in each episode. Every-visit MC: average returns from every visit to $s$ .

Properties:

Unbiased: uses actual returns, no bootstrapping
High variance: full returns are noisy (depend on many random transitions)
Requires complete episodes: can't learn from incomplete trajectories
Model-free: doesn't need $P(s'|s,a)$

MC vs TD:

	MC	TD
Update uses	Actual return $G_t$	Estimated return $R + \gamma V(s')$
Bias	None	Some (bootstrapping)
Variance	High	Lower
Episodes	Must be complete	Can update every step

MC control: MC + $\epsilon$ -greedy policy improvement → learns Q-values and improves the policy.

See also: Miscoral Difference Learning, Value Functions, Q-Learning

Monte Carlo Methods in RL

Linked from