Tags: data-science, reinforcement-learning

Mastering Reinforcement Learning: Monte Carlo Evaluation vs. The Bellman Expectation Equation

If you have ever dipped your toes into the world of Reinforcement Learning (RL), you have likely run into a wall of intense-looking mathematical notation. Words like "bootstrapping," "expectation," and "trajectory" fly around, leaving many beginners wondering how it all fits together.

At the very core of Reinforcement Learning lies the Prediction Problem: If an agent follows a specific strategy (a policy $\pi$), how can we accurately estimate the value of being in any given state?

To solve this, RL relies on two foundational titans: Monte Carlo (MC) Policy Evaluation and the Bellman Expectation Equation.

While one relies on raw, brute-force experience, the other relies on elegant mathematical recursion. In this post, we will tear down the math, look at how they operate, and discover how these two seemingly different concepts are deeply intertwined parts of the same puzzle.

---

1. What is Monte Carlo Policy Evaluation?

Monte Carlo (MC) Policy Evaluation is an experiential, data-driven approach to solving the prediction problem. It answers a simple question: What is the value of a state? Let’s run a bunch of trials, see what rewards we get, and average them out.

The Core Logic: Learning from Complete Trajectories

Monte Carlo methods are model-free, meaning the agent does not need to know the physics or transition probabilities of its environment. It learns purely from trial and error.

To evaluate a policy, the agent starts at an initial state and interacts with the environment until it reaches a terminal (end) state. This complete sequence of states, actions, and rewards is called an episode:

graph LR
    S0[State 0] -->|Action 0| R1(Reward 1)
    R1 --> S1[State 1]
    S1 -->|Action 1| R2(Reward 2)
    R2 --> S2[State 2]
    S2 -->|...| ST[Terminal State]
    
    style ST fill:#f9f,stroke:#333,stroke-width:2px

Once the episode terminates, the algorithm works backward from the end to calculate the total accumulated reward from each time step, known as the Return ($G_t$):

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}$

(Where $\gamma$ is the discount factor between 0 and 1, ensuring the agent values immediate rewards more than distant future rewards).

The Mathematical Rule

According to the Law of Large Numbers, if an agent visits a state $s$ an infinite number of times across many episodes, the average of the observed returns will perfectly converge to the true value $V(s)$:

$V(s) \approx \text{Average}(G_t \text{ for all times where } S_t = s)$

Variations: First-Visit vs. Every-Visit

If an agent loops back and visits the same state multiple times in a single episode, we have two ways to calculate the average:

• First-Visit MC: You only record and average the return ($G_t$) following the very first time the state is hit in that episode.
• Every-Visit MC: You treat every single occurrence of the state in that episode as a separate data point and average all of them.

---

2. What is the Bellman Expectation Equation?

While Monte Carlo forces you to wait until the very end of an episode to learn anything, the Bellman Expectation Equation takes a radically different, recursive approach. Named after Richard Bellman, it allows an agent to calculate a state's value step-by-step without waiting for the episode to finish.

The Core Logic: Value Decomposition

The brilliance of the Bellman Equation lies in breaking down the long-term Return ($G_t$) into two clean components:

1. The immediate reward you get right now ($R_{t+1}$).
2. The discounted value of the next state you land in ($\gamma V(S_{t+1})$).

Mathematically, it looks like this:

$\mathbf{V(s) = \mathbb{E} [R_{t+1} + \gamma V(S_{t+1}) \mid S_t = s]}$

This is known as bootstrapping—estimating a guess based on another guess. If you know the exact probabilities of your environment, you don't need to run simulations; you can turn this equation into a system of linear equations and solve for the value of every state simultaneously.

Deconstructing the Brilliance: How the Bellman Equation Solves the Future

To truly appreciate the genius of Richard Bellman’s formulation, we have to look closely at the mathematical bottleneck it solves.

In Reinforcement Learning, an agent wants to maximize its Return ($G_t$)—the total accumulated, discounted reward from the current time step $t$ until the end of time. The formula for the return looks ahead into an infinite horizon:

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \dots$

If you try to calculate the value of a state $V(s)$ using this raw definition, you run into a massive computational wall: you cannot calculate $G_t$ until you have lived through the entire future. You must trace every step, action, and reward until the episode ends.

Bellman’s brilliant breakthrough was realizing that this infinite sequence wraps neatly inside itself.

---

The Mathematical Magic: Step-by-Step Factoring

Let’s apply a basic algebraic trick to the return equation. If we look at every term after the immediate reward $R_{t+1}$ and factor out a single discount factor ($\gamma$), something amazing happens:

$G_t = R_{t+1} + \gamma \left( R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \dots \right)$

Look closely at the expression inside the parentheses. It is exactly the definition of the return, just shifted one step into the future! It is the return for time step $t+1$:

$G_{t+1} = R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \dots$

By substituting $G_{t+1}$ back into our original equation, we collapse an infinite series of future rewards into a crisp, two-part recursive relationship:

$\mathbf{G_t = R_{t+1} + \gamma G_{t+1}}$

Because the Value Function $V(s)$ is simply the expected value ($\mathbb{E}$) of the return given that you start in state $s$, we can seamlessly swap out the raw returns for values:

$\mathbf{V(s) = \mathbb{E} [R_{t+1} + \gamma V(S_{t+1}) \mid S_t = s]}$

graph LR
    CurrentState((Current State: s)) -->|Step 1: Act| ImmediateReward(Immediate Reward: R_t+1)
    ImmediateReward -->|Step 2: Land| NextState((Next State: S_t+1))
    
    subgraph Lookahead Window
        ImmediateReward
        NextState
    end

    style CurrentState fill:#bbf,stroke:#333,stroke-width:2px
    style NextState fill:#dfd,stroke:#333,stroke-width:2px

This equation is a fundamental shift in perspective. It proves that the value of your current state is equal to the immediate reward you get right now, plus the discounted value of wherever you happen to land next.

---

The Complete Anatomical Anatomy of $V^\pi(s)$

When we expand this expectation out to account for an agent navigating a probabilistic world, the equation opens up into an elegant look-ahead tree.

To calculate the absolute true value of a state, the math must map out two layers of uncertainty:

1. The Agent's Choice: What action will the policy select?
2. The Environment's Physics: Where will the environment throw the agent as a result?

Here is the complete, expanded Bellman Expectation Equation for State-Value:

$V^\pi(s) = \sum_{a \in A} \pi(a \mid s) \sum_{s' \in S} P(s' \mid s, a) \left[ R(s, a, s') + \gamma V^\pi(s') \right]$

To visualize exactly how this equation aggregates information up from the future, let's look at its structural anatomy using a Mermaid look-ahead tree:

graph TD
    %% Define Nodes
    S((Current State: s))
    
    A1(Action: a1)
    A2(Action: a2)
    
    S_next1((Next State: s'))
    S_next2((Next State: s''))
    S_next3((Next State: s'''))

    %% Connect Nodes with Probability Labels
    S -->|Policy: pi a1 given s| A1
    S -->|Policy: pi a2 given s| A2
    
    A1 -->|Physics: P s' given s,a1| S_next1
    A1 -->|Physics: P s'' given s,a1| S_next2
    A2 -->|Physics: P s''' given s,a2| S_next3

    %% Note Labels for Value Injection
    S_next1 -.->|Injects value| V1[Reward + gamma * V s']
    S_next2 -.->|Injects value| V2[Reward + gamma * V s'']
    S_next3 -.->|Injects value| V3[Reward + gamma * V s''']

    %% Styling
    style S fill:#bbf,stroke:#333,stroke-width:2px
    style S_next1 fill:#dfd,stroke:#333
    style S_next2 fill:#dfd,stroke:#333
    style S_next3 fill:#dfd,stroke:#333

Breaking Down Every Term in the Anatomy

• $V^\pi(s)$: The overall value score of your current location.
• $\sum_{a \in A} \pi(a \mid s)$: The Agent Layer. It calculates a weighted average across all possible actions you might take, multiplied by the probability ($\pi$) that your current policy will choose them. $\pi(a \mid s)$ (The Policy's Choice): The policy $\pi$ is the agent's strategy, which outputs the probability of choosing action (a) while standing in state (s). $\sum_{a \in A}$ (The Agent Payout): This sums up the outcomes of all possible choices. Because the policy probabilities add up to 100%, this summation mathematically calculates the weighted average (Expected Value) of your rewards based on how likely you are to pick each action.
• $\sum_{s' \in S} P(s' \mid s, a)$: The Environment Layer. Once an action is committed, the environment calculates a weighted average across all the states ($s'$) you might realistically slip or land into based on transition physics ($P$).
• $R(s, a, s')$: The immediate payout or penalty handed to you the microsecond you transition.
• $\gamma V^\pi(s')$: The cached value score of the next state, discounted by $\gamma$. Because this value already represents the sum of its own future, the math stops here.

Why is this brilliant?

Instead of forcing a computer to remember thousands of steps backwards across history, the Bellman Equation allows an agent to update its knowledge locally, one step at a time. It bridges the present directly to the immediate future, turning an intractable, infinite-horizon timeline into a solvable, step-by-step game of optimization.

• $\pi(a \mid s)$: The probability that your policy chooses a specific action.
• $P(s' \mid s, a)$: The environmental probability that your action actually lands you in a specific next state.
• $R(s, a, s') + \gamma V^\pi(s')$: The immediate reward plus the discounted future value of that next state.

---

3. How Are They Related?

At first glance, they seem like complete opposites: Monte Carlo uses empirical, real-world sampling, while Bellman uses structural, theoretical expectation. Yet, they are mathematically identical in expectation.

Here is exactly how they bridge together:

1. The Expectation Bridge

By definition, the value of a state is the expected value of the return: $V(s) = \mathbb{E}[G_t \mid S_t = s]$.

• Monte Carlo directly samples this expectation by running the code out to infinity and calculating the mean of $G_t$.
• The Bellman Equation mathematically expands that exact same expectation term ($\mathbb{E}$) into a localized, one-step recursive look-ahead.

Monte Carlo is the sample-based realization of what the Bellman Expectation Equation dictates in theory.

2. The Interaction Matrix

We can visualize how these two methods navigate the look-ahead tree of Reinforcement Learning.

• Monte Carlo traces a single, deep, narrow path all the way to the end of the tree.
• Bellman Expectation averages all possible shallow, wide branches exactly one step forward.

graph TD
    subgraph Bellman Expectation - Shallow and Wide
        B_S((s)) --> B_A1(a1)
        B_S --> B_A2(a2)
        B_A1 --> B_S1((s'))
        B_A1 --> B_S2((s''))
    end

    subgraph Monte Carlo - Deep and Narrow
        MC_S((s)) --> MC_A1(a)
        MC_A1 --> MC_S1((s'))
        MC_S1 --> MC_A2(a)
        MC_A2 --> MC_S2((s''))
        MC_S2 --> MC_A3(...)
        MC_A3 --> MC_ST((Terminal))
    end

    style B_S fill:#bbf
    style MC_S fill:#bbf
    style MC_ST fill:#f9f

3. Temporal Difference Learning: The Ultimate Child of Both

The relationship between Monte Carlo and Bellman becomes beautifully explicit when you look at Temporal Difference (TD) Learning (like TD(0)).

TD learning wants the sample-based freedom of Monte Carlo (no model required), but it wants the step-by-step speed of the Bellman Equation (no waiting for the episode to end). It combines them into one update rule:

$V(S_t) \leftarrow V(S_t) + \alpha \underbrace{[ \overbrace{R_{t+1} + \gamma V(S_{t+1})}^{\text{Bellman Target}} - V(S_t) ]}_{\text{TD Error (Sampled like MC)}}$

---

Summary Side-by-Side Comparison

Feature	Monte Carlo Policy Evaluation	Bellman Expectation Equation
Operational Strategy	Sampling. Runs full episodes to gather actual data points.	Analytical. Uses mathematical recursion to evaluate states.
Bootstrapping	No. Values are updated using true, terminal rewards.	Yes. Updates state values based on estimated values of next states.
Environmental Knowledge	Model-Free. Requires no prior knowledge of probabilities.	Model-Based. Requires transition probabilities ($P$) and rewards ($R$).
Variance vs. Bias	High Variance, Zero Bias. Every episode is wildly different, but accurate.	Low Variance, High Bias. Stable to calculate, but errors compound early on.
Execution Constraint	Can only be used on Episodic tasks that eventually end.	Can be used on Continuous tasks that run forever.

Conclusion

Monte Carlo Evaluation and the Bellman Expectation Equation are two sides of the same coin. Monte Carlo is what happens when you roll up your sleeves, jump into the environment, and measure what actually happens over time. The Bellman Expectation Equation is the underlying rules of the universe that dictate what those averages should ideally converge to.

By mastering both, you gain a complete spatial understanding of how an AI calculates value—setting you up perfectly to conquer advanced control algorithms like Q-Learning and Policy Gradients!