Derivation of the Bellman Equation for qπ

Understanding the Bellman Equation for q_π

In reinforcement learning, the Bellman equation provides a recursive relationship that connects the value of a state‑action pair to the values of subsequent state‑action pairs. This course unpacks the derivation of the Bellman equation for the action‑value function q_π(s,a), highlighting key concepts such as returns, conditional expectations, the Markov property, and the role of the discount factor.

1. The Return G_t and Its Recursive Definition

The return G_t represents the total discounted reward accumulated from time step t onward:

• Recursive relationship: G_t = R_t+1 + γ·G_t+1

This equation states that the return at time t consists of the immediate reward R_t+1 plus the discounted return from the next time step. The discount factor γ (0 ≤ γ ≤ 1) ensures that future rewards contribute less than immediate rewards, which is essential for convergence in infinite‑horizon problems.

2. From Return to Action‑Value Function q_π(s,a)

By definition, the action‑value function under policy π is the expected return when starting from state s, taking action a, and thereafter following π:

q_π(s,a) = 𝔼_π[ G_t \mid s_t = s, a_t = a ]

Substituting the recursive definition of G_t yields:

q_π(s,a) = 𝔼_π[ R_{t+1} + γ·G_{t+1} \mid s,a ]

Applying the linearity of conditional expectation separates the terms:

• q_π(s,a) = 𝔼_π[ R_{t+1} \mid s,a ] + γ·𝔼_π[ G_{t+1} \mid s,a ]

This step is crucial because it isolates the immediate reward from the future return, allowing us to treat each component independently.

3. Leveraging the Markov Property

The Markov property of a Markov Decision Process (MDP) states that the future is independent of the past given the present state‑action pair. Consequently, the expected return from the next step depends only on the next state s′ and the next action a′:

• 𝔼_π[ G_{t+1} \mid s,a, s′,a′ ] = q_π(s′,a′)

This substitution replaces the expectation of the future return with the action‑value function evaluated at the subsequent state‑action pair, simplifying the recursion.

4. Transition Probabilities Under a Stationary Policy

When the policy π is stationary (i.e., it does not change over time), the joint transition probability of moving from (s,a) to (s′,a′) factorizes as:

P_π(s′,a′ \mid s,a) = p(s′ \mid s,a)·π(a′ \mid s′)

First, the environment determines the next state s′ via the dynamics p(s′|s,a). Then, the policy selects the next action a′ based only on the new state, reflecting the intuition of arriving at a new city before choosing the next route.

5. Compact Bellman Equation for q_π(s,a)

Combining the pieces above, we arrive at the compact Bellman equation that expresses q_π(s,a) in terms of immediate rewards and the state‑value function v_π(s′):

q_π(s,a) = \sum_{s′,r}\, p(s′,r \mid s,a)\,\big[ r + γ·v_π(s′) \big]

Here, p(s′,r|s,a) is the joint distribution over next state and reward, and v_π(s′) = \sum_{a′} π(a′|s′) q_π(s′,a′) is the expected value of state s′ under policy π.

6. Applying the Law of Total Expectation

To compute 𝔼_π[ G_{t+1} \mid s,a ], we introduce the random variables for the next state and action:

• St+1 (the next state) and At+1 (the next action)

Using the law of total expectation, the inner expectation conditions on these variables, allowing us to replace the future return with q_π(s′,a′) as described earlier.

7. Why Sum Over s′ and r?

The expectation of the immediate reward given (s,a) is expressed as a sum over possible next states and rewards because the reward may depend on the resulting state. The joint distribution p(s′,r|s,a) captures both the probability of transitioning to a particular state and the associated reward, ensuring that all possible outcomes are accounted for.

8. The Role of the Discount Factor γ

In the Bellman equation, γ serves to weight the contribution of future q‑values relative to the immediate reward. A larger γ (close to 1) places more emphasis on long‑term returns, while a smaller γ (close to 0) makes the agent short‑sighted, focusing primarily on immediate rewards.

9. Summary of Key Steps

• Define the return G_t recursively.
• Express q_π(s,a) as the expectation of the return.
• Apply linearity of expectation to separate immediate reward and future return.
• Use the Markov property to replace the future return with q_π(s′,a′).
• Factorize the joint transition probability under a stationary policy.
• Combine everything into the compact Bellman equation.
• Recognize the influence of the discount factor γ.

10. Frequently Asked Questions

What does the term p(s′,r|s,a) represent?

It is the joint probability of landing in state s′ and receiving reward r after taking action a in state s. This joint distribution allows us to handle cases where the reward depends on the next state.

How is the state‑value function v_π(s′) related to q_π(s′,a′)?

v_π(s′) = Σ_{a′} π(a′|s′) q_π(s′,a′). It is the expected value of state s′ when actions are chosen according to policy π.

Why is a stationary policy important for the factorization?

A stationary policy ensures that the action selection probability π(a′|s′) does not change over time, allowing the clean separation of environment dynamics p(s′|s,a) and policy decisions.

Can the Bellman equation be used for optimal policies?

Yes. By replacing π with the optimal policy π* and using the max operator over actions, we obtain the Bellman optimality equation for q_* (s,a). This forms the basis of algorithms such as Q‑learning.

11. Practical Implications for Reinforcement‑Learning Algorithms

Understanding the derivation equips you to implement and debug algorithms that rely on the Bellman equation:

• Policy Evaluation: Iteratively compute q_π using the Bellman update until convergence.
• Policy Improvement: Update the policy by selecting actions that maximize the estimated q‑values.
• Temporal‑Difference Learning: Approximate the expectation with sample returns, leading to methods like SARSA and Q‑learning.

Each of these methods hinges on the same recursive structure derived above, making the Bellman equation a cornerstone of modern reinforcement learning.