Dynamic Selection in Algorithmic Decision-making

Dynamic Selection in Algorithmic Decision-making

Introduction

This paper studies the dynamic selection problem in algorithmic decision-making. The use of algorithms has become increasingly popular among business firms. The algorithms analyze data continuously and allow firms to adjust their decisions in response to new information constantly. This feature, known as online learning, implies that algorithms are both consumers and producers of data. They take data as inputs and analyze them to make decisions. They also produce data by choosing which product---movies, songs, or articles---to recommend.

Because an online algorithm uses prior data analysis to generate data, the data it generates are not random. As a result, the data the algorithm uses for its analysis is also non-random. The non-randomness of the data naturally leads to a data selection problem. Importantly, this selection problem is dynamic due to the online-learning nature of algorithms: past selection problems affect the data the algorithm generates, creating new data selection problems.

To demonstrate and address this dynamic selection problem, we focus on a class of algorithms known as contextual multi-armed bandits (MAB). Contextual bandit algorithms are commonly used across various domains due to their ability to balance exploration and exploitation while incorporating contextual information; see, for example, applications in product recommendation LiChuLangfordSchapire10, online advertising TangRosalesSinghAgarwal13, and mobile healthcare TewariMurphy17. News outlets such as the New York Times utilize contextual bandit algorithms to learn about their readers' behavior and recommend articles tailored to their interests more effectively Coenen19.

To illustrate how a contextual bandit algorithm works, consider a website that recommends news articles to its users. The website aims to maximize user engagement, measured by the number of articles read or the time users spend reading articles. The website can base its recommendation on the information it has on the users, known as the contextual information, which may include features like user demographics (age, gender, location) and user behavior (browsing history, time of the visit).

When a user visits the website, the contextual bandit algorithm gathers information about the user. Using this context and its current knowledge, it selects a news article to recommend, also known as which arm to pull, by using a model (such as linear regression) to predict user engagement. After the recommendation, the algorithm observes a reward, such as whether the user read the article or the time spent reading. The algorithm then updates its knowledge based on the context, chosen arm, and reward to improve its future recommendations.

A potential issue with the contextual bandit algorithm is that its knowledge-updating process may be impacted by an endogeneity problem. For instance, the news website might estimate the effectiveness of recommending sports articles by regressing their click rates on the reader's age. Click rates depend on both the reader's age and their free time available. But the website only observes the reader's age and not the free time. If the reader's free time is correlated with his age, an omitted-variable problem arises, leading to a biased estimate of the effectiveness of sports articles.

The omitted-variable problem causes a dynamic selection problem when the size of the omitted-variable bias varies among subsamples of data. In this case, the estimated effectiveness of sports articles depends on which subsamples are used for the regression. Because the algorithm recommends the article based on its estimated effectiveness, this implies that different past subsamples can lead to different recommendation rules. The past subsample therefore affects the new data generated, creating the dynamic selection problem.

Because of the dynamic selection problem, the decision rule (i.e., policy) in the long run under the contextual bandit algorithm is a fixed point: the optimal policy derived from analyzing the subsample must coincide with the long-run policy that generates the subsample. For example, suppose that the algorithm recommends the article to readers aged 60 and above. In this case, the regression analysis performed on the subsample of readers aged 60 and above must indicate that the optimal policy involves recommending the article to readers aged 60 and above.

The fixed-point property of the long-run policy leads to two problems. First, the oracle policy---that is, the true optimal policy had the effectiveness of each arm been known in advance---may not be a fixed point. This implies that the long-run policy is suboptimal. Second, and, relatedly, because the past policys affect the choice of future policys, the long-run policy may not be unique, implying that there are multiple fixed points.

Our first result shows that the non-uniqueness problem can be severe. Depending on the distribution of the omitted variable, there can be an arbitrarily large number of fixed points. Furthermore, these fixed points can be arbitrarily away from the optimal policy induced by the true parameter of interest. We refer to the difference between true parameter and its long-run estimate as the self-fulfilling bias. Our first result states that the self-fulling bias can be arbitrarily large and can take arbitrarily many values.

We then propose algorithms that correct for the self-fulfilling bias and generate actions with low levels of regret (loss in payoff compared to optimal actions). Our method integrates the instrumental variable (IV) approach into a greedy-type online learning algorithm designed for contextual bandit problems. Our proposed algorithms consist of three phases. In Phase 1, arms are randomly selected. At the end of Phase 1, the two-stage least squares (2SLS) method is implemented on the data associated with each arm to compute the arm-specific coefficient estimates. In Phase 2, the arm with the highest expected reward (using the coefficient estimates in Phase 1) is selected in each period. The covariance matrix of the estimates are calculated at the end of Phase 2. In Phase 3, arms are selected in a greedy fashion and the coefficients and covariance matrices are updated using “joint-2SLS” in each period. Under this algorithm, the coefficients converge to the true value in the long run. The regret of our algorithm is of order $\mathcal{O}(\log(T))$. In particular, the two special features of the algorithm---the existence of Phase 2 and joint-2SLS in Phase 3---are critical. Without either of the two, the coefficient estimates can fail to converge to the true value.

Our third contribution is to develop a technique that facilitates the theoretical analysis of online learning algorithms with dynamic selection problems. As mentioned above, a key feature of online learning algorithms is that data and actions are intertwined. This complicates the analysis because the effects of past actions can be long-lasting. Mathematically, in our proposed algorithm and in online learning algorithms in general, this complication manifests in a two-way dependence between (i) the estimates of the coefficients and (ii) the estimates of the covariance matrix between the IVs and an augmented vector of the covariates. On the one hand, in 2SLS, the coefficient estimates depend on the covariance estimates. On the other hand, each covariance estimate depends on all the past coefficient estimates because they affect the past actions and the past realization of data. This latter dependence is new and central to the analysis of online learning algorithms with dynamic selection problems. Moreover, the dependence is complicated both because the coefficient estimates are serially correlated and because they affect the estimates of the covariance matrix in a nonlinear manner.

Our technique deals with this two-way dependence by performing an induction in a zig-zag matter. In each induction step, we first derive the properties of the covariance estimates (zig), and then use this property to establish the induction hypothesis on coefficient estimates (zag). The heart of the induction is the zig-part, which employs a special technique to eliminate the dependence of the covariate estimates on all past coefficient estimates. The theoretical analysis of this dependence also indicates that, for the coefficient estimates to converge to the true value, the covariance estimates at the beginning of Phase 3 must be sufficiently close to the covariance matrix induced by the oracle policy. This motivates Phase 2 in our algorithm, which stabilizes the covariance estimates.

Finally, this technique establishes the rate of convergence of the estimates. These rates are used to analyze the regret of the algorithm. They are also used to establish the asymptotic distribution of the parameter estimators at the terminal period of the algorithm and, therefore, allow for the construction of confidence intervals and hypothesis testing.

Our paper contributes to the literature on dynamic learning. Within this literature, a key emphasis has been the trade-off between exploration and exploitation March91. The workhorse for analyzing this trade-off is the multi-armed bandit models. Economists have extensively studied their theoretical and empirical implications (see BergemannValimaki08 for a review). Recently, there is a growing sub-literature that studies algorithmic decision-making based on multi-armed bandit models (PerchetRigolletChassangSnowberg16,Caria_etal20,CurrieMacLeod20,KasySautmann21,Kawaguchi21, KawaguchiUetakeWatanabe21)\footnote{While we focus on online learning environments, there is a rich line of work that studies offline learning of optimal policies after the experimental or observational data is collected (KitagawaTetenov18,NaritaYasuiYata19,AtheyWager21,KallusZhou21, ShiWanChernozhukovSong21, ZhanHadadHirshbergAthey21, ChenAndrews23).}. The closest one to our study is that of LiRaymondBergman20, which examines application of contextual bandit algorithms for making decisions in the hiring process. We add to this sub-literature by both studying the biases that arise in algorithmic decision-making when there is an endogeneity problem and showing how to correct for it.

Our paper also contributes to the vast literature of casual inference; see, for example, ImbensRubin15 for a review. Most of this literature does not examine the environment of online learning, where the actions influence and are influenced by data. Two notable exceptions are NambiarSimchiWang19 and LiLuoZhang21_fullversion. NambiarSimchiWang19 consider a dynamic pricing problem with learning, where the endogeneity problem arises from mis-specification of demand functions. LiLuoZhang21_fullversion consider a Markov decision process setup with learning and show that online learning environments may exacerbate the estimation bias. Different from these papers, our focus is on the dynamic selection problem where current data, through affecting the choice of actions, affects how future data is generated. This dynamic selection problem also differs from selection problems in Heckman79,Heckman90, rubinpropensity, Altonji2005Selection00, and Oster19, which do not feature how past selection problems affect future data selection.

The remainder of the paper is organized in the following manner. Section (ref) introduces the background of the contextual bandit problem. Section (ref) discusses the case where there exists at least one endogenous variable in the contextual bandit problem, which leads to the dynamic selection problem and self-fulfilling bias. Section (ref) presents a set of regularity conditions for IVs and the contextual bandit setup as well as proposes a class of IV-based bandit algorithms. Section (ref) establishes the main results including regret bounds and asymptotic distribution for the proposed algorithms. Section (ref) demonstrates the performance of these algorithms in a series of simulations. Section (ref) presents the conclusions. Technical proofs are included in the Appendix.

Background

Consider an agent who follows an algorithm to make a sequence of decisions over a time horizon of $T$ periods. At each time $t=1,\ldots,T$, the agent observes a vector of covariates $\boldsymbol{v}_t\in\mathbb{R}^p$, takes an action (i.e., pulls an arm) $a_t\in \{1,\ldots,K\}$ with $K\geq 2$, and receives a random reward $R_t$:

where $\mu_i(\boldsymbol{v})$ is the unknown reward function associated with arm $i$, and $\varepsilon_t$ is the noise. At each time point $t$, the algorithm specifies a policy that maps $\boldsymbol{v}_t$ to $a_t$, based on the historical data $\mathcal{H}_{t-1}\coloneqq (\boldsymbol{v}_1,a_1,R_1,\ldots,\boldsymbol{v}_{t-1},a_{t-1},R_{t-1})$. The goal is to maximize the expected cumulative reward $\operatorname{\mathbb{E}}[\sum_{t=1}^T \mu_{a_t}(\boldsymbol{v}_t)]$, where the expectation is taken with respect to the distribution of $\mathcal{H}_T$ induced by the particular algorithm.

This sequential decision-making problem is commonly known as the contextual bandit problem Slivkins19. Evidently, if each reward function $\mu_i$ is known in advance, the agent would employ the oracle policy at each time $t$, pulling the optimal arm associated with $\boldsymbol{v}_t$, that is, $\pi^*(\boldsymbol{v}_t)\coloneqq \operatorname*{argmax}_{ i = 1,\ldots,K}\mu_i(\boldsymbol{v}_t)$. In practice, however, $\mu_i$ is unknown and must be estimated from data. Hence, the arm that is actually pulled at each time $t$ is in general not the optimal arm, leading to an instantaneous regret: $\max_{i=1,\ldots,K} \mu_i(\boldsymbol{v}_t) - \mu_{a_t}(\boldsymbol{v}_t)$. A standard metric for measuring the performance of an algorithm is expected cumulative regret:

We simply refer to it as “regret” for the remainder of this paper. The regret quantifies the difference in expected cumulative reward between an algorithm and the oracle policy. As such, the agent's goal is to approximate the performance of the oracle by progressively learning the reward functions. For simplicity, we will henceforth assume that for each arm $i$, the reward function $\mu_i$ is linear in the covariate vector (i.e., $\mu_i(\boldsymbol{v}) = \boldsymbol{v}^\intercal \boldsymbol{\alpha}_i$), where $\boldsymbol{\alpha}_i\in\mathbb{R}^p$ is an unknown parameter vector. Consequently, the problem is reduced to learning these linear coefficients over time.

When the covariates are exogenous, that is, $\mathbb{E}[\varepsilon_t|\boldsymbol{v}_t]=0$, numerous effective algorithms have been proposed to learn the coefficients. While these algorithms vary in their finite-time and asymptotic properties, they all converge to the true value of the coefficients over time and, therefore, exhibit a sublinear regret: that is, $T^{-1}\mathsf{Regret}(T)\to 0$ as $T\to\infty$. This indicates that as the horizon increases, the agent is increasingly likely to take the optimal action in most periods.

Self-fulfilling Bias: An Example

We now study an example in which the covariates are endogenous---that is, $\mathbb{E}[\varepsilon_t|\boldsymbol{v}_t]\neq 0$. We show that the endogeneity of covariates leads to distortion in actions, which generates another type of endogeneity; that is, it creates “endogeneity spillover”. The additional endogeneity generates a dynamic selection problem and leads to a new type of bias, which we refer to as self-fulfilling bias.

Consider the following special case of our setup. Assume that there exist two arms, and between the two arms $\mathcal{A}=\{1,2\}$, one is the safe arm, having a known expected reward that is independent of the covariates, while the other is the risky arm, whose expected reward has an unknown linear dependence on the covariates. Further, assume that the covariates are one-dimensional. In this simple example, the reward functions are \[ \mu_1(v) \equiv c \qq{and} \mu_2(v) = \alpha v,\quad \forall v\in\mathbb{R}. \] It follows that, if $\alpha$ is known and positive, then the oracle policy for the agent is to pull arm 2 if $v> c/\alpha$, and pull arm 1 otherwise.

However, because $\alpha$ is unknown, the agent needs to estimate its value over time and makes her decisions accordingly. In contrast to the standard regression analysis in which data is taken as given, in the dynamic environment considered here, the data used for estimating $\alpha$ is only available when arm 2 is pulled (pulling arm 1 generates noisy observations of $c$, which are irrelevant to $\alpha$). Now, suppose the agent uses the ordinary least squares (OLS) method to estimate $\alpha$ and the estimates converge to a limit, say $\widehat \alpha$. Then, in the long run,

Note that given $\widehat \alpha$, the agent's policy in the long run is to pull arm 2 when $v>c/\widehat \alpha$. Thus, the conditioning event in equation (ref) is identical to $\{v_t > c/\widehat\alpha\}$. Using the fact that $R_t = \alpha v_t + \varepsilon_t$ for arm 2, we have

It is evident from equation (ref) that $\widehat{\alpha}$ is a fixed point as it appears on both sides of the equation. It also shows that the bias of the estimate, $\widehat\alpha-\alpha$, has an expression that is similar to, but different from, that of the usual OLS bias, which is given by $ \frac{\operatorname{Cov}[v_t, \varepsilon_t]}{\operatorname{Var}[v_t]}$. We refer to $\widehat \alpha - \alpha$ as the self-fulfilling bias to reflect that the limit policy of the agent is induced by her limit belief (i.e., the limit estimate $\widehat{\alpha}$), and the limit belief is confirmed by the data generated from the limit policy.

To unpack the self-fulfilling bias, note that there are two---rather than one---types of endogeneity problems. The first type results from the correlation between the noise and the covariates. This directly creates a bias in the estimate in a manner that is similar to the usual OLS bias. The second type results from sample selection, which arises because the estimated coefficients affect the actions of the agents. This sample selection is dynamic in nature because the policy that determines agent's actions changes over time.

To illustrate the two types of endogeneity formally, we rewrite equation (ref) as

When $\varepsilon_t$ and $v_t$ are correlated, the first type of endogenous variable in this regression is $ v_t \operatorname{\mathbb{I}}(a_t = 2)$ if the arm $a_t$ is selected independent of $v_t$. But because $a_t$ depends on $v_t$---through the relation $\operatorname{\mathbb{I}}(a_t=2) = \operatorname{\mathbb{I}}(v_t > c/\widehat\alpha)$ in the long run---the correlation between $\varepsilon_t$ and $v_t$ leads to a correlation between $\operatorname{\mathbb{I}}(a_t=2)$ and $\varepsilon_t$. In other words, the endogeneity problem in $v_t$ spills over to $\operatorname{\mathbb{I}}(a_t = 2)$, creating another endogenous variable.

The additional endogenous variable complicates the dependence of the value of the limit coefficient estimate $\widehat\alpha$ on the joint distribution of $v_t$ and $\varepsilon_t$. In particular, unless the term $\frac{\operatorname{Cov}[v_t, \varepsilon_t|v_t > s]}{\operatorname{Var}[v_t|v_t>s]}$ is the same for all cutoff $s$---this happens only when $\mathbb{E}[\varepsilon_t|v_t]$ is a linear function of $v_t$\footnote{$\mathbb{E}[\varepsilon_t|v_t]$ is a linear function of $v_t$ when $(v_t,\varepsilon_t)$ has a joint normal distribution.}---$\widehat\alpha$ is different from the OLS estimate. In other words, an additional bias arises whenever $\mathbb{E}[\varepsilon_t|v_t]$ is a nonlinear function of $v_t$.

When there is the additional bias, the value of $\widehat{\alpha}$ (and hence the value of the self-fulling bias) may not be unique, which happens when equation (ref) contains multiple solutions. Figure (ref) illustrates one such case and shows that the agents' beliefs converge to two different values in the long run. With multiple self-fulfilling biases, this example shows that agents can adopt different policies in the long run, even if the underlying production environment is the same. This provides one explanation for why seemingly similar enterprises may choose different practices and result in persistent differences in performance, a central question in organizational economics and strategy (see, e.g., GibbonsHenderson12 for a review).

We conclude this section by making two comments. First, we have illustrated the self-fulfilling bias and its severity using a simple example. Despite its simplicity, the example points to a general problem: in any dynamic environment where the agent's actions depend on some covariates, the endogeneity in the covariates can generate additional endogeneity with the actions. Because of the self-fulfilling bias, the policy is suboptimal in the long run. The number of periods a wrong action is taken is proportional to the time horizon $T$. Thus, the regret of the policy with self-fulfilling bias is in the order of $\mathcal{O}(T)$.

Second, the self-fulfilling bias cannot be corrected by the usual exploration of the agent, i.e., randomly choosing actions occasionally. This is because as long as $v_t$ is endogenous, OLS bias remains. Moreover, when the data from the non-random actions is used in the regression, the endogeneity in $v_t$ spills over to $\operatorname{\mathbb{I}}(a_t=2)v_t$, creating additional bias. The solution for the endogeneity in $v_t$ is not to carry out exploration in the conventional sense. Instead, the solution is to do causal exploration---that is, to perturb the data generating process, and, through doing so, generating IVs accordingly. Unlike the randomization of actions in the literature (conventional exploration), which we denote as ex-post exploration, the generation of IVs through perturbation of data generating process is ex-ante to decision making, thus we call it ex-ante exploration. We discuss how to correct the self-fulfilling bias with IVs in the next section.

IV-Greedy Algorithm

We now proceed to illustrate how to integrate IVs into bandit algorithms. The algorithm we propose not only corrects the self-fulfilling bias, thereby providing consistent estimation of the reward functions and progressively improving a policy $\pi(\cdot | v)$ towards the oracle policy over time, but also attains a sublinear regret of order $\mathcal{O}(\log(T))$. Simultaneously addressing the two concerns---endogeneity and regret---is crucial for online learning environments.

As illustrated in the example above, we can rewrite observed rewards in Equation (ref) as:

where

Equation (ref) represents a joint linear regression model in that it integrates reward observations across all time periods, as opposed to partitioning them based on the selected arm. The use of $\widetilde{\boldsymbol{v}}_t$ as the regressors in formulation (ref) underscores the endogeneity spillover issue discussed in Section (ref). Specifically, the action $a_t$ may become endogenous due to its potential dependence on $\boldsymbol{v}_t$ and the endogeneity of $\boldsymbol{v}_t$, hence making $\operatorname{\mathbb{I}}(a_t=i)\boldsymbol{v}_t$ endogenous for each $i$. As a result, the OLS method leads to a biased estimation of the coefficient vector $\boldsymbol{\alpha}$.

Assuming a set of IVs, as denoted by $z_t$, are available, we can use the 2SLS method to correct for this bias, as is typically done in a static data analysis environment. However, our online learning environment introduces substantial challenges due to the intertemporal dependencies among the regressors $\{\widetilde{\boldsymbol{v}}_t : t = 1, \ldots, T\}$, which are a result of the adaptive nature intrinsic to any effective algorithm. To address the challenges, we propose to employ a joint-2SLS approach, as defined later in Equation (ref), to estimate $\boldsymbol{\alpha}$ using the joint linear regression model (ref), rather than estimating for each arm separately.

We introduce our algorithm in Section (ref). The algorithm's two key features---the joint-2SLS and three-phase structure---are discussed in detail in Section (ref) and Section (ref), respectively.

Structure

In this subsection, we propose an IV-based algorithm for linear contextual bandits and name it IV-Greedy. This algorithm consists of three phases, which are formally demonstrated in Algorithm (ref).

Phase 1: Coefficient Stabilization. In this phase, we seek a stable estimate of the coefficient vector $\boldsymbol{\alpha}$, meaning that the estimate should stay close to the true value with a high probability. For this purpose, our policy is to select each arm randomly---irrespective of the observed covariates---with equal probability. At the end of Phase 1, we run arm-specific-2SLS to obtain an estimate of the coefficient vector $\boldsymbol{\alpha}$. Specifically, depending on the arm pulled in each period---whether $a_t=1$, $2$, etc.---we divide the periods into $K$ groups and then conduct 2SLS separately on the data (i.e., rewards, covariates, and IVs) in each group. Note that the estimate is unbiased because the actions are generated randomly, and the IVs are used to correct for the endogeneity in the covariates. But the absence of bias is achieved at the cost of a regret that is linear in the number of periods $\mathtt{T}_1$. To balance the regret and the purpose of coefficient stabilization, we choose the duration of Phase 1 to be $\mathtt{T}_1 = \mathcal{O}(\log(T))$.

Phase 2: Covariance Stabilization. In this phase, the policy takes the form of a greedy policy---that is, it uses the estimate of $\boldsymbol{\alpha}$ from Phase 1 to evaluate the expected payoff of each arm for a given value of the covariates, and then selects an arm that maximizes the expected payoff. During this phase, which lasts from period $\mathtt{T}_1+1$ to $\mathtt{T}_2$, the estimate of $\boldsymbol{\alpha}$ is not updated. Fixing the coefficient estimate helps initialize Phase 3 of the algorithm with a good estimate of the covariance matrix $\boldsymbol{\Omega}^*$, as defined in Equation (ref). As discussed in Section (ref), the presence of Phase 2 is critical for the estimate of $\boldsymbol{\alpha}$ to converge to the true value. Similar to Phase 1, we set the duration of this phase to be $\mathtt{T}_2-\mathtt{T}_1=\mathcal{O}(\log(T))$ so that sufficient data is generated without causing excessive regret.

Phase 3: Policy Improvement. In this phase, the policy is again greedy: we select the arm that maximizes the estimated expected reward in each period. However, in contrast to Phase 2, the criterion for evaluating the expected reward is constantly updated. In each period, the expected reward for each arm is calculated from the most updated estimate of $\boldsymbol{\alpha}$. Note that in this phase, the estimator that we propose to use is the joint-2SLS estimator. Namely, we consider to estimate a 2SLS model jointly for all arms $i=1,\ldots,K$, This is critical for the algorithm to produce consistent estimator asymptotically. We discuss this point in more detail in Section (ref).

To describe the arm-specific-2SLS method used in Algorithm (ref), we introduce the following notation. Let $\boldsymbol{V}_{i,\mathtt{T}_1}$ denote the observed covariates in those time periods of Phase 1 when arm $i$ is selected. Specifically, $\boldsymbol{V}_{i,\mathtt{T}_1}$ is a matrix formed of row vectors $\boldsymbol{v}_t^\intercal$ for all $t$ such that $t \leq \mathtt{T}_1$ and $a_t = i$. Similarly, we define $\boldsymbol{Z}_{i,\mathtt{T}_1}$ as the matrix composed of row vectors $\boldsymbol{z}_{i,t}^\intercal$, and $\boldsymbol{R}_{i,\mathtt{T}_1}$ as the column vector composed of elements $R_{i,t}$, both corresponding to the same time periods as those utilized in defining $\boldsymbol{V}_{i,\mathtt{T}_1}$. The number of rows in these three matrices (or in the case of the vector) corresponds to the number of times that arm $i$ is pulled during Phase 1. Then, the arm-specific-2SLS estimator for the coefficient vector $\boldsymbol{\alpha}_i$ of the reward function associated with arm $i$ is given by

where $\mathcal{P}$ denotes the projection operator, defined as $\mathcal{P}[\boldsymbol{Z}] \coloneqq \boldsymbol{Z}(\boldsymbol{Z}^\intercal \boldsymbol{Z})^{-1} \boldsymbol{Z}^\intercal$ for any matrix $\boldsymbol{Z}$. The formula provided above is derived from standard calculations associated with the 2SLS method.

To define the joint-2SLS estimator used in Phase 3, for any $t \geq \mathtt{T}_1+1$, we introduce $\widetilde{\boldsymbol{V}}_{\mathtt{T}_1:t}$ as the matrix composed of row vectors $\widetilde{\boldsymbol{v}}_s^\intercal$ for all $s = \mathtt{T}_1+1, \ldots, t$, where $\widetilde{\boldsymbol{v}}_{s}$ is the augmented covariate vector as defined in (ref). This matrix has $(t-\mathtt{T}_1)$ rows because we use all data that starts from the beginning of Phase 2. Likewise, we can define $\boldsymbol{Z}_{\mathtt{T}_1:t}$ and $\boldsymbol{R}_{\mathtt{T}_1:t}$. These three represent the data accumulated from the start of Phase 2 through time $t$. The joint-2SLS estimator for the coefficient vector $\boldsymbol{\alpha}$ is then given by

Lastly, the need for inference calls for a characterization of the limiting covariance matrix linked with the joint-2SLS estimate of $\boldsymbol{\alpha}$. Intuitively, if the policy induced by the proposed algorithm converges to the oracle policy, the data will, in the long run, be generated under this oracle policy. Following standard calculations for the 2SLS method, it becomes evident that the covariance matrix should converge to

where \[\boldsymbol{\Sigma}^*_{vz}\coloneqq \mathbb{E}[\boldsymbol{v}_t^*\boldsymbol{z}_t^\intercal],\quad \boldsymbol{\Sigma}_{zz}\coloneqq \mathbb{E}[\boldsymbol{z}_t \boldsymbol{z}_t^\intercal], \qq{and} \boldsymbol{v}_t^*\coloneqq

\in\mathbb{R}^{Kp}.\]

Key Features of the Algorithm

The IV-Greedy algorithm has two distinctive features that merit further exploration. The first feature is the use of the joint-2SLS approach, and the second is the three-phase structure, with a particular emphasis on the role of Phase 2.

The Necessity of the Joint-2SLS

During Phase 3, the main phase of the algorithm, the joint-2SLS approach is utilized. As we will demonstrate, several seemingly obvious alternate design choices for the algorithm are available. However, they fail to achieve consistent estimation with a sublinear regret, which is the dual objective in our online learning environment.

Contrary to the 2SLS estimator (ref), a simple approach to estimating $\boldsymbol{\alpha}$ in Phase 3 involves using the standard OLS method in an arm-specific way. Specifically,

where $\boldsymbol{V}_{i,\mathtt{T}_1:t}$ denotes the covariates $\boldsymbol{v}_s$ (instead of the augmented covariates $\widetilde{\boldsymbol{v}}_s$) that are observed in the time periods $s=T_1+1,\ldots, t$ when arm $i$ is selected, and $\boldsymbol{R}_{i,\mathtt{T}_1:t}$ is similarly defined. This estimator is separately constructed for the parameter $\boldsymbol{\alpha}_{i,t}$ for each arm $i$ based on the data available up to time $t$.

While the use of the OLS method in an arm-specific manner is standard practice in linear contextual bandit problems, the presence of endogeneity clearly results in a biased estimate of each $\boldsymbol{\alpha}_i$. Moreover, as illustrated in the example in Section (ref), a self-fulfilling bias will emerge, leading to sub-optimal policies in the long run.

A second approach to estimating $\boldsymbol{\alpha}$ in Phase 3 is the arm-specific application of the 2SLS method. This approach is a natural choice if a set of IVs are available and can be considered as a generalization of (ref):

Here, $\boldsymbol{Z}_{i,\mathtt{T}_1:t}$ is defined in the same way as $\boldsymbol{V}_{i,\mathtt{T}_1:t}$. However, this estimator still does not yield consistent estimates of $\boldsymbol{\alpha}_i$. This inconsistency stands in contrast to the traditional use of the 2SLS method in static data analysis settings, where it is employed to correct bias caused by endogeneity issues. As discussed in Section (ref), this failure is attributed to the endogeneity spillover effect. In other words, the selected arms, which form part of the data, can also become endogenous, in addition to the endogenous covariates. The arm-specific 2SLS approach fails to address the part of endogeneity that spills over to the selected arms. This issue arises from the dynamic sample selection, which is a consequence of the policy's adaptive nature in arm selection.

A straightforward way to circumvent the dynamic sample selection issue is to render the policy non-adaptive. This leads to a third alternative approach to estimating $\boldsymbol{\alpha}$ in our endogenous online learning environment. Specifically, one could implement the so-called “randomize-then-commit” (RTC) strategy as follows. Initially, arms are selected uniformly at random for a series of consecutive time periods, say $t=1,\ldots,\mathtt{T}_1$, similar to what is done in Phase 1 of the IV-Greedy algorithm. Then, the estimate $\widehat\boldsymbol{\alpha}_{\mathtt{T}_1}$ is constructed using the arm-specific 2SLS. As $\mathtt{T}_1\to\infty$, this becomes a consistent estimator because all arms have been randomly selected, thus avoiding the endogeneity spillover effect. Finally, one commits to the greedy policy that selects the seemingly optimal arm based on the estimate $\widehat\boldsymbol{\alpha}_{\mathtt{T}_1}$, without updating the estimates in all subsequent periods. In other words, $a_t = \operatorname*{argmax}_i \{\widehat\boldsymbol{\alpha}_{\mathtt{T}_1}^\intercal \boldsymbol{v}_t \}$ for all $t=\mathtt{T}_1+1,...T$.

While the RTC strategy avoids the endogeneity spillover effect and ensures consistent estimation, it does so at the expense of a linear regret---a drawback not shared by the IV-Greedy algorithm. The greedy mechanism, or any adaptive mechanism aiming to emulate the decisions of the oracle policy in an online learning environment, is indispensable if the objective is to achieve a sublinear regret. Consequently, the dynamic selection issue is likely to be generated by such an adaptive mechanism, necessitating an adjustment in the estimation approach accordingly.

The Necessity of the Covariance Stabilization Phase

The second key feature of the IV-Greedy algorithm is the inclusion of Phase 2. This phase aids in stabilizing the matrix $\mathbb{E}[\widetilde{\boldsymbol{v}}_t \boldsymbol{z}_t^\intercal]$ towards the limit $\mathbb{E}[\boldsymbol{v}_t^* \boldsymbol{z}_t^\intercal]$, resulting in an accurate estimate of the covariance matrix $\boldsymbol{\Omega}^*$, as defined in Equation (ref). An intuitive alternative approach might involve carrying out Phase 1 first, which provides a sufficiently accurate estimate of $\alpha_t$, and then moving directly to the joint-2SLS. However, due to the online nature of our problem, this approach fails to yield a consistent estimate over the long term. Poor estimates of either the coefficients or the covariance matrix in the past have lasting effects through their impact on the chosen actions, leading to biased long-term estimates.

Suppose one arm (for the sake of discussion, let's say arm 1) encounters a bad draw, which results in a lower estimate of $\boldsymbol{\alpha}$. Without the covariance stabilization phase, the magnitude of this downward estimate could be substantially large. In such a scenario, a direct application of Phase 3 of the algorithm implies that arm 1 may not be chosen again throughout the entire sequence of iterates. This leads to a permanent underestimate of the reward function of arm 1, hence resulting in a sub-optimal policy. Technically, a bad draw could imply that the indicator $\operatorname{\mathbb{I}}(a_t = 1)$ approaches zero as $t\rightarrow \infty$. This leads to the near singularity of the matrix $\mathbb{E}[ \widetilde{\boldsymbol{v}}_t \boldsymbol{z}_t^\intercal]$, causing unstable estimates of $\boldsymbol{\Omega}^*$ and inconsistent estimates of $\boldsymbol{\alpha}$. We formally demonstrate the necessity of Phase 2 in the proposition below.

Theoretical Results

In this section, we analyze the theoretical properties of the IV-Greedy algorithm. We show that this algorithm produces a regret of order $\mathcal{O}(\log(T))$. We also show that it delivers consistent and asymptotically normal estimates of $\boldsymbol{\alpha}$.

Condition (ref) is common in the bandit literature and is key for establishing a $\log(T)$-like regret bound. For example, GoldenshlugerZeevi13 assume normality on $\varepsilon_t$, and ZhongHongLiu21 assume boundedness, both of which are special cases of Condition (ref). BastaniBayatiKhosravi21 impose the same sub-Gaussian condition as we do. If Condition (ref) is replaced with moment restrictions on $\varepsilon_t$, one might still obtain a sublinear regret, but not a $\log(T)$ regret. Conditions (ref) and (ref) are again common assumptions in the IV and contextual bandit literature, respectively.

Condition (ref) implies that $\boldsymbol{\Sigma}_{vz}^*\boldsymbol{\Sigma}_{zz}^{-1}(\boldsymbol{\Sigma}_{vz}^*)^\intercal \in \mathbb{R}^{(Kp)\times (Kp)} $ is a positive definite matrix. This is a key condition for parameter identification. It requires that the oracle policy must be dependent on $\boldsymbol{v}_t$; more specifically, $\operatorname{\mathbb{I}}(a_t^*=1)\boldsymbol{v}_t, \ldots,\operatorname{\mathbb{I}}(a_t^*=K)\boldsymbol{v}_t$ should not be co-linear when projected to the $\boldsymbol{z}_t$ space. Condition (ref) holds in general if $\boldsymbol{\delta}_{i,j} \neq \boldsymbol{0}$ for all $1\leq i\neq j\leq K$.

Further, Condition (ref) states that the density of $\boldsymbol{v}_t$ is Lipschitz continuous in the vicinity of the hyperplance $\{\boldsymbol{v}:\boldsymbol{v}^\intercal \boldsymbol{\delta}_{i,j} = 0\}$. This condition is often referred to as the “margin condition” in statistical learning literature Tsybakov04. It is also a standard condition in the literature on contextual bandits. Moreover, Conditions (ref) and (ref) together imply that $ \Pr(\boldsymbol{v}_t^\intercal \boldsymbol{\delta}_{i,j} <0)>0$ and $ \Pr(\boldsymbol{v}_t^\intercal \boldsymbol{\delta}_{i,j}>0)>0$, which is referred to as the “diversity condition” in GoldenshlugerZeevi13.

Regret Analysis

In this subsection, we describe the long-run regret of the IV-Greedy algorithm. We then discuss a new technique---zig-zag induction---that we develop for analyzing algorithms associated with online learning environments.

Note that in the presence of endogeneity, an algorithm that does not produce consistent estimates of the coefficient vector $\boldsymbol{\alpha}$ will generally suffer a linear regret NambiarSimchiWang19. Therefore, it is necessary to establish consistency of the coefficient estimate. This requires analyzing the probability of the estimate $\widehat\boldsymbol{\alpha}_t$ falling in the vicinity of $\boldsymbol{\alpha}$ over Phase 3 of the algorithm.

From the 2SLS formula, it can be shown that the coefficient estimate $\widehat{\boldsymbol{\alpha}}_t$ in Phase 3 depends on the covariance estimate $\widehat{\boldsymbol{\Sigma}}_{vz,{\mathtt{T}_1:t}}$. The calculation of $\widehat{\boldsymbol{\Sigma}}_{vz,{\mathtt{T}_1:t}}$, however, is not standard because it depends on the past estimates $\{\widehat{\boldsymbol{\alpha}}_s:\mathtt{T}_1\leq s\leq t-1\}$---that is,

where $a_s$ is selected by the greedy algorithm and depends on $\widehat{\boldsymbol{\alpha}}_s$.

Note that if the optimal arm $a^*_s$ were known and selected in each period, we would simply calculate

which is standard because it involves the average of samples from i.i.d. random variables.

However, because the optimal arms are unknown, the analysis of $\widehat{\boldsymbol{\Sigma}}_{vz,\mathtt{T}_1:t}$ poses a challenge. First, since $\widehat{\boldsymbol{\Sigma}}_{vz,\mathtt{T}_1:t}$ depends on the choice of arm $a_s$ for all $s$ from $\mathtt{T}_1+1$ to $t$, any past coefficient estimate $\widehat{\boldsymbol{\alpha}}_s$, through its effect on the selected arm, has an effect on $\widehat{\boldsymbol{\Sigma}}_{vz,{\mathtt{T}_1:t}}$. Second, these coefficient estimates are serially correlated because they are all calculated from the same data source. Lastly, not only does $\widehat{\boldsymbol{\Sigma}}_{vz,{\mathtt{T}_1:t}}$ depend on $\{\widehat{\boldsymbol{\alpha}}_s:\mathtt{T}_1\leq s\leq t-1\}$, $\widehat{\boldsymbol{\alpha}}_t$ also depends on $\widehat{\boldsymbol{\Sigma}}_{vz,{\mathtt{T}_1:t}}$. This two-way dependence implies that the coefficient estimates and the covariance estimates are entangled.

The two-way dependence, a common feature of online learning environments, makes it difficult for the coefficient estimates to converge to the true value in the long run. A poor coefficient estimate can lead to a wrong action, which contaminates the generated data (since the data associated with the right arm is no longer observed). The wrong data then worsens the future coefficient estimates and, thus, the future data-generating process. In summary, errors made in the past do not disappear: they make future errors more likely.

To deal with this problem, we untangle the dependence via a “zig-zag” induction. As an overview of its structure, assume that, in period $t-1$ in Phase 3, the coefficient estimate $\widehat{\boldsymbol{\alpha}}_s$ is sufficiently close to the true value for all $s$ from $\mathtt{T}_2+1$ to $t-1$ with a sufficiently high probability. A induction step is then used to show that this remains true for period $t$. To carry out the induction step, two sub-steps are needed.

The first sub-step shows that the covariance estimate $\widehat{\boldsymbol{\Sigma}}_{vz,{\mathtt{T}_1:t}}$ is sufficiently accurate in period $t$. This is the zig-step. In the second sub-step, we use this result from the zig-step to show that the induction hypothesis holds at time $t$. The difficult part of the induction is the zig-step. As mentioned earlier, the covariance estimate in the zig-step depends on all the coefficient estimates in the past, which are serially correlated.

To deal with the challenge in the zig-step, let \[\mathscr{A}_t\coloneqq \Biggl\{\|\widehat{\boldsymbol{\alpha}}_t-\boldsymbol{\alpha}\|\leq C_A \sqrt{\frac{\log(T)}{t-\mathtt{T}_1}}\Biggr\} \qq{and} \mathscr{B}_t\coloneqq \bigl\{\|\widehat{\boldsymbol{\Sigma}}_{vz,\mathtt{T}_1:t}-\boldsymbol{\Sigma}_{vz}^*\|\leq \eta\bigr\}, \] for some constant $C_A>0$, where $\|\cdot\|$ denotes the Euclidean norm for vectors and the spectral norm for matrices. Further, let $\mathscr{A}_{\mathtt{T}_2:t}:=\cap_{s=\mathtt{T}_2+1}^{t} \mathscr{A}_{s}$, where we note that the intersection begins at the beginning of Phase 2. This is the event in which all the past coefficient estimates from Phase 2 are sufficiently accurate. With these definitions, the induction shows that there exists a constant $C>0$, such that

This is achieved via a two-step induction using $\mathscr{B}_t$ as a bridge---first from $\mathscr{A}_{\mathtt{T}_2:t-1}$ to $\mathscr{B}_t$ and then from $\mathscr{B}_t$ to $\mathscr{A}_t$ (see Figure (ref)).

Note that we perform the induction on $\mathscr{A}_{\mathtt{T}_2:t}$ instead of $\mathscr{A}_t$. This is because the zig-zag induction step requires the analysis of the covariance estimate. As we emphasize above, the covariance estimate depends on the past coefficient estimates. Therefore, showing that the covariance estimate is sufficiently accurate requires event $\mathscr{A}_{\mathtt{T}_2:t}$ to occur---that is, all the past coefficient estimates from Phase 2 on to be sufficiently accurate.

A key observation in our induction step is that, when the assumption holds in period $t-1$ of Phase 3, we can show (with details in the proof) that there exists a constant $C'>0$, such that

for all $s=\mathtt{T}_2+1,\ldots,t-1$. Therefore, this relation states that a wrong arm is selected only when the difference in the actual expected reward between this arm and some other arm is small. (We can also show, with a similar argument, that (ref) holds all $s=\mathtt{T}_1+1,\ldots,\mathtt{T}_2$, i.e., Phase 2 of the algorithm, provided that the coefficient estimate at the end of Phase 1 is sufficiently accurate.)

The intuition for this observation is that, when the coefficient estimate is sufficiently accurate, the estimated expected reward of choosing each arm (calculated from the coefficient estimate) is also close to the actual expected reward; and thus the arm selected by the algorithm is optimal if the actual expected reward from this arm is sufficiently different than that from any other arm. In other words, when a wrong arm is selected, it must be that the difference in the actual expected reward between this arm and some other arm is small.

A consequence of this observation is that, instead of estimating the probability that a wrong arm is selected, which depends on the past coefficient estimates, it suffices to estimate the probability that the covariate vector $\boldsymbol{v}_s$ falls within a bound. Specifically, we can show that

for some constant $\tilde{C}>0$. Because the covariate vectors $\boldsymbol{v}_s$ are i.i.d. over different periods, so are $\operatorname{\mathbb{I}}\left(|\boldsymbol{v}_s^\intercal \boldsymbol{\alpha}_j - \boldsymbol{v}_s^\intercal \boldsymbol{\alpha}_i|\leq C'\eta \right)$. In other words, the right-hand-side of the inequality (ref) is a sample average of i.i.d. random variables; and therefore, bounds on its tail probability can be established using standard concentration inequalities. This allows us to show that, with a sufficiently high probability, $\widehat{\boldsymbol{\Sigma}}_{vz,{\mathtt{T}_1:t}}$ is close to $\widehat{\boldsymbol{\Sigma}}_{vz,{\mathtt{T}_1:t}}^*$.

The induction shows that, with a sufficiently high probability, the coefficient estimates remains sufficiently accurate over the entire Phase 3 of the algorithm. Standard calculation BastaniBayatiKhosravi21 can then be applied to show that the regret in Phase 3 is $\mathcal{O}(\log(T))$. Since the durations of Phases 1 and 2 are both $\mathcal{O}(\log(T))$, this shows that the total regret is $\mathcal{O}(\log(T))$. GoldenshlugerZeevi13 prove that in a standard linear contextual bandit problem---with no endogeneity involved---the best possible lower bound for any algorithm is $C\log(T)$ for some constant $C$. Since our setup allows endogeneity in the covariates and includes standard linear contextual bandits as special cases, $C\log(T)$ is also a lower bound on regret for our setup. Hence, Theorem (ref) shows that IV-Greedy achieves the asymptotically minimal regret.

Statistical Inference

The contextual bandit literature mostly focuses on regret analysis, whereas results on statistical inference are relatively scarce. We provide such results for the coefficient estimates.

To construct a confidence interval for $\boldsymbol{\alpha}$, we need a consistent estimator of the covariance matrix $\sigma^2\bigl(\boldsymbol{\Sigma}_{vz}^*\boldsymbol{\Sigma}_{zz}^{-1}(\boldsymbol{\Sigma}_{vz}^*)^\intercal\bigr)^{-1}$ in (ref). To this end, note that $\widehat{\sigma}^2_T$, $\widehat{\boldsymbol{\Sigma}}_{vz,\mathtt{T}_1:T}$, and $\widehat{\boldsymbol{\Sigma}}_{zz,\mathtt{T}_1:T}$ are consistent estimators of $\sigma^2$, $\boldsymbol{\Sigma}_{vz}^*$, and $\boldsymbol{\Sigma}_{zz}$, respectively. Moreover, by the definition of $\widehat{\boldsymbol{\Omega}}_T$ in Algorithm (ref), \[ (T-\mathtt{T}_1) \widehat{\boldsymbol{\Omega}}_T = \bigl(\widehat{\boldsymbol{\Sigma}}_{vz,\mathtt{T}_1:T}\widehat{\boldsymbol{\Sigma}}_{zz,\mathtt{T}_1:T}^{-1}(\widehat{\boldsymbol{\Sigma}}_{vz,\mathtt{T}_1:T})^\intercal\bigr)^{-1}. \] Thus, we use $(T-\mathtt{T}_1)\widehat{\sigma}^2_T \widehat{\boldsymbol{\Omega}}_T$ to consistently estimate $\sigma^2\bigl(\boldsymbol{\Sigma}_{vz}^*\boldsymbol{\Sigma}_{zz}^{-1}(\boldsymbol{\Sigma}_{vz}^*)^\intercal\bigr)^{-1}$. Then, standard calculation leads to the following result, which facilitates inference on $\boldsymbol{\alpha}$.

Simulation Experiments

In this section, we present a simulation study to demonstrate the performance of IV-Greedy and compare it with the following alternatives. These alternatives---similar to IV-Greedy---all have a randomization phase of duration $\mathtt{T}_1$, in which each arm is selected uniformly at random.

For all the four algorithms, we set $\mathtt{T}_1=50$ and the total run length $T=20000$. In addition, we set $\mathtt{T}_2=100$ for IV-Greedy.

We evaluate these algorithms based on regret and the number of wrong arms pulled---both of which are common metrics for online learning algorithms. Additionally, we perform statistical inference on the coefficients in the reward function upon the termination of the algorithms. To this end, we consider a two-armed linear contextual bandit problem with three-dimensional covariates, i.e., $K=2$. Let the covariate vector $\boldsymbol{v}_t = (1, x_t, d_t)^\intercal$, where $x_t\in\mathbb{R}$ is an exogenous variable and $d_t\in\mathbb{R}$ is an endogenous variable. The endogeneity is introduced in the following manner. Suppose the random reward at time $t$ is \[ R_t = \sum_{i=1}^2 \mu_i(\boldsymbol{v}_t)\operatorname{\mathbb{I}}(a_t=i) +\varepsilon_t, \] where $\mu_i(\boldsymbol{v}_t) = \beta_{i,0} + \beta_{i, 1}x_t + \gamma_{i} d_t$, for some parameters $\beta_{i,0}$, $\beta_{i,1}$, and $\gamma_i$. Suppose also \[d_t = \sqrt{x_t} + \rho_{\check{z}} \check{z}_t + \rho_\eta \eta_t \qq{and} \varepsilon_t = \tilde{\varepsilon}_t + 2\eta_t,\] where $\rho_{\check{z}}$ and $\rho_\eta$ are some positive constants, and $x_t$, $\check{z}_t$, $\eta_t$, and $\tilde{\varepsilon}_t$ are independent random variables with the following distributions:

Here, we use $\mathsf{TruncNorm}(\mu, \sigma^2, l, u)$ to denote the truncated normal distribution that is derived from bounding the $\mathcal{N}(\mu,\sigma^2)$ distribution on the interval $(l, u)$. The parameters are specified as follows:

Note that $\varepsilon_t$ and $d_t$ are correlated through $\eta_t$ and, thus, $d_t$ becomes endogenous. Moreover, $\check{z}_t$ is correlated with $d_t$ but is uncorrelated with $\varepsilon_t$, so $\check{z}_t$ serves as an IV for $d_t$. However, for IV-Greedy to work, the number of IVs must be at least twice as many as the number of endogenous variables in order to account for the endogeneity spillover issue; see Remark (ref). As discussed in Remark (ref), we create additional IVs using $\operatorname{\mathbb{I}}(x_t\geq \mathring{x})$, $\operatorname{\mathbb{I}}(\check{z}_t\geq \mathring{z})$, and the interaction terms between them and $x_t$ or $\check{z}_t$, for some threshold values $\mathring{x}$ and $\mathring{z}$. Specifically, we use the following list of IVs: \[ \bigl\{1, \; x_t,\; \check{z}_t, \;\operatorname{\mathbb{I}}(x_t\geq 1), \;\operatorname{\mathbb{I}}(x_t\geq 1)\check{z}_t,\; \operatorname{\mathbb{I}}(x_t\geq 1.5),\; \operatorname{\mathbb{I}}(x_t\geq 1.5)\check{z}_t, \;\operatorname{\mathbb{I}}(\check{z}_t\geq 2), \;\operatorname{\mathbb{I}}(\check{z}_t\geq 2)\check{z}_t\bigr\}. \]

Further, we run the four algorithms (IV-Greedy, Naive-IV-Greedy, OLS-UCB, and RTC) 1000 times each and present the results in Figures (ref) and (ref) as well as Table (ref).

Figure (ref) presents the regret of each algorithm. First, in contrast to the others, IV-Greedy achieves a regret with a diminishing growth rate after a sufficient number of iterations (e.g., $T=5000$). The confidence bands further show that the performances of these two algorithms are stable in the learning process. Second, to verify our theoretical result in Theorem (ref), we conduct a linear regression analysis of the regrets of IV-Greedy on $\log(t)$. The value of $R^2$ is $0.99$, thereby providing strong empirical evidence for our theory. Third, although the theoretical analysis requires that Phases 1 and 2 of IV-Greedy should be “sufficiently long,” the simulation results indicate that they can be set to be moderate values ($\mathtt{T}_1=50$ and $\mathtt{T}_2=100$) in practice.

Figure (ref) presents the biases of the coefficient estimates. For the estimates produced by IV-Greedy, the bias vanishes as the number of iterations increases, while the other algorithms are generally biased. In particular, the fact that Naive-IV-Greedy produces inconsistent estimates of the coefficients demonstrates the existence of endogeneity spillover in this online learning example (the endogeneity in the covariates is addressed by the use of IVs in the arm-specific 2SLS, but the endogeneity that spills over to the actions remains).

Secondly, it is well known in the online learning literature that the use of the UCB criterion encourages the “exploration” (in the conventional sense) of seemingly inferior arms. Assuming the absence of endogeneity, this would allow OLS-UCB to provide consistent estimates of the coefficients at the cost of a sub-linear regret. The observation that OLS-UCB does not yield consistent estimates aligns with our discussion at the end of Section (ref). Namely, to address the endogeneity issue in an online learning environment, one must undertake what is termed “ex-ante exploration”. This process involves perturbing the data-generating process, and IVs serve this purpose effectively.

Lastly, RTC first performs arm-specific 2SLS to data from randomization and then commits to the coefficient estimates. This results in a dilemma: on the one hand, if the randomization period is long, then the regret is large, because the randomization produces a linear regret; on the other hand, if the randomization period is short, then the coefficient estimates are inaccurate,\footnote{In general, the 2SLS estimates have a second-order bias if the sample size is small or the IVs are weak AndrewsStockSun19.} which also leads to a large regret in the long run. Thus, the regret of RTC is, at best, a fractal polynomial of $T$, which is significantly worse than $\log(T)$.

In Table (ref), we report main statistics for the coefficient estimates after 20000 iterations of the five algorithms. For all the coefficients, IV-Greedy results in almost zero bias and the corresponding confidence intervals achieve proper coverage of the true values (the coverage is close to 95% for 95% confidence intervals). Note that Naive-IV-Greedy produces both substantially biased estimates and confidence intervals with zero coverage, which, again, demonstrates the endogeneity spillover issue. Note also that the quality of the inference results produced by RTC is fair, but the SD is much larger than IV-Greedy.

Conclusions

We study the dynamic selection problems that arise in algorithmic decision-making when the data has endogeneity problems. In a contextual bandit model, endogeneity in data influences the arms pulled, causing a non-random sampling of data that results in self-fulfilling bias. We correct for the bias by incorporating IVs to existing online learning algorithms. The new algorithms lead to the true parameter values and meanwhile attain low (logarithmic-like) regret levels. We also prove a central limit theorem for statistical inference of the parameters of interest. To establish these properties, we develop a general technique that untangles the interdependence between data and actions.

The use of IVs corrects the bias because they perturb the data-generating process. Therefore, our approach features “ex-ante exploration”, which contrasts with the “ex-post exploration”---that is, randomizing the choices given to the users once they arrive. The ex-post exploration, typically under the name of exploration, is the focus of most research. However, in the presence of endogenous data, our analysis highlights the importance of ex-ante exploration. Understanding how best to carry out ex-ante exploration and how these two types of exploration interact offer fruitful venues for future research.