Trading off rewards and errors in multi-armed bandits

1 Introduction

• In research studies, designers must balance participants’ cumulative reward with reliable estimates of available options, especially in education, health, and online experiments.Poor experiences may lead participants to leave permanently.Source: §1 · p. 1
• Reward maximization and accurate arm estimation are not generally simultaneously optimal, motivating a careful tradeoff between these objectives.The paper notes prior results showing incompatibility between sub-linear regret and optimal best-arm identification.Source: §1 · p. 2
• The paper proposes a weighted objective integrating rewards and estimation errors, allowing a designer to set their relative importance.The tradeoff between cumulative reward and arm-value estimation accuracy was first introduced by Liu et al. [2014].Source: §1 · p. 2
• ForcingBalance optimizes this objective when arm distributions are unknown.Source: §1 · p. 2
• ForcingBalance’s regret asymptotically matches the minimax rate for cumulative regret minimization and the performance of active-exploration algorithms.The paper also reports that a simple UCB extension is insufficient and that synthetic and educational-data simulations support the analysis.Source: §1 · p. 2

2 Balancing Rewards and Errors

• The estimation-error objective alone calls for pulling arms in proportion to σ_i^(2/3), while the chosen normalization equalizes the separate objectives’ standard regret bounds at eO(1/√n).Source: §2 · p. 2
• For equal-variance arms in the illustrated two-arm example, λ* is even at small w and shifts toward arm 2 as w rises, allocating everything to it at w=1.Source: Figure 1 · p. 3
• The objective combines reward and normalized estimation error as a convex combination weighted by w; w=1 gives reward maximization and w=0 gives error minimization.Using root mean square error makes the objective scale-invariant and links w to a Lagrange multiplier for a reward-under-accuracy constraint.Source: §2 · p. 3
• The continuous relaxation approximates the difficult discrete allocation problem, and each arm’s optimal discrete pull fraction differs from λ* by at most 1/n.The resulting objective-value difference is bounded by 1/n^2.Source: §2 · pp. 3–4
• The optimal allocation λ* favors arms with large means and variances; as w increases it concentrates increasingly on the arm with the largest mean.For small w, allocations are proportional to arm standard deviations; λ* is unique under the conditions stated in the paper.Source: §2 · p. 3
• The objective is strongly concave and smooth on a restricted simplex with a positive minimum allocation, properties used to characterize the optimization problem.The restricted simplex requires each allocation component to be at least λmin>0.Source: §2 · p. 4

3 The ForcingBalance Algorithm

• Naïve UCB can perform poorly because uncertain variance lower bounds may discourage sampling arms whose estimates need correction, preventing improvement over time.The paper therefore adopts a forcing approach inspired by GAFS-MAX.Source: §3 · p. 4
• At each step, the algorithm first selects an arm with fewer than η pulls, forcing initial exploration before allocation tracking.Source: §3 · p. 4
• Once arms have been sufficiently sampled, ForcingBalance estimates means and variances, computes an allocation on a restricted simplex, and can do so efficiently.It then selects an arm according to the estimated allocation.Source: §3 · p. 4
• ForcingBalance tracks its estimated target allocation by selecting the arm most underpulled so far, keeping realized frequencies close to the target.The authors state this tracking rule is more efficient than the ratio-based rule in GAFS-MAX.Source: §3 · p. 5
• The exploration parameter η controls forced sampling, while λmin restricts learnable allocations and must be positive for the stated uniform-convergence guarantee.A large η improves estimation and target-allocation convergence but can slow realized-allocation tracking.Source: §3 · p. 5

• Estimating f requires sampling every arm: its error is governed by the largest mean or variance estimation error, and the restricted simplex enforces a positive minimum allocation.Source: §4 · p. 5
• The theorem assumes λ* lies in the restricted simplex; when all arms have nonzero variance and w < 1, a nonzero λ_min can satisfy this condition.Source: the algorithm · p. 5
• The bound has three phases: uniform exploration through n ≤ n_0, a slow eO(n^-1/4) middle phase, then tracking λ* after n_2 steps.Source: the algorithm · p. 6
• eO(n^-1/2) asymptotic regret matches minimax rates for regret minimization and active exploration, so the reward–error tradeoff is not fundamentally harder.Source: the algorithm · p. 6
• The bound worsens as λ_min shrinks and as w approaches 1; a decreasing λ_min can relax the assumption but worsens the regret rate.Source: the algorithm · p. 6
• The proof generalizes to any strongly convex and smooth objective, relating allocation differences to objective-function differences when the optimum is not explicit.Source: the algorithm · p. 6

5.1 Synthetic Data

• The rescaled regret largely follows the predicted progression, eventually converging to a constant, although a transient decrease suggests faster actual regret decay may occur early.The analysis associates the constant rescaled regret with actual regret entering an eO(n−1/2) regime; a faster rate is suggested, not established.Source: §5.1 · pp. 6–7, Figure 3 · p. 7
• After the initial uniform-forcing phase, the estimated allocation rapidly converges to λ∗, while the actual allocation tracks it with a slightly longer delay.The algorithm begins with uniform allocation because forcing is active.Source: §5.1 · p. 7
• In the synthetic setting, allocations shift from favoring high-variance arm 4 toward reward-maximizing arm 5 as w increases, and ForcingBalance approaches λ∗ more effectively at small w.For w = 0.9, the optimal allocation favors arm 5 and gives arm 4 a partial allocation.Source: §5.1 · pp. 6–7, Figure 4 · p. 7

5.2 Educational Data

• The educational experiment uses player persistence after an initial pair of number lines as its outcome, rather than the chance of a correct answer studied in the source experiment.The game conditions vary number-line representations, tick marks, hint animations, and hint backoff rates.Source: §5.2 · p. 7, Figure 5 · p. 8
• On the educational dataset, ForcingBalance achieves the smallest regret while balancing reward and estimation accuracy; at w = 0.95 it improves reward over GAFS-MAX with little loss in ranking accuracy.The comparison uses 34,197 players and 64 conditions, with performance evaluated over 25,000 steps and 100 runs.Source: §5.2 · pp. 7–8, Figure 6 · p. 8

6 Conclusions

• The paper formulates the tradeoff between rewards and estimation errors, introduces a forced-sampling algorithm, derives regret bounds, and validates it on synthetic and educational data.The analysis can extend to any strongly convex and smooth function defined over parameters of the arms’ distributions.Source: §6 · pp. 8–9
• An explicit incompatibility result between maximizing reward and minimizing estimation error remains future work, as active exploration pulls all arms linearly often while regret minimization pulls suboptimal arms sublinearly often.The paper also identifies alternative tradeoffs and Thompson sampling adaptations as directions to study.Source: §6 · p. 8

Technical lemmas

• The objective’s Hessian is bounded between αI_K and βI_K, yielding α-strong convexity and β-smoothness.These regularity properties support the subsequent allocation analysis.Source: A Technical Lemmas · p. 11
• Corollary 1 applies a union bound over a covering of the allocation simplex together with concentration of the empirical means and variances.The stated confidence parameter is δn = δ/(4Kn2(n + 1)).Source: A Technical Lemmas · p. 11
• Lemma 5 considers the estimated optimal allocation obtained by maximizing the objective under empirical arm distributions.Its setup characterizes each empirical distribution by an estimated mean and variance based on the samples collected for that arm.Source: A Technical Lemmas · p. 12
• For a monotonically increasing sublinear threshold h(n), the forcing condition is Ti,n < h(n) + 1; the proof establishes its persistence across successive phases after the initial uniform-exploration phase.At the start, all arms are explored uniformly in a fixed order until the condition no longer triggers.Source: A Technical Lemmas · pp. 13–14

Theorem 1

• Theorem 1 bounds ForcingBalance regret for a K-arm bandit under Assumption 1, with a numerical constant C.The supplied theorem statement identifies K ≥ 2 arms, but does not include the full bound.Source: B Proof of Theorem 1 · p. 15

Proof sketch

• Because λ* has no closed-form solution, the proof explicitly translates errors in estimating f_w into deviations between estimated and optimal allocations, and back.It also analyzes the effects of forcing exploration and uses a tracking strategy distinct from GAFS-MAX.Source: B Proof of Theorem 1 · p. 16
• Forced exploration ensures each arm receives at least eO(√n) pulls, yielding an estimated allocation that approaches λ* at rate eO(1/n^1/8).The proof sketch then uses tracking to make the actual allocation approach λ* at the same rate.Source: B Proof of Theorem 1 · p. 16
• Tracking propagates the estimated allocation's accuracy to the actual allocation, which also approaches λ* at rate eO(1/n^1/8).Without this step, the allocation estimate alone would not guarantee small regret for the sequence of pulls actually made.Source: B Proof of Theorem 1 · p. 16
• After each arm receives eΩ(n) pulls, more accurate estimates improve allocation accuracy to eO(1/n^1/4), which the proof translates into the final regret bound.The proof sketch distinguishes this later phase from the earlier, slower convergence phase.Source: B Proof of Theorem 1 · p. 16

Optimal allocation

• At w = 0.4, optimal allocations are almost balanced in settings 1 and 2 but favor one arm in settings 3 and 4.The text attributes the imbalance to variance differences in setting 3 and mean differences in setting 4.Source: C Supplementary Results · p. 19

Comparison with Naive-UCB

• ForcingBalance's rescaled regret converges to a constant in settings 2 and 3, while (μ, σ)-Naive-UCB has a slower initial phase in setting 2 and constant regret at n = 5000 in setting 3.In setting 2, variance underestimation leads Naive-UCB to favor the higher-mean arm and explore the other arm less; in setting 3, it can fail to recover from bad variance estimates.Source: C Supplementary Results · p. 19, Figure 7 · p. 20

Tracking performance

• Without tracking, the actual allocation converges to λ* significantly more slowly and regret is much higher, although the estimated allocation is unaffected.Figure 8 compares ForcingBalance with and without its tracking step.Source: Figure 8 · p. 21, C Supplementary Results · p. 21