Monte Carlo Methods

7.1 Foundations Review: The Journey So Far

The lecture opened with a comprehensive review of everything covered in the first six lectures. A student volunteered to walk through the entire arc, providing a useful map of the conceptual terrain that leads into Monte Carlo methods.

7.1.1 RL vs Supervised vs Unsupervised Learning

Reinforcement learning differs from supervised and unsupervised learning in a fundamental way. In supervised learning, we have labeled input-output pairs \(\,$X,Y)$ — the correct answer is provided for every training example. In unsupervised learning, we do tasks like clustering or market basket analysis without labels — the algorithm discovers structure on its own. Reinforcement learning is different: an agent interacts with an environment and learns from experience by maximizing the reward it receives. The key insight is that the agent learns what to do by actually doing things and observing consequences, not by being told the right answer.

When to use RL. Reinforcement learning is the right tool when a model of the environment is not known but an analytical solution is also not available. Whenever a solid analytical solution exists, supervised or unsupervised learning is preferred. The textbook emphasizes that RL is designed for situations where an agent learns by interacting with its environment — it requires no prior knowledge of the environment's dynamics, yet can still attain optimal behavior.

7.1.2 Core Elements and Value Functions

Core elements of RL. The fundamental elements are: the agent (the learner we are training), the environment (where the agent interacts), actions (what the agent does), states (the agent's current situation or point in the environment), rewards (feedback from the environment), policies (the agent's strategy), and value functions (how good a state or state-action pair is under a given policy).

A policy $\pi$ is a mapping from states to probabilities of selecting each possible action. If the policy is deterministic, it maps each state to a single action. If stochastic, it maps each state to a probability distribution over actions.

Value functions. There are two types: state value functions $V_{\pi }(s)$ and action value functions $Q_{\pi }(s,a)$. The state value function estimates the expected return starting from a given state under policy $\pi$:

where $G_t$ is the return (cumulative discounted reward) from time $t$. The action value function goes one step further — it estimates the expected return starting from a state, taking a specific action, and then following policy $\pi$ afterward:

As the student described it: "state value function is from the current point and action value function is after taking action, whatever value I can generate."

7.1.3 Multi-Armed Bandits and MDPs

Multi-armed bandits. The multi-armed bandit problem introduced the exploration-exploitation tradeoff. Given some unknown population distribution (like a slot machine with multiple arms), the goal is to estimate which arm is best. Algorithms for this include:

• Greedy bandits: Always pick the arm with highest estimated value. Simple but may miss better arms.
• Epsilon-greedy: Pick the best arm most of the time, but randomly explore a fraction $ϵ$ of the time. Balances exploitation with exploration.
• UCB (Upper Confidence Bound): Creates a confidence interval around each arm's estimated value and picks the arm with the highest upper bound. Naturally balances exploration and exploitation based on uncertainty.

Agent-environment interface and MDPs. The transition from bandits to Markov Decision Processes introduced state into the picture. In bandits, actions are stateless — each pull is independent. In an MDP, the agent moves from state to state: at time $t$, the agent is in state $S_t$, takes action $A_t$, receives reward $R_{t+1}$, and transitions to state $S_{t+1}$. This is the $S_0,A_0,R_1,S_1$ ordering.

The MDP framework is defined by:

• A set of states $S$
• A set of actions $A$
• A transition probability function $P(s^{\prime }|s,a)$ — the probability of reaching state $s^{\prime }$ from state $s$ after taking action $a$
• A reward function $R(s,a,s^{\prime })$ — the reward received for transitioning from $s$ to $s^{\prime }$ via action $a$
• A discount factor $\gamma \in [0,1]$ — how much we value future rewards relative to immediate ones

7.1.4 Returns and Bellman Equations

Returns. Two types of returns were covered. Episodic return is a simple sum of all future rewards:

where $T$ is the terminal time step. Discounted return uses a discount factor $\gamma \in [0,1]$ to weight future rewards:

The discount factor controls how much we value distant future rewards relative to immediate ones.

Why discounting matters. There are several reasons to use discounting:

1. Mathematical convenience. Without discounting ($\gamma =1$), the return might be infinite for continuing tasks. Discounting ensures the return is finite.
2. Uncertainty about the future. Future rewards are less certain than immediate ones — discounting reflects this uncertainty.
3. Economic reasoning. A dollar today is worth more than a dollar tomorrow (time value of money).
4. Animal behavior. Animals (including humans) tend to prefer immediate rewards over delayed ones.

Bellman equations. The Bellman equation expresses the value of a state in terms of the values of successor states:

This equation says: the value of state $s$ is the expected immediate reward plus the discounted value of the next state, averaged over all possible actions (weighted by the policy) and all possible next states (weighted by transition probabilities).

The Bellman optimality equation gives the value under the optimal policy:

Here, instead of averaging over actions according to the policy, we pick the best action (the one that maximizes the expected return).

A critical requirement: the Bellman equation assumes the model dynamics $P(s^{\prime }|s,a)$ are known. If model dynamics are not well defined, the Bellman equation cannot be applied directly. This is the key limitation that motivates Monte Carlo methods.

Dynamic programming and Generalized Policy Iteration (GPI). Dynamic programming solves the Bellman equation by iteratively computing value functions. It alternates between:

• Policy evaluation: Compute $V_{\pi }$ for the current policy $\pi$. Start with arbitrary values and repeatedly apply the Bellman equation until the values converge.
• Policy improvement: Update the policy greedily with respect to the current values. For each state, choose the action that maximizes the expected return.

When policy improvement finds no improvement (the policy is already greedy with respect to its own values), the policy is optimal. This iteration between evaluation and improvement is the essence of Generalized Policy Iteration (GPI). Value iteration is one instance of GPI.

7.1.5 Symbol Registry

• $V_{\pi }(s)$ — state value function under policy $\pi$ — scalar, expected return from state $s$
• $Q_{\pi }(s,a)$ — action value function under policy $\pi$ — scalar, expected return from $(s,a)$
• $\pi (a\mid s)$ — policy: probability of action $a$ in state $s$ — scalar in $[0,1]$
• $\gamma$ — discount factor — scalar in $[0,1]$
• $G_t$ — return (cumulative discounted reward) — scalar
• $R_t$ — reward at time step $t$ — scalar
• $S_t$ — state at time step $t$ — state variable
• $A_t$ — action at time step $t$ — action variable
• $P(s^{\prime }\mid s,a)$ — transition probability — scalar in $[0,1]$
• $V^{\ast }(s)$ — optimal state value function — scalar

7.2 Model-Based vs Model-Free Approaches

7.2.1 The Model-Based Paradigm and Its Limitations

Everything discussed in the previous lectures — dynamic programming, policy evaluation, policy improvement — relied on having a model of the environment. This is called a model-based approach. The model means we know the transition probabilities $P(s^{\prime }|s,a)$ and rewards $R(s,a,s^{\prime })$ for every state-action pair. With this model, we can compute the optimal policy even without ever interacting with the real environment — we work entirely with the model, which is a simulation of the real world. This is sometimes called planning or offline learning: we learn the policy offline using the model, then deploy it.

The problem is that in many real-world scenarios, we do not have a model. We do not know the transition probabilities or rewards in advance. Consider these examples:

• Autonomous driving. We cannot write down the exact probability distribution of how other cars will react to our actions.
• Game playing. In complex games like Go or chess, writing down all possible transitions is infeasible.
• Robotics. The physics of a robot's interaction with the world is too complex to model exactly.
• Finance. Stock prices and market dynamics are not governed by known equations.

This motivates model-free approaches, where the agent learns directly from experience — from actually interacting with the environment (or from recorded interactions) rather than from a known model.

The core distinction. Both model-based and model-free approaches are value-based methods: they learn value functions and use them to derive policies. The difference is that model-based methods require a model to compute values, while model-free methods estimate values from data alone.

Why model-free matters. For many problems — physical behavior modeling, computational biology, computer graphics, finance, game prediction, weather prediction — exact mathematical models are not available. These are not exhaustive examples; there are many domains where no precise model exists. In practice, data-driven (model-free) approaches are often preferred because they adapt as the environment changes, rather than relying on a fixed model that may become stale.

7.2.2 From Model-Based DP to Data-Driven MC Learning

The transition from model-based DP to data-driven MC learning can be illustrated using the race-car problem under two distinct operational paradigms:

7.3 Monte Carlo Methods: The Core Idea

7.3.1 The Darts Analogy

The professor introduced Monte Carlo methods through a vivid analogy. Imagine you have an 8×8 wall with an irregularly shaped piece of art on it, and you want to estimate the area the art covers. The shape is arbitrary — computing it with formal geometry or numerical methods would be tedious. The Monte Carlo approach is simple: take darts and throw them randomly at the wall. After many throws, count how many landed inside the shape versus outside. If you threw 100 darts and 63 landed inside the shape, the estimated area is:

This is an estimate. If you throw 1000 darts instead of 100, you get more data and a better estimate. As you keep repeating the experiment with more samples, the estimate improves.

This is the heart of Monte Carlo methods: estimation without formal math, entirely driven by data. Instead of knowing the model and computing values analytically, we collect experiences and estimate values from those experiences.

Formal connection. The darts analogy maps directly to RL:

The textbook notes that the term "Monte Carlo" is often used broadly for any estimation method involving a significant random component. In RL, we use it specifically for methods based on averaging complete returns (as opposed to methods that learn from partial returns, which we will cover in the next chapter on temporal difference learning).

7.3.2 Experience Replaces Model

Experience replaces model. Consider the race car problem that was used in earlier lectures. In the dynamic programming solution, we needed to know every transition probability — from "cool," if we take a certain action, what is the probability of reaching "warm"? What reward do we get? With Monte Carlo methods, all of those transition probabilities are immaterial. We do not need the model at all. All we need is experience: records of what actually happened when agents interacted with the environment.

Sources of experience. Experience can come from three places:

1. Actual experience. Real recorded data from actual interactions. For example, recorded trajectories of a defender across 1000 soccer games, or millions of recorded chess games, or driving data from cars with smart features and sensors. The textbook emphasizes that learning from actual experience is "striking because it requires no prior knowledge of the environment's dynamics, yet can still attain optimal behavior."

1. Simulated experience. For problems where real interaction is expensive or dangerous — like an agent that needs to uncover land mines or explore tunnels — we simulate the environment and generate experience from the simulation. The agent learns from simulated data, then we deploy the learned policy in the real environment. The textbook notes that "although a model is required, the model need only generate sample transitions, not the complete probability distributions."

1. Model-generated experience. We may have an imprecise model of the environment. Rather than using dynamic programming with that model, we use it to randomly generate a large number of experiences. The model acts as a planner — it generates an initial policy, and then the agent interacts with the actual environment to refine it.

Real-world: The professor highlighted autonomous driving as a case where experience data is abundant — manufacturers record sensor data from every car with smart features on the road, providing massive datasets for learning driving policies.

The episode assumption. For the Monte Carlo approach covered in this lecture, we assume that experience is collected as episodes. An episode is a complete sequence from a starting state through a series of state-action-reward transitions until a terminal state is reached:

Each episode is one complete experience. Multiple episodes give us a collection of experiences to learn from. The textbook defines MC methods as "only for episodic tasks" — all episodes must eventually terminate, no matter what actions are selected.

The professor acknowledged the question of what to do when we do not have complete episodes, and deferred it to a later module. For now, the assumption is: we have complete episodes, either generated or recorded.

7.4 Monte Carlo Policy Evaluation (First Visit)

The first concrete algorithm is Monte Carlo policy evaluation, also called Monte Carlo prediction. The goal: given a policy $\pi$, estimate the state value function $V_{\pi }(s)$ for every state $s$, using experience collected under that policy. This is the same policy evaluation we did with dynamic programming, except now we do it from data instead of a model.

Setup. A policy $\pi$ is given (for example, from state A, probability of going left is some value, probability of going right is some other value). We want to estimate $V_{\pi }(A)$, $V_{\pi }(B)$, $V_{\pi }(C)$, etc. Initially, all values are set to zero. For each state, we maintain a return list — initially empty — where we will accumulate the returns computed from each episode.

7.4.1 The First-Visit MC Prediction Algorithm

The formal algorithm for First-Visit Monte Carlo Prediction estimates $V\approx v_{\pi }$ by accumulating returns from sampled episodes and updating running averages:

Input: a policy π to be evaluated
Initialize:
  V(s) ∈ ℝ arbitrarily for all s ∈ 𝒮
  Returns(s) ← empty list for all s ∈ 𝒮

Repeat for each episode:
  (a) Generate one complete episode following π: S₀, A₀, R₁, S₁, A₁, R₂, ..., S_{T-1}, A_{T-1}, R_T, S_T
  (b) G ← 0
  (c) Scan the episode backward from t = T-1 down to 0:
        G ← γG + R_{t+1}
        If S_t does not appear earlier in S₀, S₁, ..., S_{t-1}:
          Append G to Returns(S_t)
          V(S_t) ← average(Returns(S_t))

7.4.2 Worked Example: Five-State Grid Prediction

Consider a five-state linear layout with nonterminal states A, B, C, D, E. Moving between adjacent states yields an ordinary step reward of -1. State A exits to the left into a penalty terminal state with reward -10, while state D exits to the right into a goal terminal state with reward +10. We evaluate a fixed policy $\pi$ under undiscounted returns ($\gamma =1.0$).

Observed Episodes & Backward Return Calculations:

Following the First-Visit MC algorithm, each episode is scanned backward from termination ($t=T-1\downarrow 0$) applying $G_t=R_{t+1}+\gamma G_{t+1}$. Only the first occurrence of a state in each episode appends its return to $\text{Returns}(s)$:

Sequential Evolution of Value Estimates $V(s)$:

As each episode finishes, state values are updated by taking the average of all accumulated returns in $\text{Returns}(s)$:

7.4.3 Five-Episode Example with Repeated Visits

Consider an episodic task with nonterminal states A, B, C, D, E, G and terminal state T. State G gives a final transition reward of +10. Other transition rewards are shown below. We use discount factor $\gamma =0.9$. Because states appear multiple times in single episodes, first-visit and every-visit MC yield different estimates.

Observed Episode Trajectories:

• Episode 1: $A\stackrel{-1}{\to }B\stackrel{0}{\to }C\stackrel{-1}{\to }B\stackrel{0}{\to }D\stackrel{2}{\to }C\stackrel{0}{\to }E\stackrel{-1}{\to }D\stackrel{0}{\to }E\stackrel{0}{\to }G\stackrel{10}{\to }T$
  First-visit returns: $G(A)=2.84,G(B)=4.27,G(C)=4.75,G(D)=7.09,G(E)=6.29,G(G)=10.00$
• Episode 2: $A\stackrel{0}{\to }C\stackrel{-1}{\to }B\stackrel{0}{\to }C\stackrel{0}{\to }D\stackrel{2}{\to }E\stackrel{0}{\to }D\stackrel{0}{\to }B\stackrel{-1}{\to }E\stackrel{0}{\to }G\stackrel{10}{\to }T$
  First-visit returns: $G(A)=3.81,G(C)=4.23,G(B)=5.81,G(D)=7.18,G(E)=5.75,G(G)=10.00$
• Episode 3: $B\stackrel{-1}{\to }A\stackrel{0}{\to }B\stackrel{0}{\to }C\stackrel{-1}{\to }D\stackrel{2}{\to }C\stackrel{0}{\to }E\stackrel{0}{\to }D\stackrel{0}{\to }E\stackrel{0}{\to }G\stackrel{10}{\to }T$
  First-visit returns: $G(B)=3.46,G(A)=4.95,G(C)=6.11,G(D)=7.90,G(E)=7.29,G(G)=10.00$
• Episode 4: $C\stackrel{-1}{\to }B\stackrel{0}{\to }C\stackrel{-1}{\to }B\stackrel{0}{\to }A\stackrel{0}{\to }D\stackrel{2}{\to }E\stackrel{0}{\to }D\stackrel{0}{\to }E\stackrel{0}{\to }G\stackrel{10}{\to }T$
  First-visit returns: $G(C)=3.25,G(B)=4.72,G(A)=7.70,G(D)=8.56,G(E)=7.29,G(G)=10.00$
• Episode 5: $A\stackrel{-1}{\to }B\stackrel{0}{\to }D\stackrel{2}{\to }B\stackrel{0}{\to }C\stackrel{-1}{\to }E\stackrel{0}{\to }D\stackrel{0}{\to }E\stackrel{0}{\to }C\stackrel{0}{\to }G\stackrel{10}{\to }T$
  First-visit returns: $G(A)=3.84,G(B)=5.38,G(D)=5.97,G(C)=4.90,G(E)=6.56,G(G)=10.00$

First-Visit MC Running Updates:

Side-by-Side Comparison: First-Visit vs Every-Visit MC:

7.4.4 Student Q&A on Policy Evaluation

7.4.5 Symbol Registry

• $\pi$ — policy being evaluated — function: states $\to$ action probabilities
• $V_{\pi }(s)$ — state value under policy $\pi$ — scalar
• $G$ — return (sum of rewards from first visit) — scalar
• $\gamma$ — discount factor — scalar in $[0,1]$
• $R_t$ — reward at step $t$ — scalar
• $T$ — terminal time step — positive integer
• $Returns(s)$ — list of returns for state $s$ — list of scalars

7.5 Returns: Forward and Backward Computation

Computing returns efficiently is critical for Monte Carlo methods. There are two approaches: forward (naive) and backward (efficient). The textbook strongly recommends the backward method.

7.5.1 Forward Computation

The straightforward way to compute returns is forward: for each state's first occurrence, scan forward through the episode, summing rewards. For a long episode with many states, this means recomputing overlapping sums — the return for state $S_t$ includes all rewards from $t+1$ to $T$, and the return for state $S_{t+1}$ includes all rewards from $t+2$ to $T$. This is redundant.

Example of redundancy. Consider an episode with rewards: $R_1=4,R_2=8,R_3=1$.

• Return from step 0: $G_0=4+8+1=13$
• Return from step 1: $G_1=8+1=9$
• Return from step 2: $G_2=1$

Each return recomputes part of the previous one. The sum $8+1$ appears in both $G_0$ and $G_1$.

7.5.2 Backward Computation (Efficient Method)

The textbook recommends computing returns backward, scanning from the end of the episode to the beginning. This is computationally more efficient — in a single backward scan, you compute the return for every state.

The method works as follows. Consider an episode: state S, action A, reward 4 → state Y, action B, reward 8 → state T, action A, reward 1 → terminal.

We want to compute the return for each of S, Y, and T.

Why this works mathematically. The return from time $t$ is:

We can rewrite this recursively:

The backward scan exploits this recursion. Starting from $G_{T-1}=R_T$ (the last reward), we work backward using the recurrence.

7.5.3 Symbol Registry

• $R$ — running return (accumulated backward) — scalar
• $\gamma$ — discount factor — scalar in $[0,1]$
• $G_t$ — return from time $t$ — scalar
• $T$ — terminal time step — positive integer

7.6 First-Visit vs Every-Visit MC

7.6.1 Definitions and Comparison

There are two variants of Monte Carlo policy evaluation:

Consider an episode where B appears at positions 1 and 3. Under first-visit, we add the return from position 1 (which includes the reward from position 3 and everything after). Under every-visit, we add returns from both position 1 and position 3. The return from position 3 is entirely contained within the return from position 1, so certain portions of the experience are heavily reused.

Convergence properties. Both approaches converge to $V_{\pi }(s)$ as the number of visits (or first visits) to $s$ goes to infinity. The textbook provides formal convergence guarantees:

• First-visit MC. Each return is an independent, identically distributed estimate of $V_{\pi }(s)$ with finite variance. By the law of large numbers, the sequence of averages converges to the expected value. The standard deviation of the error falls as $1/\sqrt{n}$, where $n$ is the number of returns averaged.

• Every-visit MC. Less straightforward because the returns are not independent (they share overlapping subsequences). However, estimates also converge to $V_{\pi }(s)$. The convergence rate is similar but the analysis is more complex (Singh and Sutton, 1996).

The professor noted that if asked to compute every-visit returns on an exam, students should be comfortable doing so. The computation is the same — just don't skip subsequent occurrences of the same state.

7.6.2 Symbol Registry

• $G^{(i)}$ — return from episode $i$ for a given state — scalar
• $N(s)$ — number of times state $s$ has been visited — non-negative integer
• $V(s)$ — estimated value of state $s$ — scalar

7.7 Monte Carlo Control and GPI

We now move from the prediction (evaluation) problem to the control problem. In prediction, a policy is given and we estimate values. In control, we learn the policy itself. We start with a random policy and iteratively improve it by interacting with the environment.

The overall framework follows Generalized Policy Iteration (GPI):

1. Start with an initial policy $\pi$.
2. Generate an episode using $\pi$.
3. Use the episode to compute (or update) $Q_{\pi }(s,a)$ — the action values for all state-action pairs.
4. Use the updated action values to improve the policy (make it greedy with respect to the new Q-values).
5. Use the improved policy to generate a new episode.
6. Repeat.

7.7.1 Worked Example: MC Control with GPI

Consider an environment with states W, X, Y, Z, C where Y, Z, C are terminal states and W, X are non-terminal. Actions are {N, E, S, W} (north, east, south, west). Rewards: from U, exit gives +1; from W, exit gives +10; from Z, exit gives −1.

Initial policy: From W, always go E. From X, always go N. Terminal states have only exit actions.

Episode 1: W → (E, reward 0) → X → (N, reward 0) → Z → (exit, reward −1) → terminal.

With $\gamma =1$, compute action values (state-action returns):

• $Q(Z,\text{exit})=-1$
• $Q(X,N)=0+(-1)=-1$
• $Q(W,E)=0+0+(-1)=-1$

Update policy: From W, E gives −1 while all other actions give 0 (by initialization). So switch W's action from E to W (breaking ties, choosing among the equally-valued 0 actions). From X, N gives −1 while others give 0. Switch X's action from N to E (tie-breaking).

Episode 2: W → (W, reward 0) → U → (exit, reward +1) → terminal.

Compute action values:

• $Q(U,\text{exit})=1$
• $Q(W,W)=0+1=1$

Update policy: From W, the action W now has value 1 (the highest). From X, E still has value −1 and other actions have value 0, so X's policy remains E.

The convergence problem. After this update, the policy says: from W, always go W; from X, always go E. If we generate new episodes using this deterministic policy, the agent from W will always go left to U and exit with +1. It will never go right through X to reach Z (where exit gives −1) or discover other paths. The policy has converged to a local optimum, not the global optimum.

7.7.2 Symbol Registry

• $\pi$ — policy being improved — function: states $\to$ action probabilities
• $Q(s,a)$ — action value function — scalar
• $V(s)$ — state value function — scalar
• $G$ — return — scalar
• $\gamma$ — discount factor — scalar in $[0,1]$
• $A$ — set of actions — set

7.8 Exploration: Epsilon-Soft and Epsilon-Greedy Policies

The fundamental problem identified in the previous section is maintaining exploration. Two solutions are discussed:

Exploring starts. The idea is to ensure that every state-action pair has a non-zero probability of being selected as a starting state. If we can start from any state and take any action, a deterministic policy is fine — we will cover everything through varied starting conditions. However, this assumption is often unrealistic. You would not start a car in 4th gear with the brake pressed. In most problems, the starting state is fixed.

Stochastic policies (the practical solution). Instead of deterministic policies, we use stochastic policies that maintain a non-zero probability for every action from every state. This is the approach used in practice.

7.8.1 Epsilon-Soft Policies

An epsilon-soft policy is one where, from each state, every action has a non-zero probability. Formally, for all states $s$ and all actions $a$:

More precisely, an $ϵ$-soft policy satisfies:

where $|A(s)|$ is the number of actions available in state $s$. This ensures every action has at least a minimum probability of being selected.

No action is completely ruled out. For example, a state with four actions might have probabilities (0.001, 0.0003, 0.4997, 0.499) — as long as none are exactly zero, it is epsilon-soft.

7.8.2 Epsilon-Greedy Policies

An epsilon-greedy policy is a special case of epsilon-soft. It has a parameter $ϵ$ and works as follows:

• The greedy action (the one with the highest estimated value) gets probability $1-ϵ+\frac{ϵ}{|A|}$
• Every non-greedy action gets probability $\frac{ϵ}{|A|}$

where $|A|$ is the total number of actions.

Epsilon-soft vs epsilon-greedy. Every epsilon-greedy policy is epsilon-soft, but not every epsilon-soft policy is epsilon-greedy. Epsilon-greedy is the more structured version: it specifically boosts the greedy action while maintaining a minimum exploration floor for all others.

Initialization vs update. In practice, we initialize with an epsilon-soft policy (random probabilities that are all non-zero) and update using the epsilon-greedy rule. The general GPI framework does not enforce this, but the specific algorithms are explicit: initialize as epsilon-soft, update as epsilon-greedy.

7.8.3 Symbol Registry

• $ϵ$ — exploration parameter — scalar in $(0,1)$
• $\pi (a\mid s)$ — policy probability of action $a$ in state $s$ — scalar in $[0,1]$
• $|A|$ — number of actions — positive integer
• $a^{\ast }$ — greedy action (highest Q-value) — action

7.9 On-Policy First-Visit MC Control (Epsilon-Soft)

This algorithm combines Monte Carlo estimation with GPI to learn an optimal policy from experience. The full name tells you exactly what it does:

• On-policy: the policy used to generate episodes is the same policy being improved (as opposed to off-policy, covered later).
• First-visit: returns are computed based on the first occurrence of each state-action pair in each episode.
• MC control: it learns a policy (not just evaluates one), using Monte Carlo (data-driven) methods.
• Epsilon-soft: the policy maintains non-zero probabilities for all actions throughout.

7.9.1 Algorithm: Initialization

Step 1. Initialize $\pi$ to be an epsilon-soft policy. For each state with $|A|$ actions, assign random probabilities to each action and normalize so they sum to 1. Ensure every action gets non-zero probability. This is straightforward: generate $|A|$ random numbers and normalize.

Step 2. Initialize all action values $Q(s,a)$ arbitrarily for every state-action pair (e.g., all zeros).

Step 3. For each state-action pair \(\,$s,a)$, initialize an empty return list $Returns(s,a)$.

7.9.2 Algorithm: Main Loop

The main loop runs indefinitely (repeat forever):

Step 1 — Generate an episode. Use the current policy $\pi$ to generate a complete episode. This involves real interaction with the environment: for each state, consult $\pi$ to choose an action, execute it, observe the reward and next state, and continue until termination.

Step 2 — Estimate Q-values. For each state-action pair \(\,$s,a)$ appearing in the episode, compute the return $G$ following the first occurrence of \(\,$s,a)$. Append $G$ to $Returns(s,a)$. Update:

Step 3 — Improve the policy (epsilon-greedy update). For each state $s$ appearing in the episode, identify the greedy action — the action $a^{\ast }$ with the highest $Q(s,a)$. Update the policy using the epsilon-greedy rule:

Then return to Step 1 and generate a new episode with the updated policy.

Initialize:
  pi(s) ← epsilon-soft policy, for all s
  Q(s,a) ← arbitrary, for all s,a
  Returns(s,a) ← empty list, for all s,a

Loop forever:
  Generate episode following pi: S0,A0,R1,...,S_{T-1},A_{T-1},R_T
  G ← 0
  Loop for each step t = T-1, T-2, ..., 0:
    G ← gamma * G + R_{t+1}
    Unless (St, At) appears earlier in episode:
      Append G to Returns(St, At)
      Q(St, At) ← average(Returns(St, At))
      A* ← argmax_a Q(St, a)
      For all a in A(St):
        pi(a|St) ← { 1 - eps + eps/|A|  if a = A*
                    { eps/|A|             if a != A*

7.9.3 Example 1: Four-State Line World (On-Policy MC Control)

Consider a line-world environment with nonterminal decision states x, y, state w (which exits to a bad terminal state with reward -100), and state z (which exits to a good terminal state with reward +10). Ordinary moves between x and y receive reward 0. We set discount factor $\gamma =0.9$ and exploration parameter $ϵ=0.2$.

7.9.4 Example 2: Five-State Grid Control Example

Consider again the five-state grid layout. State D exits with reward +10, state A exits with reward -10, and step moves receive reward -1. Actions are $B\stackrel{E}{\to }C$, $E\stackrel{N}{\to }C$, and from C either $E$ toward D or $N$ toward A. We use $\gamma =0.9$ and $ϵ=0.2$.

• Episode 1: $B\stackrel{E,-1}{\to }C\stackrel{E,-1}{\to }D\stackrel{\text{Exit},+10}{\to }T⟹G(C,E)=8,G(B,E)=6.2⟹Q(C,E)=8⟹\pi (E\mid C)=0.9,\pi (N\mid C)=0.1$.
• Episode 2: $E\stackrel{N,-1}{\to }C\stackrel{N,-1}{\to }A\stackrel{\text{Exit},-10}{\to }T⟹G(C,N)=-10,G(E,N)=-10⟹Q(C,E)=8,Q(C,N)=-10⟹\pi (E\mid C)=0.9$.
• Episode 3: $E\stackrel{N,-1}{\to }C\stackrel{E,-1}{\to }D\stackrel{\text{Exit},+10}{\to }T⟹G(C,E)=8,G(E,N)=6.2⟹Q(E,N)=\frac{-10+6.2}{2}=-1.90$.
• Episode 4: $B\stackrel{E,-1}{\to }C\stackrel{E,-1}{\to }D\stackrel{\text{Exit},+10}{\to }T⟹G(C,E)=8,G(B,E)=6.2$.

Action-Value Summary & Policy Implication Table:

7.9.5 Symbol Registry

• $\pi$ — $ϵ$-soft policy — function: states $\to$ action probabilities
• $Q(s,a)$ — action value function — scalar
• $ϵ$ — exploration parameter — scalar in $(0,1)$
• $\gamma$ — discount factor — scalar in $[0,1]$
• $|A|$ — number of actions per state — positive integer
• $a^{\ast }$ — greedy action — action
• $Returns(s,a)$ — list of returns for state-action pair — list of scalars
• $G$ — return — scalar

7.10 On-Policy and Off-Policy Learning

In Monte Carlo control, the policy used to generate data determines what the agent experiences. Sutton and Barto distinguish two primary learning paradigms based on whether the data-generating policy matches the policy being evaluated and improved:

7.11 Review Questions

Below are comprehensive review questions covering conceptual, numerical, and modeling aspects of Monte Carlo methods, complete with step-by-step solutions:

Exam Guidance Summary

• Monte Carlo methods — understand the core idea of estimation from data without a model. Know the area-estimation analogy (darts on a wall).
• Model-based vs model-free — know the difference, when to use each, and why model-free is preferred when models are unavailable. Model-based requires $P(s^{\prime }|s,a)$; model-free learns from experience.
• MC policy evaluation — be able to compute state values from episodes using first-visit returns, with and without discounting. Know the formula: $V(s)=\text{average}(Returns(s))$.
• First-visit vs every-visit — know the difference, why first-visit is preferred, and be able to compute every-visit returns. First-visit uses only the return after the first occurrence; every-visit uses returns after every occurrence.
• Backward computation — understand how to compute returns efficiently by scanning backward through an episode. The update rule $R\leftarrow \gamma R+R_{t+1}$ is the key operation — it appears in every subsequent algorithm.
• MC control with GPI — understand the evaluate-improve cycle. Be able to trace through the algorithm with numerical examples. Action values $Q(s,a)$ are needed (not $V(s)$) because we need to compare actions without a model.
• Epsilon-soft vs epsilon-greedy — know the definitions, the relationship (epsilon-greedy is a special case of epsilon-soft), and how the epsilon-greedy update works. Be able to compute probabilities given $ϵ$ and $|A|$.
• Maintaining exploration — understand why deterministic policies fail (converge to local optima) and how stochastic policies solve this.
• On-policy vs off-policy — know the distinction (same policy for behavior and target vs different policies). This distinction is fundamental and will appear on the exam.
• Expect numerical problems where you trace through episodes, compute returns, update Q-values, and perform epsilon-greedy policy updates.
• The professor emphasized spending time with the textbook algorithm for backward computation, as it appears in all subsequent algorithms.

Key Industry Applications

• Autonomous driving: Manufacturers record sensor data from cars with smart features, providing massive experience datasets for learning driving policies. Model-free methods can learn from this recorded experience without needing to model the complex dynamics of traffic, weather, and human behavior.
• Game playing: Recorded trajectories from thousands of soccer games or chess matches serve as experience for training RL agents (defenders, players). Monte Carlo methods can evaluate strategies by averaging outcomes from recorded games.
• Demining / hazardous exploration: Agents for uncovering land mines or exploring tunnels learn from simulated experience because real interaction is too dangerous. The agent learns a policy in simulation, then deploys it in the real environment.
• Physical behavior, computational biology, computer graphics, finance, business, weather prediction: All cited as domains where exact mathematical models are unavailable, making data-driven (model-free) approaches essential. In these fields, the environment is too complex to model precisely, but experience data is often abundant.