Statistical Inference with M-Estimators on Bandit Data

Kelly W. Zhang

Lucas Janson<EMAIL_ADDRESS>
Susan A. Murphy<EMAIL_ADDRESS>
Harvard University,
Cambridge, MA 02139, USA

Bandit algorithms are increasingly used in real world sequential decision making problems, from online advertising to mobile health. As a result, there are more datasets collected using bandit algorithms and with that an increased desire to be able to use these datasets to answer scientific questions like: Did one type of ad increase the click-through rate more or lead to more purchases? In which contexts is a mobile health intervention effective? However, it has been shown that classical statistical approaches, like those based on the ordinary least squares estimator, fail to provide reliable confidence intervals when used with bandit data. Recently methods have been developed to conduct statistical inference using simple models fit to data collected with multi-armed bandits. However there is a lack of general methods for conducting statistical inference using  more complex models. In this work, we develop theory justifying the use of M-estimation [Van der Vaart, 2000], traditionally used with i.i.d data, to provide inferential methods for a large class of estimators—including least squares and maximum likelihood estimators—but now with data collected with (contextual) bandit algorithms. To do this we generalize the use of adaptive weights pioneered by Hadad et al., 2019 and Deshpande et al., 2018. Specifically, in settings in which the data is collected via a (contextual) bandit algorithm, we prove that certain adaptively weighted M-estimators are uniformly asymptotically normal and demonstrate empirically that we can use their asymptotic distribution to construct reliable confidence regions for a variety of inferential targets.

contextual bandits, statistical inference, adaptively collected data

§ INTRODUCTION

Due to the need for interventions that are personalized to users, bandit algorithms are increasingly used to address sequential decision making problems in health-care, online education, and public policy [Caria et al., 2020, Kasy and Sautmann, 2019]. For example, in mobile health, bandit algorithms are used to determine when interventions should be delivered to help users manage chronic health problems like obesity [Klasnja et al., 2020], addiction [Barnett et al., 2020, Song et al., 2019, Bell et al., 2020] and mental illness [Neary and Schueller, 2018, Lipschitz et al., 2019]. Bandit algorithms are used to personalize teaching strategies to each student in online education problems [Liu et al., 2014, Rafferty et al., 2019, Shaikh et al., 2019] and to learn when to send useful reminders to defendants about their upcoming court dates[Stanford Computational Public Policy Lab: <https://policylab.stanford.edu/projects/nudge.html>]. In the contextual bandit framework, the algorithm personalizes by learning to choose the best interventions in each context, i.e., the action that leads to the greatest expected reward. How well a bandit algorithm personalizes is measured by its regret, which is the total expected reward under that algorithm compared to the total expected reward of an oracle algorithm.

Besides the goal of regret minimization and personalizing interventions to each user online, another critical goal in these real world problems is to be able to use the resulting data collected by bandit algorithms to advance scientific knowledge [Liu et al., 2014, Erraqabi et al., 2017]. By scientific knowledge, we specifically mean information gained by using the data collected to conduct a variety of machine learning and statistical analyses, including confidence interval construction. While the personalization or regret-minimizing objective is a within-experiment learning objective, gaining scientific knowledge from the resulting adaptively collected data is a between-experiment learning objective, which ultimately helps with regret minimization between deployments of bandit algorithms. Here we refer to deployments of bandit algorithms as “experiments” because using a bandit algorithm is a type of experimental design. Note that the data collected by any reinforcement learning algorithm is adaptively collected because previous observations are used to inform what actions to select in future timesteps.

While in theoretical problems it is generally assumed that all interesting  outcomes in  bandit experiments are subsumed in the reward, in real life sequential decision making problems there are often a variety of additional scientifically interesting outcomes that are collected during the bandit experiment. For example, in the online advertising setting, the reward might be whether an ad is clicked on, but one may be interested in the outcome of amount of money spent or the subsequent time spent on  the advertiser's website. If it was found an ad had high click-through rate, but low amounts of money was spent after clicking on the ad, one may redesign  the reward for use in the next bandit  experiment.
One type of after-study analysis would be to  construct confidence intervals for the relative effect of the actions on multiple outcomes (in addition to the reward)  conditional on the context.
Furthermore, due to engineering and practical limitations, some of the variables that might be useful as context are often not accessible to the bandit algorithm during the bandit experiment. If after-study analyses find some such contextual variables to have sufficiently strong influence on the relative usefulness of an action, this might lead investigators to ensure these variable are accessible to the bandit algorithm in the next experiment.

Similarly, engineering and practical limitations might mean that the action space included in the current bandit experiment does not subsume the entire space of actions of interest.  For example in the online education setting, not all interesting teaching strategies might be included as actions due to time constraints in implementing the bandit experiment. If it is found that no teaching strategies perform well in a particular context (context could include student's background, student's recent progress, etc.), it may make sense to develop new teaching strategies that are specifically designed to do better in that context.

As discussed above, we can gain scientific knowledge from bandit data by

constructing confidence intervals and

hypothesis tests for unknown quantities such as the effect of the actions on outcomes in different contexts.

Unfortunately, standard statistical methods developed for independently collected data fail to provide
valid inference when applied to bandit data. For example, on data collected with common bandit algorithms, the sample mean of rewards from an arm

fails to converge uniformly in distribution, which precludes use of this distribution in

constructing uniformly valid confidence intervals [Hadad et al., 2019, Deshpande et al., 2018, Zhang et al., 2020].

Recently, statistical inference methods for use with simple models have been developed for data collected using bandit algorithms [Hadad et al., 2019, Deshpande et al., 2018, Zhang et al., 2020]. However, there is a lack of general statistical inference methods for bandit data in more complex data analytic settings, including parameters in non-linear models for outcomes such as the reward.

For example, there are currently no methods for constructing uniformly valid confidence intervals for the parameters of a logistic regression model for binary outcomes or for constructing confidence intervals based on robust estimators like the median or minimizers of the Huber loss function on bandit data.

In this work we show that a wide variety of estimators which are frequently used both in  science and industry on independently sampled data,

namely, M-estimators [Van der Vaart, 2000], can be used to conduct valid inference on bandit data when adjusted with adaptive weights, i.e., weights that are a function of previously collected data.
The use of adaptive weights is common throughout the previously developed methods for conducting statistical inference on bandit data for simple models [Deshpande et al., 2018, Hadad et al., 2019, Zhang et al., 2020].

The adaptive weights we use most closely resemble those of [Hadad et al., 2019].  [Hadad et al., 2019] use adaptive weights  to stabilize the variance of estimators for both the mean reward for an arm and the difference in mean rewards for two arms.

We show that adaptive weights can be used with a much larger class of statistical models to conduct valid inference on bandit data.

An outline of our paper is as follows:

* Section <ref> formalizes the problem statement and introduces notation.

* Section <ref> introduces adaptively weighted M-estimators and presents how to construct uniformly valid asymptotic confidence intervals with these estimators.

* Section <ref> discusses related work.

* Section <ref> gives simulation results for weighted versions of common M-estimators on bandit data.

* Section <ref> discusses open questions regarding the use of bandit algorithms to collect data when the goal is to both personalize as well as use the resulting data to improve scientific knowledge.

§ PROBLEM FORMULATION AND NOTATION

We assume that the data we have after running a contextual bandit algorithm is comprised of contexts $\{ X_t \}_{t=1}^T$, actions $\{ A_t \}_{t=1}^T$, and rewards $\{ R_t \}_{t=1}^T$, and outcomes $\{ Y_t \}_{t=1}^T$. We assume that rewards are a deterministic function of the outcomes, i.e., $R_t = f(Y_t)$ for some known function $f$.

We are primarily interested in estimating parameters of the data generating distribution of $Y_t$ given $(X_t, A_t)$.

$T$ is deterministic.

Below we consider $T \to \infty$ in order to derive the asymptotic distributions of estimators and the resulting confidence intervals based on the asymptotic distributions.
We use potential outcome notation [Imbens and Rubin, 2015] and assume that the potential outcomes $\{ X_t, Y_t(a) : a \in \MC{A} \}$ are i.i.d. random variables across $t \in [1 \colon T]$. The observed outcomes are given by $Y_t := Y_t(A_t)$ and $R_t := R_t(A_t)$.
We define the history $\HH_t := \{ X_{t'}, A_{t'}, Y_{t'} \}_{t'=1}^t$. Actions $A_t \in \MC{A}$ are selected according to action selection probabilities $\pi_{t,a} = P \left( A_t = a | \HH_{t-1}, X_t \right)$. We allow the action space $\MC{A}$ to be finite or infinite; if the action space is infinite then for each $t \in [1 \colon T]$, $\pi_{t,a}$ is a probability density function over $a \in \MC{A}$. Note that while we assume i.i.d potential outcomes, since the contextual bandit algorithm uses past data $\HH_{t-1}$ to choose action selection probabilities $\pi_{t,a}$, the observed data $\{ X_t, A_t, Y_t \}$ are not independent across $t \in [1 \colon T]$.

We are interested in constructing confidence intervals for some unknown $\theta^* \in \Theta \subset \real^d$, which is a parameter of the data generating distribution of $Y_t$ given $(X_t, A_t)$.
Specifically, we assume that $\theta^*$ is a conditionally maximizing value of criterion $m_{\theta}$, i.e.,

\begin{equation}
\label{eqn:thetastar}
\theta^* \in \argmax_{\theta \in \Theta} E_{\theta^*} \left[ m_{\theta} ( Y_t, X_t, A_t ) | X_t, A_t \right] ~ \TN{ w.p. } 1.
\end{equation}

Note that $\theta^*$ does not depend on $X_t$ and $A_t$.

To estimate $\theta^*$, we use  M-estimation [Huber, 1992, Van der Vaart, 2000], which selects the estimator $\hat{\theta}$ to be the $\theta \in \Theta$ that maximizes a criterion function of the following form:

\begin{equation*}
\hat{\theta} = \argmax_{\theta \in \Theta} \sum_{t=1}^T m_{\theta} ( Y_t, X_t, A_t ).
\end{equation*}

For example, in a classical linear regression setting with $K$ treatments, a natural choice for $m_{\theta}$ would be the squared loss function:

\begin{equation*}
m_{\theta} ( Y_t, X_t, A_t ) = - \sum_{k=1}^K \left( Y_t - X_t^\top \theta_{A_t} \right)^2.
\end{equation*}

Other natural choices for

$m_{\theta}$ include likelihood functions and other loss functions. In the case that $Y_t$ is binary and $|\MC{A}| = K$, we might choose $m_{\theta}$ to be a logistic regression model:

\begin{equation*}
m_{\theta} ( Y_t, X_t, A_t )
= - \left[ Y_t X_t^\top \theta_{A_t} - \log \left( 1 + \exp \left( X_t^\top \theta_{A_t} \right) \right) \right].
\end{equation*}

For more details about GLMs see Appendix <ref> and Agresti, 2015.
When the data, $\{X_t,A_t, Y_t\}_{t=1}^T$, are  independently distributed,  classical approaches can be used to prove the consistency and asymptotic normality of M-estimators [Van der Vaart, 2000]. However

standard M-estimators (like the ordinary least squares estimator) fail to be asymptotically normal when used on bandit data and fail to provide valid confidence intervals based on a normal approximation [Hadad et al., 2019, Deshpande et al., 2018, Zhang et al., 2020]. In this work, we show that M-estimators can still be used for provide valid statistical inference on bandit data as long as they are adjusted with well-chosen adaptive weights.

§ ADAPTIVELY WEIGHTED M-ESTIMATORS

§.§ Introducing the Estimator

We consider a weighted M-estimating criteria with adaptive weights $W_t \in \sigma (\HH_{t-1}, X_t, A_t)$ given by $W_t = \sqrt{ \frac{ \pi_{t,A_t}^{\TN{eval}} }{ \pi_{t,A_t} } }$. Here $\{ \pi_t^{\TN{eval}} \}_{t=1}^T \in \sigma(\HH_0)$ are evaluation policies of choice and $\pi_{t,a}^{\TN{eval}} = P_{\pi_t^{\TN{eval}}} (A_t = a | X_t)$. We discuss considerations for the choice of $\{ \pi_t^{\TN{eval}} \}_{t=1}^T$ in section <ref>, but a default choice for the evaluation policy when the action space is finite and of size $K$, is just $\pi_{t,a}^{\TN{eval}} = 1/K$.
We call these weights square-root importance weights because they are the square-root of the standard importance weights which are commonly used in reinforcement learning [Thomas and Brunskill, 2016, Jiang and Li, 2016] and Monte Carlo methods [Hammersley, 2013]. Our estimator $\thetahat_T$ for $\theta^*$ is the maximizer of the weighted M-estimating criterion:

\begin{equation*}
\thetahat_T := \argmax_{\theta \in \Theta} \sum_{t=1}^T W_t m_\theta (Y_t, X_t, A_t)
= \argmax_{\theta \in \Theta} M_T( \theta ).
\end{equation*}

Although $W_t$ in this paper will always be square-root importance weights, we note that if instead $W_t$ were set to $1$, the above equation would correspond to a standard unweighted M-estimator.

In this work, our goal is to derive asymptotically valid confidence intervals for $\theta^*$. Specifically we will do this by deriving the asymptotic limiting distribution of $\hat\theta_T$ as $T \to \infty$ and by demonstrating that the convergence to the limiting distribution is uniform over
$\theta^* \in \Theta$. Intuitively, uniformity fails if for any sample size, $T$, there exists a $\theta^*_T \in \Theta$ for which the probability that the $1-\alpha$ confidence interval contains  $\theta^*_T$ is  less than  $1-\alpha$.

Formally, uniformly asymptotically valid $1-\alpha$ level confidence intervals $C_T$ for $\theta^*$ satisfy:

\begin{equation}
\label{eqn:uniformCI}
\liminf_{T \to \infty} \inf_{\theta^* \in \Theta} P_{\theta^*} \left( \theta^* \in C_T(\alpha) \right) \geq 1-\alpha.
\end{equation}

Confidence intervals constructed using asymptotic approximations fail to be reliable when convergences does not hold uniformly over the parameter space. The importance of uniformity for the reliability of confidence intervals in practice is discussed in many areas of statistics including statistical inference via boostrap [Romano et al., 2012], statistical inference after model selection [Leeb and Pötscher, 2005], and econometrics [Kasy, 2019]. Note that on i.i.d. data, “uniformity” in convergence typically comes for free, i.e., on i.i.d. data it is generally straightforward to show that estimators that converge in distribution do so uniformly. However, as discussed in Zhang et al., 2020, estimators that converge uniformly on independently collected data can fail to converge uniformly on data collected with bandit algorithms. See Appendix <ref> for information on the importance of uniformity and how uniform convergence of estimators can fail.

To construct uniformly valid confidence intervals for $\theta^*$
we prove

that $\thetahat_T$ is uniformly asymptotically normal:

\begin{equation*}
\Sigma_{\theta^*, T}^{-1/2} \left[ \frac{1}{T} \ddot{M}_T( \thetahat_T ) \right] \sqrt{T} ( \thetahat_T - \theta^* )
\Dto \N \left( 0, I_d \right) \TN{ uniformly over } \theta^* \in \Theta,
\end{equation*}

where $\dot{M}_T( \theta ) = \frac{\partial}{\partial \theta} M_T( \theta )$, $\ddot{M}_T( \theta ) = \frac{\partial^2}{\partial^2 \theta} M_T( \theta )$, and $\Sigma_{\theta^*, T} := \frac{1}{T} \sum_{t=1}^T E_{\theta^*, \pi_t^{\TN{eval}}} \left[ \dot{m}_{\theta^*}(Y_t, X_t, A_t)^{\otimes 2} \right]$. We define $P_{\theta^*, \pi_t^{\TN{eval}}}$ to be the distribution of $(Y_t, X_t, A_t)$ when $A_t$ are selected according to the evaluation policy $\pi_t^{\TN{eval}}$.

§.§ Intuition for Square-Root Importance Weights

To provide some intuition for how weighting M-estimators with square-root importance weights $W_t = \sqrt{ \frac{\pi_{t,A_t}^{\TN{eval}}}{\pi_{t,A_t}} }$ ensures uniform asymptotic normality, we consider the weighted least squares estimator as an example.
Assume that $E_\theta [ Y_t | A_t, X_t ] = \phi(X_t, A_t)^\top \theta$  holds with probability $1$ and that $\pi_{t}^{\TN{eval}}$ is the same for all $t \in [1 \colon T]$ so that we can drop the $t$ index. We include adaptive weights $W_t$ on the following least squares criterion to estimate $\theta^*$, as defined in equation (<ref>),

\begin{equation}
\label{eqn:awlscriterion}
\hat{\theta}^{\TN{AW-LS}} := \argmax_{\theta \in \Theta} \left\{- \frac{1}{2} \sum_{t=1}^T W_t \left( Y_t - \phi(X_t, A_t)^\top \theta \right)^2 \right\}.
\end{equation}

By taking the derivative of the criterion equation (<ref>), we have that

\begin{equation*}
0 = \sum_{t=1}^T W_t \phi(X_t, A_t) \left( Y_t - \phi(X_t, A_t)^\top \hat{\theta}^{\TN{AW-LS}} \right).
\end{equation*}

By Taylor Series expansion,

\begin{equation*}
= \sum_{t=1}^T W_t \phi(X_t, A_t) \left( Y_t - \phi(X_t, A_t)^\top \theta^* \right)
- \sum_{t=1}^T W_t \phi(X_t, A_t)^{\otimes 2} \left( \hat{\theta}^{\TN{AW-LS}} - \theta^* \right).
\end{equation*}

Rearranging terms, we have the following:

\begin{equation}
\label{eqn:awlsEquation}
\frac{1}{ \sqrt{T} } \sum_{t=1}^T W_t \phi(X_t, A_t)^{\otimes 2} \left( \hat{\theta}^{\TN{AW-LS}} - \theta^* \right)
= \frac{1}{ \sqrt{T} } \sum_{t=1}^T W_t \phi(X_t, A_t) \left( Y_t -\phi(X_t, A_t)^\top \theta^* \right).
\end{equation}

Note that the right hand side of equation (<ref>) above is a martingale difference sequence with respect to history $\{ \HH_{t-1} \}_{t=1}^T$, i.e., $E_{\theta^*} \left[ W_t \left( Y_t - \phi(X_t, A_t)^\top \theta^* \right) | \HH_{t-1} \right] = 0$, since $W_t \in \sigma(\HH_{t-1}, X_t, A_t)$ and $E_{\theta^*} [ Y_t | A_t, X_t ] = \phi(X_t, A_t)^\top \theta^*$. We can show that (<ref>) is asymptotically normal by applying a martingale central limit theorem [Dvoretzky, 1972]. Specifically for a martingale difference sequence $\{ Z_t\}$ with respect to $\{ \HH_{t-1} \}_{t=1}^T$, $\frac{1}{\sqrt{T}} \sum_{t=1}^T Z_t \Dto \N(0, \sigma^2)$ uniformly over $\theta^* \in \Theta$ under the following two conditions:

* Conditional Variance: $\frac{1}{T} \sum_{t=1}^T E_{\theta^*} \left[ Z_t^2 | \HH_{t-1} \right] \Pto \sigma_{\theta^*}^2$ uniformly over $\theta^* \in \Theta$ for $\sigma_{\theta^*}$ uniformly bounded above zero for all $\theta^* \in \Theta$

* Conditional Lindeberg: For any $\delta > 0$, $\frac{1}{T} \sum_{t=1}^T E_{\theta^*} \left[ Z_t^2 \1_{|Z_t| > \delta \sqrt{T} } \big| \HH_{t-1} \right] \Pto 0$ uniformly over $\theta^* \in \Theta$.

Note that to satisfy the conditional Lindeberg condition, it is sufficient for $E_{\theta^*}[ Z_t^4 | \HH_{t-1} ] < m < \infty$ for some constant $m$ for all $t$ and $\theta^* \in \Theta$. Since it is more straightforward to show the Lindeberg condition holds under sufficient moment assumptions, we focus on ensuring that our choice of adaptive weights ensures that the conditional variance condition holds. To ensure that the martingale difference sequence of equation (<ref>) satisfies the conditional variance condition, we choose adaptive weights $W_t$ such that the following holds for some fixed positive definite matrix $\Sigma_{\theta^*}$:

\begin{equation}
\label{eqn:condvar}
\frac{1}{T} \sum_{t=1}^T E_{\theta^*} \left[ W_t^2 \phi(X_t, A_t)^{\otimes 2} \left( Y_t - \phi(X_t, A_t)^\top \theta^* \right)^2 \bigg| \HH_{t-1} \right] \Pto \Sigma_{\theta^*} \TN{ uniformly over } \theta^* \in \Theta.
\end{equation}

We will now show how our choice of weight $W_t = \sqrt{ \frac{\pi_{A_t}^{\TN{eval}}}{\pi_{t,A_t}} }$ ensures (<ref>) holds by changing the sampling measure for the conditional variance from the adaptive policy $\pi_{t,A_t}$ to the non-adaptive evaluation policy $\pi^{\TN{eval}}$. For square-root importance sampling weights, equation (<ref>) equals the following:

\begin{equation}
\label{eqn:variancestbilizingintuition}
\frac{1}{T} \sum_{t=1}^T E_{\theta^*} \left[ E_{\theta^*} \left[ \frac{ \pi_{A_t}^{\TN{eval}} }{ \pi_{t,A_t} } \phi(X_t, A_t)^{\otimes 2} \left( Y_t - \phi(X_t, A_t)^\top \theta^* \right)^2 \bigg| \HH_{t-1}, X_t \right] \bigg| \HH_{t-1} \right] \\
\end{equation}

\begin{equation*}
\underset{(a)}{=} \frac{1}{T} \sum_{t=1}^T E_{\theta^*} \left[ E_{\theta^*, \pi^{\TN{eval}}} \left[ \phi(X_t, A_t)^{\otimes 2} \left( Y_t - \phi(X_t, A_t)^\top \theta^* \right)^2 \bigg| \HH_{t-1}, X_t \right] \bigg| \HH_{t-1} \right]
\end{equation*}

\begin{equation*}
\underset{(b)}{=} E_{\theta^*, \pi^{\TN{eval}}} \left[ \phi(X_t, A_t)^{\otimes 2} \left( Y_t - \phi(X_t, A_t)^\top \theta^* \right)^2 \right].
\end{equation*}

Above, (a) holds because the weights changes the sampling measure from the adaptive policy $\pi_{t, A_t}$ to the evaluation policy $\pi^{\TN{eval}}$. (b) holds because after changing the sampling measure from the adaptive policy $\pi_t \in \sigma(\HH_{t-1})$ to the non-adaptive
policy $\pi^{\TN{eval}} \in \sigma(\HH_0)$, the distribution of $(Y_t, X_t, A_t)$ no longer depends on history $\HH_{t-1}$.

Since the weights $W_t = \sqrt{ \frac{\pi_{A_t}^{\TN{eval}}}{\pi_{t,A_t}} }$ have the effect of changing the sampling measure of the conditional variance from the adaptive policy $\pi_{t}$ to evaluation policy $\pi^{\TN{eval}}$, they can be interpreted as square-root importance weights or square-root Radon–Nikodym derivative weights. Note that in the setting that the action space $\MC{A}$ is finite, the conditional Lindeberg condition will also hold if we let $W_t = \frac{1}{ \sqrt{\pi_{t,A_t}}}$;  this is equivalent to setting the evaluation policy $\pi^{\TN{eval}}$ to the uniform policy over $\MC{A}$.
The square-root importance weights we use are a form of variance stabilizing weights, akin to those introduced in Hadad et al., 2019 for estimating mean rewards and differences in mean rewards on data collected using multi-armed bandits. In fact, in the special case that $|\MC{A}| = K$ and $\phi(X_t, A_t) = [\1_{A_t=1}, \1_{A_t=2}, ..., \1_{A_t=K}]^\top$, the adaptively weighted least squares estimator is equivalent to the weighted average estimator of Hadad et al., 2019.

In Figure <ref>, we show plots of the least squares estimator z-statistic both with and without adaptive weighting for data collected using Thompson Sampling on a two-arm bandit. It is clear that the least squares z-statistic for estimators of $\theta_1^*$ is much closer to a normal distribution with adaptive weighting.

Above we plot the empirical distribution of the OLS and the AW-LS estimator with weights $W_t = \frac{1}{ \sqrt{\pi_{t,A_t}} }$, in a two arm bandit setting. We perform Thompson Sampling with standard normal priors, $\theta^* = [ \theta_0^*, \theta_1^*]^\top = [0,0]^\top$, standard normal errors, and $T=1000$. Specifically we plot $\sqrt{\sum_{t=1}^T A_t } ( \hat{\theta}_{1,T}^{\OLS} - \theta_1^* )$ in the left histogram and $\frac{1}{\sqrt{T}} \sum_{t=1}^T \frac{ A_t }{\sqrt{\pi_{t,1}}} ( \hat{\theta}_{1,T}^{\TN{AW-LS}} - \theta_1^* )$ in the right histogram.

§.§ Asymptotic Normality

In this section, we discuss the conditions under which we  prove that

\begin{equation*}
%    \label{eqn:Zestgoal}
\Sigma_{\theta^*, T}^{-1/2} \left[ \frac{1}{T} \ddot{M}_T( \thetahat_T ) \right] \sqrt{T} ( \thetahat_T - \theta^* )
\Dto \N \left( 0, I_d \right) \TN{ uniformly over } \theta^* \in \Theta.
\end{equation*}

In general, the conditions we assume differ from those made for standard M-estimators on i.i.d. data because (i) we guarantee convergence in distribution that is uniform over $\theta^* \in \Theta$, which is stronger than the guarantee of asymptotic normality for each fixed $\theta^* \in \Theta$, and (ii) $\pi_{t,a}$ can depend on $\HH_{t-1}$ and $X_t$.

[Stochastic Contextual Bandit Environment]

$X_t$ are i.i.d., $Y_t$ is independent of $\mathcal{H}_{t-1}$ given $X_t, A_t$, and the conditional distribution $Y_t \mid X_t, A_t$ is in variant over $t \in [1 \colon T]$.

Adopting potential outcome notation, condition <ref> is satisfied when $\left\{ X_t, Y_t(a) : a \in \MC{A} \right\}$ are i.i.d. across $t \in [1 \colon T]$. Note that action space $\MC{A}$ can be finite or infinitely large.

The first three derivatives of $m_\theta(Y_t, X_t, A_t)$ with respect to $\theta$ exist for all $\theta \in \Theta$ almost surely with respect to $P_{ \theta^*, \pi_t^{\TN{eval}} }$ for all $t \in [1 \colon T]$.

[Bounded Parameter Space]

$\theta^* \in \Theta$ compact for $\Theta$ open subset of $\real^d$.

There exists some function $g$ such that $E_{\theta^*, \pi_t^{\TN{eval}}}[ g (Y_t, X_t, A_t)^2 ]$ is uniformly bounded over $\theta^* \in \Theta$ and $\{ \pi_t^{\TN{eval}} : t \geq 1 \}$, which satisfies the following for all $\theta, \theta' \in \Theta$:

\begin{equation*}
\left| m_{\theta}  (Y_t, X_t, A_t)  - m_{\theta'}  (Y_t, X_t, A_t) \right| \leq g  (Y_t, X_t, A_t) \| \theta - \theta' \|_2.
\end{equation*}

Conditions <ref> and <ref> together are used to ensure the following functionally uniform law of large numbers result that $\sup_{\theta \in \Theta} \left| \sum_{t=1}^T W_t m_{\theta} (Y_t, X_t, A_t) - E_{\theta^*} \left[ W_t m_{\theta} (Y_t, X_t, A_t) | \HH_{t-1} \right] \right| = o_p(1)$ uniformly over $\theta^* \in \Theta$. This property is used to prove the consistency of $\thetahat_T$. On i.i.d. data, an analogous functional uniform law of large numbers result holds under these conditions. Additionally, on i.i.d. data consistency can be shown without assuming the parameter space is compact when $m_\theta$ is assumed to be concave in $\theta$, by showing that $\hat{\theta}_T$ are contained within a bounded space eventually [Van der Vaart, 2000, Engle, 1994, Bura et al., 2018]. We expect that a similar result would hold for our adaptively weighted M-estimators.

The fourth moments of $m_{\theta^*} (Y_t, X_t, A_t)$, $\dot{m}_{\theta^*} (Y_t, X_t, A_t)$ and $\ddot{m}_{\theta^*} (Y_t, X_t, A_t)$ with respect to $P_{ \theta^*, \pi_t^{\TN{eval}} }$ are bounded uniformly over $\theta^* \in \Theta$ and $\{ \pi_t^{\TN{eval}} : t \geq 1 \}$.
For all sufficiently large $T$, the minimum eigenvalue of $\Sigma_{T, \theta^*} = \frac{1}{T} \sum_{t=1}^T E_{ \theta^*, \pi_t^{\TN{eval}} } \left[ \dot{m}_{\theta^*} (Y_t, X_t, A_t)^{\otimes 2} \right]$ is bounded above $\delta_{\dot{m}^2} > 0$ for all $\theta^* \in \Theta$.

Condition <ref> is similar to those those made in <cit.>. However, in order to guarantee uniform convergence in distribution we assume that moment bounds hold uniformly over $\theta^* \in \Theta$ and $\{ \pi_t^{\TN{eval}} : t \geq 1 \}$.

[Third Derivative Domination]

There exists a function $\dddot{m} (Y_t, X_t, A_t)$ such that for some $\epsilon_{ \dddot{m} } > 0$, the following holds with probability $1$,

\begin{equation}
\label{eqn:thirdderiv}
\sup_{\theta \in \Theta : \| \theta - \theta^* \| \leq \epsilon_{\dddot{m}} } \| \dddot{m}_{\theta} (Y_t, X_t, A_t) \|_1
\leq \| \dddot{m} (Y_t, X_t, A_t) \|_1.
\end{equation}

Above, for any $B \in \real^{d \by d \by d}$, we denote $\| B \|_1 = \sum_{i=1}^d \sum_{j=1}^d \sum_{k=1}^d |B_{i,j,k}|$.
Also the second moment of $\dddot{m} (Y_t, X_t, A_t)$ with respect to $P_{ \theta^*, \pi_t^{\TN{eval}} }$ are bounded uniformly over $\theta^* \in \Theta$ and $\{ \pi_t^{\TN{eval}} : t \geq 1 \}$.

Condition <ref> equation (<ref>) is similar to assumptions made in classical proofs of the asymptotic normality of M-estimators; see <cit.>.

[Maximizing Solution]

* $\theta^* \in \argmax_{\theta \in \Theta} E_{\theta^*} \left[ m_{\theta}(Y_t, X_t, A_t) \big| X_t, A_t \right]$ with probability $1$ for all $t \in [1 \colon T]$. Also $E_{\theta^*} \left[ \dot{m}_{\theta^*}(Y_t, X_t, A_t) \big| X_t, A_t \right] = 0$ with probability $1$ for all $t \in [1 \colon T]$.

* The minimum of the absolute values of eigenvalues of $\frac{1}{T} \sum_{t=1}^T E_{ \theta^*, \pi_t^{\TN{eval}} } \left[ \ddot{m}_{\theta^*} (Y_t, X_t, A_t) \right]$ is bounded above $\delta_{\ddot{m}} > 0$ for all $\theta^* \in \Theta$ for all sufficiently large $T$.

Condition <ref> ensures that $\theta^*$ is a conditionally maximizing solution for all contexts $X_t$ and actions $A_t$. Note that it does not require that $\theta^*$ is conditionally always a unique optimal solution, which means that our theory allows for there to be no unique optimal $\theta^*$ for some contexts and actions. We will use condition <ref> to ensure that $\{ \dot{m}_{\theta^*} (Y_t, X_t, A_t) \}_{t=1}^T$ is a martingale difference sequence with respect to $\{ \HH_t \}_{t=1}^T$.

[Well-Separated Solution]

For sufficiently large $T$, for any $\epsilon > 0$, there exists some $\delta > 0$ such that

\begin{equation*}
\inf_{\theta \in \Theta:\|\theta-\theta^*\|_2 > \epsilon} \left\{ \frac{1}{T} \sum_{t=1}^T E_{\theta^*, \pi_t^{\TN{eval}}} \left[ m_{\theta^*,t} - m_{\theta,t} \right] \right\}
\geq \delta,
\end{equation*}

for all $\theta^* \in \Theta$.

A well-separated solution condition akin to condition <ref> is commonly assumed to prove consistency of M-estimators, e.g., see <cit.>.

[Adaptive Square-Root Importance Weights]

We set adaptive weights $W_t = \sqrt{ \frac{ \pi_{t,A_t}^{\TN{eval}} }{ \pi_{t, A_t} } }$  for evaluation policies $\{ \pi_t^{\TN{eval}} \}_{t=1}^T \in \sigma(\HH_{0})$. Also for all $t \in [1 \colon T]$, $\sqrt{\rho_{\min}} \leq W_t \leq \sqrt{\rho_{\max}}$ w.p. $1$ for some constants $0 < \rho_{\min} \leq \rho_{\max} < \infty$.

Under Conditions <ref>-<ref> and <ref>-<ref> we have that $\hat{\theta}_T \Pto \theta^*$ uniformly over $\theta^* \in \Theta$.

Let $\hat{\theta}_T \Pto \theta^*$ uniformly over $\theta^* \in \Theta$. Under Conditions <ref>, <ref>, <ref>- <ref>, and <ref>,

\begin{equation}
\label{eqn:Zestgoal}
\Sigma_{\theta^*, T}^{-1/2} \left[ \frac{1}{T} \ddot{M}_T( \thetahat_T ) \right] \sqrt{T} ( \thetahat_T - \theta^* )
\Dto \N \left( 0, I_d \right) \TN{ uniformly over } \theta^* \in \Theta.
\end{equation}

§.§ Confidence Intervals

Standard asymptotic normality results for estimators on i.i.d. data typically are of the form $\sqrt{T} ( \thetahat_T - \theta^* ) \Dto \N(0, \Sigma)$.

However, our result is not of this form because $\frac{1}{T} \ddot{M}_T( \thetahat_T )$ in equation (<ref>) fails to converge in probability to a constant uniformly under common bandit algorithms. For this reason, we use projected confidence regions when constructing confidence regions for subsets of indices of $\theta^*$; note that these projections are not needed when constructing joint confidence regions for the entire vector $\theta^*$. The asymptotic normality result of equation (<ref>) guarantees that for $d$-dimensional $\theta^*$,

\begin{equation*}
\liminf_{T \to \infty} \inf_{\theta^* \in \Theta} P_{\theta^*} \left( \frac{1}{T} ( \thetahat_T - \theta^* )^\top \ddot{M}_T( \thetahat_T )^\top \Sigma_{\theta^*, T}^{-1} \ddot{M}_T( \thetahat_T ) ( \thetahat_T - \theta^* )
\leq \chi^2_{d,(1-\alpha)} \right) = 1-\alpha.
\end{equation*}

Note that the region

\begin{equation}
\label{eqn:ellipse}
\left\{ \theta \in \Theta : \frac{1}{T} ( \thetahat_T - \theta )^\top \ddot{M}_T( \thetahat_T )^\top \Sigma_{\theta^*, T}^{-1} \ddot{M}_T( \thetahat_T ) ( \thetahat_T - \theta )
\leq \chi^2_{d,(1-\alpha)} \right\}
\end{equation}

defines a $d$-dimensional hyper-ellipsoid confidence region for $\theta^*$. Suppose we are interested in constructing a confidence region for $d_1$-dimensional $\theta_1^*$ where $\theta^* = [\theta_0^*, \theta_1^*]$. We can project the ellipse defined in equation (<ref>) onto a $d_1$-dimensional space to get a $d_1$-dimensional ellipsoid, which represents the confidence region for $\theta_1^*$. See Figure <ref> for an example of a two-dimensional ellipsoid projected onto one dimension. See Appendix <ref> for more details of how to construct projected confidence regions.

Projection of two-dimensional ellipse onto one dimension (x-axis).

§.§ Choice of Evaluation Policy

When the action space is bounded, a natural default choice for $\pi_t^{\text{eval}}$ is the uniform distribution over $\MC{A}$, and since the weights are invariant to scaling by a global constant, this choice corresponds to $W_t = \frac{1}{\sqrt{\pi_{t,A_t}} }$.

In general though, when the action space is not bounded, it is necessary to explicitly choose $\pi_{t,A_t}^{\TN{eval}}$.

We now discuss how to choose evaluation policies $\{ \pi_t^{\TN{eval}} \}_{t=1}^T$ in order to minimize the asymptotic variance of adaptively weighted estimators.
We focus on the adaptively weighted least squares estimator in a multi-armed bandit setting. Let $\vec{A}_t = [ \1_{A_t = 1}, \1_{A_t = 2}, ..., \1_{A_t = | \MC{A} | } ]^\top$. The least squares estimator has function $m_\theta = - \frac{1}{2} (Y_t - \vec{A}_t^\top \theta)^2$.

We assume that $E[ Y_t | A_t ] = \theta^\top \vec{A}_t$ and that $E[ (Y_t - \vec{A}_t^\top \theta)^2 | A_t=a ] = \sigma_a^2$ for all $a \in \MC{A}$. The adaptively weighted least squares estimator is defined as $\hat{\theta}^{\TN{AW-LS}} := \argmax_{\theta \in \Theta} \left\{  \sum_{t=1}^T W_t \left( Y_t - \vec{A}_t^\top \theta \right)^2 \right\}$.

The variance of $\hat{\theta}_T^{\TN{AW-LS}}$ is as follows:

\begin{equation}
\label{eqn:pievalLowerbound}
\sum_{a=1}^{|\MC{A}|} \vec{a}^\top \vec{a} \sigma_a^2 \frac{ \frac{1}{T} \sum_{t=1}^T \pi_{t,a}^{\TN{eval}} }{ \left( o_p(1) + \frac{1}{T} \sum_{t=1}^T \sqrt{ \pi_{t,a} \pi_{t,a}^{\TN{eval}} } \right)^2 }
\end{equation}

Above, $\vec{a} = [ \1_{a = 1}, \1_{a = 2}, ..., \1_{a = | \MC{A} | } ]^\top$. By Cauchy-Schwartz inequality, we can lower bound each term in the summation in (<ref>):

\begin{equation}
\vec{a}^\top \vec{a} \sigma_a^2 \frac{ \frac{1}{T} \sum_{t=1}^T \pi_{t,a}^{\TN{eval}} }{ \left( \frac{1}{T} \sum_{t=1}^T \sqrt{ \pi_{t,a} \pi_{t,a}^{\TN{eval}} } \right)^2 }
\succeq \vec{a}^\top \vec{a} \sigma_a^2 \frac{1}{ \frac{1}{T} \sum_{t=1}^T \pi_{t,a} }.
\end{equation}

Note that this lower bound is achieved when $\pi_{t,a}^{\TN{eval}} = \pi_{t,a}$. However, since $\pi_{t,a}$ is random and $\{ \pi_{t}^{\TN{eval}} \}_{t=1}^T \in \sigma(\HH_0)$, setting $\pi_{t,a}^{\TN{eval}} = \pi_{t,a}$ is generally an unfeasible choice. We want to choose $\pi_{t,a}^{\TN{eval}}$ to match $\pi_{t,a}$ as close as possible subject to the constraint that $\pi_{t,a}^{\TN{eval}} \in \HH_0$. Thus to approximately minimize the variance of the AW-LS estimator we propose setting $\pi_{t,a}^{\TN{eval}} = E_{\theta^*} [ \pi_{t,a} ]$ for all $t \in [1 \colon T]$. Note that $E_{\theta^*}[\pi_{t,a}]$ depends on the value of $\theta^*$, which is unknown. Thus, it is natural to choose $\pi_{t,a}^{\TN{eval}}$ to be $E_{\theta^*}[\pi_{t,a}]$ weighted by a prior on $\theta^*$. Note that as long as the evaluation policy ensures that weights $W_t$ are bounded, the choice of evaluation policy does not affect the asymptotic validity of the estimator.

In Figure <ref>, we display the difference in mean squared error for the AW-LS estimator for two different choices of evaluation policy: (1) the uniform evaluation policy which selects actions uniformly from $\MC{A}$ and (2) the expected $\pi_{t,a}$ evaluation policy for which $\pi_{t,a}^{\TN{eval}} = E_{\theta^*}[\pi_{t,a}]$. We can see in this setting that by setting $\pi_{t,a}^{\TN{eval}} = E_{\theta^*}[\pi_{t,a}]$ we are able to decrease the mean squared error of the AW-LS estimator compared AW-LS with the uniform evaluation policy. Note though that in some cases setting $\pi_{t,a}^{\TN{eval}} = E_{\theta^*}[\pi_{t,a}]$ is equivalent to choosing the uniform evaluation policy. For example, in the two arm bandit case in which $\theta^* = [ \theta_0^*, \theta_1^*]^\top$, note that when $\theta_0^* = \theta_1^*$, both arms are optimal so under common bandit algorithms $E_{\theta^*}[\pi_{t,a}] = 0.5$ for all $t \in [1 \colon T]$, which will make the evaluation policy $\pi_{t,a}^{\TN{eval}} = E_{\theta^*}[\pi_{t,a}]$ equivalent to the uniform policy.

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 $\MC{A}$ and (2) expected $\pi_{t,a}$ evaluation policy for which $\pi_{t,a}^{\TN{eval}} = E_{\theta^*}[\pi_{t,a}]$ (oracle quantity). In a two arm bandit setting we perform Thompson Sampling with standard normal priors, $0.01$ clipping, $\theta^* = [ \theta_0^*, \theta_1^*]^\top = [0,1]^\top$, standard normal errors, and $T=1000$. Error bars denote standard errors computed over 5,000 Monte Carlo simulations.

§ RELATED WORK

The adaptive clinical trials literature mostly uses classical statistical methods, like ordinary least squares (OLS) and maximum likelihood estimation, and associated asymptotic approximations to the distributions of the estimators and test statistics to conduct statistical inference [Hu and Rosenberger, 2006, Hu et al., 2009]. This is possible because algorithms with smooth limiting allocations (i.e., the limiting rate at which arms are selected is a smooth function of the difference in expected rewards) are used. While smooth limiting allocation functions preclude algorithms with sub-linear regret (which includes all regret-minimizing bandit algorithms), they are the focus of that literature
because the increased exploration increases the power of tests on the resulting data.

Villar et al., 2015 and Rafferty et al., 2019 empirically illustrate that classical OLS inference methods have inflated Type-1 error when used on data collected with any of a variety of regret-minimizing multi-armed bandit algorithms. There have been a variety of recent works proposing alternative methods for statistical inference using asymptotic approximations on bandit data. The common thread between all of these methods is that they all utilize a form of adaptive weighting.
The first work in this area was by Deshpande et al., 2018 who construct the W-decorrelated estimator, which adjusts the standard OLS estimator with a sum of adaptively weighted residuals. As discussed in the appendix of Zhang et al., 2020, in the multi-armed bandit setting, the W-decorrelated estimator up-weights observations from early in the study and down-weights observations from later in the study. In the batched bandit setting, Zhang et al., 2020 show that the Z-statistics for the OLS estimators computed separately on each batch are jointly asymptotically normal. Standardizing the OLS statistic for each batch effectively adaptively re-weights the observations in each batch.

Hadad et al., 2019 introduce the Adaptively-Weighted Augmented Inverse Propensity Weighted estimator (AW-AIPW) and the Adaptively-Weighted Average estimator (AWA) for inference regarding the expected reward and margin (difference in expected rewards between two arms) for data collected with bandit algorithms. AW-AIPW and AWA are modifications of the standard augmented-inverse propensity weighted (doubly robust) estimator and the sample mean estimator with adaptive weights, respectively. In particular, Hadad et al., 2019 introduce a class of adaptive “variance stabilizing” weights, which guarantee that the variance of a normalized version of their estimators converges in probability to a constant. Note that the AW-AIPW and AWA estimators as presented in Hadad et al., 2019 are limited to only estimating the scalar values (e.g., difference in mean rewards for two arms of a multi-armed bandit) on data collected with bandit algorithms. In the discussion section of Hadad et al., 2019 they discuss three open questions related to their work. Our work addresses two of these questions: 1) “What additional estimators can be used for normal inference with adaptively collected data?” and 2) How do their results generalize to more complex sampling designs, like data collected with contextual bandit algorithms? In this work, we demonstrate that adaptive variance stabilizing weights are not only applicable to estimators for the mean reward and differences in mean rewards. Rather, a large class of M-estimators modified with adaptive square-root importance weights, which are variance stabilizing, can be used to construct uniformly valid confidence intervals using data collected with (contextual) bandit algorithms. This generalization allows us to construct confidence intervals for a much larger class of inferential targets, including multivariate parameters in the contextual bandit setting for a variety of models for the expected outcome.

An alternative to using asymptotic approximations to construct confidence intervals is to use high probability confidence bounds. High probability anytime confidence bounds are used throughout the bandit literature to prove guarantees for algorithms—like regret bounds and best-arm identification probabilities—and for providing anytime-valid confidence intervals and p-values [Abbasi-Yadkori et al., 2011, Howard et al., 2018]. High probability anytime bounds are guaranteed to hold for finite samples (not just asymptotically) and hold simultaneously for any number of observations, i.e., for all $T \geq 1$, and thus provide stronger guarantees than confidence intervals constructed using asymptotic approximations. The downside of using anytime high probability confidence bounds is that they are generally wider than those constructed using asymptotic approximations. Additionally, these methods require a bounded parameter space and moreover that the parameter space bounds are known, as they are explicitly incorporated into the confidence bounds.

The above is a common reason why much of classical statistics, with a long history of success in science, uses asymptotic approximations to provide valid statistical inference.  Here we do the same. In the simulation Section <ref>, we compare our proposed approach to high probability confidence bounds.

§ SIMULATION RESULTS

In this section, we let $Y_t = R_t$. We first consider a linear contextual bandit setting, where the expected reward is a linear function of the parameters. We focus on this setting first because other methods for constructing valid confidence intervals on bandit data have been developed for linear contextual bandit, which we compare to. Later, we will discuss more complicated statistical models.

Specifically, we consider a two-arm linear contextual bandit setting with the following linear model for the expected reward:

\begin{equation*}
E_{\theta}[ R_t | X_t, A_t ] = \tilde{X}_t^\top \theta_0 + A_t \tilde{X}_t^\top \theta_1,
\end{equation*}

where $\tilde{X}_t = [1, X_t]$ ($X_t$ with intercept term) and $A_t \in \{ 0, 1 \}$. We use the weighted least squares estimator (an example of an M-estimator):

\begin{equation*}
\hat{\theta}_T^{\TN{AW-LS}}
= \argmax_{\theta \in \Theta} \left\{ - \sum_{t=1}^T W_t \left(R_t - \tilde{X}_t^\top \theta_0 + A_t \tilde{X}_t^\top \theta_1 \right)^2 \right\}.
\end{equation*}

In the simulations below we generate data using the following model for the expected reward $E_{\theta^*}[ R_t | A_t, X_t ] = \tilde{X}_t^\top \theta_0^* + A_t \tilde{X}_t^\top \theta_1^*$. In our simulations, $X_t$ is two dimensional, which makes $\theta^*$ six dimensional and the parameters of the advantage function, $\theta_1^*$, three dimensional. We set $\theta^* = [\theta_0^*, \theta_1^*] = [0.1,0.1,0.1,0,0,0]$. The contexts $X_t$ are drawn i.i.d. from a uniform distribution. We generate the noise on the rewards, $R_t(A_t)-E_{\theta^*}[R_t|A_t,X_t]$, by sampling i.i.d. from a student's $t$ distribution with five degrees of freedom.

We collect data using Thompson Sampling with a linear model for the expected reward and normal priors [Agrawal and Goyal, 2013]. We constrain the action selection probabilities with clipping at a rate of $0.01$; this means that while typical Thompson Sampling produces action selection probabilities $\pi_{t,a}^{\TN{TS}}$, we instead use action selection probabilities $\pi_{t,a} = 0.01 \vee \left( 0.99 \wedge \pi_{t,a}^{\TN{TS}} \right)$ to select actions. We constrain the action selection probabilities in order to satisfy condition <ref> with the uniform evaluation policy. Also note that increasing the amount the algorithm explores decreases the width of confidence intervals constructed on the resulting data; see section <ref> for more discussion of the trade-off between regret minimization and statistical inference objectives.

As discussed earlier, in order to construct confidence regions for the parameters of the treatment effect or advantage function, $\theta_1^*$,

we use a projected confidence region.

We also compare to the W-decorrelated estimator of Deshpande et al., 2018 and the high probability self-normalized martingale bound of Abbasi-Yadkori et al., 2011. For all our simulations, we use $5,000$ Monte-Carlo repetitions and the error bars plotted are standard errors. See our Appendix <ref> for more details about our simulations, as well as additional simulation results.

Figure <ref> plots the mean squared error of the AW-LS estimator, the unweighted least squares estimator, and the W-decorrelated estimator [Deshpande et al., 2018] computed on the data collected as decribed in the previous paragraph.
We can see from the figure that the AW-LS estimator has comparable mean squared error than the standard least squares estimator. The W-decorrelated estimator has much greater MSE than other estimators, which is not surprising because the W-decorrelated estimator decreases the bias of estimators by increasing the variance [Deshpande et al., 2018].

Mean squared error for different estimators of $\theta^*$ on data collected under Thompson Sampling.

In Figure <ref>, we plot the empirical coverage probabilities and volume of 90% confidence regions for $\theta^*$. For convenience, through the remainder of this section we refer to a confidence region constructed using the asymptotic distribution of an estimator as the ADCR (asymptotic distribution confidence region) of an estimator. The least squares estimator ADCRs have significant undercoverage, which does not improve as $T$ increases, while the AW-LS estimator ADCRs have very reliable coverage. The confidence regions constructed using the self-normalized martingale bound have reliable coverage, but are very conservative. Methods for constructing confidence regions which undercover can have much smaller confidence regions than those that provide at least the nominal coverage level. To allow for a fair comparison between methods for constructing confidence regions with varying levels of empirical coverage, when computing the volumes of the confidence regions for all our simulations, if a method for constructing confidence regions under-covers for any value of $T$, we set the cutoff values for the statistic to that which empirically guarantees $90\%$ coverage. The AW-LS estimator ADCRs have similar volume to the least squares estimator ADCRs and significantly smaller volume than the self-normalized martingale bound confidence regions and W-decorrelated estimator ADCRs. Empirically, we found that the coverage probability of the W-decorrelated estimator ADCRs were very sensitive to the choice of tuning parameters; we follow a similar method for choosing these parameters as Deshpande et al., 2018 as discussed in Appendix <ref>.

In Figure <ref>, we plot the empirical coverage probabilities and volume of $90\%$ confidence regions for the advantage parameters, $\theta_1^*$. Due to the need for using projected confidence regions, the AW-LS estimator ADCRs are significantly more conservative than the unweighted least squares estimator ADCRs in this setting. The volume of the AW-LS estimator ADCRs is still close to that of the unweighted least squares estimator ADCRs, and significantly outperforms both the W-decorrelated estimator ADCRs and the self-normalized martingale bound confidence regions.

Parameters $\theta^*$:  Empirical coverage probabilities for 90% confidence ellipsoids for parameters $\theta^*$ (left) and volume of 90% confidence ellipsoids for $\theta^*$ (right).

Advantage Parameters $\theta_1^*$: Empirical coverage probabilities for 90% confidence ellipsoids for advantage parameters $\theta_1^*$ (left) and volume of 90% confidence ellipsoids for $\theta_1^*$ (right).

Next we show simulation results for an adaptively weighted maximum likelihood estimator (AW-MLE) for a logistic regression model in a contextual bandit problem with binary rewards. We assume the following model for expected rewards:

\begin{equation*}
E_{\theta}[ R_t | X_t, A_t ] = \left[ 1 + \exp \left( - \tilde{X}_t^\top \theta_0 - A_t \tilde{X}_t^\top \theta_1 \right) \right]^{-1}.
\end{equation*}

Our simulation set-up is analogous to that for the AW-LS estimator, but for binary rewards. We collect data using Thompson Sampling with a linear model for the expected reward and Normal priors with constrained action selection probabilities via clipping a rate of $0.01$. In our simulations, $X_t$ is two dimensional, which makes $\theta^*$ six dimensional and the parameters of the advantage function, $\theta_1^*$, three dimensional. We set $\theta^* = [\theta_0^*, \theta_1^*] = [0.1,0.1,0.1,0,0,0]$. We use a uniform evaluation policy. See more details in Appendix <ref>.

Bernoulli Rewards, parameters $\theta^*$: Empirical coverage probabilities for 90% confidence ellipsoids for parameters $\theta^*$ (left) and volume of 90% confidence ellipsoids for $\theta^*$ (right).

Bernoulli Rewards, advantage parameters $\theta_1^*$: Empirical coverage probabilities for 90% confidence ellipsoids for advantage parameters $\theta_1^*$ (left) and volume of 90% confidence ellipsoids for $\theta_1^*$ (right).

In Figure <ref>, we plot the empirical coverage probabilities and volume of 90% confidence regions for $\theta^*$ for Bernoulli rewards. Note that the W-decorrelated estimator and Self-Normalized Martingale bounds were developed for settings in which the expected reward is a linear function of the context and are thus not applicable in this setting. The unweighted MLE ADCRs have significant undercoverage, which does not improve as $T$ increases, while the AW-MLE ADCRs have very reliable coverage. The ADCRs for both the unweighted and weighted MLEs have similar volumes. In Figures <ref>, we plot the empirical coverage probabilities and volume of $90\%$ confidence intervals for the advantage parameters, $\theta_1^*$, for Bernoulli rewards. Due to the projected confidence region, the AW-MLE ADCRs are significantly more conservative than the unweighted MLE ADCRs in this setting. However, the AW-MLE ADCRs have much more reliable coverage than the unweighted MLE ADCRs. We also show simulation results for the AW-MLE for a generalized linear model with Poisson distributed rewards in Appendix <ref>. Overall, the results for the AW-MLE ADCRs for Bernoulli and Poisson distributed rewards are very similar.

§ DISCUSSION

There are many open research areas regarding statistical inference on data collected with bandit and other adaptive algorithms. We discuss two main areas of open research: (i) more general and robust statistical inference methods and (ii) developing methods to help guarantee power on adaptively collected data.

§.§ Developing More General and Robust Statistical Inference Methods on Bandit Data

Weakening model assumptions
In this work we make the conditional optimality assumption that $\theta^* \in \argmax_{\theta \in \Theta} E_{\theta^*} \left[ m_{\theta} ( Y_t, X_t, A_t ) | X_t, A_t \right] ~ \TN{ w.p. } 1.$  Our theorems heavily rely on the conditional optimality assumption to ensure that $\{ W_t \dot{m}_{\theta} ( Y_t, X_t, A_t ) \}_{t \geq 1}$ is a martingale difference sequence with respect to $\{ \HH_{t} \}_{t \geq 0}$. On i.i.d. data it is common to define $\theta^*$ to be the best projected solution, i.e., $\theta^* \in \argmax_{\theta \in \Theta} E_{\theta^*} \left[ m_{\theta} ( Y_t, X_t, A_t ) \right]$. Note that the best projected solution, $\theta^*$, depends on the distribution of $(Y_t, X_t, A_t)$. It would be ideal to also be able to perform inference for a projected solution on adaptively collected data as well.

Statistical inference methods for adaptively collected data in more complex environments

One natural question is whether variance stabilizing methods work in more complicated environments, like for Markov Decision Processes (MDPs).
It is not straightforward to apply the adaptive weighting method without knowing state transition probabilities. For example, consider the least squares estimator we discuss in Section <ref>. Recall that to apply the uniform martingale central limit theorem, we needed to ensure that the conditional variance condition  (as discussed in section <ref>) holds,
i.e., $\frac{1}{T} \sum_{t=1}^T E_{\theta^*} \left[ W_t^2 \phi(X_t, A_t)^{\otimes 2} \left( Y_t - \phi(X_t, A_t)^\top \theta^* \right)^2 \big| \HH_{t-1} \right] \Pto \Sigma_{\theta^*} \TN{ uniformly over } \theta^* \in \Theta$. In equation (<ref>) we show for that weights $W_t = \sqrt{ \frac{\pi_{A_t}^{\TN{eval}}}{ \pi_{t,a} } }$ this condition holds when $\{ X_t \}_{t \geq 1}$ are i.i.d.; however, these weights are not generally sufficient in the MDP setting in which the distribution of $X_t$ can depend on $(X_{t-1}, A_{t-1})$. However, suppose we knew transition probabilities $P(X_t | X_{t-1}, A_{t-1})$ and set weights $W_t = \sqrt{ \frac{ \pi_{A_t}^{\TN{eval}} P_{\TN{eval}}(X_t) }{ \pi_{t,a} P(X_t | X_{t-1}, A_{t-1}) } }$, where $P_{\TN{eval}}(X_t)$ is some distribution over $X_t$. Then the conditional variance would be

\begin{equation*}
\frac{1}{T} \sum_{t=1}^T E_{\theta^*} \left[ W_t^2 \phi(X_t, A_t)^{\otimes 2} \left( Y_t - \phi(X_t, A_t)^\top \theta^* \right)^2 \bigg| \HH_{t-1} \right]
\end{equation*}

\begin{equation*}
= \frac{1}{T} \sum_{t=1}^T E_{\theta^*} \left[ E_{\theta^*} \left[ \frac{ \pi_{A_t}^{\TN{eval}} P_{\TN{eval}}(X_t) }{ \pi_{t,A_t} P(X_t | X_{t-1}, A_{t-1}) } \phi(X_t, A_t)^{\otimes 2} \left( Y_t - \phi(X_t, A_t)^\top \theta^* \right)^2 \bigg| \HH_{t-1}, X_t \right] \bigg| \HH_{t-1} \right] \\
\end{equation*}

\begin{equation*}
= \frac{1}{T} \sum_{t=1}^T E_{\theta^*} \left[ \frac{ P_{\TN{eval}}(X_t) }{ P(X_t | X_{t-1}, A_{t-1}) } E_{\theta^*, \pi^{\TN{eval}}} \left[ \phi(X_t, A_t)^{\otimes 2} \left( Y_t - \phi(X_t, A_t)^\top \theta^* \right)^2 \bigg| \HH_{t-1}, X_t \right] \bigg| \HH_{t-1} \right]
\end{equation*}

\begin{equation*}
= E_{\theta^*, \TN{eval}} \left[ E_{\theta^*, \pi^{\TN{eval}}} \left[ \phi(X_t, A_t)^{\otimes 2} \left( Y_t - \phi(X_t, A_t)^\top \theta^* \right)^2 \bigg| X_t \right] \right].
\end{equation*}

The outer expectation in the last term above is over $X_t$ which follows the distribution $P_{\TN{eval}}$. Since the above is a constant, this satisfies the conditional variance condition. However, in general we do not expect to know the transition probabilities $P(X_t | X_{t-1}, A_{t-1})$ and if we tried to estimate them, our theory would require the estimator to have error $o_p( 1 / \sqrt{T})$, below the parametric rate.
[Specifically, if we estimate $P(X_t | X_{t-1}, A_{t-1})$ and use estimated weights $\hat{W}_t$, for $\{ \hat{W}_t \dot{m} (Y_t, X_t, A_t) \}_{t \geq 1}$ to be an approximate martingale difference sequence to apply the martingale CLT, we require that $\frac{1}{ \sqrt{T} } \sum_{t=1}^T \hat{W}_t \dot{m} (Y_t, X_t, A_t) \Pto 0$, which given our assumptions requires $\hat{W}_t - W_t = o_p( 1 / \sqrt{T} )$.]

§.§ Developing Methods to Guarantee Power on Adaptively Collected Data

As discussed in the literature, in sequential decision making problems there is a fundamental trade-off between minimizing regret and minimizing estimation error for parameters of the environment (e.g., the difference in expected reward for two arms of a multi-armed bandit) using the resulting data collected [Bubeck et al., 2009, Dean et al., 2018, Erraqabi et al., 2017]. Given this trade-off there are many open questions regarding how to guarantee power, i.e., the probability of correctly rejecting a null hypothesis and making a scientific discovery. For example, there is the need for algorithms that balance the objectives of regret minimization and power [Offer-Westort et al., 2019, Liu et al., 2014, Erraqabi et al., 2017, Yao et al., 2020] and a need for the development of sample size calculators that output the sample size needed to guarantee a certain amount of power under a particular alternative when using a particular bandit algorithm for data collection.

[Abbasi-Yadkori et al., 2011]
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.
Improved algorithms for linear stochastic bandits.
In Advances in Neural Information Processing Systems, pages
2312–2320, 2011.

[Agrawal and Goyal, 2013]
Shipra Agrawal and Navin Goyal.
Thompson sampling for contextual bandits with linear payoffs.
In International Conference on Machine Learning, pages
127–135, 2013.

[Agresti, 2015]
Alan Agresti.
Foundations of linear and generalized linear models.
John Wiley & Sons, 2015.

[Barnett et al., 2020]
Adrian Barnett, Hang Ding, Karen E Hay, Ian A Yang, Rayleen V Bowman, Kwun M
Fong, and Henry M Marshall.
The effectiveness of smartphone applications to aid smoking
cessation: A meta-analysis.
Clinical eHealth, 2020.

[Bell et al., 2020]
Lauren Bell, Claire Garnett, Tianchen Qian, Olga Perski, Henry WW Potts, and
Elizabeth Williamson.
Notifications to improve engagement with an alcohol reduction app:
protocol for a micro-randomized trial.
JMIR research protocols, 90 (8):0 e18690,

[Bubeck et al., 2009]
Sébastien Bubeck, Rémi Munos, and Gilles Stoltz.
Pure exploration in multi-armed bandits problems.
In International conference on Algorithmic learning theory,
pages 23–37. Springer, 2009.

[Bura et al., 2018]
Efstathia Bura, Sabrina Duarte, Liliana Forzani, Ezequiel Smucler, and Mariela
Asymptotic theory for maximum likelihood estimates in reduced-rank
multivariate generalized linear models.
Statistics, 520 (5):0 1005–1024, 2018.

[Caria et al., 2020]
Stefano Caria, Maximilian Kasy, Simon Quinn, Soha Shami, Alex Teytelboym,
et al.
An adaptive targeted field experiment: Job search assistance for
refugees in jordan.

[Dean et al., 2018]
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu.
Regret bounds for robust adaptive control of the linear quadratic
arXiv preprint arXiv:1805.09388, 2018.

[Deshpande et al., 2018]
Yash Deshpande, Lester Mackey, Vasilis Syrgkanis, and Matt Taddy.
Accurate inference for adaptive linear models.
In Jennifer Dy and Andreas Krause, editors, Proceedings of the
35th International Conference on Machine Learning, volume 80 of
Proceedings of Machine Learning Research, pages 1194–1203,
Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.

[Dvoretzky, 1972]
Aryeh Dvoretzky.
Asymptotic normality for sums of dependent random variables.
In Proceedings of the Sixth Berkeley Symposium on Mathematical
Statistics and Probability, Volume 2: Probability Theory. The Regents of the
University of California, 1972.

[Engle, 1994]
Robert F Engle.
Handbook of econometrics: volume 4.
Number 330.015195 E53 v. 4. 1994.

[Erraqabi et al., 2017]
Akram Erraqabi, Alessandro Lazaric, Michal Valko, Emma Brunskill, and Yun-En
Trading off rewards and errors in multi-armed bandits.
In Artificial Intelligence and Statistics, pages 709–717.
PMLR, 2017.

[Hadad et al., 2019]
Vitor Hadad, David A Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey.
Confidence intervals for policy evaluation in adaptive experiments.
arXiv preprint arXiv:1911.02768, 2019.

[Hammersley, 2013]
John Hammersley.
Monte carlo methods.
Springer Science & Business Media, 2013.

[Howard et al., 2018]
Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon.
Uniform, nonparametric, non-asymptotic confidence sequences.
arXiv preprint arXiv:1810.08240, 2018.

[Hu and Rosenberger, 2006]
Feifang Hu and William F Rosenberger.
The theory of response-adaptive randomization in clinical
trials, volume 525.
John Wiley & Sons, 2006.

[Hu et al., 2009]
Feifang Hu, Li-Xin Zhang, and Xuming He.
Efficient randomized-adaptive designs.
The Annals of Statistics, pages 2543–2560, 2009.

[Huber, 1992]
Peter J Huber.
Robust estimation of a location parameter.
In Breakthroughs in statistics, pages 492–518. Springer,

[Imbens and Rubin, 2015]
Guido W Imbens and Donald B Rubin.
Causal inference in statistics, social, and biomedical
Cambridge University Press, 2015.

[Jiang and Li, 2016]
Nan Jiang and Lihong Li.
Doubly robust off-policy value evaluation for reinforcement learning.
In International Conference on Machine Learning, pages
652–661. PMLR, 2016.

[Kasy, 2019]
Maximilian Kasy.
Uniformity and the delta method.
Journal of Econometric Methods, 80 (1), 2019.

[Kasy and Sautmann, 2019]
Maximilian Kasy and Anja Sautmann.
Adaptive treatment assignment in experiments for policy choice.

[Klasnja et al., 2020]
Predrag Klasnja, Dori E Rosenberg, Jing Zhou, Jane Anau, Anirban Gupta, and
David E Arterburn.
A quality-improvement optimization pilot of barifit, a mobile health
intervention to promote physical activity after bariatric surgery.
Translational Behavioral Medicine, 2020.

[Lai and Wei, 1982]
Tze Leung Lai and Ching Zong Wei.
Least squares estimates in stochastic regression models with
applications to identification and control of dynamic systems.
The Annals of Statistics, 100 (1):0 154–166,

[Leeb and Pötscher, 2005]
Hannes Leeb and Benedikt M Pötscher.
Model selection and inference: Facts and fiction.
Econometric Theory, pages 21–59, 2005.

[Lipschitz et al., 2019]
Jessica Lipschitz, Christopher J Miller, Timothy P Hogan, Katherine E Burdick,
Rachel Lippin-Foster, Steven R Simon, and James Burgess.
Adoption of mobile apps for depression and anxiety: cross-sectional
survey study on patient interest and barriers to engagement.
JMIR mental health, 60 (1):0 e11334, 2019.

[Liu et al., 2014]
Yun-En Liu, Travis Mandel, Emma Brunskill, and Zoran Popovic.
Trading off scientific knowledge and user learning with multi-armed
In EDM, pages 161–168, 2014.

[Neary and Schueller, 2018]
Martha Neary and Stephen M Schueller.
State of the field of mental health apps.
Cognitive and Behavioral Practice, 250 (4):0
531–537, 2018.

[Offer-Westort et al., 2019]
Molly Offer-Westort, Alexander Coppock, and Donald P Green.
Adaptive experimental design: Prospects and applications in political
Available at SSRN 3364402, 2019.

[Rafferty et al., 2019]
Anna Rafferty, Huiji Ying, and Joseph Williams.
Statistical consequences of using multi-armed bandits to conduct
adaptive educational experiments.
JEDM| Journal of Educational Data Mining, 110
(1):0 47–79, 2019.

[Romano et al., 2012]
Joseph P Romano, Azeem M Shaikh, et al.
On the uniform asymptotic validity of subsampling and the bootstrap.
The Annals of Statistics, 400 (6):0
2798–2822, 2012.

[Shaikh et al., 2019]
Hammad Shaikh, Arghavan Modiri, Joseph Jay Williams, and Anna N Rafferty.
Balancing student success and inferring personalized effects in
dynamic experiments.
In EDM, 2019.

[Song et al., 2019]
Ting Song, Siyu Qian, and Ping Yu.
Mobile health interventions for self-control of unhealthy alcohol
use: systematic review.
JMIR mHealth and uHealth, 70 (1):0 e10899,

[Thomas and Brunskill, 2016]
Philip Thomas and Emma Brunskill.
Data-efficient off-policy policy evaluation for reinforcement
In International Conference on Machine Learning, pages
2139–2148. PMLR, 2016.

[Van der Vaart, 2000]
Aad W Van der Vaart.
Asymptotic Statistics, volume 3.
Cambridge University Press, 2000.

[Villar et al., 2015]
Sofía S Villar, Jack Bowden, and James Wason.
Multi-armed bandit models for the optimal design of clinical trials:
benefits and challenges.
Statistical science: a review journal of the Institute of
Mathematical Statistics, 300 (2):0 199, 2015.

[Yao et al., 2020]
Jiayu Yao, Emma Brunskill, Weiwei Pan, Susan Murphy, and Finale Doshi-Velez.
Power-constrained bandits.
arXiv preprint arXiv:2004.06230, 2020.

[Zhang et al., 2020]
Kelly W Zhang, Lucas Janson, and Susan A Murphy.
Inference for batched bandits.
NeurIPS 2020, 2020.


# Novel Architecture to Create and Maintain Personal Blockchains

Collin Connors  Computer Science Department
University of Miami
Miami, FL
<EMAIL_ADDRESS>Dilip Sarkar  Computer Science Department
University of Miami
Miami, FL

###### Abstract

Blockchain has been touted as a revolutionary technology. However, despite the
excitement, blockchain has not been adopted in many fields. Many are hesitant
to adopt blockchain technology due to privacy concerns, barriers to use, or
lack of practical use cases. In this work, we outline a potential blockchain
use case for tracking financial transactions across multiple financial
institutions. We show the downsides of traditional centralized approaches and
that blockchain approaches fail to give all the privacy and accessibility
required for this use case. Thus we propose a novel blockchain architecture to
support our use case. This novel architecture combines the ease of use of
public blockchains with the privacy of private blockchains by allowing users
to create personal blockchains. We believe this novel personal blockchain
architecture will lead to more blockchain adoption, particularly in use cases
handling private data.

##  I Introduction

People trust financial institutions to maintain records properly with little
hesitation. These institutions are governed by various regulatory authorities
and must comply with data security laws and regulations [10]. However, these
financial systems are often independent of one another. Since a modern
consumer or business uses many financial institutions, tracking all of their
transactions can be challenging.

Individuals, for example, may have multiple credit cards issued by different
banks, investment accounts, or other financial instruments. A business may
have various incoming and outgoing invoices, utilize multiple banks, and even
use various global financial institutions. Transactions across multiple
financial institutions can be challenging to document. Thus false and
fraudulent transactions are often missed even by the most vigilant consumers.

An individual may mistakenly sign up for a subscription service and not notice
charges for months. Alternatively, a business may pay fake invoices to
malicious actors without realizing it. To spot these transactions, users must
aggregate all of their transactions into a single ledger. Centralized
applications such as Mint by Intui [5] help consumers generate this ledger.
However, these applications can lead to unnecessary data privacy risks.
Another proposed solution is to use blockchain technology similar to its use
in cryptocurrency.

Cryptocurrency utilizes advanced technology for recording transactions of
account holders [9]. Cryptocurrencies such as Bitcoin [7] rely on digital
ledgers known as a blockchain. A blockchain is a distributed, tamper-evident,
tamper-resistant digital ledger [13]. In its most basic form, a blockchain
allows users to write data in an append-only manner without needing a
centralized entity.

As cryptocurrency has evolved, so has the way users interact with blockchains.
While blockchain was initially designed to store cryptocurrency transaction
records, modern blockchains allow storing varied and complex data. Developers
can use platforms such as Ethereum [2] to create dynamic distributed
applications. Since security and accuracy are critical for financial
applications, many developers utilize the blockchain to create decentralized
FinTech applications [3].

In this work, we propose a blockchain-based application that stores users’
financial transaction history across multiple financial institutions on a
blockchain. We show why centralized applications add unnecessary data privacy
risks, and thus a blockchain-based solution is required. We then describe the
issues if users store their financial transaction history on blockchains such
as Ethereum. Thus, we propose a novel blockchain architecture for creating
personal blockchains to overcome the issues posed by traditional blockchain
applications. This work aims to highlight a need for the proposed novel
architecture, and in future work, we plan to give a more detailed technical
description of the architecture.

We have organized the rest of this paper as follows. In section II, we provide
a primer on blockchain technology and its uses. In section III, we provide a
summary of our proposed application. In section IV, we expand on our summary
providing details on how our novel blockchain architecture can be used to
create the proposed application. Finally, we provide some concluding remarks
and plans for future work in section V.

##  II Background

Blockchains are _append-only_ , _tamper-evident_ , _tamper-resistant_ ,
_distributed fault-tolerant_ digital ledgers [13]. As the name suggests, a
blockchain is a linked chain of blocks. A block consists of the block header
and the block data.

The block header contains the cryptographic hash of the previous block. Thus,
any change to the previous block’s header will indicate that it was tampered
with. Likewise, the hash of the block data section is also included in the
block header. Thus, if any change is made to the data, the hash value in the
block header will not match the hash of the data. Therefore tampering with
data in a block can be identified easily.

The block data contains a list of transactions. While initially, in Bitcoin,
transactions were actual cryptocurrency transactions, modern blockchains allow
a transaction to be any arbitrary data. For example, if a doctor’s office was
using a blockchain to track appointments, the transactions might be
appointment dates and who made the appointment.

A blockchain is a chronological ledger. The transactions are timestamped and
ordered. Notice that transactions cannot be reordered after creating a block,
as this would change the hash of the block data. Thus everything in the
blockchain is chronological and cannot be changed.

The first block of a blockchain is called the genesis block. This is the only
block in the blockchain that’s block header does not contain the cryptographic
hash of the previous block. Because it has no previous block, it is critical
to ensure that the creation of the genesis block is legitimate. For example,
in a blockchain for cryptocurrency, one must ensure the creator of the
cryptocurrency did not give themselves tokens in the genesis block.

Next, let us briefly review the concepts introduced in 1991 that laid
foundation for _append-only_ _tamper-evident_ electronic ledger [8]. To append
a new document to an existing ledger, a digital digest of the previous
document is added to the document. Then a digest of the document is digitally
signed. Any change to the most recently appended document will change the
digest of the document of the next documents, and tampering will be evident.
Since a digital digest of the previous document has been included in the most
recent document, any change to the previous document will not match with the
digest on the most recent document, and tampering will be evident. This
tamper-evident relationship between two consecutive documents is true for all
documents in the ledger.

Append-only tamper-evident and tamper-resistant electronic ledgers utilize
cryptographic hash functions [11] and public-key cryptography [4] to create
digital digest and digitally signing the documents, respectively. Blockchains
also utilize cryptographic hash functions and public-key cryptography for many
purposes. For example, it is used for creating user identification numbers and
signing transactions.

Blockchains are decentralized. There is no central authority keeping track of
the ”real” blockchain; instead, many nodes worldwide agree on what
transactions are in the blockchain. This method of agreeing is known as the
Sybil Control mechanism [6], sometimes referred to as the consensus protocol
or consensus algorithm. There are many different Sybil Control mechanisms used
by blockchains, such as Proof of Work, Bitcoin, and Proof of Stake, used by
Ethereum.

Blockchain networks are categorized based on their permission model [9].
Permissionless blockchains allow anyone to join the Sybil control mechanism
and attempt to create new blocks. For example, Bitcoin is a permissionless
blockchain network since anyone can try to mine blocks. In contrast,
permissioned networks, such as those created by Hyperledger Fabric [1],
require permission from an authority to participate in the Sybil control.
Similarly, a blockchain ledger is categorized as public or private based on
its viewing option. A _public blockchain_ ledger is available to everyone for
viewing. Most permissionless blockchains are public ledgers because their
contents are available to everyone for viewing. A _private blockchain_ ledger
requires permission for viewing it.

###  II-A Limitation of Current Blockchain Ledgers

While blockchain technology can enhance many applications, the current
blockchain architectures have limitations. Blockchain networks must choose
between decentralization, scalability, and privacy [12]. Thus no blockchain
network is optimal in all three categories. Many blockchains chose to optimize
decentralization at the cost of scalability and privacy.

Likewise, permissionless blockchains have a cost when executing transactions.
One such cost is the transaction fee users need to pay to use the network.
While some blockchains have attempted to ensure low transaction fees, many
users are still turned off. Likewise, users may need to wait for transactions
to be approved. Some blockchains have attempted to speed up transaction times,
but typically, these solutions are not scalable.

Users who wish to avoid the drawbacks of permissionless blockchains may
consider permissioned blockchains. However, these blockchains require
technical expertise from the users to set up and maintain. Likewise, users
need their own hardware to operate these blockchains, making them inaccessible
to the average consumer.

We believe blockchain technology must be integrated with legacy technology,
such as database technology. Moreover, a _blockchain system_ ought to be a
collection of _independent services_. Different independent operators should
provide these services. Thus, future users can deploy the blockchain system by
choosing each service from a set of available service providers.

##  III Proposed Application

Financial systems have become more accessible and specialized. This
specialization has led consumers to utilize multiple different financial
intuitions. The complex web of various financial institutions has made it
difficult for consumers to keep track of all their financial transactions. For
example, an individual may have multiple banks, credit cards, and investments.
Figure 1 shows how a customer interacts with existing financial institutions.
The customer is receiving data from many different financial institutions. The
consumer is responsible for collecting all of these sources of financial data,
which can be time-consuming, tedious, and prone to mistakes.

Figure 1: A high-level view of the traditional financial institutions. In this
model, customers are responsible for collecting and maintaining all of their
financial transactions.

To aid consumers, we propose an application that would aggregate all of their
financial transactions across multiple financial institutions. Our proposed
application relies on existing APIs provided by financial institutions to
collect transaction data. Likewise, the application stores financial
transactions in a blockchain. The blockchain gives users financial records
immutability and chronological order, two highly desired properties when
tracking financial records. Figure 2 gives a high-level overview of such an
application. In this model, all financial transactions are sent to the
blockchain.

Figure 2: A high-level overview of the proposed blockchain-augmented financial
application. This model stores a customer’s financial transactions on a
blockchain. We assume that the financial institutions already have an existing
API layer to send transaction data.

Some centralized applications, such as Mint by Intuit [5], have already
attempted to solve this problem. These applications aggregate a user’s
financial transitions to the application. While this does make tracing complex
financial transactions easier for consumers, these applications provide
convince to the customer at the cost of privacy. Users must hand over their
finical records to a centralized third party. This third party may use the
financial transaction data for advertising or other purposes. Even if the
third party does not utilize the data, if a hacker were to breach the third
party, the customer’s sensitive financial data could get leaked. Using a
centralized application requires consumers to take on risk, which is
undesirable in financial applications.

Likewise, a similar application that allows users to store data on their own
devices or cloud infrastructure does not provide all the desirable features.
Critically past financial history should never change. Thus any storage should
be immutable. Likewise, financial transaction history must be ordered. For
example, consumers need to know if they have funds in their accounts before
they make a purchase. Thus the consumer must ensure that they have funds
deposited before they make a purchase. In addition, no party should have
access to a consumer’s financial records other than the consumer and the
financial institutions. Considering these factors, blockchain presents itself
as an ideal solution. However, current blockchain implementations are
suboptimal for this proposed application.

If our proposed application were to use a permissionless blockchain such as
Ethereum, users would have to publish their financial transactions to the
blockchain. Since anyone can read a public blockchain, this could expose
sensitive financial transactions. Even if the user were to take privacy
measures such as encrypting the transactions, they would still risk leaking
sensitive information. User error, mismanaged keys, or new technologies can
reveal encrypted data. Lastly, users must pay a fee for every transaction in a
permissionless blockchain. Even on blockchains with low fees, the cost can
dissuade individuals and businesses alike from using our proposed application.

In contrast, if our proposed application were to use an existing permissioned
blockchain, such as Hyperledger Fabric, the user would be required to create
and maintain their own blockchain infrastructure. Creating and maintaining
infrastructure can be costly and complex. Likewise, users are responsible for
managing permissions to the blockchain. If a user were to make a mistake with
the permission set, they could grant access to parties who should not have
access. A permissioned blockchain requires technical skill and computing power
and is prone to mistakes making it a suboptimal solution for an application
aimed at average consumers.

Thus we propose a novel blockchain architecture to create personal blockchains
to support our proposed application. The following section describes the
blockchain architecture and summarizes the modules necessary to support our
application. This work aims to show the need for our novel blockchain
architecture. We do not go into technical detail on our system but only show
how such an architecture is ideal for our proposed application.

##  IV Novel Architecture to Support the Application

Since there is no existing blockchain development platform [3] that supports
our use case, we propose a novel blockchain architecture for creating
individual blockchains. Our proposed architecture is unlike other blockchain
architectures in that each user has their own blockchain rather than one
single chain for all the users. Our proposed architecture aims to add more
security and privacy to blockchain applications while being accessible to all
users.

Our novel architecture relies on modular, decentralized services to support
the creation and maintenance of personal blockchains. In this work, we assume
that these modules exist and are widespread. In future work, we will outline
the technical specifications behind the modules and provide an implementation.
For this work, it should be understood that each module is independent. Thus
users could utilize multiple service providers and even change service
providers during the application’s lifecycle.

While we describe our modules in the context of a financial application our
architecture is general and can apply to many use cases. Similar to how web
services such as hotmail first made email allowed the average person to create
a personal email account, our proposed architecture can be used to bring
personal blockchains to the average consumer. A single user may have multiple
personal blockchains such as a blockchain for financial and a blockchain for
health records. Our architecture is designed to make blockchain technology
accessible to everyone regardless of technical knowledge.

Figure 3 shows how our proposed architecture allows users to create personal
financial blockchains. Through their APIs or other means, the financial
institution will send data to the customer. Notice from the point of view of
the financial institutions, nothing has changed, making this system easy to
adopt. The customer forwards the data to the blockchain services. The
blockchain services are made up of four independent modules:

  1. 1.

The Blockchain Management Service - Responsible for allowing access to the
blockchain

  2. 2.

The User Account Service - Responsible for managing permissions on the
blockchain

  3. 3.

The Block Creation Services - Responsible for adding new blocks to the
blockchain

  4. 4.

The Reporting Service - Responsible for adding an application and presentation
layer to the blockchain

We will briefly cover how the various components interact with our proposed
application. We will give detailed technical specifications for each proposed
module in future work.

Figure 3: A block diagram of our novel architecture applied to our proposed
application. In this model, the financial institutions send transactions, via
an API layer, to the customer. The costumer then forwards those transactions
to the various blockchain services. Note that each customer has their own
individual blockchain.

All our modules can be run decentralized, ensuring that no centralized entity
can access users’ data. The users can choose the extent of decentralization;
some users may be comfortable using only centralized services, while others
might prefer a fully decentralized approach. Likewise, users can choose how
the blockchain is stored. Some may wish to store their blockchain on local
storage or in the cloud. Others may prefer to use services such as IPFS to
maintain decentralized storage. Lastly, users can decide the scope of
transactions they wish to store. Some users may wish to store every
transaction and all of its details. Other users may only store a summary of
transactions. Since each user has their own personal blockchain, our
architecture is highly flexible and can accommodate various users’ concerns.

###  IV-A Blockchain Management Service

The Blockchain Management Service (BCMS) is responsible for allowing
interactions between a user and their blockchain. This service provides an API
for users to read and write data from a blockchain. The BCMS acts as an
interface allowing our customers to read the blockchain’s data and allow the
various financial institutions to submit transactions to the blockchain.

Likewise, the BCMS also provides access to blockchain storage. Customers can
choose how they want their blockchain to get stored. Some customers may desire
the blockchain to be stored on a device they control, such as a physical
drive. Others may want to utilize centralized cloud storage options like
Google Drive. Similarly, some users may wish to utilize decentralized storage
such as IPFS. It is the job of the BCMS to ensure that regardless of the
storage option, the user has access to their blockchain.

Customers concerned about privacy could store the blockchain on a server they
control, ensuring they are the only entity with a copy of their data. For
example, a business cannot risk leaking sensitive financial transactions. Thus
they could have the BCMS store the blockchain on an internal secured server
allowing the business to maintain control of its data.

This service is independent of the blockchain storage method. Thus users can
change BCMS service providers without losing access to their blockchain.
Additionally, since the BCMS does not store the blockchain itself, if a BCMS
service provider were to be breached, users would leak far less data than in
traditional centralized applications.

###  IV-B User Account Service

The User Account Service (UAS) works with the BCMS to maintain customer and
financial institutions’ identities and permissions. The UAS acts like a
certificate authority in web 2.0 or an identity management system in
permissioned blockchains. The UAS issues certificates to customers and
financial institutions containing their public keys, permissions, and other
auxiliary information, such as the financial institution’s API access tokens.

Likewise, the UAS creates special blocks on the blockchain defining the
permissions of users and financial institutions. For example, when customers
start using our proposed application, they will need to tell the application
which financial institutions they currently use and obtain API keys. The UAS
is responsible for creating certificates for the financial institutions and
writing to the blockchains to which institutions the customer has access.
Storing the permissions on the blockchain allows other services to verify that
the correct financial institutions are being queried.

Similarly, throughout the life cycle of the proposed application, a customer
may change financial institutions or join new financial institutions. It is
the responsibility of the UAS to ensure that the proper permissions are
maintained and reflect the institutions the customer currently utilizes.

###  IV-C Block Creation Services

The Block Creation Services (BCS) are responsible for creating new data blocks
and appending them to the user’s blockchain. The BCS only has write access to
the customer’s blockchain, ensuring the customer’s privacy.

The BCS maintains a pending transaction queue for each customer. When the BCMS
submits a new transaction to the BCS, it validates the transaction by
authenticating the institution’s and customer’s digital signatures on the
transaction. Then it inserts the current time stamp, digitally signs the
transaction, and inserts it into the customer’s pending transaction queue.

Once a transaction queue accumulates sufficient transactions, the BCS creates
a new block and publishes it by sending it to the Blockchain Management
Service for storing the block. Two things are important to note: The number of
transactions could be determined by the maximum size (say in MB) of a block or
the end of a period, month, or quarter. Unlike mining nodes in a Bitcoin-like
blockchain, the BCS does not store blockchains. The BCS only creates new
blocks and is not responsible for storing and managing blockchain data.

###  IV-D Reporting Service

The reporting service adds interconnection for the application and
presentation layers to the user’s blockchain. In contrast to the Block
Creation Services, this service has read-only permissions. The read-only
property prevents the reporting service from adding data when presenting data.

For all applications, the reporting service is responsible for checking the
integrity of the blockchain. This service checks the hash of each block as
well as the hashes stored in each block’s header to ensure that the blockchain
has not been tampered with. The reporting service reports to the user if any
tampering has been detected.

Likewise, this service is responsible for adding application features to our
blockchain. In our proposed application, users will need to query their
blockchain for specific data, such as all transactions made on a specific
date. The reporting service runs these advanced queries and returns this
information to the user. Similarly, this module allows for interaction between
a frontend layer and the blockchain. The reporting service acts as an API that
can query information from the blockchain and return it to a frontend.

Notice that the reporting service’s functionality is different for each
application. For example, a healthcare application will require a different
reporting service than a financial application. It is up to developers to
create reporting service nodes for their desired applications. Likewise, the
reporting service may be used to share blockchain data. For example, in a
health care application a doctor may need to see a copy of health records
stored on a users personal blockchain.

In this section, we only briefly describe the various components necessary for
a novel architecture that supports our proposed application. This architecture
is unlike other blockchain architecture as it allows for creating personal
blockchains. The use of personal blockchains combines the ease of use and
accessibility of permissionless blockchains with the privacy and control of
data provided by permissioned blockchains. We plan to provide detailed
technical specifications for our proposed novel architecture in future work.

##  V Conclusion and Future Work

In this work, we described an application for tracking all of a customer’s
transactions across multiple financial institutions using blockchain. We
discussed how traditional centralized approaches lead to a loss in data
privacy. Likewise, we discussed why current blockchain development platforms
would make such an application suboptimal. Thus we described a novel
blockchain architecture to create personal blockchains.

Our proposed architecture relies on four independent modules to create,
maintain, and process the blockchain. Our proposed architecture blends the
ease of use of public blockchains with the privacy-preserving features of
private blockchains. Unlike traditional blockchains, where all users share one
blockchain, our system allows each user to create their own personal
blockchain. This novel architecture increases data privacy and security,
allowing developers to create blockchain-based applications for fields that
require high privacy.

This work aimed to highlight a use case where traditional blockchain
development platforms struggle to ensure privacy and accessibility. In future
work, we plan to give an in-depth technical description of our proposed
architecture. Likewise, we plan to implement our proposed architecture and our
proposed application.

## References

  * [1] Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin, Konstantinos Christidis, Angelo De Caro, David Enyeart, Christopher Ferris, Gennady Laventman, and Yacov et al. Manevich.  Hyperledger fabric.  Proceedings of the Thirteenth EuroSys Conference, 2018.
  * [2] Vitalik Buterin.  Ethereum whitepaper.
  * [3] Collin Connors and Dilip Sarkar.  Comparative study of blockchain development platforms: Features and applications.  10 2022.
  * [4] A. Das and C.E.V. Madhavan.  Public-key Cryptography: Theory and Practice.  Pearson Education, 2009.
  * [5] Intuit.  Mint.
  * [6] Mubashar Iqbal and Raimundas Matulevičius.  Exploring sybil and double-spending risks in blockchain systems.  IEEE Access, 9:76153–76177, 2021.
  * [7] Satoshi Nakamoto.  Bitcoin: A peer-to-peer electronic cash system.  SSRN Electronic Journal, 2008.
  * [8] Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, and Steven Goldfeder.  Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction.  Princeton University Press, 1 edition, 2016.
  * [9] Michael Nofer, Peter Gomber, Oliver Hinz, and Dirk Schiereck.  Blockchain.  Business Information Systems Engineering, 59(3):183–187, 2017\.
  * [10] Jan Putnis, editor.  The Banking Regulation Review.  Gideon Roberton, 4 edition, 2013.
  * [11] Rajeev Sobti and G. Geetha.  Cryptographic hash functions: A review.  International Journal of Computer Science, 9, 2012.
  * [12] Nick Szabo.  Formalizing and securing relationships on public networks.  First Monday, 2(9), 1997.
  * [13] Dylan Yaga, Peter Mell, Nik Roby, and Karen Scarfone.  Blockchain technology overview.  2018\.