Monte Carlo Control

Monte Carlo Control is the application of Generalized Policy Iteration (GPI) using Monte Carlo estimation as the evaluation mechanism, with no access to a transition model $p(s', r \mid s, a)$. Recall that GPI is the interplay of two processes: policy evaluation (compute $v_\pi$ or $q_\pi$ for the current policy $\pi$) and policy improvement (make $\pi$ greedy, or partially greedy, with respect to those value estimates). In dynamic-programming methods this interplay uses the Bellman equations directly; in Monte Carlo methods, since there is no model, evaluation must instead be done by averaging observed returns from sampled episodes. A crucial design decision separates MC control from DP-style policy iteration: MC control estimates action-value functions $q_\pi(s,a)$ rather than state-value functions $v_\pi(s)$. This is not a stylistic choice — it is forced. Greedy policy improvement under $v_\pi$ requires

which needs the model $p(s',r\mid s,a)$ to look one step ahead. Without a model, this lookahead is unavailable. But if we instead estimate $q_\pi(s,a)$ directly, greedy improvement is simply

no model required. This is the single idea that makes model-free control possible. The second essential idea is the exploration problem. A deterministic greedy policy, by definition, never selects the non-greedy actions again once it locks onto a choice at a state. If some $(s,a)$ pair is never selected, its Monte Carlo estimate $q(s,a)$ never receives new samples and may remain permanently wrong — possibly making a genuinely excellent action look bad forever, with no way to correct the mistake. Two standard remedies exist. Exploring Starts (ES) assumes every episode begins at a uniformly random state-action pair, guaranteeing infinite visits to every pair over infinitely many episodes (a strong, often unrealistic assumption in real environments where you cannot "teleport" the start). ε-soft policies instead relax the target policy class itself: every action at every state retains probability at least $\varepsilon/|\mathcal{A}(s)|$, so no action is ever completely abandoned. This yields on-policy Monte Carlo control with ε-greedy policies, the workhorse version of the algorithm and the version emphasized here.

The algorithm maintains, for every state–action pair, a running estimate of the action-value $Q(s,a) \approx q_\pi(s,a)$, obtained by averaging the returns following visits to $(s,a)$ across many sampled episodes. After each full episode, the policy is updated to be ε-greedy with respect to the current $Q$. This single loop — generate episode, evaluate, improve — is repeated until $Q$ (and hence the policy) stabilizes. Two bookkeeping choices matter and must be fixed explicitly:

• First-visit vs every-visit: first-visit MC averages only the return following the first occurrence of $(s,a)$ within an episode; every-visit averages the return following every occurrence. First-visit gives i.i.d.-style samples per episode and has the cleanest convergence proof (by the law of large numbers, since the samples across different episodes are independent). Every-visit is also consistent (converges to the same $q_\pi$) but the within-episode samples are correlated, which affects finite-sample variance and standard convergence arguments slightly differently.
• Incremental averaging: rather than storing every return, maintain a visit count $N(s,a)$ and update incrementally,

which is mathematically identical to a running sample mean but uses $O(1)$ memory per pair instead of $O(N)$. ```pseudocode Algorithm: On-Policy Monte Carlo Control (first-visit, epsilon-greedy) Input: epsilon in (0,1], discount factor gamma, number of episodes M Initialize: Q(s,a) arbitrarily for all s in S, a in A(s) # e.g. all zeros N(s,a) <- 0 for all s, a # visit counts pi(a|s) <- an arbitrary epsilon-soft policy # e.g. uniform random for episode = 1 to M:

# 1. GENERATE an episode by following current policy pi S_0, A_0, R_1, S_1, A_1, R_2, ..., S_{T-1}, A_{T-1}, R_T <- rollout using pi until terminal state S_T

# 2. EVALUATE: compute first-visit returns and update Q G <- 0 visited <- empty set for t = T-1 down to 0: G <- gamma G + R_{t+1} if (S_t, A_t) not in visited: # first-visit check visited.add((S_t, A_t)) N(S_t, A_t) <- N(S_t, A_t) + 1 Q(S_t, A_t) <- Q(S_t, A_t) + (1 / N(S_t, A_t)) (G - Q(S_t, A_t))

# 3. IMPROVE: make pi epsilon-greedy with respect to updated Q for each state s visited in this episode: A_star <- argmax_a Q(s, a) # ties broken arbitrarily/randomly for each a in A(s): if a == A_star: pi(a|s) <- 1 - epsilon + epsilon / |A(s)| else: pi(a|s) <- epsilon / |A(s)| return Q, pi ``` The loop is structured exactly as GPI: step 2 pulls $Q$ toward $q_\pi$ (evaluation), and step 3 pulls $\pi$ toward greediness with respect to $Q$ (improvement), and the two processes chase each other episode by episode until convergence.

Per-episode time complexity. Let $T$ be the episode length (number of time steps until termination). Generating the episode costs $O(T)$ environment interactions. Computing returns backward and updating $Q$ costs $O(T)$ arithmetic operations (each step does $O(1)$ work: one increment, one running-average update, one set-membership check, which is $O(1)$ amortized with a hash set). The improvement step recomputes the greedy action at each visited state, costing $O(|\mathcal{A}|)$ per state, so at most $O(T \cdot |\mathcal{A}|)$ for the episode. Total per-episode cost: $O(T \cdot |\mathcal{A}|)$. Over $M$ episodes, total time is $O(M \cdot \bar{T} \cdot |\mathcal{A}|)$ where $\bar T$ is average episode length.

Space complexity. The algorithm stores $Q(s,a)$ and $N(s,a)$ for every reachable $(s,a)$ pair, giving $O(|\mathcal{S}| \cdot |\mathcal{A}|)$ space — independent of the number of episodes, because of incremental averaging. This is a major practical advantage over storing raw return lists, which would cost $O(|\mathcal{S}||\mathcal{A}|M)$ in the worst case.

Correctness argument. The proof of convergence rests on two pillars. Pillar 1 — Monte Carlo evaluation is consistent. For a fixed policy $\pi$, by the strong law of large numbers, the sample average of returns following first visits to $(s,a)$ converges almost surely to $\mathbb{E}_\pi[G_t \mid S_t=s, A_t=a] = q_\pi(s,a)$ as the number of visits $\to \infty$, provided returns have finite variance (true whenever rewards are bounded and $\gamma < 1$, or episodes are guaranteed to terminate when $\gamma = 1$). Pillar 2 — the Policy Improvement Theorem. If $\pi'$ is greedy (or ε-greedy in the appropriate sense) with respect to $q_\pi$, then $q_\pi(s, \pi'(s)) \geq v_\pi(s)$ for all $s$ implies $v_{\pi'}(s) \geq v_\pi(s)$ for all $s$. For ε-soft policies the correct statement uses the ε-soft improvement theorem: if $\pi'$ is the ε-greedy policy with respect to $q_\pi$ and $\pi$ was already ε-soft, then

which follows because the ε-greedy distribution places all its "extra" non-uniform mass on $\arg\max_a q_\pi(s,a)$, and a weighted average that shifts mass toward the max value can only increase (a short averaging argument: writing $\pi'$'s distribution as $\varepsilon$-uniform plus $(1-\varepsilon)$ on the argmax, and comparing against any other ε-soft $\pi$ expressed the same way, term-by-term the argmax action dominates). Chaining these two pillars: each full cycle of evaluation-then-improvement produces a policy whose value function is weakly better everywhere, and value functions are bounded above (rewards and hence returns are bounded, or discounted to be summable), so the sequence of value functions converges. At the fixed point, the policy is already ε-greedy with respect to its own $q_\pi$, satisfying the ε-soft Bellman optimality condition restricted to the ε-soft policy class.

Honest tradeoffs.

• With Exploring Starts, the fixed point is the true optimal policy $\pi_*$, because greedy improvement combined with guaranteed infinite exploration of every pair satisfies the classical GPI convergence theorem exactly.
• With ε-greedy (no exploring starts), the algorithm provably converges only to the optimal policy within the ε-soft policy class — a policy that must keep exploring with probability at least ε forever, so it cannot be arbitrarily close to a deterministic optimal policy unless ε is annealed toward zero.
• High variance: Monte Carlo returns $G_t$ accumulate all randomness over an entire episode, so estimates can be noisy, especially with long episodes or high-variance rewards. This is the central weakness that motivates SARSA: On-Policy TD Control, which bootstraps from one-step estimates instead of waiting for full returns, trading some bias for large variance reduction.
• Episodic requirement: pure Monte Carlo control needs episodes to terminate (or requires special handling for $\gamma=1$ non-terminating tasks), unlike temporal-difference methods that update online, step by step.

Consider a tiny 1-row gridworld with three non-terminal states $A, B, C$ in a line, and a terminal state $T$ to the right of $C$. From every state the agent can choose action Right (move toward $T$) or Left (move toward the wall, bouncing back to the same state at cost). Reward is $-1$ per step until reaching $T$, where the episode ends; $\gamma = 1$. The optimal policy is obviously "always go Right," but the agent starts knowing nothing, with $Q(s,a) = 0$ for all $s,a$, and $\varepsilon = 0.2$, uniform-random initial policy. Trace one early episode starting at $A$ under the (initially uniform-random) policy:

Episode length $T=5$. Returns computed backward ($\gamma=1$, so $G_t = \sum_{k>t} R_k$):

First-visit check: each $(S_t,A_t)$ pair above is distinct within this episode (no repeats), so all five updates apply. After this episode, with $N=1$ for each pair, $Q$ becomes exactly these returns:

Policy improvement at each visited state now makes Right the greedy action wherever both actions were tried (at $A$: $-4 > -5$, at $B$: $-2 > -3$), so $\pi(\text{Right}\mid A)$ and $\pi(\text{Right}\mid B)$ jump to $1-\varepsilon+\varepsilon/2 = 0.9$, while Left drops to $0.1$. Note that $(C,\text{Left})$ was never visited, so $Q(C,\text{Left})$ remains at its initial value $0$ — larger than the newly learned $Q(C,\text{Right}) = -1$! If the policy at $C$ were made purely greedy right now, it would wrongly prefer the untried Left action, since $0 > -1$. This is precisely why ε-softness matters: the ε-greedy policy still assigns Left at $C$ a small probability ($\varepsilon/2=0.1$), so it will eventually be sampled, its true (poor) value discovered, and the estimate corrected — whereas a fully greedy policy with no exploration could lock onto the wrong action at $C$ permanently. Across many further episodes, every action at every state keeps getting sampled with probability $\geq \varepsilon/|\mathcal{A}|$, all $Q(s,a)$ converge to the true $q_\pi(s,a)$ under the current $\pi$, and the ε-greedy policy converges toward always choosing Right (up to the residual ε exploration floor).

Monte Carlo methods for control emerged directly from the reinforcement learning framework formalized by Richard Sutton and Andrew Barto, who unified earlier scattered ideas — trial-and-error learning, dynamic programming, and temporal-difference methods — into the modern GPI-based treatment of prediction and control. The Monte Carlo approach itself borrows its statistical machinery (sampling to estimate expectations) from the Monte Carlo method invented for physics computations, but its application to control via action-values is a distinctly reinforcement-learning-era contribution built on the policy iteration ideas from dynamic programming (Bellman) and the exploration-versus-exploitation framing from bandit theory.

Monte Carlo Control's core idea — estimate action-values from sampled outcomes, then greedily (or ε-greedily) tighten the policy — underlies much of practical reinforcement learning even where the specific first-visit averaging is replaced by more sophisticated machinery. Classic applications include backgammon and other turn-based games where full episodes are cheap to simulate and the outcome (win/lose/score) is a natural terminal return. Monte Carlo Tree Search, used in AlphaGo and its successors, borrows the same "sample full rollouts, average returns, improve action selection" philosophy, generalized into a search tree rather than a flat table. In industrial and robotics settings, Monte Carlo-style episodic evaluation is used whenever a simulator can generate complete episodes but a differentiable or explicit transition model is unavailable — for instance, evaluating a trading strategy over historical episodes, or a dialogue policy over full conversations, where the "return" is only meaningful at the end of an interaction. The exploration mechanisms introduced here (ε-soft policies, and the exploring-starts idea of injecting randomized starting conditions) recur throughout deep RL, from ε-greedy DQN agents to the initial-state randomization used in robotics sim-to-real training. Most importantly, this algorithm is the conceptual stepping stone to SARSA: On-Policy TD Control and On-Policy vs Off-Policy Learning: nearly every idea here — action-values, GPI, ε-soft exploration, the improvement theorem — reappears verbatim once returns are replaced by bootstrapped one-step targets.

Ask the tutor: How does replacing full-episode Monte Carlo returns with one-step bootstrapped targets turn this algorithm into SARSA?