Why a Finite-Horizon Recursion Is Useful
With several treatment decisions, an early action can affect both the reward received now and the covariates that will be observed before later decisions. The optimization must account for both effects. A finite-horizon Bellman recursion does this by starting at the last decision, where there is no future treatment value to calculate, and working backward one stage at a time. The earlier material on the Bellman optimality principle motivates this backward approach; here the goal is to write and derive the recursion precisely, including intermediate rewards.
Consider \(K\) treatment stages. At stage \(t\), the history \(H_t\) is observed, an action \(A_t\) is taken, and a reward \(R_t\) is accrued. Before the next treatment decision, new covariates \(L_{t+1}\) may be observed. For \(t<K\), write \(H_{t+1}=(H_t,A_t,L_{t+1})\). The terminal reward \(R_K\) is observed after the final action. A policy \(g=(g_1,\ldots,g_K)\) specifies an action \(g_t(H_t)\) at each stage.
The conditional expectations below are under the treatment action specified at the current stage and the future actions prescribed by the policy being evaluated. A history is evaluated only where the relevant conditional distributions and action choices are defined. In the finite-action setting, the maximum is over the feasible actions at that history.
Assumptions for a Causal Recursion
A recursion can be written mathematically for any specified transition law. To interpret its value as the expected outcome under interventions on treatment, the observed data must also identify the relevant intervention distributions. The following are standard sufficient conditions.
- Consistency: for a person whose observed treatment sequence agrees with a regime through a given time, the observed covariates and rewards through that time equal the corresponding potential covariates and rewards under that regime.
- Sequential exchangeability: at each stage \(t\), conditional on the observed history \(H_t\), treatment \(A_t\) is independent of the potential future covariates and rewards under the treatment continuations being considered. This rules out unmeasured confounding of treatment at that stage, given \(H_t\).
- Positivity: actions a regime may choose must lie in the conditional support of treatment given the histories where that regime may operate. For a finite action set, a sufficient condition is positive conditional probability for each such action at those histories. For non-discrete actions, the relevant action must be in conditional support; identifying a conditional mean at a particular continuous action can additionally require regularity of that mean.
- Integrability and well-defined histories: the rewards have finite expected absolute sum under the regimes considered, and regular conditional distributions exist. For the simple measurable-selection argument below, assume finite action sets and measurable reward and transition laws.
These assumptions are stated to clarify the causal interpretation, not because the algebraic recursion itself requires treatment assignment to be randomized. Consistency and sequential exchangeability let us replace intervention-specific conditional distributions with observed conditional distributions; positivity ensures the required actions are supported. The recursion is interpreted up to histories reached under the policies in question, with suitable versions of conditional expectations.
The Backward Recursion
For \(t<K\), the expectation integrates over both the current reward and the next history induced by action \(a\). Thus an action can be preferred even if its immediate expected reward is lower, provided it leads to more favorable future histories. In a causal analysis, the conditional law in this expression is identified from observed data under consistency, sequential exchangeability, and positivity.
Set \(V_{K+1}^*=0\), then calculate the final-stage value from the expected terminal reward for each feasible final action.
For each history and each current action, add expected current reward to expected next-stage optimal value.
Take the largest of these action-specific expectations and repeat until stage 1.
The population value is the expectation of the stage-1 optimal value under the baseline distribution.
Derivation and proof. At stage \(K\), after choosing action \(a\), the only remaining reward is \(R_K\). The best conditional expected total reward is therefore the largest conditional mean of \(R_K\), which gives the stated terminal formula.
Now suppose the recursion correctly gives the best attainable conditional expected reward from stage \(t+1\) onward for every relevant next history. At history \(h\), any policy must first choose an action \(a\). Conditional on that action and the resulting next history, its expected remaining reward cannot exceed \(V_{t+1}^*(H_{t+1})\), by the induction hypothesis. Taking the conditional expectation gives the upper bound
The best first action therefore cannot yield more than the maximum in the recursion. Conversely, because the action set is finite, at each history there is an action attaining that maximum. Choose such an action, then at each resulting next history choose an action attaining the recursively defined next-stage maximum. This policy attains the displayed bound. Backward induction proves the recursion at every stage. The maximizers can be chosen measurably under the stated finite-action and measurability conditions, for example by fixing a tie-breaking order. Finally, averaging the conditional stage-1 value over \(H_1\) gives the population value. \(\square\)
Randomizing among actions cannot improve this value. If a randomized choice assigns probabilities \(\pi(a\mid h)\), its conditional expected continuation reward is a weighted average of the action-specific expectations:
The inequality holds because the weights are nonnegative and sum to one. A deterministic maximizing action is therefore at least as good at each history.
Worked Examples
Worked Example: A Terminal Decision
There is one treatment stage. The baseline history \(H_1\) is binary, with \(P(H_1=0)=0.6\) and \(P(H_1=1)=0.4\). Both actions \(A_1=0,1\) are supported at each history. The conditional mean terminal rewards are:
| History | \(E[R_1\mid H_1,A_1=0]\) | \(E[R_1\mid H_1,A_1=1]\) |
|---|---|---|
| 0 | 2 | 5 |
| 1 | 6 | 4 |
There is no continuation after stage 1, so \(V_2^*=0\). At \(H_1=0\), \(V_1^*(0)=\max(2,5)=5\), attained by action 1. At \(H_1=1\), \(V_1^*(1)=\max(6,4)=6\), attained by action 0. The optimal policy therefore uses different actions for the two histories. Its population value is
For comparison, always choosing action 1 has value \(0.6(5)+0.4(4)=4.6\), and always choosing action 0 has value \(0.6(2)+0.4(6)=3.6\). Both are below 5.4.
Worked Example: An Intermediate Reward Changes the First Choice
There are two stages and a single stage-1 history. At stage 2, a binary state \(L_2\) is observed. The stage-2 terminal reward has the following conditional means:
| \(L_2\) | Mean reward if \(A_2=0\) | Mean reward if \(A_2=1\) | \(V_2^*(L_2)\) |
|---|---|---|---|
| 0 | 3 | 5 | 5 |
| 1 | 7 | 4 | 7 |
At stage 2, choose action 1 when \(L_2=0\), since \(5>3\), and choose action 0 when \(L_2=1\), since \(7>4\). Thus the continuation value is 5 at state 0 and 7 at state 1.
At stage 1, action 0 yields immediate reward 1 and has \(P(L_2=1\mid A_1=0)=0.25\). Its total expected reward under the optimal stage-2 decisions is \(1+0.75(5)+0.25(7)=1+3.75+1.75=6.5\). Action 1 yields immediate reward 0 and has \(P(L_2=1\mid A_1=1)=0.8\). Its total is \(0+0.2(5)+0.8(7)=1+5.6=6.6\). The recursion therefore selects action 1 at stage 1, even though it gives a smaller immediate reward. Its advantage comes from the distribution of the later state.
Worked Example: Three Stages with Rewards at Every Stage
At stage 3, the terminal reward means are 2 and 3 for actions 0 and 1 when \(L_3=0\), and 8 and 6 when \(L_3=1\). Hence \(V_3^*(0)=3\) and \(V_3^*(1)=8\).
At stage 2, the observed state is \(L_2\). If \(L_2=0\), action 0 gives immediate reward 1 and \(P(L_3=1)=0.25\); its total is \(1+0.75(3)+0.25(8)=5.25\). Action 1 gives immediate reward 0 and \(P(L_3=1)=0.8\); its total is \(0+0.2(3)+0.8(8)=7\). Thus \(V_2^*(0)=7\).
If \(L_2=1\), action 0 gives immediate reward 2 and \(P(L_3=1)=0.5\), for a total of \(2+0.5(3)+0.5(8)=7.5\). Action 1 gives immediate reward 1 and \(P(L_3=1)=0.9\), for a total of \(1+0.1(3)+0.9(8)=8.5\). Thus \(V_2^*(1)=8.5\).
Finally, at stage 1, action 0 gives immediate reward 0 and has \(P(L_2=1)=0.2\). Its total is \(0+0.8(7)+0.2(8.5)=5.6+1.7=7.3\). Action 1 gives immediate reward 1 and has \(P(L_2=1)=0.75\). Its total is \(1+0.25(7)+0.75(8.5)=1+1.75+6.375=9.125\). The optimal first action is 1, and the optimal population value for this fixed initial history is 9.125.
Diagnostics, Alternatives, and Limitations
A backward recursion is only as credible as its conditional reward and transition estimates. Check that each stage uses the history available before its treatment decision, that the next history is generated under the action being evaluated, and that intermediate rewards are added exactly once. In computation, compare the final-stage values to direct conditional outcome means and verify each earlier-stage calculation by substituting the estimated transition probabilities and next-stage values.
Support deserves particular care. Positivity fails when a policy may choose an action with zero conditional probability, or an action outside the relevant conditional support, at a history where that policy may operate. By contrast, an action not observed at one particular history in a finite sample does not by itself establish a population positivity failure. Sparse observations may signal unstable estimation or difficulty learning the conditional law; they are a diagnostic concern, not proof that the population probability is zero. With continuous histories, exact repeated observations at one history are generally not expected even when the treatment probability is positive.
The main alternatives serve different purposes. Evaluating a prespecified regime by the longitudinal g-formula propagates its specified actions forward; it does not, by itself, maximize over actions. Exhaustive enumeration can find the best policy when there are few stages, histories, and actions, but the number of possible action sequences grows rapidly. The recursion reuses stage-specific conditional calculations and is especially natural when future decisions can be optimized separately at each history. These approaches do not remove the need for credible conditional models or causal identification assumptions.
The finite-action assumption makes the maximum and a measurable maximizing choice straightforward. For infinite or continuous action spaces, an optimum may fail to exist; one may instead need compactness and continuity conditions or work with a supremum and approximate policies. Likewise, the optimal value can be well-defined while the estimated maximizing action is unstable when two actions have nearly equal conditional values. The recursion describes the target optimization; it does not guarantee that finite data estimate every stage well.
Check Your Understanding
Work through the questions, then compare your reasoning with the solutions.
- At a final stage, the conditional mean rewards for actions 0 and 1 are 4 and 4.5. What is the optimal value, and what does a tie-breaking rule change?
- At a two-stage history, action 0 gives immediate reward 2 and continuation value 3 with certainty. Action 1 gives immediate reward 1 and continuation value 6 with certainty. Which action is optimal?
- If a treatment action is absent from a finite sample at one continuous-valued history, has population positivity necessarily failed?
- Why can a randomized mixture of actions not exceed the best action-specific conditional expected continuation reward?
Solutions. (1) The value is \(\max(4,4.5)=4.5\), attained by action 1. A tie-breaking rule matters only if action-specific values are equal; it selects one maximizer without changing the value. (2) Action 0 gives \(2+3=5\), while action 1 gives \(1+6=7\), so action 1 is optimal. (3) No. Finite-sample nonobservation alone does not establish a zero population probability or lack of conditional support; it may indicate sparse data or estimation difficulty. (4) The mixture is a weighted average of the action-specific expectations, with nonnegative weights summing to one. Such an average cannot exceed their maximum.