Pseudo-Regret and Realized Regret

Two Regret Measures, Two Sources of Variation

Regret compares the reward collected by an allocation policy with a benchmark: repeatedly receiving the expected reward of the best treatment. The comparison can be made using expected rewards alone, or using the outcomes actually observed. These choices produce pseudo-regret and realized regret, respectively. They answer related but different questions: how much expected reward was forgone by the assignments, and how did the observed reward total compare with the benchmark?

The distinction matters because observed outcomes vary even when the assigned treatment is fixed. A patient assigned to a treatment with a high response probability may not respond; a patient assigned to a lower-response treatment may respond. Pseudo-regret isolates the assignment decisions against the model’s expected rewards. Realized regret also includes this outcome variability.

Setup and Definitions

Suppose there are $K$ treatment arms and a fixed horizon of $T$ assignments. At time $t$, the policy assigns arm $A_t$, and the observed reward is $Y_t$. Let $\mu_a$ be the expected reward from arm $a$, and let $\mu^*=\max_{1\leq a\leq K}\mu_a$ be the largest arm mean. Rewards are coded so that larger values are preferred. The benchmark is $T\mu^*$: the expected reward from using a best-mean arm for all $T$ assignments.

Definition: The pseudo-regret through time $T$ is $$ \bar{R}_T=\sum_{t=1}^{T}(\mu^*-\mu_{A_t}). $$ The realized regret through time $T$, relative to the same expected-reward benchmark, is $$ R_T=T\mu^*-\sum_{t=1}^{T}Y_t. $$

Each term in pseudo-regret is an expected-reward gap for the assigned arm. Since $\mu^*$ is the largest arm mean, every term is nonnegative, so $\bar{R}_T\geq 0$. Pseudo-regret is generally random because the actions $A_t$ may depend on earlier observed outcomes or on policy randomization. In contrast, realized regret uses the actual observed rewards and can be negative: a sequence of unusually favorable outcomes can exceed the benchmark $T\mu^*$.

These definitions use an expected-reward benchmark, not the reward that a particular patient would have received under a different treatment. The latter is a counterfactual quantity and is not observed for that patient. The benchmark therefore describes performance relative to the best arm’s mean, rather than a patient-by-patient comparison with an unobserved outcome.

Assumptions and the Relationship Between the Measures

For the standard stochastic bandit interpretation, assume each arm has a stable expected reward $\mu_a$ over the horizon. The policy chooses $A_t$ using information available before observing $Y_t$, and the conditional mean of the next reward satisfies $\mathbb{E}(Y_t\mid \mathcal{H}_{t-1},A_t=a)=\mu_a$, where $\mathcal{H}_{t-1}$ denotes the history available before assignment $t$. Thus the policy may adapt to past data, but the current reward has the assigned arm’s mean conditional on that history and assignment. Rewards must have finite means; finite variances are needed for variance-based summaries of reward noise.

The key identity follows by adding and subtracting the expected reward of the assigned arm at each time:

\begin{aligned} R_T &=T\mu^*-\sum_{t=1}^{T}Y_t\\ &=\sum_{t=1}^{T}(\mu^*-\mu_{A_t}) +\sum_{t=1}^{T}(\mu_{A_t}-Y_t)\\ &=\bar{R}_T+\sum_{t=1}^{T}(\mu_{A_t}-Y_t). \end{aligned}

The second sum is the accumulated difference between each assigned arm’s mean and its observed reward. Under the conditional-mean assumption, each difference has conditional expectation zero after the arm is selected. Taking expectations therefore gives

\mathbb{E}(R_T)=\mathbb{E}(\bar{R}_T).

This equality does not say the two regret values are equal on a particular allocation path. It says their averages over repeated runs of the policy and reward process agree under the stated model. The identity also clarifies what the two measures separate: pseudo-regret records the loss associated with assignments to arms below the best mean, while the remaining term records reward noise around the assigned arms’ means.

Worked Example: Computing Both Measures for One Allocation Path

Consider two hypothetical arms with expected rewards $\mu_A=0.60$ and $\mu_B=0.45$ successes per assignment. Suppose the policy assigns $A,B,B$ over three assignments, and the observed rewards are $1,0,1$. These values are consistent with Bernoulli rewards, and the stipulated arm means are the success probabilities. The best mean is $\mu^*=0.60$.

For pseudo-regret, the first assignment has gap $0.60-0.60=0$, while each assignment to $B$ has gap $0.60-0.45=0.15$. Thus

\bar{R}_3=(0.60-0.60)+(0.60-0.45)+(0.60-0.45)=0.30

The benchmark is $3(0.60)=1.80$ expected successes. The observed total is $1+0+1=2$ successes, so realized regret is

R_3=1.80-2=-0.20\text{ successes}.

The realized regret is negative because the observed total exceeds the expected benchmark. Check the identity: the reward-noise term is $(0.60-1)+(0.45-0)+(0.45-1)=-0.50$ successes, and $0.30+(-0.50)=-0.20$. This single run does not contradict the nonnegative pseudo-regret; the two quantities differ by outcome noise.

Worked Example: The Same Assignments, Different Outcomes

Keep the same means and the same assignments $A,B,B$, but suppose the hypothetical observed rewards are $0,1,0$. The allocation path and hence pseudo-regret are unchanged:

\bar{R}_3=0+0.15+0.15=0.30\text{ expected successes}.

The observed total is now $1$ success, so

R_3=3(0.60)-1=0.80\text{ successes}.

The reward-noise term is $(0.60-0)+(0.45-1)+(0.45-0)=0.50$, and $0.30+0.50=0.80$. The allocation decisions have the same expected-reward cost as in the previous example, but different outcomes lead to different realized regret. For Bernoulli rewards, each listed outcome has positive probability under its assigned arm: both 0 and 1 are possible because both arm means lie strictly between 0 and 1.

Worked Example: Expected Regret Under a Randomized One-Assignment Policy

Suppose there is one assignment, with $\mu_A=0.60$ and $\mu_B=0.40$. A policy assigns $A$ with probability $0.75$ and $B$ with probability $0.25$, before observing the outcome. Assume Bernoulli rewards with those success probabilities. Here $\mu^*=0.60$.

The pseudo-regret is $0$ if $A$ is assigned and $0.20$ if $B$ is assigned. Its expectation is

\mathbb{E}(\bar{R}_1)=0.75(0)+0.25(0.60-0.40)=0.0500\text{ expected successes}.

For realized regret, the benchmark is $0.60$ successes. The four possible assignment-outcome combinations have probabilities and regrets as follows: $A$ with reward 1 has probability $0.75(0.60)=0.45$ and regret $-0.40$; $A$ with reward 0 has probability $0.75(0.40)=0.30$ and regret $0.60$; $B$ with reward 1 has probability $0.25(0.40)=0.10$ and regret $-0.40$; $B$ with reward 0 has probability $0.25(0.60)=0.15$ and regret $0.60$. Therefore

\mathbb{E}(R_1)=0.45(-0.40)+0.30(0.60)+0.10(-0.40)+0.15(0.60)=0.0500\text{ successes}.

The expected realized regret matches expected pseudo-regret, while individual realized regrets vary with both the random assignment and the Bernoulli outcome.

Interpretation, Diagnostics, and Limits

Pseudo-regret is useful when evaluating how a policy allocates across arms in a model whose mean rewards are known, such as a simulation. It holds observed outcome fluctuations apart from the expected cost of the choices. Realized regret reflects actual accumulated rewards against the same benchmark and is therefore more sensitive to chance variation. In a clinical trial, a reward may be a binary response, so regret can be expressed in expected or observed successes; if rewards are measured in another unit, the regret has that reward unit.

Neither measure is usually directly available in an ongoing real trial. The realized reward total can be recorded, but the best arm mean $\mu^*$ is unknown. Pseudo-regret also requires the true arm means. Replacing unknown means by estimates gives an estimated regret, not the exact quantity defined here; estimation error can affect both the estimated gaps and the estimated best arm. In simulation, by contrast, the data-generating means can be specified and both measures can be calculated.

Feature	Pseudo-regret	Realized regret
Uses assigned arms’ means	Yes	Only through the best-mean benchmark
Uses observed rewards	No	Yes
Can be negative?	No, when $\mu^*$ is the largest arm mean	Yes, if observed rewards exceed the benchmark
Changes when outcomes change but assignments do not?	No	Yes
Expected value under the stated model	Equals expected realized regret	Equals expected pseudo-regret

A useful diagnostic in a simulation is to calculate both measures over many independent runs. Their run-by-run values need not match, but their averages should be close when the number of runs is adequate and the model assumptions hold. Large differences in averages can signal a coding error, a mismatch between the reward generator and the means used to compute regret, or use of an outcome-dependent assignment rule that incorrectly uses information from the current reward before choosing the current arm.

The main alternative is to report cumulative observed reward, $\sum_{t=1}^{T}Y_t$, directly rather than converting it to regret. Cumulative reward is an outcome total; regret expresses that total relative to a specified benchmark. The two regret definitions serve different diagnostic purposes, but neither alone describes all clinical objectives: patient benefit, treatment safety, uncertainty, and the value of learning may require separate summaries.

Common Mistake

Common mistake: “Realized regret must be nonnegative because every assignment to a non-best arm loses reward.” This confuses expected-reward gaps with observed outcomes. An assignment to a lower-mean arm contributes a nonnegative amount to pseudo-regret, but its observed reward can still be unusually high. Realized regret subtracts all observed rewards from $T\mu^*$, so it can be negative. The correction is to use pseudo-regret for the sum of expected gaps and realized regret for the comparison based on actual outcomes.

Key takeaway: Pseudo-regret measures the expected-reward cost of the chosen arms; realized regret compares the best-arm expected benchmark with actual rewards. Under the conditional-mean model, outcome noise has mean zero, so their expectations agree even though their values in a particular run can differ substantially.

Check Your Understanding

Answer each question, then compare with the solutions below.

Two arms have means $0.70$ and $0.50$. In two assignments, the lower-mean arm is assigned once. What is pseudo-regret?
Using the means and two-assignment setup in question 1, suppose observed rewards total $2$. What is realized regret, and why can it be negative?
State the conditional-mean assumption that ensures expected realized regret equals expected pseudo-regret.
In a simulation, the average realized regret is much larger than average pseudo-regret across many runs. Give two possible explanations to investigate.

Solutions. (1) The gap for the lower-mean assignment is $0.70-0.50=0.20$, and the other assignment to the best-mean arm contributes zero, so pseudo-regret is $0.20$ expected reward units. (2) The benchmark is $2(0.70)=1.40$, so realized regret is $1.40-2=-0.60$ reward units. It is negative because the observed total exceeded the expected benchmark. (3) Conditional on the history before assignment $t$ and the selected arm $A_t=a$, the next reward must have mean $\mu_a$: $\mathbb{E}(Y_t\mid\mathcal{H}_{t-1},A_t=a)=\mu_a$. (4) Check whether the reward generator’s conditional means match the means used in the regret calculation, and whether the same benchmark and reward scale are used for both measures. Also check for an implementation error; under the stated model, their averages should agree apart from Monte Carlo variability.