The Bellman Equation: Defining Optimal Value Functions

Introduction

In our previous lesson, we established the mathematical framework for reinforcement learning: the Markov Decision Process (MDP). We defined the problem of an agent interacting with an environment to maximize a cumulative reward. However, we haven't yet discussed the solution. How does an agent determine the best action to take in any given state? The key lies in being able to quantify the long-term "value" of being in a state.

This lesson introduces one of the most fundamental concepts in reinforcement learning: the Bellman equation. You will derive this equation and understand its central role in defining value functions. We will first explore the version for evaluating a given policy, and then, crucially, the version for finding the optimal value function. This recursive equation forms the theoretical basis for a vast array of RL algorithms, and understanding it is essential for designing intelligent agents. Given your background in computer science, you'll see deep connections to dynamic programming and fixed-point iteration.

The Value Function and The Bellman Expectation Equation

The agent's goal is to maximize the cumulative discounted reward, which we call the return. The value of a state is defined as the expected return an agent can get starting from that state.

First, let's formalize the concepts of return and the state-value function, $V^{\pi }(s)$, which is the expected return starting in state $s$ and then following a specific policy $\pi$.

As you saw, the return $G_t$ from time step $t$ is the discounted sum of future rewards:

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots =\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$$

The state-value function for a policy $\pi$, denoted $V^{\pi }(s)$, is the expected return, conditioned on starting in state $s$ and following policy $\pi$ thereafter:

$$V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$$

The core insight of Richard Bellman was that this value function has a recursive structure. The value of the current state can be expressed in terms of the value of the next state. This relationship is what's known as the Bellman equation.

Let's see the derivation for a policy $\pi$.

Let's formalize this. The decomposition you just saw is:

$$V^{\pi }(s)={\mathbb{E}}_{\pi }[R_{t+1}+\gamma V^{\pi }(S_{t+1})|S_t=s]$$

This is the Bellman expectation equation. It states that the value of being in state $s$ under policy $\pi$ is the immediate expected reward plus the discounted expected value of the next state, where the expectation is taken over the actions selected by the policy $\pi$ and the environment's transition dynamics.

Expanding the expectation, we get:

$$V^{\pi }(s)=\sum _{a\in A}\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma V^{\pi }(s^{\prime })\right]$$

Similarly, we can define the action-value function, $Q^{\pi }(s,a)$, which is the expected return after taking action $a$ in state $s$ and following policy $\pi$ thereafter. Its Bellman equation is:

$$Q^{\pi }(s,a)=\sum _{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma \sum _{a^{\prime }\in A}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })\right]$$

For a finite number of states, the Bellman expectation equation defines a system of linear equations. If you have $|S|$ states, you have $|S|$ linear equations with $|S|$ unknowns (the values $V^{\pi }(s)$ for each state). This system can be solved directly.

The direct solution is $V^{\pi }=(I-\gamma P^{\pi }{)}^{-1}{R}^{\pi }$. While elegant, the $O(|S{|}^3)$ complexity of matrix inversion makes it impractical for large state spaces. This motivates the iterative algorithms we will discuss later.

The Bellman Optimality Equation

Evaluating a policy is useful, but the ultimate goal is to find the best policy. This leads us to the concept of the optimal value function.

The optimal state-value function, $V^{\ast }(s)$, is the maximum value achievable from state $s$ over all possible policies.

$$V^{\ast }(s)=\underset{\pi }{\max }{V}^{\pi }(s)$$

Similarly, the optimal action-value function is $Q^{\ast }(s,a)={\max }_{\pi }{Q}^{\pi }(s,a)$.

The Bellman optimality equation provides a recursive relationship for these optimal value functions. It looks similar to the expectation equation, but with a crucial difference: a maximization operator.

As derived by Ng, the Bellman optimality equation for $V^{\ast }(s)$ is:

$$V^{\ast }(s)=\underset{a\in A}{\max }\sum _{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma V^{\ast }(s^{\prime })\right]$$

This equation says that the optimal value of a state $s$ is found by taking the action $a$ that maximizes the expected immediate reward plus the discounted optimal value of the resulting state $s^{\prime }$.

This equation is the key to solving RL problems. If we can find $V^{\ast }$, we can determine the optimal policy. The optimal policy ${\pi }^{\ast }(s)$ is simply to take the action a that achieves the maximum in the Bellman optimality equation:

$${\pi }^{\ast }(s)=\underset{a\in A}{\mathrm{argmax}}\sum _{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma V^{\ast }(s^{\prime })\right]$$

There is also a Bellman optimality equation for $Q^{\ast }(s,a)$. It expresses the optimal value of a state-action pair in terms of the optimal values of the next state-action pairs:

$$Q^{\ast }(s,a)=\sum _{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma \underset{a^{\prime }\in A}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })\right]$$

Having $Q^{\ast }$ makes finding the optimal policy even simpler: ${\pi }^{\ast }(s)={\mathrm{argmax}}_a{Q}^{\ast }(s,a)$.

The following diagram provides a visual intuition for these recursive relationships.

Unlike the Bellman expectation equation, the optimality equation is non-linear due to the max operator. We cannot solve it with a simple matrix inversion. This necessitates different solution methods, which rely on the theoretical properties of this equation.

The Theory of Contraction Mappings

Why can we be sure that iterative algorithms will converge to the unique optimal value function? The answer lies in the mathematics of fixed-point theory, specifically the Banach fixed-point theorem. This theorem states that if an operator is a "contraction," it has a unique fixed point, and applying the operator repeatedly will converge to that fixed point from any starting point.

The Bellman equations can be rewritten using operators. For example, the Bellman optimality equation becomes $V=B^{\ast }(V)$, where $B^{\ast }$ is the Bellman optimality operator.

This theoretical foundation is powerful. It assures us that by repeatedly applying the Bellman optimality operator to an arbitrary initial value function, we will provably converge to the true optimal value function.

Case Study: Optimal Asset Allocation

Let's see the Bellman optimality equation applied to a concrete, non-trivial problem from finance: dynamic asset allocation. The goal is to decide how much wealth to allocate between a risky and a risk-free asset over time to maximize the utility of final wealth.

This example is a classic application of dynamic programming. It beautifully illustrates how the Bellman equation allows us to break a complex, multi-step optimization problem into a sequence of simpler, single-step problems.

Conclusion

In this lesson, we have derived the central equations of reinforcement learning. These equations provide the link between the value of a state and the values of its potential successor states, allowing us to solve for the values that guide optimal decision-making.

Here are the key takeaways:

• The Bellman Expectation Equation provides a recursive definition for the value function $V^{\pi }$ of a given policy $\pi$. It forms a system of linear equations that can be solved directly for small state spaces.
• The Bellman Optimality Equation defines the optimal value function $V^{\ast }$, which gives the maximum possible return from any state. It is a non-linear equation due to the maximization over actions.
• Bellman Operators and Contraction Mappings: The Bellman equations can be framed as finding the fixed point of an operator. Both the policy operator $B^{\pi }$ and the optimality operator $B^{\ast }$ are $\gamma$-contractions, which guarantees the existence of a unique fixed point ($V^{\pi }$ or $V^{\ast }$) and the convergence of iterative solution methods.
• Solving for the Optimal Policy: Finding $V^{\ast }$ is the primary goal, as the optimal policy ${\pi }^{\ast }$ can be easily extracted from it by choosing the action that maximizes the one-step lookahead value.

We now have the theoretical tools to find optimal policies, assuming we have a perfect model of the environment (the MDP). In our next lesson, we will introduce Q-learning, a powerful algorithm that leverages the Bellman optimality equation to learn optimal policies even without a model of the environment's dynamics, learning directly from experience.