---
title: Monte Carlo Methods
module: Tabular Solution Methods
moduleNumber: 2
lessonNumber: 3
order: 203
summary: >
  Monte Carlo methods learn value functions and optimal policies from complete
  sampled episodes, with no model of the environment: they simply average the
  returns that actually followed each state. We build prediction (first-visit and
  every-visit averaging), see why estimating action values forces the exploration
  question, and answer it two ways on-policy — exploring starts and epsilon-soft
  control. Throughout, Monte Carlo samples one whole trajectory to
  termination and never bootstraps.
topics: [Tabular Methods]
sources:
  - book: Sutton & Barto
    ref: "Ch. 5 — Monte Carlo Methods; §5.1 Monte Carlo Prediction; §5.2 Monte Carlo Estimation of Action Values"
  - book: Sutton & Barto
    ref: "§5.3 Monte Carlo Control; §5.4 Monte Carlo Control without Exploring Starts"
---

[Dynamic programming](/reinforcement-learning/tabular-methods/dynamic-programming)
solves a [Markov decision process](/reinforcement-learning/foundations/markov-decision-processes)
by leaning hard on the model: every update sweeps the dynamics
$p(s',r \mid s,a)$, expanding the exact expectation in the
[Bellman equation](/reinforcement-learning/foundations/value-functions-and-optimality)
over all successors. Monte Carlo methods throw that model away. They require only
_experience_ — sampled sequences of states, actions, and rewards from actual or
simulated interaction — and yet they can still estimate value functions and find
optimal policies.[^sb-intro] The trade is exact expectation for sampling: where DP
_computes_ $\mathbb{E}_\pi[G_t \mid S_t = s]$ from a known distribution, Monte
Carlo _averages_ the returns $G_t$ it actually observes.

The idea is the definition of a value function read literally. The value
$v_\pi(s)$ is the expected return from $s$ under $\pi$. An expectation is a
long-run average, so the most direct estimate imaginable is: follow $\pi$, and
every time you pass through $s$, record the return that followed; the running
average of those returns converges to $v_\pi(s)$. Nothing about the dynamics is
needed — the environment supplies the samples, and the law of large numbers does
the rest.

Because a "return" only makes sense once an episode has ended, we restrict Monte
Carlo to **episodic** tasks: experience divides into episodes that terminate no
matter what actions are chosen, and value estimates change only on the completion
of an episode. Monte Carlo is thus incremental episode-by-episode, but not
step-by-step.[^sb-intro] Each state acts like a separate
[bandit](/reinforcement-learning/foundations/multi-armed-bandits) problem — sample
and average a signal — except the problems are coupled: the return after acting in
one state depends on the actions taken in later states of the same episode, so as
the policy changes underneath, each state's bandit is nonstationary.

## Monte Carlo prediction

Fix a policy $\pi$ and suppose we want $v_\pi(s)$ from a batch of episodes
generated by following $\pi$. Each occurrence of state $s$ in an episode is a
**visit** to $s$. A single episode may visit $s$ several times; the first one is
the **first visit**. Two estimators split on which visits to count:[^sb-pred]

> **Definition (First-visit and every-visit MC).** _First-visit MC_ estimates
> $v_\pi(s)$ by averaging the returns following only the **first** visit to $s$ in
> each episode. _Every-visit MC_ averages the returns following **all** visits to
> $s$. Both converge to $v_\pi(s)$ as the number of (first) visits to $s$ goes to
> infinity.

The two are close cousins but have slightly different theory. First-visit MC is
the classic, studied since the 1940s: each first-visit return is an independent,
identically distributed, unbiased estimate of $v_\pi(s)$ with finite variance, so
by the law of large numbers the average converges, and the standard deviation of
its error falls as $1/\sqrt{n}$ in the number of returns $n$. Every-visit MC is
biased for finite $n$ (returns from repeated visits within one episode are
correlated) but its bias also vanishes asymptotically, and it extends more
naturally to
[function approximation](/reinforcement-learning/approximation/on-policy-prediction)
and eligibility traces.[^sb-pred]

The first-visit algorithm walks each episode _backward_, which lets it accumulate
the return $G_t = R_{t+1} + \gamma G_{t+1}$ with one multiply-add per step.

```algorithm
caption: $\textsc{First-Visit-MC-Prediction}(\pi)$ — estimate $V \approx v_\pi$
$V(s) \in \mathbb{R}$ arbitrarily, $Returns(s) \gets$ empty list, for all $s \in \mathcal{S}$
for each episode do
  generate an episode following $\pi$: $S_0, A_0, R_1, \ldots, S_{T-1}, A_{T-1}, R_T$
  $G \gets 0$
  for $t = T-1, T-2, \ldots, 0$ do
    $G \gets \gamma G + R_{t+1}$
    if $S_t \notin \{S_0, S_1, \ldots, S_{t-1}\}$ then // first-visit check
      append $G$ to $Returns(S_t)$
      $V(S_t) \gets \average(Returns(S_t))$
```

Delete the "unless $S_t$ appears earlier" line and the same loop becomes
every-visit MC: it records every step's return, first visit or not.

### A worked averaging trace

For example, run the backward loop on one short episode. Take $\gamma = 0.9$ and the
observed trajectory

$$
S_0 = A,\; R_1 = 0,\; S_1 = B,\; R_2 = 2,\; S_2 = A,\; R_3 = 0,\; S_3 = C,\; R_4 = 10,\; S_4 = \text{terminal},
$$

so state $A$ is visited twice (at $t=0$ and $t=2$). Running the loop from
$t = 3$ down to $0$ accumulates $G \gets \gamma G + R_{t+1}$:

$$
\begin{aligned}
t = 3:\quad & G = 0.9\cdot 0 + 10 = 10, & &\text{state } C,\; G_3 = 10,\\
t = 2:\quad & G = 0.9\cdot 10 + 0 = 9, & &\text{state } A,\; G_2 = 9,\\
t = 1:\quad & G = 0.9\cdot 9 + 2 = 10.1, & &\text{state } B,\; G_1 = 10.1,\\
t = 0:\quad & G = 0.9\cdot 10.1 + 0 = 9.09, & &\text{state } A,\; G_0 = 9.09.
\end{aligned}
$$

**First-visit MC** records the return only from the _earliest_ occurrence of each
state. State $A$'s first visit is $t = 0$, so it contributes $G_0 = 9.09$; the later
visit at $t = 2$ with return $9$ is skipped. States $B$ and $C$ each occur once and
contribute $10.1$ and $10$. **Every-visit MC** instead records both of $A$'s returns,
so $A$ gets the two-sample average $(9.09 + 9)/2 = 9.045$ from this single episode.
The two estimators already disagree after one episode; the gap is the within-episode
correlation that makes every-visit MC biased for finite $n$. Now suppose a second
episode gives a first-visit return of $7.5$ for $A$. The running first-visit estimate
becomes $(9.09 + 7.5)/2 = 8.295$ — a plain average of independent samples, exactly the
law-of-large-numbers estimator converging to $v_\pi(A)$.

### The backup diagram: one trajectory, no bootstrap

The contrast with DP is sharpest in the backup diagram — the picture of which
future outcomes an update draws on. A DP backup for $v_\pi$ roots at a state and
branches over _every_ one-step successor, weighting each by the model; it is one
level deep and exhaustive. A Monte Carlo backup roots at a state and follows the
_single sampled trajectory_ all the way down to the terminal state; it is one path
wide and full-episode deep.[^sb-pred]

$$
% caption: DP versus Monte Carlo backups for $v_\pi$. DP (left) expands one full
% level of the model — every successor $(s',r)$ weighted by $p(s',r\mid s,a)$ —
% and bootstraps off the successors' current estimates $v_\pi(s')$. MC (right)
% follows one sampled trajectory to termination, averaging the realized return
% $G_t$ with no reference to any other state's estimate.
\begin{tikzpicture}[>=stealth, font=\small,
  st/.style={circle, draw, fill=white, minimum size=5mm, inner sep=0pt},
  ac/.style={circle, draw, fill=black, minimum size=2.4mm, inner sep=0pt},
  lf/.style={circle, draw, fill=white, minimum size=4mm, inner sep=0pt},
  term/.style={draw, fill=black!12, minimum size=4.4mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % ===== LEFT: DP backup (one full level, bootstraps) =====
  \begin{scope}
    \node[st, label={[text=acc]above:s}] (s) at (0,3.2) {};
    \node[ac] (a1) at (-1.3,2.1) {};
    \node[ac] (a2) at (1.3,2.1) {};
    \draw[acc, thick] (s) -- (a1);
    \draw[acc, thick] (s) -- (a2);
    \node[lf] (l1) at (-2.0,0.9) {};
    \node[lf] (l2) at (-0.6,0.9) {};
    \node[lf] (l3) at (0.6,0.9) {};
    \node[lf] (l4) at (2.0,0.9) {};
    \draw[black] (a1) -- (l1); \draw[black] (a1) -- (l2);
    \draw[black] (a2) -- (l3); \draw[black] (a2) -- (l4);
    \node[anchor=north, font=\footnotesize] at (0,0.5) {all successors};
    \node[anchor=north, align=center, font=\footnotesize] at (0,-0.1)
      {DP: one level,\\bootstraps of\/f v(s')};
  \end{scope}
  % ===== RIGHT: MC backup (one trajectory to terminal) =====
  \begin{scope}[xshift=6.6cm]
    \node[st, label={[text=acc]above:s}] (t0) at (0,3.2) {};
    \node[ac] (m0) at (0,2.55) {};
    \node[st] (t1) at (0,1.9) {};
    \node[ac] (m1) at (0,1.25) {};
    \node[st] (t2) at (0,0.6) {};
    \draw[acc, thick] (t0) -- (m0);
    \draw[acc, thick] (m0) -- (t1);
    \draw[acc, thick] (t1) -- (m1);
    \draw[acc, thick] (m1) -- (t2);
    \node[ac] (mZ) at (0,-0.75) {};
    \draw[acc, thick, dotted] (t2) -- (mZ);
    \node[term] (tT) at (0,-1.4) {};
    \draw[acc, thick] (mZ) -- (tT);
    \node[anchor=west, align=left, font=\footnotesize] at (0.55,1.9)
      {sampled\\trajectory};
    \node[anchor=north, align=center, font=\footnotesize] at (0,-1.75)
      {MC: full episode,\\no bootstrap};
  \end{scope}
\end{tikzpicture}
$$

Two facts fall out of that picture. First, **Monte Carlo does not bootstrap**: the
estimate for one state is built from realized returns, never from the current
estimate of another state. DP's every update reuses neighbors' estimates; MC's
uses none. Second, the estimates for different states are **independent** — the
cost of estimating one state's value is independent of the number of states. If
you care about the value of only a handful of states, you can generate episodes
_starting_ from just those states and average their returns, ignoring the rest of
the state space entirely.[^sb-pred] DP has no such option; it must sweep everything.

### Blackjack

The casino game of blackjack makes a clean episodic MDP. The player draws cards to
get a hand sum as close to 21 as possible without exceeding it; face cards count
10, and an ace counts 11 unless that would bust, in which case it counts 1 (a
**usable** ace is one still counting as 11). The player _hits_ (draws) or _sticks_
(stops); busting loses. Each game is an episode with reward $+1$, $-1$, or $0$ for
win, loss, or draw, all intermediate rewards zero and $\gamma = 1$, so the terminal
reward _is_ the return. A state is the triple (current sum $12$–$21$, dealer's one
showing card, usable ace or not) — 200 states in all.[^sb-blackjack]

Take the policy "stick on 20 or 21, otherwise hit." There is no easy way to apply
DP here: you would need $p(s',r\mid s,a)$ — for instance the probability of
finishing with $+1$ given the dealer shows a 6 and you stick on 14 — and computing
all those distributions in advance is delicate and error-prone. But _simulating_
games is trivial. So we play many episodes under the policy and average the
returns following each state. After 500,000 games the value function is well
approximated; states with a usable ace stay noisier, because they arise less
often.[^sb-blackjack] This is a real advantage even here, where the dynamics are
technically known: Monte Carlo needs only a _sample_ model — something that
generates transitions — not the full distribution DP demands.

## Estimating action values

Without a model, state values alone are not enough. With a model you can turn
$v_\pi$ into a policy by a one-step lookahead — for each action, combine the reward
and the successor's value, pick the best — but that lookahead _needs_ the dynamics.
Without them, $v_\pi(s)$ tells you how good a state is but not which action gets you
somewhere good. So the primary target of Monte Carlo control is the **action-value**
function $q_\pi(s,a)$: with $q$ in hand, the greedy policy is just
$\arg\max_a q(s,a)$, no model required.[^sb-actionvalues]

Estimating $q_\pi$ is the same averaging, indexed by pairs. A state–action pair
$(s,a)$ is _visited_ in an episode if $s$ is visited and $a$ is taken there;
first-visit MC averages returns following the first such visit in each episode,
every-visit MC averages all of them. Both converge to $q_\pi(s,a)$ as visits to
each pair go to infinity.

The complication is **exploration**. Many state–action pairs may never be visited
at all. If $\pi$ is deterministic, then following it you observe returns for only
_one_ action per state — the one $\pi$ chooses — and the estimates for the other
actions never improve. But comparing alternatives is the whole point of estimating
action values: to improve a policy you must know the value of actions it does _not_
currently take.

$$
% caption: Why a deterministic policy starves the action-value estimates. Following
% $\pi$ deterministically, only the chosen action (solid) ever returns data; the
% alternatives (dashed) are never sampled, so their $q_\pi(s,a)$ estimates cannot
% improve — and policy improvement needs exactly those unseen values.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=6mm, inner sep=0pt},
  ac/.style={circle, draw, fill=black, minimum size=2.6mm, inner sep=0pt},
  gh/.style={circle, draw, dashed, fill=white, minimum size=2.6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[st] (s) at (0,0) {s};
  \node[ac] (a2) at (2.4,0) {};
  \node[gh] (a1) at (1.6,1.4) {};
  \node[gh] (a3) at (1.6,-1.4) {};
  \draw[acc, thick] (s) -- (a2);
  \draw[red, dashed] (s) -- (a1);
  \draw[red, dashed] (s) -- (a3);
  \node[acc, anchor=south, font=\scriptsize] at (1.6,0.08) {chosen: sampled};
  \node[red, anchor=south west, font=\scriptsize] at (1.7,1.45) {never taken};
  \node[red, anchor=north west, font=\scriptsize] at (1.7,-1.55) {never taken};
\end{tikzpicture}
$$

One way to force coverage is the assumption of **exploring starts**: episodes begin
in a state–action pair chosen so that _every_ pair has nonzero probability of being
the start. Over infinitely many episodes every pair is then visited infinitely
often.[^sb-actionvalues]

> **Definition (Exploring starts).** The assumption that episodes start in a
> state–action pair drawn from a distribution giving every pair positive
> probability. It guarantees that all state–action values are estimated, but it is
> unrealistic when learning from actual interaction — you rarely get to choose the
> starting conditions of the real world.

Exploring starts is a crutch. It works for simulated episodes but cannot be relied
on in general. The two ways to drop it — keep the behaving policy stochastic
everywhere (on-policy), or learn about one policy while behaving by another
(off-policy) — organize the rest of the lesson.

## Monte Carlo control

To find optimal policies, Monte Carlo slots evaluation into **generalized policy
iteration** (GPI): maintain a policy and a value function, repeatedly push the
value toward $q_\pi$ (evaluation) and repeatedly make the policy greedy in the
current value (improvement). The two chase each other to a joint fixed point that
is optimal.[^sb-control] The classical version alternates _complete_ evaluations
and improvements,

$$
\pi_0 \xrightarrow{\;\text{E}\;} q_{\pi_0} \xrightarrow{\;\text{I}\;} \pi_1
\xrightarrow{\;\text{E}\;} q_{\pi_1} \xrightarrow{\;\text{I}\;} \pi_2
\xrightarrow{\;\text{E}\;} \cdots \xrightarrow{\;\text{I}\;} \pi_\ast
\xrightarrow{\;\text{E}\;} q_\ast,
$$

where $\xrightarrow{\text{E}}$ is a full MC policy evaluation and
$\xrightarrow{\text{I}}$ is greedy improvement. Improvement needs no model: for any
action-value function $q$, the greedy policy is
$\pi(s) \doteq \arg\max_a q(s,a)$. Why does going greedy in $q$ help? Because the
greedy action is, by definition, the best-scoring action, so switching to it can
only raise the value at that state — the same logic as in DP, now with $q$ instead of
a one-step model lookahead. The **policy improvement theorem** applied to
$\pi_{k+1} = \text{greedy}(q_{\pi_k})$ makes this precise:

$$
q_{\pi_k}(s, \pi_{k+1}(s))
= q_{\pi_k}\!\big(s, \arg\max_a q_{\pi_k}(s,a)\big)
= \max_a q_{\pi_k}(s,a)
\;\ge\; q_{\pi_k}(s, \pi_k(s))
\;\ge\; v_{\pi_k}(s),
$$

so each $\pi_{k+1}$ is uniformly at least as good as $\pi_k$, and the process
converges to $\pi_\ast$ and $q_\ast$ from sample episodes alone.[^sb-control]

$$
% caption: Generalized policy iteration with Monte Carlo. Evaluation drives the
% estimate $Q$ toward $q_\pi$ by averaging returns; improvement makes $\pi$ greedy
% in $Q$. Each step spoils the other's target, yet together they climb to the
% optimal pair $(\pi_*, q_*)$.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \node[align=center] (pi) at (-2.6,0) {policy\\pi};
  \node[align=center] (q)  at (2.6,0)  {value\\Q};
  \draw[->, acc, thick] (pi) to[bend left=32] node[above, font=\footnotesize] {evaluation: Q $\to$ q\_pi} (q);
  \draw[->, thick] (q) to[bend left=32] node[below, font=\footnotesize] {improvement: pi $\to$ greedy(Q)} (pi);
  \node[acc, anchor=west, font=\footnotesize] at (3.35,0) {(pi-star, q-star)};
\end{tikzpicture}
$$

Two unrealistic assumptions bought that clean guarantee: exploring starts, and
infinitely many episodes per evaluation. The second is easy to relax. Rather than
run each evaluation to convergence, we can evaluate _toward_ $q_{\pi_k}$ without
finishing — exactly the move value iteration makes for DP. For Monte Carlo the
natural rhythm is episode-by-episode: after each episode, average the observed
returns to update $Q$ at the visited pairs, then immediately make the policy greedy
at those states. This gives **Monte Carlo ES** (Exploring Starts).[^sb-control]

```algorithm
caption: $\textsc{Monte-Carlo-ES}$ — estimate $\pi \approx \pi_\ast$
$\pi(s) \in \mathcal{A}(s)$ arbitrarily, $Q(s,a) \in \mathbb{R}$ arbitrarily, $Returns(s,a) \gets$ empty, for all $s,a$
for each episode do
  choose $S_0 \in \mathcal{S}$, $A_0 \in \mathcal{A}(S_0)$ at random, all pairs with probability $> 0$
  generate an episode from $S_0, A_0$ following $\pi$: $S_0, A_0, R_1, \ldots, S_{T-1}, A_{T-1}, R_T$
  $G \gets 0$
  for $t = T-1, T-2, \ldots, 0$ do
    $G \gets \gamma G + R_{t+1}$
    if $(S_t, A_t) \notin \{(S_0, A_0), \ldots, (S_{t-1}, A_{t-1})\}$ then
      append $G$ to $Returns(S_t, A_t)$
      $Q(S_t, A_t) \gets \average(Returns(S_t, A_t))$
      $\pi(S_t) \gets \arg\max_a Q(S_t, a)$
```

Applied to blackjack — where exploring starts is trivial to arrange, since we
simply deal random opening states and pick the first action at random — Monte Carlo
ES recovers essentially the known optimal strategy. (That Monte Carlo ES converges
at all is intuitively clear: a fixed point requires both policy and value to be
mutually consistent, which happens only at the optimum. A formal proof remains one
of the open theoretical questions in the field.)[^sb-control]

## On-policy control with ε-soft policies

To drop exploring starts on-policy, we keep the behaving policy **soft**: every
action retains some probability everywhere, $\pi(a\mid s) > 0$ for all $s,a$,
shifting only gradually toward determinism. The standard choice is
**$\varepsilon$-greedy**: with probability $1 - \varepsilon$ take the greedy
action, and with probability $\varepsilon$ pick uniformly at random among all
actions.[^sb-onpolicy] So every nongreedy action keeps probability
$\varepsilon / |\mathcal{A}(s)|$, and the greedy action gets the rest,
$1 - \varepsilon + \varepsilon/|\mathcal{A}(s)|$.

> **Definition ($\varepsilon$-soft and $\varepsilon$-greedy).** A policy is
> _$\varepsilon$-soft_ if $\pi(a\mid s) \ge \varepsilon/|\mathcal{A}(s)|$ for every
> state and action, for some $\varepsilon > 0$ — no action is ever ruled out. It is
> _$\varepsilon$-greedy_ if it puts the minimum $\varepsilon/|\mathcal{A}(s)|$ on
> every action and the remaining probability on the greedy one; among
> $\varepsilon$-soft policies these are the closest to greedy.

Now GPI cannot push the policy all the way to greedy — that would kill exploration.
Instead, improvement moves the policy toward the $\varepsilon$-greedy policy for the
current $Q$. The policy improvement theorem still applies: any $\varepsilon$-greedy
policy with respect to $q_\pi$ is an improvement over any $\varepsilon$-soft $\pi$.

```algorithm
caption: $\textsc{On-Policy-First-Visit-MC-Control}$ — $\varepsilon$-soft, estimate $\pi \approx \pi_\ast$
parameter: small $\varepsilon > 0$
$\pi \gets$ an arbitrary $\varepsilon$-soft policy; $Q(s,a) \in \mathbb{R}$ arbitrarily; $Returns(s,a) \gets$ empty
for each episode do
  generate an episode following $\pi$: $S_0, A_0, R_1, \ldots, S_{T-1}, A_{T-1}, R_T$
  $G \gets 0$
  for $t = T-1, T-2, \ldots, 0$ do
    $G \gets \gamma G + R_{t+1}$
    if $(S_t, A_t) \notin \{(S_0, A_0), \ldots, (S_{t-1}, A_{t-1})\}$ then
      append $G$ to $Returns(S_t, A_t)$
      $Q(S_t, A_t) \gets \average(Returns(S_t, A_t))$
      $A^\ast \gets \arg\max_a Q(S_t, a)$ // ties broken arbitrarily
      for each $a \in \mathcal{A}(S_t)$ do
        if $a = A^\ast$ then
          $\pi(a \mid S_t) \gets 1 - \varepsilon + \varepsilon/|\mathcal{A}(S_t)|$
        else
          $\pi(a \mid S_t) \gets \varepsilon/|\mathcal{A}(S_t)|$
```

The catch is that this converges only to the best policy _among $\varepsilon$-soft
policies_, not to the unconstrained optimum — the price of forcing perpetual
exploration into the policy you actually follow. That residual suboptimality is
what off-policy learning removes.

This continues in [Monte Carlo Methods: Off-Policy Learning](/reinforcement-learning/tabular-methods/monte-carlo-off-policy), which removes that ceiling: it learns about a greedy target policy from data generated by a soft behavior policy, using importance sampling to correct for the mismatch, and closes by placing Monte Carlo on the model/bootstrap map beside dynamic programming and temporal-difference learning.

[^sb-intro]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), Ch. 5 — introduction: Monte Carlo methods require only sample experience (actual or simulated), average complete returns rather than partial ones, are defined for episodic tasks, and change estimates only on episode completion.
[^sb-pred]: **Sutton & Barto**, §5.1 — Monte Carlo Prediction: first-visit versus every-visit MC and their convergence (5.1 algorithm box); the Monte Carlo backup diagram (one sampled trajectory to termination) contrasted with the DP backup; that MC does not bootstrap and that per-state estimates are independent.
[^sb-blackjack]: **Sutton & Barto**, §5.1, Example 5.1 (Blackjack): the episodic MDP formulation ($\gamma = 1$, terminal reward equals return, 200 states, usable-ace notion), the "stick on 20 or 21" policy evaluated by MC (Figure 5.1), and the difficulty of applying DP without the explicit distribution $p$.
[^sb-actionvalues]: **Sutton & Barto**, §5.2 — Monte Carlo Estimation of Action Values: why state values are insufficient without a model, first/every-visit estimation of $q_\pi(s,a)$, the maintaining-exploration problem for deterministic policies, and the exploring-starts assumption.
[^sb-control]: **Sutton & Barto**, §5.3 — Monte Carlo Control: GPI with MC evaluation, the policy-iteration chain and the policy-improvement inequality for greedy $\pi_{k+1}$, relaxing the infinite-episodes assumption episode-by-episode, and the Monte Carlo ES algorithm (Example 5.3, Figure 5.2).
[^sb-onpolicy]: **Sutton & Barto**, §5.4 — Monte Carlo Control without Exploring Starts: $\varepsilon$-soft and $\varepsilon$-greedy policies, the on-policy first-visit MC control algorithm, and the policy-improvement argument (5.2) showing convergence to the best $\varepsilon$-soft policy.