Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
68,259 characters · 9 sections · 57 citation commands
Causal Bandits: Online Decision-Making in Endogenous Settings
The proliferation of user-level data presents a unique challenge in front of decision-makers. Decision-makers want to use individual-level data to tailor their decisions for each user. However, given the dynamic nature of online platforms, decision-makers need to adopt these decisions with incrementally available data. woodroofe1979one first proposed a simple model to solve such sequential decision-making problems with covariates. langford2007epoch later named the model "contextual bandit". Contextual linear bandits have been adopted across a wide variety of applications from advertising tang2015personalized, aramayo2022multi to healthcare durand2018contextual, dialogue systems liu2018customized, and personalized product recommendations li2010contextual,qin2014contextual. In the setting of a contextual linear bandit problem, in each round, the decision-maker observes a set of actions with each action characterized by a set of features. Decision-maker selects an action and observes a reward corresponding to that action. The objective of the decision-maker is to achieve cumulative reward close to that of optimal policy in hindsight.
Traditional formulations of contextual bandits make the unconfoundedness assumption i.e., the arm covariates are exogenous and are uncorrelated with the unobserved noise. However, in many economic settings, arm features can be correlated with unobserved noise. For instance, consider the problem of generating product recommendations for consumers. Platform operators would usually run online experiments to uncover the relationship between product features and consumer demand. Generally in such settings, product observable features like price are controlled by product owners (different from the platform operator) which could be set in anticipation of consumer demand and hence be correlated with the demand shocks unobserved by the platform operator (see Figure (ref) for illustration). In such settings, traditional bandit algorithms might lead to sub-optimal decisions. A common approach to correct the endogeneity bias in the offline setting is to use instrumental variables. Instruments are a set of variables correlated with endogenous variables but are otherwise not associated with the outcome variable. Offline instrumental variable methods use the variation in the exogenous component of the endogenous variable induced by the variation in the instrumental variables to make inference of causal effects. In this work, we propose an online instrumental variable method, we term $\epsilon$-BanditIV to address the issues induced by endogenous features in online settings and estimate the relationship between rewards and features.
Next, literature in contextual linear bandit has also primarily focused on minimizing the expected regret of the algorithm auer2002using, dani2008stochastic, chu2011contextual, abbasi2011improved. However, in a variety of social science problems, one may also be interested in understanding the asymptotic distribution of the estimated parameters. Algorithms that just minimize the regret may not guarantee the consistency of the model parameters and might lead to non-standard asymptotic distribution. Further, having standard asymptotic distributions, one can easily test the significance of features, and offers a traditional way to select variables. For instance, in the product recommendation example, an online platform might also be interested in understanding the effect of various marketing-mix variables (like price, and promotion) on consumer demand. To this end, we propose a linear bandit algorithm that pursues both regret minimization and consistent estimation of model parameters in endogenous settings. We use the martingale central limit theorem to show that our estimator of model parameters is asymptotically normal.
Finally, we demonstrate how $\epsilon$-BanditIV algorithm can be used to place optimal bids and simultaneously measure the average treatment effect (ATE) of advertising in Real-time bidding (RTB) auctions. In targeted marketing, RTB has become a dominating mechanism for selling user exposure to advertisers. Real-time bidding (RTB) systems, utilize auctions to allocate user impressions to competing advertisers. Even after their widespread adoption, measuring the effectiveness of advertising in such systems has remained hard in practice. Recent literature johnson2017ghost has characterized the inherent endogeneity in such settings and challenges in designing scalable experimental designs. On a high level, there are two key challenges that one needs to account for while designing experiments for RTB systems. The first challenge is that estimating the ATE of advertising requires randomly exposing users to advertising and then comparing the outcomes of users exposed to advertising to those who were not. However, in RTB settings, exposures are strictly not in the control of the bidder or experimenter and are determined through an auction.
The second challenge is the cost of the experimentation. To induce randomized exposure across the customer populations, the experimenter has to intentionally win or lose auctions. When bidding is not optimized, experimentation could lead to significant costs. For instance, in absence of optimal bidding function, overbidding to win an auction could lead to higher ad costs. Similarly, unnecessarily losing auctions could lead to lower consumer exposure and hence revenue. To this end, demonstrate how $\epsilon$-BanditIV can be used to tackle both these challenges. We also propose examples of plausible exogenous data that can be used as instrumental variables in such settings. We finally compare our method with existing online algorithms including Optimism in the Face of Uncertainty Linear bandit (OFUL) and Thompson Sampling (TS). We find significant advantages of our algorithm in both expected regret and parameter inference.
To summarize, our paper makes the following contributions --
The rest of the paper is organized as follows. We review related literature in areas of marketing, computer science, and econometrics in Section (ref). We set up the main problem, i.e. endogeneity problem in online stochastic linear bandits in Section (ref). We formulate the $\epsilon$-BanditIV algorithm in Section (ref) and show regret bound in Section (ref). We derive theoretical analysis on consistency and normality of the estimator used in the $\epsilon$-BanditIV algorithm in Section (ref). We conduct simulations of the proposed algorithm on synthetic data and RTB data in Sections (ref) and (ref) respectively.
Our paper contributes to three different strands of literature (i) adaptive experimentation and digital advertising, (ii) interactive learning and inference with MABs, and (iii) machine learning and econometrics.
The unprecedented growth of digital advertising markets attract increasing attention from both industry and academia. To improve the allocative efficiency of digital advertising market, there has been a surge of papers studying the advertising effect. The advertising effect is the incremental number of outcomes obtained as a result of an advertising campaign, such that these outcomes would not have happened without the campaign gordon2021inefficiencies. zantedeschi2017measuring proposed a hierarchical Bayesian model for advertising effects considering individual differences in purchase propensity and marketing response. rafieian2021targeting developed a unified modeling framework to answer a set of questions which includes the advertising effect of adopting efficient targeting policies. However, a number of challenges regarding the measurement of advertising effects remain. gordon2019comparison empirically compared multiple observational models for causal effects of digital advertising and suggested that common observational approaches fail to accurately measure the true causal effect. gordon2021inefficiencies pointed out several problems with experiments on ad effects, such as large sample size required and high experimental costs.
Adaptive experiments are increasingly used to investigate the advertising effect. araman2022diffusion studied a Bayesian sequential experimentation problem through dynamic programming and diffusion-asymptotic analysis. misra2019dynamic proposed a dynamic price experimentation policy which extended MAB algorithms to include microeconomic choice theory. gur2022adaptive considered auxiliary information between decision epochs into the development of an adaptive policy to improve experimentation performance. bertsimas2019covariate proposed an online allocation algorithm in experimental clinical trials using robust mixed-integer optimization to achieve a high statistical power. moazeni2020sequential modeled the marketing campaign performance as a multiplicative advertising exposure problem and proposed a computationally efficient learning policy through solving sequentially mixed-integer linear optimization problems. delshad2022adaptive studied the personalized dose-finding clinical trial problem through a Bayesian framework by stochastic programming and proposed an adapted one-step look-ahead approximate policy. anderer2022adaptive introduced a Bayesian adaptive clinical trial design that combined both surrogate and true outcomes to improve trial performance. bumbaca2020scalable proposed an algorithm to efficiently estimate Bayesian hierarchical models for inferences when researchers have limited number of observations per consumer in online targeted marketing.
At the framework level, several studies formulated adaptive experimentation and targeted advertising problems as MAB. schwartz2017customer utilized MAB to solve the online ad allocation problem. aramayo2022multi studied complete collections of ads and nonstationary rewards in house ads recommendation problem by using a MAB scheme. tang2015personalized presented implementations of contextual bandit algorithms on an online advertising problem. aramayo2022multi studied a contextual bandit approach to dynamically exhibit house ads to customers. We focus on the sequential decision making under the linear contextual bandit framework. auer2002using first introduced the contextual bandit setting through the Linear Reinforcement Learning (LinRel) algorithm with linear value functions. Subsequently, the contextual framework was improved by dani2008stochastic, chu2011contextual and abbasi2011improved through Upper Confidence Bound (UCB) type algorithms. This stream of literature often requires independency between contexts and the random error term, which however cannot be always satisfied in the reality. We consider a setting which allows the dependency between contexts and error term. This more general setting is well suited to real-world applications where endogeneity problems happen.
However, machine learning methods, such as methods used in MAB problems, are usually designed to obtain the best out-of-sample predictions, while econometric methods are focused on deriving best unbiased estimators dzyabura2018machine. In this paper, we are interested in both reaching good predictions and unbiased causal estimation. Yet, the adaptive nature of MAB problem complicates the causal inference of advertising effects. nie2018adaptively showed that estimates of arm-specific expected rewards in UCB and TS algorithms are biased downwards. This downward bias is due to that arms with random upward fluctuation are sampled more, while those arms with downward fluctuation are sampled less (hadad2021confidence). bibaut2021post presented that standard estimators no longer follow normal distribution asymptotically so that classic confidence intervals fail to provide correct coverage. To address this inference problem in online settings, chen2021statistical studied the consistency and asymptotic distribution of the online ordinary least square estimator under epsilon-greedy policy. We extend their approach to two stage least square estimation in online settings and contribute to the literature by providing the consistency and asymptotic normality of our estimator. Besides, lattimore2016causal studied the bandit problem on a causal graph and proposed new algorithms to learn good interventions in stochastic online settings. There are two significant differences between their work and ours. First, we focus on a single linear model of the features and rewards, while they studied causal graph of features and rewards. Second, they did not consider the endogeneity problem, which our work mainly contributes to.
This paper is also closely related to the stream of literature in instrumental variable methods for endogeneity problems. griliches1977estimating, hausman1983specification, angrist1995identification, and chen2005measurement provided theoretical analysis of instrumental variables in linear models. Different from the standard data analysis framework in offline settings, the endogeneity problem can be exacerbated during the dynamic interaction between data generation and data analysis in online settings li2021causal. This paper builds on existing instrumental variable methods in offline settings and considers the dynamic interaction by utilizing the CMAB framework. For these reasons, the paper contributes to the literature by combining both CMAB models and instrumental variable methods to improve the estimation of causal effect of ad exposure and hence achieve better performance of decision policies.
Lastly, this paper is related with the literature in RTB. choi2020online reviewed research work in RTB questions regarding both advertisers, like how to calculate the impression value, and publishers, like how to allocate impressions across advertisers. sayedi2018real used a game theory framework to study the effects of RTB on publisher' revenue, advertisers' profits as well as their strategies. balseiro2022dynamic studied an auction mechanism design to satisfy two properties including no positive transfers and periodic individual rationality, which can reach asymptotically first best for the platform. balseiro2015repeated examined the equilibrium in repeated auctions considering strategic responses of budget-constrained bidders and provided implications on auction mechanism design for publishers. In this paper, instead of addressing questions for publishers, we focus on the questions advertisers face in RTB. We aim to learn the optimal bidding price and the effect of an ad exposure through the algorithms we propose.
Let $T$ be the number of rounds and $K$ the number of arms in each round. In each round $t$, the learner observes a feature vector $x_{t,a}\in \mathbb{R}^d$, $a\in \{1,\cdots,K\}$, with $||x_{t,a}||_2\le L_x$, for each arm. We use the subscript $a$ to represent the $a^{th}$ arm from the $K$-arm set and $L_x$ to represent a constant upper bound for $||x_{t,a}||_2$. After observing the feature vectors, the learner selects an arm $a_t$ and receives a reward $y_{t,a}\in \mathbb{R}$, with $|y_{t,a}|\le L_y$ where $L_y$ is a constant upper bound for $|y_{t,a}|$. Under linear realizability assumption, we have $\mathbb{E}[y_{t,a}|x_{t,a}]=x'_{t,a}\beta_0$ for all $t$ and $a$, where $\beta_0\in \mathbb{R}^d$ is an unknown true coefficient vector. We specifically assume $y_{t,a}$ as the following.
where $e_{t,a}\in \mathbb{R}$ is a 1-subgaussian error term, s.t. $\mathbb{E}[e_{t,a}]=0$. We denote the cumulative distribution of $e_{t,a}$ as $\mathcal{P}_e$. Unlike traditional bandit algorithms, we have a twofold goal in this problem: (i) to estimate the main coefficient of interest $\beta_0$ (ii) to achieve the largest reward by selecting the optimal arm.
Standard Contextual Linear Bandit settings have $\mathbb{E}[e_{t,a}x_{t,a}]=0$, which implies that the error term is independent with the feature vector. However, this assumption can be violated in various cases such as when we have omitted variable in the error term, measurement error in the regressor, simultaneous equation estimation, and etc. Mathematically, when we have the following,
the endogeneity problem occurs. Ordinary Least Square (OLS) estimator for the coefficient of interest $\beta_0$ is inconsistent in endogenous settings. Econometrics literature uses Instrumental Variable (IV) method to address the endogeneity problem. A variable $z_{t,a}$ is a valid instrumental variable if it satisfies the following three conditions m2014introductory: (i) it is uncorrelated with the error term $e_{t,a}$, i.e. $\mathbb{E}[z_{t,a}e_{t,a}]=0$, (ii) it is correlated with the endogenous covariates $x_{t,a}$, (iii) it has no direct effect on the reward $y_{t,a}$. Consider a valid instrumental variable $z_{t,a}\in \mathbb{R}^k$, with $||z_{t,a}||_2\le L_z$ where $L_z$ is a constant upper bound for $||z_{t,a}||_2$. We assume $\mathbb{E}[z_{t,a}x'_{t,a}]\in \mathbb{R}^{k\times d}$ has full column rank $d$.\footnote{The assumption $\mathbb{E}[z_{t,a}x'_{t,a}]\in \mathbb{R}^{k\times d}$ has full column rank $d$ implies that $k\ge d$.} and the minimum eigenvalue of $\mathbb{E}[z_{t,a}z_{t,a}']$ is positive.
where $\Gamma_0\in \mathbb{R}^{k\times d}$ is an unknown true coefficient vector, each element in $u_{t,a}\in \mathbb{R}^{d}$ is a 1-subgaussian error term with mean zero and the independency condition $\mathbb{E}[z_{t,a}u'_{t,a}]=0$ is satisfied by construction. Notice that by plugging the equation of $x_{t,a}$ (Equation ((ref))) into Equation ((ref)), we have
where $v_{t,a}=\beta'_0u_{t,a}+e_{t,a}$. We can prove that each element of $v_{t,a}$ is $(||\beta_0||_2^2 +1)$-subgaussian (we provide the proof in Appendix B). We denote $\Gamma_0\beta_0$ as $\delta_0$ for the simplicity of analysis.
Two-Stage Least Squares (TSLS) is an instrumental variable method commonly used in offline settings to correct estimation bias in the endogeneity problem. Consider vector $Y\in \mathbb{R}^T$ with $y_{t,a}$ as its elements, matrix $X\in \mathbb{R}^{T\times d}$ with $x'_{t,a}$ as its rows, matrix $Z\in \mathbb{R}^{T\times k}$ with $z'_{t,a}$ as its rows, where $t\in \{1,\cdots, T\}$. We briefly illustrate TSLS estimation procedure in offline settings as the following: (i) First, regress the set of feature vectors $X$ on the set of instrumental variable vectors $Z$ using OLS method to obtain an estimated sample features $\hat{X}$; (ii) Then regress $Y$ on the estimated feature vectors $\hat{X}$ to obtain the estimator $\hat{\beta}_{\hat{X},Y}$ using OLS method again.
To facilitate further analysis on the TSLS estimator, we also define related OLS estimators as the following, where $\hat{\delta} = \hat{\Gamma} \hat{\beta}_{\hat{X},Y}$ (to see this equation, refer Appendix B for the proof).
It is known that TSLS estimator is consistent in offline settings. In this paper, we adopt the standard two-stage least square procedure to the online setting and demonstrate how one can use instrumental variables to address the issue of endogeneity in linear contextual bandits.
We aim to design an online decision-making algorithm that learns the coefficient of main interest $\beta_0$ so that we can maximize the total expected reward after pulling arms under the endogeneity problem. We define the total expected regret of an algorithm after $T$ rounds as
where $a_t^*=\arg\max_{a} \langle \Gamma'_0z_{t,a}, \beta_0 \rangle$ is the best arm at round $t$ according to the true coefficient vectors $\beta_0$ and $\Gamma_0$, and $a_t$ is the arm selected by the algorithm at round $t$.
We relist key assumptions in this paper as the following,
Assumption (ref) ensures that the $||\cdot||_2$ of instrumental variables, feature vectors, and the reward are bounded by positive constants. Notice that the $||\cdot||_{\infty}$ of a vector is smaller than the $||\cdot||_2$ of the vector, which implies that the $||\cdot||_{\infty}$ of the instrumental variables, features , and the reward are also upper bounded by these constants, $L_z$, $L_x$, and $L_y$ respectively. Assumption (ref) guarantees that, with high probability, the sample second moment $\sum_{s=1}^t z_{s,a}z_{s,a}'$ is non-singular so that the OLS estimators $\hat{\Gamma}$ and $\hat{\delta}$ exist. We need these assumptions to bound the total regret and the inference bias.
In this section, we propose the $\epsilon$-BanditIV Algorithm (Algorithm (ref)) by incorporating instrumental variables in online settings. The algorithm is based on existing linear bandit algorithms, especially the OFUL algorithm proposed by abbasi2011improved.
The $\epsilon$-BanditIV algorithm takes as input initial regularization parameters $\gamma_z, \gamma_x>0$, confidence set parameters $\{G_t\}_{t=1}^{\infty}$, $\{B_t\}_{t=1}^{\infty}$, as well as a sequence of non-increasing exploration parameters $\{\epsilon_t\}_{t=1}^{\infty}$. We will specify the confidence set parameters in Section (ref).
Estimation: The algorithm maintains four matrices $U_t, V_t, W_t, Q_t$ to calculate estimated parameters in each round as described in the pseudo code of Algorithm (ref). If the current time $t$ is after the first round, the algorithm utilizes past-choice-related instrumental variables $Z_t$ and past choices $X_t$ to estimate $\Gamma_0$ through OLS and obtain an estimated $X_t$, which is $\hat{X}_t$. Then, based on $\hat{X}_t$ and past observations of rewards $Y_t$, the algorithm estimates $\beta_0$ by OLS again. We denote the estimator for $\beta_0$, which is $\hat{\beta}_t$, in the $\epsilon$-BanditIV algorithm as the BanditIV estimator.
Confidence Sets: Following the Optimisim in the Face of Uncertainty principle (OFU), we need to maintain confidence sets for all unknown parameters in the model. As described in Section (ref), we have two unknown parameters, $\Gamma_0$ and $\beta_0$. Thus, we construct two confidence sets $C_{1,s}$, $C_{2,s}$, $s \in \{1,\cdots, T\}$ for the first and the second stage estimation respectively in each round. The idea for the confidence sets are to make the estimation optimistic with the conditions that "with high probability" the true coefficients are in the confidence sets and we can calculate the confidence sets from the past chosen arms $X_t$, related instrumental variables $Z_t$, and rewards $Y_t$.
Execution: In each round, we conduct a stochastic decision with probability $\epsilon_t$ for choosing a random arm and probability $1-\epsilon_t$ for choosing the estimated best arm. The estimated best arm generated by the algorithm is an arm $a_t$ which is related to an instrumental variable $z_t$ that can maximize the estimated reward jointly with a pair of optimistic estimates of two-stage coefficients in the confidence sets. To maximize the estimated reward, the algorithm chooses a pair of optimistic estimates $(\tilde{\Gamma}_t, \tilde{\beta}_t)=\arg\max_{\Gamma \in C_{1,t}\\ \beta \in C_{2,t}}(\max_{z\in \mathcal{Z}_t} \langle \Gamma'z, \beta \rangle)$ and then chooses an arm $a_t$ such that $a_t=\arg \max_{a\in \mathcal{A}_t} \langle \tilde{\Gamma}'_tz_a, \tilde{\beta}_t \rangle$, where we denote the arm set at time $t$ as $\mathcal{A}_t$. Equivalently, the estimated best arm $a_t$, is stated in Equation ((ref)). After an arm is chosen, we observe the reward $y_{t,a_t}$ as stated in Equation ((ref)).
Note that when $\epsilon_t=0$ for $t\in \{1,2\cdots,\infty\}$, the algorithm chooses the estimated best arm in each round. To simplify the analysis, we denote the algorithm when $\epsilon_t=0$ for $t\in \{1,2\cdots,\infty\}$ as BanditIV.
For the simplicity of notations, we omit the subscript $a$ of $z_{t,a}$, $x_{t,a}$, and $y_{t,a}$ from below. By $x_t$, we mean one arm chosen by the algorithm from the arm set $\mathcal{X}_{t}$ at time $t$; the variable $z_t$ is the instrumental variable related to $x_t$; the variable $y_t$ is the reward generated by choosing the arm $x_t$. By $x_t^*$, we mean the true optimal arm from the arm set $\mathcal{X}_{t}$ at time $t$; $z_t^*$ is the instrumental variable related to $x_t^*$.
In this section, we give upper bounds on the regret of the $\epsilon$-BanditIV algorithm as well as the BanditIV algorithm. The proofs can be found in Appendix A. We first show an $\tilde{\mathcal{O}}(k\sqrt{T}$) upper bound for the total expected regret with parameters of confidence set by Theorem (ref) and Corollary (ref). Then by Lemma (ref) and Lemma (ref), we present that the true coefficients are in the confidence sets with high probability and we also give accurate definitions for confidence set parameters.
abbasi2011improved proved an $\tilde{\mathcal{O}}(d\sqrt{T}$) upper bound for the expected regret of OFUL algorithm without considering the endogeneity problem. Taking the endogeneity problem into consideration, we can still keep an upper bound at the same level with their results by Theorem (ref).
By setting $\epsilon_t=0$, we can derive the following corollary directly,
Due to that we have two-stage estimators in the algorithm, we construct double confidence intervals for the estimators to guarantee the regret bound. In every round, the algorithm chooses estimates for $\Gamma_0$ and $\beta_0$ from the confidence sets as we describe in Section (ref). Lemmas (ref) and (ref)show that $\Gamma_0$ and $\beta_0$ with high probability in ellipsoids with center at $\hat{\Gamma}_t$ and $\hat{\beta}_t$ respectively, i.e. in the double confidence sets.
Due to the adaptive nature of multi-armed bandits, calculating confidence intervals is not straightforward as the collected data is no longer iid. In this section, we show asymptotic properties of the BanditIV estimator following chen2021statistical and bastani2020online. We first present the consistency of the online OLS estimator and the BanditIV estimator, then we demonstrate the normality of the BanditIV estimator. The proofs are presented in Appendix A.
Proposition (ref) states that both the OLS estimator based on the instrumental variable and the first stage OLS estimator are consistent if $t\epsilon_t^2\rightarrow \infty$ as $t\rightarrow \infty$. Based on this result, we derive the tail bound for the BanditIV estimator as the following.
Following from the Propositions (ref) and (ref), we obtain the consistency of the OLS estimators $\hat{\delta}_t$ and $\hat{\Gamma}_t$ and the BanditIV estimator $\hat{\beta}_t$ easily.
Based on above results, we can derive the normality of the BanditIV estimator by applying Slutsky Theorem. We also provide a consistent estimator for the variance of the normal distribution. The proof for the consistency of the variance estimator can be found in Appendix A.
Theorem (ref) provides a theoretical guarantee that the BanditIV estimator asymptotically follows a normal distribution with mean zero and variance $S$. We can see that this variance depends on the expectation of the error term $v_t$, which includes the errors in both first stage and the second stage. The variance also depends on the distribution of the instrumental variable, $\mathcal{P}_z$. Notice that, although we need the assumption about $\epsilon_t$ to guarantee the consistency of the estimator, the asymptotic variance of the BanditIV estimator does not depend on $\epsilon_t$.
To compute confidence intervals of our estimate of $\beta_0$ post running our bandits, we provide two ways as the following. As the first way, we use directly Theorem (ref). The data set is constructed as illustrated in Section (ref). We set all elements in $\Gamma_0$ and $\beta_0$ as $1$. We run 1000 trials in total. In each trial, we take the final estimation $\hat{\beta}$ from a pre-run $\epsilon$-BanditIV with 1000 rounds as the mean of the confidence interval and calculate the estimated standard deviation as the theorem provides to construct one confidence interval. Among the 1000 trials, for $95\%$ confidence intervals, we get $94.4\%$ coverage when we set $k=2$, $d=1$ and $94.6\%$ coverage when we set $k=1$, $d=1$, which are very close to the ideal.
As the second way, we use a re-randomization test similar to that of bojinov2020design and farias2022synthetically. For the estimate $\hat{\beta}$, we test the sharp null hypothesis that the $\beta_0=\tau$ for all $t$. The sharp null hypothesis implies that the new outcome is $y_t+\tau'(x^{H}_t-x_t)$ where $x^{H}_t$ is a newly pulled arm and $x_t$ is a pulled arm by our bandit algorithm.
We conduct exact tests by using the known assignment mechanism to simulate new assignment paths. Algorithm (ref) provides the details of how to implement it. In particular, we propose $\tau$ by a downward search method based on the estimate from the bandit algorithm. Under the sharp null hypothesis of $\beta_0=\tau$, a new arm assignment path $1:T$ leads to a sequence of observed outcomes $y_t+\tau'(x^{H}_t-x_t)$ for $t\in \{1,\cdots ,T\}$. To obtain a confidence interval, we invert a sequence of exact hypothesis tests to identify the region outside where the null hypothesis is violated at the prespecified significance level imbens2015causal, bojinov2020design.
Consistent with the setting illustrated in the first way, all of these experiments are run on synthetic data constructed as in Section (ref) and we consider two cases including $k=2$, $d=1$, and $k=1$, $d=1$. For each case, we run 50 trials. In each trial, we propose 20 hypotheses for $\beta_0$ based on the estimated coefficient of our main interest, $\hat{\beta}$ from a pre-run $\epsilon$-BanditIV and construct confidence intervals for all dimensions of $\beta_0$. For each hypothesis of $\beta_0$, we run the sharp null hypothesis test where we set $N_H$ as 200. We choose the significance level to be $\alpha=0.05$. Under $\epsilon$-greedy BanditIV, the coverage of the test is 96% when $k=2$, $d=1$ and 94% when $k=1$, $d=1$. We can see that, given the significance level as $0.05$, the coverage of the test is close to ideal. Thus, the re-randomization tests and corresponding confidence intervals reported here are adequate for inference of the main treatment effect.
In this section, we construct synthetic data to further validate our algorithm. Referring the simulation set up in bakhitov2021causal, we consider the model as follows, for $t=1,\cdots, T$,
Suppose that all elements of the instrument $Z_t \in \mathbb{R}^{k \times 1}$ are uniformly distributed on the support $[-3,3]$. The error term $e_t\in \mathbb{R}^{n_t \times d}$ is the confounder, where $n_t$ is the number of arms at time $t$ and all elements of $e_t$ follows $\mathbb{N}(0,1)$. The parameter $\rho \in \mathbb{R}^{d \times 1}$ measures the degree of endogeneity. A lower $\rho$ implies a less serious endogeneity issue. As an extreme example, when $\rho=0$, endogeneity disappears, which we can see from Equation ((ref)). The additional noise terms $u_t\in \mathbb{R}^{n_t \times d}$, and $\varepsilon_t\in \mathbb{R}^{n_t \times 1}$ are i.i.d. normally distributed. All elements of $u_t$ and $\varepsilon_t$ follow $\mathbb{N}(0,0.01)$ and $\mathbb{N}(0,1)$ respectively. WLOG, we set $n_t=50$, for $t=1,\cdots, T$ in this simulation.
We have two objectives in the simulation: (i) to achieve the maximum reward through selecting optimal arms (ii) to obtain an accurate estimation of the causal relation parameter $\beta_0$. We compare performance of our algorithm regarding the two objectives, with other existing algorithms including TS and OFUL under endogeneity. We run $T=2000$ time steps for each algorithm and observe the regret and estimation bias along the time. We use the true cumulative regret which excludes random error terms to measure the regret and $||\beta_0-\hat{\beta}_t||_2$ to measure the estimation bias. Figures (ref) and (ref) show the results where we consider various endogeneity degrees and dimensions of the instrumental variable. In Figure (ref), we set the dimension of the instrumental variable as $k=1$ which is equal to the dimension of endogenous variable $d=1$. When $k=d$, we have the same number of instrumental variables as that of endogenous variables and $\beta_0$ will be just identified. In Figure (ref), we set the dimension of the instrumental variable as $k=2$ which is larger then the dimension of endogenous variable $d=1$. When $k>d$, we have more instrumental variables than endogenous variables, which can cause overidentification. Across these two cases regarding the dimensions, we find quite robust results that our proposed algorithms outperform TS and OFUL both on regret and inference. This outperformance is more significant under higher endogeneity. In both Figures (ref) and (ref), the first, second, third row present results when $\rho=2, 1, 0.5$ respectively. We can see that BanditIV and $\epsilon$-{BanditIV} can achieve lower bias in inference than TS and OFUL and this difference become larger when the endogeneity degree increases. Also, BanditIV reaches lower expected regret than $\epsilon$-BanditIV, but $\epsilon$-BanditIV can obtain a less biased estimation.
RTB is a dominant auction mechanism for selling ad exposures in display markets. A consumer entering a publisher's website generates an ad impression opportunity for advertisers. An auction takes place for a single impression opportunity. In RTB, an advertiser makes buying decision in the auction immediately after the consumer arrives on the publisher's website. Buying decisions of impressions involve programmatic automation. The advertiser's ad is served to the consumer only if the advertiser wins the auction of the impression.
An advertiser is able to make buying decisions based on impression-specific information, like the width, height and visibility of an ad slot, and the user's profile. Therefore, we can model the advertiser's buying problem as a linear bandit problem. The objective of this problem is twofold: first, to measure the marginal value of the ad exposure; second, to achieve the largest profit through optimizing the bidding price. Notice that the advertiser has to bid in an auction to win the impression opportunity. Either overbidding or underbidding may bring significant costs to the advertiser. The advertiser can obtain a higher winning probability with a very high bid but may not cover the paying price with the profit of ad exposure. On the contrary, the advertiser will be less likely to win with a low bid.
Now, we illustrate the model (see Equation ((ref))) and explain the potential endogeneity issue. We model the advertiser's revenue ($\Tilde{y}_t$) from winning the auction as some base revenue ($\beta_0$) plus the revenue generated from the ad exposure ($\beta_1$). The advertiser profit ($y_t$) is given by the advertiser's revenue minus the paying price in case the advertiser wins the auction ($\mathbb{I}\{B_{CP,t}\le b_t\}$). For our setting, we assume a second-price auction. The base revenue is a part of the revenue the advertiser will always get no matter whether the advertiser wins the auction or not. We use $\beta_0$ to represent the expected base revenue. The marginal profit of the ad exposure, $\beta_1$, is our main coefficient of interest and we also call it as the treatment effect i.e., the effect of ad exposures on revenue. We use an indicator function, $\mathbb{I}\{B_{CP,t} \le b_t\}$, to present whether the advertiser wins the auction or not, where $B_{CP,t}$ is the highest bidding price among the advertiser's competitors at time $t$ and $b_t$ is the advertiser's bidding price at time $t$. Notice that $B_{CP,t}$ is also the advertiser's paying price in the second-price auction. We use $\eta_t$ to denote the unobserved demand shocks at time $t$.
Note that the above specification suffers from the endogeneity problem, i.e. the covariate $\mathbb{I}\{B_{CP,t} \le b_t\}$ can be correlated with the unobserved error term $\eta_t$. The advertiser cannot randomize the ad exposure because the advertiser does not know others' bids, and the result of the auction cannot be controlled by the advertiser; Thus, the unobserved demand shocks could be correlated with $B_{CP,t}$ and create a potential endogeneity issue. The unobservables here could be some common shock in the market, which affects the bidding prices in the market but are not observable in the data in the error term $\eta_t$. Extant literature (johnson2017ghost) has characterized this inherent endogeneity in RTB settings and discusses how unobserved consumer taste shocks affect both consumer demand and advertisers' bidding behavior.
To make the analysis clearer, we reformulate the error term in the model as Equation ((ref)), where we rewrite $\eta_t$ as the sum of two errors, $\delta_t$ and $\varepsilon_t$. We assume $\mathbb{I}\{B_{CP,t} \le b_t\}$ is correlated with the first error term, $\delta_t$, while uncorrelated with the second error term, $\varepsilon_t$. The parameter $\rho$ indicates the degree of endogeneity. Larger $\rho$ implies higher endogeneity.
To correct the endogeneity-generated bias of estimation for $\beta_1$, we can utilize instrumental variable methods. A valid instrumental variable $\nu_t$ for $\mathbb{I}\{B_{CP,t} \le b_t\}$ should satisfy the following conditions: (i) $\mathbb{E}[\nu_t\eta_t]=0$, (ii) $\nu_t$ affects $\mathbb{I}\{B_{CP,t} \le b_t\}$, (iii) $\nu_t$ has no direct effect on $y_t$. One example of potential exogenous data that can be used as instrument variables in RTB auctions could be -- the intensity of political ads (sinkinson2019ask) at a given time. Political ads have a displacement effect on commercial ads (sinkinson2019ask). Yet, political ads don't have a direct effect on the revenue generated from commercial ads. Therefore, the variation of political ads can represent the exogenous variation in the advertiser winning an auction and serve as a potential instrument in the RTB problem. For our exercise, we artificially simulate such an instrument and assume a linear relationship between $\mathbb{I}\{B_{CP,t} \le b_t\}$ and the instrument ($\nu_t$). {
To evaluate the performance of our proposed $\epsilon$-BanditIV algorithm on this RTB problem, we use real data from iPinYou liao2014ipinyou. The iPinYou RTB data set is publicly available and includes logs of ad biddings, impressions, clicks, and final conversions. We use the impression data for one product category, Telecom. Impression slot characteristics, bidding price, and paying price are main variables we use in this section.
An advertiser has 2000 time periods to run in total. In each time period, the advertiser is shown an impression opportunity. The advertiser observes the characters of the impression slot. The advertiser has to estimate competitors' bidding prices and decide a bidding price to participate in the auction of the impression. We assume the advertiser considers a set of $R$ arms $r=1,\cdots, R$, each of which associated with a bidding price, $b_{r}$. WLOG, we let $b_{1}<b_{2}<\ldots<b_{R}$ for all $x$. We use the same set of arms for all contexts for simplicity; this setup can trivially be adjusted to accommodate context-specific arms and context-specific number of arms. After the advertiser bids with the chosen arm, $b_r$, the advertiser can observe whether wins or not, paying price for the auction and the realized profit.
Applying the $\epsilon$-BanditIV algorithm to the RTB problem, we estimate the treatment effect of ad exposure based on past records of impression characteristics, bidding prices, instrumental variables, whether win or not, and rewards. We choose the bidding price which maximizes the estimated profit jointly with optimistic estimates of coefficients within the double confidence sets of two-stage coefficients.
Figures (ref), (ref) and (ref) show the results of regret variation and estimation bias for four algorithms including BanditIV, $\epsilon$-{BanditIV}, TS and OFUL on the RTB data. We compare algorithm performance under endogeneity case when the endogeneity degree changes. We find that BanditIV and $\epsilon$-BanditIV significantly outperform other two classic algorithms both on regret and inference, especially under higher endogeneity cases. In Figure (ref) and (ref), at round $2000$, TS and OFUL still have larger than 3 times the norm difference of the $\epsilon$-BanditIV or BanditIV; in Figure (ref), at round $2000$, TS and OFUL have around than 2.7 times the norm difference of the $\epsilon$-BanditIV or BanditIV. Regarding the regret variation, there are slight differences between the performances of TS and OFUL, or between BanditIV and $\epsilon$-{BanditIV}. But due to the large magnitude of numbers, we can barely see the differences. To conclude, our proposed algorithms consistently outperform state-of-art algorithms like TS and OFUL, in the aspects of regret and inference.
In this paper, we study the endogeneity problem in online decision-making settings where we formulate the decision-making process as a contextual linear bandit model. We discuss how many economic settings can be characterized by endogeneity and extant methods can lead to estimation bias and sub-optimal decisions. To correct the bias and optimize online decisions, we propose the $\epsilon$-BanditIV algorithm by utilizing both existing linear bandit algorithms and instrumental variables. We present the theoretical properties of our algorithm. We first show an upper bound for the total expected regret, and then show the consistency, asymptotic normality of the estimator in the algorithm. On the applied side, we conduct extensive simulations on synthetic data. We find that the $\epsilon$-BanditIV algorithm outperforms several benchmark linear bandit algorithms when the endogeneity problem occurs. Finally, we demonstrate by using data from the real-time bidding (RTB) system to demonstrate how $\epsilon$-BanditIV can be effective in estimating the causal impact of advertising while maintaining close to oracle regret.