Monte Carlo methods

What Makes Monte Carlo Different?

Why model-free matters: In real-world problems (robotics, game playing, resource allocation), we rarely have accurate models of how the environment responds to actions. MC methods let us learn directly from interaction.

The Return: What We're Averaging

Formula Return from Time Step t

The return $G_t$ is the total discounted reward from time step $t$ onwards in an episode: $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{T-t-1} R_T$

Where:

$R_{t+1}$ is the reward received after time $t$
$\gamma \in [0,1]$ is the discount factor
$T$ is the terminal time step

Recursive form (useful for computation): $G_t = R_{t+1} + \gamma G_{t+1}$

Why discount? Immediate rewards are more certain than distant rewards. Discounting also ensures infinite-horizon problems have bounded returns. $\gamma=0$ means "myopic" (only immediate reward matters), $\gamma \to 1$ means "far-sighted" (future matters almost as much as present).

Derivation of recursive form: Starting from the definition: $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots$

Factor out $\gamma$ from all terms except the first: $G_t = R_{t+1} + \gamma(R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \cdots)$

The expression in parentheses is exactly $G_{t+1}$ : $G_t = R_{t+1} + \gamma G_{t+1}$

First-Visit vs Every-Visit MC

Why the distinction? In some episodes, you might visit the same state multiple times (e.g., in a maze, you might return to the same room). Should we count each visit separately or only the first?

Worked example First-Visit vs Every-Visit

Consider an episode in a 3-state chain: $S_1 \to S_2 \to S_1 \to S_3$ (terminal)

Rewards: +1 for reaching $S_3$ , 0 otherwise
Discount $\gamma = 1$ (undiscounted for simplicity) Returns from this episode:
First $S_1$ visit (step 0): $G_0 = 0+ 0 + 1 = 1$
$S_2$ visit (step 1): $G_1 = 0 + 1 = 1$
Second $S_1$ visit (step 2): $G_2 = 1$ First-Visit MC for $S_1$ : Only uses $G_0 = 1$ (first visit) Every-Visit MC for $S_1$ : Uses both $G_0 = 1$ and $G_2 = 1$ , averages to 1

In this case they agree, but with different rewards they would differ. Every-visit gives $S_1$ two data points from one episode.

Monte Carlo Policy Evaluation

Formula MC Estimation of State Value

To estimate $v_\pi(s)$ (value of state $s$ under policy $\pi$ ):

Initialize: $V(s) = 0$ , $N(s) = 0$ (visit counter) for all $s$
For each episode:

Generate episode following $\pi$ : $S_0, A_0, R_1, S_1, A_1, R_2, \ldots, S_T$
For each state $s$ $s$ visited (first-visit: only first occurrence):
- Calculate return: $G = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}$
- $N(s) \leftarrow N(s) + 1$
- $V(s) \leftarrow V(s) + \frac{1}{N(s)}[G - V(s)]$

The update is an incremental mean: $V(s) \leftarrow V(s) + \alpha(G - V(s))$ where $\alpha = 1/N(s)$ or a fixed step-size.

Why this works: We're computing sample mean of returns. By law of large numbers, as $N(s) \to \infty$ , $V(s) \to \mathbb{E}_\pi[G_t | S_t = s] = v_\pi(s)$ .

Why incremental update? Instead of storing all returns and recomputing mean: $\text{NewMean} = \frac{1}{n}\sum_{i=1}^n x_i = \frac{1}{n}\left[(n-1)\cdot\text{OldMean} + x_n\right] = \text{OldMean} + \frac{1}{n}(x_n - \text{OldMean})$

This is memory-efficient and mathematically equivalent.

Worked example MC Policy Evaluation: Blackjack

Problem: Estimate value of "stick on 20 or 21" policy in simplified blackjack.

States: (player sum, dealer showing, usable ace?)
Episode example: Start (12, 2, no) → hit → (19, 2, no) → stick → dealer draws to 21 → lose $R = -1$ First visit to state (12, 2, no):
$G = -1$ (final reward, $\gamma=1$ )
If $N$ (12, 2, no) $= 5$ , then this is the 6th visit: $V(12,2,\text{no}) \leftarrow V(12,2,\text{no}) + \frac{1}{6}[-1 - V(12,2,\text{no})]$ Why this step? We observed a new sample return from this state. We update our running average to incorporate this new evidence. The $1/6$ weight (sixth visit) ensures all samples contribute equally to the mean.

After 10,000 episodes, (12, 2, no) might have been visited 200 times with various returns, and $V(12,2,\text{no})$ converges to true value (around -0.3 to -0.5 depending on exact rules).

Monte Carlo Control: Learning Optimal Policy

Policy evaluation tells us how good a policy is. Monte Carlo control finds the optimal policy through generalized policy iteration: alternate between evaluation and improvement.

Formula MC Control with ε-Greedy Exploration

Goal: Learn optimal policy $\pi_*$ without a model.

Challenge: Must maintain exploration to find better actions. Solution: ε-greedy policies.

Algorithm (On-Policy First-Visit MC Control):

Initialize: $Q(s,a) = 0$ , $N(s,a) = 0$ , $\pi$ = ε-greedy w.r.t. $Q$
Repeat:

Generate episode using $\pi$ : $S_0, A_0, R_1, \ldots, S_T$
For each $(s,a)$ $(s, a)$ pair visited (first-visit):
- $G \leftarrow$ return following first occurrence of $(s,a)$
- $N(s,a) \leftarrow N(s,a) + 1$
- $Q(s,a) \leftarrow Q(s,a) + \frac{1}{N(s,a)}[G - Q(s,a)]$
Policy Improvement: For each $s$ in episode: $\pi(s) = \begin{cases} \arg\max_a Q(s,a) & \text{w.p. } 1-\varepsilon \\ \text{random action} & \text{w.p. } \varepsilon \end{cases}$ Why ε-greedy? Pure greedy ( $\varepsilon=0$ ) might never try actions that lead to optimal path. With $\varepsilon > 0$ , we explore (try random actions) with small probability, ensuring all $(s,a)$ pairs visited infinitely often → convergence to optimal policy.

Why learn $Q(s,a)$ instead of $V(s)$ ? For policy improvement, we need: $\pi'(s) = \arg\max_a \left[r(s,a) + \gamma \sum_{s'} P(s'|s,a) V(s') \right]$

But we don't know $P$ or $r$ (model-free)! With $Q(s,a)$ , improvement is simple: $\pi'(s) = \arg\max_a Q(s,a)$ No model needed— $Q$ already encapsulates the expected future.

Worked example MC Control: Grid World

Environment: 4×4 grid, goal at (3,3), -1 reward per step.

Episode under random policy: $(0,0) \xrightarrow{\text{right}} (0,1) \xrightarrow{\text{down}} (1,1) \xrightarrow{\text{down}} (2,1) \xrightarrow{\text{right}} (2,2) \xrightarrow{\text{right}} (2,3) \xrightarrow{\text{down}} (3,3)$

Total steps: 6, so $G = -6$ from start Q-value updates (first-visit, $\gamma=1$ ):
$Q((0,0), \text{right}) \leftarrow Q((0,0), \text{right}) + \alpha[-6 - Q((0,0), \text{right})]$
$Q((0,1), \text{down}) \leftarrow Q((0,1), \text{down}) + \alpha[-5 - Q((0,1), \text{down})]$
... (each state-action gets return from that point forward)

Why this step? Each $(s,a)$ pair gets credit for the return from when it was taken. After many episodes, $((0,0), \text{right})$ averages returns from all episodes where right was taken from start. Eventually, optimal actions (e.g., shortest paths) get better Q-values.

Policy improvement: After 100 episodes, if $Q((0,0), \text{right}) = -5.2$ and $Q((0,0), \text{down}) = -6.8$ , ε-greedy makes right action preferred (taken with probability $1-\varepsilon+\varepsilon/4$ if 4 actions).

Importance Sampling for Off-Policy Learning

Formula Importance Sampling Ratio

To estimate $\mathbb{E}_\pi[G_t | S_t=s]$ using episodes from policy $b$ : $\rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(A_k|S_k)}{b(A_k|S_k)}$

This is the importance sampling ratio: how much more/less likely is the trajectory under $\pi$ vs $b$ ?

Ordinary importance sampling (unbiased, high variance): $V(s) = \frac{\sum_{t \in \mathcal{T}(s)} \rho_{t:T(t)-1} G_t}{|\mathcal{T}(s)|}$

Weighted importance sampling (biased, lower variance): $V(s) = \frac{\sum_{t \in \mathcal{T}(s)} \rho_{t:T(t)-1} G_t}{\sum_{t \in \mathcal{T}(s)} \rho_{t:T(t)-1}}$

Where $\mathcal{T}(s)$ is the set of time steps where $s$ is visited.

Why the ratio? We're reweighting samples to correct for wrong distribution: $\mathbb{E}_b[\rho \cdot G] = \sum_\tau P_b(\tau) \cdot \frac{P_\pi(\tau)}{P_b(\tau)} \cdot G(\tau) = \sum_\tau P_\pi(\tau) \cdot G(\tau) = \mathbb{E}_\pi[G]$

Derivation of importance sampling correction: We want: $v_\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]$

But we sample from $b$ , giving: $\mathbb{E}_b[G_t | S_t = s]$

Trick: multiply and divide by $P_b(\tau)$ , i.e. insert the factor $1 = \dfrac{P_b(\tau|s)}{P_b(\tau|s)}$ and rewrite the numerator as $P_\pi(\tau|s)$ , where $\tau$ is the trajectory following $s$ : $\mathbb{E}_\pi[G | S_0=s] = \sum_\tau P_\pi(\tau|s)\, G(\tau) = \sum_\tau P_b(\tau|s)\,\frac{P_\pi(\tau|s)}{P_b(\tau|s)}\, G(\tau) = \mathbb{E}_b\!\left[\frac{P_\pi(\tau|s)}{P_b(\tau|s)}\, G \;\middle|\; S_0=s\right]$

The ratio $\dfrac{P_\pi(\tau)}{P_b(\tau)} = \prod_{t=0}^{T-1} \dfrac{\pi(A_t|S_t)}{b(A_t|S_t)}$ because the state-transition probabilities $P(S_{t+1}|S_t,A_t)$ appear identically in both numerator and denominator (same environment) and cancel.

Worked example Importance Sampling in Action

Scenario: Target policy $\pi$ always goes right. Behavior policy $b$ goes right 50%, left 50%.

Episode from $b$ : Start $S_0$ → right → $S_1$ → right → $S_2$ (terminal), $G_0 = 10$ Importance ratio: $\rho_{0:1} = \frac{\pi(\text{right}|S_0)}{b(\text{right}|S_0)} \times \frac{\pi(\text{right}|S_1)}{b(\text{right}|S_1)} = \frac{1.0}{0.5} \times \frac{1.0}{0.5} = 4.0$

Why this step? The trajectory (right, right) is 4× more likely under $\pi$ than $b$ . So we weight this episode's return by 4 when updating $V(S_0)$ for the target policy $\pi$ .

Weighted update: If this is our only episode, ordinary importance sampling gives $V(S_0) = \frac{4.0 \times 10}{1} = 40$ , while weighted importance sampling gives $V(S_0) = \frac{4.0 \times 10}{4.0} = 10$ . The weighted estimate is more stable here because dividing by the sum of ratios keeps the value on the same scale as the observed return.

Problem: If $b$ had taken left-left (probability 0 under $\pi$ ), that episode would have $\rho=0$ and contribute nothing. We can only learn from episodes that $\pi$ could have generated. If $\pi$ is deterministic and $b$ is stochastic, many episodes get zero weight → inefficient.

Common mistake Common Pitfalls

Mistake 1: "MC is just averaging—I can use partial episodes" Why it feels right: We're averaging returns, so why wait for episode to end? Why it's wrong: The return $G_t$ is defined as the sum to episode termination. Cutting an episode short gives a biased estimate (e.g., if you stop before reaching reward, $G_t = 0$ always). MC requires episodic tasks. Fix: Use TD methods (temporal difference) for continuing tasks or environments where episodes are too long.

Mistake 2: "Pure greedy works—why explore?" Why it feels right: If $Q(s, a_1) > Q(s, a_2)$ , always take $a_1$ to maximize return. Why it's wrong: Initial $Q$ estimates are based on limited samples. $a_2$ might actually be better but hasn't been tried enough. Greedy locks into local optima discovered early. Fix: ε-greedy guarantees exploration. Start with larger $\varepsilon$ (e.g., 0.1), decay over time. Ensures all actions tried infinitely often → finds global optimum eventually.

Mistake 3: "Importance sampling always works for off-policy" Why it feels right: The math shows $\mathbb{E}_b[\rho G] = \mathbb{E}_\pi[G]$ , so just weight samples. Why it's wrong: If $\pi$ and $b$ are very different, $\rho$ has huge variance. Most episodes get near-zero weight, few get enormous weight → estimates explode or converge slowly. If $\pi$ is deterministic and trajectory takes even one action with $\pi(a|s)=0$ , that entire trajectory contributes nothing. Fix: Keep $b$ close to $\pi$ (e.g., $b$ = ε-greedy version of greedy $\pi$ ). Use off-policy methods designed for this (like Q-learning with TD, covered separately).

MC vs Temporal Difference (TD)

Advantages of MC:

Unbiased estimates (converges to true value)
No bootstrapping → no error propagation from incorrect value estimates
Simple to implement and understand
Can learn from incomplete knowledge of environment (as long as episodes terminate)

Disadvantages of MC:

High variance: Single episode's return can vary wildly due to stochasticity
Requires episodic tasks (must reach terminal state)
Slow convergence: Need many episodes before estimates stabilize
Delayed learning: Can't update until episode completes (bad for long episodes)

Recall Explain to a 12-Year-Old

Imagine you're learning to play a video game and trying to figure out how good each level is. Monte Carlo way: You play the entire game from that level to the end, see your final score, and say "Okay, starting from level 3, I got 50 points on average." You do this over and over—play complete games, write down what happened, and average the results. It's like doing a science experiment where you run the full test every time and record the final result. Super accurate, but takes a long time because you have to finish each game!

Why it's cool: You don't need to know the game rules! You just play and see what happens. Even if the game is random (sometimes enemies appear, sometimes they don't), if you play enough times, your average is really close to the truth.

The tricky part: If the game is really long or never ends (like Minecraft), you can't use this method because you never get to the "final score"!

Connections

5.1-Markov-Decision-Processes: MC estimates values that satisfy Bellman equations
5.1.2-Dynamic-Programming

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Monte Carlo methods ka core idea bahut simple aur khoobsurat hai. Socho tum chess seekh rahe ho by playing poore-poore games, aur game khatam hone ke baad tum peeche mudke dekhte ho — "jab main is position mein tha, tab mera average final score kitna raha across saare games?" Bas yehi hai MC methods ka funda. Yeh algorithms complete episodes se seekhte hain aur jo actual returns milte hain unka average nikalte hain. Koi model nahi chahiye, koi guessing (bootstrapping) nahi — sirf raw experience start se end tak. Naam "Monte Carlo" isliye kyunki jaise casino mein random sampling hoti hai, waise hi yahan bhi tum jitne zyada episodes play karoge, tumhare estimates utne hi true values ke kareeb converge karte jaayenge.

Ab yeh important kyun hai? Real-world problems mein — jaise robotics, gaming, ya resource allocation — humein aksar pata hi nahi hota ki environment action ke response mein kaise behave karega. Yani hamare paas transition dynamics ya reward ka accurate model nahi hota. MC methods ka beauty yehi hai ki yeh model-free hain — seedhe interaction se seekhte hain bina kisi model ke. Jo cheez tum average karte ho woh hai return $G_t$ , matlab us time step se aage ka total discounted reward: $G_t = R_{t+1} + \gamma R_{t+2} + \cdots$ . Yeh discount factor $\gamma$ isliye hai kyunki immediate rewards zyada certain hote hain distant future ke rewards se, aur yeh ensure karta hai ki returns bounded rahein.

Ek chhoti si important detail hai — first-visit vs every-visit. Kabhi ek hi episode mein tum same state ko multiple baar visit kar sakte ho (jaise maze mein ghoomte hue same room mein wapas aa gaye). Toh sawaal yeh hai ki us state ka return count karte waqt sirf pehli visit lo (first-visit) ya har visit lo (every-visit). Dono hi methods sahi answer $v_\pi(s)$ tak converge karte hain jab visits infinite ho jayein, bas first-visit theoretically analyze karna easy hai kyunki har episode ek independent sample deta hai. Practically MC methods thode high-variance hote hain kyunki har return ek single random path hai stochastic environment ke through — lekin yeh unbiased hote hain, matlab lambe run mein bilkul sahi jagah pahunchte hain. Yehi trade-off aage TD learning samajhne ke liye base banata hai.

What Makes Monte Carlo Different?

The Return: What We're Averaging

First-Visit vs Every-Visit MC

Monte Carlo Policy Evaluation

Monte Carlo Control: Learning Optimal Policy

Importance Sampling for Off-Policy Learning

MC vs Temporal Difference (TD)

Connections

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Reinforcement Learning Foundations

Connections