Foundations — Monte Carlo methods

This page assumes you have never seen the symbols in the parent Monte Carlo note. We will build every letter, subscript, and Greek symbol from the ground up, in an order where each new idea stands on the one before it. By the end you will be able to read the parent note line by line without stopping.

A quick note on how figures are named: each picture on this page is tagged s01, s02, s03 in the order it appears. When the text says "look at figure s01", it means the first embedded picture, and so on — the little tag matches the file name so you never lose track of which drawing we mean.

0. The stage: what is an "episode"?

Before any letter, picture the thing Monte Carlo methods live inside.

An episode is one complete run of a task from a start to a finish. A chess game from first move to checkmate. One hand of blackjack from deal to payout. One walk through a maze from entrance to exit.

Look at the picture above (figure s01). Time flows left to right. At each moment you are in some situation (a circle), you do something (an arrow), and you get a number back (a reward). Then the world moves you to the next situation. The chain ends — that is the crucial word. Monte Carlo only works when the chain ends, because we need to reach the finish before we can look back and add up what happened.

Everything below is just names for the parts of that picture.

1. State $S_t$ — "where you are right now"

• Plain words: $S$ stands for "State". The little $t$ below it (a subscript) is a clock reading — $S_0$ is where you start, $S_1$ is where you are one step later, and so on.
• The picture: each circle in figure s01. In blackjack a state might be (player total 19, dealer shows 2, no usable ace). In a maze it is which room you stand in.
• Why the topic needs it: Monte Carlo estimates "how good is this state?" — so it must be able to point at "this state" with a name. $S_t$ is that name.

2. Action $A_t$ — "what you chose to do"

• Plain words: $A$ for "Action", subscript $t$ = which step. $A_0$ is your first move.
• The picture: the labelled arrows in figure s01 (hit, stick, right, down).
• Random variable too: like $S_t$, the action $A_t$ can vary run to run (especially when the policy chooses randomly), so it is also a random variable filled in by chance each episode.
• Why needed: the control half of Monte Carlo has to compare actions to find the best one. No actions, nothing to improve.

3. Reward $R_{t+1}$ — "the number the world hands back"

• The picture: the numbers floating above each arrow in figure s01 (0, 0, +1, -1).
• Also a random variable: the same action in the same state can yield different rewards on different runs, so $R_{t+1}$ is random too.
• Why needed: rewards are the only feedback we get. Monte Carlo has no rulebook, no map — just this trickle of numbers. Everything we learn is built by adding these up.

4. Terminal time $T$ — "when the episode ends"

• Plain words: a plain capital $T$ = "Terminal". If a maze run takes 6 moves, then $T=6$.
• The picture: the double circle on the far right of figure s01.
• Why needed: Monte Carlo must reach $T$ before it can compute anything — that is the whole "wait until the end, then look back" idea. This is exactly why MC only works on tasks that terminate.

5. The discount factor $\gamma$ — "how much the future is worth"

Now the first Greek letter. It is pronounced "gamma" and drawn $\gamma$.

Look at figure s02. Each bar is the weight ${\gamma }^k$ applied to a reward that is $k$ steps away. When $\gamma =0.9$ the bars fade slowly — the far future still matters. When $\gamma =0.5$ they collapse fast — you barely care about anything distant.

• Reading the extremes: $\gamma =0$ means "I only care about the very next reward" (myopic — near-sighted). $\gamma \to 1$ (gamma creeping toward one) means "a reward 100 steps away is almost as precious as one right now" (far-sighted).
• The superscript ${\gamma }^k$: this just means "$\gamma$ multiplied by itself $k$ times". ${\gamma }^0=1$ (no shrink), ${\gamma }^1=\gamma$, ${\gamma }^2=\gamma \times \gamma$, and so on. Since $\gamma \le 1$, each power is smaller than the last — that is the shrinking you see in s02.

6. The Return $G_t$ — "the total score, looking forward from now"

This is the star of the show. Everything before was setup.

Let us read it slowly, term by term, using figure s02's weights:

• $R_{t+1}$ is the next reward, weighted by ${\gamma }^0=1$ (full value, no delay).
• $\gamma R_{t+2}$ is the reward two steps out, shrunk once.
• ${\gamma }^2{R}_{t+3}$ shrunk twice, and so on.
• The last term ${\gamma }^{T-t-1}{R}_T$ is the final reward at the end; the exponent $T-t-1$ just counts how many steps of delay separate "now" ($t$) from "the end" ($T$).

The recursive shortcut

There is a beautiful shortcut. Factor $\gamma$ out of everything except the first term:

$G_t=R_{t+1}+\gamma \left(\underset{\text{this is exactly }{G}_{t+1}}{\underbrace{R_{t+2}+\gamma R_{t+3}+\cdots }}\right)$

The bracket is the return starting one step later, which is $G_{t+1}$. So:

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

Read figure s03 right-to-left: the sweep begins at the terminal circle where $G_T=0$, and at each earlier state we stack "my reward now" on top of "$\gamma \times$ the return I already know from the next state".

7. Policy $\pi$ — "your rulebook for choosing actions"

The next Greek letter, "pi", drawn $\pi$ (same symbol as $3.14\dots$ but here it means something totally different — do not confuse them).

• The picture: a table pinned to each circle in figure s01 saying "in this state, do this".
• Why needed: Monte Carlo evaluates a specific policy — "how good is state $s$ if I keep behaving like $\pi$?" Without naming the behaviour, "how good is this state" has no answer, because the future depends on how you act. The policy $\pi$ is also what decides the probabilities of each random $A_t$ — so it shapes the whole distribution of returns.

8. Expectation $\mathbb{E}$ — "the long-run average"

Before we can define value we need the averaging symbol itself.

• Plain words: think of rolling a fair die forever and averaging: the average settles on $3.5$. That $3.5$ is $\mathbb{E}[\text{die}]$ — a number no single roll ever shows, yet the true center of them all.
• The subscript ${\mathbb{E}}_{\pi }$: the outcomes of $S_t,A_t,R_t$ depend on how you behave. Writing ${\mathbb{E}}_{\pi }$ says "average over the randomness produced when actions are chosen by policy $\pi$". Change $\pi$ and the whole distribution — and hence the average — changes.
• The bar $\mid$ inside, as in ${\mathbb{E}}_{\pi }[G_t\mid S_t=s]$: the bar reads "given that". So the whole thing means "the average return, over all $\pi$-driven episodes, among only those runs where the state at time $t$ was $s$".
• Why the topic needs it: the true value we chase is a long-run average of a random return. $\mathbb{E}$ is the precise name for that average. Monte Carlo's whole job is to estimate this $\mathbb{E}$ by literally averaging observed samples.

9. The value function $v_{\pi }(s)$ — "how good a state is, on average"

Now averaging finally meets value.

Every symbol here is now earned: ${\mathbb{E}}_{\pi }[\cdots ]$ is the $\pi$-driven long-run average (§8), the bar $\mid$ is "given that", and $S_t=s$ says the random state landed on the particular state $s$.

10. First-visit vs every-visit — which returns we average

Inside a single episode you might pass through the same state $s$ more than once. That raises a fair question: if $s$ shows up twice in one run, do we record both returns or only the first? The answer defines two variants.

11. The action-value $Q_{\pi }(s,a)$ — "how good doing $a$ in $s$ is"

• The subscript $\pi$ matters: just like $v_{\pi }$, the action-value depends on the policy you follow after the first action — so it wears the same $\pi$ label. Different policy afterward, different $Q_{\pi }$.
• Difference from $v$: $v_{\pi }(s)$ scores a state; $Q_{\pi }(s,a)$ scores a state-and-a-choice.
• Why the topic desperately needs $Q$: to improve a policy you must compare actions. With only $v$, choosing the best action needs a model of the world (if I do a, where do I land?) — which model-free MC does not have. But $Q_{\pi }(s,a)$ already bakes in the consequence, so "pick the best action" becomes simply "pick the $a$ with the largest $Q_{\pi }(s,a)$". No model required.

12. Counters, initialization, and the incremental mean: $N(s)$, $V(s)$, $\alpha$

To average returns as they arrive (without hoarding every number), we keep two running quantities per state:

Initialization (before any episode): set $V(s)=0$ and $N(s)=0$ for every state $s$. Starting the count at zero is essential — the very first update will make $N(s)=1$, so the first sample entirely replaces the initial guess (as it should, since a single sample is its own average). The starting value $V(s)=0$ is arbitrary and gets washed out immediately by that first update.

Now the update loop. Each time a fresh return $G$ arrives for state $s$ (first-visit: only its first occurrence in the episode):

1. First bump the count: $N(s)\leftarrow N(s)+1$
2. Then nudge the estimate using the updated count: $V(s)\leftarrow V(s)+\frac{1}{N(s)}[G-V(s)]$

The order matters: we increment $N(s)$ first so that the fraction $\frac{1}{N(s)}$ uses the new, correct visit number. On the very first visit this makes $N(s)=1$ and the step is $\frac{1}{1}(G-V)=G-V$, so $V$ jumps straight to $G$ — exactly the mean of one sample.

Reading the update: the arrow $\leftarrow$ means "becomes / gets updated to". The bracket $G-V(s)$ is the error — how far the new sample sits from our current guess. We step a fraction $\frac{1}{N(s)}$ of the way toward it.

Sometimes we replace $\frac{1}{N(s)}$ with a fixed small number $\alpha$ (Greek "alpha"), giving:

$V(s)\leftarrow V(s)+\alpha [G-V(s)]$

• Why a fixed $\alpha$ instead of $\frac{1}{N}$? With $\frac{1}{N}$, every sample counts equally forever — great for a fixed world. A fixed $\alpha$ forgets old samples slowly, letting the estimate track a changing world (useful when the policy is still improving). $\alpha$ is a knob between "trust all history equally" and "chase recent evidence".

13. $\epsilon$-greedy — "mostly best, sometimes curious"

Last Greek letter, "epsilon", drawn $\epsilon$ — think "a tiny bit".

• $\arg {\max }_a{Q}_{\pi }(s,a)$ reads "the action $a$ that makes $Q_{\pi }(s,a)$ largest" ($\arg \max$ = "the argument giving the max", i.e. which $a$, not the value).
• Why needed: if you always pick what looks best right now (pure greedy, $\epsilon =0$), you might never try the action that would have been great — you'd never gather evidence for it. A dash of randomness $\epsilon >0$ guarantees every state-action pair gets sampled eventually, which is exactly what the "average over many samples" promise requires.

The prerequisite map

Read top to bottom: episodes give you states, actions, and rewards; rewards fold into the return $G_t$ (with the help of $\gamma$ and the base case $G_T=0$); the expectation $\mathbb{E}$ turns returns into true value; and value plus $Q_{\pi }$ plus exploration is exactly what Monte Carlo needs.

Equipment checklist

Cover the right side and see if you can answer each before revealing.