Why Local Maximization Can Be Globally Optimal
A treatment decision at one stage can change both the reward received now and the state in which later decisions are made. Therefore, maximizing immediate reward at each stage is not generally optimal. The relevant local comparison is instead between the expected reward from an action and the best achievable continuation after that action. Backward induction makes this comparison precise: it incorporates future opportunities into each current-stage Q-function and then proves that the resulting decisions maximize total expected reward.
The claim is exact for a finite-horizon decision problem when its assumptions hold. In particular, the state must contain the information needed to describe future rewards and transitions, and each stage’s maximum must be attained. Under these conditions, the proof compares the recursively constructed regime with every other admissible regime, not merely with a particular alternative.
Setup and Assumptions
Assume the state is sufficient in the following sense: conditional on \(S_t=s\) and \(A_t=a\), the joint distribution of the current reward and next state is described by a fixed transition-and-reward kernel \(K_t(dr,ds'\mid s,a)\). This law does not depend on earlier history once \(s\) and \(a\) are specified. If the available information includes relevant past history, that history must be included in the state. For a causal interpretation, the reward and transition laws must also be the appropriate laws under the intervention that sets the action; this tutorial takes those laws as given.
For a transparent set of sufficient regularity conditions, take the horizon \(T\) to be finite, each action set \(\mathcal A_t\) to be finite and nonempty, rewards to be measurable and uniformly bounded in absolute value by a constant \(M<\infty\), and the kernels to be measurable in the state and action. These assumptions make all expected sums finite. Finiteness of the action sets also ensures that a maximizing action exists. More general spaces can be handled if maxima are attained and a measurable maximizing rule exists; a supremum that is not attained does not automatically define an optimal regime.
The Q-function accounts for the current reward and the value of the next state under optimal future decisions. It is not merely the expected reward at the current stage. The terminal convention \(V_{T+1}^*=0\) means that all rewards through stage \(T\) are included in \(R_1+\cdots+R_T\); a terminal reward can instead be included in the last-stage reward.
Worked Example: Two Stages With Different Future States
Worked Example: Two Stages With Different Future States
There is one initial state. At stage 1, action 0 gives reward 1 and leads to state \(x\) with probability \(0.75\) and \(y\) with probability \(0.25\). Action 1 gives reward 0 and leads to \(x\) with probability \(0.20\) and \(y\) with probability \(0.80\). At stage 2, rewards are:
| Stage-2 state | Reward for action 0 | Reward for action 1 | Optimal value |
|---|---|---|---|
| \(x\) | 3 | 1 | 3 |
| \(y\) | 0 | 4 | 4 |
At stage 2, the maximum rewards give \(V_2^*(x)=\max(3,1)=3\) and \(V_2^*(y)=\max(0,4)=4\). Thus stage 1 action 0 has value \(1+0.75(3)+0.25(4)=1+2.25+1=4.25\). Action 1 has value \(0+0.20(3)+0.80(4)=0+0.60+3.20=3.80\). The maximizing first action is 0, followed by action 0 in state \(x\) and action 1 in state \(y\). Its total expected reward is 4.25.
The larger immediate reward for action 0 is not by itself the reason to choose it: the comparison also accounts for the chance of reaching each stage-2 state. If the transition probabilities were different, action 1 could have the larger total value despite its smaller immediate reward.
Optimality Theorem and Proof
Proof. We use backward induction on \(t\). At \(t=T+1\), both the optimal continuation value and every regime’s continuation value equal 0, so the claimed inequality holds. Now suppose \(V_{t+1}^d(s')\leq V_{t+1}^*(s')\) for every next state \(s'\). Under regime \(d\), the stage-\(t\) action at state \(s\) is \(d_t(s)\). The conditional value recursion and the induction hypothesis give
The first inequality follows because the next-state value under \(d\) is no larger at every state, and conditional expectation preserves inequalities. The last inequality follows from the definition of the maximum. This proves dominance at stage \(t\), completing the induction. For \(d^*\), its action attains the maximum at every state; the same recursion, starting with \(V_{T+1}^{d^*}=V_{T+1}^*=0\), gives equality at each stage. Finally, averaging the statewise inequality at \(t=1\) over any initial-state distribution gives the stated comparison of regime values. \(\square\)
The proof’s key comparison is between the continuation value of an arbitrary regime and the optimal continuation value. It does not claim that a current action maximizing immediate reward is optimal. Rather, it shows that once the future values have been correctly computed, maximizing the resulting Q-function at the current stage cannot do worse than the action chosen by any competing regime.
Worked Example: Three Stages, Recomputed Backward
Worked Example: Three Stages, Recomputed Backward
Consider three stages. At stage 3, the rewards in states \(u\) and \(v\) are as follows:
| Stage-3 state | Action 0 | Action 1 | Maximum |
|---|---|---|---|
| \(u\) | 5 | 2 | 5 |
| \(v\) | 1 | 4 | 4 |
Therefore, \(V_3^*(u)=5\) and \(V_3^*(v)=4\). At stage 2, the action determines both the immediate reward and the next state. In state \(L\), action 0 gives reward 2 and leads to \(u\), while action 1 gives reward 1 and leads to \(v\). The two Q-values are \(2+5=7\) and \(1+4=5\), so \(V_2^*(L)=7\), attained by action 0. In state \(R\), action 0 gives reward 0 and leads to \(v\); action 1 gives reward 3 and leads to \(u\). The Q-values are \(0+4=4\) and \(3+5=8\), so \(V_2^*(R)=8\), attained by action 1.
Initially, stage-1 action 0 gives reward 1 and leads to \(L\) with probability 0.60 and \(R\) with probability 0.40. Its value is \(1+0.60(7)+0.40(8)=1+4.2+3.2=8.4\). Action 1 gives reward 0 and leads to \(L\) with probability 0.20 and \(R\) with probability 0.80. Its value is \(0+0.20(7)+0.80(8)=1.4+6.4=7.8\). The optimal first action is 0, and the full regime then chooses action 0 in \(L\), action 1 in \(R\), action 0 in \(u\), and action 1 in \(v\). The calculations add the immediate reward to the continuation value at every step; omitting either term changes the answer.
Measurable Decisions and Randomization
With finitely many actions, choosing a maximizing action can be made into a measurable rule. Fix an ordering of the actions. At each state, choose the first action in that ordering whose Q-value equals the maximum. Each Q-function is measurable under the kernel assumptions, and the set on which a particular action is the first maximizer can be expressed using finitely many measurable comparisons of Q-values. The resulting rule is therefore measurable. This avoids a hidden gap between the pointwise existence of a maximizing action and the existence of an admissible regime.
Randomization does not improve the maximum in this setting. If at state \(s\) a decision rule chooses action \(a\) with probabilities \(\pi(a\mid s)\), its one-step continuation value, with optimal future values already included, is
The inequality holds term by term because each \(Q_t(s,a)\) is at most the maximum, and the probabilities sum to 1. Thus randomization cannot exceed the value of a maximizing deterministic action. This argument does not say randomization is never useful under additional constraints; it says it cannot improve the unconstrained finite-action maximum defined here.
Worked Example: A Randomized Choice at the Final Stage
Suppose at a final-stage state the Q-values are 6 for action 0 and 2 for action 1. A rule that chooses action 0 with probability 0.25 and action 1 with probability 0.75 has expected value \(0.25(6)+0.75(2)=1.5+1.5=3\). The deterministic maximizing action has value 6, so randomization lowers value by \(6-3=3\). The calculation is a direct instance of the weighted-average inequality: a probability-weighted average of 6 and 2 cannot exceed 6.
Diagnostics, Alternatives, and Limits
A backward calculation should be checked at each stage, not only at the final comparison. Confirm that each Q-value includes the current reward and the continuation value; that transition probabilities sum to 1; and that the selected action actually attains the largest listed Q-value. In a stochastic example, check each weighted sum explicitly. A useful independent check for a very small problem is to evaluate the complete value of every possible action sequence or state-dependent rule and compare the best one with the backward result.
That exhaustive approach is a valid alternative for a tiny finite problem, but the number of candidate regimes can grow rapidly with the number of stages, states, and actions. Backward induction avoids listing all full regimes: it reuses the optimal continuation value at each state. A forward greedy rule that maximizes immediate reward is not an equivalent alternative, because it ignores future states. A direct optimization over complete regimes is also possible, but the Bellman recursion exposes how each stage’s decision contributes to the global optimum.
The theorem has limits. If the state omits information needed to predict future rewards or transitions, the conditional recursion may not represent the actual problem. If an action maximum is not attained, the best available action may only approach the supremum, and an optimal regime need not exist. If the transition or reward law changes with unrepresented history, the Q-functions are not the stated stage-and-state summaries. Finally, this is a population-value result for the specified decision process: it does not by itself establish that estimated Q-functions or a regime chosen from data have the same optimality property.
A common mistake is to conclude that backward induction proves a regime optimal merely because each stage appears to use a maximum. The proof requires the maximum to be taken over the Q-function that includes the optimal future value. Maximizing an immediate-reward model, or a Q-function built with an incorrect continuation value, does not satisfy the theorem’s premise. The correction is to derive the recursion from the terminal stage backward and verify the reward-plus-continuation calculation at each stage.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- Why does the Q-function include a continuation value rather than just the current expected reward?
- At a stage, an arbitrary regime chooses action \(a\). Which two inequalities establish that its value cannot exceed the optimal value at that state?
- Two final-stage actions have values 7 and 3. What is the value of choosing the first with probability 0.4 and the second with probability 0.6? Does it exceed the deterministic maximum?
- Name one condition that makes the statewise backward-induction argument invalid or incomplete if it is not addressed.
Solutions. 1. The current action can affect later states and rewards, so its total value includes the expected optimal value of the next state; omitting that term can select the wrong action. 2. The arbitrary action’s Q-value is no larger than the maximum over actions, and its actual continuation under its own later decisions is no larger than the optimal continuation used to define that Q-value. 3. The randomized value is \(0.4(7)+0.6(3)=2.8+1.8=4.6\), which is below the deterministic maximum of 7. 4. Examples include an insufficient state, a missing or nonmeasurable maximizing rule, or a supremum that is not attained.