Trading off rewards and errors in multi-armed bandits

In plain words

A bandit problem is a series of choices among several options (arms) whose payoffs are unknown until you try them. Usually the goal is to collect as much payoff as possible, which means trying the best-looking option most of the time. A different goal is to learn each option's average payoff accurately, even if that costs some payoff along the way. This paper argues that a designer often wants both: participants should get a good experience, and the designer should still learn reliable facts about every option. Think of a teacher who must teach well today and also learn which lesson designs actually work.

The paper combines the two goals into one score with a weight w between 0 and 1. A larger w favours payoff, a smaller w favours accurate estimates. Its method, ForcingBalance, first makes sure every option is tried a minimum number of times. After that, it keeps its choices close to the mix of options that scores best given what it has learned so far. The authors show it reaches a good trade-off over time and test it on synthetic data and on data from an educational math game.

TL;DR

• Standard bandit methods chase reward and learn little about the other options; pure-accuracy methods learn well but give up reward.
• The paper scores a choice mix by w * reward - (1 - w) * error, where the error term is a root-mean-square error scaled by sqrt(n) §2, eq. 3.
• ForcingBalance forces minimum pulls per arm, then tracks the optimal mix of the estimated objective §3.
• Regret is bounded in three phases, with an asymptotic rate of n^-1/2 §4, thm. 1. All results are author-reported, and the bound does not cover the lambda_min = 0 setting used in the experiments.

Problem

A designer runs a multi-armed bandit with K arms, each with unknown mean mu_i and variance sigma_i^2. Two objectives conflict. Cumulative reward wants to pull the best arm almost always, while accurate estimation of every arm's mean wants balanced sampling §1, §2. The paper frames this as a practical concern in education and medicine, where poor early experience can make users leave §1. Known results already show that low regret and best-arm identification cannot both be optimal §1, citing Bubeck et al. 2009.

The paper's setting assumes arms with bounded support in [0, 1]. The results are said to extend to sub-Gaussian arms, which the experiments use §2.

Method

Objective. For a fixed pull sequence I_n, the average reward is rho and the estimation error is eps, defined by equations 1 and 2 §2, eq. 1 §2, eq. 2. The error is multiplied by sqrt(n) so that its size is comparable to reward at any horizon §2. The combined objective is f_w = w * rho - (1 - w) * eps §2, eq. 3. The paper then works on the continuous relaxation over allocations lambda in the simplex §2, eq. 4:

f_w(lambda) = w * sum_i lambda_i * mu_i
              - ((1 - w) / K) * sum_i sigma_i / sqrt(lambda_i)

For w = 1 the problem is pure reward; for w = 0 it is pure error minimisation. The paper studies w in (0, 1) §2. The optimal allocation lambda* is unique when w < 1 and it always exists §2. The authors note that lambda* tends to concentrate on the best-mean arm when w is large, and to follow standard deviations when w is small §2. The objective is strongly concave and smooth on the restricted simplex §2, lem. 1.

Why not UCB. A naive optimistic bound on f_w with confidence intervals on means and standard deviations (equation 5) fails in the authors' analysis. For small w, it lowers variance estimates, starves arms with wide intervals, and so never corrects its estimates §3. The authors' experiments in the appendix support this app. C.

ForcingBalance. The algorithm is shown as the paper's "forcing algorithm" §3. It is inspired by GAFS of Antos et al. §3.

# ForcingBalance  [§3]
# Input: forcing parameter eta, weight w, lower bound lambda_min, horizon n
# Output: arm pulled at each step t

def forcing_balance(eta, w, lambda_min, n):
    # Start with no pulls and no reward samples for any arm  [§3]
    counts = zeros(K)
    samples = [[] for _ in range(K)]
    for t in range(1, n + 1):
        # Least-pulled arm U_t = argmin_i T_{i,t}  [§3]
        least = argmin(counts)
        if counts[least] < eta * sqrt(t):
            # Forcing: pull the least-pulled arm  [§3]
            arm = least
        else:
            # Empirical means and standard deviations  [§3]
            means = sample_means(samples)    # (K,)
            stds = sample_stds(samples)      # (K,)
            # Allocation maximising f_w on the restricted simplex  [§3] [eq. 4]
            lambda_hat = argmax_simplex(f_w, means, stds, w, lambda_min)
            # Empirical share of pulls so far  [§3]
            lambda_tilde = counts / t
            # Tracking: pull the arm furthest below its target share  [§3]
            arm = argmax(lambda_hat - lambda_tilde)
        # Pull the arm and record the reward  [§3]
        reward = pull(arm)
        samples[arm].append(reward)
        counts[arm] += 1

# Relaxed objective over allocations  [§2] [eq. 4]
def f_w(lambda_, means, stds, w):
    # Reward term: w times the allocation-weighted mean  [§2] [eq. 4]
    reward = w * sum(lambda_ * means)
    # Error term: (1 - w) over K times sum of sigma_i / sqrt(lambda_i)  [§2]
    error = (1 - w) / len(lambda_) * sum(stds / sqrt(lambda_))
    return reward - error

Notes on the steps:

• Sample variance. The paper estimates each variance with the pairwise-difference formula sigma_hat^2 = sum_{s,s'} (X_s - X_s')^2 / (2 T (T - 1)) §3. By our algebra this equals the usual unbiased sample variance with denominator T - 1. The value of sigma_hat used in f_w is the square root of this; the paper writes the bounds on sigma_hat §4, prop. 1 but does not spell out this step.
• Restricted simplex. The optimisation runs over {lambda_i >= lambda_min, sum lambda_i = 1} §3. The paper states that lambda_min = 0 is a viable algorithmic choice, because f_w always has a maximiser on the full simplex §3.
• Forcing rule. Forcing fires when the least-pulled arm has fewer than eta * sqrt(t) pulls §3. Forcing is what guarantees each arm is pulled at a rate of order sqrt(n) §4 proof sketch, app. B.
• Tracking rule. Among arms, it selects argmax_i (lambda_hat_i - lambda_tilde_i), which is the arm furthest below its estimated target. The paper says this rule is more efficient than the GAFS ratio rule, and gives an experiment in the appendix to support it §3 app. C.

Bound. With probability 1 - delta, where delta_n = delta / (4 K n (n + 1)) and under Assumption 1 (the optimal allocation lies in the restricted simplex), the pseudo-regret R_n = f* - f_w(lambda_tilde_n) obeys three phases §4, thm. 1:

• R_n <= 1 for n <= n_0, with n_0 = K (K eta^2 + eta sqrt(K) + 1) §4, thm. 1.
• R_n is at most 43 K^(5/2) (beta / alpha) sqrt(log(2/delta_n) / (eta lambda_min)) n^(-1/4) for n_0 < n <= n_2 §4, thm. 1.
• R_n is at most 153 K^(5/2) (beta / alpha) sqrt(log(2/delta_n) / (lambda_min lambda*_min)) n^(-1/2) for n > n_2 §4, thm. 1.

Here alpha and beta are the strong-concavity and smoothness constants of f_w §2, lem. 1, and lambda*_min is the smallest entry of lambda*. The theorem requires eta <= 21 §4, thm. 1.

Hyperparameters

Results

Author-reported. The setups are the two experiments in the paper.

Synthetic setting, K = 5, w = 0.9, eta = 1, lambda_min = 0, 200 runs §5.1.

The reward-only optimum pulls arm 5 always. The error-only optimum favours arm 4, which has the largest variance; for w = 0 its share is above 0.41 §5.1. The paper reports that the rescaled regret sqrt(n) R_n rises like sqrt(n) early, like n^(1/4) next, and then levels off. This matches the three phases of the bound §5.1 §4, rem. 1. The tracking figure shows that the estimated allocation converges quickly to lambda* and the actual allocation follows with a delay §5.1.

Educational data, K = 64, n = 25,000, eta = 1, 100 runs §5.2. Players in the Treefrog Treasure math game were given one of 64 number-line conditions, and the outcome is persistence §5.2. Forcing is compared with UCB, GAFS-MAX adapted to minimise error, and uniform sampling (Unif). All values come from the paper's table §5.2:

The authors read these numbers as follows. UCB gets the highest reward but is poor at estimation and ranking. GAFS is accurate but collects less reward. ForcingBalance has the smallest regret in both rows, and at w = 0.95 it has more reward than GAFS while keeping the ranking close §5.2. The table's headers are as printed in the paper; see Pitfalls for the normalisation.

Paper vs code

No official code.

The paper's source has no repository link and no project page. We searched the GitHub repository API for "ForcingBalance", for "rewards errors bandits forcing", for "Erraqabi bandit", for "active exploration bandit", for "sequel bandit" inside the SequeL organisation, and for "educational bandit reward estimation". None returned a repository owned by an author or their lab. The source contains a commented-out link to the educational dataset, which is not in the text, so we don't treat it as released.

Pitfalls

• Theory and experiments disagree on lambda_min. Theorem 1 needs lambda_min > 0 and lambda*_min >= lambda_min §4, asm. 1. The experiments run with lambda_min = 0 §5.1. The authors say the bound does not directly cover this case and that Lemma 2 fails there §4, rem. 2. The experiments therefore don't test the guarantee; they only show behaviour.
• Two versions of n_2. The main text gives n_2 with lambda_min^2 in the denominator §4, thm. 1. The appendix restatement of the same theorem gives lambda_min^4 app. B. Use the main-text statement only if you can't check the proof, and flag the difference.
• Unstated constant. The C in n_2 is a numerical constant that is not given §4, thm. 1. The bound is therefore not computable.
• Tracking index. T_{i,t} counts pulls before step t (sum to t - 1) §2, but the tracking rule uses lambda_tilde_{i,t}. Whether that share is over t or t - 1 pulls is not stated. Use the same convention in both places.
• Notation drift. The algorithm mixes n and t for the same index, and writes sigma_hat^2 where the bounds use sigma_hat §3 §4, prop. 1. Implement sigma_hat = sqrt(sigma_hat^2).
• Variance with few samples. The pairwise formula divides by T (T - 1), so it needs T >= 2. With eta = 1, the forcing test T < eta * sqrt(t) makes this hold whenever t >= 2 §3. For smaller eta the paper does not say how T = 1 is handled. Our inference from the formula; the paper does not state it.
• Boundary of the simplex. Footnote 1 of §2 says f_w is -infinity when an entry of lambda is zero but its arm has nonzero variance. A gradient-based solver therefore can't reach that boundary. With lambda_min = 0 the solver must handle it, and the paper does not say how it does so §2 §3.
• Normalisation of eps in the results. The text says eps is normalised by the largest standard deviation §5.2. The table header says eps / var_max §5.2. Check which one a reproduction uses.
• Typo in the Pareto text. For w = 0.95 the text gives lambda*_4 = 0.0484 and lambda*_4 = 0.9326 §5.1. The second should probably be lambda*_5. Our inference.
• Regret for baselines. The text says UCB, GAFS and Unif don't depend on w, but their regret is computed against different lambda* for each w §5.2. Reported R_n for UCB changes from 95.15 to 1343 between the two rows.
• Uncertainty. The synthetic results are plotted as averages and a 0.95-quantile without a stated confidence interval §5.1. The educational results have no confidence interval §5.2.
• Hidden cost. Forcing pulls every arm at least eta * sqrt(t) times, including arms that are poor for reward. The paper's experiments show this trades reward for accuracy in a controlled way, but the cost is in reward, not in computation. Each step solves a convex problem over the simplex §3. No runtime is reported.
• Pure-error baseline. The GAFS baseline is adapted to minimise error, and its chosen tracking rule differs from the paper's §3 §5.2.

Lineage

• Builds on: Liu et al. (2014), which introduced the reward-versus-error trade-off with a heuristic that uses Hoeffding intervals and has no formal analysis §2 §1. ForcingBalance replaces their error measure with the variance-based one above §2.
• Builds on: GAFS of Antos et al. (2010) for active exploration, whose tracking rule the paper modifies §3.
• Compared against: standard UCB §5.2; GAFS-MAX adapted to minimise error §5.2; uniform sampling §5.2; a Naive-UCB construction of the trade-off app. C.
• Related: Bubeck et al. (2009) on pure exploration and regret §1; Lattimore et al. (2015), Drugan et al. (2013) and Sani et al. (2012) on multi-objective bandits §1; Carpentier et al. (2011, 2015) on active exploration §2.
• Superseded by: not stated.