Statistical Inference with M-Estimators on Adaptively Collected Data

Abstract

Bandit algorithms are increasingly used in real-world sequential decision-making problems. Associated with this is an increased desire to be able to use the resulting datasets to answer scientific questions like: Did one type of ad lead to more purchases? In which contexts is a mobile health intervention effective? However, classical statistical approaches fail to provide valid confidence intervals when used with data collected with bandit algorithms. Alternative methods have recently been developed for simple models (e.g., comparison of means). Yet there is a lack of general methods for conducting statistical inference using more complex models on data collected with (contextual) bandit algorithms; for example, current methods cannot be used for valid inference on parameters in a logistic regression model for a binary reward. In this work, we develop theory justifying the use of M-estimators-which includes estimators based on empirical risk minimization as well as maximum likelihood-on data collected with adaptive algorithms, including (contextual) bandit algorithms. Specifically, we show that M-estimators, modified with particular adaptive weights, can be used to construct asymptotically valid confidence regions for a variety of inferential targets.

Figure 3:. Poisson Rewards:

Empirical coverage probabilities for 90% confidence ellipsoids for parameters ${\theta }^{\ast }(\mathcal{P})$ and parameters ${\theta }_1^{\ast }(\mathcal{P})$ (top row). We also plot the volumes of these 90% confidence ellipsoids for ${\theta }^{\ast }(\mathcal{P})$ and parameters ${\theta }_1^{\ast }(\mathcal{P})$ (bottom row). We set the true parameters to ${\theta }^{\ast }(\mathcal{P})=[0.1,0.1,0.1,0,0,0]$ (left) and to ${\theta }^{\ast }(\mathcal{P})=[0.1,0.1,0.1,0.2,0.1,0]$ (right).

Figure 4:

Empirical coverage probabilities (upper row) and volume (lower row) of 90% confidence ellipsoids. In these simulations, ${\theta }^{\ast }(\mathcal{P})=[0.1,0.1,0.1,0.2,0.1,0]$. The left two columns are for the linear reward model setting (t-distributed rewards) and the right two columns are for the logistic regression model setting (Bernoulli rewards). We consider confidence ellipsoids for all parameters ${\theta }^{\ast }(\mathcal{P})$ and for advantage parameters ${\theta }_1^{\ast }(\mathcal{P})$ for both settings.

Figure 5:

Mean squared error estimators of ${\theta }^{\ast }(\mathcal{P})$ for linear model (top), logistic regression model (middle), and generalized linear model for Poisson rewards (bottom). We consider simulations with ${\theta }^{\ast }(\mathcal{P})=[0.1,0.1,0.1,0,0,0]$ (left) and simulations with ${\theta }^{\ast }(\mathcal{P})=[0.1,0.1,0.1,0.2,0.1,0]$ (right).

Figure 6:

Above we plot the mean squared errors for the adaptively-weighted least squares estimator with evaluation policies: (1) uniform evaluation policy which selects actions uniformly from $\mathcal{A}$ and (2) expected ${\pi }_t(a,{\mathcal{H}}_{t-1})$ evaluation policy for which ${\pi }_t^{\text{sta}}(a)={\mathbb{E}}_{\mathcal{P},\pi }[{\pi }_t(a)]$ (oracle quantity). In a two arm bandit setting we perform Thompson Sampling with standard normal priors, 0.01 clipping, ${\theta }^{\ast }(\mathcal{P})=[{\theta }_0^{\ast }(\mathcal{P}),{\theta }_1^{\ast }(\mathcal{P})]=[0,1]$, standard normal errors, and T = 1000. Error bars denote standard errors computed over 5,000 Monte Carlo simulations.

Figure 7:

Above we plot empirical allocations, $\frac{1}{T}{\sum }_{t=1}^T{A}_t$, under both Thompson Sampling (standard normal priors, 0.01 clipping) and ϵ-greedy (ϵ = 0.1) under zero margin ${\theta }_0^{\ast }(\mathcal{P})={\theta }_1^{\ast }(\mathcal{P})=0$. For our simulations T = 100, errors are standard normal, and we use 50k Monte Carlo repetitions.

Figure 8:

Above we construct confidence intervals for ${\theta }_1^{\ast }(\mathcal{P})-{\theta }_0^{\ast }(\mathcal{P})$ using a normal approximation for the OLS estimator. We compare independent sampling (π_t = 0.5) and TS Hodges, both with standard normal priors, 0.01 clipping, standard normal errors, and T = 10, 000. We vary the value of ${\theta }_1^{\ast }(\mathcal{P})-{\theta }_0^{\ast }(\mathcal{P})$ in the simulations to demonstrate the non-uniformity of the confidence intervals.

Figure 1:

The empirical distributions of the weighted and unweighted least-squares estimators for ${\theta }_1^{\ast }(\mathcal{P})≔{\mathbb{E}}_{\mathcal{P}}[Y_t(1)]$ in a two arm bandit setting where ${\mathbb{E}}_{\mathcal{P}}[Y_t(1)]={\mathbb{E}}_{\mathcal{P}}[Y_t(0)]=0$. We perform Thompson Sampling with $\mathcal{N}(0,1)$ priors, $\mathcal{N}(0,1)$ errors, and T = 1000. Specifically, we plot $\sqrt{{\sum }_{t=1}^T{A}_t}({\widehat{\theta }}_{T,1}^{\text{OLS}}-{\theta }_1^{\ast }(\mathcal{P}))$ on the left and $\left(\frac{1}{\sqrt{T}}{\sum }_{t=1}^T\sqrt{\frac{0.5}{{\pi }_t(1)}}{A}_t\right)({\widehat{\theta }}_{T,1}^{\text{AW-LS}}-{\theta }_1^{\ast }(\mathcal{P}))$ on the right.

Figure 2:

Empirical coverage probabilities (upper row) and volume (lower row) of 90% confidence ellipsoids. The left two columns are for the linear reward model setting (t-distributed rewards) and the right two columns are for the logistic regression model setting (Bernoulli rewards). We consider confidence ellipsoids for all parameters ${\theta }^{\ast }(\mathcal{P})$ and for advantage parameters ${\theta }_1^{\ast }(\mathcal{P})$ for both settings.