Characterizing Bias in Post-Bandit Inference under Index Algorithms

Technical Summary: Characterizing Bias in Post-Bandit Inference under Index Algorithms

Problem Statement
The paper addresses the statistical challenge of performing inference on data generated by Multi-Armed Bandit (MAB) algorithms. Unlike conventional independent and identically distributed (i.i.d.) data, bandit data is adaptively collected, creating a feedback loop where allocation decisions depend on past observations. This adaptivity induces a systematic selection bias in the sample mean estimator, $\bar{X}_a(N_a(T))$, which can distort confidence intervals and hypothesis tests. While prior literature has established that such bias exists (e.g., Nie et al., 2018) and provided general asymptotic bounds (e.g., Shin et al., 2019a,b; Russo and Zou, 2016), there is a lack of sharp, leading-order characterizations of this bias for widely used, fully adaptive index algorithms like UCB1. The central research question is to determine the precise magnitude of the sample-mean bias and the associated Z-statistic bias under canonical index algorithms and to understand how algorithmic design choices influence this bias.

Methodology
The authors focus on stable index algorithms, a class that includes the canonical Upper Confidence Bound (UCB1) and its generalizations. The core methodological innovation is a novel empirical fluid approximation of the algorithm's sampling dynamics.

1. Fluid Approximation: The authors first define a deterministic fluid approximation, $n_T$, by replacing empirical sample means with population means ($\mu$) in the index-equalization equations. This captures the first-order allocation behavior but ignores stochastic fluctuations.
2. Empirical Fluid Approximation: To capture the critical correlation between pull counts and reward fluctuations that drives bias, the authors introduce a second-order approximation, $\tilde{n}_T$. This is constructed by re-introducing sample means evaluated at the fluid allocation counts ($\bar{X}_a(n_{a,T})$) into the index-equalization equations.
3. Key Quantity: The analysis identifies a critical algorithm-dependent quantity termed the effective exploration rate, denoted $\Gamma_{a,T}$. For an index function $I_t(x, n)$, this is defined as $\Gamma_t(x, n) := -2n^{3/2} \frac{\partial_n I_t(x, n)}{\partial_x I_t(x, n)}$. This rate quantifies how responsive the allocation is to sample mean perturbations; a higher rate implies less responsiveness and thus lower bias.
4. Stability Conditions: The theoretical results rely on three conditions: regularity of the index function (smoothness and monotonicity), fluid scaling conditions (ensuring suboptimal arms are pulled sufficiently for concentration), and stability conditions (ensuring the actual pull counts concentrate around the empirical fluid approximation).

Key Contributions and Results

• Sharp Characterization of Bias: The paper derives explicit leading-order expressions for the bias of the sample mean and the Z-statistic as the horizon $T \to \infty$.

  • For any arm $a$ that is not the unique optimal arm, the standardized bias of the Z-statistic, $E[Z_{a,T}]$, converges to:
    $$E[Z_{a,T}] \approx -\left(1 - \frac{1}{|O|}\mathbb{1}\{a \in O\}\right) \frac{\sigma_a}{\Gamma_{a,T}}$$
    where $O$ is the set of optimal arms and $\sigma_a$ is the reward standard deviation.
  • For the unique optimal arm, the bias is of a much smaller order, decaying polynomially fast (e.g., $O(f_T/T)$ for generalized UCB), whereas non-unique optimal arms exhibit bias decaying at the rate $1/\Gamma_{a,T}$.

• Application to Generalized UCB: Specializing to generalized UCB algorithms with index $I_t(x, n) = x + f_t/\sqrt{n}$, the effective exploration rate is $\Gamma_{a,T} = f_T$.

  • UCB1 Case: For standard UCB1, $f_T = \sqrt{2 \log T}$. Consequently, the standardized bias decays at the extremely slow rate of $1/\sqrt{\log T}$. This implies that even for large $T$, the bias remains substantial at the inferential scale.
  • Generalized Case: The bias scales as $1/f_T$.

• Regret-Bias Trade-off: The authors establish a fundamental trade-off between regret minimization and inference bias.

  • The regret for generalized UCB scales as $f_T^2$.
  • The bias scales as $1/f_T$.
  • Therefore, bias scales as $1/\sqrt{\text{Regret}}$. Algorithms designed to minimize regret aggressively (like UCB1 with slow-growing $f_T$) incur higher bias. Conversely, more exploratory algorithms (faster-growing $f_T$) reduce bias but increase regret.

• Algorithmic Origin of Bias: The results reveal that the bias is driven by the "effective exploration rate." The bias arises because the algorithm adjusts allocations to equalize indices; when an arm's sample mean fluctuates upward, the algorithm pulls it more often, creating a positive correlation between the number of pulls and the sample mean. This positive correlation results in a negative (downward) bias in the estimator relative to the true mean, as reflected in the negative sign of the leading-order expression.

Significance and Claims
The paper claims to provide the first sharp, leading-order characterization of bias for fully adaptive, stable index algorithms. Its significance lies in:

1. Quantifying the Inferential Cost: It demonstrates that for standard algorithms like UCB1, the bias decays so slowly ($1/\sqrt{\log T}$) that it may dominate the standard error in practical inference settings, challenging the validity of standard post-bandit inference without correction.
2. Algorithmic Insight: It clarifies that the bias is not merely a function of adaptivity but is structurally determined by the specific form of the index function (via the effective exploration rate).
3. Design Implications: It highlights a qualitative distinction between instances with a unique optimal arm (low bias) and those with multiple optimal arms (high bias), and explicitly maps the trade-off between minimizing regret and minimizing bias.
4. Methodological Contribution: The empirical fluid approximation framework is presented as a tractable tool for analyzing the complex temporal dependencies in adaptive sampling, potentially applicable to other inferential properties of bandit algorithms.

The authors note that their results are specific to stable index algorithms and do not directly apply to unstable algorithms (like Thompson Sampling or $\epsilon$-greedy) or non-index methods, suggesting these as directions for future work. They also emphasize that while the bias formula suggests natural corrections, constructing practical confidence intervals with improved finite-sample performance remains an open task.