Does the algorithm know the true reward probabilities?

No; they were supplied only to evaluate the teaching example.

Can it choose the worse action?

Yes. Finite samples can reverse the apparent ranking.

Can m use the entire horizon?

Yes, if Km = T, but then no rounds remain for exploitation.

AI Glossary / Mathematics and optimization / Advanced

Explore-then-commit algorithm

Definition

The explore-then-commit algorithm is a strategy for a stochastic multi-armed bandit problem that separates learning from exploitation. In its basic fixed-budget form, it samples every available action a specified number of times, compares the observed average rewards, and chooses one action for every remaining round. The chosen action is the empirical winner, which need not be the action with the highest true expected reward.

What it means

A business may need to learn which of several alternatives works best while also benefiting from its choices. Explore-then-commit addresses this by setting aside an initial trial period and then making a fixed choice for the rest of a defined horizon.

Its simplicity creates a trade-off. A small trial leaves more time to use the selected action but can select the wrong one. A large trial provides more evidence while spending more rounds on alternatives that may be inferior. The basic policy does not revisit its choice after commitment.

How it works

Choose the number of actions K, the total horizon T, and the exploration count m per action, with Km <= T. Sample each action m times and calculate its empirical mean reward. Select an action with the highest empirical mean, using a specified rule to resolve ties. Play that action for the remaining T - Km rounds.

The usual stochastic model assumes each action has a fixed reward distribution and that new rewards are sampled according to that model. Analysis often separates regret into losses incurred while exploring and losses from committing to an inferior action. The latter depend on both the chance of choosing incorrectly and the number of rounds left.

Three practical examples

1. Interface selection: A team tries two interface variants for a predetermined number of interactions each, then uses the empirical winner for the remaining campaign. A noisy early lead can persist operationally because the policy does not reopen the comparison.

2. Routing experiment: A service tests several routing choices using a common reward definition, such as a suitably defined latency score. If traffic conditions change after commitment, the fixed-distribution assumption becomes questionable and the original analysis may no longer describe the deployment.

3. Recommendation prototype: A developer compares a fixed list of recommendation strategies before choosing one for a short demonstration. The trial can illustrate sequential decision-making, but its winner is not automatically a statistically established or universally best recommendation method.

Think of it this way

Think of tasting each of several recipes a fixed number of times, choosing the one with the best average rating, and serving only that recipe for the rest of an event. More tastings can improve the evidence, but consume part of the event. An unusually favorable set of early ratings can also lock in the wrong recipe.

Worked example

Consider an original two-action model with 20 rounds. Action A produces a reward of one with probability 0.6 and zero otherwise. B produces one with probability 0.4. Rewards are independent across pulls. These probabilities are known to us for analysis but unknown to the learner.

Use m = 2 pulls per action and choose uniformly at random if the observed means tie. Exploration therefore consumes four rounds, leaving sixteen for commitment.

One possible exploration record is A: 1,0 and B: 1,1. The observed means are 0.5 and 1, so the algorithm commits to B even though A has the higher true mean. Later disappointing B rewards do not change this basic policy's choice.

Across all possible exploration records, exact enumeration gives probability 0.352 of committing to B, including the random tie rule. The probability of choosing A is 0.648.

The true reward gap is 0.6 - 0.4 = 0.2. During exploration, the two B pulls contribute expected regret 2(0.2) = 0.4. During commitment, expected regret is 16(0.2)(0.352) = 1.1264. Total expected regret is therefore 1.5264.

An oracle always choosing A would earn expected total reward 20(0.6) = 12. This explore-then-commit policy earns 12 - 1.5264 = 10.4736 in expectation. These are averages over reward randomness and tie-breaking, not guaranteed totals for the single displayed record. All sixteen four-pull exploration records were enumerated using their exact probabilities.

Illustrative case study

In a fictional online service, a team reserves an initial period for comparing two onboarding flows, then plans to use the observed winner for the rest of a campaign. A favorable trial result leads to a commitment, but subsequent performance appears weaker than expected.

The analyst explains that the basic algorithm has no built-in mechanism for restarting exploration. The team reviews whether the reward definition, user population, and campaign conditions remained comparable. It also distinguishes a commitment rule from a claim that the trial has proved one flow superior.

For the next campaign, the team explicitly chooses between a fixed commitment policy and an adaptive strategy.

Common misconceptions and mistakes

The largest observed mean is not necessarily the largest true mean. Commitment does not mean rewards become deterministic. More exploration reduces the remaining exploitation horizon, so exploration length cannot be judged only by the amount of data collected.

Do not report the worked example's expected regret as a guaranteed loss in each run. Do not silently change the tie rule: it affects selection probabilities in discrete-reward examples. A policy that continues comparing or switching after commitment is a different variant and should be described accordingly.

Business use

Explore-then-commit offers a simple baseline for decisions with a clear trial period and deployment horizon. Teams should record action definitions, reward measurement, exploration allocation, tie-breaking, and the planned commitment duration. They should also assess whether conditions are likely to remain stable. The method can make a decision process explicit, but it does not replace experiment design, measurement validation, or monitoring of changing conditions.

Check your understanding

How many rounds remain after exploring two actions twice in a 20-round horizon?

Answer: Sixteen.

Why does the displayed record select B?

Answer: B has the larger empirical mean.

What does 0.352 represent?

Answer: The probability of committing to B across possible exploration records and the specified tie rule.

Related terms

Regret
Upper confidence bound
Thompson sampling
Multi-armed bandit
exploration and exploitation
empirical mean

Learn next

Reproduce the sixteen-record calculation, then change the tie rule or exploration count. Compare both selection error and total expected regret. Next examine algorithms that continue balancing exploration and exploitation throughout the horizon.

Regret

Sources

Tor Lattimore and Csaba Szepesvari, Bandit Algorithms tutorial, explore-then-commit policy and regret decomposition: https://tor-lattimore.com/downloads/talks/2018/aaai/finite-armed-bandits.pdf

The Bernoulli example, exact enumeration, and fictional onboarding case are original illustrations.

Previous: Exploratory forecasting Next: Exploring starts