Monte Carlo Action Values

When the rules of the world are unknown, the way to price an action is to try it, finish the episode, and average the totals it earned.

Three finished episodes price two actions at 4.75 and 6.20, so the greedy choice is the second action with no model involved

Why Does This Exist?

With a known model, state values $V(s)$ are enough: look one step ahead through $P(s' \mid s, a)$ and pick the action leading to the best successor. Without a model that lookahead is impossible. Knowing the next state is worth a lot helps nothing if you cannot say which action reaches it.

Action values $Q(s, a)$ remove the need for the lookahead entirely. The greedy choice becomes a plain maximum over numbers already learned:

\pi'(s) = \arg\max_{a} Q(s, a)

Monte Carlo estimation learns those numbers from raw episodes: run an action, finish the episode, record the total, average. No transition probabilities, no bootstrapped guesses. The structural cost is coverage: states are visited naturally along trajectories, but every action from each state must be tried on purpose, or its value stays unknown. This page teaches that estimation step. The prediction background is Monte Carlo methods, the counting variants are first visit versus every visit, and the control loop built on top is Monte Carlo control.

The one idea you need first

The action value $Q^{\pi}(s, a)$ is the expected discounted total from taking $a$ in $s$ and following $\pi$ after. Value functions define both $V$ and $Q$ precisely. Monte Carlo turns that expectation into an average of finished episode totals.

Think of It Like This

Pricing two wine pairings across repeated dinners

A restaurant offers two pairings with the sea bass course but hides the recipes, so no amount of menu study predicts which evening you will enjoy more. You try the white across two full dinners and the red across one, score each whole evening, and average: white averages 4.75 evenings of enjoyment against red at 6.20, so you order red next time.

The scores price the pairing decision directly, with no chemistry model of wine and sauce. Where it stops: dinners are scored by memory and mood, while the agent banks exact discounted sums, and it must keep ordering both pairings on a schedule instead of settling after one pleasant night.

How It Actually Works

For a trajectory ending at $T$ , the return from step $t$ is accumulated backward:

G_t = R_{t+1} + \gamma G_{t+1}, \qquad G_T = 0

with discount $\gamma$ in $[0, 1]$ . First visit estimation records $G_t$ only at each pair's first appearance per episode, then averages all recorded totals:

Q(s, a) = \frac{1}{N(s, a)} \sum G \quad \text{over recorded returns for } (s, a)

or incrementally with visit count $N(s, a)$ :

Q(s, a) \leftarrow Q(s, a) + \frac{1}{N(s, a)}[G_t - Q(s, a)]

A deterministic policy replays the same action forever, starving the rest, so convergence needs exploring starts or ongoing random exploration: every pair visited again and again.

Worked example

State $s_0$ offers $a_1$ and $a_2$ with $\gamma = 0.9$ . All tables start empty.

Episode 1 starts with $a_1$ : rewards $R_1 = 2.0$ then $R_2 = 4.0$ . The return is $G_0 = 2.0 + 0.9 \times 4.0 = 2.0 + 3.6 = 5.60$ , so $N(s_0, a_1) = 1$ and $Q(s_0, a_1) = 5.600$ .

Episode 2 starts with $a_2$ : rewards $R_1 = -1.0$ then $R_2 = 8.0$ . The return is $G_0 = -1.0 + 0.9 \times 8.0 = -1.0 + 7.2 = 6.20$ , so $N(s_0, a_2) = 1$ and $Q(s_0, a_2) = 6.200$ .

Episode 3 retries $a_1$ : rewards $R_1 = 3.0$ then $R_2 = 1.0$ . The return is $G_0 = 3.0 + 0.9 \times 1.0 = 3.90$ . The running average moves to

Q(s_0, a_1) = 5.600 + \frac{1}{2}(3.90 - 5.600) = 5.600 - 0.850 = 4.750

which equals $(5.60 + 3.90) / 2$ . Greedy choice at $s_0$ compares $4.750$ against $6.200$ and picks $a_2$ , with no model queried.

Code

This snippet averages the three episode returns exactly as the worked example does and prints the greedy pick.

1def episode_return(rewards: list[float], gamma: float = 0.9) -> float:2    g = 0.03    for r in reversed(rewards):4        g = r + gamma * g5    return round(g, 2)6
7
8g1 = episode_return([2.0, 4.0])    # -> 5.69g2 = episode_return([-1.0, 8.0])   # -> 6.210g3 = episode_return([3.0, 1.0])    # -> 3.911q_a1 = round((g1 + g3) / 2, 3)12print(g1, g2, g3)                  # -> 5.6 6.2 3.913print(q_a1, g2)                    # -> 4.75 6.214print("a2" if g2 > q_a1 else "a1")  # -> a2

The three returns print as 5.6, 6.2, and 3.9. The averaged $Q(s_0, a_1)$ is 4.75 against 6.2 for $a_2$ , so the greedy pick prints as the second action.

Watch Out For

Starving actions under a greedy policy

Once one action leads, a greedy policy replays it forever while the rest sit at $N(s, a) = 0$ . An optimal action that drew one unlucky negative reward on its first trial then never gets a second chance.

Symptom: value tables where some pairs have hundreds of visits and neighbors have none, plus a policy that plateaued early. Fix: force coverage with exploring starts in resettable simulators or epsilon greedy exploration online, so every pair is visited infinitely often as episodes accumulate.

The Quick Version

$Q(s, a)$ prices an action directly, so greedy choice needs no transition model.
Monte Carlo estimates it by averaging finished episode returns from each pair's first visit per episode.
The worked example prices $a_1$ at $(5.60 + 3.90) / 2 = 4.750$ and $a_2$ at $6.200$ , so $a_2$ wins.
Deterministic policies starve untried actions, so exploring starts or epsilon greedy coverage is required.
Every symbol is concrete: $G_t$ is the sampled total, $N(s, a)$ counts visits, $\gamma$ discounts the future.