Monte Carlo Methods
Monte Carlo methods learn values from complete episodes by averaging the actual returns that follow each state.
Learning from full returns
Monte Carlo (MC) methods estimate value functions directly from experience, without a model, by averaging observed returns. To evaluate a state, the agent records the total discounted reward that actually followed each visit to it, then averages those returns. As the number of samples grows, the average converges to the true expected value.
Requires episodes to end
Because MC uses the complete return from a state to the end of the episode, it applies only to episodic tasks: the agent must wait until an episode terminates before it can compute returns and update estimates. This is its defining limitation and its defining strength — the return is an unbiased sample of value.
First-visit and every-visit
- First-visit MC: average returns only from the first time a state is reached in each episode.
- Every-visit MC: average returns from every occurrence of the state.
- Both converge to the true value as visits accumulate.
Control with Monte Carlo
For control, MC estimates action values Q(s, a) and improves the policy greedily, following generalized policy iteration. To keep exploring, MC control uses either exploring starts or an epsilon-soft policy so every action keeps some probability of being tried.
Bias, variance, and contrast
Monte Carlo estimates are unbiased but high variance: a single return depends on a long chain of random events. This is the opposite trade-off from temporal-difference learning, which bootstraps from current estimates to get lower variance at the cost of some bias. The two are unified by TD(lambda) and eligibility traces.