Epsilon-Greedy Allocation

From estimated rewards to randomized assignments

In an adaptive trial, an allocation rule uses outcomes observed so far to choose a treatment for the next participant. Epsilon-greedy allocation makes this choice by combining two actions: it usually assigns to an arm with the highest estimated mean reward, but sometimes assigns at random to encourage exploration. Its key tuning parameter, \(\epsilon\), is the probability of taking the exploration action at a given assignment.

The phrase “explore with probability \(\epsilon\)” does not, by itself, specify the probability of assigning to each arm. This tutorial uses a particular convention: on an exploration assignment, select uniformly from all arms, including the arm or arms currently considered best. Other conventions are possible and produce different assignment probabilities. Stating the convention is essential when describing or implementing a policy.

A common choice for \(\hat{\mu}_{j,t-1}\) is the sample mean reward among the \(N_{j,t-1}\) participants assigned to arm \(j\). For a binary reward coded as 1 for success and 0 otherwise, this is the observed success proportion. The estimates must be defined before the policy can compare arms: one practical approach is to start with a randomized initialization that assigns at least one participant to each arm, then begin epsilon-greedy allocation. Alternatively, a specified prior estimate can be used, but that is a different initialization choice and should be reported.

For the rule above, the conditional probability of assigning the next participant to arm \(j\), given the observed history, is $$ P(A_t=j\mid \mathcal{H}_{t-1})= \frac{\epsilon_t}{K} +(1-\epsilon_t)\frac{\mathbb{1}(j\in G_t)}{|G_t|}, $$ where \(A_t\) is the assigned arm, \(\mathcal{H}_{t-1}\) is the information available before assignment \(t\), \(|G_t|\) is the number of currently greedy arms, and \(\mathbb{1}(j\in G_t)\) is 1 when \(j\) is in the greedy set and 0 otherwise. The first term is the probability of selection through exploration; the second is the probability of selection through exploitation. These probabilities sum to 1 across the arms.

Worked assignment probabilities

Why the rule has these probabilities

The allocation can be viewed as a two-stage random mechanism. First, a random choice determines whether to explore or exploit. If it selects exploration, each arm has probability \(1/K\). If it selects exploitation, each member of \(G_t\) has probability \(1/|G_t|\), and every other arm has probability zero. The law of total probability then gives, for any arm \(j\), $$ P(A_t=j\mid\mathcal{H}_{t-1}) =P(\text{explore}\mid\mathcal{H}_{t-1})P(A_t=j\mid\text{explore},\mathcal{H}_{t-1}) +P(\text{exploit}\mid\mathcal{H}_{t-1})P(A_t=j\mid\text{exploit},\mathcal{H}_{t-1}). $$

Substituting the probabilities of the two actions gives the stated formula: the exploration contribution is \(\epsilon_t/K\), while the exploitation contribution is \((1-\epsilon_t)/|G_t|\) for a greedy arm and zero otherwise. This also shows why the probability of selecting a non-greedy arm is not always \(\epsilon_t\). Exploration can select a greedy arm too, so the total probability of a greedy assignment is $$ \frac{\epsilon_t|G_t|}{K}+(1-\epsilon_t), $$ and the total probability of a non-greedy assignment is \(\epsilon_t(K-|G_t|)/K\).

Assumptions and the role of the exploration rate

To interpret the empirical means as information about arm performance, a basic stochastic-reward model assumes that each arm \(j\) has a stable reward distribution with mean \(\mu_j\). In the simplest setting, outcomes for participants assigned to arm \(j\) are independent draws from that arm’s distribution, with rewards coded so that larger values represent greater benefit. Only the reward for the assigned treatment is observed for a participant. The assignment probabilities are calculated from the history available before the next assignment, not from that participant’s unobserved outcome.

These assumptions can fail or need modification in a clinical trial. For example, treatment effects that vary with calendar time, interference between participants, or changes in outcome measurement can make a single stable arm mean an inadequate description. Epsilon-greedy allocation does not correct such problems; the reward model and the definition of benefit must be appropriate for the trial. Ethical, safety, and minimum-allocation requirements may also constrain which probabilities are acceptable.

With a unique greedy arm and fixed \(\epsilon>0\), each non-greedy arm receives probability \(\epsilon/K\) at every assignment, even when its estimated reward is lower. This supplies ongoing random exploration. But it also means that a fixed fraction of assignments continues to be distributed through the exploration branch, including assignments to arms that may truly be inferior. For example, if arm \(b\) is suboptimal by a mean reward gap \(\Delta_b=\mu_*-\mu_b>0\), where \(\mu_*\) is the largest arm mean, the exploration contribution to its expected reward loss at a single step with a unique greedy arm is \((\epsilon/K)\Delta_b\). Summing these contributions over a fixed horizon gives a persistent cost of exploration; exploitation mistakes can add further loss.

A changing exploration rate can reduce random exploration over time, but it must be specified as part of the policy. If \(\epsilon_t\) becomes very small too quickly, early estimation errors can leave a truly better arm receiving little allocation. If it remains high, more participants continue to be assigned at random, even after the estimates become informative. The schedule therefore affects both learning and the distribution of treatment assignments. A policy’s expected allocation to arm \(j\) over \(T\) assignments is the sum of its assignment probabilities at each step, averaged over the possible histories: $$ E[N_{j,T}]=\sum_{t=1}^{T} E\!\left[P(A_t=j\mid\mathcal{H}_{t-1})\right]. $$ The probabilities inside the expectation can vary with the observed outcomes and are themselves random across possible trial histories.

Comparison, diagnostics, and limitations

Explore-then-commit allocation separates exploration and exploitation into distinct phases: it gathers information first and then commits to a chosen arm. Epsilon-greedy allocation instead interleaves random exploration and reward-based exploitation throughout the adaptive phase. This can respond to updated estimates, but with a fixed exploration rate it continues making random assignments. Neither approach guarantees that early estimates identify the best arm in a finite trial.

Upper confidence bound allocation is another adaptive approach, but it chooses arms using estimates together with an uncertainty-based bonus rather than a fixed-probability exploration branch. That is a different mechanism; the practical distinction here is that epsilon-greedy’s exploration frequency is directly controlled by \(\epsilon_t\). The choice among approaches depends on the trial objective, horizon, acceptable treatment probabilities, and assumptions about outcomes.

Useful implementation checks include verifying that the probabilities sum to one at each assignment, that every probability is nonnegative, and that the recorded assignment matches the randomization rule and its history. Monitor arm-specific sample sizes and reward estimates, and check that the analysis records the actual assignment probabilities when they are needed for downstream evaluation. A low \(\epsilon_t\), a long run of outcomes favoring one arm, or a coding error in tie handling can all lead to unexpectedly concentrated allocation.

A common mistake is to say, “With \(\epsilon=0.20\), the chance of assigning to a non-greedy arm is 20%.” Under the convention used here, that is generally wrong: exploration selects uniformly from all arms, so some exploration assignments go to greedy arms. With \(K=3\) and a unique leader, the probability of assigning to a non-greedy arm is \(0.20(2/3)\), not \(0.20\). Another mistake is to report the exploration rate without stating how the exploration branch selects arms. If it instead selects uniformly only among non-greedy arms, the probabilities differ, and that alternative must be defined explicitly.