Regret From Estimated Treatment Rules

Why a Good Q-Function Is Not the Whole Goal

A treatment rule is useful because of the outcomes it can achieve, not because its fitted Q-function looks accurate in isolation. For a given history, a small error in estimated action values may not matter if the best action is clearly separated from the alternatives. The same error can change the selected action when two or more actions have similar values. Regret measures the value lost from that decision error and makes this distinction explicit.

The results below concern a single decision with a finite action set. They apply to a decision stage whose Q-function incorporates the relevant continuation value. In a sequential regime, the Q-function at a stage must be the one appropriate to the decision being evaluated; extending a one-stage bound to total regime regret also requires accounting for how rules affect later histories.

Definition: Let $H$ be a history drawn from a target population, let $\mathcal A$ be a finite action set with at least two actions, and let $Q(h,a)$ be the conditional value of taking action $a$ at history $h$. A rule $d$ maps each history to an action in $\mathcal A$. Its value is $V(d)=E[Q(H,d(H))]$. Define $Q^*(h)=\max_{a\in\mathcal A}Q(h,a)$, and let $d^*$ be any measurable rule that selects an action attaining this maximum. The regret of $d$ is $\mathcal R(d)=V(d^*)-V(d)=E[Q^*(H)-Q(H,d(H))]$.

This definition presumes that the Q-function represents the value relevant to the target population and decision. In a causal analysis, interpreting $V(d)$ as a causal regime value additionally requires the identification conditions appropriate to that analysis. The regret results themselves are mathematical comparisons of rules under the specified $Q$ and distribution of $H$.

Let $\hat Q$ be an estimated Q-function, and let $\hat d$ maximize $\hat Q(h,a)$ over $a$ at each history. To describe how close a history is to a decision boundary, order the true action values at $h$ from largest to smallest, counting tied actions separately. Define the action gap $\Delta(h)$ as the largest value minus the second-largest value. Thus $\Delta(h)=0$ when the best action is tied with another best action. Small gaps identify histories where small perturbations can change which action appears best.

A Basic Bound and Its Proof

The first result gives a worst-case guarantee when the estimated Q-function is uniformly close to the truth. The event in the bound includes zero-gap histories: a tie among the best actions does not rule out selection of a strictly worse action.

Theorem: Suppose $\hat d$ maximizes $\hat Q(h,a)$ over $\mathcal A$ for every $h$, and for some $\delta\geq 0$, $\max_{a\in\mathcal A}|\hat Q(h,a)-Q(h,a)|\leq\delta$ for every history under consideration. Then $$ \mathcal R(\hat d)\leq 2\delta\,P\{\Delta(H)\leq 2\delta\}. $$

Bound the loss at a history.
Fix $h$, and choose any true maximizing action $a^*$. Since $\hat d(h)$ maximizes $\hat Q$, $\hat Q(h,\hat d(h))\geq \hat Q(h,a^*)$. The uniform error bound therefore gives $Q(h,a^*)-Q(h,\hat d(h))\leq 2\delta$.

Locate histories with possible loss.
If $\hat d(h)$ is truly optimal, the loss is zero. If it is suboptimal, the second-largest true action value is at least $Q(h,\hat d(h))$, so $\Delta(h)\leq Q(h,a^*)-Q(h,\hat d(h))\leq 2\delta$.

Take expectations.
Pointwise, the loss is at most $2\delta\,\mathbf 1\{\Delta(h)\leq2\delta\}$. Taking expectations under the target distribution of $H$ yields the stated bound. $\square$

The theorem is a deterministic implication conditional on the stated uniform error event. If $\hat Q$ is random, the same conclusion holds on the event that its error is bounded by $\delta$; a probability statement about regret then also needs a probability bound for that event. The theorem does not require a unique optimal action.

Worked Example: A Tie Can Still Produce Regret

At one history, suppose three actions have true values $(1,1,0.9)$, while the estimated values are $(0.9,0.9,1.0)$. The largest absolute error is $\delta=0.1$, and the estimated rule selects the third action.

The true best value is $1$, so the selected action incurs regret $1-0.9=0.1$. The largest and second-largest true values are both $1$, giving $\Delta=0$. Thus $P\{\Delta\leq2\delta\}=1$ in this one-history example, and the bound gives $0.1\leq 2(0.1)(1)=0.2$, as required.

A bound using only $P\{0<\Delta\leq2\delta\}$ would give zero here and would be false. Having a tie between optimal actions does not prevent the estimated rule from selecting an action below both of them.

Margin Conditions and Faster Regret Bounds

A uniform error bound alone gives $\mathcal R(\hat d)\leq2\delta$. The action-gap result can be sharper when histories close to a decision boundary are uncommon. A common formalization is an action-gap margin condition: for constants $C>0$ and $\alpha>0$, assume

P\{\Delta(H)\leq t\}\leq Ct^\alpha \quad\text{for all }t>0\text{ in the range of interest.}

Combining this condition with the theorem, for $2\delta$ in that range,

\mathcal R(\hat d)\leq 2\delta\,C(2\delta)^\alpha = C\,2^{\alpha+1}\delta^{\alpha+1}.

This is a faster power of $\delta$ than the generic linear bound when $\alpha>0$. The condition is imposed on $P\{\Delta(H)\leq t\}$, not just on $P\{0<\Delta(H)\leq t\}$. In fact, if it holds for all $t>0$ with $\alpha>0$, then $P\{\Delta(H)=0\}=0$: the events $\{\Delta(H)\leq1/k\}$ decrease to $\{\Delta(H)=0\}$, and their probabilities are bounded above by $Ck^{-\alpha}$, which tends to zero. If ties have positive probability, this particular margin condition cannot hold as $t$ approaches zero.

Worked Example: A Threshold Rule With Few Near-Boundary Histories

Let $X$ be uniform on $[-1,1]$, with actions $0$ and $1$. Set $Q(x,0)=0$ and $Q(x,1)=x$. The optimal rule chooses action $1$ when $x>0$ and action $0$ when $x<0$. The gap is $\Delta(x)=|x|$.

Suppose the estimated values are $\hat Q(x,0)=0$ and $\hat Q(x,1)=x-\varepsilon$, where $0<\varepsilon\leq1$. The maximum Q-function error is $\delta=\varepsilon$. The estimated rule chooses action $0$ unless $x>\varepsilon$; consequently, it loses value only for $0<x<\varepsilon$.

Since the density of $X$ is $1/2$, the regret is $E[X\mathbf 1\{0<X<\varepsilon\}]=\int_0^\varepsilon x(1/2)\,dx=\varepsilon^2/4$. For $0\leq t\leq1$, $P\{\Delta(X)\leq t\}=P\{|X|\leq t\}=t$, so the margin condition holds with $C=1$ and $\alpha=1$ in that range. The bound at $2\varepsilon\leq1$ is $2\varepsilon(2\varepsilon)=4\varepsilon^2$, which is valid but conservative relative to the exact regret $\varepsilon^2/4$.

The example shows why regret can be small even when a rule disagrees with the optimal rule for some histories. The disagreement occurs only in a narrow interval where the two actions have nearly equal values, so the loss per affected history is also small.

Beyond a Uniform Error Bound

Uniform error control can be demanding, particularly when the history space is large. A useful alternative bound needs only integrability of the largest pointwise Q-function error. Let $e(h)=\max_{a\in\mathcal A}|\hat Q(h,a)-Q(h,a)|$. The same maximizing argument used in the theorem gives

Result: If $\hat d$ maximizes $\hat Q$ pointwise and $E[e(H)]<\infty$, then $\mathcal R(\hat d)\leq2E[e(H)]$.

Indeed, for each history, $Q(h,a^*)-Q(h,\hat d(h))\leq2e(h)$, where $a^*$ is a true maximizing action. Taking expectations proves the result. This bound does not exploit the distribution of the action gap, but it can be informative when a global supremum bound is unavailable. In applications, an estimated error measure is not automatically a bound on $e(H)$; uncertainty assessment or other justification is needed before treating it as one.

Regret should also be distinguished from decision agreement. A rule can disagree with an optimal rule on histories of positive probability and still have small regret if the competing actions are nearly tied there. Conversely, a small average Q-function error does not by itself guarantee exact agreement of decisions: even tiny perturbations can reverse rankings at ties. This is the distinction between value consistency and decision consistency.

Diagnostics, Comparisons, and Limitations

In practice, the action gap is usually unknown because it depends on the true Q-function. Diagnostics therefore cannot certify the margin condition simply by inspecting fitted values. They can, however, reveal where a proposed rule may be fragile and where additional estimation accuracy matters most.

Inspect fitted gaps. For each history, compare the largest and second-largest fitted action values. A concentration of small fitted gaps flags histories where modest changes in the model or data could alter the rule.
Check ranking stability. Refit under reasonable modeling choices or resampling perturbations and compare actions selected at the same histories. Frequent switching suggests that decisions are weakly separated, though stability alone does not prove small regret.
Check coverage of actions and histories. Sparse data in a region can make estimated action values unreliable there. A visually large fitted gap is not reassuring if the Q estimates are poorly supported.
Separate value from classification. Report both the rule's estimated value and, where relevant, how often its decisions change across analyses. Neither quantity alone establishes the other.

Alternative summaries answer different questions. The uniform-error bound is simple and yields a direct worst-case guarantee, but may be loose. The expected-error bound avoids requiring a supremum but does not use the boundary structure. A margin-based bound can sharpen rates when near-tie histories are sufficiently rare, but depends on a distributional assumption that may fail, especially when exact ties occur with positive probability. In finite samples, estimated margins are not a substitute for a justified condition on the true gap distribution.

These bounds are guarantees about value under the specified target distribution and Q-function. They do not establish that the Q-model is correctly specified, that causal identification assumptions hold, or that the estimated rule will transport to a different population. In a multistage regime, a local decision improvement can change the distribution of later histories; total regret must be evaluated with the sequential value structure rather than by mechanically applying a single-stage probability bound to every stage.

Common pitfall: Excluding $\Delta=0$ from the near-boundary event can make a regret bound false. Ties among the best actions do not imply every action is optimal. Use $P\{\Delta(H)\leq2\delta\}$, including zero, unless you separately assume that the estimated rule selects an optimal action at every tied history or that ties have probability zero.

Worked Example: A General Error Bound Without a Margin Assumption

Suppose there are two actions and a particular history has true values $Q(h,0)=4.0$ and $Q(h,1)=3.7$. If the estimated rule selects action $1$, its loss at this history is $4.0-3.7=0.3$. The gap is $\Delta(h)=0.3$, so the theorem implies that any uniform error bound capable of allowing this mistake must have $2\delta\geq0.3$, or $\delta\geq0.15$.

For example, if $\delta=0.10$, the theorem says a mistaken choice is impossible at this history because $\Delta(h)=0.3>2\delta=0.2$. Directly, the estimated value of the inferior action can be at most $3.8$, while that of the better action can be at least $3.9$; hence the inferior action cannot maximize $\hat Q$. This is a local guarantee and requires no assumption about how often other histories have small gaps.

Check Your Understanding

Answer each question, then compare with the solutions below.

With two actions, the true values at a history are $2.0$ and $1.8$. Can a rule maximizing an estimated Q-function with uniform error at most $0.05$ select the inferior action? Explain.
Why must a general gap-based regret bound include histories where $\Delta(H)=0$?
If $P\{\Delta(H)\leq t\}\leq 3t^2$ and a uniform Q-function error bound is $\delta=0.1$, what regret bound follows, assuming $2\delta$ is in the stated range?
Does a low regret guarantee imply that the estimated rule agrees with an optimal rule at almost every history? Explain.

Solutions. (1) No. The gap is $0.2$, while $2\delta=0.1$. The theorem's pointwise argument rules out selecting the inferior action. (2) At a tied history, the estimated rule can select an action that is strictly below the tied best actions; this can incur positive regret even though the gap is zero. (3) The bound is $2\delta C(2\delta)^\alpha=0.2(3)(0.2)^2=0.024$. (4) No. The rule may disagree on histories where the competing values are very close, producing little value loss. Regret measures value loss, not the frequency of decision disagreement.