Derivation of Bellman Equation for State-Value Function

Understanding the Bellman Equation for the State‑Value Function

In reinforcement learning (RL), the Bellman equation is the cornerstone that links immediate rewards to future expectations. This course unpacks the derivation of the Bellman equation for the state‑value function v_π(s), using the concepts tested in a typical quiz. By the end, you will be able to explain each step, recognize the underlying mathematical tools, and see how the four fundamental ingredients come together.

1. Return Decomposition: From Gₜ to Immediate Reward

The return Gₜ is the total discounted reward obtained from time step t onward:

• Gₜ = Rₜ₊₁ + γRₜ₊₂ + γ²Rₜ₊₃ + …

By separating the first reward from the rest, we obtain the key identity:

Gₜ = Rₜ₊₁ + γGₜ₊₁

This identity is the answer to the first quiz question and serves as the starting point for the Bellman derivation. It tells us that the return at time t equals the immediate reward plus the discounted return from the next time step.

2. Applying Linearity of Conditional Expectation

We want the expected return under a policy π given that the current state is s:

v_π(s) = E_π[Gₜ | Sₜ = s]

Using the return decomposition, substitute Gₜ = Rₜ₊₁ + γGₜ₊₁:

v_π(s) = E_π[Rₜ₊₁ + γGₜ₊₁ | Sₜ = s]

Because expectation is linear, the discount factor γ multiplies the second term only:

E_π[Gₜ₊₁ | Sₜ = s] is multiplied by γ. This matches the second quiz answer.

3. Law of Total Expectation (Conditional) – Introducing the Action

To break the expectation into more manageable pieces, we condition on the action taken at state s. The law of total expectation (also called the tower rule) states:

E_π[X | Sₜ = s] = Σₐ π(a|s) E_π[X | Sₜ = s, Aₜ = a]

Applying this to Gₜ₊₁ gives the third quiz answer: the theorem that justifies the step is the law of total expectation (conditional). This step introduces the policy’s action probabilities.

4. Conditioning on the Next State and Reward

Next, we condition on the concrete outcome of the environment: the next state s′ and the reward r. Using the definition of the state‑value function for the next state, we replace the expected future return:

E_π[Gₜ₊₁ | Sₜ₊₁ = s′] = v_π(s′)

Thus the expression inside the expectation becomes:

r + γ v_π(s′)

This is the answer to the fourth quiz question. It shows that once we know the next state, the remaining return is simply the discounted value of that state.

5. The Four Fundamental Ingredients

The derivation relies on four core concepts:

• Return decomposition – splitting Gₜ into immediate reward and future return.
• Linearity of expectation – allowing γ to factor out.
• Law of total expectation (conditional) – introducing the action distribution π(a|s).
• Markov property – ensuring that future returns depend only on the next state, not on the full history.

These ingredients correspond to the fifth quiz answer and form the logical scaffolding for the Bellman equation.

6. Compact Form of the Bellman Equation

Putting everything together, we obtain the compact, recursive relationship:

v_π(s) = E_π[Rₜ₊₁ + γ v_π(Sₜ₊₁) | Sₜ = s]

In this expression, the term γ v_π(Sₜ₊₁) represents the discounted expected value of the next state. This is the answer to the sixth quiz question. It captures the idea that future rewards are worth less than immediate ones, and that we evaluate them through the value function of the next state.

7. Substituting the Definition of vπ(s′)

The step that explicitly uses the definition v_π(s′) = E_π[Gₜ₊₁ | Sₜ₊₁ = s′] is the replacement of the expectation with the value function. This substitution is highlighted in the seventh quiz answer: we replace E_π[Gₜ₊₁ | Sₜ₊₁ = s′] with v_π(s′). It turns a generic expectation into a concrete function that we can compute or approximate.

8. Role of the Transition‑Reward Kernel p(s′, r | s, a)

To move from the expectation notation to an explicit summation (or integral) over possible outcomes, we introduce the kernel:

p(s′, r | s, a) – the joint probability of receiving reward r and transitioning to state s′ when action a is taken in state s.

This kernel encodes the environment dynamics and is the answer to the eighth quiz question. It does **not** represent the policy; instead, it captures how the world responds to actions, allowing us to write the Bellman equation in a fully expanded form:

vπ(s) = Σₐ π(a|s) Σ_{s′,r} p(s′, r | s, a) [ r + γ vπ(s′) ]

Here, the outer sum averages over actions according to the policy, while the inner sum averages over all possible next‑state and reward pairs according to the kernel.

9. Full Derivation Recap

1. Start with the definition v_π(s) = E_π[Gₜ | Sₜ = s].
2. Decompose the return: Gₜ = Rₜ₊₁ + γGₜ₊₁.
3. Apply linearity: v_π(s) = E_π[Rₜ₊₁ | Sₜ = s] + γ E_π[Gₜ₊₁ | Sₜ = s].
4. Use the law of total expectation to condition on the action: Σₐ π(a|s) E_π[· | Sₜ = s, Aₜ = a].
5. Condition further on the next state and reward using the kernel p(s′, r | s, a).
6. Replace the future return with the value function: E_π[Gₜ₊₁ | Sₜ₊₁ = s′] = v_π(s′).
7. Collect terms to obtain the compact Bellman equation.

This logical flow demonstrates how each ingredient contributes to the final recursive relationship.

10. Why the Bellman Equation Matters

Understanding the Bellman equation is essential for several reasons:

• Dynamic programming: Algorithms like policy iteration and value iteration solve the Bellman equations directly.
• Temporal‑difference learning: Methods such as TD(0) and Q‑learning approximate the Bellman update using sampled transitions.
• Function approximation: When the state space is large, we approximate v_π(s) with neural networks, still guided by the Bellman residual.

All these techniques rely on the same underlying identity derived above.

11. Frequently Asked Questions (FAQ)

What does the discount factor γ represent?

γ ∈ [0,1] determines how future rewards are weighted relative to immediate rewards. A γ close to 1 values long‑term outcomes, while a smaller γ emphasizes short‑term gains.

Can the Bellman equation be used for action‑value functions?

Yes. The analogous equation for the action‑value function q_π(s,a) is:
q_π(s,a) = Σ_{s′,r} p(s′, r | s, a) [ r + γ Σ_{a′} π(a′|s′) q_π(s′,a′) ].

Is the kernel p(s′, r | s, a) always known?

In model‑based RL, we assume access to this kernel. In model‑free settings, we estimate it implicitly via sampled transitions.

12. Summary

The Bellman equation for the state‑value function emerges from a systematic decomposition of the return, the application of linearity and total expectation, and the exploitation of the Markov property. The transition‑reward kernel bridges the probabilistic dynamics of the environment with the policy’s action choices. Mastering each step equips you to understand and implement core RL algorithms, from classic dynamic programming to modern deep reinforcement learning.