Uncertainty In Estimated Regime Value

Where Value Uncertainty Enters

In a sequential treatment problem, an estimated Q-function at one stage helps determine the treatment decision and continuation value used at earlier stages. Its estimation error can therefore affect more than the decision made at that stage: it can also propagate backward through the value calculation. To quantify this propagation, it is useful to separate two sources of uncertainty: error in the fitted stage-specific Q-functions, and error from averaging a fitted baseline value function over a finite sample.

Consider a finite-horizon problem with stages $t=1,\ldots,K$. Let $H_t$ denote the observed history immediately before treatment $A_t$, and suppose the available treatment set $\mathcal A_t$ is finite. Let $Y$ be the terminal outcome. The regime value is defined for a target baseline distribution $P_0$. For a causal interpretation, consistency, sequential exchangeability, and positivity must identify the relevant conditional outcome distributions; the calculations below concern uncertainty once those distributions, and hence the target Q-functions, are identified.

Definition: Set $V_{K+1}=Y$. For $t=K,\ldots,1$, define $$ Q_t(h,a)=E[V_{t+1}\mid H_t=h,A_t=a], \qquad V_t(h)=\max_{a\in\mathcal A_t} Q_t(h,a). $$ The optimal-regime value is $V=P_0 V_1=E_{P_0}[V_1(H_1)]$. A fitted backward recursion uses $\hat V_{K+1}=Y$, fitted functions $\hat Q_t$, and $\hat V_t(h)=\max_{a\in\mathcal A_t}\hat Q_t(h,a)$. Its population plug-in value is $P_0\hat V_1$; its empirical plug-in value is $P_n\hat V_1=n^{-1}\sum_{i=1}^n\hat V_1(H_{1i})$.

The distinction between the two plug-in values matters. A bound on the fitted value function relative to $V_1$ controls $P_0\hat V_1-P_0V_1$. It does not, by itself, control the additional difference between $P_n\hat V_1$ and $P_0\hat V_1$.

A Backward Error Bound

To express stage-specific fitting error, measure each fitted Q-function against the conditional expectation of the fitted continuation value. For $t<K$, define the residual $r_t(h,a)=\hat Q_t(h,a)-E[\hat V_{t+1}(H_{t+1})\mid H_t=h,A_t=a]$. At the last stage, define $r_K(h,a)=\hat Q_K(h,a)-E[Y\mid H_K=h,A_K=a]$. Suppose, on an event of interest, that $|r_t(h,a)|\leq\eta_t$ for every relevant history and treatment at stage $t$. These are uniform bounds; a bound holding only on average needs a different argument.

Theorem: Suppose the treatment sets are finite, the conditional expectations in the Bellman recursions exist, and the residual bounds above hold uniformly on the histories under consideration. Then, for every stage $t$, $$ \sup_h |\hat V_t(h)-V_t(h)| \leq \sum_{s=t}^{K}\eta_s. $$ In particular, if $P_0\hat V_1$ is finite, then $$ |P_0\hat V_1-P_0V_1| \leq \sum_{s=1}^{K}\eta_s. $$

Proof. For any two finite vectors $x=(x_a)$ and $z=(z_a)$, $|\max_a x_a-\max_a z_a|\leq\max_a|x_a-z_a|$: each coordinate of $x$ is at most the corresponding coordinate of $z$ plus $\max_a|x_a-z_a|$, and reversing $x,z$ gives the other direction. At stage $t$, the residual definition and the true Bellman recursion therefore give $$ |\hat V_t(h)-V_t(h)| \leq \max_{a\in\mathcal A_t} \left\{\eta_t+ \left|E[\hat V_{t+1}-V_{t+1}\mid h,a]\right|\right\} \leq \eta_t+\sup_{h'}|\hat V_{t+1}(h')-V_{t+1}(h')|. $$ The last inequality follows because the absolute value of a conditional expectation is bounded by the conditional expectation of the absolute value, which is at most the uniform supremum. At stage $K+1$, $\hat V_{K+1}=V_{K+1}=Y$, so the error is zero. Applying the displayed inequality backward from $K$ proves the stagewise bound. Finally, $|P_0(\hat V_1-V_1)|\leq P_0|\hat V_1-V_1|\leq\sup_h|\hat V_1(h)-V_1(h)|$, proving the population-value bound. $\square$

This result adds worst-case stage errors. It does not assert that they add in a typical sample, nor that the bound is sharp: errors can cancel after conditional averaging. If the fitted Q-functions are instead compared directly with the true optimal Q-functions, those direct errors already include whatever continuation error entered their construction. The residual formulation makes the backward propagation explicit and avoids counting that same error twice.

Worked Example: A Two-Stage Uniform Error Bound

Suppose $K=2$, with residual bounds $\eta_1=0.15$ and $\eta_2=0.20$. The theorem gives $\sup_h|\hat V_1(h)-V_1(h)|\leq0.35$, and hence $|P_0\hat V_1-P_0V_1|\leq0.35$. If the fitted value averaged over the fixed target baseline distribution is 8.40, then the true population value lies in $[8.05,8.75]$.

That interval is a statement about $P_0\hat V_1$, not automatically about $P_n\hat V_1$. For example, if the empirical baseline average is 8.40 but its difference from the population average is 0.30, then the triangle inequality gives only $|P_n\hat V_1-P_0V_1|\leq0.30+0.35=0.65$. The resulting interval from these two bounds is $[7.75,9.05]$. The extra 0.30 is not implied by the Q-function residual bounds; it must be controlled separately.

How Stage Errors Average Through a Recursion

Worked Example: Conditional Averaging Can Reduce the Actual Error

There are two stages. At stage 2, the state $X$ is either 0 or 1. The true terminal conditional means for the two stage-2 treatments are $Q_2(0,0)=4,\ Q_2(0,1)=3,\ Q_2(1,0)=2,\ Q_2(1,1)=5$. Thus $V_2(0)=4$ and $V_2(1)=5$. Suppose the fitted stage-2 values are $4.10,3.00,2.00,4.80$, in the same order. The fitted maximizing treatments remain 0 at $X=0$ and 1 at $X=1$, so $\hat V_2(0)=4.10$ and $\hat V_2(1)=4.80$. Their errors are $0.10$ and $-0.20$, both within $\eta_2=0.20$.

At stage 1 there are treatments $L$ and $R$. Under $L$, $P(X=0\mid A_1=L)=0.5$; under $R$, $P(X=0\mid A_1=R)=0.8$. The true continuation means are $Q_1(L)=0.5(4)+0.5(5)=4.50$ and $Q_1(R)=0.8(4)+0.2(5)=4.20$. Using the fitted stage-2 values, the continuation means are $4.45$ under $L$ and $4.24$ under $R$. Suppose the stage-1 fitting residuals are $r_1(L)=0.05$ and $r_1(R)=-0.03$. Then $\hat Q_1(L)=4.50$, $\hat Q_1(R)=4.21$, and the fitted optimal first treatment remains $L$.

The stage-1 residual bound is $\eta_1=0.05$. The theorem guarantees a stage-1 value error no larger than $0.05+0.20=0.25$. In this calculation the actual error is zero: $\hat V_1=4.50=V_1$. The stage-2 errors partially cancel when averaged under $L$, and the stage-1 residual then offsets the remaining difference. The bound remains valid but is deliberately conservative.

Sampling Uncertainty in the Baseline Average

When the same data are used to fit $\hat V_1$ and to calculate $P_n\hat V_1$, the empirical average is generally dependent on the fitted function. A simple concentration bound conditional on a fixed fitted function is not justified without addressing this dependence. An independent evaluation sample provides one clean way to separate the two errors.

Theorem: Let $\hat V_1$ be fitted using training data, and let $H_{11},\ldots,H_{1m}$ be an independent evaluation sample from $P_0$. Conditional on the training data, suppose $\hat V_1(H_1)$ lies in an interval of width at most $R$ almost surely. For $\tilde V=m^{-1}\sum_{i=1}^m\hat V_1(H_{1i})$, with probability at least $1-\delta$, $$ |\tilde V-P_0V_1| \leq \sup_h|\hat V_1(h)-V_1(h)| +R\sqrt{\frac{\log(2/\delta)}{2m}}. $$ If the residual bounds in the preceding theorem hold, the first term can be replaced by $\sum_{t=1}^K\eta_t$.

Proof. Decompose the error as $\tilde V-P_0V_1=(\tilde V-P_0\hat V_1)+P_0(\hat V_1-V_1)$. The absolute value of the second term is at most $\sup_h|\hat V_1(h)-V_1(h)|$. Conditional on the training data, the evaluation observations are independent and identically distributed, and each $\hat V_1(H_{1i})$ lies in an interval of width $R$. Hoeffding's inequality gives $P(|\tilde V-P_0\hat V_1|>u\mid\text{training})\leq2\exp(-2mu^2/R^2)$. Taking $u=R\sqrt{\log(2/\delta)/(2m)}$ makes this probability at most $\delta$. Combining the two bounds proves the claim. $\square$

This result illustrates why uncertainty statements should name their target and their sampling scheme. Independent evaluation supports the stated conditional concentration argument. With an in-sample average, dependence must be handled by an appropriate empirical-process argument, sample splitting, or another justified inference procedure; the Q-function error bound alone does not supply it.

Worked Example: Adding a Baseline Evaluation Bound

Suppose the two-stage residual bounds sum to $0.35$, and an independently sampled baseline evaluation set has size $m=200$. Assume the fitted values lie in an interval of width $R=10$. For a 95% bound, take $\delta=0.05$. The Hoeffding term is $$ 10\sqrt{\frac{\log(40)}{400}} =10\sqrt{\frac{3.6889}{400}} \approx 10(0.0960)=0.960. $$ Therefore the displayed theorem gives a total error bound of $0.35+0.960=1.310$, with probability at least 0.95. This bound may be conservative, particularly because Hoeffding uses only the range and not the variance. It nevertheless controls both the fitted-value error and the finite evaluation-sample error, unlike a Q-function bound alone.

Variance Propagation When Decisions Are Stable

A worst-case bound is not a standard error. For a variance calculation, one useful special case is that the maximizing treatment at each relevant history remains unchanged under small estimation perturbations. A strict gap between the largest and second-largest true Q-values helps ensure local stability, but random estimation errors must also be small enough that the gap is not crossed. Near ties this smooth approximation may fail; the earlier material on nonregular inference near treatment ties addresses that issue.

Worked Example: Correlated Sources of Value Uncertainty

Suppose the first-stage optimal treatment has a true advantage of 2 over its competitor, and the fitted perturbations are small enough that this choice and the relevant second-stage choices do not change. Under the selected first treatment, $P(X=0)=0.25$ and $P(X=1)=0.75$. Let $U_1$ be the stage-1 fitting error, and let $U_{20},U_{21}$ be the stage-2 fitted-value errors at states 0 and 1. In this stable-decision region, the value error is $\Delta=U_1+0.25U_{20}+0.75U_{21}$.

Assume the errors have mean zero, are mutually independent, and have variances $0.04,\ 0.09,\ 0.16$, respectively. Then $$ \operatorname{Var}(\Delta) =0.04+(0.25)^2(0.09)+(0.75)^2(0.16) =0.04+0.005625+0.09 =0.135625. $$ The standard deviation is $\sqrt{0.135625}\approx0.3683$. If the stage-1 error and stage-2 errors are correlated, covariance terms must be added; for example, the contribution of $U_1$ and $U_{20}$ is $2(0.25)\operatorname{Cov}(U_1,U_{20})$. The independence calculation is not a general formula for Q-learning; it shows explicitly how stage errors are weighted and why their dependence matters.

Diagnostics, Alternatives, and Limits

A useful uncertainty report distinguishes the error components rather than compressing them into one unexplained interval. Examine stage-specific prediction errors or uncertainty estimates, inspect whether fitted action gaps are small, and assess how sensitive the earlier-stage fitted values are to plausible changes in later-stage predictions. Large residuals at a late stage can affect several earlier values; apparent stability of the final average does not prove that each stage is well estimated.

Uniform bounds versus average errors. The backward theorem uses a supremum bound. A small mean squared prediction error does not establish that bound, especially when rare histories have large errors.
Decision changes. A value function can be stable while the maximizing treatment changes, and a smooth variance approximation can fail near ties. Do not infer stable treatment decisions from a small value error bound.
Baseline sampling. An empirical average adds sampling error. State whether the value is averaged over a fixed target distribution or an estimated empirical distribution, and justify any uncertainty bound for the latter.
Model and identification limits. The calculations do not repair misspecified conditional models, violations of causal identification assumptions, poor support, or an ill-defined target population. The value being quantified must first be identified and clearly specified.

The main alternatives answer different questions. A backward error bound gives a transparent worst-case guarantee when credible stagewise residual bounds are available. A variance or influence-function calculation can give more informative uncertainty under regularity conditions, including stable maximizing decisions and justified asymptotic approximations. Resampling can reflect fitting variability, but it must repeat the relevant fitting and selection steps and may not resolve nonregular behavior near ties. Independent evaluation or sample splitting separates fitting from baseline averaging, at the cost of using fewer observations for each task.

Common mistake: “The recursive Q-function error is at most 0.35, so an empirical plug-in estimate of 8.40 guarantees that the true value lies between 8.05 and 8.75.” This conclusion silently treats an empirical average as a population average. The bound only places $P_0\hat V_1$ within 0.35 of $P_0V_1$. To make a statement about an empirical plug-in value, add a valid bound for $|P_n\hat V_1-P_0\hat V_1|$, or explicitly report the result as applying to the population average of the fitted function.

Check Your Understanding

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

For three stages with residual bounds $0.10,\ 0.20,\ 0.05$, what bound does the theorem give for the population plug-in value error?
Why does that bound alone not guarantee that an empirical plug-in value is within the same distance of the true population value?
In the stable-decision example, what is the variance contribution from state 1 if its value-error variance is $0.16$ and its probability is $0.75$?
Name two conditions needed for the independent-evaluation Hoeffding bound stated here.

Solutions: (1) Add the stage bounds: $0.10+0.20+0.05=0.35$. (2) The theorem controls $|P_0\hat V_1-P_0V_1|$, not the separate sampling difference $|P_n\hat V_1-P_0\hat V_1|$; that difference needs its own bound. (3) The contribution is the squared probability weight times the variance: $(0.75)^2(0.16)=0.09$. (4) The evaluation observations must be independent draws from $P_0$ and independent of the training data used to fit $\hat V_1$; additionally, the fitted values must be bounded within an interval of known width $R$ for the stated Hoeffding bound.