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.
85,001 characters · 12 sections · 40 citation commands
Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learning
Randomized experiments that contrast several treatments to one another (and possibly to a control group) can be used not just to understand the average differences between treatment arms but also to inform the design of targeted treatment assignment policies - a task we refer to as “policy learning.” For example, if the problem concerns which drug to give to a patient, policy learning entails estimating a rule that assigns the best drug to patients given their characteristics. When an experiment has more than a few arms, however, it can be expensive or time consuming to gather enough data to accurately estimate the performance of each treatment arm for subgroups of the population. In this setting, adaptive experiments can be used to focus data collection on promising treatment arms for each set of participant characteristics. Thus, the researcher may learn a more effective targeted treatment assignment policy (or learn a good policy more quickly). Experimental subjects simultaneously benefit as they are more likely to be exposed to treatments that work for them during the experiment. Assigning treatments in this way reduces ethical concerns related to assigning participants to clearly inferior treatment arms.
However, adaptive experiments also have several potential downsides. For example, treatment arms might be discarded too quickly. Further, it may be difficult at the end of the experiment to accurately compare alternative (counterfactual) targeted treatment assignment policies if some arms are assigned with low probability in some regions of the participant characteristic space. Indeed, adaptive experimentation where treatment assignment varies with participant characteristics creates just the types of problems for estimation (assignment probabilities that vary with characteristics and may be very low) that a large literature on estimating treatment effects with observational data attempts to address imbens2015causal. Because learning a good policy requires evaluating a variety of alternative policies that may not have much overlap with the policies used to collect data (“off-policy evaluation”), adaptive data collection can increase the chance of mistakes in policy learning kitagawa2018should, athey2021policy, zhou2018offline. Adaptive data collection can also raise challenges for hypothesis testing after the experiment, as discussed in, e.g., hadad2021confidence, zhan2021off, and zhan2021policy.
In this paper, we consider the problem of designing an adaptive experiment with two goals. The first goal is to use the data from the experiment to design an effective targeted treatment assignment rule at the end of the experiment. Our second goal is to avoid assigning observations to suboptimal treatment arms during the experiment, and in particular, to target treatment assignments to individuals on the basis of their observed characteristics (their “contexts”). This type of adaptive experiment is known as a “contextual bandit.” In our study, this implies minimizing assignment to proposed charities for participants identified to be unlikely to respond well to them. This goal is often important in settings where the treatments make a big difference to participants. This consideration is substantively less important in our application. Another reason this goal can be important is because there is an opportunity cost in making a solicitation due to limited attention as well as the potential opportunity cost of the space on a web page where a donation is solicited. An objective in this paper is to illustrate the trade-off between the goal of maximizing outcomes for the participants in the experiment and our first goal of policy learning.
We apply our proposed model in an experiment where the treatment is the choice of which charity to show to a participant, and the outcome is how participants felt about making a donation to the selected charity (a hypothetical proxy for how much they would donate). In our experiment, we gathered information about participant characteristics from a set of survey questions. Then, we used those characteristics to determine which treatment, or charity, to show the participant. We find that when targeting is not possible, Greenpeace is the optimal charity to recommend to individuals. When targeting is possible, the policy selects Greenpeace for many participants and selects more polarizing charities for specific subgroups. However, even when targeting is possible, it is difficult to find a subgroup and a charity that strongly dominates Greenpeace - other than the group who feels strongly about the right to bear arms for whom the National Rifle Association (NRA) is more appealing. Targeting based on identification of participants being liberal versus conservative has relatively modest benefits. Assigning Planned Parenthood instead of Greenpeace to liberals increases their average outcome by 7.2%, and assigning NRA instead of Greenpeace to conservatives increases their average outcome by 2.6% (See Table (ref)). We used the data we collected to create semi-synthetic data sets for simulation studies. We used these data sets to establish that, in our setting, the approach of running a contextual bandit algorithm is expected to lead to a slightly (about 1%) better learned policy than collecting data uniformly using a standard randomized controlled trial, while at the same time substantially improving the experiment's outcomes.
Our paper is one of a small number (e.g., li2010contextual and bastani2021efficient) that has conducted a contextual bandit in practice and analyzed its performance relative to alternatives (Section (ref) reviews the literature). The relative lack of empirical applications of this type contrasts with the massive applied literature that estimates causal effects of treatments using observational data. When comparing estimation methods, a single data set can be used to compare a variety of methods. In contrast, contextual bandit algorithms are algorithms that guide data collection. They require a particular arm to be used for a particular covariate vector (context), so that it is not straightforward to reanalyze historically collected data to simulate the performance of a bandit. Given that running survey experiments on popular platforms such as Mechanical Turk or Lucid can cost $\$1$ or more per subject, it is difficult to run many parallel experiments comparing algorithms with sufficient sample size. Thus, papers comparing methods have typically used some form of simulation or semi-synthetic data.
We address the challenge of comparing contextual bandit methods and evaluating the trade-offs in their performance for different objectives by combining several rounds of real-world data collection with semi-synthetic simulations. We proceed in three steps: First, we run a pilot and use it to create semi-synthetic data for comparing and selecting among algorithms; Second, we run a single contextual bandit algorithm on real subjects using the selected algorithm; Third, we conduct a second simulation exercise using the adaptively-collected data to update the parameters used to generate semi-synthetic data.
To describe the problem of adaptive experimental design more precisely, some basic notation is helpful. Each observation $t$ is represented by $(X_t, W_t, Y_t)$, where $X_t \in \mathbb{R}^{p}$ is the context, a vector of observed covariates (demographic characteristics, measures of political affiliation, etc.); $W_t \in [K]$ \footnote{$[K]$ denotes the set $\{1,2, \cdots, K\}$.} is the index of the treatment arm assigned to that participant; and $Y_t$ is the observed outcome. We let $Y_t(1), Y_t(2), \cdots, Y_t(K)$ denote potential outcomes under treatment arm $\{1,2,\cdots, K\}$, so that $Y_t = Y_t(W_t)$.
The first goal described above is policy learning manski2004statistical, stoye2009minimax, kitagawa2018should, athey2021policy. A policy is a deterministic treatment rule, formalized as a function from contexts to treatments $\pi: \mathbb{R}^{p} \mapsto [K]$. In the policy learning problem, we are given some previously collected data (following any arbitrary assignment rule) and a set of available policies $\Pi$. Our objective is to approximate the policy $\pi^*$ that maximizes the expected outcome, i.e., $$\pi^* := \arg\max_{\pi \in \Pi} \mathbb{E}[Y_t(\pi(X_t))].$$ The set of available policies is often restricted in some way, such as belonging to the set of decision-tree policies zhou2018offline or satisfying some cost-benefit threshold sun2021empirical. We can also express the goal as selecting a policy $\hat\pi$ based on available data that minimizes expected simple regret, or the expected loss from using the learned policy in the future: $$R(\hat\pi)=\mathbb{E}[Y_t(\pi^*(X_t))]-\mathbb{E}[Y_t(\hat\pi(X_t))].$$
The second goal is often called cumulative regret minimization. “Cumulative regret” refers to the gap in expected reward attained by the treatment $W_t$ that was assigned to a participant (e.g., in an adaptive experiment) and the one that would have been attained under the optimal policy $\pi^*$, i.e., $\mathbb{E}[Y_t(\pi^*(X_t))] - \mathbb{E}[Y_t(W_t)]$.\footnote{Some authors call this expected regret and reserve the term regret to mean the random variable $Y_t(\pi^*(X_t)) - Y_t(W_t)$.} Of course, minimizing cumulative regret also implies maximizing rewards accrued during the experiment. There is a large literature in adaptive experimental design that deals with the cumulative regret minimization problem lattimore2020bandit. Such algorithms, referred to as contextual bandit algorithms, devise optimal strategies to minimize the time spent acting somewhat at random (“exploration”) to quickly learn which treatments work best and focus assignment on those treatments (“exploitation”). Often these strategies are probabilistic: Given a vector of covariates $x_t$, the algorithm outputs a vector of probabilities from which the arm identity is drawn.
At first glance, the two aforementioned goals might seem aligned. To learn which policies work, the researcher needs “enough” data about the performance of each arm across the covariate space (i.e., for different types of participants), but, at the same time, it seems wasteful to collect “too much” data on arms that are clearly suboptimal. Since suboptimal arms are disfavored by a cumulative regret minimization algorithm, one could hypothesize that such an algorithm would also generate data that would be amenable for policy learning. And indeed, these forces can lead algorithms focused on cumulative regret to also improve on nonadaptive experiments in terms of policy learning (even2006action,kasy2021adaptive).
However, it turns out that the two goals are partially in conflict. As we demonstrate using simulations designed based on our pilot data, the true value of the best policies estimated from adaptive data collection is often lower than that of the best policies estimated from nonadaptive data collection, such as through a randomized control trial with uniform assignment probabilities. We hypothesize that the problem is that standard bandit algorithms are overly aggressive, dropping arms too quickly for a policy learning method to do a good job at approximating the optimal policy.
The above issue motivates us to propose an algorithm based on simple heuristics that align both goals - achieving high quality policy learning while also minimizing regret during the experiment. We begin with a cumulative regret minimization algorithm but modify it in two ways to achieve both of our goals. First, we impose a lower bound on assignment probabilities suggested by the algorithm. This lower bound decays slowly, so that no arm is discarded too quickly. Second, when learning a policy at the end of the adaptive experiment, we compute a score that tracks how much each arm is favored by the cumulative regret minimization algorithm. We then learn a policy using only the arms that are most favored. We show that this heuristic is able to learn a policy whose value on average is at least as good as the one we would have learned by collecting data non-adaptively (i.e., via a randomized controlled trial with uniform assignment probabilities) while still yielding substantial reduction in regret accrued during the experiment.
We compare five distinct contextual bandit algorithms in our simulation study to evaluate the trade-offs between cumulative and simple regret (i.e., in-experiment outcomes versus policy learning) in these commonly-used algorithms. The first is Uniform, where all treatments are assigned with equal probability, as in a classic randomized controlled trial. Next, we consider three different bandit algorithms proposed in the literature. A classic algorithm is Linear Thompson sampling, where at each stage, a regression is used to fit an outcome model as a function of the treatment arm and participant characteristics. This model in turn is used to construct, conditional on a vector of participant characteristics, the posterior probability that arm w is best. Arms are assigned to participants according to the posterior probability that the arm is optimal. We also consider two modifications of this algorithm that have been shown theoretically to optimize for policy learning: Exploration Sampling kasy2021adaptive and Top-Two Thompson Sampling russo2016simple. We show that in the empirical setting we study, the theoretical promise of these algorithms is not born out in practice; they do not in fact improve over Uniform assignment for policy learning. To address the problems we find with these algorithms, we propose a final algorithm we call TreeBagging, which is inspired by bagging algorithms studied by, e.g., agarwal2014taming. With TreeBagging, assignment probabilities are determined by aggregating the results of a procedure that repeatedly estimates tree-based treatment assignment policies learned on training data sets drawn with replacement from previous observations. We incorporate the heuristic modification discussed above (a decaying lower bound on assignment probabilities, combined with selection of arms for policy learning) to TreeBagging.
The rest of the paper is structured as follows: Section (ref) reviews related literature. Section (ref) describes the research design. Section (ref) describes the main experiment and the pilot experiments conducted to select the bandit algorithm most appropriate for our setting and objective, including the Treebagging algorithm we propose in detail. Section (ref) demonstrates the performance of the Treebagging algorithm through simulations and compares adaptive and nonadaptive experiments. Section (ref) describes our survey design, while Section (ref) explains how our experiments were implemented. Section (ref) shows the results of a new experiment conducted on recruited subjects in which we deployed the Treebagging algorithm. Section (ref) compares bandit performance with that of uniform randomization. Section (ref) concludes. Additional figures and tables, as well as mathematical details, are provided in the Appendix.
Our work falls within a small but growing literature on adaptive experimental design that considers the goal of policy learning (equivalently, “minimizing simple regret”). Several algorithms have been proposed and analyzed theoretically. For example, for the problem without contexts, kasy2021adaptive propose a modification of Thompson sampling called “exploration sampling,” which assigns treatments in proportion to the posterior probability that an arm is optimal; this modification slows down learning relative to Thompson sampling and performs well at policy learning. deshmukh2018simple propose a “contextual gap” algorithm, where the assignment probability for a given arm and context is inversely proportional to the gap between the estimated best possible payoff for the context and the estimated payoff for a given arm. Theoretical performance and simulations indicate the algorithm shows promise at policy learning. chambaz2017targeted consider a setting in which there are covariates but only two arms and propose a sequential experiment design for nonparametric policy learning; their method is based on assigning observations to treatment or control depending on how certain one is of a positive treatment effect. The authors show that under specific exploration regimes, they can learn an optimal policy with sufficient data. The TreeBagging algorithm we propose in this paper attempts to explicitly balance the two objectives of policy learning and cumulative regret.
The best arm identification literature studies a problem related to the one we address in this paper. This literature aims to identify the best treatment arm in a setting with no covariates as quickly as possible or with the highest possible certainty audibert2010best, jamieson2014best, russo2016simple, kasy2021adaptive,lu2021variance. Relaxing the requirement of finding the best arm to an approximate requirement, the $(\epsilon,\delta)$-PAC best arm identification problem that considers the problem of identifying, with probability at least $1-\delta$, an arm that is within $\epsilon$ of being optimal, with as few samples as possible even2006action,hassidim2020optimal. Another related line of work studies best arm identification in a multi-armed bandit setting that places additional structure on the problem. This setting assumes that the expected reward of arms (as a function of arm features) lies in a known function class. The best arm identification in this setting exploits this additional structure with bounds that depend on the complexity of the reward model class soare2014best,xu2018fully,jedra2020optimal,kazerouni2021best.
The practical limitations of algorithms designed for policy learning have not been fully explored in the literature. In particular, we are not aware of research documenting findings analogous to our result that in a range of outcome models consistent with our pilot data, uniform (nonadaptive) sampling performs better than algorithms that were explicitly designed for policy learning, though the fact that uniform sampling is in general a strong baseline is suggested by the theoretical results in bubeck2009pure. The findings in this paper suggest that there is still room for improvement in algorithms designed for policy learning, and also for algorithms that optimize for regret in a contextual bandit settings; see krishnamurthy2021adapting, krishnamurthy2021optimal, carranza2022flexible, simchi2022bypassing for some recent discussions of challenges for standard algorithms that arise when the functional form of the mapping between individual characteristics and outcomes is unknown.
Although a full theoretical analysis is beyond the scope of this paper, here we show that a few modifications of standard algorithms improve performance. In particular, we incorporate lower bounds on assignment probabilities in our proposed TreeBagging algorithm. The idea of modifying a cumulative regret minimization algorithm by imposing a lower bound on assignment probabilities to attain better policy learning is motivated by proposals such as the Tempered Thompson algorithm described in caria2020adaptive.
Our paper also contributes to a small but growing literature using contextual bandits in real-world applications. Bandit algorithms have been used in a wide range of applications including mobile health interventions rabbi2019optimizing, clinical trial design durand2018contextual, news article recommendation li2010contextual, and public health interventions mate2021field. However, there are only a handful of studies that apply contextual bandits to real-world participants (rather than in simulations) and test hypotheses about the impact of the final policy. bastani2021efficient show the usefulness of adaptive design based on real-time data in informing border testing policies during the COVID-19 pandemic in Greece by comparing the value of the targeted policy with those of counterfactual policies. yang2020targeting study optimal targeted discounts for The Boston Globe subscribers and implemented their learned targeted policy with bootstrap Thompson sampling in a second experiment. offer2021optimal study effective interventions to combat the spread of misinformation about COVID-19 on social media in sub-Saharan Africa by learning and evaluating a targeted policy. caria2020adaptive propose the Tempered Thompson algorithm, which balances the goals of maximizing the precision of treatment effects estimates and maximizing the welfare of experiment participants; they implemented the method to study labor market policies in Jordan.
From a substantive perspective, our paper estimates a targeted treatment assignment policy for targeting specific charities on the basis of participant characteristics. We are not aware of other papers addressing this type of objective in charitable giving. However, the targeting policies we learn are not particularly surprising, and indeed the charities (e.g., the NRA) were selected to ensure that there would be a strong benefit to targeting. Nonetheless, the magnitudes of the treatment effects we estimate and how they differ by subgroup may be useful to charitable giving platforms and organizations. The broad problem of encouraging giving has been studied from different angles in economics and other social sciences. See andreoni2006philanthropy, list2011market and andreoni2013charitable for a summary on general facts about charitable giving and a review of theoretical and empirical research within public economics.
Table (ref) provides an overview of the overall research design, including two pilots, a simulation study used to select tuning parameters for the adaptive experiment, the two phases of the main experiment, and a final simulation study conducted using the data from the main experiment which revisits questions about the benefits of adaptivity.
For the Pilots and the Main Experiment, we implemented survey experiments using recruited subjects (Mechanical Turk for the pilots, and Lucid for the Main Experiment). In each case, the survey experiment consisted of three sections. In the first section, participants answered questions about general demographic characteristics, political affiliation, and media consumption. In the second section, participants were shown a charity logo and a paragraph of information about it. They were asked to rank, on a scale from -10 to 10, “how would people like you feel if we donated one thousand dollars to the following charity.”\footnote{This framing of the question was designed to measure participants' preferences for charities, given budget constraints and the need to avoid deception.} The charity shown to the participant was selected uniformly at random from a list of eight charities: National Rifle Association (NRA), the American Israel Public Affairs Committee (AIPAC), Greenpeace, Planned Parenthood Federation of America, the Black Lives Matter movement (BLM), the Chan Zuckerberg Initiative (CZI), People for the Ethical Treatment of Animals (PETA), and the Clinton Foundation. The display contained the charity's logo and a description (from the organization's Wikipedia page).
The questions regarding participant characteristics were chosen to capture features hypothesized to influence preferences for different charities. The end goal was an experiment where targeted treatment assignment would result in higher average outcomes than a policy where all individuals were exposed to the same charity.
Before the main experiment, we conducted two pilot experiments to finalize our experimental design. The first pilot experiment, which was conducted in March of 2020, was a randomized experiment in which the participants were recruited via Amazon Mechanical Turk and were randomly assigned to one of the treatments with equal probability. We call this experiment the Pilot 1 experiment (n=2,463). The second pilot experiment, which was conducted in August of 2021, was an adaptive experiment with a learning and evaluation phase. We call this experiment the Pilot 2 experiment (n=3,064). In Pilot 2, the participants were recruited via Lucid. More survey details and the analyses of the pilot experiments can be found in Appendices (ref) and (ref).
In Pilots 1 and 2, we included the Salvation Army as one of the charities, bringing the total number of treatments (charities) to nine. Pilot 1 data revealed that the Salvation Army is favored by both conservatives and liberals (see Tables (ref) and (ref) in Appendix (ref)), and it was selected as the best fixed policy in Pilot 2 (see Table (ref) in Appendix (ref)). The contextual policies of maximal depth 1 to 3 that are learned in Pilot 2 are not statistically distinguishable from assigning everyone to the Salvation Army (also in Table (ref) in Appendix (ref)). As different groups showed strong preferences for the Salvation Army, we excluded the Salvation Army as a treatment in the main experiment in order to illustrate gains from personalizing treatments when there is an underlying heterogeneity in optimal treatment.
Our main experiment has two phases: the learning phase and the evaluation phase. The goal of the learning phase is to learn a treatment assignment policy, balancing exploration and exploitation with both cumulative regret and policy learning. Participants are recruited in batches during this phase, with the treatment assignment probabilities in each batch changing based on the results of the previous batch. In this experiment, the assignment probabilities for each batch are determined using the TreeBagging algorithm we detail in the next subsection.
At the end of the learning phase, we use the collected data from all batches to estimate two different types of policies. The first is the best non-contextual policy $\hat{\pi}^{\text{N}}$; that is, the best single treatment arm if we had to assign the same treatment arm to all participants. The second estimated policy is a contextual (tree) policy for treatment assignment $\hat{\pi}^{\text{C}}$, where subgroups can be assigned different treatments based on a decision tree that forks according to a participant's covariates.
The primary goal of the evaluation phase is to provide accurate estimates of the policies learned at the end of the learning phase. In particular, we examine whether the estimated contextual (tree) policy (personalized treatment assignment) is better than the estimated non-contextual policy (assignment to the best single treatment).
During the evaluation phase, we collect data non-adaptively (but also not uniformly) using the following procedure. With probability $\epsilon$, which we set to $\epsilon=0.3$, treatment arms are uniformly randomly assigned; with probability $(1-\epsilon)/2$, we assign arms according to the learned tree policy $\hat{\pi}^{\text{C}}$; and with probability $(1-\epsilon)/2$, we assign arms according to the learned non-contextual policy $\hat{\pi}^{\text{N}}$. The uniform sampling with probability $\epsilon$ is to gather data for additional analyses after the experiment.
As we discuss further below, simulations based on pilot data showed poor performance for standard learning algorithms, and so we designed a new algorithm, referred to as the TreeBagging Algorithm, that performed better.\footnote{See, for example, krishnamurthy2021adapting, krishnamurthy2021optimal, carranza2022flexible, simchi2022bypassing for recent discussions of the challenges with selecting functional forms in contextual bandits, as well as proposals for algorithms that may perform better.} In the learning phase, we compute an assignment probability function for each batch according to a standard bagging algorithm agarwal2014taming to which we make two changes. We first describe a bagging algorithm generally, then detail the changes.
In essence, a bagging algorithm, or bootstrap aggregating, entails drawing samples of observations with replacement. Specifically, at the beginning of a new batch, we estimate a sequence of policies $\hat{\pi}^{(s)}(x)$ for $s \in [S]$ batches (we set $S=50$), where $x_t \in \mathbb{R}^{p}$ are participant covariates. Each policy in $S$ is fit by sampling with replacement from previous batches' data.\footnote{The first batch uses uniform random assignment.} Then, for each value of $x_t$ observed in the new batch, we compute tentative assignment probabilities for each arm $w_t$ according to the proportion of fitted policies in the ensemble of policies to which observations with a value of $x$ were assigned. Letting $\tilde{e}_t(x_t, w_t)$ denote the assignment probabilities suggested by the algorithm for participant $t$,
In terms of obtaining high rewards during the experiment (i.e., cumulative regret minimization), the bagging algorithm described above often performs similarly to other optimal bandit algorithms bietti2018contextual. However, as we demonstrate in the next section, when we use data collected via this heuristic to learn a policy (i.e., simple regret minimization), we often end up with a policy whose value is relatively low (i.e., the approach is not successful at identifying the best policy assignment rule, which is one of our stated goals). In fact, we are often better off collecting data by assigning arms uniformly at random.
We propose two adjustments to this bagging algorithm. First, our simulations suggest that we can often obtain a higher-value policy and reduce the likelihood of successful treatment arms being discarded by imposing a decaying lower bound $f(t) := t^{-\alpha}/K \: (\alpha > 0, K > 0)$ on the assignment probabilities above:
where $c > 0$ is a number chosen so that all probabilities sum to one. When a new batch arrives, the values of $ f(t), \tilde{e}_t(x, w)$ and $c$ in (ref) are recomputed.
The second adjustment occurs at the end of the learning phase, when we use the data collected thus far to learn a contextual tree policy. To promote overlap between the data collected and the learned policy, we drop arms that are not promising. We choose which arms to drop by assigning the following “frequency score” that shows how often a treatment arm is assigned:
where $T_{\text{learn}}$ is the length of the learning batch, and $\pi_B^{(s)}$ are the policies in the bagging ensemble during the last learning phase batch. We order arms according to their score (ref) in descending order and select only the top $k$ arms. Our default value is $k=4$, and our experiment has eight arms (charities), so half of all arms are selected.
Once we have selected the top arms, we use the subset of data assigned to these arms to compute Augmented Inverse Propensity Weighting scores (AIPW; see Appendix (ref)) for each observation and estimate a tree policy, following athey2021policy. The tree depth (i.e., the highest number of nodes from the root of the tree to the bottommost tree leaf) is chosen via cross-validation. We fit tree policies of depths 1 and 2 on the first 80% of the data (training data) and then evaluate these policies on the remaining 20% of the data (test data). We select the tree depth that yields the highest estimated value in the test data. Finally, we refit a policy with the selected depth using the entire data set (training plus test data). This final policy is denoted by $\hat{\pi}^{\text{C}}$. Figure (ref) in Section (ref) illustrates a learned contextual policy tree.
This section outlines the simulations undertaken to determine our chosen algorithm and the parameter values in Table (ref) that were used in the main experiment. Our choices aim to balance several objectives: high per-period value obtained during the experiment (low cumulative regret), high policy value for the policy estimated at the end of the experiment (policy learning), and accurate estimates of the benefit of adaptive experimentation.
\paragraph{Simulation design} We use the data from Pilot 2 for the simulations, which we refer to as “pilot data” throughout this section for simplicity. To generate contexts, we draw with replacement from pilot data. To generate outcomes, we proceed as follows. First, we draw a sample with replacement from the pilot data. Next, we fit an ordinal classification model to predict the probability that a participant will choose each response level, given contexts (e.g., age, gender and political leaning) and treatments (charities).\footnote{The model used here is based on the penalized logistic regression generalization for ordinal outcomes described in rennie2005loss and implemented in the Python package mord.} The set of explanatory variables included covariates (and their squares), treatments, and interactions between covariates and dummified treatments. The regularization parameter used when fitting the model above (i.e., the factor multiplying the sum of squares of coefficients in the regularized regression) impacts the heterogeneity in the data and is chosen randomly from a set of prespecified parameters $\{10,50,100,500\}$ ranging from low to high.\footnote{Higher regularization parameters induce lower heterogeneity in our data-generating process. We consider fairly high regularization parameters to allow for data-generating processes that are relatively pessimistic in how much heterogeneity is induced. }
\paragraph{Algorithms} We consider different treatment assignment schemes. (i) Uniform, in which all treatments are assigned with equal probability, i.e., $e_t(x, w) \equiv 1/K$; (ii) TreeBagging, following the explanation in the previous section; (iii) Linear Thompson sampling, in which we maintain an approximate posterior probability that each arm is optimal conditional on contexts, based on a linear model of the outcome, and assign treatments roughly according to this posterior. That is, if according to our model, the Bayesian posterior probability that arm $w$ is the best is $x\%$ for observation $t$, then we assign that arm $w$ with $x\%$ probability; \textit{(iv)} \emph{Exploration Sampling}, an Exploration Sampling variant of Algorithm (iii); \textit{(v)} \emph{Top-Two Thompson Sampling}, a Top-Two Thompson Sampling variant of Algorithm (iii). Algorithms (ii) and (iii) are formally described in Appendix (ref). Table (ref) describes default values of tuning parameters associated with these algorithms.
Tables (ref) and (ref) compare simulation results across algorithms. For TreeBagging, Table (ref) shows that the learned policy is at least as good as the one learned when collecting data through uniform randomization, and, in fact, it shows improvement by a modest margin. Table (ref) shows that, indeed, regret decreases (by around 20%) with TreeBagging as compared to Uniform.
Figure (ref) shows the value of the learned policy as we vary any one of the default parameters shown in Table (ref). Of particular interest is that the value of the policy increases as we increase the lower bound on assignment probabilities. This reinforces our intuition that the “raw” assignment probabilities output by traditional bandit algorithms are too aggressive (i.e., discards treatment arms too quickly) for accurate off-policy learning.
In Figure (ref), we present various statistics associated with the difference in value between the learned contextual and non-contextual policies, as we vary parameters away from their “default” value. We present the average of the following statistics over simulation runs: the true difference between the two learned policies, the estimate of the difference, the standard error, and the statistical power. At the default experiment length of $3,000$ observations, we have over 99% statistical power to detect differences between these two policies.
Lastly, Figure (ref) shows the trade-offs between the true value of the learned contextual policy, the average value during the learning phase, and the power to detect a difference in value between the learned contextual and non-contextual policies. Consider first the evaluation fraction, where a value of 1/2 attains high policy value and high average value during the learning phase. Although a value of 1/3 attains both higher policy value and higher average value during the learning phase compared to 1/2, the power to detect the value difference between the learned contextual and non-contextual policies is lower. Next, consider the lower bound exponent, where a value of -1/16 attains a high policy value while attaining higher average value during the learning phase than -1/32. Selecting four arms attains higher policy value while attaining a slightly lower average value during the learning phase compared to selecting six arms, though the differences are very small. Lastly, the power to detect the difference is 97% at length 2,000 and 99% at length 3,000.
In December of 2021, we conducted our main survey experiment in which participants were recruited via Lucid.
\paragraph{Behavior during the experiment.} Table (ref) shows the number of valid observations in each batch. We aimed to collect 150 observations in each batch, but the numbers are not exact as we do not have fine control over the flow of participants' responses in Lucid.
Figure (ref) shows average reward - the score assigned by respondents spanning extremely dissatisfied (-10) to extremely satisfied (10) - obtained over time. In the top left panel, we see that after batch 4, the average reward does not increase. We also plot the average reward obtained over time for different subgroups: “liberals” (political leaning $<4$ on a seven-point scale, with 1 being Strong Democrat) and “conservatives” (political leaning $\geq4$), “young” (age $<30$) and others, “pro-choice” (does not agree that abortion should be restricted, i.e., answered 1 to 3 on a five-point scale), and others (agree that abortion should be restricted). While the average reward mostly increases over time for “conservatives,” it starts high and ends up lower than where it started for “liberals.” For the other subgroups, the average reward oscillates a bit over time. However, for each of these subgroups except for liberals, the average reward is (weakly) higher than where it initially started, although the estimates are noisy.
Figure (ref) shows how average assignment probabilities evolve over time, i.e., $1/|B| \sum_{s \in B} e_{s}(X_s, w)$ for each batch $B$ and treatment $w$. This is a crude but informative measure to understand which arms are being favored by the algorithm. As we can see in Figure (ref), the algorithm assigned NRA most often in the beginning of the experiment. The algorithm assigned Greenpeace more often later in the experiment - at the 6th batch; it is the most favored arm, and it continues to be either the first or the second most favored arm after that. Planned Parenthood was favored early on but declined in overall appeal relative to Greenpeace and finished with a third place. BLM had rather constant evolution over time and finished in a fourth place in terms of assignment probabilities.
It is not possible to fully understand the behavior of the bandit by looking at average probabilities. An alternative approach is to determine a specific covariate value $x$ and observe the evolution of assignment probabilities for that value; i.e., $e_1(x, w), e_{51}(x, w), \cdots, e_{451}(x, w)$ for each treatment $w$.\footnote{Recall that assignment probabilities $e_t$ are fixed throughout for each $t$ in a batch of 50 observations, so that $e_1(x, w) = e_{2}(x, w) = \cdots = e_{50}(x, w)$ for each fixed context vector $x$ and arm $w$, and similar for other batches.}
For example, what are the average assignment probabilities of each charity to participants who identify as liberal? To produce this, we first computed the median values of other covariates (e.g., views on abortion) among participants who reported their political leanings to be less than 4 (i.e., participants who identified as Strongly/Moderate/Leaning Democrat) and then computed the sequence of assignment probabilities for a hypothetical participant with these covariate values. Our results are in the first panel in Figure (ref). Figure (ref) indicates that the assignment probabilities are different for “liberals” and “conservatives.” For liberals, Greenpeace is the most favored arm and Planned Parenthood is the second most favored arm by the end of the learning phase. For conservatives, NRA was favored early on, but Greenpeace takes over after the 5th batch.
We analogously create and plot the same figures across all political subgroups in Figure (ref). For Democrats and independent participants, Greenpeace is favored by the algorithm. On the other hand, for Republicans, the algorithm strongly favors NRA.
Participants who favor abortion restrictions also have very different assignment probabilities compared to those who do not. Figure (ref) indicates that among those who strongly agree with the statement “Abortion should be banned or aggressively restricted,” NRA is generally the most favored arm, while Greenpeace is generally the most favored arm for other subgroups.
\paragraph{Learned policies.} At the end of the learning phase, the four charities selected according to the frequency score ((ref)) were BLM, Planned Parenthood, Greenpeace, and NRA. We then used policyTree to estimate the best contextual policy using data from the learning phase, restricted to those four treatment arms. Figure (ref) shows the contextual policy $\hat{\pi}^{\text{C}}$ that was estimated using these four arms. The estimated best non-contextual policy $\hat{\pi}^{\text{N}}$ assigns Greenpeace to every observation.
\paragraph{Subgroups} Table (ref) shows the average rewards and their standard errors for different subgroups for the four selected arms which are BLM, Greenpeace, NRA and Planned Parenthood. The subgroups are the ones that appear in Figure (ref). This time, we use the entire sample (i.e., learning and evaluation data) to compute the average rewards. Figure (ref) plots those means along with their 95% confidence intervals.
We observe variations across arms and across groups. When we classify participants based on their political leanings, we find that Planned Parenthood is the most favored charity among liberals and NRA is the most favored charity among conservatives. Point estimates indicate that the benefit of being assigned to the best charity over being assigned to Greenpeace is 7.2% for liberals and 2.6% for conservatives.
When classifying participants by age group, we find that those who are below age 30 favor BLM the most, and those who are above age 30 favor Greenpeace the most. Assigning BLM instead of Greenpeace to those below age 30 increases their outcome by 2% in terms of point estimates.
When classifying participants by abortion views, we find that pro-choice participants favor Planned Parenthood the most and those who are anti-choice favor NRA the most. Assigning Planned Parenthood to pro-choice participants and NRA to anti-choice participants, instead of Greenpeace, increases their outcomes by 11% and 71%, respectively.
Some charities can be polarizing. For example, BLM is highly favored by liberals and those below age 30, but BLM is not favored by conservatives and those who are anti-choice. On the other hand, Greenpeace is less polarizing.
\paragraph{Evaluating Policies}
Let $\widehat{\pi}$ be the policy learned at the end of the learning phase, and let $\pi^{N}$ denote the policy that always assigns the best (learned) fixed policy, learned using the data in the learning phase. The hypothesis we want to test is the following:
We use data from the evaluation phase to test this hypothesis. (Note that biases can arise if the same data is used to select a policy and evaluate it.) The estimated values of the learned contextual policy and the best fixed policy are given in Table (ref). Column 3 in Table (ref) reports the difference between the value of the learned contextual policy and the best fixed policy, along with its standard error and p-value, validating our hypothesis as it shows that rewards are higher in the contextual policy setting compared to the best fixed policy. We also report the values of all fixed policies in Table (ref).
The learned policy divides the covariate space into (possibly empty) regions $R_1, ..., R_K$ defined by $R_w := \{ x \in \mathcal{X} : \hat{\pi}^{\text{C}}(x) = w \}$. The next hypothesis we want to test is the following:
Table (ref) shows the contrast estimates per region. For the region where NRA was recommended, we successfully validate this hypothesis. For the region where BLM was recommended, the difference seems to be too small to detect even with the evaluation data (which is designed to detect these differences). Unfortunately, for the region where Planned Parenthood was recommended, it appears that Greenpeace dominates. However, only a few users fall into this region.
In this section, we use the additional data collected from the main experiment to reevaluate the benefits of the bandit design over standard uniform sampling. Ideally, we would run our bandit design and uniform sampling several times and then compare the value of the policy learned and cumulative regret. However, this would be prohibitively expensive, so we instead consider two approaches to evaluating the benefits.
\paragraph{Summary statistics from the main experiment highlight adaptivity benefits.} Contextual bandits can outperform uniform sampling for policy learning when they collect more data on potentially optimal policies, since this enables more accurate selection of the best policy. To evaluate whether this benefit was present in the main experiment, we present evidence that indeed, the learning phase collected more data about our ultimately selected policy than would have been collected under uniform randomized sampling (used in the first batch). From Figure (ref), we observe that the average probability for choosing the arm recommended by the learned policy (empirically optimal policy) increases over time. This data collection allowed us to understand with higher precision at the end of the learning phase that this policy was indeed a high-performing policy. Further, from Table (ref), we see that the average reward of the TreeBagging bandit we use is higher than the estimated reward from uniform assignment, providing evidence that our algorithm did indeed achieve lower cumulative regret.
\paragraph{Simulation study based on main experiment data.} Our next exercise to evaluate the performance of our selected adaptive experimental design is to conduct a final simulation study designed to mirror our setting. Note that our earlier simulation study was based on pilot data. In this final simulation study we run our bandit design and uniform sampling as well as the other algorithms we considered in Section (ref) several times on data generating processes learned from data collected in our learning and evaluation phases -- then compare the value of the policy learned and cumulative regret.
The simulation design is the same as in Section (ref) except that we use different sets of regularization parameters that best capture the heterogeneity in the main experiment data. Specifically, the set of regularization parameters (the factor multiplying the L2-norm of coefficients in the model described in Section (ref)) are selected via the one standard error rule from the following list of regularization parameters, $\{5, 10, 20, 40, 50, 80, 100, 160, 320, 500, 640, 1280, 2560, 5120\}$. Figure (ref) plots normalized 10-fold cross-validation (CV) scores for this list of regularization parameter. The responses and predicted values lie in the range $[-10,10]$, and before computing the mean squared errors, we normalize these to lie in $[0,1]$. Using the one standard error rule, which selects the regularization parameters with CV scores within a one standard error of the best CV score, we get the following list of regularization parameters $\{80, 100, 160, 320, 500, 640, 1280, 2560\}$.
Tables (ref) and (ref) quantify the benefits of running our adaptive experiment design. Table (ref) shows that the learned policy is at least as good as the one learned when collecting data uniformly, and, in fact, it improves upon it by a modest margin. Table (ref) shows that we indeed get modest benefits (about 20% reduction) in terms of regret.
In this paper, we consider the problem of designing an adaptive experiment when the goal is to learn a personalized treatment assignment rule. Adaptive experiments risk discarding potentially successful treatment arms too early, sacrificing accuracy at the expense of minimizing cumulative regret. We demonstrate that policy learning methods are able to find policies of higher values when data is collected through uniform assignment probabilities rather than standard contextual bandit algorithms, and we propose a simple heuristic to overcome this issue. Specifically, we impose a lower bound on assignment probabilities which decays slowly so that no arm is discarded too quickly. When conducting policy learning using the adaptively-collected data, we also compute a score that tracks how much each arm is favored by the adaptive algorithm and restrict the set of arms used to learn a policy to those that are most favored in the adaptive data collection.
We illustrate our approach by conducting an adaptive survey experiment eliciting user preferences in charitable giving. Our setting considers data sets that cost several thousand dollars to collect using commonly accessed survey platforms, and so the size of our experiment is comparable in size to those accessible to academic researchers. The benefits to personalization are likely to be greater in our experiment than many others - it was designed with personalization in mind - so our findings may not be representative of the challenges faced by standard algorithms in more typical studies. We believe there is a great opportunity for future research to improve on the performance of adaptive experiments in settings with moderate sample sizes relative to the signal in the data.