Is IMED the same as greedy selection?

No. Its count and divergence terms can favor sampling an arm with a lower empirical mean.

Does it require a neural network?

No. The original policy is a statistical bandit algorithm.

Does it know the best true reward mean?

No. It uses observed distributions and the current empirical best mean.

AI Glossary / Mathematics and optimization / Advanced

Algorithm IMED

Definition

Algorithm IMED, short for Indexed Minimum Empirical Divergence, is a method for choosing actions in a stochastic multi-armed bandit problem. It balances using actions that currently look rewarding with gathering more evidence about alternatives. Its score combines the number of observations of an action with an information-based measure of how plausible it is that the action could outperform the current empirical leader.

What it means

An “arm” is an available action, such as one of several fixed interface variants. Selecting it reveals a reward for that action; the rewards of unselected actions remain unknown. The challenge is to learn while making choices, rather than collecting a complete labeled dataset first.

IMED is a specific policy introduced by Honda and Takemura, not a general name for adaptive experimentation. The original analysis concerns stochastic rewards with a known upper bound and technical regularity assumptions. Its guarantees should not be transferred automatically to changing audiences, adversarial outcomes, or arbitrary unbounded rewards.

How it works

Start by sampling every arm. For arm i, retain its observation count N_i and empirical reward distribution F_i. Let m be the largest empirical mean across the arms.

The IMED score is N_i × D_inf(F_i,m) + ln(N_i). D_inf is the smallest Kullback - Leibler divergence from the observed distribution to an allowed distribution whose mean exceeds m. Choose an arm with the smallest score and update after observing its reward.

The divergence term penalizes alternatives that the evidence makes unlikely to beat the leader. The logarithmic count term discourages endlessly selecting an already heavily sampled arm. Unlike scores computed solely from one arm's history, IMED's score also depends on the empirical leader across all arms.

Three practical examples

1. An experiment compares fixed onboarding messages using a clearly defined binary completion reward. IMED is a candidate allocation rule if the stationary bandit assumptions are a reasonable approximation.

2. A simulation studies how different exploration policies behave when one action has received few observations. The reward distributions are specified, allowing regret to be measured against their true best mean.

3. A researcher compares policies for a process with rewards bounded above but potentially negative. The reward model and moment conditions are checked against the original analysis rather than assuming binary rewards are required.

Think of it this way

Think of revisiting competing explanations for which service counter is fastest. A counter with a disappointing record may still deserve another try if that record is very small. IMED formalizes a related evidence - sampling trade-off. The analogy does not reproduce its divergence calculation or account for queues that change because people follow the recommendation.

Worked example

Consider binary rewards with a success worth 1 and a failure worth 0. Arm A has 8 successes in 10 observations, giving empirical mean 0.8. Arm B has 2 successes in 4 observations, giving mean 0.5. The current best empirical mean is therefore m = 0.8.

For this Bernoulli example, the divergence for a lower mean p is d(p,m) = p ln(p/m) + (1−p) ln((1−p)/(1−m)), using natural logarithms. The leader's divergence is zero as an infimum.

A's score is ln(10), approximately 2.3026. B's divergence is 0.5 ln(0.5/0.8) + 0.5 ln(0.5/0.2), approximately 0.2231. Its score is 4 × 0.2231 + ln(4), approximately 2.2789. IMED selects B because the smaller score wins, despite B's lower empirical success rate.

Suppose the next B outcome is a failure. B now has 2 successes in 5 observations, so p = 0.4. Its divergence against 0.8 is approximately 0.3819 and its new score is 5 × 0.3819 + ln(5), approximately 3.5190. A's unchanged score is lower, so A is selected next. These hand calculations illustrate two choices, not a performance comparison or a prediction of future outcomes.

Illustrative case study

Fictional case: Linden Software prototypes adaptive selection among several help prompts. Its team initially proposes using clicks as the reward, but reviewers notice that a click can reflect confusion rather than success.

The team defines a completion event, specifies how delayed outcomes are recorded, and tests the policy in a stationary simulator before considering live allocation. It also separates device groups when checking whether one shared reward distribution is defensible. The case illustrates that a mathematically specified selection rule still depends on a well-defined experiment; it asserts no increase in engagement or revenue.

Common misconceptions and mistakes

Do not select the largest score: IMED minimizes this index. Also do not replace the distributional divergence with an arbitrary distance between means; that changes the algorithm.

The empirical best arm need not be the truly best arm. A choice that looks inferior under current averages can be purposeful exploration.

An asymptotic regret guarantee is not a promise to choose correctly on every round or to outperform every policy on a short experiment. Distribution drift, delayed feedback, contextual information, and operational constraints require separate treatment. None is resolved simply by giving an existing policy a new reward label.

Business use

IMED is most relevant when repeated choices, partial feedback, and a credible stochastic reward model are central to the problem. Compare it with alternative bandit policies using realistic horizons, computation costs, and evaluation metrics.

Retain the decision history, observed rewards, model assumptions, and handling of missing outcomes. An adaptive allocation should not be analyzed as if every variant received a fixed random sample without considering the sampling process. Choose an evaluation method appropriate to how the observations were collected.

Check your understanding

Why is B selected first in the worked example despite a 0.5 average against A's 0.8?

Answer: Its IMED score, about 2.2789, is smaller than A's 2.3026. The rule accounts for limited evidence, not only observed averages.

Related terms

Empirical distribution
Regret
Thompson sampling
Multi-armed bandit
exploration–exploitation
KL divergence
UCB
stochastic optimisation

Learn next

Study stochastic bandits and KL divergence next. Recalculate the example with equal observation counts, and explain how changing evidence affects the score without changing the rule to minimize it.

Sources

Primary reference: Honda and Takemura, “Non-Asymptotic Analysis of a New Bandit Algorithm for Semi-Bounded Rewards,” https://jmlr.org/papers/volume16/honda15a/honda15a.pdf. Algorithm 1 and its assumptions were opened and read. Bernoulli calculations and the fictional case are original teaching illustrations.

Previous: Algorithm BSTW Next: Algorithm selection