Bellman Equation

The defining characteristic of the Bellman equation is its ability to break down an infinite-horizon problem into a two-part structure: the immediate reward plus the discounted value of the successor state. This allows a complex sequential problem to be solved by iteratively applying a single-step update. The value of a state V(s) is defined as the expected return starting from s, which is equivalent to the immediate reward R(s,a) plus the expected value of the next state V(s'). This bootstrapping property eliminates the need to simulate infinite trajectories.

A problem exhibits optimal substructure if its optimal solution can be constructed from optimal solutions of its subproblems. The Bellman equation explicitly encodes this property for Markov Decision Processes (MDPs). The Bellman Optimality Equation states that the optimal value of a state is the maximum expected return achievable by taking the best action, which in turn depends on the optimal values of subsequent states. This guarantees that a greedy policy with respect to the optimal value function is globally optimal, forming the basis for algorithms like Value Iteration.

The Bellman operator is a contraction mapping in the space of value functions with respect to the max norm. When applied iteratively, the distance between successive value function estimates shrinks by a factor of at least the discount factor γ (gamma). By the Banach fixed-point theorem, repeated application of the Bellman operator is guaranteed to converge to a unique fixed point—the true value function—regardless of the initial value estimates. This property provides the theoretical convergence guarantee for Dynamic Programming algorithms like Value Iteration.

The validity of the Bellman equation is strictly contingent on the environment satisfying the Markov property: the future is conditionally independent of the past given the present state. The equation assumes that the state signal s_t contains all relevant information to predict the next state and reward. If the state representation is non-Markovian (e.g., a single camera frame in a partially observable environment), the Bellman equation fails to hold, and the agent requires memory-augmented architectures like Recurrent Neural Networks or explicit belief states to restore the property.

The Bellman equation exists in two distinct variants serving different purposes. The Bellman Expectation Equation evaluates a specific fixed policy π, computing V^π(s) as the expected return when following that policy. The Bellman Optimality Equation directly solves for the optimal value function V*(s) by maximizing over actions rather than averaging according to a policy. The expectation form is used in Policy Evaluation, while the optimality form drives control algorithms like Q-Learning and Value Iteration.

While the Bellman equation provides an exact solution in theory, its tabular implementation suffers from the curse of dimensionality. The computational and memory requirements grow exponentially with the number of state variables. For a state space with n dimensions and k discrete values each, the table size is k^n. This renders tabular Dynamic Programming intractable for real-world problems. This limitation motivates the use of function approximation with deep neural networks, as seen in Deep Q-Networks (DQN), which generalize across states rather than storing values individually.