Causal Contextual Bandits with Targeted Interventions
Authors: Chandrasekar Subramanian
Balaraman Ravindran
Venue: ICLR 2022 Poster (2022)
Keywords: causality
contextual bandits
causal inference
bandits

Abstract: We study a contextual bandit setting where the learning agent has the ability to perform interventions on targeted subsets of the population, apart from possessing qualitative causal side-information. This novel formalism captures intricacies in real-world scenarios such as software product experimentation where targeted experiments can be conducted. However, this fundamentally changes the set of options that the agent has, compared to standard contextual bandit settings, necessitating new techniques. This is also the first work that integrates causal side-information in a contextual bandit setting, where the agent aims to learn a policy that maps contexts to arms (as opposed to just identifying one best arm). We propose a new algorithm, which we show empirically performs better than baselines on experiments that use purely synthetic data and on real world-inspired experiments. We also prove a bound on regret that theoretically guards performance.

Published as a conference paper at ICLR 2022
CAUSAL CONTEXTUAL BANDITS WITH TARGETED IN- TERVENTIONS
Chandrasekar Subramanian' Balaraman Ravindran'. Robert Bosch Centre for Data Science and Artificial Intelligence 2 Department of Computer Science and Engineering Indian Institute of Technology Madras, Chennai, India
sekarnet gmail iiriiii.o com, ravi@cse. aitm.ac.in
ABSTRACT
We study contextual bandit setting where the learning agent has the ability perform interventions on targeted subsets the population, apart from possess- ing qualitative causal andeiinformation. This novel formalism captures intricacies in real-world scenarios such as software product experimentation where targeted experiments can be conducted. However, this fundamentally changes the set of options that the agent has, compared to standard contextual bandit settings, ne- cessitating new techniques. This is also the first work that integrates causal side- information in a contextual bandit setting, where the agent aims to learn a policy that maps contexts to arms (as opposed just identifying one best arm). We pro- pose new algorithm, which we show empirically performs better than baselines on experiments that use purely synthetic data and on real world-inspired experi- ments. We also prove bound on regret that theoretically guards performance.
INTRODUCTION
Contextual bandits have been used as natural frameworks to model interactive decision making sce- narios such as recommendation systems (Liu et al., 2018). marketing campaign allocation (Sawant al. 2018) and more (Bouneffouf Rish 2019). In this framework, the learning agent repeatedly interacts with an environment with the aim of learning near-optimal decision policy that maps context space to set of actions (also referred to as arms or interventions)] In the standard stochas- tic variant, in each round of interaction, the agent observes a context from the environment and, once the agent chooses an action, the environment returns a sampled reward that a function of the current context and chosen action (Lattimore & Szepesvári 2020). The agent's objective is to mini- mize some meaningful measure of closeness of the policy to optimality (see Lattimore Szepesvári 2020 for some standard definitions).
One of the key issues in the wide application of contextual bandits (and reinforcement learning, in general IDulac-Arnol et al. 202Tb) is their need for large number of samples that are costly to actualize in practice. For example, each arm might correspond to performing a product experiment on users conducting specific medical intervention. However, we show that there nuances in real-world situations which - though not fully captured by the standard formulations of contextual bandits modeled and leveraged, allow us build methods that can improve the rate which good policies can be identified.
motivating example Consider asses-assistance software agent that is learning suggest campaign that is optimal for given sales lead (defined by set of features). With software products, there is often an opportunity to conduct experiments with variants the software on defined subvets of the population of users (each specified by set of characteristics, or context variables) to learn about resulting metrics; see Google (202I) for an example. We can think of these experiments as constituting training phase. More specifically, the agent, for example, can conduct a campaign
We use the term intervention here because actions or arms in a (contextual) bandit setting can be interpreted as Pearl do() interventions on causal model (Zhang & Bareinboim 2017 Lattimore al. 2016). See Pearl 2009 2019) for more discussion the do() operation.

---

Published as a conference paper at ICLR 2022
(i.e., the intervention) specific subset of users (for example, the context value os=iOS could define a subset) and observe the outcome. Thus, instead of necessarily performing an intervention on randomly sampled user coming from the natural population distribution, the agent can instead choose to target the intervention on a randomly selected user with specific characteristics (as defined by an assignment of context variable values). This type of interventions, which we call targeted interventions, fundamentally changes the set of options that the agent has in every training round.
In addition, the training phase often happens in more lenient environment where the agent might have access to auxiliary context variables (such as IT (T-spend) that are unavailable in the evaluation phase. Further, there is also causal side-information sometimes available. For instance, we might know that email 1 sub ject causes openemail, 1. and not the other way around. Encoding this qualitative side-information as causal graph can help the agent make use of this structure. [atti-] more et al. (2016) and Yabe et al. (0188) demonstrate this in the best-arm identification case. After training, there is an evaluation phase (e.g., when the agent is deployed), where the agent observes the main context variables and decides action; its regret performance is measured at this point.
Our framework Our framework captures the above intricacies (which are not restricted to software product experimentation). The formal treatment is in Section 2 we present overview here. The agent has T rounds of interaction that act as the training phase, followed by a (T + 'tth round on which it is evaluated. In each of the T training rounds, it has the choice perform either targeted intervention or a standard interaction. Further, in addition to the main context variables, the agent can observe (possibly empty) set of additional auxiliary context variables during training: these auxiliary context variables are not observable during evaluation. All variables are made available to the agent at the end of every training round (this similar to Lattimore et al. (2016)) The agent also has access to a causal graph that models the qualitative causal relationships between the variables; there are very few assumptions made on this graph (discussed in Section 2.I). The causal graph allows a factorized representation of the joint distribution of the variables, and as result, enables information leakage i.e., updating beliefs about several interventions after every single intervention. Also, importantly, we allow context variables to be categorical, and therefore the usual assumptions that enable generalization of the learned policy across contexts, such as lincarity (c.g., in Dimakopoulou et al. 2019)) become invalid.
The agent's problem is one of sample allocation - how to allocate samples across the T training rounds so to learn policy that minimizes regret in the (T + 1)'th round that represents the evaluation phase. In the evaluation phase, the agent observes the main context variables from the environment, against which it chooses action and receives a reward much like in standard contextual bandit setting. Since targeted interventions are restricted to the training phase, it intro- duces difference between the training and evaluation phases. The agent's challenge, therefore, is to learn policies that minimize regret in the evaluation phase using samples it collects in the training phase (from a combination of standard interactions and targeted interventions). The algorithm we propose utilizes a novel entropy-like measure called Unc that guides this sample allocation in way that also exploits the information leakage.
1.1 CONTRIBUTIONS
In this paper, we formalize this modified setting, which we call "causal contextual bandits with tar- geted interventions", provide a novel algorithm and show both theoretical and experimental results. Specifically, our contributions are:
We formalize the more nuanced contextual bandit setting described above (Sec. 2 This is the first work that we know of that formulates a contextual bandit setting with causal hide-information. This is also the first paper we are aware of that introduces targeted inter- ventions in a contextual handit setting.
We propose a new algorithm based on minimizing a novel entropy-like measure (Sec.
3.1
We prove a bound on its regret, providing a theoretical guard on its performance (Sec.
3.2)
We show results of experiments that use purely synthetic data (Sec. 4.1 The results demonstrate that our algorithm performs better than basclines.
We also run experiments that are inspired by proprictary data from Freshworks Inc. (Sec. 4.2). providing evidence of our algorithm's performance in more realistic scenarios as well.
2

---

Published as a conference paper at ICLR 2022
Our motivation comes from real world settings where experiments costly; therefore, interested in empirical behavior when the training budget T is relatively small.
1.2 RELATED WORK
Causal bandits have been studied in literature recently (Lattimore et al. 2016 Sen et al. 2017
Yabe et al. 2018 Lu et al., 2020) and they leverage causal side-information transfer knowledge across interventions. They, however, have been studied only in best arm identification setting, with each arm modeled as an intervention on a set of variables: the objective is to learn a single best arm. Our setting differs significantly since the agent attempts to learn a policy (by which we mean a mapping from contexts to arms) instead of single best arm. Therefore, while the agent can perform targeted interventions that specify both the context and action, it is still attempting to learn an optimal context-action mapping.
The contextual bandit literature is well-studied Zhou 2016) and Lattimore & Szepesvári (2020) for surveys), and has taken various approaches to enable knowledge transfer across contexts. For example. Diimakooulouu et al. (2019) assume expected reward is linear function of context, while Agarwal et al. (2014) make assumptions about the existence of a certain oracle. However, there has not been work that has looked at contextual bandits which utilize causal side-information to transfer knowledge across contexts, or considered targeted interventions in the space of options for the agent. Our method utilizes the information leakage that the causal graph provides to not just learn about other interventions after every intervention, but also to be smarter about the choice of targeted interventions to conduct.
way
Another related area is active learning (Settles 2009). In active learning, supervised learning agent gets the option query an oracle actively to obtain the true labels for certain data points. However, it is in the supervised learning setting where the agent receives true label feedback, whereas in our setting the agent only receives bandit feedback (that is, only for the action that was taken). Never- theless, our work can be thought of as infusing some elements of the active learning problem into the contextual bandits setting by providing the agent the ability to perform targeted interventions. There has been some work investigating the intersection of causality and bandits with the aim of transfer learning. Zhang & Bareinboim (2017) study transfer of knowledge from offline data in the presence of unobserved confounders, in non-contextual setting. As can be seen, this differs significantly from our setting.
2 FORMALISM
We assume that the underlying environment is modeled as a causal model M, which is defined by directed acyclic graph G over all variables - i.e., the variable to be intervened (X), the reward variable (Y), and the set context variables (C) - and a joint probability distribution IP that factorizes over G (Pearl) 2009; Koller & Friedman| (009). C is partitioned into the set of main context variables (Ctar) and the set of auxiliary context variables (Cother). G is sometimes called the causal graph finite, known set of values; note that this is quite
or causal diagram of M. Each variable takes generic, and allows for categorical variables. An intervention do = x) on M involves removing all arrows from the parents of X into X, and setting X = (Pearl 2009 The agent has access only to G and not to M: therefore, the agent is not given any knowledge a priori about the underlying conditional probability distributions (CPDs) of the variables.
We specify a targeted intervention = I conditioned on context Cter = for succinctly by (ar, cfor). While standard interventions Pearl 2009) result in distribution of the form IP(, do(x))) targeted interventions result in IP. do(x), Clar clar). Table I summarizes the key notation used in this paper.
The agent is allowed T training rounds of interaction with the environment, at the end of which it aims to have learned a policy ò val(Cter) - val(X). Specifically, in each of the T training rounds, the agent can choose to either
(Standard interaction) Observe context carr ~ P(Ctar), choose intervention z, and observe (y, cother) IP(Y, Cother do(x)) e elar), (or)
3

---

Published as a conference paper at ICLR 2022
Table 1: Summary of key notation
Symbol/Notation
Meaning
X
variable that will be intervened upon reward variable
Y
Ctar, Car,Cohher
set of main context variables and set of auxiliary context variables, respec- tively; so the set of all context variables is C Clar U Cother (u., Ci....) ..... random variable; e.g., C1 or X
Capital letters
Small letters
random variable's value; e.g., e1 or x
Small bold font
vector of random variable values; e.g., clar denotes specific choice of values taken by variables in Cfar
(ar, clar) P. E Dvlpa
specifies targeted intervention x = subset defined by C = clar estimate of distribution PP and expectation E based on current beliefs beliefs (vector of Dirichlet parameters) about parameters of (VVp) ((4) Vilpy, the entry corresponding to V - v.
val(V)) val(V)
set values taken by the variable V, and set of variables V, respectively.
Nv, Nv
|vva(V)),, val()) [
pav
value of variables in PAv, the parents of V. For Y, we let PAy denote its parents excluding X to keep proof easier read.
number of training rounds
fraction of rounds in Phase 1 of training if a is an assignment of values to A, then aB) is assignment of those values to respective variables B A. for readability, we use them on vectors as well, where there is no ambiguity.
aB))
Set operations
(Targeted intervention) Choose intervention and a target subset given by context values Clar = clor and observe (y, cather) ~ IP(Y, Cother do(x), clar)
where, when there is no ambiguity, we use IP interchangeably to mean either the joint distribution or a marginal distribution. Note that in both modes interaction above, the intervention is only on X; they differ, however, in whether the agent observes the context values from the environment or whether it chooses the context values on which to condition the intervention.
After training, the agent is evaluated in the (T + 1)'th round. Here, the agent is presented query context ear P(ttar) to which it responds with an action x @(clar) using the learned policy, and receives a reward y ~ P(Y do(x)) c'arr from the environment.
The objective of the agent is to learn a policy à that minimizes simple-regren, which is defined as: Regret
Σ WWater [etar]] P((tar)== Σ Regr .P(ctar) clur
cluc
where 6* is an optimal policy, uCarr A (ctar)); car] etar] and flctor - {[)]do((((tar)) darr
2.1 ASSUMPTIONS
We are interested in DAGS G where there is an edge X Y, and no other directed path between X and Y; that is, X directly affects Y; there is no context variable caused by X. This models the natural situation we encounter settings such as recommendation system where click-through rate (Y) of user is directly affected by the user's features (the context) and the recommendation (X); the recommendation does not cause any contexts, so doesn't have a path Y through them. We assume that there are unobserved confounders (UCs); but purely interactive bandit settings, such as ours, are robust to direct UCs between and since actions can be interpreted as sampling from the P(. (()((()))) distribution (Bareinboim et al. 22055] Guo et al. 2020).. We make an additional assumption to simplify the factorization in Section 3.2 (AI) confounds C' E Ctar and Y} = C. E Ctar_ A sufficient condition for (A1) be true if Caar is ancestral (i.e., Ctar contains all its ancestors). This assumption does not preclude UCs (for example, the graph used the synthetic experiments in Section could have a UC between X and Y), and can be relaxed in the future.
4

---

Published as a conference paper at ICLR 2022
3 SOLUTION APPROACH
3.1 ALGORITIIM (UNC_CCB)
Algorithm la: Training phase of Unc CCB
Data: Graph 9; fraction of Phase I rounds. Initialization: For all V E C (Y),, set Ovipa, = (1,..., 1), for all values of pay-
(Phase for 1... a''' do
Observe context ctar (P((ter)
Choose I val(X) uniformly at random
Observe (y. cother) IP(Y, Cother do(x)) clar) for V in C do upplateBcliessV,cCPAAA...1) end
// //denote ctar Ucteer by
end
10
(Phase 2) for f al + do
Choose T, car as:
arg min xxval(X), etor eval(Ctar)
Σ
Unc [E[))d)(z'), clart| x, clar)
of x'Eval(X) X), (Cal(
Do targeted intervention (Ir, clar) and observe (y, cather) ~ (ooher)do(x)) for V in Cother do updattBBllieexx,((PPAA)))..
12
14
end
updateBeliefs(Y, (4
16
end
Result: Final set of beliefs for all V, pay: {..., O Oylpa Procedure updateBeliefs(/, pay,
VV) + -(())
19
pay +1
Algorithm 1b: Evaluation phase of Unc CCB
Data: Graph G. learned beliefs { {... VVlpa ...) user context be decided Aar
for every V. pay do
for v E val (V) do
O E. Vipay
Set PVV = v/pay)
end
end for x E va((X) do
Compute (xx A [lo)d)( clar] using PP in Equation
end
Result:
Return ((ctar) A arg max, (xx clar)
We call our proposed algorithm Unc.CCB, The training phase of Unc CCB (given as Algorithm lab consists of two phases. In each round of Phase I (a fraction of the rounds), it observes context from the environment, then uniformly at random chooses an action, and finally observes the remaining variables. The observed values are used to perform standard Bayesian updates the beliefs about parameters all relevant CPDs. Since we do not assume any a priori beliefs for the agent, this uniform exploration helps the agent enter Phase with reasonable starting beliefs.
5

---

Published as a conference paper at ICLR 2022
In Phase 2 (the remaining (1 a.) fraction of the rounds) of training, the agent tries to allocate tar- geted interventions optimally. To this end. needs to trade-off between exploring new contexts and gaining more knowledge about already -eepooe-e contexts, while taking into account the information leakage resulting from the shared pathways in the causal graph (or equivalently, shared CPDs the factorized representation of IP; Appendix E discusses related subcase). The novel, entropy-like, Unc measure (discussed below) helps guide the agent in this decision in every round. Algorithm [b specifies the evaluation phase of Unc.CCB, where the agent is evaluated on simple regret.
Intuition behind the Unc measure As mentioned before, performing a targeted intervention given by (x, clar) would allow the agent to update its beliefs about effects of other targeted interventions (I',
(a',ctar)) clar)). Intuitively, we would want the algorithm to allocate more samples to those targeted inter- ventions that are most informative about the most "valuable" (in terms of reward Y) targeted inter- ventions. Unc captures this intuition by providing measure of the effect on the agent's 's knowledge of [E [dd]((()") caar] when a targeted intervention (zr, c²er) performed. The agent, then aggregates this over all possible (x', ,etrr), providing a measure of overall resulting knowledge from targeted Iab.
intervention (x, clar); this helps guide its sample allocation (see Line 11 of Algorithm
Definition of the Unc measure We model the conditional distribution IP(V ppay for any variable V as a categorical distribution whose parameters are sampled from a Dirichlet distribution. That is, P(V|pay)
Cat(V; ; b1, b,), where (b1, ..., b,)) Dirc(Ov pap). Here (ylpay is vector of length, say, r. Let denote pay denote the i'th entry of Ovipay. We define an object called Ent that captures a measure of our knowledge of the CPD:
0 P [d]
Ent( p)a)) 2 -
Eg Og pay Lil ΣS Ipay Di]
Let the parents of V be PAy (U1, Up): suppose they take particular set of values pay (Ui,..., Up). We define that CPD P(V P(V[pay) unaffected by targeted intervention (x, ctar) if there exists E p} such that either (1) U; is X and u; * or (2) U; E Ctar and c (Ui) & u, In other words, the CPD PVV ((yl)ay) is unaffected by (x,,²ar) ) if doing this targeted intervention and update beliefs about P(V (ay) using
observing all variables (x, clar cother) does not enable
knowledge of G. Now, define
Ent(PP(V pay if pay) is unaffected by (zz, ctar) En (P(V) pay:)), otherwise
Ent(PP(V pay) car)
where En is computed by averaging the resulting Ent values over the possible belief up- dates the agent might make after performing (a., caar). That is, Ent" (P(VIpay))
E Ent
Cat(bl....,. where (b,...,,b,) Dirc (..., (v.,,
1]. Bylpay [c] + 1, Oylpa, 1!.....
Letting c' denote ctart U othhrrt we can now define Unc which captures our knowledge of E[Y(do(x'), clarr) if we perform some other targeted intervention given by (x.c c!ar):
Unc (B(Y|do(x')) c c carr) A
Σ
Ent(P(V]d (*a*)
euther! Eval(
VECulker
Ent(P(Y|2' ('(p) .P(c') -Ir d
3.2 REGRET BOUND
Theorem 3.1. For any 0 < < 1, with probability
2 8-8,
2
2Nxx(Nc + (C))
Regret S 3R Paya ptar
In
all' Nx
P(pay. appay:co ctar)
-xX.PAY
5
+3
Σ
Epa otar
2
In
(2(Ne + 1C
(1)
-
8
CEcother

---

Published as a conference paper at ICLR 2022
where
aT 2
NPAc (No + =(()) EX,PAv = V
af
In NNxNPA (Ne (CI)
CPAc
In
5
2
Proof. Due to space constraints, we only provide proof sketch here. The full proof is provided in Appendix A as part of the Supplementary Text. For readability of the proof, we assume that and all variables in C. are binary, whereas X can take any finite set of values. Under Assumption (A1) described in Section 2.1 we can factorize as follows:
E|y [ chor]
Σ
PP(Y = 1|2,
II cEcother
P(C de((Ac))
(2)
eother (valerut
where e denotes car Uc The proof first bounds errors of estimates of P(Y = 1|,, c(PA)) and P(C cle(PAc) with high probability using union bounds, concentration bounds, and the fact that the number of rounds which the agent observes any set context values lower bounded by the number of times it sees in Phase 1. We also make use of the fact that all variables are observed after every round. We then aggregate these bounds of individual CPD estimates to bound the overall estimate of (o)))) clar), and then finally bound regret by utilizing the fact that the algorithm chooses arms based on the estimated E.
Discussion Theorem 3.1 bounds the regret (with high probability). Note that
00
Regret + 0, which shows that the regret bound has desirable limiting behavior Further, regret is inversely related to vT. similar to other simple-regre algorithms such as in Lattimore et al. (0166) However, other terms that are a function of the space of possible interventions (Nc are different since we in a contextual bandit setting (whereas Lattimore et al. (2016) is non-contextual); more specifically, regret related proportionally strictly tighter than this. We prove the bound primarily to provide a theoretical guard on regret; we do not claim improved regret bounds since there is no comparable simple-regret contextual bandit regret bound. We show improved performance over baselines empirically in Section 4
Nx Nc In (Nx
fact, our regret bound is
4 EXPERIMENTAL EVALUATION
Since there is no setting studied previously that directly maps to our setting, we adapt existing multi-armed bandit algorithms to make use of causal side-information and targeted interventions in a variety of ways to form a set of baselines against which we compare our algorithm's performance.
The baseline algorithms are the following. Std.TS and Std UníExp follow the standard bandit interaction protocol during training observe context, choose action, receive reward. They treat each for as a separate problem and learn an optimal arm for each; they differ in that Std. TS uses Thompson Sampling (Agrawal & Goyal 2012) for each clar problem, whereas Std UniExp does uniform exploration over val(X). The other set of algorithms are TargInt_TS, Targlnt.UniExp and Targlnt.TS.UniExp. These treat the space val(X) val(Ctar) as the set of arms for targeted interventions. Targint TS performs Thompson Sampling over this space, and Targint UniExp per- forms uniform exploration over this space. Targint TS UniExp is a variation of Targint TS that, with some probability P chooses a random targeted intervention; this infuses a controlled degree of uniform exploration into Targint_ All five algorithms update CPD beliefs after each round. No baseline is strictly stronger than another; their relative performance can vary based on the spe- cific setting. We also compare against a non-causal version of algorithm Std_ TS, which we call NonCausal.Std.TS. to provide one non-causal baseline (i.e., which does not utilize the causal iideinformmation.
The evaluation phase for each baseline algorithm is analogous to Algorithm lb given a car, the action with the highest expected reward, based on beliefs the end of the training phase, is chosen.
There is technical requirement keep the denominator in Eq 1 greater than 0; however, it casy to see that this only requires that 7 > constantt, so there is no impact on asymptotic behavior. We choose this probability he 0.5 for the plots. There is more discussion this in Appendix F.

---

Published as a conference paper at ICLR 2022
KonCausal
NonCausal TS
SS
Std, UniExp
Shd, UniExp
Tanglnt_
Margint Marginn_Uiits UniExo
Targhtt, UniEpp
Targint, T5, UnlExp
Targint, T5, Un.ExE
Unc (Ours)
Regrect
Number of training rounds 7 jas fraction (MNNge))
Number training rounds
Figure 1: Mean regrets for Experiment I (Sec- tion 4.1. Regret normalized [0, 1] and T as fractions of Nx Ne
Figure 2: Mcan regrets for Experiment 2 (Sec- tion
4.1 PURELY SYNTHETIC DATA
We consider a causal model M whose causal graph G consists of the following edges: C1 - Co. Co + X, Co + Y, X + Y. We assume that Cter {Ci} and that Cother {Co}. We choose the fraction of Phase rounds a 0.5 More details and code are in the Supplementary Material. Additional experiments, analyzing the reason for why our algorithm performs better than baselines, are in Appendix B.
empirically found that to be a good choice.
Experiment Given the wide range of possible settings arising from different parameterizations of M. the first experiment seeks to answer the question: "what is the expected performance of our algorithm over a set of representative settings?". Each setting can be interpreted naturally when, for example, think of (ter as the set of user features that recommendation agent observes post-deployment. The settings are chosen to capture the intuition that, typically, the agent sees high- value contexts (i.e., contexts for which, if the agent learns the optimal action, can fetch high rewards) relatively less frequently. say, 20% of the time, but there can be variation in the number of different Cter values over which that probability mass is spread and in how "risky" they are (for example, very low rewards for non-optimal actions). In each run, the agent is presented with randomly selected setting from this representative set. Results are averaged over 300 independent runs; error bars display 11.96 standard errors. For details on specific parameterizaatins, refer Appendix D.
Figure D provides the results of this experiment. The axes are normalized since the representative set of settings could have different ranges for T and for regret. We see that our algorithm performs better than all baselines, especially for lower values of T. This, fact, a recurring theme our algorithm's performance improvement is more pronounced in low T-budget situations, which, as we stated in Section [.]] is what we are interested in. Further, Appendix C contains plots for two individual settings from the set, where Std TS and Std UniExp perform significantly better than Targint_TS. TS, Targint_UniExp and Targint_TS TStTTS__UniEEE Tn_nnixxp, and another where is the converse; in contrast, our algorithm performs close the best baseline both. The intuition behind this is that the Unc measure incentivizes exploring new context values (due to its entropy-like nature) while weighting more the contexts that are likely to yield more rewards (based on our current estimates). Also, as expected, JonCausal.Std.I1 performs the worst as it ignores the causal graph.
Experiment 2 To ensure that the results are not biased due to our choice of the representative set, the second experiment asks "what happens to performance when we directly randomize the parameters of the CPDs in each run, subject realistic constraints?".. Specifically, in each run, we (1) randomly pick an E {1,.... [Ne, } (2) distribute 20% of the probability mass randomly over C1 values (I,..., i}. (3) distribute the remaining 80% of the mass over C₁ values {i+1, Nc, J. The Ci values in the 20% bucket are higher-value. while those in the 80% bucket are lower-value. Intuitively, this captures the commonly observed 80-20 pattern (for example, 20% of the users contribute to around 80% of the revenue), but randomizes the other aspects; this gives estimate of how the algorithms would perform on expectation. The results are averaged over 100 independent runs; error bars display +1. .96 standard errors. Figure shows that our algorithm performs better than all baselines
8

---

Published as a conference paper at ICLR 2022
in this experiment, with more pronounced improvement for the smaller values of T. For instance, when T = 24, our algorithm's 's mean regret is around 35% lower than that of the next best baseline.
4.2 CRM SALES DATA-INSPIRED EXPERIMENT
This experiment seeks answer the question: "how does the algorithm perform on realistic scenarios?". We setup the experiment inspired by real world scenario. Consider a bandit agent that could assist salespeople by learning to decide how many outgoing calls to make in an ongoing deal, given just the type of deal (new business, etc.) and size of customer (small, medium, etc.), so as to maximize reward metric (which we call the 'expected deal value'). Deal type affects the reward via the source of the lead (for example, chat). The trained agent would be deployed internally or to the company's 's clients, where it would generally not have access to lead source. The causal graph relating these variables is given in Figure Bal which was obtained using domain knowledge. 'Deal type' and 'Customer size' are Clar, 'Lead source' is Cother, '# outgoing this causal
Experiment 3
calls' is X, and 'Exp. deal value' is Y. The parameters of each CPD corresponding graph was calibrated using proprietary sales data from Freshworks Inc., after some adjustments using domain knowledge (for example, where there were coverage gaps). Note that the algorithms use only the CPDs and not this raw data; in any case, we make the dataset available in anonymized form wtthttps://ddon orgg O. 52 82111 zenodo. 5540348 undeer
under the 'CC BY-NC 4.0' license.
Further, we also do a warm-start for all algorithms to account for the fact that, in practice, there is often some starting beliefs about the CPDs from past data, domain knowledge, etc., which can be encoded into the agent's prior beliefs 4 Specifically, we ran pure random exploration for 15 rounds the beginning of each algorithm and updated all CPD beliefs; this simulates warm-start. Due to this, we used a = 0 for our algorithm. Results are averaged over 50 independent runs; eπror bars display +1 1966 standard errors. Figure 3 shows that our algorithm performs better than all baselines in this realistic setting as well. The Supplementary Material provides the code.
Nonciasall Std, T5 Std.TS
Std Un
type
Targi nt
Thrg nt_ Un
Tara nt. T5 Unitap
Unc. CCB (Ours)
Customer
Lead source
size
32-
outgoing calle
Exp. deal
value
Number of training rounds 7
(a) Causal graph.
(b) Mean regrets.
Figure 3: CRM sales data-inspired experiments (Section 4.2
CONCLUSION AND FUTURE DIRECTIONS
This work presented contextual bandits formulation that captures real-world nuances such as the ability to conduct targeted interventions and the presence of causal side-information, along with novel algorithm that exploits this to achieve improved sample efficiency. In addition synthetic experiments, we also performed real world-inspired experiments set up using actual CRM sales data.
A useful direction of future investigation is the development of algorithms when is unknown or partially known. Another important direction is the development of methods robust to distributional shifts. Distributional shifts have been studied for prediction tasks (Magliacane et al. 2018 Gong
et al. 2016) and for causal effects (Bareinboim & Pearl 2014 Correa & Bareinboim, (020);: it is an interesting question to study this in our setting, when 9 remains the same between training and evaluation but M changes.
*Other works such as Dimakopoulou al. (019 and Liu 2018 have used warm starting well.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
This work was partly funded by Freshworks Inc. through a research grant to Balaraman Ravindran and Chandrasekar Subramanian.
REPRODUCIBILITY STATEMENT
The full proof of Theorem 3.1 is provided in an appendix the end of this PDF file (after the ref- erences) as part of the Supplementary Text. The source code of all the experiments in the main paper, along with a README on how to run them, is provided as part of the Supplementary Ma- terials in file named Supplementa SateeentalCoodeeaaeeeeeee gorithms use only the CPDs and not the raw data, the dataset used calibrate the real world- inspired experiments (see Section 4.2 of main paper) is made available in anonymized form at https::/dol org/10. 02t.//15.881///// zenodo. 5540348 under the 'CC BY-NC 4.0" license. The other experiments were synthetic and did not involve the use of any dataset.
zip. Further, even though the al-
ETHICS STATEMENT
This work is foundational work that provides improved mathematical framework and algorithm for contextual bandits. Some experiments were set up utilizing data from Freshworks Inc.; the data is released in anonymized form with the consent of the company (link to dataset given in the main paper). To the best of our knowledge, we do not believe there were any ethical issues associated with the development of this work. Further, given the nature of the work as foundational and introducing a new algorithm (and not specific to an application), we do not foresee any specific potential negative ethical issues created by this work. However, their specific applications should adhere to ethical standards of their own (e.g., by avoiding targeting interventions subpopulations based on racial attributes).
do point out that researchers utilizing this method to
10

---

Published as a conference paper at ICLR 2022
REFERENCES
Alckh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits. In Proceedings of the 31st International Conference Machine Learning, volume 32 of PMLR, pp. 1638- 1646, 2014.
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit prob- lem. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of PMLR, pp. 39.1-39.26. 2012.
Elias Bareinboim and Judea Pearl. Transportability from multiple environments with limited exper- iments: Completeness results. In Proceedings of the 27th International Conference on Neural Information Processing Systems, volume 1, pp. 280-288, 2014.
Elias Bareinboim, Andrew Forney, and Judea Pearl. Bandits with unobserved confounders: causal approach. In Proceedings of the 28th International Conference on Neural Information Processing Systems, volume 1, pp. 1342-1350, 2015.
Djallel Bouneffouf and Irina Rish. survey on practical applications of multi-armed and contextual bandits. 1904:
2019.
Juan D. Correa and Elias Bareinboim. A Calculus for Stochastic Interventions: Causal Effect Iden- tification and Surrogate Experiments. In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 34, 2020.
Maria Dimakopoulou, Zhengyuan Zhou, Susan Athey, and Guido Imbens. Balanced Linear Con- textual Bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp- 3445-3453, 2019.
Gabriel Dulac-Arnola Nir Levine, Daniel J. Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal, and Todd Hester. Challenges of real-world reinforcement learning: definitions, benchmarks and analysis. Machine Learning, Apr 2021.
Mingming Gong, Kun Zhang, Tongliang Liu, Dacheng Tao, Clark Glymour, and Bernhard Schölkopf. Domain Adaptation with Conditional Transferable Components. In Proceedings of the 33rd International Conference on Machine Learning, volume 48, pp. 2839-2848, 2016.
Google. Targeting overview. btttps://suppor..co google www opt.//pt...0 weeettmiiieeaaee /e/answer/ 6283420 2021. Accessed: 2021-10-02.
Ruocheng Guo, Lu Cheng, Jundong Li, P. Richard Hahn, and Huan Liu. A survey of learning causality with data: Problems and methods. ACM Comput. Surv, 53(4), July 2020.
Daphne Koller and Nir Friedman. Probabilistic Graphical Models: principles and techniques. MIT Press, 2009.
Finnian Lattimore, Tor Lattimore, and Mark D. Reid, Causal bandits: Learning good interventions via causal inference. Proceedings of the 30th International Conference on Neural Information Processing Systems, volume 29, pp. 1189-1197, 2016.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithuss. Cambridge University Press, 2020.
Bo Liu, Ying Wei, Yu Zhang, Zhixian Yan, and Qiang Yang. Transferable contextual bandit for cross-domain recommendation. Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, pp. 3619-3626, 2018.
Yangyi Lu. Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret analysis of bandit prob- lems with causal background knowledge. In Proceedings of the 36th Conference Uncertainty in Artificial Intelligence (UAI), volume 124 of PMIR, pp. 141-150, 2020.
Sara Magliacane, Thijs Van Ommen, Tom Claassen, Stephan Bongers, Joris M. Mooij, and Philip Versteeg. Domain adaptation by using causal inference to predict invariant conditional distribu- tions. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 108699-1889,, 2018
11

---

Published as a conference paper at ICLR 2022
Judea Pearl. Causality. Cambridge University Press, 2nd edition, 2009.
Judea Pearl. On the Interpretation of do(x). Journal Causal Inference, 2019.
Neela Sawant, Chitti Babu Namballa, Narayanan Sadagopan, and Houssam Nassif. Contextual multi-armed bandits for causal marketing. arXiv:1810.01855 2018.
Rajat Sen, Karthikeyan Shanmugam, Alexandres G. Dimakis, and Sanjay Shakkottai. Identifying best interventions through online importance sampling. Proceedings of the 34th International Conference Machine Learning, volume 70 of PMLR, pp. 3057-3066, 2017.
Burr Settles. Active learning literature survey. Technical Report 1648, University of Wiscon- sin-Madison, 2009.
Akihiro Yabe, Daisuke Hatano, Hanna Sumita, Shinji Ito, Naonori Kakimura, Takuro Fukunaga, and Ken-ichi Kawarabayashi. Causal Bandits with Propagating Inference. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of PMLR, pp. 5512-5520, 2018.
Junzhe Zhang and Elias Bareinboim. Transfer learning in multi-armed bandits: A causal approach. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, pp-
1340-1346, 2017.
Li Zhou. A survey contextual multi-armed bandits. arXiv: 1508. 033266 2016.
12

---

Published as a conference paper at ICLR 2022
A APPENDIX (SUPPLEMENTARY TEXT): PROOF OF THEOREM 3.1
This is the full version of the proof sketch presented in Section 3.2 of the paper. For readability of the proof, assume that Y and all variables in C are binary, whereas X can have any finite set of values. In Sections A.1 through A.5 we derive the expression for bounding Regret(c"""), which is the simple regret given Clar -c Then, in Section A.6 we derive the final expression for bounding overall Regret.
In addition to the notation in Table 1 of the main paper, we use few other notations to keep the proof more readable:
denotes caar U U
(B) is shortened to b when it is unambiguous what is; for example, c(PAv) is shortened to pay when it obvious that the current set of values taken by all the context variables.
We write P(VV pay) interchangeably with P(vlpay) since we use small letters (e.g.. u) to denote the value taken by the random variable denoted by the respective capital letter (e.g., V).
Now, the factorization under Assumption (A1) can be written in this simpler notation as:
E|y [d(x))) c
Σ
P(Y = 1 pay)
II
P(clpac)
eather (v
eEcother
Recollect that we use set operations on vectors as well, wherever there is no ambiguity.
A.1 BOUNDING THE ERROR OF F(Y = 1|r, pay) ESTIMATES
Let pay denote the value taken by PAy (i.e., Y's parents), excluding x. Say, for a (z. pay).
P [IPYY 1/2, ) IPYY = 1/2, pay-)l 2 Ex.pay S 6x óx,pay
Using the union bound, can rewrite it as
Ya, V 1|X, pay) P(Y pay)) 2 Ex.pay S dxxpaa
px, the following event Ex pay is true: In other words, with probability 2 5x pay
Mr, Tp(YY = 1|X, )ay) P(Y = 1|X, pay)) S Ex.pay
We derive expressions for ex, and 6x,pay P.y in Lemma A.2
A.2 BOUNDING THE ERROR OF P(C = c (PAC) ESTIMATES Now, say, for a C' E C (taking value = c). and for given pac-
P [(((ppac) -
2 6c|pa < 6c/pac
Note that p()ppac) + (1|paa = 1 and P(O)pac) + estimates are given by ēc. That is, ? e P(clpac) P(((ppa)) Therefore,
= 1. Now, say the actual errors in
p(0))aa)) + ((()pac) = + IP(0) )(00)aa)))) + C pac
+ P(1 paa) + Ellpac =1
+ Ed|po + éllpac
= 1
= 0 Ep|pace + é pac.
Now, this means that
[20ppag S
I |2 S a
Therefore, the event | pac. the following is true:
< is the same event the event |21pal S Therefore, given
PP [e,, 1Koppaol S <C/ppa] 2 1 - 8c|pac
13

---

Published as a conference paper at ICLR 2022
which is the same where 6cppag is function of EClpse Note that now have 6pipg instead of Oelpace In other words, given a pac, with probability 2 8c
P vc, [cpppcc P((ppac)] & pcipac 2 1 8cipac
p0pp pac the following event Ecipa is true:
Ve, [P(C clpac) - PC = clpac)| S ECIpac
We derive expressions for dc/p and 60/pag in Lemma A.1
A.3 PUTTING THEM TOGETHER FOR THE OVERALL BOUND FOR REGRET((((r)
Using the union bound, for any clar, with probability 2 1 Epay. 8x,pay -Eoec Eme 8cipa all of Ex. and Ea are true simultaneously Vpay and Vpac VC (C \ PAa)). Let's call this event E. In other words, under event E, all estimates bounded.
Let Golg = ò(ctar) denote the action chosen by the algorithm in the evaluation phase when presented with ctar; and let a" denote an optimal action for efar Therefore, given Crar c under event E,
E|y (ddooaat))); clar]=
Σ
P(Y
1 lelgs pay) II cEeather
PP(cppcc
cother
(Factorization due to G as earlier)
E eother
P(Y = 1aslo pay)
II (P(clpac) EC pp
cEgather
(Since Ecipa are actual errors.)
Σ eeter
(P = 1/aaig pay) EX.
} II
(p(clpac) ECIpac
cEgnther
(Due to event E)
P(Y (Ido((atg).
Σ
Σ
P Jar "eu")ep
CEcacherUY gnther (Algebra discussed separately in Section A.3.1
Y [do(aatg), carj
Σ
Σ P(pac
tar (ecrccpp
CECotseryy pac
(Since Y is binary)
"BlYdo((") caay
Σ Cecotheruy pac
EP(pac
e Cllpa
x=
(Due to proposed algorithm)
Continuing and applying similar steps, we get
B[Y]do(aoig), (Mar) E,Y (d((a))) caar - Σ P(pay car Jex.pay.
Σ P(pppc tor Jeclpa
CECotker pac
Defining
é'x
A Σ
Pppy tar
pay
and
60
Σ
Pl lar (ar)
pac
14

---

Published as a conference paper at ICLR 2022
get that,
E|y (do(aatg) clarj 2 B[Y]do(a" c,arr) - -26x -
Σ & CECother
Therefore, under event (that is, with probability 2 any given elar,
Σ Epay
pay óx,pay
Ecec pac 6clppa) for
Regret(c'"r) = BBY(ddo(a") cta") E|Y]do((atg)) clar] I 22xx +3
Σ
6
(3)
CECuter
We derive expressions for each of these terms in Sections
A.4 and
A.5 and then arrive the final
bound in Section A.6
A.3.1
ALGEBRA FOR INTERMEDIATE EXPRESSION
We wish to show that
Σ
(P 1|,, pay) e pay
II
(P(c)pac)
EC/ppc
cocher
oeher
Pp d))) carr)
Σ
E
Picateer for (arr JeCipac
CECotheruy eather
Let us denote the expression on the left hand side by (A).
Let G oother chosen in reverse topological order; this ensures that a child is chosen before any of its parents. Let C₁ be the corresponding variable in Cother, Then we can write
(A) = Σ
(P(YY- = 11, pay) cx.pay H(((c: - Eog pac, }
cotherlez
II
(P(cllpay)) - Eellpacrr
d'eentheree
Σ
Σ P( = 1/2 pay (P (ccl)pac))) Ecs pac,
P(Y = -1/2,pay-)
cuther le:
pa, P(c:lpaci) + Ex, Ecclpme.) ]]
II d'gcnhhrlees
(P(c'|pacc - EEc' }
Q0.1l -|cl ECilpac
εx pac,
II
(F(dlppac)) Eci
cother Les
deenther (ea
where
fo|Y=11z. & P(Y 1/2, pay
II (fd
ded
and
Ex pac,
Σ pay (cc.
These make use of the fact that éc, pac, < <C (pac, Eo|pac, = - lpac, and that < 1. We can keep reapplying the above steps in reverse topological order till we exhaust all c. and we'll lll get
(A) 2 Qctther Y = 1|2, ear
Σ Σ ptcther | tar (aar)) CCC
CECotherLy cothor
Noting that Qeasser y 1/,, clar] Po(Y [do(()) clar) gives the desired inequality.
15

---

Published as a conference paper at ICLR 2022
A.4 EXPRESSIONS FOR 60/pag AND CC pac
Lemma A.I.
2 T'P c ctor) EPAC
P Ve, (P(clpac) - P(clpa)) 2
In
2 1 òcipac
òcipac
Proof. Let T be the set of time indices during training when PAc pac was chosen/seen by algorithm, and pag = 1 Now, for a C that observed and not choser note that estimate of IP(C | computed (00) +1)/(Tpa + +2). We approximate this as g(l) C/pac /Tpp Using Hoeffding'ss 's inequality, for any c,
(- Tpac
P - - clpaa) - P(C = c cl 2 <Cipae]
S cxp (- (<cipac))
But since already observed, the two events (corresponding to 0 and 1) are the same, have
IP Ve,, [P(c|pac) (Pfplacc)pP((ppaa)))) S ECipac]
21 - 2xxp
(-2
pac (ECIpag) )2
2
Therefore, let
Tpac
óc|pac 2 2xx
(-2
(colpmo)
Now, let T aT be the number of rounds of Phase 1. Let Taipac be the number of times C was updated Phase 1 as a results of encountering PAc = pac. Note that the mean of To pag. is (PP(ear)PPppaplll (paapp clar). By the Hoeffding s inequality,
2( I pag )2
P TT pag 2 ('P(ppa.ctary clar) - -ppce) 1 exp
T
By the union bound, we have (let's call the event as ET CCIPAc
2(cFAa)
P ypac, Talpa 2 TTP(pac dar) EFAc)] 21 21-NPAC exp
7"
where NpAc = -ITEPAC Nc.
2(1 2((pso)²)
Letting ECpAco A NPAC exp
we have
T
NPAC
T EI
Im
2
Note that TeIpac 2 To pag. Therefore, given that ET
CIPAo true, we have
To|pa (EC) p2)
Ye, (P(clpac) P(c|paa)) EClpac 2 1 - 2exp
T'P(pac, ctar) - T
PAC (EC) pa )2
1 - 2 exp
2
*This means O' E C during Phase of the algorithm, or C E Calbber in Phase 2. 't's easy that this does not change the asymptotic behavior of the bound.
16

---

Published as a conference paper at ICLR 2022
Defining lc/r
T' T' paac clar))
- =ECIPcc (Eclpao) )²
óc|pac
exxp
gives us
<C|pac
Ppppp cpac clar)) CCPAO
T
80/pac
(4)
A.5
EXPRESSIONS FOR dx,pay ex,, AND c'
Lemma A.2.
Vr, [P(Y = 1/x,pay)) P(Y = 1 (/x,paa))
2
2Nx ox dx
In
1
8x pay
P(pay, :oaly,ctar - PX Nx
T'
Proof. As before, let Tr. pay be the set of time indices during training when (X, PAy) (x. pay was chosen/seen by the algorithm, and let Tz T2.pay = |Ta.pay As before, note that our estimate of P(Y 1/,, pay) is computed as (0y 22yypay + 1)/(TT 2), which we can approximate as
( Myz.pay /Tr.pay- Now, by Hoeffding's inequality
p P[iPCY 1/2,, pay) PPY 1|2, pay)) 2 Expaa
S 2exp
(- 2
T Ts.pay
Exppy
During Phase 1, let T pay be the random variable denoting the number of times that PAy) (I, p scen/chosen. Note that, due to the nature of Phase 1 (i.e., each x is chosen with probability Nrx: the mean of T Ta.pay is ("P(ppayaeee elor) the Hoeffding's inequality.
(darr Nx. Therefore, using the union bound and
V(z, pay), To Te.pay 2 T'Pappa, tar 1
1 21 2 1x-NxNPA, exp (-7 TT (cX.
Ex,PAy
Nx
Since V(I, pay), Ts Ta,pay To pay we have (let's call this event ET P.))
V(z, pay), Tapay 2 T'P(pay, c'ar) 1
&krAa 2 L--NXNPAY exp
( ( ((k.)a))))
Nx
Letting PA & Nx exp (- (cT, we have
Nx
6X.PAY
In
OX,
Now, we can get that, for given pay, Va. (let's call it event Ex pay )
P Vx, IP = 1/2. pay) - P(Y 1/2,, pay)) S 6X,pay
Tr.pay
1 - Σ 2 exp
(Ex,pay)
(payy ; clor) -x. (cx.pay }2
2N exp
Nx
2
17

---

Published as a conference paper at ICLR 2022
Setting
T P Ppay, clar) -x (ex,pay) )2
8x,pay = =N exp
Nx
2
we have,
2Nx
Exppay
T ctary
cl Px
óx.pay
(5)
Nx
A.6 DERIVING THE FINAL REGRET BOUND
The probability that events E, PAA C) and Ex PAy are all simultancously true
1 Σ
óx.pay 5x. PAY
Σ do + PAC
pay
CEC
Substituting Equations for given clar.
and
(
back into Equation
we get that, with the above probability,
2
2NNx
Regret(ctarr
3
Σ
P (elayyllarr
In
P (pay, ctar)
-EX
óx,pay
pay
Nx
Σ
Σ E(ppacle
In
2
TVP(pa clar) - T
òctped
CEcother pag
where
T" V 1
NPAC OCIPAC
T CIPAAc
In
and
T 2
Nx 5x.PAY
T PAy
In
We set 3 6xxpay 50 -X =dc/pac 8T AA VC, pappay.Pp pac- Thus, for given ctar, with probability 2 -NPAY 3- 5- -NNAPAA - CC PAy 8,
2NNx
Regrel(ctar) tar) 3
Σ Sopaylctry
In
T' P Ppay, stor) Nx
cttor)
T XxPAA
pay
Σ Σ P(pac car))
2
2
In
T'IP (pa ctar)
T
Cecather pac
EcIPAc
where
T [
NNAc 8
CIPAo
T
-1
In
and
T 2
Nx NpAY 8
EXPPAY
T
1/
In
18

---

and Published as a conference paper at ICLR 2022
Now, noting that NPA, 8 + + Ne, 8 + |c PAy / & (Ne + ICI),, set 5 (No + (C1) So we get that with probability 2 6,
2
2Nx + (Cl)
Regret(c'ar) 3
Σ pay
P(paylelar)
In
(pay, clar)
-EX.PAy
Nx
2
2(NNe + (cl))
P(pack cler).
In
(6)
a aTP ppac ctar) - -CPAC
6
CECother pag.
where
af
NPAc (Nc + -(C1)
E
|
In
8
aT
Nx (Ne |C1)
T X,PAY
In
Substituting Equation 6 into the definition of Regret in Section of the main paper, get the expression in Theorem 3.1.
B APPENDIX (SUPPLEMENTAN) TEXT): ADDITIONAL EXPERIMENT UNDERSTANDING THE REASON FOR BETTER PERFORMANCE
Std UniExp
Targint UniExp
0.110
0.110
of times chosen/seen
0.105
% of times chosen/seen
0.105
0.100
0.100
0.095
0.095
0.90
0.090
0.085
0.085
0.000
0.080
ce value
value
(a) Uni_pp
(b) TarglnttUniExp
Unc_CCB (Ours)
0.110
% of times chosen/Seen
0.105
0.100
0.095
0.090
0.085
0.080
value
(c) Our proposed algorithm
Figure 4: Frequency choosing or encountering each value of Ctar, Highlighted red color are the 'high-value' contexts (i.e., contexts for which learning the right actions provides higher expected rewards).
In this analysis, we try to "understand why our algorithm exhibits better performance than basclines." We had pointed intuitively that the Unc measure trades off between exploring new contexts and
19

---

Published as a conference paper at ICLR 2022
learning more about explored contexts based on (a) current knowledge of the various context-action pairs, and (b) current estimates of the 'value' (i.e., rewards obtainable) of context-action pairs. This section attempts to zoom into this behavior.
Specifically, we consider one of the settings (setting #1) from the representative set used in Ex- periment 1; it has Ne others (i.e., learning the right actions for these contexts can give higher rewards); see code (config.setting
10, all equally likely, but C E {0,1} more valuable than
. py) for more details. We zoom into the case when T' 15. We do 500 independent runs, count the number of times every possible Clar value is encountered or cho- sen, and plot the frequencies. We compare our algorithm's behavior with two representative base- lines - Algorithm Std UniExp (which does standard contextual bandit interactions) and Algorithm Targint UniExp (which does targeted interventions): the effect is similar for the other two baselines as well. As seen in Figure 4 our algorithm chooses the higher value contexts (C E {0, 1}) with relatively higher frequency than the baselines, while still ensuring good exploration of other contexts in line with the intuition discussed in the main paper.
C APPENDIX (SUPPLEMENTARY TEXT): MORE DETAILS ABOUT EXPERIMENT 1
In the discussion about Experiment I in the main paper, it mentioned that Appendix C con- tains plots for two individual settings from the representative set - one where Algorithms Std_TS and Unixp perform significantly better than Algorithms Targint_TS, Diigint.TS.niEEx.. and another where it is the converse while our algorithm performs close to the best baseline in both. Figure Seuure/ppreseee presents those plots. Each result is based on 50 runs.
Marglnt_UniEEt and
D APPENDIX (SUPPLEMENTARY TEXT): REGARDING PARAMETERIZATIONS USED IN THE EXPERIMENTS
For the specific parameterizations of all settings used all the experiments, refer to the README file in
zip as part of the Supplemental Material.
E APPENDIX (SUPPLEMENTARY TEXT): MORE DISCUSSION ON THE CASE WHERE Cother Ø
If Cother Ø (that is, if it is empty), it might appear if there would not be any information
leakage. However, this is not true, and information leakage can still exist, For instance, consider the same graph in used in Section 4.1 But now suppose that Clar {Ci, Co whereas Cother Ø. Consider two targeted interventions, (Ir C1) and (z, co, c1), where e1 * cq. Note that the distribution Y after these two targeted interventions would, respectively, be
P(Y]do(z), (co,e)) (2) (co, e()) = IP | co)
The common term IPY lr, co) enables information leakage between these two targeted interventions. To see this, note that if the agent conducts targeted intervention (I, co. e1), then is able update its beliefs about P(Y| co) which improves its estimates of (Ir, co, e4) as well due the shared term. So Cother = Ø does not preclude information leakage.
Instead, suppose that we are considering the interventions (Ir, Co, e1) and (x, cb. 61), where co + ch In this case, information leakage gains will not be possible. However, our algorithm would still be able to achieve better performance compared to baselines by balancing between exploring new (I, ctar") pairs and learning more about already explored "valuable" (z, ctar) pairs. To see this, note that in the definition of Unc in Section 3.1 the "information" component weighted by the "value" component (the last two terms, namely, P(c'). [y do(x))))
20

---

Published as a conference paper at ICLR 2022
NonCausal_Sta
Std _S
2.0
Std UniExp
Targint TS
Targint UniExp
1.5
Regret
Targint_ TS Seanit__SS_niippppppp
Unc_CCB (Ours)
0.0
10
12
Number training rounds
(a) Algorithms Targint TS, Targint UniExp and Targint TS UniExp perform
ter than other baselines.
NonCausal Std TS
Std_TS
Std UniExp
2.5
Targint_T5
2.0
Targint Lninnt_U
Regret
Targint_TS_un Laint__TS_umii SniiEEx
Unc_CCB (Ours)
0.5
Number of training rounds T
(b) Algorithms SS. Std UniExp perform better than other baselines.
Figure 5: Different baselines outperform each other in two different settings; however, our algorithm performs close the best baseline in both.
F APPENDIX (SUPPLEMENTARY TEXT): REGARDING THE CHOICE OF THE PROBABILITY OF UNIFORM EXPLORATION IN BARGINT.TS.UNIEL
Thompson Sampling aims to minimize cumulative regret in best-arm identification setting (Agrawal & Goyal 2012). For cumulative regret minimization, it performs better than simple ex- ploration algorithms such as e-greedy, by controlling the exploration based the agent's current beliefs. However, as discussed in the main part of the paper, in our setting, the agent is faced with the task of learning a policy, while balancing exploration of new contexts and learning more about already explored contexts. Thus, apart from having standard Thompson Sampling as baseline (TargInt.TS), we also create variation of this (called Targint_ TS TS_inEp where, in each round, the algorithm, with some probability X, chooses targeted intervention uniformly random (from the space val(X) x val(Ctar)) for exploration; with probability X, it chooses the targeted inter- vention given by Thompson Sampling. This probability allows to directly control the degree of uniform exploration.
In Experiment 1 (Section
chose the probability of uniform exploration 0.5 for Targint TS UniExp. This was to act as a midpoint between the Targint TS algorithm (attempting optimize cumulative regret) and Targint UniExp (which does uniform exploration). We noted
21

---

Published as a conference paper at ICLR 2022
that our algorithm continues to perform better than all baselines. Figure 6 shows that this continues to be true even when À in Srsggnt_TS.niExppp is not as large as 0.5, by setting 0.2.
10-
NonCausal _td__
Std_Ts _dd_T
Std Std_ UniEnnExppp
Targint_Ts
Regret (normalized to [o, 1D)
Targint UniExp
Targint TS rS__erredyy
Unc_CCB (Ours)
0.6
0.4
01
02
0.4
0.6
Number of training rounds T (as fraction of NyNcua)
Figure 6: Experiment results when probability of uniform exploration in Doallt__TS_nmn Unnniixp was chosen to be 0.2 (instead of 0.5), Our algorithm continues to perform better than all baselines.
22


Reviews:
[{"review_id": "i82SkoT1GG", "reviewer": "Reviewer_swHk", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths\n1. The paper provides a complete analysis of a reasonable theoretical guarantee on regret. \n2. The simulation and real-data experiments also show good performance of the proposed method, compared with some other methods considering contextual variables.\n\nWeaknesses\n1. I wonder what’s the comparison (in simulation or theoretically) between the proposed method and some existing method that does not account for contextual variables (use the same policy for all observed environments)? \nMy intuition is that the latter would still perform fairly well when contextual variables have values with high probability mass. Would one outperform another in different cases of the underlying distribution for (X, Y, C), or the proposed one would always be better?\n2. In section 2.1, the authors claimed that the ordinary interactive bandit setting is “robust to unobserved confounders”. Does this claim hold when the proposed framework uses targeted intervention where the values of contextual variables are restricted?", "summary_of_the_paper": "This paper considers the problem of interactive decision-making given some context variables from the environment, which is referred to as contextual bandit setting in the paper. The proposed method is novel in the sense that (a) the analyst can choose to make an intervention on a targeted subpopulation (b) it incorporates causal structure among the context variables and the intervention variable. \n", "summary_of_the_review": "Overall I think it is an interesting problem to account for context variables in interactive decision making. The proposed method is intuitive and the authors provide theoretical and numerical evidence for its performance. Still, I would be more convinced if there is a direct comparison between the proposed method with an existing method that does not account for context variables. \n", "strength_and_weaknesses": "", "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": {}}, {"review_id": "_5_KZ6pUlYJ", "reviewer": "Reviewer_DesA", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Thanks for bringing an interesting bandit setup and proposing an intuitive solution.\n\nFirst, the assumption on the causal graph seems less accurately described. \nCurrently, the model the authors are considering seems a Markovian model where there exists no unmeasured confounders. However, it is less clear since, the authors are well-aware of what unobserved confounders are. Then, the assumption (A1) says that any variable that confounds a target context C and reward Y is also in the target contexts C where a sufficient condition for (A1) is C-target being ancestral. \nHowever, In Equation 2, the authors factorized P(bold c_other | bold c_target) as the product of P(c_other | Pa_c_other ), which is not always plausible if you allow unobserved confounders (applying chain rule and conditional independence to prune conditionals). This error indicates that the authors are not quite careful/sure about imposing assumptions on the underlying causal graphs.\n(Yet, it is true that one can estimate P(bold_c_other | bold_c_target) as a whole. )\n\nSecond, experimental setup is rather naive. In the training phase, there is no reason for an agent to pursue Standard Thompson Sampling (TS) since the task here is not to minimize cumulative regret. The focus here is pure exploration. Similarly, other baseline TargInt_TS is not a proper exploratory agent. As you can see TarInt UniExp performs even better than TargInt_TS. In other words, TargInt UniExp should be considered the minimal baseline, and one may figure out what can be better baselines to compete against the proposed method. For example, what if we use the upper confidence bounds instead of the current estimate multiplied by entropy. Or randomly sample E[Y|d,do(x’)] from posterior distribution instead of using hat E[Y|d,do(x’)]. There are many reasonable possibilities. How about simply dropping uncertainty ? What is the contribution of this entropy term? What if Gini-index? and so on.\n\nHence, the authors may focus on clarifying the assumptions and analyze the method thoroughly comparing to other possible stronger baselines.\n", "summary_of_the_paper": "This paper proposes a contextual bandit problem where an agent is capable of intervening on a targeted population (e.g., a user whose characteristic matches a specific context) instead of getting a context stochastically sampled from the underlying distribution over contexts. The authors proposed an intuitive solution that a targeted intervention should be performed for a specific context with an accompanying action such that, after the intervention, the uncertainty weighted by currently estimated rewards goes down most. \n", "summary_of_the_review": "The paper has a certain interesting problem with an intuitive solution. Yet, the theoretical and empirical analysis seem a bit lacking. Further, the assumptions need to be further clarified.", "strength_and_weaknesses": "", "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": {}}, {"review_id": "EwpayOen8kM", "reviewer": "Reviewer_i8oB", "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": "I have reviewed a previous version of this paper. Most of my comments regarding clarity in that version are now resolved: in particular, the notation in Section 2 is more consistent, and the baselines for the experiments are introduced more clearly.\n\nMy main concern was that the paper does not particularly explain well how does the side information obtained from the causal structure lead to more efficient exploration. I appreciate the addition of the paragraph \"Intuition behind the Unc measure\" in the new version, which addresses this concern. It is mentioned there that an intervention $(x,\\mathbf{c}^\\mathrm{tar})$ could reveal information about other interventions $(x',\\mathbf{d}^\\mathrm{tar})$ and that $\\mathrm{Unc}$ is a measure of this potential information gain. A concrete example of how this happens in one of the settings considered during the experiments would be even more helpful.\n\nHowever, what still remains unclear to me is the role of auxiliary context variables $\\mathcal{C}^\\mathrm{other}$ in this story. I might be mistaken about this but the problem seems to be interesting only when $\\mathcal{C}\\neq \\mathcal{C}^\\mathrm{tar}$ and $\\mathcal{C}^\\mathrm{other}\\neq\\emptyset$. Otherwise, it could be treated as a regular contextual bandit problem, where $\\mathcal{C}\\cap \\mathrm{PA}_Y$ is treated as the context variables (letting $\\bar{\\mathcal{C}}=\\mathcal{C}\\cap \\mathrm{PA}_Y$, no intervention $(x,\\bar{\\mathbf{c}})$ would be informative about other interventions on $X\\cup\\bar{\\mathcal{C}}$). If this is the case, I would have like to see a discussion of it. For instance, in what real world problems do we have $\\mathcal{C}\\neq \\mathcal{C}^\\mathrm{tar}$? If this is not the case, then how does Unc_CCB perform compared with standard contextual bandit algorithms (that only consider $\\bar{\\mathcal{C}}$ as the context and ignore other variables) when $\\mathcal{C}= \\mathcal{C}^\\mathrm{tar}$? If there is still an improvement, then what is the source of the gain there?\n", "summary_of_the_paper": "This paper formulates a contextual bandit problem with causal side-information, where the agent has the option to perform targeted interventions. Then, the paper proposes an algorithm for solving this problem and shows that its regret is bounded.", "summary_of_the_review": "The paper is clearer compared with an older version I have reviewed but I still have questions regarding how the knowledge of a causal structure helps with learning.", "strength_and_weaknesses": "", "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": "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": "A6dVbmbWbw", "reviewer": "Reviewer_cUNV", "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": "### Strengths: \n\n1. The paper is well-explained, well-organized and paints a linear, coherent story (albeit the notation is a bit difficult to follow). The paragraph on discussion of the theorem is useful and brief paragraphs explaining the intuition behind Unc measure are helpful for the reader. \n2. The paper explores a novel formulation of contextual bandits motivated by a real-world software agent application and lays the foundation for approaching this setting by proposing a solution approach.\n3. The paper also presents theoretical analysis of the proposed algorithm. (I haven’t checked the theorem math and details, so would defer to other reviewers to check for sanity here)\n\n### Weaknesses: \n\n1. It is not discussed why the two-phase algorithm mentioned is optimal. For example, instead of splitting into blocks of $\\alpha$ and $1-\\alpha$ could it have been better to keep oscillating between uniform interventions and targeted interventions during training? Or could there be some other way of allocating interventions that is optimal or is there some reasoning for the proposed method that I’m missing?\n2. In the experimental section, each of the baselines considered has a specific, significant shortcoming making it appear somewhat like a strawman. I’m wondering whether it could have been possible to compare the proposed algorithm with other possible ways of leveraging targeted interventions to make the comparison more competitive?\n3. The notation is difficult to follow. In section 2, what is $\\mathcal{D}$? I thought the same was denoted by $\\mathcal{C}$ earlier? In the same paragraph, $\\mathcal{C}^{tar}$ is defined but $\\textbf{c}^{tar}$ is used in some places. \n4. Terms like belief are mentioned in the introduction but are only explained later in Table 1. I’m not sure Table 1 clearly defines ‘belief’ either — is it a distribution over possible parameter values? That makes it hard to follow the algorithm and parse terms like updateBelief(). \n5. In a broader picture of the paper, I’m confused how the casual side-information piece relates to the targeted interventions? It seems like these are two disconnected ideas/features of the problem setting that the paper tries to capitalize on. Does the key idea of the paper in any way rely on leveraging both these phenomena simultaneously rather than independently?\n", "summary_of_the_paper": "The paper studies a contextual bandit setting with two unique features: (1) the learning agent has ability to perform targeted interventions during the learning phase (ability to select target sub-populations or context) and (2) it also has access to and integrates casual information in the setting. The key motivation is that this setting captures real-world scenarios such as software product experimentation. One key contribution of the work is a new algorithm that achieves better sample efficiency. The algorithm is evaluated using synthetic experiments and real-world-inspired synthetic experiments. \n", "summary_of_the_review": "The paper studies a new contextual bandit setting motivated from real-world scenarios and proposes a new algorithm and presents theoretical guarantees on the same. There is experimental evaluation via simulations but I’m unsure if the baselines considered are competitive. The paper is well-written generally. \n", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers a new setting of contextual bandits where the learning agent has the ability to perform interventions on targeted subsets of the population. The problem is motivated from software product experimentation but with more general applicability. The paper provides a method under this setting, with both empirical and theoretical support. Reviewers agree that this is an interesting setting, and the paper contributes new results. The initial concerns on assumptions, correctness and experiments were addressed in the rebuttal. I thus recommend accept. The authors should include the response carefully in the final version.
Decision: Accept (Poster)