Bandits and Exploration

A bandit chooses an action, observes its reward, and uses that feedback to choose again. A recommendation slot might offer one of several messages; the reward might be a click. Only the chosen action’s reward is observed. The policy must balance learning about uncertain options with earning reward now. A fixed-allocation experiment and a bandit serve different decision goals, but neither guarantees better reward or better inference in every setting.

An arm is an available action. Exploration tries actions that may be useful but are uncertain; exploitation chooses according to current reward estimates. The first experiment assumes five fixed arms, independent Bernoulli rewards, immediate feedback, and stationary success probabilities \(\mu_a\). Actions do not change future users or the reward mechanism. If actions alter future states or retention, a one-step bandit objective may miss the relevant consequences.

We measure cumulative pseudo-regret, \(R_T=\sum_{t=1}^T(\mu_* - \mu_{A_t})\), where \(A_t\) is the chosen arm and \(\mu_*=\max_a\mu_a\). Choosing a 0.10 arm instead of a 0.15 arm costs 0.05 expected rewards per pull, or 5 across 100 such pulls. This uses the simulator’s known means; actual clicks fluctuate. Regret relative to a best fixed arm is a different benchmark from an oracle that knows each user’s context or each future change.

Greedy chooses the largest sample mean. Here unseen arms receive an optimistic value of 1 and ties go to the lowest index. Epsilon-greedy chooses uniformly with probability 0.10 and otherwise acts greedily. UCB first tries every arm, then maximizes \(\hat\mu_a+\sqrt{2\log(t)/n_a}\), adding a bonus for uncertainty. Thompson sampling starts with independent Beta(1,1) priors and samples from Beta(1+s,1+n−s) after n pulls and s successes. After 3 successes in 10 pulls, that posterior is Beta(4,8). It chooses the largest sampled value; its probability of selecting an arm equals that arm’s probability of being best under the maintained posterior.

Comparing exploration rules

The helper simulates independent runs in parallel: rows of its count arrays are runs and columns are arms. It still makes one decision at a time within each run. Reusing a seed across policies does not pair their complete reward histories, since policies consume random draws differently.

import numpy as np

def simulate(policy, probs, T=20000, reps=300, seed=0, after=None, window=None):
    probs = np.asarray(probs)
    K = len(probs)
    if policy not in {"uniform", "greedy", "eps", "ucb", "thompson"}:
        raise ValueError("unknown policy")
    if window is not None and (policy != "thompson" or window < 1):
        raise ValueError("window requires Thompson sampling and a positive length")
    g = np.random.default_rng(seed)
    rows = np.arange(reps)
    n = np.zeros((reps, K), dtype=int)
    successes = np.zeros_like(n)
    pulls = np.zeros_like(n)
    reward = np.zeros(reps)
    regret = np.zeros(reps)
    late_best = np.zeros(reps)
    if window is not None:
        action_history = np.empty((window, reps), dtype=int)
        reward_history = np.empty((window, reps), dtype=int)
    for t in range(T):
        p = probs if after is None or t < T // 2 else np.asarray(after)
        means = np.divide(successes, n, out=np.ones_like(n, dtype=float), where=n > 0)
        if policy == "uniform":
            action = g.integers(K, size=reps)
        elif policy == "greedy":
            action = means.argmax(1)
        elif policy == "eps":
            action = np.where(g.random(reps) < 0.10, g.integers(K, size=reps), means.argmax(1))
        elif policy == "ucb":
            if t < K:
                action = np.full(reps, t)
            else:
                action = (means + np.sqrt(2 * np.log(t + 1) / n)).argmax(1)
        else:
            action = g.beta(1 + successes, 1 + n - successes).argmax(1)
        r = (g.random(reps) < p[action]).astype(int)
        if window is not None:
            slot = t % window
            if t >= window:
                old = action_history[slot]
                n[rows, old] -= 1
                successes[rows, old] -= reward_history[slot]
            action_history[slot] = action
            reward_history[slot] = r
        n[rows, action] += 1
        successes[rows, action] += r
        pulls[rows, action] += 1
        reward += r
        regret += p.max() - p[action]
        if t >= T // 2:
            late_best += action == p.argmax()
    return dict(n=n, successes=successes, pulls=pulls, reward=reward,
                regret=regret, late_share=late_best / (T - T // 2))

probs = np.array([0.10, 0.12, 0.15, 0.13, 0.11])
print("policy       mean regret  best-arm share  share below 0.30")
for policy in ("uniform", "greedy", "eps", "ucb", "thompson"):
    result = simulate(policy, probs)
    share = result["pulls"][:, probs.argmax()] / 20000
    print(f"{policy:10s} {result['regret'].mean():12.1f} {share.mean():15.4f} {(share < .30).mean():17.4f}")
# policy       mean regret  best-arm share  share below 0.30
# uniform           559.9          0.2001            1.0000
# greedy            744.0          0.1208            0.8767
# eps               153.2          0.7277            0.1167
# ucb               377.0          0.4119            0.0033
# thompson           98.9          0.8262            0.0133

The rows average 300 simulated runs of 20,000 pulls. The low-share column counts runs that allocate less than 30% of pulls to the best arm. It is a descriptive threshold, not a test for permanent lock-in: uniform random allocation is expected to put only 20% on that arm. Greedy can stop revisiting an underestimated arm, though its chosen arm can still change as new rewards arrive. Initialization and tie-breaking are part of the policy compared here.

Uniform allocation has expected pseudo-regret 20,000 × (0.15 − 0.122) = 560; the simulated mean is 559.9. Greedy reaches 744.0 in this setup and Thompson sampling 98.9. Compare pseudo-regret with the best-arm share: allocating more pulls to the best arm often helps, but the cost of the other pulls also depends on their reward gaps. Thompson sampling uses uncertainty in its posterior to explore. Its performance depends on the reward model, prior, and horizon; the table does not establish a universal ranking.

This UCB bonus can spend substantial traffic on close alternatives at the displayed horizon. A low fraction of low-share runs does not prove that the ranking has been learned, and changing the horizon or gaps does not guarantee a particular reversal. With a fixed positive epsilon and unequal arm means, uniform exploration alone contributes regret proportional to the horizon. UCB and Thompson sampling have sublinear-regret results under appropriate stochastic assumptions, but those asymptotic statements do not determine this finite table.

Reward and effect estimation under adaptive allocation

The next comparison uses two stationary arms with probabilities 0.10 and 0.11, a fixed horizon, and 400 independent runs. Equal allocation is simulated directly with binomial totals. Thompson sampling updates after each reward. Both rows use the same plug-in normal interval and two-sided rejection calculation, so a difference in test formulas does not explain the comparison. The interval’s calibration on adaptive data is precisely what is being checked.

from scipy import stats

def summarize(label, n, successes, truth):
    if (n == 0).any():
        raise ValueError("An arm was never observed; its naive mean is unavailable")
    means = successes / n
    effect = means[:, 1] - means[:, 0]
    se = np.sqrt((means * (1 - means) / n).sum(1))
    if (se == 0).any():
        raise ValueError("Degenerate normal approximation")
    reject = np.abs(effect / se) > stats.norm.ppf(.975)
    covered = np.abs(effect - truth) <= stats.norm.ppf(.975) * se
    print(f"{label:10s} reward {successes.sum(1).mean():7.1f}  effect {effect.mean():+.5f}"
          f"  sd {effect.std(ddof=1):.5f}  naive reject {reject.mean():.4f}  coverage {covered.mean():.4f}")

for probs in (np.array([.10, .11]), np.array([.10, .10])):
    print(f"true difference {probs[1] - probs[0]:.2f}")
    counts = np.full((400, 2), 10000)
    fixed = np.random.default_rng(31).binomial(counts, probs)
    summarize("A/B 50/50", counts, fixed, probs[1] - probs[0])
    ts = simulate("thompson", probs, reps=400, seed=31)
    summarize("Thompson", ts["n"], ts["successes"], probs[1] - probs[0])
# true difference 0.01
# A/B 50/50  reward  2102.9  effect +0.00949  sd 0.00427  naive reject 0.5975  coverage 0.9475
# Thompson   reward  2163.5  effect +0.01332  sd 0.01494  naive reject 0.4975  coverage 0.8975
# true difference 0.00
# A/B 50/50  reward  2002.2  effect -0.00043  sd 0.00430  naive reject 0.0625  coverage 0.9375
# Thompson   reward  1998.8  effect +0.00011  sd 0.01207  naive reject 0.1425  coverage 0.8575

With a true difference of 0.01, the Thompson row earns 2,163.5 rewards on average versus 2,102.9 for equal allocation, but its naive effect estimates average 0.01332. Under the null, its naive rejection rate is 14.25% and interval coverage is 85.75%; the corresponding equal-allocation estimates are 6.25% and 93.75%. These results demonstrate a calibration problem for this adaptive procedure and this naive analysis. The table reports realized reward, the mean estimated difference, variation across runs, naive rejection frequency, and empirical coverage of the true difference. The effect case measures detection; the null case checks false alarms. A rejection frequency under a nonzero effect is not a power comparison at a common error rate unless calibration also holds. With 400 repetitions, a rate near 5% has Monte Carlo standard error about 1.1 percentage points.

Adaptive allocation makes arm sample counts depend on earlier rewards. Unlucky early observations can leave an arm with a small, unrepresentative sample, and unequal counts also reduce precision. The usual fixed-sample standard error need not describe the resulting estimator’s sampling distribution. This does not imply that every bandit estimate is biased upward or that valid inference is impossible: planned exploration, logged selection probabilities, and estimators and intervals designed for adaptive data can support inference. An independent fixed-allocation evaluation sample is another option.

Decision goal	Possible design	Requirement
Earn reward while learning	A bandit policy	A suitable reward, horizon, and exploration budget
Estimate a treatment effect	Fixed allocation or adaptive inference	An estimator and uncertainty calculation valid for the allocation
Limit harmful exposure	Safety monitoring and stopping rules	Explicit harm criteria; reward optimization alone is not a safety guarantee
Personalize actions	A contextual bandit	Useful pre-action features and supported exploration

Evaluating a policy you never ran

Off-policy evaluation estimates a target policy’s value from actions chosen by a logging policy. Let \(b(a\mid x)\) be the logged probability of selecting action a for context x, and \(\pi(a\mid x)\) the target probability. Inverse propensity scoring (IPS) averages \(w_i r_i\), with \(w_i=\pi(a_i\mid x_i)/b(a_i\mid x_i)\). For a deterministic target, the numerator is 1 on matching actions and 0 otherwise. Self-normalized IPS (SNIPS) divides the weighted reward sum by the weight sum; that random denominator generally introduces finite-sample bias.

n = 60000
g = np.random.default_rng(0)
x = g.integers(2, size=n)
target_reward = np.where(x == 0, .20, .80)
p_arm1 = np.where(x == 0, .90, .10)
a_log = (g.random(n) < p_arm1).astype(int)
r = (g.random(n) < np.where(a_log == 1, target_reward, .10)).astype(float)
match = a_log == 1
weights = match / p_arm1
print("population target value 0.5000; limiting match-only value 0.2600")
print(f"target expectation on sampled contexts {target_reward.mean():.4f}")
print(f"mean logged reward {r.mean():.4f}")
print(f"match-only reward {r[match].mean():.4f}; group-1 share among matches {x[match].mean():.4f}")
print(f"IPS {(weights * r).mean():.4f}; SNIPS {(weights * r).sum() / weights.sum():.4f}")
# population target value 0.5000; limiting match-only value 0.2600
# target expectation on sampled contexts 0.4998
# mean logged reward 0.1814
# match-only reward 0.2612; group-1 share among matches 0.1001
# IPS 0.5028; SNIPS 0.5025

Here half the contexts are group 0 and half are group 1 in the population. The target always chooses arm 1, whose success probabilities are 0.20 and 0.80 in the two groups. Its population value is 0.50. The logger chooses that arm with probabilities 0.90 and 0.10, respectively. Matching rows therefore contain about 90% group 0 and only 10% group 1; their limiting mean is 0.90 × 0.20 + 0.10 × 0.80 = 0.26. Dependence of the logger on observed features does not make matching unbiased.

IPS gives matching group-0 rows weight 1/0.9 and matching group-1 rows weight 1/0.1. Within each context, averaging over the logged action cancels its selection probability: E[1{A=1}R/b(1|X) | X] = E[R(1)|X]. Matching alone works when its selection probability is constant across contexts, or under other conditions that make the selection harmless; it is not generally justified by conditioning the logger on features.

The propensity is the probability of choosing the action before observing its reward. For epsilon-greedy with a unique greedy arm, it is 1−epsilon+epsilon/K for that arm and epsilon/K for each other arm. A Thompson posterior draw is not a propensity: the required probability is that an arm wins the posterior sampling competition. Recording the sampled value or the observed fraction of historical pulls does not supply that conditional probability.

This calculation requires correctly recorded selection probabilities, support for every target action in relevant contexts, and rewards observed without unaccounted selection. The logging decision must be randomized conditional on the information used in the analysis; the context and reward mechanism must match the target evaluation setting. An adaptive logger needs probabilities conditional on the history used to choose each action and corresponding uncertainty methods. A fixed target should be evaluated on data not used to select it, or with an analysis that accounts for that selection. A deterministic logger can evaluate a target that agrees on its support, but cannot identify rewards for unsupported alternative actions without additional assumptions.

References

• Russo et al., A Tutorial on Thompson Sampling
• Nie et al. Adaptively Collected Data and the Bias of the Sample Mean
• Wang et al. Optimal and Adaptive Off-policy Evaluation in Contextual Bandits.

For fixed-allocation experiments and planned interim decisions, see A/B Testing and Experiment Design.