Inference for Batched Bandits

Abstract

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.

Figure 6:

Stationary Setting: Type-1 error for a two-sided test of H₀ : Δ = 0 vs. H₁ : Δ ≠ 0 (α = 0.05). We set β₁ = β₀ = 0, n = 25, and a clipping constraint of $0.1\le {\pi }_t^{(n)}\le 0.9$. We use 100k Monte Carlo simulations and standard errors are < 0.001.

Figure 7:

Stationary Setting: Power for a two-sided test of H₀ : Δ = 0 vs. H₁ : Δ ≠ 0 (α = 0.05). We set β₁ = 0, β₀ = 0.25, n = 25, and a clipping constraint of $0.1\le {\pi }_t^{(n)}\le 0.9$. We use 100k Monte Carlo simulations and standard errors are < 0.002. We account for Type-1 error inflation as described in Section 6.

Figure 8:

Nonstationary setting: The two upper plots display the power of estimators for a two-sided test of H₀ : ∀t ∈ [1: T], β_t,1 − β_t,0 = 0 vs. H₁ : ∃t ∈ [1: T], β_t,1 − β_t,0 ≠ 0 (α = 0.05). The two lower plots display two treatment effect trends; the left plot considers a decreasing trend (quadratic function) and the right plot considers a oscillating trend (sin function). We set n = 25, and a clipping constraint of $0.1\le {\pi }_t^{(n)}\le 0.9$. We use 100k Monte Carlo simulations and standard errors are < 0.002.

Figure 1:

Empirical distribution of the Z-statistic (σ² is known) of the OLS estimator for the margin. All simulations are with no margin (β₁ = β₀ = 0); $\mathcal{N}(0,1)$ rewards; T = 25; and n = 100. For ϵ-greedy, ϵ = 0.1.

Figure 2:

Empirical undercoverage probabilities (coverage probability below 95%) of confidence intervals using on a normal approximation for the OLS estimator. We use Thompson Sampling with $\mathcal{N}(0,1)$ priors, a clipping constraint of $0.05\le {\pi }_t^{(n)}\le 0.95$, $\mathcal{N}(0,1)$ rewards, T = 25, and known σ². Standard errors are < 0.001.

Figure 3:

Stationary Setting: Type-1 error for a two-sided test of H₀ : Δ = 0 vs. H₁ : Δ ≠ 0 (α = 0.05). We set β₁ = β₀ = 0, n = 25, and a clipping constraint of $0.1\le {\pi }_t^{(n)}\le 0.9$. We use 100k Monte Carlo simulations and standard errors are < 0.001.

Figure 4:

Stationary Setting: Power for a two-sided test of H₀ : Δ = 0 vs. H₁ : Δ ≠ 0 (α = 0.05). We set β₁ = 0, β₀ = 0.25, n = 25, and a clipping constraint of $0.1\le {\pi }_t^{(n)}\le 0.9$. We use 100k Monte Carlo simulations and standard errors are < 0.002. We account for Type-1 error inflation as described in Section 6.

Figure 5:

Non-stationary baseline reward setting: Type-1 error (upper left) and power (upper right) for a two-sided test of H₀ : Δ = 0 vs. H₁ : Δ ≠ 0 (α = 0.05). In the lower two plots we plot the expected rewards for each arm; note the margin is constant across batches. We use n = 25 and a clipping constraint of $0.1\le {\pi }_t^{(n)}\le 0.9$. We use 100k Monte Carlo simulations and standard errors are < 0.002.