PaperlayerView exact revision on arXiv

Source-linked AI summary

Inference for Batched Bandits

Kelly W. Zhang, Lucas Janson, Susan A. Murphy

arXiv:2002.03217v3cs.LGstat.ML

TL;DR

Adaptive bandit data challenge inference because action choices depend on previous actions and rewards, despite the need for reliable conclusions from experiments. The paper proves that OLS can be asymptotically non-normal at zero margin and introduces BOLS for batched multi-arm and contextual data. BOLS is asymptotically normal and robust to batch-varying baseline rewards when the margin remains constant.

  • Problem

    Bandit data are adaptively collected, violating the independent-assignment assumption of many inference methods and making reliable inference on arm-reward differences challenging.

    Source: §1 · p. 1

  • Method

    The paper introduces BOLS, which computes and variance-normalizes batch-level OLS estimates of the margin.

    Source: §5.1 · p. 6

  • Results

    At zero margin, OLS is asymptotically non-normal under common bandit algorithms, while BOLS is asymptotically normal for multi-arm and contextual bandits.

    Source: §1 · p. 2, §7 · p. 9

  • Takeaways & Limitations

    BOLS supports inference with batch-varying baseline rewards when the margin stays constant, and simultaneous batch-specific intervals when the margin varies.

    Source: §1 · p. 2

    The stated robustness to batch-varying rewards applies when the margin remains constant; changing margins call for simultaneous intervals for each batch.

    Source: §1 · p. 2

Abstract

from arXiv · show

As bandit algorithms are increasingly utilized in scientific studies and industrial applications, there is an associated increasing need for reliable inference methods based on the resulting adaptively-collected data. In this work, we develop methods for inference on data collected in batches using a bandit algorithm. We first prove that the ordinary least squares estimator (OLS), which is asymptotically normal on independently sampled data, is not asymptotically normal on data collected using standard bandit algorithms when there is no unique optimal arm. This asymptotic non-normality result implies that the naive assumption that the OLS estimator is approximately normal can lead to Type-1 error inflation and confidence intervals with below-nominal coverage probabilities. Second, we introduce the Batched OLS estimator (BOLS) that we prove is (1) asymptotically normal on data collected from both multi-arm and contextual bandits and (2) robust to non-stationarity in the baseline reward.

1 Introduction

Bandit data are collected adaptively, challenging inference methods that assume independent treatment assignment. The paper studies confidence intervals for arm-reward differences in batches, proving a zero-margin failure of OLS and introducing BOLS for inference in multi-arm and contextual settings, including non-stationarity.

1 Introduction

  • Inference on bandit data can help practitioners compare arm rewards, inform future interventions, and share findings for scientific discovery and decision-making.The introduction illustrates this with using results from an online education experiment to revise teaching strategies and publish comparisons.Source: §1 · p. 1
  • Adaptive action choices violate the independent-assignment assumption used by many inference methods, and can make estimators such as the sample mean biased.Past actions and rewards inform future action selection.Source: §1 · p. 2
  • Batched studies keep the number of batches fixed while batch size grows asymptotically, reflecting settings where study duration is constrained but participant numbers can grow.The authors note that this asymptotic device is used to approximate finite-sample distributions, not because real experiments require batch size to grow without bound.Source: §1 · p. 2
  • At zero margin, OLS is asymptotically non-normal under common bandit algorithms, while BOLS is asymptotically normal for multi-arm and contextual bandits, including non-stationary baseline rewards.For a changing margin, BOLS can instead construct simultaneous confidence intervals for each batch.Source: §1 · p. 2

2 Related Work

Prior approaches to bandit inference include high-probability bounds and adaptive-weight estimators, but they involve tradeoffs in interval width, power, or non-stationary guarantees. The paper reports that its asymptotic-approximation approaches generally retain reliable coverage and Type-1 error control while outperforming a martingale-bound test in power.

2 Related Work

  • Existing stage-wise p-value results do not cover arbitrary-stage adaptive trials with unknown reward distributions and real-valued selection probabilities such as Thompson Sampling.The cited results concern two-stage trials and impose restrictions on adaptive rules or conditional reward distributions.Source: §2 · p. 3
  • High-probability confidence intervals offer finite-sample guarantees but are more conservative, requiring more observations for comparable interval width or test power.The passage notes that increasing study participants can be costly.Source: §2 · p. 3
  • Asymptotic-approximation approaches in the simulations significantly outperform a self-normalized martingale-bound test in power while generally providing reliable interval coverage and Type-1 error control.The martingale bound is guaranteed on adaptively collected data; the authors characterize asymptotic inference as having weaker guarantees.Source: §2 · p. 3
  • Prior adaptive-weight methods include AW-AIPW and W-decorrelated OLS, while the cited approaches lack guarantees for non-stationary bandit settings.AW-AIPW has a CLT under conditions on its weights; the W-decorrelated estimator down-weights later rewards in the two-arm setting.Source: §2 · p. 3

3 Problem Formulation

The formulation considers batched actions and rewards, allowing reward means to change across batches. It also requires sufficient exploration through a clipping constraint on action-selection probabilities.

3 Problem Formulation

  • In each of T batches, the two-arm setup selects n binary actions and observes one independent reward for each selected action.The distribution of actions in a later batch may depend on how many observations were collected in earlier batches.Source: §3 · p. 4
  • Reward means may vary across batches, with a stationary mean model as the special case where batch-specific parameters are equal.The errors are defined as rewards minus their batch-specific linear means, and the conditional mean does not depend on prior actions or rewards.Source: §3 · p. 4
  • A clipping constraint explicitly limits action-selection probabilities to guarantee exploration, while allowing them to approach zero or one at a specified rate.The passage motivates exploration for inference, test power, and settings where the margin varies between batches.Source: §3 · p. 4

4 Asymptotic Distribution of the Ordinary Least Squares Estimator

OLS asymptotic normality depends on stability of the design, which common bandit algorithms provide under a non-zero margin. At zero margin, action probabilities fail to concentrate, producing non-normal OLS behavior and potentially poor normal-approximation coverage, including at low signal-to-noise ratios.

4.1 Conditions for Asymptotically Normality of the OLS estimator

  • The triangular-array CLT gives OLS asymptotic normality when its stated moment and stability conditions hold.The authors generalize an adaptive-sampling CLT because the random-variable distributions change with batch size.Source: §4.1 · p. 5
  • When the margin is non-zero, ϵ-greedy, Thompson Sampling, and UCB with constant-rate clipping satisfy the stated OLS stability conditions.The stability condition requires the asymptotic rate of arm selection to be predictable before the experiment.Source: §4.1 · p. 5

4.2 Asymptotic Non-Normality under No Margin

  • At zero margin, OLS is asymptotically non-normal under Thompson Sampling, ϵ-greedy, and UCB because action-selection probabilities do not concentrate without a unique optimal arm.The theorem states the Thompson Sampling result under its stated clipping, reward, and prior conditions; similar results for ϵ-greedy and UCB are cited.Source: §4.2 · pp. 5–6
  • Because OLS is normal at non-zero margins but not at zero, its convergence is non-uniform, undermining normal-approximation inference near statistically indistinguishable margins.The zero-margin asymptotic distribution is relevant to finite samples when the margin is difficult to distinguish from zero.Source: §4.1 · p. 5, §4.2 · p. 6
  • Even at non-zero margins, low signal-to-noise ratios can yield below-nominal coverage for normal-approximation confidence intervals.For any batch size and noise variance, the passage states that some non-zero margin has a finite-sample distribution poorly approximated by a normal distribution.Source: §4.2 · p. 6

5 Batched OLS Estimator

Batched OLS (BOLS) computes a margin estimate within each batch, supporting asymptotically normal inference for multi-arm and contextual bandits under stated conditions. Its statistic also supports inference when baseline rewards vary across batches.

5.1 Batched OLS Estimator for Multi-Arm Bandits

  • BOLS computes OLS margins within batches and normalizes them using batch-specific variance estimates, rather than pooling all observations.The estimator targets the margin Δ_t = β_t,1 − β_t,0 for each batch.Source: §5.1 · p. 6
  • Under moment and conditionally i.i.d. action assumptions with clipping rate f(n) = 1/n^α, 0 ≤ α < 1, BOLS is asymptotically normal for multi-arm bandits.The theorem also extends to unequal batch sizes when the smallest batch size grows and batch size is independent of history.Source: §5.1 · p. 6
  • A weighted combination of batch-level Z-statistics supports testing because BOLS establishes their asymptotic independence despite bandit-dependent batches.The passage relates this statistic to inverse normal p-value combination tests used for independent studies.Source: §5.1 · p. 7

5.2 Batched OLS Estimator for Contextual Bandits

  • For contextual bandits, BOLS is asymptotically normal under the stated moment, action, context, boundedness, and conditional clipping assumptions.The conditional clipping rate is f(n) = c for 0 ≤ c < 1/2.Source: §5.2 · p. 7

5.3 Batched OLS Statistic for Non-Stationary Bandits

  • When the margin stays constant as baseline rewards change across batches, the BOLS test needs no adjustment; if margins vary, it can form simultaneous confidence regions for each batch’s margin.The passage also describes estimating variance separately by batch to allow variance to vary between batches.Source: §5.3 · p. 8

6 Simulation Experiments

Simulations compare inference methods for stationary and non-stationary baseline-reward settings. BOLS offers stronger Type-1 error control in small samples and under baseline non-stationarity, with a modest stationary-power trade-off.

Procedure

  • OLS and AW-AIPW show inflated Type-1 error in the simulations, and correcting their power-test cutoffs requires null simulations that are infeasible for real experiments.The experiments test whether the margin is zero, assume homoscedastic errors, and estimate the noise variance.Source: §6 · p. 8

Results

  • For nT ≲300, BOLS controls Type-1 error more reliably than variance-stabilized AW-AIPW; after nT ≥500, AW-AIPW controls it and has slightly greater stationary power.The stationary Type-1 error and power comparisons are shown in Figures 3 and 4.Source: §6 · p. 8, Figure 3 · p. 9, Figure 4 · p. 9
  • BOLS retains proper Type-1 error control under non-stationary baseline rewards and can have much greater power than other estimators in that setting.The figure uses a constant margin across batches and plots Type-1 error, power, and expected rewards for each arm.Source: §6 · p. 8, Figure 5 · p. 9

7 Discussion

The discussion links OLS’s zero-margin asymptotic non-normality to non-concentrating action-selection probabilities and identifies broader method-of-moments inference as an open question.

Discussion

  • When the margin is zero, OLS is asymptotically non-normal because action-selection probabilities do not concentrate.The paper notes OLS is a canonical method-of-moments estimator, so its result suggests standard method-of-moments guarantees may fail when there is no unique optimal regret-minimizing policy.Source: §7 · p. 9
  • BOLS remains asymptotically normal even when action-selection probabilities do not concentrate.This is the contrast the discussion draws with pooled OLS in the zero-margin case.Source: §7 · p. 9
  • Whether batched versions of general method-of-moments estimators can support adaptive inference remains open.Source: §7 · p. 9

Broader Impact

The paper argues that valid inference on bandit data supports more reliable scientific conclusions and experimentation.

Broader Impact

  • Valid statistical inference on bandit data is presented as supporting more reliable scientific conclusions and facilitating experimentation with bandit algorithms.Source: Broader Impact · p. 10

A.1 W-Decorrelated Estimator

  • The W-decorrelated estimator’s λ is selected using the 1/(nT) quantile of λ_min(X⊤X)/log(nT), with the procedure adjusted for sample size.The cited work’s fixed 0.15-quantile procedure was adjusted because it evaluated only nT = 1000 and valid λ values change with sample size.Source: §A.1 · p. 13

A.2 AW-AIPW Estimator

  • The appendix gives an AW-AIPW treatment-effect estimator and variance estimator, and describes a self-normalized-bound test that rejects when arm confidence bounds do not overlap.Source: §A.2 · p. 13, §A.3 · p. 13

A.4 Estimating Noise Variance

  • For OLS and its W-decorrelated modification, the noise-variance estimator applies a degrees-of-freedom bias correction, normalizing by nT − 2 rather than nT.The authors report that this worked well in practice for Type-1 error control with the W-decorrelated estimator.Source: §A.4 · p. 14

A.5 Non-Stationary Treatment Effect

The appendix compares tests for non-stationary treatment effects and describes the asymptotic argument underlying its results. BOLS NSTE performs poorly in the stationary setting but outperforms the other tests in the non-stationary setting.

A.5 Non-Stationary Treatment Effect

  • The paper gives a confidence region that contains every batch’s true margin simultaneously with probability 1 − α.The stated result applies when the margin varies across batches and assumes the conditions of Theorem 3.Source: §A.5 · p. 14
  • Under the global null that every batch’s margin is zero, the test statistic converges to a chi-squared distribution with T degrees of freedom.The test considers the alternative that at least one batch has a nonzero margin.Source: §A.5 · p. 15
  • In the non-stationary setting, BOLS NSTE significantly outperforms the other test statistics, though it has lower power in the stationary setting.Figure 8’s upper plots show test power; its lower plots show decreasing and oscillating treatment-effect trends.Source: §A.5 · p. 15, Figure 8 · p. 16

B Asymptotic Normality of the OLS Estimator

Condition (b): Conditional Variance

B.1 Corollary 1 (Sufficient conditions for Theorem 5)

The appendix gives sufficient conditions for OLS asymptotic normality under common bandit algorithms and examines why OLS can fail to converge uniformly under Thompson Sampling. For Thompson Sampling, the probability that arm 1 is better has a uniform limit when the margin is zero.

C.1 Thompson Sampling

  • Under Thompson Sampling, the posterior probability that arm 1 is better converges to 1 for a positive margin, 0 for a negative margin, and Uniform[0, 1] at zero margin.The limiting probability at zero margin does not concentrate at one fixed value.Source: §C.1 · pp. 23–24

C Non-uniform convergence of the OLS Estimator

  • The Thompson-sampling analysis establishes non-uniform convergence of the normalized OLS errors, which are asymptotically normal under i.i.d. sampling.The theorem is stated under the setup and conditions of Proposition 2, with β1 = b.Source: §C.1 · p. 24

C.2 ϵ-Greedy

This section studies inference under standard ϵ-greedy and clipped UCB sampling, including OLS behavior, BOLS asymptotic normality and variance estimation, and a two-arm analysis of the W-decorrelated estimator.

C.2 ϵ-Greedy

  • Under zero treatment effect, ϵ-greedy sampling probabilities do not concentrate and normalized OLS errors are non-normal; for nonzero effects, the normalized errors are asymptotically normal.The non-concentration result is stated for T = 2; the nonzero-effect cases correspond to β1 − β0 > 0 or β1 − β0 < 0.Source: §C.2 · pp. 27–28

C.3 UCB

  • For clipped UCB, normalized OLS errors are non-normal when the treatment effect is zero, while the nonzero-effect cases are asymptotically normal.The result is stated for T = 2; when β1 − β0 = 0, the sampling probability does not concentrate.Source: §C.3 · pp. 29–30

D Asymptotic Normality of the Batched OLS Estimator: Multi-Arm Bandits

  • Under weak-moment and conditionally i.i.d. action assumptions with clipping rate f(n) = ω(1/n), the multi-arm BOLS estimator is asymptotically normal.The theorem establishes this result for the multi-arm bandit setting.Source: D Asymptotic Normality of the Batched… · p. 31

Condition(b): Conditional Variance

  • Under the stated conditions, BOLS estimates of the two-arm margin are asymptotically normal, and the BOLS variance estimator is consistent under moment, action, and clipping conditions.The variance-estimator result applies for each batch t and assumes f(n) = ω(1/n).Source: Condition(b): Conditional Variance · pp. 34, 36

E Asymptotic Normality of the Batched OLS Estimator: Contextual Bandits

  • For K-armed contextual bandits, BOLS is asymptotically normal under weak-moment, conditionally i.i.d. action and context, bounded-context, and clipping assumptions.The theorem gives the result for each batch t.Source: E Asymptotic Normality of the Batched… · pp. 38, 40

Condition(b): Conditional Variance

  • BOLS estimates of arm differences are asymptotically normal for any two arms and time under the conditions of Theorem 4.The proof uses the same martingale CLT as Theorem 4, with an adjusted b_t,k vector.Source: Condition(b): Conditional Variance · pp. 43–44

F W-Decorrelated Estimator [6]

  • The paper examines the W-decorrelated estimator in a two-arm bandit to understand its relatively low power despite its asymptotic-normality guarantee.Source: F W-Decorrelated Estimator [6] · p. 45

F.1 Decorrelation Approach

The decorrelation approach modifies OLS using a weighted residual correction. Its weighting trades off bias and variance, and the specified W-decorrelated estimator upweights earlier samples and downweights later ones.

F.1 Decorrelation Approach

  • The choice of Wn trades off bias against variance: reducing the bias term can come at the cost of increased variance.The paper formulates this trade-off as an optimization over Wn and λ.Source: §F.1 · p. 45
  • The W-decorrelated estimator adds a weighted residual correction to the OLS estimate.The displayed definition is d = β̂OLS + Wn(Rn − Xnβ̂OLS).Source: §F.1 · pp. 45–46
  • For λ ≥ 1, the W-decorrelated estimator downweights later samples and upweights earlier samples.This follows from the stated form of the estimator’s weights.Source: §F.1 · p. 46

Related papers

Loading 2002.03217v3…