A Two-Arm Bernoulli Regret Calculation

Why Calculate Regret in a Two-Arm Trial?

In an adaptive trial, the allocation policy determines which treatment each participant receives, and outcomes are observed only for the assigned treatment. If the two treatments have different success probabilities, assigning a participant to the less successful treatment has an expected opportunity cost. Expected regret summarizes that cost across the trial relative to a benchmark that always assigns the treatment with the higher success probability.

This calculation is deliberately narrow: it evaluates expected reward under specified success probabilities and an allocation policy. It does not, by itself, establish which treatment is better from trial data, or say how a policy should be chosen. The probabilities and policy must be supplied or otherwise justified.

Definition: In a two-arm Bernoulli model, let $A_t\in\{1,2\}$ be the arm assigned at time $t$, and let $Y_t\in\{0,1\}$ be the observed reward, with 1 denoting success. Assume that, conditional on assigning arm $i$, the reward is Bernoulli with fixed success probability $\mu_i$: $P(Y_t=1\mid A_t=i)=\mu_i$. Write $\mu_*=\max(\mu_1,\mu_2)$ for the best arm’s success probability. For a horizon of $T$ assignments, the expected pseudo-regret is $$ R_T = T\mu_* - E\!\left[\sum_{t=1}^{T}Y_t\right]. $$ It is the expected number of successes forgone, compared with assigning the best arm on all $T$ occasions.

The benchmark is an oracle: it is defined using the true success probabilities, which may not be known to the trial policy. The model assumes the probabilities remain fixed over the horizon, each participant contributes a Bernoulli reward, and assignment is made before that participant’s outcome is observed. For the calculations below, outcomes are generated according to the assigned arm’s Bernoulli model; the policy may use past assignments and outcomes, as well as its own randomization.

Regret is expressed in expected successes, not in dollars, clinical utility, or a probability of harm unless reward has specifically been defined on that scale. It is also not the difference between the oracle’s outcomes and the particular outcomes observed in one trial. That observed difference is random; expected regret averages over the policy’s assignments and the trial outcomes.

Regret as a Gap Times an Expected Count

Let $N_i(T)=\sum_{t=1}^{T} I(A_t=i)$ be the number of assignments to arm $i$, where $I(\cdot)$ equals 1 when its condition is true and 0 otherwise. Given the assignment history, the expected reward on an assignment to arm $i$ is $\mu_i$. Consequently, the policy’s expected total reward is $\mu_1 E[N_1(T)]+\mu_2 E[N_2(T)]$. Since $N_1(T)+N_2(T)=T$, subtracting this reward from the oracle benchmark gives the arm-wise expression below.

R_T = \sum_{i=1}^{2}(\mu_*-\mu_i)E[N_i(T)].

If arm 1 is better, define the gap $\Delta=\mu_1-\mu_2>0$. Then arm 2 is the only suboptimal arm, so $R_T=\Delta E[N_2(T)]$. If arm 2 is better, the corresponding expression is $R_T=(\mu_2-\mu_1)E[N_1(T)]$. If the success probabilities are equal, the gap is zero and expected regret is zero under this benchmark, regardless of the allocation counts.

Justification: For each assignment, conditional on the assigned arm, the expected reward is that arm’s success probability. Therefore $$ E\!\left[\sum_{t=1}^{T}Y_t\right] =\sum_{i=1}^{2}\mu_i E[N_i(T)]. $$ Also, $T\mu_*=\sum_{i=1}^{2}\mu_* E[N_i(T)]$, because $E[N_1(T)+N_2(T)]=T$. Subtracting the first equality from the second yields the arm-wise regret formula. This argument does not require assignments to be independent over time; it requires the stated reward model and finite expected counts.

A policy can be adaptive and still fit this calculation. If $q_t$ denotes the conditional probability of assigning the suboptimal arm at time $t$, given the information available just before assignment, then $E[I(A_t=\text{suboptimal})]=E[q_t]$. Summing over assignments gives $E[N_{\text{suboptimal}}(T)]=\sum_{t=1}^{T}E[q_t]$. This follows by taking expectations of the conditional assignment probabilities. It is especially useful when $q_t$ depends on the observed history: average the assignment probability over possible histories rather than treating one history’s probability as fixed for the whole trial.

Worked Example: Fixed Randomization With a Known Best Arm

Suppose, hypothetically, that $\mu_1=0.70$, $\mu_2=0.55$, and the trial has $T=10$ assignments. At each assignment, the policy chooses arm 1 with probability 0.60 and arm 2 with probability 0.40, independently of past outcomes. Calculate expected regret.

Arm 1 is best, and the gap is $\Delta=0.70-0.55=0.15$ expected successes per assignment to arm 2. The expected number of assignments to arm 2 is $$ E[N_2(10)]=10(0.40)=4. $$

Thus, $$ R_{10}=(0.15)(4)=0.600 $$ expected successes. As a check, expected reward under the policy is $10[(0.60)(0.70)+(0.40)(0.55)]=10(0.64)=6.40$ successes, while the benchmark is $10(0.70)=7.00$. Their difference is $7.00-6.40=0.600$ expected successes.

Calculating Regret When Allocation Depends on Outcomes

For a history-dependent policy, the probability of assigning the suboptimal arm may vary from one assignment to the next and from one observed history to another. The expected count is obtained by averaging each conditional assignment probability over the histories that can occur. The outcomes matter twice: they contribute reward, and they can influence later assignments.

Worked Example: A Three-Assignment History-Dependent Policy

Consider a hypothetical trial with $T=3$, $\mu_1=0.60$, and $\mu_2=0.40$. Arm 1 is best, with gap $\Delta=0.20$. The policy assigns arm 1 at $t=1$. At $t=2$, it assigns arm 2 with probability 0.70 if the first outcome was a failure, and with probability 0.30 if the first outcome was a success. At $t=3$, it assigns arm 2 with probability 0.20 if the second outcome was a success, and with probability 0.50 if the second outcome was a failure. Find expected regret.

At $t=1$, arm 1 is assigned, so the probability of a failure is $1-0.60=0.40$. The probability of assigning arm 2 at $t=2$ is therefore $$ P(A_2=2)=(0.40)(0.70)+(0.60)(0.30)=0.46. $$

The second outcome is a success with probability 0.40 when arm 2 is assigned and 0.60 when arm 1 is assigned. Averaging over the assignment gives $$ P(Y_2=1)=(0.46)(0.40)+(0.54)(0.60)=0.508. $$ Thus $P(Y_2=0)=1-0.508=0.492$, and the probability of assigning arm 2 at $t=3$ is $$ P(A_3=2)=(0.508)(0.20)+(0.492)(0.50)=0.3476. $$

Since arm 2 is never assigned at $t=1$, $$ E[N_2(3)]=0+0.46+0.3476=0.8076. $$ The expected regret is $$ R_3=(0.20)(0.8076)=0.16152 $$ expected successes, or approximately 0.1615 expected successes. Averaging over histories is essential here: adding the conditional probabilities 0.70 and 0.30 directly would not give the probability of an arm 2 assignment.

The same calculation can be expressed using the policy’s expected reward. In this example, the oracle benchmark is $3(0.60)=1.80$ expected successes. The expected reward of the policy is $1.80-0.16152=1.63848$ expected successes. This is a check on the gap-times-count calculation, not a separate definition of the policy’s observed outcome.

Worked Example: A Time-Varying Allocation Schedule

Suppose, hypothetically, that $\mu_1=0.62$, $\mu_2=0.50$, and $T=12$. Arm 1 is best, with $\Delta=0.12$. A policy assigns arm 2 with probability 0.50 for the first four assignments, 0.25 for the next four, and 0.10 for the final four. The probabilities may represent scheduled randomization rates; they need not be generated by a particular algorithm.

The expected number of assignments to arm 2 is the sum of its assignment probabilities: $$ E[N_2(12)]=4(0.50)+4(0.25)+4(0.10)=2+1+0.4=3.4. $$ Therefore, $$ R_{12}=(0.12)(3.4)=0.408 $$ expected successes. The benchmark is $12(0.62)=7.44$ expected successes, so the policy’s expected reward is $7.44-0.408=7.032$ expected successes. This result depends on the stated allocation probabilities and success rates, not on whether the probability changes were triggered by outcomes or specified in advance.

Checking the Calculation and Its Limits

A reliable calculation has four ingredients: the two success probabilities, the horizon, the identity of the best arm, and the expected number of assignments to the other arm. A useful diagnostic is to calculate the expected total reward directly and verify that subtracting it from $T\mu_*$ matches the gap-times-count result. The expected regret must be nonnegative under this benchmark, and it cannot exceed $T\Delta$ when there is one suboptimal arm, because its count cannot exceed $T$.

For a policy that assigns the suboptimal arm with conditional probability $q_t$, the expected count is $\sum_t E[q_t]$, not generally $\sum_t q_t$ evaluated at one observed history. For a fixed probability $q$, this simplifies to $Tq$. A common error is to use the probability of choosing the best arm in this product: the regret gap is incurred on assignments to the suboptimal arm. Another is to report the gap alone as total regret; the gap is the expected loss per suboptimal assignment, and it must be multiplied by the expected number of such assignments.

The calculation is also limited by its assumptions. If success probabilities change over time, there is no single fixed gap unless the benchmark and arm-specific probabilities are redefined over time. If the reward is not coded so that 1 means a beneficial success, then maximizing the success probability may not represent the desired clinical objective. And a small regret value does not establish that an adaptive trial gives an unbiased or precise treatment-effect estimate: regret evaluates cumulative reward against a benchmark, not every scientific or ethical goal of a trial.

Compared with expected regret, expected total reward is an absolute measure on the same reward scale: under the stated model it is $T\mu_*-R_T$. Expected regret instead reports the shortfall from the best-arm benchmark, which makes the allocation cost explicit. Realized regret is a random quantity tied to outcomes in a particular run; the expected calculation averages over possible runs and should not be described as the number of successes certainly lost in the trial that occurred.

Key takeaway: For two fixed Bernoulli success probabilities, expected regret is the success-probability gap multiplied by the expected number of assignments to the suboptimal arm. Under an adaptive policy, compute that expected count by averaging assignment probabilities over the histories that can occur.

Check Your Understanding

Try each calculation, then compare with the solutions below.

For a hypothetical $T=8$ trial, $\mu_1=0.75$, $\mu_2=0.60$, and fixed assignment probability 0.25 to arm 2, find expected regret.
Arm 1 is best with $\mu_1=0.55$, $\mu_2=0.50$. A three-assignment policy assigns arm 2 with probabilities 0.20, 0.40, and 0.10, respectively. Find expected regret.
Suppose $\mu_1=0.40$, $\mu_2=0.65$, and $E[N_1(10)]=3$. Find expected regret and state which count belongs in the calculation.
For equal success probabilities, explain why this benchmark gives zero expected regret even if the policy assigns the arms in unequal numbers.

Solutions. (1) Arm 1 is best, $\Delta=0.75-0.60=0.15$, and $E[N_2(8)]=8(0.25)=2$. Hence $R_8=(0.15)(2)=0.300$ expected successes. (2) The expected number of arm 2 assignments is $0.20+0.40+0.10=0.70$. The gap is $0.55-0.50=0.05$, so $R_3=(0.05)(0.70)=0.035$ expected successes. (3) Arm 2 is best, so count assignments to arm 1: $\Delta=0.65-0.40=0.25$, and $R_{10}=(0.25)(3)=0.750$ expected successes. (4) If $\mu_1=\mu_2=\mu_*$, then each arm’s gap $\mu_*-\mu_i$ is zero. Thus $R_T=\sum_i(\mu_*-\mu_i)E[N_i(T)]=0$, regardless of the allocation counts.

A Two-Arm Bernoulli Regret Calculation

What You'll Learn