Understanding Bellman Equation
In a Markov decision process an agent chooses actions whose outcomes are uncertain, and wants the policy with the greatest expected discounted reward. The Bellman equation states the relationship the optimal utilities must satisfy: the utility of a state is its immediate reward plus the discounted expected utility of the best action from it.
Each piece of that sentence is load-bearing. The maximum ranges over actions, which the agent chooses. The sum inside it ranges over successor states, which the agent does not choose, so the future arrives as an average weighted by the transition model. Swapping the two would describe an agent that picks its own luck.
It is a condition rather than a recipe. With n states it gives n equations in n unknowns, but the max makes them nonlinear, so they cannot be solved directly. Value iteration applies the right-hand side repeatedly as an update and converges because the update is a contraction; policy iteration alternates between evaluating a fixed policy, which IS linear, and improving it.
The discount factor does two jobs. It keeps an infinite run of bounded rewards finite and therefore comparable, and it says that sooner is better. Its size sets the effective horizon: below about 1 the agent is myopic and sees only the immediate reward, and as it approaches 1 the agent will accept a long unrewarding stretch for a distant payoff.
How to Calculate
U(s) = R(s) + \gamma \max_{a \in A(s)} \sum_{s'} P(s' \mid s, a)\, U(s')
where
- U(s)
- the utility of state s under an optimal policy
- R(s)
- the immediate reward for being in s
- \gamma
- the discount factor, between 0 and 1
- P(s' \mid s, a)
- the probability that action a from s lands in s'
Example of Bellman Equation
Take a discount of 0.9. A reward one step away is worth 0.9 of its face value, five steps away 0.5905, ten steps away 0.3487, and fifty steps away 0.0052. The first step at which a reward is worth less than one per cent of its face value is step 44, which is a usable definition of the horizon this discount implies.
That number moves sharply with the discount, and it is the reason the discount is a modelling choice rather than a tuning knob. At 0.99 the same one per cent threshold sits beyond step 450; at 0.5 it arrives at step 7.
The structure matters as much as the arithmetic. In a grid world with a small living cost, an action that keeps the agent where it is can never beat one that moves it toward a better state, however myopic the discount: staying is worth R + gamma U(s) and moving is worth R + gamma U(s'), so the comparison reduces to U(s') against U(s) and the discount cancels entirely.
Frequently Asked Questions
Why can the equations not just be solved?
Because of the maximum. For a FIXED policy the max disappears and what remains is a linear system that can be solved directly, which is exactly what the evaluation step of policy iteration does.
What happens at a discount of exactly 1?
The sum need not converge, and two policies with infinite total reward cannot be compared. It is usable only when every run is guaranteed to reach a terminal state, or when average reward per step is used instead of total reward.
The Bottom Line
The Bellman equation says what the optimal utilities must satisfy: reward now, plus a discounted average over outcomes you do not control, of the best action you do. It is a condition rather than a method, and the max is what makes it interesting and what stops it being linear algebra.