Trading off rewards and errors in multi-armed bandits

1. Problem Definition

The paper addresses a specific challenge in Multi-Armed Bandits (MAB): the trade-off between two conflicting objectives that are often studied separately:

1. Reward Maximization (Exploitation): Minimizing cumulative regret by selecting the arm with the highest expected mean reward.
2. Active Exploration (Estimation): Minimizing the estimation error of the mean and variance of all arms to gather generalizable knowledge.

Context: In high-stakes domains like education or medicine, a system must provide good immediate experiences to users (high reward) while simultaneously collecting data to understand the effectiveness of different strategies (low estimation error). Pure exploration algorithms may frustrate users with poor rewards, while pure exploitation algorithms (like standard UCB) fail to learn accurate models of sub-optimal options.

Formal Objective:
The authors define a new objective function $f_w$ that combines average reward $\rho$ and estimation error $\varepsilon$ as a convex combination:
$$f_w(I_n) = w \rho(I_n) - (1-w) \varepsilon(I_n)$$
Where:

• $w \in [0, 1]$ is a weight parameter.
• $\rho(I_n)$ is the average reward.
• $\varepsilon(I_n)$ is the root mean square error of the arm estimates, scaled by $\sqrt{n}$ to ensure scale invariance.
• The goal is to find a sequence of arm pulls $I_n$ that maximizes $f_w$.

2. Methodology: The ForcingBalance Algorithm

The authors propose the ForcingBalance algorithm. They first demonstrate that a naive application of "Optimism in the Face of Uncertainty" (UCB-style) fails in this setting. Constructing upper bounds on the objective function leads to poor performance because the algorithm may underestimate variances, leading to insufficient exploration of high-variance arms.

Algorithm Structure:
ForcingBalance operates in two modes at each time step $t$:

1. Forcing Phase: If any arm $i$ has been pulled fewer than $\eta \sqrt{t}$ times, the algorithm forces the selection of that arm. This ensures that every arm is sampled sufficiently often to obtain accurate estimates of both means and variances.
2. Tracking Phase: If all arms have been sufficiently pulled, the algorithm:
   • Computes the empirical estimates of means ($\hat{\mu}$) and variances ($\hat{\sigma}$).
   • Solves a continuous optimization problem to find the estimated optimal allocation $\hat{\lambda}_t$ that maximizes the objective function $f_w$ based on current estimates.
   • Selects the arm that is currently most under-pulled relative to $\hat{\lambda}_t$. Specifically, it selects $I_t = \arg\max_i (\hat{\lambda}_{i,t} - \hat{e}_{\lambda_{i,t}})$, where $\hat{e}_{\lambda}$ is the empirical frequency of pulls. This "tracking" step ensures the actual allocation converges to the estimated optimal allocation.

Key Technical Properties:

• The objective function $f_w$ is proven to be strongly concave and smooth over the restricted simplex of allocations.
• The algorithm relies on a restricted simplex $D_K$ where $\lambda_i \ge \lambda_{min} > 0$ to ensure mathematical bounds hold, though experiments suggest $\lambda_{min}=0$ works well in practice.

3. Key Contributions

1. New Objective Formulation: The paper formalizes the trade-off between reward and estimation error using a scale-invariant objective function $f_w$. Unlike previous heuristic approaches, this formulation allows for a direct, interpretable trade-off parameter $w$.
2. ForcingBalance Algorithm: Introduction of a novel algorithm that combines forced sampling (to guarantee exploration) with tracking (to converge to the optimal allocation).
3. Theoretical Guarantees:
   • The authors prove that ForcingBalance achieves a regret bound that asymptotically matches the minimax rate for both pure reward minimization and pure active exploration ($\tilde{O}(n^{-1/2})$).
   • The proof establishes that balancing these two objectives is not fundamentally more difficult than optimizing them individually.
   • The regret bound depends on the number of arms $K$, the weight $w$, the minimum variance, and the minimum proportion of the optimal allocation ($\lambda^*_{min}$).
4. Empirical Validation: Extensive experiments on synthetic data and real-world educational data (Treefrog Treasure game) demonstrating that the algorithm successfully balances user experience with data collection quality.

4. Results

Synthetic Data Experiments:

• Convergence: The rescaled regret $\sqrt{n}R_n$ converges to a constant, confirming the $\tilde{O}(n^{-1/2})$ rate.
• Tracking: The algorithm successfully tracks the optimal allocation $\lambda^*$, even when the optimal strategy shifts based on $w$.
• Failure of Naive UCB: A "Naive-UCB" variant (using upper bounds on the objective) failed significantly, often getting stuck in sub-optimal allocations due to poor variance estimation.

Real-World Educational Data (Treefrog Treasure):

• Setup: A 64-arm experiment involving different number-line representations for a math game.
• Comparison: ForcingBalance was compared against UCB, GAFS-MAX (pure exploration), and Uniform sampling.
• Findings:
  • UCB: Maximized player reward but failed to accurately rank game conditions (high RankErr), providing little insight to designers.
  • GAFS-MAX: Provided excellent insights (low estimation error) but resulted in poor player experience (low reward), risking user churn.
  • ForcingBalance: Achieved the best balance. With $w=0.95$ (favoring reward), it significantly improved player experience compared to GAFS-MAX while maintaining high estimation accuracy (low RankErr), allowing designers to identify the best game settings without losing users.

5. Significance

This paper is significant because it bridges the gap between user-centric optimization (maximizing immediate reward) and research-centric optimization (maximizing information gain).

• Practical Impact: It provides a rigorous framework for designing interactive systems (e.g., adaptive learning, clinical trials, A/B testing) where the system must serve the user and learn from them simultaneously.
• Theoretical Insight: It resolves the question of whether these objectives are mutually exclusive. The results show they are not; a single algorithm can achieve near-optimal performance for both, provided the trade-off is managed via forced sampling and tracking.
• Generalizability: The analysis relies on the strong convexity and smoothness of the objective function, suggesting the approach can be extended to other multi-objective bandit problems beyond just mean-variance trade-offs.