Decomposing Expected Regret by Arm

Why Decompose Expected Regret?

A single expected-regret value summarizes the average loss relative to always receiving the best arm’s mean reward, but it does not show where that loss comes from. The loss can be large because the policy allocates often to an arm that is substantially worse, or because it allocates less often to several arms that are only slightly worse. Decomposing expected pseudo-regret separates these two ingredients: how costly an arm is per allocation and how many times it is expected to be allocated.

This accounting identity does not prescribe an allocation policy or guarantee that a policy performs well. It gives a precise way to describe the policy’s expected allocation pattern in reward units. That is useful for interpreting cumulative reward objectives in adaptive trials, where every allocation affects both the current participant and the information available for later decisions.

Setup and Definition

Consider a finite set of \(K\) arms and a fixed horizon of \(T\) assignments. At time \(t\), the policy chooses arm \(A_t\), where \(A_t\) is in \(\{1,\ldots,K\}\). Let \(\mu_i\) denote the mean reward for arm \(i\). Assume these means are fixed over the horizon, finite, and comparable on the same reward scale. An allocation policy may be randomized and may use the observed history when choosing \(A_t\).

The standard stochastic bandit model also assumes that the reward observed after choosing arm \(i\) has conditional mean \(\mu_i\), given the information used to make that choice. This permits adaptive assignment, but rules out a change in an arm’s mean reward over time or a systematic mismatch between the stated mean and the reward generated when that arm is assigned. The identity below is an accounting identity for pseudo-regret; it does not require independent assignments or a nonadaptive policy.

Definition: Let \(\mu^*=\max_{1\leq j\leq K}\mu_j\) be the largest arm mean. The gap for arm \(i\) is \(\Delta_i=\mu^*-\mu_i\). The arm is optimal if \(\Delta_i=0\), and suboptimal if \(\Delta_i>0\). Let \(N_i(T)=\sum_{t=1}^{T}\mathbf{1}\{A_t=i\}\) be the number of times arm \(i\) is allocated by time \(T\). The cumulative pseudo-regret is \(\mathcal{R}^{ps}_T=\sum_{t=1}^{T}(\mu^*-\mu_{A_t})\), and its expectation, \(\mathbb{E}[\mathcal{R}^{ps}_T]\), is the expected pseudo-regret.

Pseudo-regret compares mean rewards, not the particular rewards that happened to be observed. On each assignment, it charges the gap associated with the chosen arm. Thus, it is random when the policy’s choices are random, even though the arm means are fixed. Its expectation averages over the policy’s possible allocation histories.

The Arm-by-Arm Identity

At each time \(t\), exactly one arm is chosen. The gap incurred at that time can therefore be written as a sum over all arms, with only the chosen arm’s indicator equal to one. Summing over time and then grouping assignments by arm gives the key identity.

\begin{aligned} \mathcal{R}^{ps}_T &=\sum_{t=1}^{T}(\mu^*-\mu_{A_t})\\ &=\sum_{t=1}^{T}\sum_{i=1}^{K}\mathbf{1}\{A_t=i\}\Delta_i\\ &=\sum_{i=1}^{K}\Delta_i\sum_{t=1}^{T}\mathbf{1}\{A_t=i\}\\ &=\sum_{i=1}^{K}\Delta_i N_i(T). \end{aligned}

Taking expectations and using linearity of expectation yields the decomposition. No independence among the assignment indicators is needed: linearity holds whether assignments are independent, correlated, or adaptively chosen using past outcomes.

Theorem: For a finite horizon and fixed, finite arm means, the expected pseudo-regret satisfies \(\mathbb{E}[\mathcal{R}^{ps}_T]=\sum_{i=1}^{K}\Delta_i\,\mathbb{E}[N_i(T)]\). Since \(\Delta_i=0\) for optimal arms, this is equivalently \(\mathbb{E}[\mathcal{R}^{ps}_T]=\sum_{i:\Delta_i>0}\Delta_i\,\mathbb{E}[N_i(T)]\).

The equality follows directly from the pathwise identity: each arm’s gap is fixed, so it can be taken outside the expectation of its allocation count. Expected counts need not be integers. They are averages over possible runs of the policy, and their fractional values are multiplied by the gaps just like integer counts.

Worked Example: Three Arms and Their Contributions

Hypothetical example. Suppose three arms have mean rewards of 12, 10, and 7 points per assignment, respectively. Over a horizon of 100 assignments, a policy has expected allocation counts of 40, 35, and 25. These expected counts sum to the horizon, as they must, because every assignment goes to exactly one arm.

The largest mean is \(\mu^*=12\) points. The gaps are \(\Delta_1=12-12=0\), \(\Delta_2=12-10=2\) points per assignment, and \(\Delta_3=12-7=5\) points per assignment. Applying the identity gives

\mathbb{E}[\mathcal{R}^{ps}_{100}] =0(40)+2(35)+5(25) =0+70+125 =195\text{ points}.

Arm 2 contributes 70 expected points of pseudo-regret, and arm 3 contributes 125 expected points. Arm 3 is allocated less often than arm 2, but its larger gap makes its contribution greater. The total is an expected loss relative to 100 assignments at a mean of 12 points each; it is not a claim that any particular run loses exactly 195 points.

What the Identity Says About Adaptive Allocation

Each product \(\Delta_i\mathbb{E}[N_i(T)]\) is the contribution of arm \(i\) to expected pseudo-regret. It combines an arm-specific cost per allocation with an expected number of allocations. This makes the decomposition useful for interpretation, but it also clarifies what cannot be concluded from the total alone: different policies can have the same total while allocating very differently across suboptimal arms.

A related constraint comes from the fact that the allocation counts sum to the fixed horizon on every run. Consequently, their expectations sum to \(T\). If there is a unique optimal arm, its expected count can be recovered from the suboptimal counts as \(T-\sum_{i:\Delta_i>0}\mathbb{E}[N_i(T)]\). The identity itself does not require a unique optimum; if several arms share the largest mean, all have zero gap and all count as optimal.

Worked Example: Comparing Two Allocation Patterns

Hypothetical example. Consider arms with means of 8, 7, and 4 units of reward per assignment, over a horizon of 50 assignments. The gaps are 0, 1, and 4 units per assignment. Policy A has expected counts \((30,15,5)\), while Policy B has expected counts \((30,10,10)\). Each set of counts sums to 50.

For Policy A, the contributions are \(0(30)=0\), \(1(15)=15\), and \(4(5)=20\) units, so expected pseudo-regret is \(0+15+20=35\) units. For Policy B, they are \(0(30)=0\), \(1(10)=10\), and \(4(10)=40\) units, so expected pseudo-regret is \(0+10+40=50\) units.

Both policies allocate 30 times in expectation to the optimal arm, but Policy B has the larger expected pseudo-regret because it allocates more often to the arm with the larger gap. The comparison is about the stated means and expected counts; it does not establish that either policy is preferable under every clinical objective.

Relation to Realized Regret

Realized regret uses observed rewards rather than arm means. For example, if \(Y_t\) is the reward actually observed at time \(t\), a common realized-regret quantity is \(T\mu^*-\sum_{t=1}^{T}Y_t\). It can be positive or negative on a particular run because observed rewards fluctuate. Pseudo-regret instead sums nonnegative mean gaps when \(\mu^*\) is the maximum arm mean.

Under the conditional-mean assumption in the setup, expected realized regret equals expected pseudo-regret. In detail, the conditional mean of the reward after choosing \(A_t\), given the choice and the information available when it was made, is \(\mu_{A_t}\). Therefore \(\mathbb{E}[Y_t]=\mathbb{E}[\mu_{A_t}]\). Summing over the fixed horizon gives

\mathbb{E}\left[T\mu^*-\sum_{t=1}^{T}Y_t\right] =T\mu^*-\sum_{t=1}^{T}\mathbb{E}[\mu_{A_t}] =\mathbb{E}\left[\sum_{t=1}^{T}(\mu^*-\mu_{A_t})\right] =\mathbb{E}[\mathcal{R}^{ps}_T].

This equality concerns expectations, not the realized values on individual runs. If reward means vary over time, or if the conditional reward mean after an assignment is not the \(\mu_i\) used in the calculation, the setup needs to be changed before applying this identity.

Checking a Decomposition and Avoiding Misinterpretation

The formula is simple, but its inputs and interpretation deserve checks. In particular, expected allocation counts describe the policy, whereas reward gaps describe the arm means. Confusing those roles can lead to incorrect calculations or overly strong conclusions.

Check the horizon total. For a fixed horizon, \(\sum_{i=1}^{K}N_i(T)=T\) on every run, so \(\sum_{i=1}^{K}\mathbb{E}[N_i(T)]=T\). A discrepancy indicates that an arm or assignment has been omitted, or that the reported counts use a different horizon or definition.
Check the gap signs and units. Every gap is \(\mu^*-\mu_i\), so it is nonnegative and is measured in reward units per assignment. Multiplying by a count gives cumulative reward units.
Check which optimum is used. The reference is the largest mean across all arms in the stated problem. An arm incorrectly labelled optimal changes the gaps and every contribution.
Do not equate expected counts with one run’s counts. Expected counts can be fractional; they are averages across possible policy histories, not a promise about a particular trial.

A common mistake is to multiply a gap by the number of assignments on which that arm’s reward happened to fall below the best arm’s observed reward. That is not this decomposition: observed rewards fluctuate, while pseudo-regret charges the fixed mean gap on every assignment to a suboptimal arm. The correction is to use \(\Delta_i=\mu^*-\mu_i\) and \(\mathbb{E}[N_i(T)]\), then sum across arms.

The main alternatives answer related but different questions. Total expected reward aggregates performance without displaying arm-specific contributions; expected pseudo-regret expresses its shortfall from the best-mean benchmark; realized regret retains the reward noise in a particular run. The arm decomposition is especially transparent for a fixed finite set of arms and horizon. It relies on meaningful, comparable fixed means and does not by itself assess uncertainty in estimated means, identify the best arm from data, or represent clinical objectives such as safety constraints and treatment-effect estimation.

Worked Example: Recovering a Missing Expected Count

Hypothetical example. A three-arm policy runs for 80 assignments. The arms have mean rewards of 5, 4.5, and 3 units per assignment, and the expected allocation counts for arms 2 and 3 are 20 and 12. The remaining expected count is \(80-20-12=48\) for arm 1. This is consistent with arm 1 being optimal, and the expected counts sum to the horizon.

The gaps are 0, \(5-4.5=0.5\), and \(5-3=2\) units per assignment. The decomposition is

\mathbb{E}[\mathcal{R}^{ps}_{80}] =0(48)+0.5(20)+2(12) =0+10+24 =34\text{ units of reward}.

The 12 expected allocations to arm 3 account for 24 of the 34 expected units of pseudo-regret. Although that count is lower than arm 2’s count, arm 3’s gap is four times as large.

Key takeaway: For fixed arm means and a fixed horizon, expected pseudo-regret is exactly the sum of each arm’s gap from the best mean multiplied by that arm’s expected allocation count. The decomposition explains where expected loss comes from; it does not, by itself, explain why a policy generated those counts or whether its objective is clinically adequate.

Check Your Understanding

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

Why does the identity remain valid when arm choices depend on previously observed rewards?
Three arms have means of 6, 5, and 2 points per assignment. Their expected counts over 40 assignments are 20, 15, and 5. Calculate expected pseudo-regret and give its units.
Suppose two arms tie for the largest mean. What is the gap for each optimal arm, and must either arm’s expected count be zero?
Explain why expected realized regret can equal expected pseudo-regret without realized regret equalling pseudo-regret on every run.

Solutions. (1) For every assignment, exactly one indicator \(\mathbf{1}\{A_t=i\}\) equals one. The pathwise identity therefore holds for every realized allocation sequence; taking expectations uses linearity, which does not require independence. (2) The gaps are 0, 1, and 4 points per assignment. Thus expected pseudo-regret is \(0(20)+1(15)+4(5)=15+20=35\) points. (3) Each arm tied at the largest mean has gap zero. Neither arm must have expected count zero; the policy may allocate to either or both. (4) Conditional on the chosen arm, the expected observed reward is that arm’s mean, so averaging realized reward loss gives the same value as averaging mean-gap loss. Individual rewards fluctuate, however, so a particular run’s realized regret can differ from its pseudo-regret.