Monte Carlo methods (RL): Definition and Examples

In reinforcement learning, Monte Carlo methods estimate the value of a state or action by running complete episodes and averaging the returns that actually followed it. They need no model of the environment and do not bootstrap from other estimates.

Monte Carlo prediction

To estimate $V^{π} (s)$ , follow policy $π$ , record the return $G_{t}$ after each visit to $s$ , and average:

V (s) \approx \frac{1}{N ( s )} i = 1 \sum N (s) G^{(i)} (s) .

$N (s)$ is the number of recorded visits and $G^{(i)} (s)$ the return after the $i$ -th one. First-visit MC uses only the first visit to $s$ in each episode; every-visit MC uses all of them. Both converge to $V^{π} (s)$ as visits grow. In incremental form, $V (s) \leftarrow V (s) + α [G_{t} - V (s)]$ , with $α = 1/ N (s)$ for an exact average or a constant $α$ for nonstationary problems.

Worked example

Three episodes pass through state $s$ , with returns 4, 10 and 1 afterwards. The estimate is $(4 + 10 + 1) /3 = 5$ . Incrementally: after the first episode $V = 4$ ; after the second $V = 4 + (10 - 4) /2 = 7$ ; after the third $V = 7 + (1 - 7) /3 = 5$ . The spread of those returns, from 1 to 10, is the variance problem in miniature.

Monte Carlo control

MC control estimates action values $Q (s, a)$ from returns and improves the policy greedily, keeping exploration alive with epsilon-greedy choices or exploring starts. Off-policy MC uses importance sampling to evaluate one policy from another's episodes.

Strengths and weaknesses

Unbiased: targets are real returns, so errors in other estimates do not leak in, and the Markov property is not required.
High variance: a return sums many random rewards, so many episodes are needed.
Episodic only: learning waits until the episode ends. TD learning removes that wait at the cost of bias.

Why it matters

Monte Carlo estimation is the simplest correct way to evaluate a policy, and it is everywhere in practice. REINFORCE is a Monte Carlo policy gradient. Group-based baselines in language-model RL, which average the rewards of several sampled responses to the same prompt, are Monte Carlo value estimates. And most evaluation of agents, running episodes and averaging scores, is Monte Carlo estimation with confidence intervals.

Sources

Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction (2nd edition), 2018. incompleteideas.net