The Bellman Equation: Formulation, Solution Methods, and Extensions
贝尔曼方程：形式化、求解与扩展
2026 · 07 · 27·12 min
Main Concept of the Bellman Equation
The Equation
The Bellman equation provides a way to break down the value of being in a certain situation (a “state”) into two parts:
Immediate Return (Reward): What you gain (or lose) right now by being in that state or taking a certain action.
Future Return (Discounted Future Value): The expected value of what you’ll gain in the future, starting from the new state you end up in, discounted by a factor that reflects how much you care about future rewards compared to immediate ones.
In essence, the Bellman equation says:
The value of a state is the immediate reward you get now plus the discounted value of what you’ll get afterward.
Formally, if V(s) represents the value of state s:
V(s)=R(s)+γs′∑P(s′∣s)V(s′)
where
R(s) = immediate reward from being in state s;
γ = discount factor, 0≤γ<1, which reduces the weight of future rewards as they move further into the future;
P(s′∣s) = probability of moving from state s to state s′.
This recursive relationship ties together the values of all states, allowing us to solve for them either iteratively or through direct methods, given the right information.
The Trade-off between Immediate and Future Return
The trade-off lies in deciding how much importance to place on immediate rewards versus future rewards. A higher discount factor (γ) places more weight on future returns, encouraging long-term planning, while a lower discount factor prioritizes immediate rewards, potentially leading to short-sighted decisions.
Reward of State s
The reward in state s, denoted R(s), represents the immediate gain or loss received upon entering or being in that state. It is typically defined by the environment and varies with the specific problem being solved.
Normally, the reward is a scalar signal. It can also be multidimensional — a vector or higher-order tensor representing several objectives or criteria simultaneously — but that doesn’t change the essence of a reward signal: return a clear signal to the agent and guide its behavior toward specific goals.
Clearly Defined Reward
When the reward is clearly defined, it provides a straightforward objective for the agent to optimize, making it easier to design policies and evaluate performance.
When the Reward Is Hard to Define
Reward modeling / imitation learning: learn an approximate reward function from demonstrations or human feedback — e.g., RLHF fits a reward model to human preference comparisons — or bypass the reward entirely by mimicking expert actions directly (behavioral cloning).
Inverse RL: infer the reward function an expert appears to be optimizing from their observed behavior, then train a policy against the recovered reward.
How to Make the Trade-off?
Clearly, the trade-off can be managed by carefully selecting the discount factor (γ). A higher γ (closer to 1) emphasizes long-term rewards, promoting strategies that prioritize future benefits, while a lower γ (closer to 0) focuses on immediate rewards, favoring short-term gains. The choice of γ depends on the specific problem and goals; for instance, in scenarios where future outcomes are uncertain or less relevant, a lower γ may be appropriate. Conversely, in problems requiring long-term planning, a higher γ is often preferred.
But it is hard to select a static γ as a hyper-parameter up front. There are several methods:
Meta-learning: Instead of hand-picking γ, you can treat it as a parameter to be optimized during training. Techniques like Bayesian optimization or evolutionary strategies can search over the space of γ values and find one that yields the best performance on a validation task.
Adaptive discounting: Some research explores a state-dependent or context-dependent discount factor. For instance, γ might be higher for states where long-term planning is more critical and lower for states where immediate outcomes are paramount. Though less common, this approach is more flexible and can be implemented by learning a function Γ(s) that predicts the appropriate discount based on the current state.
Multi-stage discount: In hierarchical RL, higher-level policies might operate with a longer horizon (larger γ), while lower-level controllers operate with a shorter horizon (smaller γ). By layering these, you avoid committing to a single global discount factor.
Some Real-Life Analogies of the Bellman Equation
Financial Investments
Imagine you have some money to invest. The “state” is having a certain amount of money right now. The “immediate reward” might be the interest or dividend you receive today. The “future value” is the expected growth of your investment over time. The Bellman equation tells you the total value of holding onto that investment — your current returns plus the discounted value of future returns.
Career Decisions
Say you’re choosing whether to go to graduate school or jump straight into a job. The “state” might represent your current position (just graduated, no income yet). The immediate reward could be a small stipend or the salary you’d earn if you start working. The future value is the benefit you’d gain over your lifetime from higher earning potential if you get the degree, discounted because those gains are in the future. The Bellman equation would factor in both the short-term costs and the long-term payoffs to give an overall “value” to each choice.
Planning a Road Trip
If you’re on a long journey and considering your next move — perhaps taking a scenic route or a shortcut — the immediate “reward” might be a beautiful view or saving on gas. The future value would consider which states you might reach next: maybe a route that leads to cheaper accommodations later or better opportunities to restock supplies. The Bellman equation combines the immediate payoff of your current move with the expected benefits in the upcoming stretches of the trip to help you decide which route is “valuable” in the long run.
Solving the Bellman Equation
The state-value function:
V(s)=R(s)+γs′∑P(s′∣s)V(s′)
The action-value function:
Q(s,a)=R(s,a)+γs′∑P(s′∣s,a)V(s′)
The relationship between the two depends on which value function is meant:
For a fixed policyπ: Vπ(s)=∑aπ(a∣s)Qπ(s,a) — the state value is the policy-weighted average of the action values.
For the optimal value functions only: V∗(s)=maxaQ∗(s,a) — the max relation is what defines the Bellman optimality equation; it does not hold for an arbitrary policy.
Solving the Bellman equation means iterating V(s) or Q(s,a) until convergence — to Vπ when evaluating a fixed policy, or to V∗ when solving for optimal control.
Solution Methods
Broadly, there are four families (the middle two are often combined in practice):
Direct solution via linear algebra — exact, when the model is known and the state space is small.
Dynamic programming — value iteration and policy iteration, when the model is known.
Model-free sampling methods — Monte Carlo and temporal-difference (TD) learning (SARSA, Q-learning), which estimate values from sampled experience without a model. For large state or action spaces they are combined with function approximation (linear models or neural networks) to represent V or Q; DQN is the canonical example.
Model-based methods — learn or assume a model of the environment’s dynamics and use it to simulate transitions and plan.
Linear Equation Method
Write the Bellman equation in vector-matrix form. Let V represent the vector of value functions for all states, R the reward vector, and P the state transition probability matrix. Then:
V=R+γPV
where γ is still the discount factor. Simple rearranging gives:
(I−γP)V=R
where I is the identity matrix. If (I−γP) is invertible, we can solve for V directly.
The linear method leads to solving
V=(I−γP)−1R
which provides an exact solution for V when P and R are known. The matrix inversion costs O(∣S∣3), so this is practical only for small state spaces — which is exactly why the iterative methods below exist.
Dynamic Programming Methods
There are two primary goals when solving the Bellman equation via DP:
Policy Evaluation: Compute the value function Vπ(s) for a given policy π. (Evaluation)
Policy Iteration and Value Iteration: Compute the optimal value function V∗(s) and optimal policy π∗. (Improvement)
The difference is that policy evaluation computes the value of a fixed policy, while policy iteration and value iteration improve the policy to find the optimal one.
Policy Evaluation
Algorithm [1] · Policy evaluation
Initialize V(s)←0 (or arbitrarily) for all states s
Repeat:
Δ←0
For each s∈S:
v←V(s)
V(s)←∑aπ(a∣s)∑s′P(s′∣s,a)[R(s,a,s′)+γV(s′)]
Δ←max(Δ,∣v−V(s)∣)
Until Δ<ϵ
Note that Δ compares the new and old value of the same state — it is the maximum change across a full sweep, not a difference between V(s) and V(s′). When the maximum change across all states falls below the threshold ϵ, the value function is considered stable.
Policy Iteration (with Policy Improvement)
Use Algorithm [1] to calculate Vπ, then update the policy greedily.
Algorithm [2] · Policy iteration
Initialize π arbitrarily for all states
Repeat:
Run Algorithm [1] until convergence, obtaining Vπ
For each state s:
π(s)←argmaxa∑s′P(s′∣s,a)[R(s,a)+γVπ(s′)]
Until the policy no longer changes
Value Iteration
Directly compute the optimal value function by iterating the Bellman optimality equation:
V(s)=amaxs′∑P(s′∣s,a)[R(s,a)+γV(s′)]
Algorithm [3] · Value iteration
Initialize V(s) arbitrarily for all states s, e.g. V(s)=0
Repeat:
Δ←0
For each s∈S:
v←V(s)
V(s)←maxa∑s′P(s′∣s,a)[R(s,a)+γV(s′)]
Δ←max(Δ,∣v−V(s)∣)
Until Δ<ϵ
Extract the optimal policy:
π∗(s)=argmaxa∑s′P(s′∣s,a)[R(s,a)+γV(s′)]
Approximation Methods
Approximation methods are used when the state or action space is too large to compute exact solutions. They rely on function approximators — linear models or neural networks — to estimate value functions or policies efficiently.
Model-based Methods
Model-based methods use a model of the environment to simulate transitions and rewards, enabling planning and decision-making without direct interaction with the environment — e.g., Dyna-style updates that mix real and simulated experience, or tree-search planning as in AlphaZero/MuZero, where the value backup inside the search tree is itself a Bellman backup over simulated transitions.
Derived Applications and Extensions
Everything below is, at its core, a different way of using the same recursion. Once you see the Bellman backup as the primitive operation, most of value-based RL — and a surprising amount of classical algorithms — falls out of it.
The Bellman Operator: Why Iteration Converges
Define the Bellman operator T by (TV)(s)=R(s)+γ∑s′P(s′∣s)V(s′). For γ<1, T is a γ-contraction in the sup-norm:
∥TV1−TV2∥∞≤γ∥V1−V2∥∞
By the Banach fixed-point theorem, T has a unique fixed point, and repeated application converges to it geometrically — this is the convergence guarantee behind policy evaluation and value iteration. The optimality operator (T∗V)(s)=maxa∑s′P(s′∣s,a)[R(s,a)+γV(s′)] is also a γ-contraction, with V∗ as its unique fixed point.
TD Learning, SARSA, and Q-Learning
When the model P is unknown, replace the expectation in the Bellman backup with a single sampled transition (s,a,r,s′). The TD error
δ=r+γV(s′)−V(s)
is a sampled Bellman residual, and TD(0) nudges V(s) toward the bootstrap target: V(s)←V(s)+αδ.
SARSA applies the sampled Bellman expectation backup to Q (on-policy): Q(s,a)←Q(s,a)+α[r+γQ(s′,a′)−Q(s,a)], where a′ is the action actually taken next.
Q-learning applies the sampled Bellman optimality backup (off-policy): Q(s,a)←Q(s,a)+α[r+γmaxa′Q(s′,a′)−Q(s,a)].
Deep Q-Networks (DQN)
DQN represents Qθ(s,a) with a neural network and trains it by minimizing the squared Bellman residual against a slowly updated target network θ−:
L(θ)=E[(r+γa′maxQθ−(s′,a′)−Qθ(s,a))2]
Experience replay decorrelates samples; the target network stabilizes the moving bootstrap target. The loss is literally the Bellman optimality equation turned into a regression objective.
Actor–Critic and Advantage Estimation
In actor–critic methods, the critic learns Vϕ via Bellman backups, and the TD error doubles as a one-sample estimate of the advantage A(s,a)=Q(s,a)−V(s), which drives the policy gradient. GAE (generalized advantage estimation) blends multi-step Bellman targets with a decay parameter λ. This machinery carries directly into LLM post-training: PPO-based RLHF treats token generation as an MDP, and the value head trained there obeys the same recursion over token sequences.
Extending the Backup Itself
Soft Bellman equation (maximum-entropy RL): replace the hard max with a log-sum-exp, V(s)=αlog∑aexp(Q(s,a)/α), which yields stochastic optimal policies and underlies SAC.
Distributional Bellman equation: model the full return distribution rather than its mean, Z(s,a)=Dr+γZ(s′,a′); C51 and QR-DQN are built on this.
Continuous Time: The HJB Equation
Taking the continuous-time limit of the Bellman equation gives the Hamilton–Jacobi–Bellman partial differential equation, the foundation of optimal control theory (LQR, trajectory optimization in robotics). Discrete-time RL and continuous-time control are the same idea on different clocks.
Beyond RL: Classical Dynamic Programming
Bellman–Ford shortest paths is value iteration specialized to a deterministic shortest-path problem: costs instead of rewards, min instead of max, and γ=1.
Inventory control and operations research — where the equation originated in the 1950s — solve restocking policies as Bellman recursions over stock levels.
Option pricing: binomial-tree valuation of American options is a Bellman backup with risk-neutral probabilities, where the early-exercise decision plays the role of the max.