Monte Carlo Methods: On-Policy Prediction and Control

8.1 Monte Carlo Fundamentals and Exploration

8.1.1 Model-Free Approach

Monte Carlo (MC) methods represent a fundamental shift from model-based to model-free reinforcement learning. In model-based approaches (like the dynamic programming methods we saw in earlier lectures), we need to know the environment's dynamics — the transition probabilities $p(s^{\prime }|s,a)$ (what happens if I take action $a$ in state $s$) and reward probabilities $p(r|s,a)$ (what rewards I get for each outcome). MC methods eliminate this requirement entirely.

The key insight: instead of needing a perfect model of the environment, we let an agent actually interact with the environment, collect real experience, and learn from that experience directly. All we need is the ability to simulate or play out episodes — actual interactions with the world.

Why this matters practically. Many real-world problems have dynamics that are too complex to write down explicitly. Consider blackjack: computing the exact probability of winning when your hand totals 14 and the dealer shows a 6 requires tracking all possible card sequences — tedious and error-prone. But simulating a thousand blackjack games is easy. MC methods exploit this asymmetry: generating sample experience is often far simpler than constructing an explicit probabilistic model.

Contrast with dynamic programming:

The textbook (Sutton & Barto) emphasizes a third advantage: even when a model is available, MC can be more efficient when you only need values for a small subset of states. You generate episodes starting from those states and ignore the rest — DP cannot do this because it must sweep through the entire state space.

8.1.2 Trajectories and Episodes

Data in MC methods comes in the form of trajectories. A trajectory is a sequence of states, actions, and rewards generated through actual interaction:

where $T$ is the terminal time step. Each element has a precise role:

- $S_t$ — the state at time step $t$, drawn from state space $\mathcal{S}$

- $A_t$ — the action taken at time step $t$, chosen by policy $\pi$ from action space $\mathcal{A}$

- $R_{t+1}$ — the reward received after taking action $A_t$ in state $S_t$, a scalar signal from the environment

The complete trajectory from start to terminal state is called an episode. An episode is one full play-through of the game or one complete interaction sequence. MC methods are defined only for episodic tasks — tasks where every episode is guaranteed to terminate eventually, no matter what actions are selected. We collect many such episodes and use the entire set as the basis for learning.

Key properties of episodes:

1. Finite length. Every episode ends. There are no infinite trajectories. This is what makes returns (cumulative rewards) well-defined — they are finite sums.

2. Independence. Each episode starts fresh from some initial state. The outcome of one episode does not affect the starting conditions of the next (though the policy we derive from past episodes will influence future episodes).

3. No step-by-step updates. Unlike temporal-difference methods (covered later), MC methods wait until an episode is complete before updating value estimates. They are "episode-by-episode" learners, not "step-by-step" learners.

There is no perfect model that exists on paper — you must actually start from a starting state, interact with the world, play the game until completion, store the trajectory, and that constitutes an episode.

8.1.3 The Exploration Problem

A critical challenge with MC methods is exploration. Since we learn from actual episodes, there's no guarantee that all states are visited, or that from each state all possible actions are tried, or that all possible outcomes from each state-action pair are observed. This is not just a theoretical concern — it is the primary obstacle in designing practical MC algorithms.

The core issue is circular: to find the best action in each state, we need to try all actions and observe their returns. But if our current policy already favors one action, we never collect returns for the alternatives. Without returns for alternatives, we cannot improve the policy. The agent gets stuck.

Three key approaches to ensuring exploration:

1. Exploring starts — Assume that every state-action pair has a non-zero probability of being the starting point of an episode. In simulated environments (like blackjack), this is easy to arrange: just pick any starting state and action at random. In real-world environments, it is unrealistic — you cannot teleport an agent to arbitrary states.

2. Epsilon-soft policies — The policy must never completely rule out any action. Formally, $\pi (a|s)\ge \frac{ϵ}{|A(s)|}$ for all states $s$ and actions $a$, for some $ϵ>0$. This ensures that if we generate episodes infinitely, we will eventually visit all state-action combinations. This is the approach used in the epsilon-greedy algorithm (Section 8.3).

3. The "repeat forever" structure — MC algorithms have a characteristic loop structure: "repeat forever." This means the algorithm never formally terminates. In practice, you can stop after any number of episodes (say 20 or 300) and use the current estimates to derive a policy. The algorithm doesn't force you to wait for convergence — you extract the best policy available at any point.

8.2 Monte Carlo Prediction (Policy Evaluation)

8.2.1 Computing Returns from Episodes

The prediction problem in MC is: given a fixed policy $\pi$, estimate the value function $V_{\pi }(s)$ or the action-value function $Q_{\pi }(s,a)$ for all states or state-action pairs. Recall from earlier lectures that $V_{\pi }(s)$ is the expected return starting from state $s$ and following policy $\pi$ thereafter. MC methods estimate this by simply averaging the returns observed after visits to $s$.

Symbol registry — Monte Carlo Returns:

- $S_t$ — state at time step $t$ — state in state space $\mathcal{S}$

- $A_t$ — action taken at time step $t$ — action in action space $\mathcal{A}$

- $R_{t+1}$ — reward received after taking action $A_t$ in state $S_t$ — scalar

- $\gamma$ — discount factor — scalar in $[0,1]$

- $G_t$ — return from time step $t$ — cumulative discounted reward, scalar

- $V_{\pi }(s)$ — value of state $s$ under policy $\pi$ — expected return, scalar

- $Q_{\pi }(s,a)$ — action-value of state-action pair $(s,a)$ under policy $\pi$ — expected return, scalar

To estimate state values, we first need to compute returns from episodes. The return $G_t$ from time step $t$ is the cumulative discounted reward — the sum of every reward received from step $t$ onward, with each future reward discounted by a power of $\gamma$. The professor describes it as: "the sum of every reward that you actually get after that, with gamma raised to successive powers."

where $T$ is the terminal time step of the episode. Written compactly:

Why discount? The discount factor $\gamma \in [0,1]$ controls how much the agent cares about future rewards versus immediate ones. When $\gamma =1$, all rewards are weighted equally (undiscounted). When $\gamma <1$, rewards further in the future are worth less. The return satisfies a useful recursive relationship:

This recursion is the backbone of backward computation in MC — once you know $G_{t+1}$, you can compute $G_t$ in one step.

8.2.2 Computing Q(S, A) from Episodes

The same algorithm works for estimating $Q_{\pi }(s,a)$ — instead of tracking returns per state, we track returns per state-action pair. A state-action pair $(s,a)$ is said to be visited in an episode if ever state $s$ is visited and action $a$ is taken there.

Why Q-values sidestep the model requirement. This point deserves emphasis. In DP methods, the greedy policy is $\pi (s)=\arg {\max }_a{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V(s^{\prime })]$ — you need the transition model. In MC, the greedy policy is simply $\pi (s)=\arg {\max }_{a}Q(s,a)$ — no model needed. This is why MC methods estimate $Q$ rather than $V$.

8.2.3 First-Visit vs Every-Visit MC

Two variants exist for how to handle multiple visits to the same state within one episode:

Which is better? Both converge to the true value as the number of episodes grows. First-visit MC has been most widely studied and is the focus of this course. Its key advantage: each return is truly i.i.d., so the convergence analysis is straightforward (law of large numbers). Every-visit MC is slightly biased for finite samples, but the bias vanishes asymptotically (Singh and Sutton, 1996). Every-visit MC extends more naturally to function approximation and eligibility traces (Chapters 9 and 12 of Sutton & Barto).

The algorithm for first-visit MC prediction:

1. Initialize $V(s)$ arbitrarily for all $s\in \mathcal{S}$; initialize Returns$(s)$ as an empty list for each state.

2. Repeat forever:

- Generate an episode following $\pi$: $S_0,A_0,R_1,S_1,A_1,R_2,\dots ,S_{T-1},A_{T-1},R_T$

- Set $G\leftarrow 0$

- Loop for each step $t=T-1,T-2,\dots ,0$:

- $G\leftarrow \gamma G+R_{t+1}$ (use the recursive return formula)

- Unless $S_t$ appears earlier in the episode (i.e., in $S_0,\dots ,S_{t-1}$):

- Append $G$ to Returns$(S_t$)

- $V(S_t)\leftarrow$ average(Returns$(S_t$))

8.3 Epsilon-Greedy Policies

8.3.1 Definition and Computation

Once we have estimated $Q$ values, we need to derive a policy from them. The epsilon-greedy policy is the standard approach. The professor describes it as: "the greedy action gets one minus epsilon, and everybody gets an equal share of epsilon."

Symbol registry — Epsilon-Greedy Policy:

- $ϵ$ — exploration parameter — scalar in $(0,1)$

- $\pi (a|s)$ — probability of taking action $a$ in state $s$ under policy $\pi$ — scalar in $[0,1]$

- $|A(s)|$ — number of available actions in state $s$ — positive integer

- $\arg {\max }_{a}Q(s,a)$ — the greedy action (highest Q-value) in state $s$ — action

Why the formula works. The total probability must sum to 1 over all actions. The greedy action gets the lion's share: $1-ϵ$ (the "trust" portion) plus its equal share of the exploration budget $\frac{ϵ}{|A(s)|}$. Every other action gets only its equal share of $ϵ$.

Connection to epsilon-soft policies. An epsilon-soft policy is any policy where $\pi (a|s)\ge \frac{ϵ}{|A(s)|}$ for all states and actions. The epsilon-greedy policy is a special case — it is the epsilon-soft policy closest to greedy. Among all epsilon-soft policies, epsilon-greedy puts the maximum possible probability on the best action while still satisfying the exploration constraint. This makes it the natural choice for on-policy MC control.

8.3.2 Worked Example: Epsilon-Greedy Computation

Effect of $ϵ$ on exploration:

8.4 On-Policy Monte Carlo Control

8.4.1 The Epsilon-Greedy MC Control Algorithm

The control problem goes beyond prediction: starting from a random policy, find the optimal policy through interaction with the environment. This is the goal of Generalized Policy Iteration (GPI) introduced in the DP chapter: maintain both an approximate policy and an approximate value function, and alternate between improving each.

Inputs & Outputs:

- Inputs: A way to generate episodes (an environment or simulator), a discount factor $\gamma$, an exploration parameter $ϵ$

- Outputs: An approximately optimal epsilon-soft policy $\pi$ and its action-value function $Q(s,a)$

Initialization:

- Initialize $\pi$ to an arbitrary epsilon-soft policy — a policy where all actions have non-zero probability

- Initialize $Q(s,a)$ arbitrarily (typically 0) for all state-action pairs

- Initialize Returns list as empty for each state-action pair

Repeat forever (for each episode):
1. GENERATE: Use current policy π to generate a complete episode:
   S_0, A_0, R_1, S_1, A_1, R_2, ..., S_{T-1}, A_{T-1}, R_T
2. EVALUATE: For each first-visited (S_t, A_t) in the episode:
   - Compute return G_t (working backward: G ← γ * G + R_{t+1})
   - Append G_t to Returns(S_t, A_t)
   - Q(S_t, A_t) ← average(Returns(S_t, A_t))
3. IMPROVE: For each state S_t visited in the episode:
   - A* ← argmax_a Q(S_t, a)
   - For all a ∈ A(S_t):
     π(a|S_t) ← 1 - ε + ε/|A(S_t)|  if a = A*
     π(a|S_t) ← ε/|A(S_t)|            otherwise

The policy improvement theorem guarantees progress. For any epsilon-soft policy $\pi$, any epsilon-greedy policy ${\pi }^{\prime }$ with respect to $Q_{\pi }$ satisfies $v_{{\pi }^{\prime }}(s)\ge v_{\pi }(s)$ for all states $s$. This is proven in Sutton & Barto (Section 5.4): the epsilon-greedy policy concentrates as much probability as allowed on the best action, which yields a higher or equal expected value. Equality holds only when $\pi$ is already optimal among epsilon-soft policies.

8.4.2 Worked Example: Five-State Grid World

8.4.3 Worked Example: Textbook Grid World (W, X, Y, Z)

8.5 Why "On-Policy" and Policy Update Dynamics

8.5.1 Same Policy for Behavior and Target

The term "on-policy" refers to a specific property of the algorithm: the same policy $\pi$ is used for both generating behavior AND as the target of learning.

In the MC control algorithm:

- Behavior role: Use policy $\pi$ to generate episodes — the agent acts in the world according to $\pi$

- Target role: Compute value estimates for $\pi$ — these estimates answer "how good is it to follow $\pi$?"

- Improvement: Update the same $\pi$ based on those estimates — make it epsilon-greedy wrt the new Q-values

The policy that generates experience is identical to the policy being improved. This creates a tight coupling: the agent explores using its current knowledge and immediately updates that same knowledge.

8.5.2 The Iterative Nature of Policy Updates

The key insight: the policy update doesn't act alone. With each episode, the environment's feedback is the dominant factor. If your preferred action consistently yields lower returns than an alternative, the evidence accumulates through averaging, and the policy update naturally corrects toward the better action.

8.5.3 Softmax vs Epsilon-Greedy

The professor makes a key distinction here — between learning the environment and learning to behave optimally:

Convergence direction comparison:

The professor's key insight: There is a difference between learning how the environment works (model learning) and learning how to behave optimally (policy learning). For model learning, you might want a stochastic policy to explore all outcomes. For policy learning — which is what MC control does — if one action gives an edge, go there. That is the optimal behavior.

8.5.4 RL vs Supervised Learning Approach

The fundamental loop that distinguishes RL from supervised learning:

This feedback loop has two critical consequences:

1. Non-stationarity. The world evolves. A policy learned from historical data may become outdated. Being able to incrementally improve behavior as the world changes is a key RL capability. Supervised learning assumes the data distribution is fixed; RL does not.

2. Targeted learning. The experiences most useful for learning are those generated by the current policy. If you are trying to learn whether turning left or right at an intersection is better, random wandering through the entire city wastes samples on irrelevant parts of the state space. RL focuses exploration on the states and actions that matter for the current policy.

8.6 On-Policy vs Off-Policy: Introduction

8.6.1 Behavior Policy vs Target Policy

The defining feature of on-policy methods is that the same policy generates behavior and is the learning target. Off-policy methods decouple these two roles.

Side-by-side comparison:

8.6.2 Why Decouple Behavior and Target?

The decoupling of behavior and target policies offers several advantages:

- Use prior knowledge. The behavior policy can be a teacher or expert whose experience provides useful learning signals. The learner doesn't have to rediscover everything from scratch.

- Learn beyond the teacher. The target policy can potentially learn better behavior than the behavior policy. A student may surpass the teacher.

- Reuse data. Historical data or expert demonstrations can serve as the behavior policy while learning a new target policy. You can learn from logged data without ever interacting with the environment yourself.

8.6.3 Off-Policy Challenges

In off-policy learning, the distribution of experience generated by the behavior policy may differ from the distribution expected by the target policy. This creates a distribution mismatch: the data you have is not the data you want.

To correct for this mismatch, off-policy methods use importance sampling — weighting returns by the ratio of the probabilities of taking the observed actions under the two policies. This ratio $\rho ={\prod }_t\frac{\pi (A_t|S_t)}{\mu (A_t|S_t)}$ transforms returns from the behavior policy's distribution to the target policy's distribution.

Why this makes off-policy harder:

1. High variance. The importance sampling ratio can be very large (when the two policies disagree) or very small, leading to high-variance estimates. In extreme cases, the variance can be infinite.

2. Coverage requirement. The behavior policy must assign non-zero probability to every action the target policy might take. If $\pi (a|s)>0$ implies $\mu (a|s)>0$. This limits the choice of behavior policy.

3. Slower convergence. Due to higher variance, off-policy methods typically need more episodes to converge than on-policy methods.

8.7 Exam Guidance Summary

8.7.1 Syllabus Coverage

The exam covers four modules: RL Fundamentals (Chapter 1), Multi-Armed Bandits (Chapter 2), MDP (Chapters 3-4), and Monte Carlo (Chapter 5, on-policy only). Below is the professor's detailed guidance on what to study for each.

8.7.2 Chapter 1: RL Fundamentals

- Understand what RL is and identify whether a given scenario is RL or not

- Tic-tac-toe problem: understand value updates (how the value of each board position changes with experience)

- Distinguish RL from supervised learning for given scenarios — the key differentiator is the feedback loop: the agent's behavior affects future training data

- Discuss stationary vs non-stationary environments — stationary means the reward and transition distributions do not change over time

- Early history of RL is not on the exam but worth reading for background

8.7.3 Module 2: Multi-Armed Bandits

- Model a given scenario as a MAB problem: identify arms, rewards, and verify the modeling is correct

- Action value computations: incremental updates, tracking non-stationarity

- Understand $\alpha =1/n$ vs constant $\alpha$ — the step-size parameter controls how much weight you give to new rewards vs old ones

- Optimistic initial values: know why it's a hack (encourages exploration early on), why it's not a general technique (fails in non-stationary settings), when it works (short, stationary problems) and when it fails

- Solve numerical problems using MAB

- UCB (Upper Confidence Bound): If given a scenario, be able to solve it using UCB. Working knowledge of UCB is valuable beyond the exam

- Gradient bandit: not currently covered, will be discussed later

- Contextual bandits: model verification, understand the difference between classic MAB, contextual bandit, and full RL. If given a scenario, tag it correctly as MAB, contextual bandit, or full RL

8.7.4 Module 3: MDP

- Model any full RL scenario as an MDP — identify all MDP elements (states, actions, transitions, rewards, discount factor)

- Goals, rewards, returns, episodes: observe these concepts carefully

- Bellman equations: Two versions — expected update and optimal update. Understand the difference between them. The expected Bellman equation averages over actions according to the policy; the optimal Bellman equation takes the max over actions.

- Write custom Bellman equations for specific scenarios (not just copy the generic form)

- Model dynamics: role in Bellman updates when outcomes and rewards are stochastic

- Policy evaluation and prediction: very important

- Value iteration: More important than policy iteration for exams. Understand both in-place and not-in-place updates.

- Key terminology note: Exam papers may use "asynchronous dynamic programming" when they actually mean "in-place update." Navigate this carefully.

8.7.5 Module 4: Monte Carlo

- Monte Carlo prediction: estimate $V_{\pi }(s)$ and $Q_{\pi }(s,a)$ — know the worked examples (computing returns from episodes, averaging across episodes)

- Monte Carlo control: the full epsilon-greedy MC control algorithm — be able to trace through multiple episodes by hand, computing returns backward, updating Q-values, and updating the policy

- Without exploring starts: use epsilon-soft policies instead of random starting states

- Each update makes an epsilon-greedy update

8.7.6 General Exam Advice

- Focus on understanding, not sample question papers — understand why each algorithm works, not just the mechanics

- Show work in tables for numerical problems — it is easier to grade and helps you avoid arithmetic errors

- Post doubts on TEAMS — responses within 24 hours

- Show partial work when asking for help, not just the problem

- Plan study time well; don't leave everything to the last minute

- Take care of health during exam preparation

8.8 Key Industry Applications

8.8.1 Game Playing and Robotics

MC methods apply to any domain where you can simulate or play out episodes — game playing (chess, Go, Atari), robotics (trial-and-error learning), traffic signal optimization, medical treatment planning, and recommendation systems.

The key requirement is episodic interaction: the problem must be decomposable into complete episodes that start and end. This makes MC natural for:

- Game playing. Each game is an episode. AlphaGo's early training used MC tree search — simulating many complete games from the current board position to estimate the value of each move.

- Robotics. Each trial (pick up object, walk across room, balance a pole) is an episode. The robot learns from repeated attempts, improving after each one.

- Medical treatment planning. A treatment course from diagnosis to outcome is an episode. MC methods can evaluate treatment policies from historical patient data.

8.8.2 Adaptive Systems

The concept of learning from interaction (rather than from a pre-existing dataset) is fundamental to applications where the environment changes over time — stock trading, adaptive systems, personalized recommendations.

In these domains, the agent cannot rely on a fixed model of the environment. Stock market dynamics shift, user preferences evolve, and traffic patterns change. MC methods adapt naturally because they learn from the most recent episodes, automatically incorporating new patterns.

8.8.3 UCB in Industry

UCB (Upper Confidence Bound) — from the MAB module — is widely used in A/B testing, clinical trials, ad placement, and any scenario requiring exploration-exploitation trade-offs. It is one of the most practically deployed RL techniques in industry.

- A/B testing. Instead of a fixed split (50/50), UCB dynamically allocates more traffic to the better-performing variant while still exploring the alternative.

- Clinical trials. UCB-based adaptive trial designs assign more patients to treatments that appear effective, reducing the number of patients receiving inferior treatments.

- Ad placement. UCB selects which ad to show by balancing the ad with the highest known click-through rate (exploitation) against ads with uncertain performance (exploration).

8.8.4 Imitation and Transfer Learning

The off-policy concept (learning from a teacher, then surpassing them) maps to imitation learning, apprenticeship learning, and transfer learning in industry AI systems.

- Imitation learning. A human expert demonstrates a task (behavior policy). The agent learns a policy from these demonstrations and can potentially improve upon them.

- Transfer learning. Knowledge from one task (source domain) is transferred to a new task (target domain). The source task's policy serves as the behavior policy; the target task's policy is what we learn.

- Robot learning from demonstration. A robot watches a human perform a task and learns a policy that replicates and eventually refines the demonstrated behavior.