The Bellman Expectation Equation

In the previous chapter, we defined the state-value function $V^{\pi}(s)$ and the action-value function $Q^{\pi}(s,a)$, which represent the expected return when starting from state $s$, or starting from state $s$ and taking action $a$, respectively, and following policy $\pi$ thereafter. Now, we need a way to compute these values. The Bellman equations provide this mechanism by relating the value of a state or state-action pair to the values of its potential successor states. They establish a recursive relationship that is fundamental to understanding and solving reinforcement learning problems.

The Bellman expectation equation specifically describes this relationship for a given policy $\pi$. It expresses the value function in terms of the expected immediate reward plus the discounted expected value of the next state. Let's examine this for both $V^{\pi}$ and $Q^{\pi}$.

Bellman Expectation Equation for V^π(s)

Recall the definition of the state-value function: $V^{\pi}(s) = \mathbb{E}_{\pi}[G_t | S_t = s]$ where $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots$ is the total discounted return starting from time $t$. We can rewrite the return recursively: $G_t = R_{t+1} + \gamma G_{t+1}$ Substituting this into the definition of $V^{\pi}(s)$: $V^{\pi}(s) = \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} | S_t = s]$ Using the linearity of expectation, we separate this into two parts: $V^{\pi}(s) = \mathbb{E}_{\pi}[R_{t+1} | S_t = s] + \gamma \mathbb{E}_{\pi}[G_{t+1} | S_t = s]$ To evaluate these expectations, we need to consider the actions the agent might take according to its policy $\pi(a|s)$, and the possible resulting next states $s'$ and rewards $r$ determined by the environment's dynamics $p(s', r | s, a)$.

The first term, $\mathbb{E}_{\pi}[R_{t+1} | S_t = s]$, is the expected immediate reward. The agent first chooses an action $a$ based on $\pi(a|s)$, and then the environment responds with a next state $s'$ and reward $r$ based on $p(s', r | s, a)$. Summing over all possibilities: $\mathbb{E}_{\pi}[R_{t+1} | S_t = s] = \sum_{a} \pi(a|s) \sum_{s', r} p(s', r | s, a) r$ The second term, $\gamma \mathbb{E}_{\pi}[G_{t+1} | S_t = s]$, involves the expected discounted return from the next state $S_{t+1}$. The expectation $\mathbb{E}_{\pi}[G_{t+1} | S_t = s]$ averages over the actions $a$ taken from state $s$ and the resulting next states $s'$. The expected return starting from a next state $s'$ is simply $V^{\pi}(s')$. Therefore: $\mathbb{E}_{\pi}[G_{t+1} | S_t = s] = \sum_{a} \pi(a|s) \sum_{s', r} p(s', r | s, a) V^{\pi}(s')$ Note that the reward $r$ in $p(s', r | s, a)$ doesn't affect the value of $V^{\pi}(s')$, so we could also sum over $p(s' | s, a) = \sum_r p(s', r | s, a)$.

Putting both terms back together gives the Bellman expectation equation for $V^{\pi}$: $V^{\pi}(s) = \sum_{a} \pi(a|s) \sum_{s', r} p(s', r | s, a) [r + \gamma V^{\pi}(s')]$

This equation states that the value of being in state $s$ under policy $\pi$ is the average over all actions $a$ (weighted by the probability $\pi(a|s)$ of taking them) of the expected immediate reward plus the discounted expected value of the subsequent state $s'$ (averaged over all possible $s'$ and $r$ weighted by $p(s', r | s, a)$).

It's often helpful to think of this relationship in terms of the action-value function $Q^{\pi}(s,a)$. The value $V^{\pi}(s)$ is simply the expected value of $Q^{\pi}(s,a)$ over the actions $a$ that policy $\pi$ might choose in state $s$: $V^{\pi}(s) = \sum_{a} \pi(a|s) Q^{\pi}(s,a)$

The value of a state $V^{\pi}(s)$ is the expected value of the action values $Q^{\pi}(s,a)$, averaged over the actions $a$ chosen by the policy $\pi$.

Bellman Expectation Equation for Q^π(s,a)

We can derive a similar equation for the action-value function $Q^{\pi}(s,a)$. Recall its definition: $Q^{\pi}(s,a) = \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a]$ Again, substitute $G_t = R_{t+1} + \gamma G_{t+1}$: $Q^{\pi}(s,a) = \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]$ $Q^{\pi}(s,a) = \mathbb{E}_{\pi}[R_{t+1} | S_t = s, A_t = a] + \gamma \mathbb{E}_{\pi}[G_{t+1} | S_t = s, A_t = a]$ Now, the expectation is conditioned on having already taken action $a$ in state $s$. The environment then determines the next state $s'$ and reward $r$ according to $p(s', r | s, a)$.

The first term is the expected immediate reward after taking action $a$ in state $s$: $\mathbb{E}_{\pi}[R_{t+1} | S_t = s, A_t = a] = \sum_{s', r} p(s', r | s, a) r$ The second term involves the expected discounted return starting from the next state $S_{t+1} = s'$. Since the agent follows policy $\pi$ from state $s'$ onwards, the expected return is $\mathbb{E}_{\pi}[G_{t+1} | S_{t+1} = s'] = V^{\pi}(s')$. Averaging over all possible next states $s'$ and rewards $r$: $\gamma \mathbb{E}_{\pi}[G_{t+1} | S_t = s, A_t = a] = \gamma \sum_{s', r} p(s', r | s, a) V^{\pi}(s')$ Combining these gives the Bellman expectation equation for $Q^{\pi}$ in terms of $V^{\pi}$: $Q^{\pi}(s,a) = \sum_{s', r} p(s', r | s, a) [r + \gamma V^{\pi}(s')]$

This tells us that the value of taking action $a$ in state $s$ is the expected immediate reward plus the discounted expected value of the next state, averaged over all possible next states $s'$ and rewards $r$.

The value of a state-action pair $Q^{\pi}(s,a)$ is the expected value over possible next states $s'$ and rewards $r$. Each outcome $(s', r)$ occurs with probability $p(s', r | s, a)$ and contributes its immediate reward $r$ plus the discounted value of the next state $\gamma V^{\pi}(s')$ to the expectation.

We can also express $Q^{\pi}(s,a)$ fully in terms of $Q^{\pi}$ by substituting $V^{\pi}(s') = \sum_{a'} \pi(a'|s') Q^{\pi}(s',a')$ into the equation: $Q^{\pi}(s,a) = \sum_{s', r} p(s', r | s, a) \left[r + \gamma \sum_{a'} \pi(a'|s') Q^{\pi}(s', a')\right]$

The System of Equations

For a finite MDP, the Bellman expectation equation for $V^{\pi}$ gives a system of $|S|$ linear equations in $|S|$ unknowns (the values $V^{\pi}(s)$ for all $s \in S$). Similarly, the equation for $Q^{\pi}$ gives a system of $|S| \times |A|$ linear equations in $|S| \times |A|$ unknowns (the values $Q^{\pi}(s,a)$ for all $s \in S, a \in A$).

These equations are fundamental because they define a consistency condition. The value of a state (or state-action pair) must be consistent with the expected value derived from its possible successors under the policy $\pi$. If we know the policy $\pi$ and the environment dynamics (the MDP), we can, in principle, solve this system of equations to find the exact value function $V^{\pi}$ or $Q^{\pi}$. This process is known as policy evaluation.

The Bellman expectation equations are the foundation upon which methods like Dynamic Programming (covered next) build to evaluate policies and find optimal ones, assuming a perfect model of the environment is available. They also inspire model-free methods like Temporal-Difference learning (discussed in later chapters) that estimate these values from experience.