Year: 2021

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 sideinformation 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.

heading: 1 INTRODUCTION
text: Contextual bandits have been used as natural frameworks to model interactive decision making scenarios such as recommendation systems (Liu et al., 2018), marketing campaign allocation (Sawant et al., 2018) and more (Bouneffouf & Rish, 2019). In this framework, the learning agent repeatedly interacts with an environment with the aim of learning a near-optimal decision policy that maps a context space to a set of actions (also referred to as arms or interventions1). In the standard stochastic 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 is a function of the current context and chosen action (Lattimore & Szepesvári, 2020). The agent’s objective is to minimize some meaningful measure of closeness of the policy to optimality (see Lattimore & Szepesvári (2020) for some standard definitions).
One of the key issues in the wide application of contextual bandits (and reinforcement learning, in general (Dulac-Arnold et al., 2021)) is their need for a large number of samples that are costly to actualize in practice. For example, each arm might correspond to performing a product experiment on users or to conducting a specific medical intervention. However, we show that there are nuances in real-world situations which – though not fully captured by the standard formulations of contextual bandits – if modeled and leveraged, allow us to build methods that can improve the rate at which good policies can be identified.
A motivating example Consider the example of a sales-assistance software agent that is learning to suggest a campaign that is optimal for a given sales lead (defined by a set of features). With software products, there is often an opportunity to conduct experiments with variants of the software on defined subsets of the population of users (each specified by a set of characteristics, or context variables) to learn about resulting metrics; see Google (2021) for an example. We can think of these experiments as constituting a training phase. More specifically, the agent, for example, can conduct a campaign (which is the intervention) on a 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 a randomly sampled user coming from the natural population distribution, the agent
1We use the term intervention here because actions or arms in a (contextual) bandit setting can be interpreted as Pearl do() interventions on a causal model (Zhang & Bareinboim, 2017; Lattimore et al., 2016). See Pearl (2009; 2019) for more discussion on the do() operation.
can instead choose to target the intervention on a randomly selected user with specific characteristics (as defined by an assignment of context variable values). We call this special type of interventions targeted interventions, and they fundamentally change the set of options that the agent has in every training round.
In addition, the training phase often happens in a more lenient environment where the agent might have access to auxiliary context variables (such as IT-spend) that are unavailable in the evaluation phase. Further, there is also causal side-information sometimes available. For instance, we might know that emailsubject causes openemail, and not the other way around. Encoding this qualitative side-information as a causal graph can help the agent make use of this structure. Lattimore et al. (2016) and Yabe et al. (2018) 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 an 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 an overview here. The agent has T rounds of interaction that act as the training phase, followed by a (T + 1)’th round on which it is evaluated. In each of the T training rounds, it has the choice to perform either a targeted intervention or a standard interaction. Further, in addition to the main context variables, the agent can observe a (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 is 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.1). The causal graph allows a factorized representation of the joint distribution of the variables, and as a 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 linearity (e.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 as to learn a 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 an action and receives a reward – much like in a standard contextual bandit setting. Since targeted interventions are restricted to the training phase, it introduces a 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 a way that also exploits the information leakage.

heading: 1.1 CONTRIBUTIONS
text: In this paper, we formalize this modified setting, which we call “causal contextual bandits with targeted 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 side-information. This is also the first paper we are aware of that introduces targeted interventions in a contextual bandit 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 baselines. • We also run experiments that are inspired by proprietary data from a CRM software com-
pany (Sec. 4.2).2 This provides evidence of our algorithm’s performance in more realistic scenarios as well.
2Identity of the company withheld here to ensure anonymity of submission.
Our motivation comes from real world settings where experiments are costly; therefore, we are interested in empirical behavior when the training budget T is relatively small.

heading: 1.2 RELATED WORK
text: 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 to transfer knowledge across interventions. They, however, have been studied only in a 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 a 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 (see Zhou (2016) and Lattimore & Szepesvári (2020) for surveys), and has taken various approaches to enable knowledge transfer across contexts. For example, Dimakopoulou et al. (2019) assume expected reward is a 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 as a way 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.
Another related area is active learning (Settles, 2009). In active learning, a supervised learning agent gets the option to 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). Nevertheless, 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 a non-contextual setting. As can be seen, this differs significantly from our setting.

heading: 2 FORMALISM
text: We assume that the underlying environment is modeled as a causal model M, which is defined by a directed acyclic graph G over all variables – i.e., the variable to be intervened (X), the reward variable (Y ), and the set of context variables (C) – and a joint probability distribution P that factorizes over G (Pearl, 2009; Koller & Friedman, 2009). 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 or causal diagram ofM. Each variable takes on a finite, known set of values; note that this is quite generic, and allows for categorical variables. An intervention do(X = x) onM involves removing all arrows from the parents ofX intoX , and settingX = x (Pearl, 2009). The agent has access only to G and not toM; 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 X = x conditioned on context Ctar = ctar succinctly by (x, ctar). While standard interventions (Pearl, 2009) result in a distribution of the form P(. | do(x)), targeted interventions result in P(. | do(x), Ctar = ctar). Table 1 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(Ctar)→ val(X). Specifically, in each of the T training rounds, the agent can choose to either
• (Standard interaction) Observe context ctar ∼ P(Ctar), choose intervention x, and observe (y, cother) ∼ P(Y, Cother | do(x), ctar), (or)
where, when there is no ambiguity, we use P interchangeably to mean either the joint distribution or a marginal distribution. Note that in both modes of 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 a query context ctar ∼ P(Ctar) to which it responds with an action x = ϕ̂(ctar) using the learned policy, and receives a reward y ∼ P(Y | do(x), ctar) from the environment.
The objective of the agent is to learn a policy ϕ̂ that minimizes simple-regret, which is defined as: Regret ≜ ∑ ctar [µ∗ctar − µ̂ctar ] · P(ctar) = ∑ ctar Regret(ctar) · P(ctar)
where ϕ∗ is an optimal policy, µ∗ctar ≜ E[Y |do(ϕ∗(ctar)), ctar] and µ̂ctar ≜ E[Y |do(ϕ̂(ctar)), ctar].

heading: 2.1 ASSUMPTIONS
text: 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 in settings such as a recommendation system where click-through rate (Y ) of a 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 to Y through them. Purely interactive bandit settings, such as ours, are robust to unobserved confounders (UCs) between X and Y since the actions can be interpreted as directly sampling from the P(.|do(x)) distribution (Bareinboim et al., 2015; Guo et al., 2020). Nevertheless, we do make an additional assumption to simplify the factorization in Section 3.2: (A1) {C confounds C ′ ∈ Ctar and Y } =⇒ C ∈ Ctar. A sufficient condition for (A1) to be true is if Ctar is ancestral (i.e., Ctar contains all its ancestors). This assumption does not preclude UCs (for example, the graph used in the synthetic experiments in Section 4.1 could have a UC between X and Y ), and can be relaxed in future extensions.

heading: 3 SOLUTION APPROACH
text: 3.1 ALGORITHM (UNC CCB)
Algorithm 1a: Training phase of Unc CCB Data: Graph G; fraction α of Phase 1 rounds. Initialization: For all V ∈ C ∪ {Y }, set θV |paV = (1, ..., 1), for all values of paV .
1 (Phase 1) for t = 1 . . . ⌈αT ⌉ do 2 Observe context ctar ∼ P(Ctar) 3 Choose x ∈ val(X) uniformly at random 4 Observe (y, cother) ∼ P(Y, Cother | do(x), ctar) 5 for V in C do 6 updateBeliefs(V, c⟨PAV ⟩, c⟨V ⟩) //denote ctar ∪ cother by c 7 end 8 updateBeliefs(Y, (c⟨PAY ⟩, x), c⟨Y ⟩) 9 end
10 (Phase 2) for t = ⌈αT ⌉+ 1, . . . , T do 11 Choose x, ctar as:
argmin x∈val(X), ctar∈val(Ctar)  ∑ x′∈val(X), ctar′∈val(Ctar) Unc ( E[Y |do(x′), ctar′] ∣∣ x, ctar) 
12 Do targeted intervention (x, ctar) and observe (y, cother) ∼ P(Y, Cother|do(x), ctar) 13 for V in Cother do 14 updateBeliefs(V, c⟨PAV ⟩, c⟨V ⟩) 15 end 16 updateBeliefs(Y, (x, c⟨PAY ⟩), c⟨Y ⟩) 17 end
Result: Final set of beliefs for all V,paV : { ..., θV |paV , ... } 18 Procedure updateBeliefs(V,paV , v) 19 θ
(v) V |paV ← θ(v)V |paV + 1
Algorithm 1b: Evaluation phase of Unc CCB Data: Graph G, learned beliefs { ..., θV |paV , ... } , user context to be decided ctar
1 for every V, paV do 2 for v ∈ val(V ) do 3 Set P̂(V = v|paV ) = θ (v)
V |paV∑ v′ θ (v′) V |paV
4 end 5 end 6 for x ∈ val(X) do 7 Compute ψ̂(x, ctar) ≜ Ê[Y |do(x), ctar] using P̂ in Equation (2) 8 end
Result: Return ϕ̂(ctar) ≜ argmaxx ψ̂(x, ctar)
We call our proposed algorithm Unc CCB. The training phase of Unc CCB (given as Algorithm 1a) consists of two phases. In each round of Phase 1 (a fraction α of the rounds), it observes a 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 over the beliefs about parameters of all relevant CPDs. Since we do not assume any a priori beliefs for the agent, this uniform exploration helps the agent enter Phase 2 with reasonable starting beliefs.
In Phase 2 (the remaining (1 − α) fraction of the rounds) of training, the agent tries to allocate targeted interventions optimally. To this end, it needs to trade-off between exploring new contexts and gaining more knowledge about already-explored contexts, while taking into account the information leakage resulting from the shared pathways in the causal graph (or equivalently, shared CPDs in the factorized representation of P; Appendix E discusses a related subcase). The novel, entropy-like, Unc measure (discussed below) helps guide the agent in this decision in every round. Algorithm 1b 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, ctar) would allow the agent to update its beliefs about effects of other targeted interventions (x′, ctar′). Intuitively, we would want the algorithm to allocate more samples to those targeted interventions that are most informative about the most “valuable” (in terms of reward Y ) targeted interventions. Unc captures this intuition by providing a measure of the effect on the agent’s knowledge of E[Y |do(x′), ctar′] when a targeted intervention (x, ctar) is performed. The agent, then aggregates this over all possible (x′, ctar′), providing a measure of overall resulting knowledge from targeted intervention (x, ctar); this helps guide its sample allocation (see Line 11 of Algorithm 1a).
Definition of the Unc measure We model the conditional distribution P(V |paV ) for any variable V as a categorical distribution whose parameters are sampled from a Dirichlet distribution. That is, P(V |paV ) = Cat(V ; b1, ..., br), where (b1, ..., br) ∼ Dirc(θV |paV ). Here θV |paV is a vector of length, say, r. Let denote θV |paV [i] denote the i’th entry of θV |paV . We define an object called Ent that captures a measure of our knowledge of the CPD:
Ent(P(V |paV )) ≜ − ∑ i [ θV |paV [i]∑ j θV |paV [j] ln ( θV |paV [i]∑ j θV |paV [j] )] Let the parents of V be PAV = (U1, ..., Up); suppose they take a particular set of values paV = (u1, ..., up). We define that a CPD P(V |paV ) is unaffected by targeted intervention (x, ctar) if there exists i ∈ {1, ..., p} such that either (1) Ui is X and ui ̸= x, or (2) Ui ∈ Ctar and ctar⟨Ui⟩ ̸= ui. In other words, the CPD P(V |paV ) is unaffected by (x, ctar) if doing this targeted intervention and observing all variables (x, ctar, cother) does not enable us to update beliefs about P(V |paV ) using knowledge of G. Now, define
Ent(P(V |paV )|x, ctar) ≜ {
Ent(P(V |paV )), if P(V |paV ) is unaffected by (x, ctar) Entnew(P(V |paV )), otherwise
where Entnew is computed by averaging the resulting Ent values over the possible belief updates the agent might make after performing (x, ctar). That is, Entnew(P(V |paV )) = 1r ∑ i Ent(
Cat(b′1, ..., b′r)) where (b′1, ..., b′r) ∼ Dirc ( ..., θV |paV [i− 1], θV |paV [i] + 1, θV |paV [i+ 1], ... ) .
Letting c′ denote ctar′ ∪ cother′, we can now define Unc which captures our knowledge of E[Y |do(x′), ctar′] if we perform some other targeted intervention given by (x, ctar):
Unc ( E[Y |do(x′), ctar′] ∣∣x, ctar) ≜ ∑ cother′∈val(Cother)  ∑ V ∈Cother Ent(P(V |c′⟨PAV ⟩)|x, ctar)+
Ent(P(Y |x′, c′⟨PAY ⟩)|x, ctar) ] · P̂(c′) · Ê[Y |c′, do(x′)]

heading: 3.2 REGRET BOUND
text: Theorem 3.1. For any 0 < δ < 1, with probability ≥ 1− δ,
Regret ≤ 3EpaY ,ctar
 √√√√[ 2
αT NX P(paY , ctar)− ϵTX,PAY
] ln ( 2NX(NC + |C|)
δ ) + 3
∑ C∈Cother EpaC ,ctar
 √√√√[ 2
αTP(paC , ctar)− ϵTPAC
] ln ( 2(NC + |C|)
δ
) (1)
where
ϵTPAC =
√[ αT
2
] ln ( NPAC (NC + |C|)
δ
) , ϵTX,PAY = √[ αT
2
] ln ( NXNPAY (NC + |C|)
δ ) Proof. Due to space constraints, we only provide a 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 Y and all variables in C are binary, whereas X can take on any finite set of values. Under Assumption (A1) described in Section 2.1, we can factorize as follows:
E[Y |do(x), ctar] = ∑
cother∈val(Cother)
[ P(Y = 1|x, c⟨PAY ⟩) ∏ c∈cother P(C = c|c⟨PAC⟩) ] (2)
where c denotes ctar∪cother. The proof first bounds errors of estimates of P̂(Y = 1|x, c⟨PAY ⟩) and P̂(C = c|c⟨PAC⟩) with high probability using union bounds, concentration bounds, and the fact that the number of rounds in which the agent observes any set of context values is lower bounded by the number of times it sees it 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 Ê[Y |do(x), ctar], 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 T → ∞ =⇒ Regret → 0, which shows that the regret bound has desirable limiting behavior.3 Further, regret is inversely related to √ T , similar to other simple-regret algorithms such as in Lattimore et al. (2016). However, other terms that are a function of the space of possible interventions (NCNX ) are different since we are in a contextual bandit setting (whereas Lattimore et al. (2016) is non-contextual); more specifically, regret is related proportionally to √ NXNC ln (NXNC); in fact, our regret bound is 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.

heading: 4 EXPERIMENTAL EVALUATION
text: 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 UniExp follow the standard bandit interaction protocol during training – observe context, choose action, receive reward. They treat each ctar 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 ctar problem, whereas Std UniExp does uniform exploration over val(X). The other set of algorithms are TargInt TS, TargInt UniExp and TargInt 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 performs uniform exploration over this space. TargInt TS UniExp is a variation of TargInt TS that, with some probability,4 chooses a random targeted intervention; this infuses a controlled degree of uniform exploration into TargInt TS. All five algorithms update CPD beliefs after each round. No baseline is strictly stronger than another; their relative performance can vary based on the specific 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 side-information).
The evaluation phase for each baseline algorithm is analogous to Algorithm 1b – given a ctar, the action with the highest expected reward, based on beliefs at the end of the training phase, is chosen.
3There is a technical requirement to keep the denominator in Eq (1) greater than 0; however, it is easy to see that this only requires that T > constant, so there is no impact on asymptotic behavior.
4We choose this probability to be 0.5 for the plots. There is more discussion on this in Appendix F.

heading: 4.1 PURELY SYNTHETIC DATA
text: We consider a causal model M whose causal graph G consists of the following edges: C1 → C0, C0 → X, C0 → Y, X → Y . We assume that Ctar = {C1} and that Cother = {C0}. We choose the fraction of Phase 1 rounds α = 0.5 as we empirically found that to be a good choice. 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.
Experiment 1 Given the wide range of possible settings arising from different parameterizations ofM, 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, we think of Ctar as the set of user features that a recommendation agent observes post-deployment. The settings are chosen to capture the intuition that, typically, the agent sees highvalue 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 Ctar 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 a randomly selected setting from this representative set. Results are averaged over 300 independent runs; error bars display ±1.96 standard errors. For details on specific parameterizations, refer Appendix D. Figure 1 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, in fact, is a recurring theme – our algorithm’s performance improvement is more pronounced in low T-budget situations, which, as we stated in Section 1.1, is what we are interested in. Further, Appendix C contains plots for two individual settings from the set, one where Std TS and Std UniExp perform significantly better than TargInt TS, TargInt UniExp and TargInt TS UniExp, and another where it is the converse; in contrast, our algorithm performs close to the best baseline in 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, NonCausal Std TS 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 to realistic constraints?”. Specifically, in each run, we (1) randomly pick an i ∈ {1, ..., ⌊NC1/2⌋}, (2) distribute 20% of the probability mass randomly over C1 values {1, ..., i}, (3) distribute the remaining 80% of the mass overC1 values {i+1, ..., NC1}. The c1 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 an 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 2 shows that our algorithm performs better than all baselines
in this experiment, with a more pronounced improvement for the smaller values of T . For instance, when T = 24, our algorithm’s mean regret is around 35% lower than that of the next best baseline.

heading: 4.2 CRM SALES DATA-INSPIRED EXPERIMENT
text: Experiment 3 This experiment seeks to answer the question: “how does the algorithm perform on realistic scenarios?”. We setup the experiment inspired by a 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 a 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 clients, where it would generally not have access to lead source. The causal graph relating these variables is given in Figure 3a, which was obtained using domain knowledge. ‘Deal type’ and ‘Customer size’ are Ctar, ‘Lead source’ is Cother, ‘# outgoing calls’ is X , and ‘Exp. deal value’ is Y . The parameters of each CPD corresponding to this causal graph was calibrated using proprietary sales data from a CRM company, 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 at https://doi.org/10.5281/zenodo.5540348 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.5 Specifically, we ran pure random exploration for 15 rounds at the beginning of each algorithm and updated all CPD beliefs; this simulates a warm-start. Due to this, we used α = 0 for our algorithm. Results are averaged over 50 independent runs; error bars display ±1.96 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.

heading: 5 CONCLUSION AND FUTURE DIRECTIONS
text: This work presented a 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 a novel algorithm that exploits this to achieve improved sample efficiency. In addition to 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 G 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, 2020); it is an interesting question to study this in our setting, when G remains the same between training and evaluation butM changes.
5Other works such as Dimakopoulou et al. (2019) and Liu et al. (2018) have used warm starting as well.
REPRODUCIBILITY STATEMENT
The full proof of Theorem 3.1 is provided in an appendix at the end of this PDF file (after the references) 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 Materials in a file named Supplemental Code Paper1203.zip. Further, even though the algorithms use only the CPDs and not the raw data, the dataset used to calibrate the real worldinspired experiments (see Section 4.2 of main paper) is made available in anonymized form at https://doi.org/10.5281/zenodo.5540348 under the ‘CC BY-NC 4.0’ license. The other experiments were synthetic and did not involve the use of any dataset.
ETHICS STATEMENT
This work is a foundational work that provides an improved mathematical framework and algorithm for contextual bandits. Some experiments were set up utilizing data from a CRM software company (identity witheld for anonymity); 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, we do point out that researchers utilizing this method to their specific applications should adhere to ethical standards of their own (e.g., by avoiding targeting interventions on subpopulations based on racial attributes).

heading: A APPENDIX (SUPPLEMENTARY TEXT): PROOF OF THEOREM 3.1
text: This is the full version of the proof sketch presented in Section 3.2 of the paper. For readability of the proof, we 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(ctar), which is the simple regret given Ctar = ctar. 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 a few other notations to keep the proof more readable:
• c denotes ctar ∪ cother. • a⟨B⟩ is shortened to b when it is unambiguous what a is; for example, c⟨PAV ⟩ is shortened
to paV when it is obvious that c is the current set of values taken by all the context variables. • We write P(V = v|paV ) interchangeably with P(v|paV ) since we use small letters (e.g., v) 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 |do(x), ctar] = ∑
cother∈val(Cother)
P(Y = 1|x,paY ) ∏
c∈cother P(c|paC)
Recollect that we use set operations on vectors as well, wherever there is no ambiguity.
A.1 BOUNDING THE ERROR OF P(Y = 1|x,paY ) ESTIMATES
Let paY denote the value taken by PAY (i.e., Y ’s parents), excluding x. Say, for a (x,paY ), P [ |P̂(Y = 1|x,paY )− P(Y = 1|x,paY )| ≥ ϵx,paY ] ≤ δx,paY
Using the union bound, we can rewrite it as P [ ∀x, |P̂(Y = 1|X,paY )− P(Y = 1|X,paY )| ≥ ϵX,paY ] ≤ δX,paY
In other words, with probability ≥ 1− δX,paY , the following event EX,paY is true:
|∀x, P̂(Y = 1|X,paY )− P(Y = 1|X,paY )| ≤ ϵX,paY We derive expressions for ϵX,paY and δX,paY in Lemma A.2.
A.2 BOUNDING THE ERROR OF P(C = c|PAC) ESTIMATES
Now, say, for a C ∈ C (taking value C = c), and for given paC , P [ |P̂(c|paC)− P(c|paC)| ≥ ϵc|paC ] ≤ δc|paC
Note that P̂(0|paC) + P̂(1|paC) = 1 and P(0|paC) + P(1|paC) = 1. Now, say the actual errors in estimates are given by ϵ̃c. That is, ϵ̃c ≜ P̂(c|paC)− P(c|paC). Therefore,
P̂(0|paC) + P̂(1|paC) = 1⇐⇒ P(0|paC) + ϵ̃0|paC + P(1|paC) + ϵ̃1|paC = 1 ⇐⇒ 1 + ϵ̃0|paC + ϵ̃1|paC = 1 ⇐⇒ ϵ̃0|paC + ϵ̃1|paC = 0
Now, this means that |ϵ̃0|paC | ≤ a⇐⇒ |ϵ̃1|paC | ≤ a
Therefore, the event |ϵ̃0|paC | ≤ a is the same event as the event |ϵ̃1|paC | ≤ a. Therefore, given a paC , the following is true:
P [ ∀c, |ϵ̃c|paC | ≤ ϵC|paC ] ≥ 1− δC|paC
which is the same as P [ ∀c, |P̂(c|paC)− P(c|paC)| ≤ ϵC|paC ] ≥ 1− δC|paC
where δC|paC is a function of ϵC|paC . Note that we now have δC|paC instead of δc|paC .
In other words, given a paC , with probability ≥ 1− δC|paC , the following event EC|paC is true:
∀c, |P̂(C = c|paC)− P(C = c|paC)| ≤ ϵC|paC We derive expressions for δC|paC and ϵC|paC in Lemma A.1.
A.3 PUTTING THEM TOGETHER FOR THE OVERALL BOUND FOR REGRET(ctar)
Using the union bound, for any ctar, with probability ≥ 1 − ∑
paY δX,paY − ∑ C∈C ∑ paC
δC|paC , all of EX,paY and EC|paC are true simultaneously ∀paY and ∀paC ∀C ∈ (C \ PAY ). Let’s call this event E . In other words, under event E , all estimates are bounded. Let aalg = ϕ̂(ctar) denote the action chosen by the algorithm in the evaluation phase when presented with ctar; and let a∗ denote an optimal action for ctar. Therefore, given Ctar = ctar, under event E ,
E[Y |do(aalg), ctar] = ∑
cother P(Y = 1|aalg,paY ) ∏ c∈cother P(c|paC)
(Factorization due to G as earlier) = ∑
cother P(Y = 1|aalg,paY ) ∏ c∈cother {P̂(c|paC)− ϵ̃C|paC}
(Since ϵ̃C|paC are actual errors.) ≥ ∑
cother {P̂(Y = 1|aalg,paY )− ϵX,paY } ∏ c∈cother {P̂(c|paC)− ϵ̃C|paC}
(Due to event E)
≥ P̂(Y = 1|do(aalg), ctar)− ∑
C∈Cother∪Y ∑ cother P(cother|ctar)ϵC|paC ∣∣∣∣∣∣ x=aalg (Algebra discussed separately in Section A.3.1)
= Ê[Y |do(aalg), ctar]− ∑
C∈Cother∪Y ∑ paC P(paC |ctar)ϵC|paC ∣∣∣∣∣∣ x=aalg
(Since Y is binary)
≥ Ê[Y |do(a∗), ctar]− ∑
C∈Cother∪Y ∑ paC P(paC |ctar)ϵC|paC ∣∣∣∣∣∣ x=aalg
(Due to proposed algorithm)
Continuing and applying similar steps, we get E[Y |do(aalg), ctar] ≥ E[Y |do(a∗), ctar]− 2 ∑ paY P(paY |ctar)ϵX,paY
− 3 ∑
C∈Cother ∑ paC P(paC |ctar)ϵC|paC
Defining ϵ′X ≜ ∑ paY P(paY |ctar)ϵX,paY
and ϵ′C ≜ ∑ paC P(paC |ctar)ϵC|paC
we get that,
E[Y |do(aalg), ctar] ≥ E[Y |do(a∗), ctar]− 2ϵ′X − 3 ∑
C∈Cother ϵ′C
Therefore, under event E (that is, with probability ≥ 1− ∑
paY δX,paY − ∑ C∈C ∑ paC
δC|paC ), for any given ctar,
Regret(ctar) = E[Y |do(a∗), ctar]− E[Y |do(aalg), ctar] ≤ 2ϵ′X + 3 ∑
C∈Cother ϵ′C (3)
We derive expressions for each of these terms in Sections A.4 and A.5, and then arrive at the final bound in Section A.6.
A.3.1 ALGEBRA FOR INTERMEDIATE EXPRESSION
We wish to show that∑ cother {P̂(Y = 1|x,paY )− ϵX,paY } ∏ c∈cother {P̂(c|paC)− ϵ̃C|paC}
≥ P̂(Y = 1|do(x), ctar)− ∑
C∈Cother∪Y ∑ cother P(cother|ctar)ϵC|paC
Let us denote the expression on the left hand side by (A).
Let ci ∈ cother chosen in a reverse topological order; this ensures that a child is chosen before any of its parents. Let Ci be the corresponding variable in Cother. Then we can write
(A) = ∑
cother\ci [∑ ci [ {P̂(Y = 1|x,paY )− ϵX,paY }{P̂(ci|paCi)− ϵ̃ci|paCi } ] ∏
c′∈cother\ci
{P̂(c′|paC′)− ϵ̃c′|paC′}  =
∑ cother\ci [∑ ci [ P̂(Y = 1|x,paY )P̂(ci|paCi)− ϵ̃ci|paCi P̂(Y = 1|x,paY )
−ϵX,paY P̂(ci|paCi) + ϵX,paY ϵ̃ci|paCi ]] ∏
c′∈cother\ci
{P̂(c′|paC′)− ϵ̃c′|paC′}
≥ ∑
cother\ci
[ Q̂Ci [Y = 1|x,paCi ]− ϵCi|paCi − ϵ̂X,paCi ] ∏ c′∈cother\ci {P̂(c′|paC′)− ϵ̃c′|paC′}
where
Q̂D[Y = 1|x, c] ≜ ∑
d P̂(Y = 1|x,paY ) ∏ d∈d {P̂(d|paD, c)}
and ϵ̂X,paCi ≜ ∑ ci ϵX,paY P(ci|paCi)
These make use of the fact that ϵ̃ci|paCi ≤ ϵCi|paCi , ϵ̃0|paCi = −ϵ̃1|paCi and that P̂ ≤ 1. We can keep reapplying the above steps in reverse topological order till we exhaust all ci, and we’ll get
(A) ≥ Q̂Cother [Y = 1|x, ctar]− ∑
C∈Cother∪Y ∑ cother P(cother|ctar)ϵC|paC
Noting that Q̂Cother [Y = 1|x, ctar] = P̂(Y = 1|do(x), ctar) gives us the desired inequality.
A.4 EXPRESSIONS FOR δC|paC AND ϵC|paC
Lemma A.1.
P ∀c, |P̂(c|paC)− P(c|paC)| ≤ √√√√[ 2
T ′P(paC , ctar)− ϵTPAC
] ln ( 2
δC|paC ) ≥ 1− δC|paC Proof. Let TpaC be the set of time indices during training when PAC = paC was chosen/seen by the algorithm, and let TpaC = |TpaC |. Now, for a C that is observed and not chosen
6, note that our estimate of P̂(C = 1|paC) is computed as (θ (1) C|paC + 1)/(TpaC + 2). We approximate 7 this as θ (1) C|paC /TpaC . Using Hoeffding’s inequality, for any c,
P [ |P̂(C = c|paC)− P(C = c|paC)| ≥ ϵC|paC ] ≤ 2 exp ( − TpaC 2 (ϵC|paC ) 2 ) But since already observed, the two events (corresponding to c = 0 and c = 1) are the same, we have
P [ ∀c, |P̂(c|paC)− P(c|paC)| ≤ ϵC|paC ] ≥ 1− 2 exp ( − TpaC 2 (ϵC|paC ) 2 ) Therefore, we let
δC|paC ≜ 2 exp ( − TpaC 2 (ϵC|paC ) 2 ) Now, let T ′ ≜ αT be the number of rounds of Phase 1. Let T̃C|paC be the number of times C was updated in Phase 1 as a results of encountering PAC = paC . Note that the mean of T̃C|paC is T ′P(ctar)P(paC |ctar) = T ′P(paC , ctar). By the Hoeffding’s inequality,
P [ T̃C|paC ≥ T ′P(paC , ctar)− ϵTpaC ] ≥ 1− exp ( − 2(ϵTpaC ) 2
T ′
)
By the union bound, we have (let’s call the event as ETC|PAC ),
P [ ∀paC , T̃C|paC ≥ T ′P(paC , ctar)− ϵTPAC ] ≥ 1−NPAC exp ( − 2(ϵTPAC ) 2
T ′ ) where NPAC = ∏ C∈PAC NC .
Letting δTC|PAC ≜ NPAC exp ( − 2(ϵ T PAC )2 T ′ ) , we have
ϵTC|PAC = √√√√[T ′ 2 ] ln ( NPAC δTC|PAC )
Note that TC|paC ≥ T̃C|paC . Therefore, given that E T C|PAC is true, we have
P [ ∀c, |P̂(c|paC)− P(c|paC)| ≤ ϵC|paC ] ≥ 1− 2 exp ( − TC|paC
2 (ϵC|paC )
2 ) ≥ 1− 2 exp ( − T ′P(paC , ctar)− ϵTC|PAC
2 (ϵC|paC )
2 ) 6This means C ∈ C during Phase 1 of the algorithm, or C ∈ Cother in Phase 2. 7It’s easy to see that this does not change the asymptotic behavior of the bound.
Defining δC|paC as
δC|paC ≜ 2 exp
( − T ′P(paC , ctar)− ϵTC|PAC
2 (ϵC|paC )
2 ) gives us
ϵC|paC = √√√√[ 2 T ′P(paC , ctar)− ϵTC|PAC ] ln ( 2 δC|paC ) (4)
A.5 EXPRESSIONS FOR δX,paY , ϵX,paY , AND ϵ ′ x
Lemma A.2. P [ ∀x, |P̂(Y = 1|x, paY )− P(Y = 1|x, paY )| ≤√√√√[ 2
T ′
NX P(paY , ctar)− ϵTX,PAY
] ln ( 2NX δX,paY ) ≥ 1− δX,paY Proof. As before, let Tx,paY be the set of time indices during training when (X,PAY ) = (x,paY ) was chosen/seen by the algorithm, and let Tx,paY = |Tx,paY |. As before, note that our estimate of P̂(Y = 1|x,paY ) is computed as (θ (1) Y |x,paY + 1)/(Tx,paY + 2), which we can approximate as θ (1) Y |x,paY /Tx,paY . Now, by Hoeffding’s inequality
P [ |P̂(Y = 1|x,paY )− P(Y = 1|x,paY )| ≥ ϵx,paY ] ≤ 2 exp ( − Tx,paY
2 ϵ2x,paY ) During Phase 1, let T̃x,paY be the random variable denoting the number of times that (X,PAY ) = (x,paY ) was seen/chosen. Note that, due to the nature of Phase 1 (i.e., each x is chosen with probability 1NX ), the mean of T̃x,paY is T
′P(paY , ctar) 1NX . Therefore, using the union bound and the Hoeffding’s inequality,
P [ ∀(x,paY ), T̃x,paY ≥ T ′P(paY , ctar) 1
NX − ϵTX,PAY
] ≥ 1−NXNPAY exp ( − 2 T ′ ( ϵTX,PAY )2) Since ∀(x,paY ), Tx,paY ≥ T̃x,paY , we have (let’s call this event E T X,PAY ),
P [ ∀(x,paY ), Tx,paY ≥ T ′P(paY , ctar) 1
NX − ϵTX,PAY
] ≥ 1−NXNPAY exp ( − 2 T ′ ( ϵTX,PAY )2) Letting δTX,PAY ≜ NXNPAY exp ( − 2T ′ ( ϵTX,PAY )2) , we have
ϵTX,PAY = √√√√[T ′ 2 ] ln ( NXNPAY δTX,PAY ) Now, we can get that, for a given paY , ∀x, (let’s call it event EX,paY ),
P [ ∀x, |P̂(Y = 1|x,paY )− P(Y = 1|x,paY )| ≤ ϵX,paY ] ≥ 1−
∑ x 2 exp ( − Tx,paY 2 (ϵX,paY ) 2 )
≥ 1− 2NX exp ( − T ′ NX P(paY , ctar)− ϵTX,PAY
2 (ϵX,paY )
2
)
Setting
δX,paY = 2NX exp
( − T ′ NX P(paY , ctar)− ϵTX,PAY
2 (ϵX,paY )
2 ) we have,
ϵX,paY = √√√√[ 2 T ′
NX P(paY , ctar)− ϵTX,PAY
] ln ( 2NX δX,paY ) (5)
A.6 DERIVING THE FINAL REGRET BOUND
The probability that events E , ETPAC (∀C ∈ C) and E T X,PAY are all simultaneously true is
≥ 1− ∑ paY δX,paY − δ T X,PAY − ∑ C∈C ∑ paC δC|paC + δ T PAC  Substituting Equations (4) and (5) back into Equation (3), we get that, with the above probability, for a given ctar,
Regret(ctar) ≤ 3 ∑ paY P(paY |ctar) √√√√[ 2 T ′ NX P(paY , ctar)− ϵTX,PAY ] ln ( 2NX δX,paY )
+ ∑
C∈Cother ∑ paC P(paC |ctar) √√√√[ 2 T ′P(paC , ctar)− ϵTPAC ] ln ( 2 δC|paC ) where
ϵTC|PAC = √√√√[T ′ 2 ] ln ( NPAC δTC|PAC ) and
ϵTX,PAY = √√√√[T ′ 2 ] ln ( NXNPAY δTX,PAY )
We set δ̃ = δX,paY = δ T X,PAY = δC|paC = δ T PAC , ∀C,paY ,paC . Thus, for a given ctar, with probability ≥ 1−NPAY δ̃ − δ̃ −NC\PAY δ̃ − |C \ PAY |δ̃,
Regret(ctar) ≤ 3 ∑ paY P(paY |ctar) √√√√[ 2 T ′ NX P(paY , ctar)− ϵTX,PAY ] ln ( 2NX δ̃ )
+ ∑
C∈Cother ∑ paC P(paC |ctar) √√√√[ 2 T ′P(paC , ctar)− ϵTC|PAC ] ln ( 2 δ̃ ) where
ϵTC|PAC =
√[ T ′
2
] ln ( NPAC δ̃ ) and
ϵTX,PAY =
√[ T ′
2
] ln ( NXNPAY
δ̃
)
Now, noting that NPAY δ̃ + δ̃ +NC\PAY δ̃ + |C \ PAY |δ̃ ≤ (NC + |C|)δ̃, we set δ = (NC + |C|)δ̃. So we get that with probability ≥ 1− δ,
Regret(ctar) ≤ 3 ∑ paY P(paY |ctar) √√√√[ 2 αT NX P(paY , ctar)− ϵTX,PAY ] ln ( 2NX(NC + |C|) δ )
+ ∑
C∈Cother ∑ paC P(paC |ctar) √√√√[ 2 αTP(paC , ctar)− ϵTPAC ] ln ( 2(NC + |C|) δ ) (6) where
ϵTPAC =
√[ αT
2
] ln ( NPAC (NC + |C|)
δ ) and
ϵTX,PAY =
√[ αT
2
] ln ( NXNPAY (NC + |C|)
δ ) Substituting Equation (6) into the definition of Regret in Section 2 of the main paper, we get the expression in Theorem 3.1.

heading: B APPENDIX (SUPPLEMENTARY TEXT): ADDITIONAL EXPERIMENT – UNDERSTANDING THE REASON FOR BETTER PERFORMANCE
text: In this analysis, we try to “understand why our algorithm exhibits better performance than baselines.” We had pointed out intuitively that the Unc measure trades off between exploring new contexts and
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 Experiment 1; it has NCtar = 10, all equally likely, but Ctar ∈ {0, 1} are more valuable than others (i.e., learning the right actions for these contexts can give higher rewards); see code (config setting1.py) for more details. We zoom into the case when T = 15. We do 500 independent runs, count the number of times every possible Ctar value is encountered or chosen, and plot the frequencies. We compare our algorithm’s behavior with two representative baselines – 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 (Ctar ∈ {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.

heading: C APPENDIX (SUPPLEMENTARY TEXT): MORE DETAILS ABOUT
text: EXPERIMENT 1
In the discussion about Experiment 1 in the main paper, it was mentioned that Appendix C contains plots for two individual settings from the representative set – one where Algorithms Std TS and Std UniExp perform significantly better than Algorithms TargInt TS, TargInt UniExp and TargInt TS UniExp, and another where it is the converse – while our algorithm performs close to the best baseline in both. Figure 5 presents those plots. Each result is based on 50 runs.

heading: D APPENDIX (SUPPLEMENTARY TEXT): REGARDING PARAMETERIZATIONS
text: USED IN THE EXPERIMENTS
For the specific parameterizations of all settings used in all the experiments, refer to the README file in Supplemental Code Paper1203.zip as part of the Supplemental Material.

heading: E APPENDIX (SUPPLEMENTARY TEXT): MORE DISCUSSION ON THE CASE
text: WHERE Cother = ∅
If Cother = ∅ (that is, if it is empty), it might appear as 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 as in used in Section 4.1. But now suppose that Ctar = {C1, C0}, whereas Cother = ∅. Consider two targeted interventions, (x, c0, c1) and (x, c0, c′1), where c1 ̸= c′1. Note that the distribution of Y after these two targeted interventions would, respectively, be
P(Y |do(x), (c0, c1)) = P(Y |x, c0) P(Y |do(x), (c0, c′1)) = P(Y |x, c0)
The common term P(Y |x, c0) enables information leakage between these two targeted interventions. To see this, note that if the agent conducts targeted intervention (x, c0, c1), then it is able to update its beliefs about P(Y |x, c0) which improves its estimates of (x, c0, c′1) as well due to the shared term. So Cother = ∅ does not preclude information leakage. Instead, suppose that we are considering the interventions (x, c0, c1) and (x, c′0, c1), where c0 ̸= c′0. 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 (x, ctar) pairs and learning more about already explored “valuable” (x, ctar) pairs. To see this, note that in the definition of Unc in Section 3.1 the “information” component is weighted by the “value” component (the last two terms, namely, P̂(c′) · Ê[Y |c′, do(x′)]).

heading: F APPENDIX (SUPPLEMENTARY TEXT): REGARDING THE CHOICE OF THE
text: PROBABILITY OF UNIFORM EXPLORATION IN TARGINT TS UNIEXP
Thompson Sampling aims to minimize cumulative regret in a best-arm identification setting (Agrawal & Goyal, 2012). For cumulative regret minimization, it performs better than simple exploration algorithms such as ϵ-greedy, by controlling the exploration based on 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 a baseline (TargInt TS), we also create a variation of this (called TargInt TS UniExp) where, in each round, the algorithm, with some probability λ, chooses a targeted intervention uniformly at random (from the space val(X)× val(Ctar)) for exploration; with probability 1− λ, it chooses the targeted intervention given by Thompson Sampling. This probability λ allows us to directly control the degree of uniform exploration.
In Experiment 1 (Section 4.1), we 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 to optimize cumulative regret) and TargInt UniExp (which does uniform exploration). We noted
that our algorithm continues to perform better than all baselines. Figure 6 shows that this continues to be true even when λ in TargInt TS UniExp is not as large as 0.5, by setting λ = 0.2.

Review summaries:
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.