A decision changes future opportunities
A locally attractive reward need not be the best choice when an action also changes the next state. An infinite-horizon discounted Markov decision process makes this tradeoff explicit. We study a finite known model and maximize expected reward; this is planning with a model, not a claim that the model has been learned from data.
Definition 10.1.1
(Discounted Markov decision process)
Let be a finite nonempty state set. Each state has a finite nonempty action set . On choosing , receive the finite deterministic reward and move to with probability , where these probabilities are nonnegative and sum to one. The model is time-homogeneous and, conditional on the current state and action, the next-state distribution is independent of the earlier history. Choose a discount factor . Because there are finitely many state–action pairs, rewards are bounded; the discounted return therefore converges absolutely on every trajectory, with even when . A policy may depend on the observed history and may randomize; a stationary deterministic policy selects one fixed action in each state. For a starting state , write for policy 's expected discounted return and .
Definition 10.1.2
(Bellman operator and value iteration)
Define the Bellman operator on real vectors indexed by :
The maximization is outside the expectation: the action is selected before the next state is drawn. A finite action set ensures a maximizing action exists. Value iteration starts from any finite vector and repeatedly sets .
Why iteration converges
Theorem 10.1.3
(Contraction of the Bellman operator)
For all real vectors indexed by , .
Proof
(The maximum is non-expansive and the probabilities average)
For vectors , write . For two finite lists, the difference of their maxima is bounded in absolute value by the largest absolute entrywise difference. Applying this inequality, and using nonnegative probabilities summing to one, gives
for every state. Thus .
Theorem 10.1.4
(Value iteration converges to the unique fixed point)
For every starting vector , the iterates converge in to a vector with . This is the only fixed point of , and .
Proof
(Geometric differences give a Cauchy sequence)
The contraction makes successive differences decrease geometrically: . The tail of the resulting geometric series shows that is Cauchy in the finite-dimensional sup norm and hence converges to some . The operator is continuous by the same inequality, so . If too, then , forcing equality of the vectors. The fixed point is unique.
Concept lensAlgorithmic
Each iterate is a finite-horizon optimum
Starting from , the vector is the largest expected value of over -step plans from : each Bellman update adds one decision at the front. In the two-state table, is the best two-step reward, achieved both by staying twice and by moving then collecting in . This explains the factor : the horizon beyond steps is weighted by .
Theorem 10.1.5
(The fixed point is the optimal value)
Let be the fixed point of . For every starting state , , even when history-dependent randomized policies are allowed. Moreover, choosing in every state an action that attains the maximum in defines a stationary deterministic policy with .
Proof
(Compare every policy with the fixed point over N steps)
Since is at least the Bellman expression for every action, condition first on the observed history and chosen action. The Markov property makes the next-state expectation the stated probability-weighted sum; averaging over any randomized action preserves the inequality. Repeating this argument over steps gives, for every policy ,
The last term tends to zero because is bounded. If , the absolute reward tail is at most . Thus no policy has larger return, so . Select a maximizing action at the exact vector in every state and use that stationary policy: the inequalities become equalities at every step, so this stationary deterministic policy attains and .
Proof X-ray
Where each hypothesis enters the optimality proof
The non-obvious move is to compare an arbitrary policy not with the unknown optimal return but with the fixed point , and to truncate at time with as a terminal reward. Each ingredient has a job. The fixed-point equation supplies the one-step inequality that is at least for every action . The Markov property lets that inequality be applied after any observed history, which is why history dependence and randomization cost nothing. Finiteness of and keeps and the rewards bounded, and makes and the reward tail vanish as . The argument closes because every inequality in the chain is an equality for the greedy stationary policy, so that policy reaches the upper bound that every other policy can only approach from below. Without the terminal term need not vanish, and the comparison with says nothing about the infinite sum.
A computable stopping certificate
Proposition 10.1.6
(Residual error bound)
For every real vector indexed by , put . Then
Proof
(Triangle inequality plus contraction)
The triangle inequality and contraction give , using . Moving the last term to the left gives , and since we may divide by it.
A small residual certifies closeness to the value vector in the sup norm; it does not by itself identify an optimal action when approximate action values are close, nor does it show that the model accurately represents the real environment.
Common mistake
(The residual is not the error)
Stopping when two successive iterates differ by and reporting as the error is wrong when is near . Take one state, one action, reward and , so . The number has error , but , so its residual is only . Here the error equals exactly, so the factor cannot be dropped.
Worked example
Worked example 10.1.7
(A two-state example with a tie)
There are two states, and , and . In , action stay pays 1 and returns to , while move pays 0 and moves to . In the only action pays 3 and returns to . These transitions are deterministic special cases of the probability model. The Bellman equations are
Start with , in the order :
| Iteration | Maximizing action at using the previous row | ||
|---|---|---|---|
| 0 | 0 | 0 | none |
| 1 | 1 | 3 | stay |
| 2 | tie | ||
| 3 | move |
For the fixed point, the equation gives . At , taking move gives 3; with , stay gives , so move is strictly better. The vector satisfies both equations and is the unique fixed point. The tie in iteration 2 compares actions using , not the final values; it does not imply a tie in the optimal policy.
For example, the residual of is , so the bound certifies error at most . Here the actual sup-norm error is also .
Common mistake
(A tie in an iterate is not a tie in the optimum)
Reading the greedy action off an intermediate vector can select a suboptimal action. In the example above, makes stay and move tie at (both give ). Yet with the action stay is worth only and move is worth , so only move is optimal. Extract the policy from , or from an iterate whose certificate separates the actions.
Worked example 10.1.8
(A stochastic transition)
Let . In the only action pays 4 and returns to . In , safe pays 1 and returns to , while gamble pays 0 and moves to or to with probability each. Then
The equation gives . Test the vector : the safe expression is and the gamble expression is , so , and . This vector is a fixed point, hence the unique one , and gamble is the optimal action at .
Now take , the value of the policy that always chooses safe. Then and , so and the certificate gives error at most . The true error is , inside the certificate. The positive residual reflects that always-safe is not optimal: gamble is strictly better at .
Worked example 10.1.9
(The edge case of no weight on the future)
Use the same model with . The operator becomes and for every , so whatever was, and . Thus and the optimal action at is safe. With the same model preferred gamble, because lets the chance of reaching count. The contrast shows that the discount factor decides how reward now is traded against opportunity later.
Limits and exercises
Discounting and bounded rewards were essential to this convergence argument. Setting removes the contraction guarantee, and an undiscounted infinite sum can diverge; an average-reward or finite-horizon problem needs its own conditions. Transition uncertainty is handled by the stated probabilities, but errors in those probabilities and rewards require a separate model-error analysis.
Counterexample mode
Dropping the discount destroys uniqueness and existence
The claim that for every the operator has a unique fixed point and value iteration converges to it is false at . Take one state, one action and reward . Then for every real number , so every number is a fixed point: iteration started at stays at and iteration started at stays at , so uniqueness fails. Now change the reward to . Then has no fixed point, and diverges, just as the undiscounted sum does. The repair is the stated hypothesis (or a different framework, such as a finite horizon or average reward).
Quick check
(In the example, compute and its residual using one further Bellman update. Is the action at selected to compute a tie?)
Solution · Answer
Using : the stay expression at is and the move expression is , so and move is strictly better, not a tie. Also . One more update gives , so the residual of is . The certificate bounds the error by , and the actual error matches it.
Quick check
(If , what does the Bellman operator return and how many updates are needed to reach its fixed point?)
Solution · Answer
With , for every , so the output does not depend on the input. One update from any already gives , and a second leaves it unchanged. The optimal policy is myopic: pick an action with the largest immediate reward.
Quick check
(Consider a separate one-step problem with a common exogenous random outcome, independent of action, and a specified payoff for every action–outcome pair. Give a two-outcome example where observing the outcome before choosing improves expected payoff. Explain why this information pattern differs from choosing first.)
Solution · Answer
Let the outcome be or with probability each. Action pays 1 if and 0 if ; action pays 0 if and 1 if . Choosing first, each action has expected payoff . Observing first, choose after and after , which pays 1 for sure. The first pattern computes and the second . In the Bellman operator the action is selected before the next state is drawn, so it has the first pattern. In the original MDP, action-dependent transition probabilities alone do not specify a common joint outcome for all actions.
Exercise 10.1.10
(Show that for real numbers and , . This is the inequality used in the contraction proof.)
FoundationProof
Hint(1)
Choose an index where attains its maximum and compare with the same entry of .
Solution(3)
- 1
Bound one direction
Key step
Let and choose with . Since , we get .
Because: the maximum of is at least its entry .
- 2
Swap the roles of the two lists
The same argument with and exchanged gives .
- 3
Combine the two directions
∎Both and its negative are at most , so .