Bayesian Optimal Experimental Design for the Survey Bandit Setting
Authors: Sang T. Truong
Willie Neiswanger
Susan Athey
Venue: Submitted to ICLR 2023 (2023)
Keywords: Bayesian optimal experimental design
contextual bandit
survey

Abstract: The contextual bandit is a classic problem in sequential decision making under uncertainty that finds broad application to tasks in precision medicine, personalized education, and drug discovery. Here, a decision maker repeatedly receives a context, takes an action, and then observes an associated outcome, with the goal of choosing actions that achieve a minimal regret. However, in many settings, the context is not given, and the decision maker must instead collect some information to infer a context before proceeding. For example, when a doctor does not have prior information about a patient, they might ask a sequence of questions before recommending a medical treatment. In this paper, we aim to develop methods for this setting—which we refer to as the \emph{survey bandit}—where the decision maker is not given access to the context but can ask a finite sequence of questions to gain information about the context before taking an action and observing an outcome. Using insights from Bayesian optimal experimental design (BOED) and decision-theoretic information theory, we view the interaction with each user as a BOED task, where the goal is to ask a sequence of questions that elicit the most information about the optimal action for this user. Our procedure is agnostic to the choice of probabilistic model, and we demonstrate its usefulness in a few common classes of distributions. Our algorithm achieves significantly better performance on both synthetic and real data relative to existing baseline methods while remaining statistically efficient, interpretable, and computationally friendly.

Under review as a conference paper at ICLR 2023
BAYESIAN OPTIMAL EXPERIMENTAL DESIGN FOR THE SURVEY BANDIT SETTING
Anonymous authors Paper under double-blind review
ABSTRACT
The contextual bandit is a classic problem in sequential decision making under uncertainty that finds broad application tasks in precision medicine, personal- ized education, and drug discovery. Here, a decision maker repeatedly receives a context, takes an action, and then observes an associated outcome, with the goal of choosing actions that achieve minimal regret. However, in many settings, the context not given, and the decision maker must instead collect some informa- tion to infer context before proceeding, For example, when doctor does not have prior information about a patient, they might ask a sequence of questions before recommending medical treatment. In this paper, we aim develop meth- ods for this setting which we refer to as the survey maker is not given access the context but can ask finite sequence of ques- tions to gain information about the context before taking an action and observing an outcome. Using insights from Bayesian optimal experimental design (BOED) and tecision-theoretic information theory, we view the interaction with each user BOED task, where the goal to ask a sequence of questions that elicit the most information about the optimal action for this user. Our procedure is agnos- tic the choice of probabilistic model, and we demonstrate its usefulness in a few common classes of distributions. Our algorithm achieves significantly better performance on both synthetic and real data relative to existing baseline methods while remaining statistically efficient, interpretable, and computationally friendly.
where the decision
INTRODUCTION
In many sequential decision making applications, a decision maker faces a sequence of users, for which they need to choose action and then observe an outcome. Each user has context vector (i.e. a set of features), which, in many cases, is not known a priori to the decision maker!. The context is needed to choose an action that yields good outcome, but acquiring this context can be expensive or time-consuming. We refer to this setting as the survey bandit, which has been previously studied by Krishnamurthy & Athey (2020). One example of this setting is in personalized medicine: a physician faces a sequence of patients, and to each they can ask a few questions before recommending a final treatment (Yao et al., 2021; Tomkins et al., 2021). Another example can be found in education: during office hours, professor faces sequence of students, and they can ask each a few questions before recommending an exercise or a reading. Last but not least, the survey bandit setting also finds application in drug and material discovery: during virtual screening, a chemist faces a large set of molecular structures, and they can perform a finite set of tests on each candidate (e.g. DFT calculation or molecular docking) before deciding whether or not it should go on to the next phase of the study (Kitchen et al., 2004; Bengio et al., 2021: Svensson et al., 2022). Users' context features are usually not independent, and thus good decision making can be achieved even when a small part of the context observed. For example, in series of questions related to political leaning, if the decision maker observes that user prefers to watch Fox News, they may need to ask whether or not they identify as conservative.
Suppose the decision maker can sequentially ask few questions before recommending treatment-what questions should they ask? One way to tackle this problem is to view querying
'This setting also includes cases where the decision maker has partial information, such as prior belief about the users' contexts, before asking questions.

---

Under review as a conference paper at ICLR 2023
answers from the user feature selection problem, where only small subset of features is use- ful to predict the outcome (Bastani & Bayati, 2020). Taking this view, Krishnamurthy & Athey (2020) treat querying answers as feature selection using ridge regression. Using the linear payoff assumption, RidgeUCB further assumes the knowledge of a threshold 9min such that features with ridge regression coefficient below this threshold have impact on the outcome, and hence can be ignored. Although this assumption is intuitive, RidgeUCB can be brittle when the assumption is violated. In practice, is unclear how between contexts and outcomes. Taking a similar perspective, Bouneffout et al. (2017) views the question phase in the survey bandit setting as feature selection problem and proposes the Contex- tual Bandit with Restricted Context algorithm as a solution. The feature selection view of the survey bandit can additionally introduce a challenging combinatorial search problem (i.e. choosing an optimal subset of the features).
3min without knowing the strength of the relationship
This paper takes an alternative point of view. We exploit the ability to sequentially query fea- tures and receive signal from the user in the survey phase to adaptively ask the most informa- tive question, following insights from Bayesian optimal experimental design (BOED) (Chaloner & Verdinelli, 1995; Ryan al., 2016) and theoreic information theory (DeGroot, 1962; Rao, 1984; Neiswanger et al., 2022). This alternative approach treats the question phase for each user a BOED problem, where the goal is to ask the most informative question, while the treatment phase can be formulated as a contextual bandit problem. Instead of eliminating the feature that is believed to be unimportant, our approach tries to model the dependencies between features by lever- aging probabilistic modeling and approximate inference, in order to carry out a sequence of decision making tasks. To the best of our knowledge, this hybrid approach between BOED and contextual bandits has not yet been explored for the survey bandit setting.
In full, our method takes advantage of a recently-develope which allows us to identify the question that elicits the most information about the best action for a given user in expectation. We conduct experiments on synthetic and real datasets in the survey bandit setting and show strong performance relative to number of baselines. Our method has intimate connections with a variety of algorithms for decision-making under uncertainty, such as Bayesian optimization, active learning, and contextual bandits. All implementations will be made publicly available.
decision-theoreti BOED approach,
2 DECISION-THEORETE ENTROPY SEARCH FOR SURVEY BANDIT
We start by establishing some notation for the survey bandit set- ting. Facing a sequence of U total users, a decision maker can ask each user fixed number of questions, observe their answers, rec- ommend a treatment, and observe a corresponding outcome. We assume there are a total of Q questions and T treatments that a deci- sion maker can choose from. For each user, the number of questions that the decision maker ask, denoted Qallow, is assumed to be given. Associated with each user is a vector y ~ p(y), 2 E RQ+T which can be partitioned into an answer vector ya , (2 [yo.1, No.r]- We can also partition y into an observed vector ylos and an unobserved vector Junobs. The decision maker's 's goal is to ask, for each user, informative questions that reveal the treatment with the highest outcome, in expectation. A graphical illustration of the problem setting is given in Figure 1.
Each row of the above matrix is a user. The shaded and unshaded cells are observed and unobserved an- swers/outcomes, respectively. Here, Qailow = 4 is shown.
Figure 1:
and an outcome vector
2.1 DECISION-THEORETT ENTROPY SEARCH
In this subsection, we assume that the joint distribution P(ya, Bo) is given, and in the following sec- tion we will discuss how to estimate this distribution from observed data. Given this joint density, the decision maker should ask the question that elicits the most information-i.ee the greatest reduction in posterior uncertainty-atieee about the best treatment, on average. One notion of mutual information be- tween answer and the best outcome can be captured by Hento-ntropy. a decision-theoreet notion of uncertainty (DeGroot, 1962; Rao, 1984; Neiswanger et al., 2022). Suppose we have a Bayesian model for parameter & E Tb Then the H -entropy is parameterized by prior distribution p()).
2

---

Under review as a conference paper at ICLR 2023
Algorithm A Search (HES) for the Survey Bandit Setting
D x-D 0
for +- to U do
Iterate through each user u E [U]
0g + Estimate model parameters using D
Du +
for + 1 to Qallow do for o' +- to Q do
Iterate through each question o' E [Q)
p(ya.q' Duu 0g) for 1 + 1 to I do
{vā.g] i== iid
Draw samples for the MC estimate
Compute p u(yolya.o' Dui 0w) end for end for
> Compute conditional distribution
+- arg / (q))
Optimize EHIG acquisition function Update user dataset with observed answer
Du t Du U (Va.9*
end for
if c (0, 1) then
Follow decaying e-greedy strategy
t t Select treatment that maximizes p(yo,
else
!" + Select treatment as draw from Unif([?))
end if
Du - Du U (yo.r"
> Update user dataset with observed outcome Update full dataset and
D - DU (Duh. etExa
end for
and reward function r # x A - R. Given dataset D, the posterior Hentt-yyropy is defined as Ho,Al(())D)] = SuPaeA (ptor))r((ss)))
For the survey bandit setting, the unknown vector of interest is the outcome vector e = Yo and we will be interested in the uncertainty (entropy) of the posterior distribution over this outcome vector, Hr, [p(yo [D)]. Here, the action set is the set of treatment indices, i.c. AA = {I...., T3 = sequence of questions asked to a given user. In
[2'. and the dataset contains the answers this setting, the reward function evaluated at treatment t and outcome vector is defined to be ryyo.t) No,1. i.e. the reward function indexes into the vector yo position t. For given user, the myopic Bayesian optimal question, which has the greatest expected increase in information about the optimal treatment, the one returned by maximizing the expected H, iin.A-information gain (EHIG) (Neiswanger al., 2022):
arg max EHIG( A) = arg max (H, (Hr,Alp(Uo)D)) Ep(v.. ID) (Hr.A(P(Volln D)Il) 4E[Q)
qE[Q]
arg max E Epise.. (D)
max Eptu Mt.. D) ([yo:))) [E(T]
(E(@)
(I)
Σ
max plyo,ollaa D) [EE[T]
arg max (
7
where the final expression is Monte Carlo estimate given by / samples { iid drawn from the posterior distribution over answers to question 9. Note that, to compute the ex- pectation over p(yolVa.g. D) in the final expression, the EHIG only needs the mean p(yo ya.qu D).
p(ya.g (D)
The two discrete optimizations are carried out by enumerating over sets [Q] and [7]. Both Monte Carlo approximation and optimization over questions and treatments can be efficiently parallelized on modern computers with vectorization.
Choosing questions according to Equation (1) is an example of the Hr.A--ntropy search (HES) al- gorithm. The full HES procedure for the survey bandit setting is given in Algorithm 1. After the question phrase, HES recommends a treatment that maximizes the conditional expected outcome. This treatment recommendation can be viewed textual bandit perspective, and following the estimated optimal action only will lead to suboptimal exploration. To encourage exploration, decaying e-greedy strategy (Auer al., 2002) is employed,
greedy (pure exploitation) action from
3

---

Under review as a conference paper at ICLR 2023
which is simple yet often effective strategy. Other strategies, such as UCB, could be used well to balance exploration and exploitation. Note that, in Algorithm 1, computing the conditional distri- bution and estimating parameters repeated many times, which imposes additional computational constraints on the choice of the probabilistic model over answers and outcomes.
2.2 THE JOINT DISTRIBUTION OF USERS' ANSWERS AND OUTCOMES
In this section, we discuss models for the joint distribution p(ye: Yo: f) that capture dependencies between answer and outcome vectors. As stated previously, the family p(ya, No; O) needs to allow conditioning efficiently and parameter estimation with missing data. Both need to be done computationally efficient manner since the HES procedure iteratively performs these steps each new user arrives. A good class of parametric distributions that satisfies these criteria the Gaus- sian mixture model (GMM) (Murphy, 2012). A GMM can capture the complex geometry of many real-world distributions while allowing closed-form conditioning and efficient parameter estima- tion. While focus on GMMs demonstrations in this paper, extensions to other probabilistic models are straightforward. Below, we briefly review GMMs and the procedures to estimate their parameters under missing data, which we will require for our method.
GMM generates data by the following hierarchical process:
(2) where is one-hot vector that denotes the cluster to which the generated sample y be- longs. is drawn from a single trial multinomial distribution with cluster proportion π = [TI....,TTd Tcl. Ee
C Mutinomial(c; I), Ya. Yo N(ya po E9)
1. In Figure 2, we show a graphical model in plate notation for the above generative process, which we extend to include U users and potentially noisy observations of an- swers and outcomes, Vats- In contrast with a typical GMM, our model for the survey bandit setting involves an additional set of observed variables, whose elements might vary from user to user.
The conditional mean, covariance, and proportion of each mix- ture model component can be updated with Bayes' rule or in closed form. We note that the EHIG optimization procedure (in Algorithm 1) only requires the following three quantities:
Vebs
C
O
1. The distribution of user's cluster assignment, condi- tioned on their observed answers, p(c))a,obs).
2. The distribution of a user's unobserved answers, condi- tioned on their observed answers, P(ya,unohe (o
U
3. The mean of user's outcome distribution, conditioned on their observed answers, p(yo obs.
Figure 2: GMM graphical model in the survey bandit setting. Shaded and unshaded nodes de- note observed (potentially with noise) and latent variables, respec- tively. The observed component of y is different for each user. C, U. and O denote the total number of clusters, the total number of users, and the total number of observed questions and outcomes, respectively.
All three of these quantities can be estimated (see Appendix A for detailed formula), via the following quantities:
1. The empirical mean of outcome and answer vectors from sample of users, ((y)) and p(ya).
2. The empirical covariance between answers from sam- ple of users, Eea--
3. The empirical covariance between answers and out- comes from a sample of users, Eno-
The covariance between outcomes, Doo. impossible to estimate without further assumptions due to the Fundamental Problem of Causal Inference (Holland, 1986), where no two outcomes can be observed simultancously. Fortunately, the EHIG optimization expression in Equation (1) does not require this quantity.
GMM parameters are estimated in the presence of missing data with the Espectation-conditin maximization (ECM) algorithm (Meng & Rubin, 1993; Ghahramani & Jordan, 1993; McCaw al., 2022). ECM is a generalization of the expectation intirattionmmaimizzzaiinn (EM) algorithm (Dempster et al., 1977), popular algorithm for maximum likelihood estimation (MLE) in GMMs, ECM replaces the
4

---

Under review as a conference paper at ICLR 2023
maximization step over all parameters of interest in EM with sequence of conditional maximization steps, where each parameter of interest is optimized individually conditioned on other parameters. ECM requires missingness in the input to satisfy the missing at random (MAR) assumption for unbiased estimation, meaning whether an element in the input vector is missing can depend on the observed elements, but not the unobserved elements. This requirement is satisfied in our setting, because whether or not HES chooses to observe a context does not depend on the unobserved data. For a detailed treatment of ECM, we refer the reader to Meng & Rubin (1993); Dempster et al. (1977); Ghahramani & Jordan (1993), and (McCaw et al., 2022). MLE is used in this study because it is computationally efficient, but other inference methods, such as Markov chain Monte Carlo or variational inference, can be used as well.
The dataset in the survey bandit setting has a large amount of missing data for two reasons: (1) the context for each user is only observed partially and at low rate, and (2) only one treatment per user is observed. This large amount of missing data can affect the stability and convergence rate of the iterative optimization procedure in ECM (McCaw et al., 2022). In Appendix A, we describe our initialization procedure to stabilize ECM in the presence of missing data.
3 EXPERIMENTS
We first verify that HES works advertised on six artificial data generating processes, where details about the set of informative questions and treatments are known. We then conduct experiments on a real dataset from the charitable giving experiment (Athey al., 2022). Each algorithm is evaluated with four metrics: (1) cumulative regret, (2) per-period regret, (3) per-period accuracy of estimating the optimal of questions/treatmmntss for the population, and (4) per-period accuracy (measured by MAE) of the outcome model. Regret is defined as the difference between the outcome of treatment chosen by the algorithm and the optimal outcome. Per-period regret and per-period accuracy (of question, treatment, and outcome estimation) are computed every 100 users. For the per-period accuracy of estimating the optimal set of questions/treatments for the population, we compute the fraction of the set of optimal questioonstreaaments that the algorithm correctly identifies". Additional details on the experimental setup are given in Appendix B. HES compared against the following six baseline algorithms.
1. LinUCB (Li et al., 2010) with full access to answers: a standard contextual bandit algorithm with access to the ground truth context, which represents what can be achieved when there is no budget constraint question selection.
2. RCdgeUCB (Krishnamurthy & Athey, 2020): discussed previously in Section 1, RidgeUCB treats question selection as feature selection, where features with sufficiently high coefficients in a ridge regression are selected, and then uses LinUCB to recommend treatment.
3. Uncertainty Sampling (US) (Lewis Gale, 1994), popular strategy in active learning: this uses a probabilistic model of answers and outcomes to query questions with the highest pre- dictive uncertainty, and then selects treatments with the highest expected conditional outcome.
4. Uniform Non-contextual Randomization (UNR) (Hariton & Locascio, 2018), a popular method for conducting non-contextual experiments: this recommends treatments uniformly at random without considering the answers to questions. UNR expected to have constant per-period regret over time, but is useful as a benchmark for how data collection influences the quality of learned models of the answer distribution and the outcomes conditional on answers.
5. UniformBOED (Fang & Lin, 2003): this method selects questions to query uniformly at ran- dom, and then selects the treatments with the highest expected conditional outcome according to probabilistic model.
6. BayesLinUCB: this method queries questions uniformly at random, infers the full context by a probabilistic model, and then uses LinUCB to recommend treatments (Levine, 2018).
"This not necessarily the per-user optimal guestions/teeatment. For example, if a population has infor- mative questions as 1, 2, and 3 and Qailww = 3, and the algorithm asks 2, 3, 4, its accuracy of identifying the set of optimal questions is .. If the set of optimal treatments for the population is (1, 2, 3). and the algorithm chooses treatment 2 for user, its accuracy of selecting the optimal set of treatments is 1, even if the true optimal treatment for this user might not be 2.
5

---

Under review as a conference paper at ICLR 2023
RidgeUCB
UniformBOED
LinUCB
BayesLinUCB
UNR
2030
pCTAC Ragedt
1190
2000
700
402
1022
1812
Peried
209
40
5000
2307
1090
1090
2300e
5000
23600
464
2000
42.00
2000
3000
Figure 3: A Simple Homogeneous Population (top) and A Homogeneous Population with Answer Dependency (bottom). Summary statistics of all metrics are given in Table and 2 in Appendix B.
Each simulated experiment is rum for sequence of 100,000 users. In the beginning, each algorithm has warm-up period where it can interact with 30 users per treatment. During this period, the decision maker can ask users all possible questions and recommend one treatment per user. There total of 16 questions and 6 treatments in all experiments. The parameters of the GMM are updated every 500 users. Parameters LinUCB and ridge regression are updated with every user. RidgeUCB is modified slightly to enable it to handle budget constraints in the number of questions: the algorithm is allowed to observe up to a size Qailow questions, which are randomly drawn from the ask?. Empirically, this modification does not change RidgeUCB behavior significantly because the algorithm rarely exceeds the budget constraint with the default Amin 0.5. Both answers and outcomes data scaled to the range (0, 1).
set of questions that it requests to
3.1 SYNTHETIC DOMAIN
Task 1: A Simple Homogeneous Population. In this task, each answer is independently drawn from a standard normal distribution and the outcome vector is constructed as follows: Vo.1 = Io No.2 = 2 No.3 = 2μ1 ya,1", and you = 0, Vi > 3. Hence, only questions {1, 2} are informative and only treatments {1, 21,2,3} should be considered. Prior to the survey phase, the deci- sion maker does not know which treatment in (0, 2} is the optimal one since they have the same statistic. An optimal decision maker should only need to ask most two questions (i.e. 0 and 1) to find the best treatment. Hence, we choose Qallow 2 here.
The result of this task shown in Figure (top row). Only LinUCB, HES, and RCdgeUCB con- verge to zero per-period regret, and RidgeUCB takes the most number of users (nearly 60,000) to converge. HES can quickly find informative questions and well-targeted treatment as shown by the fact that its fraction of informative questions and treatment approaches I over time. RidgeUCB takes much longer to do so. When there are many uninformative questions, the uniform query strat- egy is not effective, as illustrated by the fact that UniformBOED, US, and BayesLinUCB do not converge. Since the answers are independent in this setting. inferring full context after uniformly querying questions is also not effective. In addition HES, some of the other baselines such as US can achieve high accuracy in outcome prediction when conditioning on the observed answer. This high accuracy in outcome prediction does not necessarily imply high quality in decision making,
FFor example, with the budget of Qaioa = 3, if RidgeUCB requests to observe question 2, 4). it is allowed observe all three answers. Meanwhile, if it requests to observe {1, 4, 6). it will only observe subset size of its request, which could be 2, 6) ( 11,46)
'2 - has the effect of geometrically reflecting a sample through the mean. For example, if the normal distribution is centered at 5, and 4, then 2/ he higher 2/1 and is the better treatment.
is 7. If J 8, 24r = 2. Only 50% of the time would

---

Under review as a conference paper at ICLR 2023
RidgeUCB
UniformBOED
US
LinUCB
BayesLinUCB
UNR
2030
6:00
2000
402
1022
KG
A.0.2 00.5
400
10:00
Peried
200
40 Period
5000
19030
1030
Per sedoo Ragret
1790
20
400
90
1000
430
60
Figure 4: A Homogeneous Population with Many Potential Treatments (top) and Heterogeneous Population (bottom). Summary statistics of all metrics are given in Table 3 and 4 in Appendix B.
illustrated by the fact that the per-period regret of UniformBOED does not converge LinUCB achieves sublinear regret even with relatively high MAE. In the domain where explainabil- ity is important, the action taken by HES (Figure in Appendix B). The fact that the learned covariance matrix from HES is very close to the one induced from the data generating process further confirms that the algorithm works as expected.
while
also be explained by its learned covariance matrix
Task 2: A Simple Homogeneous Population with Answer Dependency. This experiment illus- trates an intuitive concept that was introduced in Section 1: when there are Q: informative questions but they are dependent, optimal algorithm may need to ask less than Qu questions. Task is mod- ified by letting Va,1 = ya,2. Similar to the previous experiment, questions {1, 2} are informative about the optimal treatment, but an optimal decision maker who knows will immediately know the other. Hence, for this experiment we choose Qallow = 1. Here, treatments {1, 2, should be considered, but of them are equally good. Similar the previous experiment, HES converges quickly in all metrics after a few thousand users (Figure 3, bottom row). Unlike the previous task, RCdgeUCB can no longer converge to zero per-period regret, which can be explained by the bias from correlated omittedd variables in ridge regression. The ability to handle dependencies between answers is crucial in the survey bandit setting, and hence this condition is included in all subse- quent experiments. Even though the data generating process has introduced dependencies between outcomes (Figure Appendix B), HES still performs well here in practice.
Task 3: A Simple Homogeneous Population with Many Potential Treatments. The previous experiments show that HES works well when there are three treatments to consider. In practice, there can be potentially many treatments consider. Here we show that our model is still effective when there are many potentially good choices for treatment. The outcome model of Task 2 is modified
as follows: ye.1 Ya. No.2 Ya.2: Vo.3 = ya,3, yo.4 2 Va,1, No.5 = 2p2 Va,2, No.6 = but, for the same reason as Task 2, only HES converges quickly all metrics, demonstrating its ability to handle a large number of good treatments (Figure 4, top row).
2p1s Va,3- The set of informative questions is
two of them should be asked. Hence, we use Qallow
A Heterogeneous Population. Real-world populations of users may not be homoge- neous. In other words, their distribution might not have simple geometry, such as being unimodal. This experiment demonstrates that HES is capable of handling this situation. The data is generated according to the following hierarchical process, where users may come from one of two groups:
Task 4:
For users in the first group, the answer is drawn from isotropic multivariate normal distribu- tion with a mean vector of [1, 2, ..., Q] and variance of The outcomes are yo, = Va.1 No.2 0a,6, No.3 2p1 ya and you 0, Vi > 3.
7

---

Under review as a conference paper at ICLR 2023
RidgeUCB
UniformBOED
LinUCB
BayesLinUCB
UNR
15.00
0.00
202
12
2
VA2 Pull
1500
2330
8000
19080
200
400
W0
1000
12.00
200
400
1200
19038
Tartall
Per sedto Reyiet
200
480
90
80
100
246
1003
100
Figure 5: A Skewed Population (top) and A Noisy Population (bottom). Summary statistics of all metrics are given in Table 5 and 6 in Appendix B.
For users the second group, the answer is drawn from an isotropic multivariate normal distribution with mean vector of (Q,.., 2, 1] and variance of 1. The outcomes are yo, 2, Vo.2 7, No,3 12, No.4 = 2112 2a, yo.5 = 2j17 - yo.7; Mo.6 2/112 - y2,
An optimal algorithm in this setting would need ask four questions from the set 6,, 12). Observing any first answer, the algorithm should know which cluster the user comes from², and asks most 3 more questions find the best treatments. Hence Qallow quickly on all metrics, demonstrating its ability to handle the hierarchical data generating process (Figure 4, bottom row). Since there no longer a simple linear relationship between the answer and outcome, even with context oracle, LinUCB does not converge to sublinear regret. This experiment highlights a strength of HES, that is with a ficxible underlying probability model, it can handle several hierarchical, nonlinear data generating processes commonly found in practice.
HES converges
Task 5: A Skewed Population As mentioned previously, the HES procedure for the survey ban- dit setting be paired with different models. For demonstration purposes, in this paper, GMM, which strikes good balance between expressiveness and statistical as well as computational efficiency. No matter the model, it is rarely perfect fit for real-world data. In some modeling tasks, when the data distribution deviates from the assumed one, and if the underlying algorithm is not ro- bust enough, the performance of the decision maker might degrade severely. This experiment shows that HES performance is robust to model misspecification. We modify Task 2 by generating answers from a skewed multivariate normal distribution, with skewness of 5, which we plot in Figure (Ap- pendix B); we note that this geometry is significantly different from the normal distribution. We choose the skewed multivariate normal family for this purpose because it allows us to control the dependency between variables while deviating from the typical Gaussian distribution. HES works well even this case, showing that HES can achieve certain level of robustness with distributional misspecification (Figure 5, top row).
common in practice to observe noisy measurements from each user. To examine the algorithm's 's robustness under noise, add 10% normal noise to each ob- servation (i.c. normally distributed noise with standard deviation 0.1 in our setting). Similar to the previous task, all metrics quickly converge for HES, demonstrating its robustness to noisy observations (Figure 5, bottom row).
Task 6: A Noisy Population
'oor example, when observing answer to question 1, the algorithm should know the user helongs to group if Va.1 Otherwise, Va.1 Q indicates that the belongs group
8

---

Under review as a conference paper at ICLR 2023
RidowUCC
UnIoomBBED
UiniB
BayestinuCS
UNR
HES
-200
Cundiiing hage
XX00
10303
1023
2380
Number of Useer
Pericd
Pericd
Figure 6: Results on the Charitable Giving experiment. Summary statistics for all of the metrics are given in Table 7 in Appendix B.
3.2 A REAL DOMAIN BASED ON CHARITABLE GIVING EXPERIMENT
In this section, real dataset from charitable giving experiment (Athey al., 2022) is used to examine the algorithm in a practical setting. This dataset includes 3065 users and their answers to 16 general demographic characteristics, political affiliation, and media consumption. It also contains the response from each user to the following question: "How would people like you feel if we donated one thousand dollars to the following charity?" The user is then shown randomly of charities. Charitable giving is an especially suitable use case for adaptive experiments since the optimal policy is difficult to obtain beforehand. Behaviors that determine charitable giving are highly individual and depend on background and interest (Athey et al., 2022).
semi-synthetic dataset that emulates the behavior of users from the above charitable experiment is generated using the following procedure. First, we learn a mapping from answers to outcomes. We train a number of models with 10-fold cross-validation on a 80:20 trainctest split using MAE as the goodness of fit criteria. The following models are chosen: random forest (Athey et al., 2016), local linear forest (Friedberg et al., 2018), decision tree, a neural network with layer 17 hidden node and sigmoid activation, linear regression, Gaussian process regression, ridge regression, elastic net regression, Bayesian ridge regression, and a one-layer neural network with sigmoid activation. Hyperparameters of each model are tuned with random grid search. The summary, given in Table (Appendix B), indicates that the one-layer neural network works well for this dataset. This model is used to generate data for further experiments, where draw context from kernel density estimator (with parameters fit via 10-fold cross-validation) of the data, and map it to the outcome. We set Qallow 2 to emulate the time constraint when interacting with real users. The results of this experiment are shown in Figure 6. Here, HES achieves the same level of regret as LinUCB even with access to only out of 16 questions. Compared to other algorithms, HES achieves similar or better accuracy and regret level, demonstrating its usefulness in real-world setting.
DISCUSSION & FUTURE WORK
In this paper, we introduce a decision- entropy search procedure for the survey bandit set- ting, which treats the question phrase sequence BOED tasks with the goal of asking infor- mative questions to recommend treatments with minimal regret. The procedure may be paired with different models for answers and outcomes, and we demonstrate its usefulness on various synthetic and real datasets.
There are multiple future directions for this study. For example, some questions and treatments in practice are continuous (e.g. recommend Img dose or 5mg dose of some drug), which allows the EHIG optimization procedure to be done with gradient-based optimization. In addition, our -e.t-entropyy search procedure is done myopically, which is computationally friendly but can be suboptimal. A non-myopic EHIG optimization procedure could achieve better performance. Third, we have considered the joint distribution of answer and outcome, but sometimes analyzing the mantic meaning of questions using tools from natural language processing can reveal information about the dependency of answers, even prior to observation of any answer. Last but not least, if computational speed is desirable, we want to explore the feasibility foundation decision maker that is pretrained using the EHIG objective, which might allow asking good questions in real time.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Susan Athey, Julie Tibshirani, and Stefan Wager. Generalized random forests, 2016. URL https: www.iii..ggaab//........ 01210.001221 01271.
Susan Athey, Undral Byambadalai, Victor Hadad, Sanath Krishnamurthy. Weiwen Leung, and Joseph Williams. The tradeoff between within-cxperiment outcomes and policy learning in con- textual bandits: A survey experiment charitable giving, 2022.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed ban- dit problem. Machine Learning, 47(2):235-256, 2002. doi: 10.1023/A:10133897044 URL /tt.///dii.// www.orggg/o.ooo 101.111/2/11111990000000000
https:
Hamsa Bastani and Mohsen Bayati. Online Decision Making with High-Dimensional Covari-
ates. Operations Research, 68( (8(1):276-294 January 2020. doi: 10. 00.1287/prre22111 2019. 1902. URL 294 html.
https://idees reper. org/ httgg//a/nnn//o//e///// http:///rorrrre////2222111111110
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup. and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation, 2021. URL
https://arxiv/ wttp://www..rgp////////////// 04399.
Djallel Bouneffouf, Irina Rish, Guillermo A. Cecchi, and Raphael Feraud. Context attentive bandits: Contextual bandit with restricted context, 2017. URL https: /taps:///axxii arxiv. org/ abs/1705, 03821.
Kathryn Chaloner and Isabella Verdinelli. Bayesian experimental design: A review. Statistical Science, 10(3):273-304 1995. ISSN 08834237. URL http:t/:// jstor org stable/ 2246015.
M. H. DeGroot. Uncertainty, Information, and Sequential Experiments. The Annals of Mathematical Statistics, 33(2):404- 419, 1962. doi: 10.1214/amm/1117700555555 URL https: //dii. wwd.doiioooo org/ 10. 10..214/aame a/oms/////////// 1117770457
A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society. Series B (Methodological), 39(1):1-38, 1977. ISSN 00359246. URL http: //www/ jsttr
Kai-Tai Fang and Dennis K.J. Lin. Ch. 4. uniform experimental designs and their applications in industry. In Statistics in Industry, volume 22 of Handbook of Statistics, pp. 131-170. Elsevier, 2003.
Rina Friedberg, Julie Tibshirani, Susan Athey, and Stefan Wager. Local linear forests, 2018, URL /ttps://arxiv... ottp:////0///////0000/ 11t.//1111..1.. 11408.
Zoubin Ghahramani and Michael Jordan. Supervised learning from incomplete data via an em approach. Advances in neural information processing systems, 6, 1993.
Eduardo Hariton and Joseph Locascio. Randomised controlled trials the gold standard for ef- fectiveness research. BJOG: An International Journal of Obstetrics & Gynaecology, 125(13): 1716 1716, 2018
Paul W. Holland. Statistics and causal inference. Journal of the American Statistical Associa- tion, 81(396)945-960, 1986. ISSN 01621459. URL http://t///// /ttp:///wwww../// jator. ottps//al//sssaaaeeeeeee.. 2289064.
Douglas B. Kitchen, Hélène Decornez, John R. Furr, and Jürgen Bajorath. Docking and scoring in virtual screening for drug discovery: methods and applications. Nature Reviews Drug Dis- covery, 3(11):935-949 2004. doi: 10.1038/nrd1549 URL https: htt///iiioogg//////// www//o............//ooo///11//// 1038/ nrd1549.
Sanath Kumar Krishnamurthy and Susan Athey. Survey bandits with regret guarantees, 2020. URL https://arxil org/
argg abs 2202 09814.
10

---

Under review as a conference paper at ICLR 2023
Sergey Levine. Reinforcement learning and control probabilistic inference: Tutorial and review, 2018. URL https: /ttpiv.ivvv./////i///aa/////aava org abagg//baaaae 100oa./180..0000 00900
David D. Lewis and William Gale, sequential algorithm for training text classifiers, 1994.
URL https:://// /ttes///axxii /aaaaaxxvvvvoo/..a/aaa org/ abs/ abs/cmp httpc/mpp1119000000000000 9407020.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international confer- ence on World wide web WWW 'O. ACM Press, 2010. doi: 0..144/1772699017777555 URL
https: //ii.ii...//
17727558
Zachary R. McCaw, Hugues Aschard, and Hanna Julienne. Fitting gaussian mixture models on incomplete data. BMC Bioinformatics, 23(1):208, 2022. doi: 10.1 18/411899900022044440000
URL https: http:://://doii http:/oo...oogoo 1111:/1111111111--00----0000-0
Xiao-Li Meng and Donald B. Rubin. Maximum likelihood estimation via the eem algorithm: A general framework. Biometrika, 80(2):267-278, 1993. ISSN 00063444. URL http: //ww..
Kevin P Murphy, Machine learning: probabilisticc perspective. MIT press, 2012.
Willie Neiswanger, Lantao Yu, Shengjia Zhao, Chenlin Meng, and Stefano Ermon. Generalizing bayesian optimization with decision-theoretic entropies. Advances in Neural Information Pro- cessing Systems, 35, 2022.
C. Radhakrishna Rao. Convexity properties of entropy functions and analysis of diversity. In In- equalities in Statistics and Probability, 1984.
Elizabeth G. Ryan, Christopher C. Drovandi, James M. McGree, and Anthony N. Pettitt. A review of modern computational algorithms for bayesian optimal design. International Statistical Review, 84(1):128-154, 2016.
Hampus Gummesson Svensson, Esben Bjerrum, Christian Tyrchan, Ola Engkvist, and Morteza Haghir Chehreghani. Autonomous drug design with multi-armed bandits, 2022. URL betps::/azzee
01393.
Sabina Tomkins, Peng Liao, Predrag Klasnja, and Susan Murphy. Intelligentpooling: practical thompson sampling for mhealth. Machine Learning, 11099)2685-2727, 2021. doi: 10.1007/ $10994-021-05995-8 URL hwtps:ttttht...ttc http///iioorg/////////// 10. 1007/ 10019994---1-1--0 021-05995--8
Jayy Yao, Emma Brunskill, Weiwei Pan, Susan Murphy, and Finale Doshi- Power strained bandits. In Ken Jung, Serena Yeung, Mark Sendak, Michael Sjoding, and Rajesh Ran- ganath (eds.), Proceedings of the 6th Machine Learning for Healthcare Conference, volume 149 of Proceedings of Machine Learning Research, pp. 209-259. PMLR, 06-07 Aug 2021. URL https://proceedinng www.iinn.........e.eee.e.e mwr.prees v149/y10222 html.
A GAUSSIAN MIXTURE MODEL DENSITY AND INITIALIZATION
This section includes details about the Gaussian mixture model (GMM), as well as the procedure for initializing the ECM algorithm under severe cases missing data.
p(yobale (c) Pr(c)
N N Polss D Pr(c)
Pr(clyoos)
Eer Poyooslle (c) Pr(d') Ee (Hltte Ho De'o Pr(c')
(3)
Munobsjobs
Punnoe + oumohssoos
(Yons Molas)
n
Jnnohsjobs
Dunobs unobs
Lbbo (2ibss.bbs)
-1 unobs
When C' 1, GMM is multivariate normal distribution:
Yo, Ya ~ N (yo: Mai p1 E); ~ N (yas Pa, Dna);
Yo N N(yoi Moy Eroo)
Dna Eng
(4)
/ [Mar Mol, D=
Eno Eeoo

---

Under review as a conference paper at ICLR 2023
In the general case,
p(u) Σ Pr(eWW E9); 1e Munbss po
Σ
unnobs, unobs
Lnnobs obs
(5)
E unobs
Lobs,
We propose the following initialization procedure to stabilize ECM optimization. This initialization only done once for the entire interaction with all users. After the warm-up period, K-mean clus- tering is employed to assign the cluster membership each data point. Next, within cluster, for each outcome, a model that map answers to the outcome learned, then used to infer unobserved outcomes. Note that this is only done for the purpose of initialization, and do alternate the data. Finally, the initial means and covariance matrices are initialized with the EM algorithm. From the second iteration, the initial mean and covariance matrix for each cluster is set the ECM result of the previous iteration.
B EXPERIMENT DETAILS
This section contains further details on the empirical results.
Period
C. Rogret
Regret
Questions
Treatments
MAE partial
MAE foll
RidgeLIB
50k
10978. 96 = 107.
0.12 = 0.09
0.46 1 0.33
0.88 0..10
0.41 = 0.05
0.32 = 0.03
100k
11419.10
0.00
0.00
UniforBBODD
506
4022.05
+ 100.79
0.08 + 0.00
0.13 + 0.02
1.00 + 0.00
0.04 + 0.00
0.03 + 0.00
100k
9501.13
350.89
0.10 0.01
0.13 + 0.01
1.00 = 0.00
0.05 +
0.03 - 0.00
502
3895.
1965.96
0.07 0.04
0.17 0-224
1.00 + 0.00
0.05 + 0.00
0.04 + 0.01
100k
7457.91
1 33622.57
0.07 0.03
0.17 0.24
1.00 0.00
0.00 = 0.00
0.04 1 0.01
LinUCB
50k
1187.45
0.00
100k
1328.58 + 49.24
0.00 + 0.00
1.00 0.00
1.00 + 0.00
0.37 + 0.01
0.37 + 0.01
Bay
50k
5061.11
100k
9666666 1 425.59
0.08 1 0.01
0.16 1: 0.02
1.00 1: 0.00
0.32 1: 0.01
0.32 1 0.01
UNR
50k
11277.18
3016.1
0.19 0.01
0.49 = 0.02
N/A
N/A
100k
22614. 64 680.06
0.23 + 0.02
N/A
0.55 0.05
NIA
N/A
HES
120..81 14.90
0.00
0.96 = 0.01
1.00
0.00 = 0.00
0.06 = 0.00
100k
143.46
14.48
0.00 0.00
0.94 1: 0.00
1.00 :: 0.00
0.06 + 0.00
0.06 1 0.00
Table 1: Performance of the seven comparison methods on Task 1, at time step 50,000 and time
step 100,000.
Period
Regret
Regret
Questions
MAE purtial
RidgeUCB
506
9193..0
26.68
0.10 4 0.01
0.12 0.04
0.98 1: 0.02
0.48 1: 0.01
0.31 1: 0.00
100k
14138 40
22..8
0.13 0.02
0.14+
0.99 0.01
0.46 +
UniforBBED
50%
1359.72 = 85.50
0.08 = 0.02
0.16 0.01
1.00 = 0.00
0.01 = 0.00
0.03 = 0.00
100k
8394,27 + 187.30
0.08 + 0.02
0.11 1 0.01
1.00 + 0.00
0.05 2: 0.01
0.03 1 0.00
US
50K
4800155 1. 160..11
0,08 0001
0.00 1 0.00
1.00 1. 0.00
0.06 1. 0.00
0.04 1
100k
9324.77 + 345.62
0.08 + 0.00
0.00 + 0.00
1.00 + 0.00
0.06 + 0.00
0.04 + 0.00
LinUCB
50k
1156.81
6.77
0.00
0.00
0.00
0.34 = 0.000
0.31
100k
1288.99 91 +: 8.98
0.00 0.00
1.00 1: 0.00
1.00 = 0.00
0.35 - 0.01
0.35 - 0.01
4404..91
0.01
100k
8510.54 + 200.46
0.08 + 0.00
0.16 + 0.02
1.00 + 0.00
0.31 + 0.01
0.30 + 0.00
UNR
10632 = 168
0.19 0.01
0.03
100k
21265.43 - 273.16
0.22 + 0.01
N/A
0.48 + 0.02
N/A
N/A
HES
50k
381 46 5.58
0.00 1 0.00
1.00 1 0.00
1.00 1 0.00
0.05 1 0.00
0.06 1 0.01
100k
381.52
5.60
0.00 + 0.00
1.00 + 0.00
1.00 + 0.00
0.05 + 0.00
0.06 : 0.00
Table Performance of the seven comparison methods on Task 2, at time step 50,000 and time step 100,000.
12

---

Under review as a conference paper at ICLR 2023
Period
C. Regret
P. Regret
Questions
Treatments
MAE partial
MAE full
RidgeL/CB
50%
65033:2 + 36,24
0,13 = 0.02
0.18 + 0.01
1.00 = 0.00
0.41 = 0.00
0.11 = 0.00
100k
12969.74 110.00
0.14 + 0.01
0.18 + 0.01
1.00 = 0.00
0.44 = 0.00
0.12 = 0.00
UnifomBOED
50%
1881.15 + 116.11
0,09 = 0.01
0.20 1 0.00
1.00 0.00
0.00 + 0.00
0.07 + 0.01
100k
9722.36 1 224.76
0.10 1 0.01
0.19 1 0.01
1.00 1 0.00
0.10 1 0.01
1.86 J 2.52
US
50%
1815.47 = 1665.06
0.09 = 0.08
0.17 0.21
1.00 0.000
0.09 = 0.00
0.08 = 0.02
100k
8537.75 3937.119
0.05
0.24
0.10
LanUCB
50C
161.33 1: 11.18
0.00 1 0.00
100 1 0.00
1.00 0.00
0.13 1 0.00
0.13 1 0.00
100k
188,25
11.44)
0.00
0.00
0.14 0.00
0.14
506
4845.81 1: 108.51
0.08 1 0.00
0.22
1 0.03
1.00 1 0.00
0.10 0.01
0.11 0.01
1004
9685.75 + 203.49
0.09 0.01
+.00
1.00 0.000
0.10 0.01
0.12 + 0.01
UNR
50%
7263.02 = 117.
0.15 0.01
N/A
1.00 = 0.00
NIA
NIA
100k
14501.58 58 = 288.03
0.15 0.01
NIA
1.00 +: 0.00
NIA
N/A
HES
50E
522.76 1. 11.26
0.00 0.00
0.85 1 0.03
1.00 1 0.00
0.13 1 0.00
0.13 1 0.00
100k
847.54 + 39.
0.00 + 0.00
0.94 + 0.02
1.00 + 0.00
0.13 + 0.00
0.13 + 0.00
Table 3: Performance of the seven comparison methods on Task 3, at time step 50,000 and at time
step 100,000.
Period
C. Rogret
P. Regret
Questions
Treatments
MAE partial
MAE full
RCdgeUCB
50%
4512.49 1 56.48
0,09 I 0.00
0.44 1 0.03
1.00 1 0.00
0.28 1: 0.01
0.07 + 0.00
100k
8970,97 1. 123.73
0.09 0.01
0.55 4 0.03
1.00 1: 0.00
0.29 1: 0.01
0.07 1: 0.00
UnifomBOED
506
699.78 = 28.50 51
0,01 = 0.00
0.32 1 0.02
1.00 + 0.00
0.02 = 0.00
0.37 : 0.00
100k
1313:25 55.81
0.02 0.00
0.32 + 0.01
1.00
0.02 + 0.00
0.37
US
50k
354.61 =: 14.06
0,01 = 0.00
1.00 1 0.000
1.00 0.000
0.022 = 0.001
0.37 1 0.00
100k
616.99
23.70
0.00
1.00 1..00
1.00 0.00
0.02
0.37
TanDCH
50C
083.51 + 10.13
0.01 + 0.00
1.00 + 0.00
1.00 + 0.00
0.10 + 0.00
0.10 + 0.00
100k
1071.22 + 27.24
0.01 = 0.00
1.00 + 0.00
1.00 + 0.00
0.11 + 0.00
0.11 + 0.00
BayesLinUCBB
50k
1426.23 +: 19.73
0.02 0.00
0.36 + 0.05
1.00 = 0.00
0.10 = 0.00
0 = 0.00
100k
2523.30 + 13:31
0.02 0.00
0.38 + 0.01
1.00 = 0.00
0.10 = 0.00
0.10 = 0.00
UNR
50k
17757. 66 = 61.97
0.31 0.01
N/A
1.00 = 0.00
NIA
N/A
1004
35368. 73 175.97
0.35 1 0.02
N/A
1.00 1 0.00
NIA
N/A
HES
502
103.03 2.08
0.00 + 0.00
1.00 + 0.00
1.00 + 0.00
0:01 + 0.00
0.37 + 0.00
100k
108. 65 + 3.09
0.00 + 0.00
1.00 + 0.00
1.00 + 0.00
0.01 + 0.00
0.37 + 0.00
Table 4: Performance of the seven comparison methods on Task 4, at time step 50,000 and at time
step 100,000.
Period
C. Regret
P. Regret
Questions
Treatments
MAE partial
MAE full
RCdgeUCB
SOk
3353.60 115.50
0.01 0.01
0.13 1 0.04
1.00 0.00
0.63 1 D.D1
0.51 1 0.02
100k
4055.85 + 281.11
0.02 0.01
0.11 + 0.01
1.00 + 0.00
0.63 + 0.01
0.50 +
UnifomBOED
50%
1036.73 + 161.11
0.01 = 0.00
0.13 + 0.02
1.00 + 0.00
0.07 = 0.00
0.06 : 0.00
100k
1555.66 302.87
0.00
1.00
US
50%
666.12 1. 135.91
0,00 1 0.00
0.67 1.47
1.00 0.00
0.08 1 0.02
0.07 1 0.03
100k
787.97 279.39
0.00
0.67
LinUCB
506
1767.77 1 44.04
0.01 1 0.00
L00 1 0.00
0.39 1 0.00
0.51 1: 0.02
0.51 1 0.02
100k
1951,94 -5..90
0.00 0.00
1.00 0.00
1.00 0.00
0.50
0.50
BnyCsLinUUBB
50%
1052.06
+ 194422
0.01 + 0.01
0.13 + 0.02
1.00
= 0.00
0.51 = 0.02
0.50 + 0.02
1004
1674.66
347.80
0.00
0.03 N/A
1.00 0.00
0.51
0.50
UNR
50%
22788. 37 = 686.00
0.47 + 0.03
0.51 0.04
N/A
N/A
1004
45515.80
1403.41
0.46 0.03
0.47 0.01
HES
50k
572.48
1: 12.05
0.00 1 0.00
0.96 1 0.06
1.00 1: 0.00
0.08 1: 0.02
0.08 1 0.02
100k
822.55
39.06
0.00 1 0.00
1.00 1 0.00
1.00 + 0.00
0.09 = 0.00
0.09 = 0.01
Table 5: Performance of the seven comparison methods on Task 5, at time step 50,000 and at time
step 100,000.
Period
C. Regret
P. Regret
Questions
Treatments
MAE partial
MAE full
RidgeLICB
50k
9189.22 + 97.77.7 94
0.10 = 0.01
0.12 + 0.02
0.98 = 0.00
0.19 : 0.00
0.32 = 0.00
100k
14261 62 = 256.18 18
0.12 + 0.01
0.11 + 0.01
1.00 + 0.00
0.47 - 0.01
0.30 -: 0.00
UnifomBOED
50k
4412.02 +: 131.56
0.09 4 0.01
0.13 1 0.02
1.00 1: 0.00
0.04 : 0.00
0.03 1 0.00
100k
8550.20 1 242.70
0.09 1 0.00
0.12 1 0.01
1.00 0.00
0.04 + 0.00
0.03 - 0.00
US
50%
3137.06 + 1961 55
0.07 = 0.05
0.33 + 0.47
1.00 0..00
0.06 - 0.00
0.01 0.01
100k
0612.09 + 4158.32
0.06 0.04
0.33 + 0.47
1.00 0.00
0.06 + 0.00
0.04 + 0.01
LinUCB
50k
1176.87 + 13.78
0.00 = 0.00
1.00 + 0.00
1.00 100:000
0.35 = 0.00
0.35 - 0.00
100k
1325.94
16.11
0.00
0.00
1:
0.34
BnyesLinnUCB
50k
4433.80 1. 120.93
0.09 1 0.02
0.14 1. 0.01
1.00 1. 0.00
0.31 1 0.01
0.30 1 0.01
100k
8569.10
197.38
0.01
1.122100000
1:
0.30
UNK
506
10649984
206.16
0.22 1 0.01
NIA
0.47 1 0.07
NA
NAA
100k
21280.19
443.96
0.03
HES
50%
159.53 = 12.97
0.00 = 0.00
1.00 + 0.00
1.00 = 0.00
0.00 = 0.000
0.08 = 0.03
100k
530.65
12.91
0.00 0.00
1.00 - 0.00
1.00 + 0.00
0.05 + 0.00
0.06 + 0.00
Table 6: Performance of the seven comparison methods on Task 6, at time step 50,000 and at time step 100,000.
13

---

Under review as a conference paper at ICLR 2023
MAE full
Period
C. Regret
Regret
Questions
Treatments
MAE partial
RidgeUCB
50k
6513,33 1 256.42
0.10 0.01
NEA
NIA
8.14 1 0.01
0.11 1. 0.00
100k
11857 = 739.71
0,11 0.01
N/A
N/A
0.13 = 0.02
0.11 = 0.00
UmlommBODD
50E
1868.65 1 119.91
0,09
0000
SIA
NIA
0388 1 0101
0.08 1 0.00
100k
9512.92 + 290.32
0.10 + 0.01
VIA
N/A
0.10 + 0.00
0.08 + 0.00
100k
8060.10
4 508.46
0.08 0.00
N/A
N/A
0.09 4: 0.00
0.11 = 0.00
4x57.71
0.10
0.10
100k
0346.26 1 845.33
0.09 + 0.01
V/A
N/A
0.10 + 0.01
0.10 + 0.01
Bny
6162.81 + 108.11
0.10 0.02
0.10
0.10
1004
0075.07 4: 112.65
0.10 + 0.00
V/A
N/A
0.10 +: 0.01
0.10 4: 0.01
UNR
50k
9752.67 1: 438:224
0,20 0.02
NIA
NIA
NIA
NTA
100k
19132.77 71 8-12.94
0.21 0.03
N/A
N/A
NIA
NIA
HES
50k
1635.96 1: 302.34
0,09 0.01
NIA
N/A
0X09 0.01
0.11 0.01
100k
9220.06 = 557.22
0.01
NIA
N/A
0.09 0.00
0.18 = 0.11
Table Performance of the seven comparison methods on Task 7, time step 50,000 and time step 100,000.
0692
1420
D012
1310
2300
1000
1000
-0011
-0003
6.0
130
4:90
Figure 7: First line: Ground truth covariance matrix (estimated from the full population) in Tasks 1, 2, and 3 (from left to right). Second line: Recovered covariance matrix by HES in Tasks 1, 2, and (from left to right).
0.0
12-
18-
Figure Skewed normal density
Local linear
Random
Linear regression
Ridge regression
Flastic Net
Decision
MLP
forest
forest
regression
Tree
MSE
0.23 1 0.01 0.2310001
0.110001
0.21
0.25:
0.26 0.01
0.231001
0.27
Table 8: Performance of various learning algorithms the Charitable Giving experiment.
14


Reviews:
[{"review_id": "gcbXvprhWy", "reviewer": "Reviewer_XEp2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates a contextual bandit problem in which the decision-maker needs to actively acquire contexts in each decision epoch before the arm is selected. Ideally, the entire context vector should be revealed for optimal decision-making. However, budget constraints force the decision-maker to sequentially select a set of informative contexts to identify the optimal arm(s). Nevertheless, when context features are dependent, good decisions can be made even when a small set of contexts is observed. For efficient sequential query of the contexts, the paper proposes a decision-theoretic entropy search principle that identifies the context feature that provides the most information about the best action. After context acquisition is completed, arms can be selected by exploration-exploitation algorithms. The proposed acquisition is compared against several baseline methods via synthetic and semi-synthetic simulations.", "summary_of_the_review": "This paper proposes an algorithm for the survey bandit problem. The problem itself has several potential practical applications. While the acquisition strategy is intuitive, theory and experiments do not fully reinforce the need for developing this new algorithm. A thorough theoretical analysis of the regret and experiments done using Q_allow different from the optimal Q_allow parameter will benefit the current work.  ", "strength_and_weaknesses": "Strengths: \n\n-Survey bandit has interesting practical applications ranging from medicine to education. \n\n-Decision-theoretic entropy search is an intuitive method for the sequential selection of questions.\n\n-Proposed model can handle heterogeneous user populations and nonlinearities.  \n\n-Detailed experiments are performed. The proposed method is compared with several other benchmarks adapted to the survey bandit problem. \n\n-Limitations are discussed.\n\nWeaknesses: \n\n-No theoretical analysis or convergence guarantees of the proposed method. The lack of theoretical results greatly hinders confidence in the algorithm. I think that theoretical regret analysis is an essential component (both lower and upper bounds on the regret) for a paper that uses Bayesian optimal experimental design techniques. \n\n-Some of the performance metrics used in experiments are unclear. This raises several questions about experimental comparisons, which should be carefully addressed (please see comments in the next section). \n\n-Scalability of the algorithm, both in terms of computing power and the number of required users, is unclear. Medicine can greatly benefit from sequential queries; however, convergence can still take a long time in terms of the number of users.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HCqL8_tlH65", "reviewer": "Reviewer_DagW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study the survey bandit setting, a scenario in which we are required to select sequentially the contextual information we want to be disclosed and, then, to select an option among a finite set. The authors used techniques from the Bayesian Optimal Experimental Design to build an algorithm for sequential selection of the context and of the option. The authors compared their approach with some baselines present in the literature and adapted for the setting.", "summary_of_the_review": "The topic is suitable for the ICLR venue, but the proposed method requires a theoretical analysis before being published.", "strength_and_weaknesses": "I think that the setting is interesting, but the work is not complete. It is true that from the experiments the authors provided that their approach seems to be effective, but no theoretical properties of convergence of the method are provided. It is common that, in practice, some heuristic methods are able to outperform the theoretically founded ones. However, without any theoretical results, we are not assured that the method will at least converge.\n\nMoreover, there are still some questions about the experimental setting. For instance, the fact that the proposed method is able to outperform an oracle should be commented on and adequately motivated.\n\n\nMinor comments:\n\n\"The decision maker’s goal ... in expectation.\" this is only a partial goal of the user. I think you should define more in detail this task and the overall goal.\n\nIn the experimental section, you should define the metrics in a formal way.\n\nIt is not clear to me how it is possible that the proposed method is able to outperform the LinUCB even if it has far more information than what has been proposed.\n\n\"During this period, ... one treatment per user.\" Is this phase required by all the methods? Why 30?\n\n\"Only LinUCB, HES, and RidgeUCB ... number of users.\" The comments in Figure 3 (top) do not correspond to the actual figure. I do not know which one of the two is the one to trust. The same holds for the bottom figure.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Ct5U5sZ03Jr", "reviewer": "Reviewer_5EZr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper tackles the survey bandit setting in which the decision maker has a limited budget of questions to ask a user, observes the answers to these questions (constituting the features of the user), then recommends a treatment and observes the outcome. The questions to ask are chosen with a decision theoretic entropy search policy while the treatment is subsequently chosen with an $\\epsilon$-greedy policy. The distributions over answers and outcomes is modeled with a GMM. The algorithm is compared to many baselines in different settings.", "summary_of_the_review": "The paper is technically solid and provides an extensive empirical evaluation. However, it suffers somewhat from a lack of significant technical novelty as the core of the algorithm was obtained from (Neiswanger et. al., 2022) with minimal modifications required to make it work for the survey bandit setting.", "strength_and_weaknesses": "Strengths:\n1. The setting is well motivated.\n2. The algorithm is relatively straightforward.\n3. The choice of GMM for modelling distributions over answers and outcomes is well justified.\n4. The experiments section is excellent.\n\nWeaknesses (more of clarifications):\n1. Currently the algorithm is broken down into two parts, choosing a question with EHIG and then choosing a treatment with an $\\epsilon$-greedy policy. Have the authors considered using the EHIG approach to choose both questions and treatments jointly? I imagine that this might lead to large cumulative regret if regret is measured based on the algorithm's chosen treatments, but perhaps this approach might be better if regret is measured based on the treatment with the highest posterior mean (i.e., immediate regret in (Hernandez-Lobato et. al., 2014)).\n\n2. Does the LinUCB baseline take advantage of the distributions obtained from the GMM? If not, did the authors consider using the same $\\epsilon$-greedy policy to choose treatments but with full access to answers instead? This seems like a more appropriate baseline to compare to see \"what can be achieved when there is no budget constraint on question selection\". I would expect such a baseline to always beat HES, while currently it seems HES beats LinUCB in some settings.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-K4TwZnGYwZ", "reviewer": "Reviewer_sGDT", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies a variant of the stochastic contextual bandits problem, where contextual information is not given but can be collected by asking a finite set of questions. The authors refer to this problem setting as *survey bandit*. The goal is to learn a policy that asks a series of questions that give the maximum information about the user (context) so that the policy can choose the best action for the given user and minimize the regret (the difference between the maximum achievable outcome and the policy's outcome).\n\nThe authors propose an algorithm named HES that uses the Bayesian optimal experimental design (BOED) approach to identify the next best question that gives the most information about the given user. They also validate the different performance aspects of the proposed algorithm on synthetic and real-world datasets.", "summary_of_the_review": "This paper significantly overlaps with my current work, and I am very knowledgeable about most of the topics covered by the paper.", "strength_and_weaknesses": "**Strengths of paper:**\n1. The problem setting of *survey bandits* (gathering information about unknown contexts) is interesting. The proposed algorithm allows decision-makers to gather information about the unknown context by efficiently asking a sequence of questions.\n\n2. The authors empirically validated the proposed algorithm's performance on synthetic and real datasets. \n\n**Weakness of paper:**\n1. Why not gather all possible information about context: Let's consider the treatment recommendation example used in the paper. Before recommending any treatment, the doctor must collect all possible information about the patient (except duplicate information). Because the cost of recommending the wrong treatment can be very high. Therefore, the authors must give a proper motivation for asking limited questions.\n\n2. Finding the set of questions that gives maximum information about the user is an NP-hard problem (subset selection). However, selecting questions greedily one after another can be a good alternative, but its trade-off needs to be discussed.\n\n3. Instead of using the decaying $\\epsilon$-greedy strategy for action selection, authors can use the action strategies like upper confidence bound or Thompson sampling, which are much more efficient in dealing with exploration and exploitation.\n\n4. Confusion about Line 1 after Section 2.1:  Assuming the known joint distribution (seems to be a typo in Line 1) of the answer and outcome can be impractical in many applications, and one has to estimate the distribution using observed data (Line 2). However, it seems that HES assumes the joint distribution is known (as doing the sampling in Line 7).\n\n4. No theoretical guarantee: No theoretical guarantee of how the proposed algorithm will work compared to oracle policy (which selects the best questions in each round). Further, in the experiments, it is not clear whether the optimal treatment (action) uses all questions (full context) or the best subset of questions. Different regret notions need to be defined formally to avoid any confusion. \n\n5. Minor issues in the algorithm: $\\alpha$ is an algorithm input. It is unclear how the value of alpha is chosen and how it influences performance. For the first user, $D$ will be an empty set, so it is unclear how the $\\theta_u$ will be computed.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject