The Bellman Optimality Principle

Why an Optimal Decision Must Look Ahead

A treatment decision can produce an immediate benefit while also changing a patient’s later health state, the options available at the next decision, or both. Choosing the action with the largest immediate reward can therefore lead to a worse overall outcome. The Bellman optimality principle formalizes the alternative: at a given state, compare actions by combining their current expected reward with the value of the best continuation they make possible.

The earlier material on value functions for treatment regimes supplies the basic idea of evaluating a regime by its expected total reward. Here the focus is the optimality principle that connects a best total value to local decisions. The setting below is finite-horizon so that existence and finiteness do not depend on unstated infinite-horizon assumptions.

Definition: Consider decision times $t=1,\ldots,T$, a finite state set $\mathcal S_t$ at each time, and a nonempty finite feasible action set $\mathcal A_t(s)$ for each state $s$. A policy $\pi$ specifies an action at each time and state. Assume the controlled process is Markov: conditional on the current state $S_t=s$ and action $A_t=a$, the conditional distribution of the next state and reward does not depend on earlier history. Write $r_t(s,a)=E[R_t\mid S_t=s,A_t=a]$ and $P_t(s'\mid s,a)=P(S_{t+1}=s'\mid S_t=s,A_t=a)$. Let $G(S_{T+1})$ be a terminal reward. The value of a policy from state $s$ at time $t$ is $$ J_t^\pi(s)=E_\pi\left[\sum_{k=t}^{T}R_k+G(S_{T+1})\mid S_t=s\right], $$ and the optimal value is $V_t^*(s)=\max_\pi J_t^\pi(s)$, when the maximum exists.

Rewards and terminal rewards are assumed to have finite expectations. In this finite setting, one can impose the simpler sufficient condition that they are bounded. A policy may depend on time as well as state; “optimal” always means maximizing the expected total reward from the state and time in question, not merely maximizing the next reward.

The Principle and Its Local Meaning

Theorem: Under the finite-horizon, finite-state, finite-action, and Markov assumptions above, an optimal policy exists. For every time $t$ and state $s$, its value satisfies $$ V_t^*(s)=\max_{a\in\mathcal A_t(s)} \left\{r_t(s,a)+\sum_{s'\in\mathcal S_{t+1}}P_t(s'\mid s,a)V_{t+1}^*(s')\right\}, $$ where $V_{T+1}^*(s)=G(s)$. An action attaining this maximum is optimal at $(t,s)$. An optimal policy can be formed by choosing a maximizing action at every time and state.

The expression inside the maximum has two parts. The first is the expected reward for acting now. The second averages the optimal future value over the states that may follow. The best action is not necessarily the one with the largest first part: it is the one with the largest sum.

The finite assumptions matter. Since there are finitely many actions at each state, a maximum over actions is attained. With a finite horizon, bounded rewards imply a finite total reward. More generally, the proof needs finite expectations and attainable optimal continuations. If maxima are not attained in a broader setting, the corresponding statement must use suprema, and it may describe actions that approach the best value without any action achieving it.

Why the Principle Holds

The key argument is that a continuation that is not optimal can be replaced by a better one. For completeness, existence and the value identity follow by backward induction.

Start at the end.
At time $T+1$, no decisions remain, so $V_{T+1}^*(s)=G(s)$. This value is attained because there is no further choice.

Fix a state and first action.
At time $t$, after choosing action $a$ in state $s$, the expected immediate reward is $r_t(s,a)$. Conditional on next state $s'$, the best remaining expected reward is $V_{t+1}^*(s')$. Averaging over the transition distribution gives the displayed sum.

Choose the best first action.
There are finitely many feasible actions, so the largest of their current-plus-future values is attained. Choose an action attaining it, then use an optimal continuation at each possible next state. By the induction hypothesis those continuations exist.

Rule out a better policy.
Any policy must take some feasible first action, and its continuation after each next state cannot exceed that state’s optimal value. Its total expected reward is therefore no greater than the maximum in the theorem. The constructed policy attains that maximum, proving the identity and existence.

This argument also gives the principle its operational interpretation: an optimal plan must remain optimal after the first decision, conditional on the state that follows. If a continuation at some state could be replaced by one with greater value, the replacement would improve the whole plan whenever that state can occur with positive probability.

The identity is often developed as a time-by-time computational recursion. The important point here is the principle behind that calculation: when the state captures the information relevant to future rewards and transitions, an optimal future plan can be attached to the state reached after the current action. If the recorded “state” omits information that changes future outcomes or feasible actions, this argument may fail; the state representation must then be expanded.

Worked Examples

Worked Example: A Lower Immediate Reward Can Win

At a decision time, a patient is in state $s$. There are two treatment actions. Action $A$ gives an immediate expected reward of $6$, then leads with certainty to a state whose optimal future value is $2$. Action $B$ gives an immediate expected reward of $3$, then leads with probability $0.8$ to a state with optimal future value $10$, and with probability $0.2$ to a state with value $0$. Which action is optimal?

For action $A$, current reward plus optimal future value is $$ 6+1(2)=8. $$ For action $B$, it is $$ 3+\{0.8(10)+0.2(0)\}=3+8=11. $$ Therefore action $B$ is optimal, even though its immediate expected reward is $3$, less than the $6$ from action $A$. Its better distribution over future states more than compensates for the smaller current reward.

Worked Example: Comparing Two Actions Through Their Continuations

Suppose the next decision is the last one, and its optimal values are $V^*(X)=8$ and $V^*(Y)=0$. At the current state, action $C$ gives reward $1$ and leads to $X$ with probability $0.8$. Action $D$ gives reward $5$ and leads to $X$ with probability $0.2$. The remaining probability in each case leads to $Y$. Find the preferred action.

The probability of $Y$ is $0.2$ after $C$ and $0.8$ after $D$. Thus $$ \begin{aligned} \text{value of }C &=1+\{0.8(8)+0.2(0)\}=1+6.4=7.4,\\ \text{value of }D &=5+\{0.2(8)+0.8(0)\}=5+1.6=6.6. \end{aligned} $$ Choose $C$, because $7.4>6.6$. Although $D$ has the greater immediate reward, $C$ makes the more valuable continuation sufficiently likely.

Worked Example: Tied Actions and Non-Unique Optimal Policies

At a state $s$, action $A$ gives immediate reward $4$ and leads to a next state with optimal value $3$. Action $B$ gives immediate reward $5$ and leads to a next state with optimal value $2$. Both transitions occur with certainty. Compare the actions.

The total values are $4+3=7$ for $A$ and $5+2=7$ for $B$. Hence both actions attain the maximum, and either can be used by an optimal policy at $s$. The Bellman principle does not imply that the optimal action is unique. If a later decision requires a single regime, a tie-breaking rule may select one maximizer, but that rule does not make the other action suboptimal.

Interpretation, Alternatives, and Diagnostics

The principle differs from evaluating a fixed treatment regime. Evaluation asks what expected reward a specified policy would produce; optimality compares feasible first actions while allowing each to be followed by its best continuation. It also differs from a greedy rule, which ranks actions by immediate reward alone. A greedy rule is justified only under additional structure that makes future value irrelevant to the ranking, not by the Bellman principle itself.

When the state and action sets are small, one alternative is to enumerate all possible policies and compare their values. This can verify a solution, but the number of complete policies can grow rapidly across decision times and states. The Bellman principle is useful because it permits comparisons locally, reusing optimal continuation values rather than treating every full sequence of decisions as unrelated.

Several checks help detect a mistaken application:

Check both parts of the comparison. If an action is selected solely because its immediate reward is largest, future value may have been omitted.
Check transition probabilities. For each state and action, probabilities over next states must be nonnegative and sum to $1$.
Check the state description. If past information changes the distribution of future outcomes or the actions available, a state containing only the current label may not be sufficient.
Check existence and finiteness. A maximum requires an attaining action; finite total value requires suitable reward and horizon conditions. These are separate questions.
Check ties. Equal current-plus-future values mean multiple actions can be optimal, even if their immediate rewards differ.

Common pitfall: “Rewards are bounded and there are finitely many states and actions, so the expected total reward is finite and a maximizing action exists.” This is not valid for an unspecified infinite horizon. With one state, one action, and reward $1$ at every time, the infinite total is infinite despite bounded rewards and finite state and action sets. A finite horizon avoids this issue. For an infinite horizon, a common sufficient setup is bounded rewards and a discount factor strictly less than $1$, together with conditions ensuring an optimal action or policy exists. In finite-state, finite-action discounted problems, the discounted Bellman operator is a contraction and an optimal stationary policy exists. The finite-horizon result above should not be transferred to an infinite horizon without such conditions.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions.

Action $A$ has immediate reward $8$ and leads to a state with optimal future value $0$. Action $B$ has immediate reward $3$ and leads with probability $0.8$ to a state with value $10$, otherwise to a state with value $0$. Which action is optimal?
Why must the continuation after an action be evaluated at the next state rather than replaced by the continuation that would follow a different next state?
If two actions have the same immediate-plus-future value at a state, what does the principle say about their optimality?
Why does bounded reward not, by itself, guarantee a finite total reward over an infinite horizon?

Solutions. (1) Action $A$ is worth $8+0=8$. Action $B$ is worth $3+\{0.8(10)+0.2(0)\}=11$, so choose $B$. (2) Future value depends on the state actually reached; the expectation must weight each state’s optimal value by its transition probability. (3) Both actions attain the maximum and are optimal; the best action need not be unique. (4) A bounded reward can recur without end. If the reward is $1$ at every time, the partial sum through time $m$ is $m$, which increases without bound as $m$ increases.