Why Reward Gaps Matter
In a multi-arm trial, regret accumulates when patients are assigned to treatments whose expected rewards are below the highest available expected reward. The size of that loss per assignment is not the whole story: a treatment with a large loss may be used rarely, while one with a small loss may be assigned often. Reward gaps let us separate these two ingredients and see how each treatment contributes to expected regret.
This is an accounting tool for cumulative reward. It does not, by itself, determine which allocation policy to use or establish which treatment is best from observed data. The gaps are defined using the arms’ true expected rewards; in practice those rewards are generally unknown.
Definition and Interpretation
Consider a finite set of \(K\) treatment arms indexed by \(i=1,\ldots,K\), observed over \(T\) assignments. Let \(Y_t\) be the reward for the patient assigned at time \(t\), and let \(A_t\) denote that patient’s assigned arm. Assume a stationary reward model: conditional on the history before assignment and on \(A_t=i\), the expected reward is \(\mu_i\), the same for every assignment to arm \(i\). For example, rewards could be independent Bernoulli outcomes with arm-specific success probabilities \(\mu_i\). Rewards must be defined on a common, comparable scale.
The allocation policy may use past assignments and rewards to choose the next arm. The simple stationary model requires that this adaptation does not change the arm-specific conditional mean: \(E[Y_t\mid\text{past}, A_t=i]=\mu_i\). Write \(\mu_*=\max_{1\leq j\leq K}\mu_j\) for the highest expected reward. An arm attaining \(\mu_*\) is optimal in expected reward under this model; there may be more than one such arm.
The gap has the same units as the reward. For a binary success reward, it is a difference in success probabilities, often described in percentage points. For a reward measured in quality-adjusted life-years, it is measured in quality-adjusted life-years per assignment, provided that is how the reward was defined. The gap is not the probability that the treatment is inferior, nor is it the observed difference between two sample averages.
Let \(N_i(T)=\sum_{t=1}^{T} I(A_t=i)\) be the number of assignments to arm \(i\) by time \(T\). The arm-specific contribution to expected pseudo-regret is the gap multiplied by the expected number of assignments to that arm.
Here \(R_T=T\mu_*-\sum_{t=1}^{T}Y_t\) is realized regret relative to the benchmark of receiving the optimal arm’s expected reward on every assignment. The displayed equality gives its expectation under the stationary conditional-mean model. It is also commonly called the expected pseudo-regret decomposition: expected regret is the sum of arm-level losses, not a claim that each realized patient outcome differs from an optimal-arm outcome by exactly \(\Delta_i\).
Why the Decomposition Holds
The key point is that adaptive assignment changes the random counts \(N_i(T)\), but under the stated model it does not change the expected reward conditional on an assignment to arm \(i\). Since exactly one arm is assigned at each time, the counts sum to \(T\). The expected reward accumulated from arm \(i\) is \(\mu_i\mathbb{E}[N_i(T)]\): this follows by summing the expected reward at each time multiplied by the indicator that arm \(i\) was assigned.
Subtract this expected reward from \(T\mu_*\). Because \(\sum_i \mathbb{E}[N_i(T)]=T\), the result is
This derivation uses the conditional expected reward \(\mu_i\), not an assumption that the policy’s assignments are fixed in advance. It does require that the mean reward for an arm remains as specified as the policy adapts. If assignment changes the meaning of the reward, or treatment effects change over time, a single fixed \(\mu_i\) may not describe the trial.
Worked Example: Gaps and Contributions for Three Arms
Suppose a hypothetical trial has three stationary Bernoulli reward distributions with means \(\mu_1=0.72\), \(\mu_2=0.65\), and \(\mu_3=0.50\). At the end of \(T=100\) assignments, the allocation counts are \(N_1=40\), \(N_2=30\), and \(N_3=30\). Treat these means and counts as known for this calculation.
The highest mean is \(\mu_*=0.72\). The gaps are \(\Delta_1=0.72-0.72=0\), \(\Delta_2=0.72-0.65=0.07\), and \(\Delta_3=0.72-0.50=0.22\). Because rewards are binary, the gaps are 7 and 22 percentage points in success probability per assignment, respectively.
The contributions to expected regret are \(0(40)=0\) for arm 1, \(0.07(30)=2.10\) for arm 2, and \(0.22(30)=6.60\) for arm 3. Thus the total is \(2.10+6.60=8.70\) expected reward units over 100 assignments. Arm 3 contributes \(6.60/8.70=0.759\), or about 75.9%, of this total. Although arms 2 and 3 were assigned equally often, the larger gap for arm 3 makes its regret contribution larger.
This is an expected-regret calculation under the specified model. The observed number of successes in a particular hypothetical run need not equal its expected reward, and its realized regret need not equal 8.70.
Gap Size Is Not the Same as Regret Contribution
The gap answers a per-assignment question: how much expected reward is given up each time this arm is used, relative to the best mean? The contribution answers a cumulative question: how much expected regret is attributable to all assignments to this arm? The first quantity depends on arm means; the second depends on both arm means and allocation.
Worked Example: A Smaller Gap Can Contribute More
Consider a hypothetical three-arm trial with stationary means \(\mu_1=0.80\), \(\mu_2=0.70\), and \(\mu_3=0.40\). Assume the expected allocation counts over the horizon are \(\mathbb{E}[N_1(T)]=10\), \(\mathbb{E}[N_2(T)]=80\), and \(\mathbb{E}[N_3(T)]=10\). These expected counts sum to \(T=100\).
Arm 1 is optimal, so \(\mu_*=0.80\). The gaps for arms 2 and 3 are \(\Delta_2=0.80-0.70=0.10\) and \(\Delta_3=0.80-0.40=0.40\). Arm 3 has the larger per-assignment loss, four times the gap of arm 2.
For arm 2, the contribution is \(0.10(80)=8.00\) expected reward units. For arm 3, it is \(0.40(10)=4.00\) expected reward units. The total expected regret is \(8.00+4.00=12.0\). Arm 2, despite its smaller gap, contributes twice as much as arm 3 because it is assigned eight times as often. Therefore, ranking arms by gaps alone does not rank their total contributions.
When a policy is randomized and the counts are not yet observed, use expected counts to describe expected contributions. For example, if the probability of assigning arm \(i\) at time \(t\), conditional on the observed past, is \(q_{i,t}\), then \(E[N_i(T)]=\sum_{t=1}^{T}E[q_{i,t}]\). Multiplying this expectation by \(\Delta_i\) gives the arm’s contribution to expected regret. A realized count can instead be used to describe the corresponding realized allocation’s plug-in accounting, but it should not be confused with the expectation over possible trial runs.
Comparing Contributions and Diagnosing Problems
A useful summary keeps the per-assignment loss and the number of assignments visible together. Reporting only total regret can hide which arms generated it; reporting only counts can hide how costly those assignments were. Reporting only gaps can make a rarely assigned arm look more consequential than it is over the horizon.
| Quantity | Question answered | What it does not show by itself |
|---|---|---|
| Gap \(\Delta_i\) | What is the expected loss per assignment to arm \(i\)? | How often the policy assigns that arm |
| Expected count \(\mathbb{E}[N_i(T)]\) | How many assignments to arm \(i\) are expected? | How costly each assignment is relative to the best mean |
| Contribution \(\Delta_i\mathbb{E}[N_i(T)]\) | How much expected regret is attributed to arm \(i\)? | How uncertain the estimated gap or count may be |
A few checks help catch errors. First, verify that \(\mu_*\) really is the maximum of the listed means; otherwise a supposed gap could be negative. Second, check that the gaps and counts refer to the same horizon and reward definition. Third, add the expected counts: they must sum to \(T\) when exactly one arm is assigned at each of the \(T\) times. Finally, add the arm contributions and compare the result with \(T\mu_*-\sum_i\mu_iE[N_i(T)]\); the two calculations must agree.
The gap calculation is only as meaningful as its reward model. Averages on incompatible scales cannot be compared directly. If clinical benefit is defined by a composite or transformed endpoint, the \(\mu_i\) and gaps refer to that defined reward, not automatically to every clinically relevant outcome. If expected rewards vary with calendar time, patient characteristics, or prior assignments, a fixed arm-level gap may conceal that variation; the model and benchmark must then be specified to match the setting. And when means are estimated rather than known, a calculated gap is an estimate, with uncertainty—not a known fact about the treatments.
A common mistake is to say, “Arm 3 has the largest gap, so it contributes the most regret.” That conclusion omits the allocation count. The correction is to calculate \(\Delta_i\mathbb{E}[N_i(T)]\) for every arm and compare those products. A second mistake is to describe the gap as the observed reward difference on each patient. It is instead a difference in expected rewards; individual outcomes can vary around their arm-specific means.
Using the Decomposition in Practice
For a specified model and horizon, an arm-by-arm contribution table makes the accounting transparent. The steps are:
State the common reward scale, the arm-specific expected rewards \(\mu_i\), and the conditions under which those means apply.
Compute \(\mu_*=\max_i\mu_i\), then calculate each \(\Delta_i=\mu_*-\mu_i\).
Use realized \(N_i(T)\) for an allocation summary or \(\mathbb{E}[N_i(T)]\) for expected regret; do not substitute one for the other without saying so.
Calculate each gap-count product and sum across arms. Confirm the counts sum to the number of assignments and the total matches the benchmark-minus-expected-reward calculation.
This decomposition complements an aggregate regret summary by identifying which suboptimal arms account for it. It can help explain whether a total is driven by frequent assignments to near-optimal arms or by fewer assignments to arms with larger losses. It does not say that every arm with a positive gap should be eliminated, nor does it provide a statistical procedure for learning the unknown means.
Worked Example: Expected Counts Under an Adaptive Policy
Suppose a hypothetical four-assignment policy has fixed arm means \(\mu_1=0.60\) and \(\mu_2=0.50\), and at each time assigns arm 2 with conditional probability \(q_{2,t}\). Assume the policy’s expected conditional probabilities of arm 2 are \(0.20, 0.30, 0.40,\) and \(0.50\) at times 1 through 4. Arm 1 is assigned otherwise. The stationary conditional-mean assumption holds by construction: assignment changes over time, but each arm’s expected reward remains its stated mean.
The optimal mean is \(\mu_*=0.60\), so \(\Delta_1=0\) and \(\Delta_2=0.60-0.50=0.10\) reward units per assignment. The expected number of assignments to arm 2 is \(E[N_2(4)]=0.20+0.30+0.40+0.50=1.40\). Therefore arm 2 contributes \(0.10(1.40)=0.140\) expected reward units to regret, while arm 1 contributes zero.
As a check, \(E[N_1(4)]=4-1.40=2.60\), so expected reward is \(0.60(2.60)+0.50(1.40)=1.56+0.70=2.26\). The benchmark is \(4(0.60)=2.40\), and \(2.40-2.26=0.140\), matching the arm-specific calculation. The example shows why adaptive assignment probabilities do not prevent the decomposition: their effect enters through the expected counts.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions below.
- Three arms have means \(0.75, 0.68,\) and \(0.55\). What are their reward gaps, and which arm or arms are optimal?
- Using those same means, suppose the expected counts are \(20,50,\) and \(30\). Calculate each arm’s regret contribution and total expected regret.
- Can an arm with a smaller gap contribute more expected regret than an arm with a larger gap? State the condition in terms of counts and gaps.
- Why must the expected counts sum to \(T\) in a trial that assigns exactly one arm at each time?
- What model feature would make fixed arm-specific reward gaps potentially misleading?
Solutions. (1) The maximum is \(0.75\), so the gaps are \(0\), \(0.75-0.68=0.07\), and \(0.75-0.55=0.20\). Arm 1 is optimal. (2) The contributions are \(0(20)=0\), \(0.07(50)=3.50\), and \(0.20(30)=6.00\); total expected regret is \(9.50\) reward units. (3) Yes. For example, arm \(i\) contributes more than arm \(j\) when \(\Delta_iE[N_i(T)]>\Delta_jE[N_j(T)]\), even if \(\Delta_i<\Delta_j\); a sufficiently larger expected count can outweigh the smaller gap. (4) Exactly one arm is assigned at each time, so the realized counts sum to \(T\) in every run; taking expectations preserves the sum. (5) If an arm’s conditional mean reward changes over time or with patient characteristics or assignment history, one fixed \(\mu_i\) may not represent its expected reward throughout the trial, so the corresponding fixed gap may not capture the relevant regret.