Why Policy Regret Matters
A treatment rule converts patient characteristics into a treatment decision. When several rules are under consideration, a learning procedure may choose the one with the largest estimated value. That choice need not be the best rule in the candidate class: estimation error can make a weaker rule look better. Policy regret measures the value lost because of that selection.
Regret bounds connect a statistical question—how far estimated values may be from their targets—to a decision question—how much worse the selected rule may perform than the best available rule. These bounds do not require that the chosen rule be optimal among all conceivable treatment strategies. They compare it with the best rule in the specified class, such as a finite collection of interpretable policies.
Policy Value and Regret Within a Class
Let \(X\) denote the characteristics available when treatment is assigned, and let \(Y(0)\) and \(Y(1)\) be the potential outcomes under control and treatment. A deterministic binary treatment policy \(\pi\) maps characteristics to an assignment: \(\pi(X)\in\{0,1\}\). Suppose larger outcomes represent better results. The population value of the policy is the expected outcome that would result if the policy were followed.
This is a causal quantity: it refers to outcomes under the treatment assignments the policy would make, not merely to outcomes observed among people who happened to receive those assignments. A causal interpretation relies on a suitable potential-outcome framework, including consistency, no interference between individuals, conditional exchangeability of treatment given measured characteristics, and positivity for the assignments needed to assess the policy. The regret arguments below take the value estimates and their error guarantees as given; they do not prescribe how to construct those estimates.
Let \(\Pi\) be the set of candidate policies. For now, assume it is nonempty and finite. The best policy in this class, denoted \(\pi^*\), has the largest population value. A learning procedure produces an estimated value \(\hat V(\pi)\) for each candidate and selects a policy \(\hat\pi\) with the largest estimated value.
The comparison is deliberately class-relative. A small regret means the selected policy performs nearly as well as the best rule in \(\Pi\); it does not imply that the best rule in \(\Pi\) is optimal among rules outside the class. Likewise, regret is not the same as the treatment effect for an individual or the difference between the policy and treating nobody.
The Basic Regret Bound
The central condition is a simultaneous error bound: every candidate rule's estimated value is close to its population value. “Simultaneous” matters because the selected rule is chosen by comparing estimates across the class.
To see why, add and subtract the estimated values for the best-in-class rule and the selected rule. The middle difference cannot be positive: by construction, the selected rule has at least as large an estimated value as any other candidate. The two remaining differences are each bounded by the uniform error.
This argument is deterministic once the simultaneous error condition holds. If that condition holds with probability at least \(1-\delta\), the regret bound also holds with probability at least \(1-\delta\). The factor of two comes from allowing error at both the best rule's estimate and the selected rule's estimate. The bound is a guarantee, not a claim that the actual regret must equal \(2\varepsilon\).
Worked Example: Comparing Three Candidate Rules
Consider three hypothetical rules, and suppose their population values and estimated values are as shown. Values are in utility points per person, with larger values preferred.
| Rule | Population value \(V(\pi)\) | Estimated value \(\hat V(\pi)\) | Absolute error |
|---|---|---|---|
| A | 0.70 | 0.71 | 0.01 |
| B | 0.76 | 0.74 | 0.02 |
| C | 0.72 | 0.75 | 0.03 |
Rule B is best in the class because its population value, 0.76 utility points per person, is the largest. The learner selects rule C because its estimated value, 0.75, exceeds the estimates for A and B. The actual regret is therefore
The largest absolute estimation error in the table is \(\varepsilon=0.03\) utility points per person. The theorem gives \(R(\hat\pi;\Pi)\leq2(0.03)=0.06\) utility points per person. The bound holds: the observed regret is 0.04, below 0.06. This example also shows why maximizing estimated value alone does not guarantee zero regret.
Rule-Specific Errors and Imperfect Optimization
The same reasoning can use different error limits for different rules. Suppose \(|\hat V(\pi)-V(\pi)|\leq\varepsilon_\pi\) for each candidate. For any comparator \(\pi\), the true value advantage of that comparator over the selected policy is at most its estimated advantage plus the two relevant error limits. Since the selected policy maximizes estimated value, the estimated advantage is nonpositive.
In particular, applying this to \(\pi^*\) gives \(R(\hat\pi;\Pi)\leq\varepsilon_{\pi^*}+\varepsilon_{\hat\pi}\). This can be more informative than \(2\varepsilon\) when the error limits for those two rules are smaller than the largest error limit anywhere in the class.
Some algorithms do not find the exact maximizer of estimated value. If their output satisfies \(\hat V(\hat\pi)\geq\max_{\pi\in\Pi}\hat V(\pi)-\eta\), where \(\eta\geq0\) is the optimization shortfall, then the middle difference in the decomposition is at most \(\eta\). Thus the uniform-error guarantee becomes \(R(\hat\pi;\Pi)\leq2\varepsilon+\eta\). The optimization shortfall is measured in the same units as policy value.
Worked Example: Using Rule-Specific Error Limits
Suppose three hypothetical rules have estimated values of 0.82, 0.80, and 0.75 utility points per person for A, B, and C, respectively. The learner chooses A. Assume the error limits are 0.01 for A, 0.03 for B, and 0.02 for C. These are simultaneous limits: each rule's true value is within its stated distance of its estimate.
For B, the estimated advantage over A is \(0.80-0.82=-0.02\). Its true advantage over A is therefore at most
For C, the corresponding upper bound is
A cannot have a positive advantage over itself. Consequently, the regret relative to the best of A, B, and C is at most 0.02 utility points per person: neither B nor C can exceed A by more than that amount under the stated limits. For instance, values \(V(A)=0.82\), \(V(B)=0.83\), and \(V(C)=0.76\) are consistent with the estimates and limits; in that case the actual regret is 0.01, which is within the bound.
From a Finite Class to a Probability Guarantee
A uniform error guarantee can sometimes be obtained by combining a concentration bound for each fixed rule with a union bound over the candidate class. The result below is illustrative: it requires bounded, unbiased value contributions, and it is not a recipe for constructing a valid causal value estimator.
Assume \(\Pi\) contains \(m\) fixed policies. For each policy \(\pi\), suppose its estimate is the average of \(n\) independent and identically distributed contributions \(W_i(\pi)\), each in \([0,1]\), with \(E[W_i(\pi)]=V(\pi)\). The contributions for different policies need not be independent. Hoeffding's inequality gives, for each fixed policy, \(P(|\hat V(\pi)-V(\pi)|>\varepsilon)\leq2\exp(-2n\varepsilon^2)\). Summing these probabilities across the \(m\) policies gives
Setting the right-hand side equal to \(\delta\) and solving for \(\varepsilon\) yields a uniform error limit. Combining it with the regret theorem gives a high-probability regret bound.
Worked Example: A Finite-Class Probability Bound
Suppose, hypothetically, that \(n=200\) independent observations provide bounded contributions in \([0,1]\) for each of \(m=5\) fixed candidate rules, and that each rule's average is unbiased for its policy value. Choose \(\delta=0.05\). The uniform error threshold is
The corresponding regret bound is \(2\varepsilon\approx0.2302\) utility points per person. Under the stated assumptions, the selected rule's regret relative to the best of those five rules is no greater than about 0.2302 utility points per person with probability at least 0.95. The bound may be conservative; it is a guaranteed limit under the assumptions, not a prediction of the regret's typical size.
Common Mistakes and Practical Meaning
- Comparing with the wrong benchmark. The bound compares the learned rule with the best rule in \(\Pi\), not with an unknown globally optimal policy. A narrow or poorly designed class can have low within-class regret while still leaving substantial value unrealized.
- Using pointwise accuracy after searching many rules. Knowing that one prespecified rule has a small estimation error does not establish that all rules—including the one selected by maximizing estimates—are accurate. The \(2\varepsilon\) result requires a simultaneous bound over the class, or another argument that accounts for selection.
- Treating a bound as the observed loss. If the bound is 0.06 utility points per person, it does not follow that regret is 0.06. It says regret cannot exceed that amount on the event where the assumptions and error guarantee hold.
- Ignoring the value scale or causal assumptions. Regret inherits the units of the chosen outcome or utility. A numerical bound on estimated values is not by itself evidence that those values represent causal policy outcomes; the value definition and identification assumptions still matter.
The practical lesson is that policy selection has two sources of possible shortfall: inaccurate value estimates and, when applicable, failure to maximize those estimates exactly. Uniform accuracy controls the first; an optimization tolerance controls the second. Keeping the benchmark, units, and assumptions explicit makes a regret guarantee interpretable as a statement about a decision, rather than merely a property of a prediction algorithm.
Check Your Understanding
Use the definitions and bounds above to answer the following questions.
- If the largest absolute value-estimation error over a candidate class is 0.04 utility points per person, what regret bound follows for an exact maximizer of estimated value?
- Why is regret relative to a candidate class not automatically regret relative to the globally optimal treatment policy?
- A learner's estimated value is within 0.01 of the largest estimated value, and the uniform estimation error is at most 0.02. What regret bound follows?
- Why does selecting the rule with the largest estimated value make simultaneous error control important?
- In the finite-class probability result, which assumptions allow Hoeffding's inequality and the union bound to be used?