Conditional Regret Gaps for Finite Actions

Why a Gap Measures the Cost of a Decision

Knowing which action minimizes conditional risk answers a selection question: which action is best given the available information? A gap answers a different question: how costly, in conditional risk, is choosing an alternative? If the best action is only slightly better than its competitors, a mistaken choice may have little consequence. If it is substantially better, the same kind of mistake carries a larger risk penalty.

This tutorial makes that comparison precise for a finite set of actions. The risk and its minimizers are conditional on the observed information, so both the optimal action and the gap can vary with the observation. Ties matter: the gap between the two lowest action risks is zero when the best risk is tied, even if every action outside the tied optimal set is much worse.

Conditional Risks and Two Gap Definitions

Let $X$ denote the information available when a decision is made, let $Y$ be the outcome, and let $\mathcal A=\{a_1,\ldots,a_K\}$ be a finite action set. The loss from taking action $a$ when the outcome is $Y$ is $L(Y,a)$. Assume $E[|L(Y,a)|]<\infty$ for every $a\in\mathcal A$. The conditional risk of action $a$ is

r_a(X)=E[L(Y,a)\mid X].

Each conditional expectation is defined up to events of probability zero. Because there are finitely many actions, we may work on one event of probability one where all these risks are finite. At an observed value $X=x$, write $r_a(x)$ for a version of the conditional risk evaluated there.

Definition: The optimal-action set at $x$ is $A^*(x)=\{a\in\mathcal A:r_a(x)=r_*(x)\}$, where $r_*(x)=\min_{a\in\mathcal A}r_a(x)$. An action is nonoptimal at $x$ if it is not in $A^*(x)$.

Order the $K$ risk values at $x$, counting repeated values, as $r_{(1)}(x)\le r_{(2)}(x)\le\cdots\le r_{(K)}(x)$. The ordinary best-versus-second-best gap is $\Delta(x)=r_{(2)}(x)-r_{(1)}(x)$, for $K\ge2$. It is positive exactly when the minimizing action is unique.

For bounds on choosing a nonoptimal action when there are ties, it is useful to define a second, tie-aware gap. If there is at least one nonoptimal action, set $\Gamma(x)=\min_{a\notin A^*(x)}[r_a(x)-r_*(x)]$. If every action is optimal, set $\Gamma(x)=0$. When the optimum is unique, $\Gamma(x)=\Delta(x)$. When several actions tie for the minimum, $\Delta(x)=0$, but $\Gamma(x)$ can still be positive.

Worked Example: A Unique Best Action

At a particular observation $x$, suppose three actions have conditional risks $2$, $5$, and $9$. Find the optimal action, both gaps, and the smallest possible excess risk from choosing a nonoptimal action.

The minimum risk is $r_*(x)=2$, attained only by action $a_1$, so $A^*(x)=\{a_1\}$. The ordered risks are $2\le5\le9$, giving $\Delta(x)=5-2=3$. The nonoptimal actions have excess risks $5-2=3$ and $9-2=7$, so $\Gamma(x)=3$ as well. Choosing any nonoptimal action therefore incurs at least $3$ units of excess conditional risk.

Worked Example: A Tie at the Minimum

Suppose four actions have conditional risks $1.5$, $1.5$, $4$, and $8$. Calculate the two gaps and explain what each says about a nonoptimal choice.

The first two actions are both optimal, so $r_*(x)=1.5$ and $A^*(x)=\{a_1,a_2\}$. The best-versus-second-best gap is $\Delta(x)=1.5-1.5=0$, reflecting the tie. The nonoptimal actions have excess risks $4-1.5=2.5$ and $8-1.5=6.5$, so the tie-aware gap is $\Gamma(x)=2.5$. Thus choosing the other tied action has zero excess risk, while choosing a nonoptimal action costs at least $2.5$.

Excess Conditional Risk: The Gap Bound

For a deterministic decision $d(X)\in\mathcal A$, its excess conditional risk at $x$ is $r_{d(x)}(x)-r_*(x)$. It is always nonnegative by the definition of the minimum. The gap gives a sharper statement when the decision is nonoptimal.

Theorem: For any $x$ where the conditional risks are finite, if $d(x)\notin A^*(x)$, then $r_{d(x)}(x)-r_*(x)\ge\Gamma(x)$. If the minimizer is unique, this is also a bound by $\Delta(x)$.

Proof. Since $d(x)\notin A^*(x)$, it belongs to the set over which $\Gamma(x)$ is minimized. Therefore its excess risk is one of the values $r_a(x)-r_*(x)$ in that set, and cannot be smaller than their minimum. With a unique minimizer, the lowest nonoptimal risk is the second-lowest action risk, so $\Gamma(x)=r_{(2)}(x)-r_{(1)}(x)=\Delta(x)$. $\square$

This statement is pointwise: it holds at each observation where the conditional risks are defined. It does not say that a decision is wrong whenever its excess risk is small. If the gap is small, a nonoptimal action can indeed have small excess risk.

Worked Example: Translating a Risk Tolerance into a Decision Guarantee

At $x$, suppose the action risks are $0.8$, $1.1$, and $1.7$. A decision rule returns an action whose excess conditional risk is at most $0.2$. Can that action be nonoptimal?

The unique minimum is $0.8$, and the next-lowest risk is $1.1$, so $\Delta(x)=1.1-0.8=0.3$. Any nonoptimal action has excess risk at least $0.3$: action two has excess $1.1-0.8=0.3$, and action three has excess $1.7-0.8=0.9$. Since the stated excess is at most $0.2$, it is below the minimum nonoptimal excess $0.3$. Therefore the returned action must be optimal.

Randomized Decisions and Their Regret

A randomized rule may select different actions with different probabilities at the same $x$. Write $\pi_a(x)=P(A=a\mid X=x)$, where $\pi_a(x)\ge0$ and $\sum_{a\in\mathcal A}\pi_a(x)=1$. Here the randomization is part of the decision rule: conditional on $X$, the action is selected without using the unobserved outcome $Y$. Its conditional risk is $\sum_a\pi_a(x)r_a(x)$, and its excess conditional risk is that quantity minus $r_*(x)$.

Theorem: For any such randomized rule, $$ \sum_{a\in\mathcal A}\pi_a(x)r_a(x)-r_*(x) \ge \Gamma(x)\sum_{a\notin A^*(x)}\pi_a(x). $$

Proof. Subtract the minimum risk and use $\sum_a\pi_a(x)=1$:

\sum_{a\in\mathcal A}\pi_a(x)r_a(x)-r_*(x) =\sum_{a\in\mathcal A}\pi_a(x)\bigl(r_a(x)-r_*(x)\bigr).

For $a\in A^*(x)$, the difference in parentheses is zero. For every $a\notin A^*(x)$, it is at least $\Gamma(x)$. Multiplying these inequalities by the nonnegative probabilities $\pi_a(x)$, and summing, gives the stated bound. If there are no nonoptimal actions, the right-hand side is zero by the definition $\Gamma(x)=0$, and all actions have zero excess risk. $\square$

The sum $\sum_{a\notin A^*(x)}\pi_a(x)$ is the probability that the rule selects a nonoptimal action. Thus the tie-aware gap multiplies the probability of a nonoptimal choice to give a lower bound on conditional regret. For a unique optimum, the same result uses the familiar best-versus-second-best gap $\Delta(x)$.

Worked Example: Randomization with a Unique Optimum

At $x$, let the risks of $a_1,a_2,a_3$ be $1, 1.4, 3$. A randomized rule selects these actions with probabilities $0.6, 0.3, 0.1$, respectively. Compute its conditional excess risk and verify the gap bound.

The unique optimal action is $a_1$, with risk $1$. The rule's conditional risk is

$$ 0.6(1)+0.3(1.4)+0.1(3)=0.6+0.42+0.3=1.32. $$

Its excess conditional risk is $1.32-1=0.32$. The gap is $\Delta(x)=\Gamma(x)=1.4-1=0.4$. The probability of selecting a nonoptimal action is $0.3+0.1=0.4$, so the lower bound is $0.4(0.4)=0.16$. The calculated excess $0.32$ is at least $0.16$, as required. The bound need not be exact because some probability is assigned to action three, whose excess risk is $3-1=2$, larger than the gap.

Common Pitfall and Practical Interpretation

Treating a zero order-statistic gap as proof that every action is equally good. If the minimum is tied, $\Delta(x)=0$, but other actions can have much larger risks. Identify the full optimal-action set and use $\Gamma(x)$ to measure the cost of leaving it.
Using the gap as the exact regret of every mistake. The gap is a lower bound on the excess risk of a nonoptimal choice, not usually its exact excess risk. In the randomized example, the risks of different nonoptimal actions were not equal.
Ignoring dependence on the observation. Risks, optimal actions, and gaps are conditional on $X=x$. A single unconditional ranking of actions need not describe their ranking at every $x$.

A gap is useful for interpreting a decision rule's conditional performance: a small excess risk can certify optimality when the gap is larger than the excess, while a large gap makes nonoptimal choices costly. In learning problems, the gap can also identify observations at which action selection is especially sensitive: when the gap is small, even a small error in estimated conditional risks may change the selected action.

Check Your Understanding

Use the definitions and bounds to answer the following questions.

Three actions have conditional risks $2, 6, 10$. What are $\Delta(x)$ and $\Gamma(x)$, and what is the smallest excess risk of a nonoptimal action?
Three actions have conditional risks $3, 3, 7$. Why is $\Delta(x)=0$, and what is $\Gamma(x)$?
A randomized rule assigns probability $0.25$ to nonoptimal actions at an observation where $\Gamma(x)=2$. What lower bound does the theorem give for its excess conditional risk?
If the minimum conditional risk is attained by every action, what are the excess risk and the defined value of $\Gamma(x)$ for any randomized rule?
When does the best-versus-second-best gap equal the gap to the best nonoptimal action?