JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Learning Values from Experience: Monte Carlo Prediction

When you don't know how the world works, just play many episodes and average what actually happened.

Why we need model-free learning

Dynamic programming can compute the value of every state exactly — but only if you already know the environment's transition probabilities and reward function. In most real problems you don't. You can't write down the dynamics of a game you've never fully analysed, a robot's contact physics, or a customer's behaviour. What you can do is act and observe: take actions, see what states and rewards follow, and learn from the stream of interaction itself.

Monte Carlo (MC) prediction is the most direct way to do this. The idea is almost embarrassingly simple: the value of a state is the expected return starting from it, so estimate that expectation by averaging the actual returns you observe after visiting the state. This is exactly the spirit of the classic Monte Carlo method — replace a hard expectation with an average over samples.

Monte Carlo learns purely from this agent–environment loop: act, observe rewards, and average the returns that actually come back.

Diagram of the reinforcement-learning loop: an agent takes an action, the environment returns a new state and reward, and the cycle repeats.

The core requirement: complete episodes

To average returns you first have to measure a return, and the return at a state is the discounted sum of all rewards from that state until the end. So Monte Carlo needs the interaction to actually end: it works on episodic tasks — games that reach a terminal state, robot trials that finish, dialogues that complete. You play an episode from start to finish, then look back and compute, for each state you visited, what return eventually followed.

G_t = R_{t+1} + \gamma R_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1}, \qquad V(s) = \mathbb{E}\,[\,G_t \mid S_t = s\,]

The return is the discounted sum of all rewards to the episode's end; the value of a state is the expected return from it.

First-visit vs every-visit

Within one episode a state can appear more than once. That raises a question: when we average returns for state s, do we use the return following every time s appeared, or only the first time? These are the two standard variants. First-visit MC averages, for each episode, only the return after the first time s is visited. Every-visit MC averages the return after every occurrence of s.

Episodes are trajectories through states; because a path can revisit a state, we must choose between first-visit and every-visit averaging.

Interactive Markov chain: nodes are states with transition arrows; a sampled path can pass through the same state more than once.

Both converge to the true value as the number of episodes grows, but their statistics differ. First-visit returns within an episode are independent, which makes the estimator an unbiased average of independent samples — easy to analyse. Every-visit returns from the same episode are correlated, so it is biased for small samples but still consistent, and it is often slightly simpler to implement and reuses more data. In practice the two behave very similarly.

The algorithm, step by step

  1. Initialise an estimate V(s) for every state (zeros are fine) and a way to track averages — a running count and sum, or an incremental update.
  2. Generate a full episode by following the current policy: s0, a0, r1, s1, a1, r2, …, until termination.
  3. Walk backwards through the episode, accumulating the discounted return G = r + γ·G at each step.
  4. For each visited state (first-visit: only its first occurrence), record G as one more sample of that state's return.
  5. Update V(s) toward the average of its observed returns. Repeat over many episodes.
# First-visit MC prediction for V (one episode)
G = 0
visited = set()
for t in reversed(range(len(episode))):       # walk backwards
    s, a, r = episode[t]
    G = r + gamma * G                          # discounted return from t
    if s not in [step.s for step in episode[:t]]:   # first visit?
        returns[s].append(G)
        V[s] = sum(returns[s]) / len(returns[s])    # average of samples
First-visit MC, computed in one backward pass over the episode.

An equivalent, memory-light form uses the incremental average V(s) ← V(s) + (1/N(s))·(G − V(s)), where N(s) counts visits. Replacing 1/N(s) with a small constant step size α turns this into a method that tracks a slowly changing target — the same update shape you will meet again in temporal-difference learning.

V(s) \leftarrow V(s) + \frac{1}{N(s)}\bigl(G - V(s)\bigr)

The incremental average nudges each state's value toward the newest observed return by one over its visit count.

Strengths, weaknesses, and what comes next

Monte Carlo's strengths are real: it needs no model, its estimate of each state is unbiased (first-visit), and it is unaffected by violations of the Markov property because it never relies on one-step structure — it just looks at outcomes. It can even estimate the value of a few states of interest without sweeping the whole state space.

The weaknesses motivate the rest of this track. First, you must wait until an episode ends before learning anything from it — useless for continuing tasks and slow when episodes are long. Second, the return depends on a long chain of random choices, so MC estimates have high variance and can need many episodes to settle. The next guide keeps the model-free, sample-driven spirit but learns during the episode by bootstrapping — that is temporal-difference learning.