Monte Carlo Methods in Reinforcement Learning

Dynamic programming needs a model of the environment. Most real problems do not provide one. Monte Carlo (MC) methods are the simplest way to learn from experience alone: play complete episodes, observe what actually happened, and average the returns. They are model-free, conceptually clean and unbiased — the natural bridge from planning to learning.

Monte Carlo prediction#

To estimate $V^\pi(s)$, generate episodes following $\pi$ and average the returns observed after visiting $s$:

• First-visit MC: use only the return following the first visit to $s$ in each episode.
• Every-visit MC: use returns after every visit.

Both converge to $V^\pi(s)$ as the number of visits grows (by the law of large numbers). An incremental form avoids storing returns:

with $\alpha = 1/N(s)$ for an exact average, or a constant $\alpha$ for non-stationary problems. This "estimate ← estimate + step × (target − estimate)" form recurs throughout RL.

Properties#

• Model-free: needs only sample episodes.
• No bootstrapping: targets are actual returns $G_t$, so estimates are unbiased.
• High variance: returns depend on many random actions and transitions.
• Episodic only: must wait until the end of an episode to update.
• Estimates for each state are independent — you can evaluate only the states you care about.

Monte Carlo control#

To improve the policy without a model, estimate action values $Q(s, a)$ (state values alone require a model to choose actions). Then follow generalised policy iteration: evaluate $Q$ from episodes, make the policy greedy with respect to $Q$.

The problem: a greedy policy never tries some actions, so their values are never learned. Two solutions:

• Exploring starts: begin episodes from random state–action pairs (often impossible in reality).
• ε-soft policies: act greedily with probability $1 - \varepsilon$ and randomly with probability $\varepsilon$. On-policy MC control with ε-greedy converges to the best ε-soft policy.

Blackjack example#

Sutton and Barto's classic: learn to play blackjack against a fixed dealer policy, using Gymnasium's environment.

import numpy as np
import gymnasium as gym
from collections import defaultdict

env = gym.make("Blackjack-v1", sab=True)
Q = defaultdict(lambda: np.zeros(2))                 # actions: 0 = stick, 1 = hit
N = defaultdict(lambda: np.zeros(2))
eps, gamma = 0.1, 1.0

def policy(state):
    return env.action_space.sample() if np.random.rand() < eps else int(np.argmax(Q[state]))

for episode in range(300_000):
    s, _ = env.reset()
    trajectory, done = [], False
    while not done:
        a = policy(s)
        s2, r, terminated, truncated, _ = env.step(a)
        trajectory.append((s, a, r)); s, done = s2, terminated or truncated
    G, visited = 0.0, set()
    first_visit = {}
    for t, (s_, a_, _) in enumerate(trajectory):
        first_visit.setdefault((s_, a_), t)
    for t in reversed(range(len(trajectory))):          # compute returns backwards
        s_, a_, r_ = trajectory[t]
        G = gamma * G + r_
        if first_visit[(s_, a_)] == t:                   # first-visit update
            N[s_][a_] += 1
            Q[s_][a_] += (G - Q[s_][a_]) / N[s_][a_]

# Evaluate the greedy policy
wins, games = 0, 20000
for _ in range(games):
    s, _ = env.reset(); done = False
    while not done:
        s, r, term, trunc, _ = env.step(int(np.argmax(Q[s]))); done = term or trunc
    wins += r > 0
print("win rate of learned policy:", wins / games)

The learned policy discovers the familiar strategy: hit on low sums, stick on high sums, with adjustments depending on the dealer's visible card and whether the player has a usable ace.

Off-policy Monte Carlo#

Sometimes we want to learn about a target policy $\pi$ (e.g. greedy) using data from a different behaviour policy $b$ (e.g. exploratory, or logged from an old system). Returns must be reweighted by importance sampling:

• Ordinary importance sampling averages $\rho G$ — unbiased but can have enormous (even infinite) variance.
• Weighted importance sampling normalises by the sum of weights — biased but much lower variance, usually preferred.

Coverage is required: $b$ must give non-zero probability to every action $\pi$ might take. Off-policy evaluation is crucial in practice — for example, estimating how a new recommendation or allocation policy would perform using logs from the current one, before deploying it.