Bellman Equation
The Bellman equation expresses the value of being in a given state (or taking a given action) as the immediate reward plus the discounted value of whatever state follows, forming the recursive foundation of dynamic programming and…
Definition
The Bellman equation expresses the value of being in a given state (or taking a given action) as the immediate reward plus the discounted value of whatever state follows, forming the recursive foundation of dynamic programming and reinforcement learning.
Overview
Named after Richard Bellman, who introduced dynamic programming in the 1950s, the Bellman equation decomposes a sequential decision problem into a simple recursive relationship: the value of a state equals the expected immediate reward plus the discounted value of the next state, averaged over the possible transitions. This recursive structure is what allows complex multi-step optimization problems to be solved by working backward or by iterative approximation, rather than by exhaustively enumerating every possible sequence of decisions. In the context of Markov Decision Processes, there are two closely related forms: the Bellman expectation equation, which evaluates a fixed policy, and the Bellman optimality equation, which characterizes the value of the best possible policy by taking a max over actions instead of an expectation. Solving the Bellman optimality equation — via value iteration, policy iteration, or, in reinforcement learning, algorithms like Q-learning — yields the optimal value function and, from it, an optimal policy. The Bellman equation is what makes Q-learning's update rule work: each observed transition nudges the current estimate of a state-action value toward a target built from the Bellman equation, using the observed reward plus the discounted value of the best action in the next state. This same recursive idea extends into deep reinforcement learning, where a neural network approximates the value or Q-function and is trained to satisfy the Bellman equation approximately (as in Deep Q-Networks), and into actor-critic methods, where a critic network estimates values used to update a policy network. The equation's central insight — that optimal long-term behavior can be computed from purely local, one-step relationships — remains one of the most important ideas in optimization and control theory.
Key Concepts
- Recursively defines a state's value as immediate reward plus discounted future value
- Bellman expectation equation evaluates a fixed policy
- Bellman optimality equation characterizes the best possible policy via a max operator
- Enables dynamic-programming solutions like value iteration and policy iteration
- Underpins the Q-learning temporal-difference update rule
- Extends to function approximation in deep reinforcement learning (e.g. DQN)
- Applies to both state-value functions and action-value (Q) functions