Transportability for Bandits with Data from Different Environments
Authors: Alexis Bellot
Alan Malek
Silvia Chiappa
Venue: NeurIPS 2023 poster (2023)
Keywords: Transportability
transfer learning
bandits
TL;DR: We propose a bandit algorithm that leverages prior data from different environments to learn more efficiently.

Abstract: A unifying theme in the design of intelligent agents is to efficiently optimize a policy based on what prior knowledge of the problem is available and what actions can be taken to learn more about it. Bandits are a canonical instance of this task that has been intensely studied in the literature. Most methods, however, typically rely solely on an agent's experimentation in a single environment (or multiple closely related environments). In this paper, we relax this assumption and consider the design of bandit algorithms from a combination of batch data and qualitative assumptions about the relatedness across different environments, represented in the form of causal models. In particular, we show that it is possible to exploit invariances across environments, wherever they may occur in the underlying causal model, to consistently improve learning. The resulting bandit algorithm has a sub-linear regret bound with an explicit dependency on a term that captures how informative related environments are for the task at hand; and may have substantially lower regret than experimentation-only bandit instances.

Transportability for Bandits with Data from Different Environments
Alexis Bellot, Alan Malek, Google DeepMind London, UK abell abellot@@goggee.com
Silvia Chiappa
Abstract
A unifying theme in the design of intelligent agents is to efficiently optimize policy based on what prior knowledge of the problem is available and what actions can be taken to learn more about it. Bandits are a canonical instance this task that has been intensely studied in the literature. Most methods, however, typically rely solely on an agent's experimentation in a single environment (or multiple closely related environments). In this paper, we relax this assumption and consider the design of bandit algorithms from a combination of batch data and qualitative assumptions about the relatedness across different environments, represented in the form of causal models. In particular, we show that it is possible to exploit invariances across environments, wherever they may occur in the underlying causal model, to consistently improve learning. The resulting bandit algorithm has a sub-linear regret bound with an explicit dependency on a that captures how informative related environments are for the task at hand; and may have substantially lower regret than experimentation-onn bandit instances.
Introduction
Multi-armed bandits (MABs) constitute one of the most widely used frameworks for modeling decision-making under uncertainty. In this framework, an agent repeatedly takes actions in an environment with the goal of optimizing desired objective, such efficiently inferring the action with highest reward or maximizing cumulative rewards in the long run [34]. As in most reinforcement learning problems, there a substantial amount of exploration involved while agent learns about reward distributions under different available actions. This process can be costly in many applications; from an ethical perspective, for example, physicians may not risk compromising their patient's 's health with unknown treatments. It is therefore important to be efficient with experimentation while learning an optimal policy. In the literature, structured bandit instances can help navigate the exploration- exploitation trade-off effectively, for example with assumptions on the functional association between action and reward that facilitate estimation such as linear bandits [1, 15, 19] and causal bandits [23, 36, 28, 27, 24, 26, 12, 29,77 7].
alternative approach alleviate the cost of active experimentation to consider leveraging prior data prior experimentation in related environments to inform agent's 's decision-making, which leads to the hybrid learning paradigm. The expectation (or rather hope) that informative prior data or prior experimentation can serve to narrow down reward distributions and warm start the MAB so as to converge to optimal actions faster and ultimately achieve higher cumulative reward. Current methods can be categorized into multi-task learning [41, 40, 13] and meta-learning [10, 42, 4, 20, 33, 30J. The former aims to solve a prescribed set of related bandit tasks with shared structure, e.g. multiple player scenarios with similar reward distributions. The latter considers an arbitrary number of bandit problems whose parameters are sampled i.i.d. from a meta-prior that
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

can be inferred as the agent experiments across the different related tasks'. However, both families of methods assume relatively restricted class of potential changes across environments and rely explicitly on agent experimentation across all environments for learning. If discrepancies across environments are more general, naively leveraging prior data does not necessarily lead to more informative reward distributions or efficiency improvements in new environment.
As concrete example, consider a learning scenario in which his- torical data is available for the design of a clinical trial aiming to determine the optimal level of a hypertension treatment X for Alzheimer's s disease Y Alzheimer's 's actiology is complex but it well established that patient's ss age Z and blood pressure W contribute to the development of the disease, and so do a num- ber of (typically) unobserved factors, e.g. physical activity levels, socio-economic status, diet patterns, etc. [37] (encoded with bi-directed dashed edge). Such data can be useful but has to be handled with care, especially if we suspect the clinical trial popula- tion to differ in several aspects from that recorded in historical data. We would expect, for example, age distributions P()) to differ. Fig. 1 graphically describes this scenario. A naive approach, ig- noring the differences across populations, can be sub-optimal. Take an instance where variables X, Z, W, Y, U 1): their values are decided by functions: X - U, W < X,Y - Z @ (W- U); @ represents the exclusive-or operator; U is independently distributed in {0, 13 but older individuals historically over-represented P(Z = 1) = 0.6 in comparison to the clinical trial population P(Z = 1) = 0.4. Historical data suggests that the better policy involves a lower dosage X = 0, as B[Y do(X 0)] 0.6 > 0.5 Y do(X 1)], which is the opposite of what is optimal for the clinical trial population.
Sz
Z W
x
Figure 1: Diagram encoding causal structure and differences across environments.
This example shows that differences across environments may be complex, subtle, and non-trivially influence optimal decision-making. Even when one is able to perfectly estimate reward distributions from historical data, the induced policy can still be sub-optimal depending on the location and magnitude of the changes expected across environments. In general, reward distributions will not straightforwardly extrapolate across different environments. In this paper, we attempt to capture this (structural) uncertainty through a causal lens. In the causality literature, this problem appears under the rubric of transportability theory [32, 3, 11]; several criteria, algorithms, and estimation methods have been developed for identifying when and how a causal effect can be computed across environments. Our task, in the bandit setting, is to define learning agent that optimally exploits prior data with knowledge of the potential discrepancies across domains, for any given graph. Prior work [43] has considered specific instances, i.e. environments defined by the Bow and Instrumental Variables graphs, but a general approach applicable to arbitrary graphs and arbitrary differences across environments still missing. Our approach is Bayesian, and involves posterior sampling of reward distributions defined by parameterization informed by the underlying causal structure. Our contribution is develop novel bandit algorithm that achieves sub-linear cumulative regret with an explicit dependency on the entropy of an inferred prior, a quantity that implicitly captures the relatedness between environments. The significance of this result is that guarantees consistent improvements on performance over methods not leveraging prior data. To the best of our knowledge, this is one of the first general attempts to consistently use prior data from related environments in general decision-making scenarios in which causal dependencies can be established.
1.1 Preliminaries
We use capital and small letters to denote random variables and their values respectively, e.g. X and I, and bold capital and small letters to denote sets of variables and their values, e.g. X and æ. The domain of variable X is indicated with Ωx.
A environment's 's data generating mechanism is described by structural causal model (SCM)
[31, Definition 7.1.1]. A SCM M is a tuple (V, U, FF,PP(U) where V is a set of endogenous (observed) variables, U is set of exogenous latent variables, and F (fvlvev is set of functions
A more extensive review of related work is given in Appendix A.
2 [17]] refer adaptive clinical trials as the "chief practical motivation [for design bandit algorithmsJ".
è For this example, Y a measured biomarker of Alzheimer's 's disease that acts as designated reward variable to be maximized.
2

---

such that fy determines values of V taking argument variables Pay S V and Uy S U, i.e. V - -fv (Paa, Uv). Values of U are drawn from an exogenous distribution P(u). We assume the model to be recursive, i.e. that there are no cyclic dependencies among the variables, such as to define a distribution P(V) over endogenous variables V. An intervention or action by an agent on a subset X = V, denoted by do(æ:), is an operation that fixed values of X to constants æ, replacing the functions {fx X E } that would normally determine their values. Let Mr denote the model induced by action do(x)). Accordingly, Mx induces a corresponding interventional distribution over V. denoted P(V2) = P(V) do(x)). We will consistently use X, E V as designated action and reward variables, respectively.
(V.E) describe the functional associations in an underlying SCM M. In particular, we draw a directed edge between two variables V - W E E if V appears as an argument of fw in M, and bi-directed dashed edge between two variables V 4----- W if Uv e Uw * Ø, i.e. V and W share an unobserved confounder. We will use standard family conventions for graphical relationships, e.g- parents pa( x = UXexpa (X) of a set of nodes X E V are all nodes in G with directed edges into elements of X. Its capitalized version Pa includes the argument as well, e.g. Pg(X); == pa( x UX. We will make use a special clustering of the nodes in V called c-components [39]: two nodes are in the same e-component C' S V if and only if they are connected by a bi-directed path. c-components form a partition over exogenous variables: a e-component C V is said to cover exogenous variable U if U Uvec Uv. We denote with Cu the c-component covering U. As an example, the diagram in Fig. has c-components {X, Y), [W), and {2}; and CUxy {X, Y), Cuw = {W), and CUz {Z}. We refer the reader to [31, Chapter 7) for a more detailed review of SCMs.
Causal graphs
2 Bandits with Transportability
From the agent's perspective, the point of departure with respect conventional bandit instances is that in addition to the ability to take actions in deployment environment π², the agent has access to data from one or more related environments π", T², ..... each characterized by SCMs M M ..... We assume that all environments have the same scope, i.e. the same sets V and U, but may differ in any other aspect. In the transportability literature [3, 32], such structural differences between environments are called domain discrepancies and can be encoded in selection diagrams.
Definition (Domain Discrepancy). Let x" and nO be two domains with SCMs M and M There exists a domain discrepancy between H² and x² if fv fty or (UV) # (Uv) for some V e V. Definition (Selection diagram). Given domain discrepancy set Aa. := (V E V : fo * I pa (Uv) + (UVv) between two domains TO and n² and a causal graph G (V,E), let = V e Aa.b) be called selection nodes. The graph go.b -V U. (Sy V) sves) is called selection diagram.
Selection nodes indicate where structural discrepancies between two environments might take place. The absence of a selection node pointing to a variable represents the assumption that the causal mechanism responsible for assigning values that variable is identical in both environments. In the clinical trial example, Fig. shows a selection diagram comparing historical and clinical trial environments, denoted 7* n7 respectively; the presence of selection node Sz indicates potential difference in the assignment of Z, i.e., either fž * f2 and / or (*(uw) * P" P"(uw)) On the other hand, the absence of e.g. selection node Sy indicates the assumption f ff and p* (uy) = (m(uy)) With this formalism, the task is to leverage data from related environments in consistent and efficient manner.
Definition 3 (Bandits with Transportability). Let n* denote the deployment environment in which the agent acts Given samples from PV(V), PV()).... and selection diagrams G* G ...., in each round = 1....,
...,,TT T the agent takes an action x!() and observes a sample from pa (Vatv), adjusting its actions minimize (expected) cumulative regret in n².
Eps RT
Σ Epe Ya Eps Y Ya,n,
that compares the optimal intervention arg max sefix Eps Yz with the agent's 's chosen intervention in each round.
3

---

Quantities such as Ep or (82) are called transportabiliity queries and their estimation with prior data, underlying structural assumptions and their use within active experimentation schemes will be the focus of this paper.
2.1 Informative priors for bandits
Before experimentation takes place there is degree of unidentifiability of reward distributions Pa (Ua) depending on causal assumptions and discrepancies between env environments. For instance, revisiting the clinical trial example, if age distributions are allowed vary arbitrarily across environments, values of (V²)) will similarly vary and thus involve a degree of uncertainty*. This unidentifiability feature relevant even without major discrepancies across domains as p* (yz) may still be unidentifiable in the presence of unobserved confounders. The Bow graph in Fig. 2 (ignoring the selection node) is common example.
One may be tempted to conclude that prior data is rarely useful. However, even under multiple discrepancies across environments, causal effects p* (yz) are rarely completely unconstrained. In general, causal effects lie in non-trivial interval (a,b]. 0 & b < For instance, for the graph ga.* in Fig. 2 (yz) can be shown to be contained in [P' (zz y), (z, y) 1 pa (z)]. In particular, with probabilistic or Bayesian interpretation of un- SCM, that is with an explicit probability measure over SCMs M M(g*)*, one can define a distribution of reward probabilities P* (yy) (or expected rewards) that honestly captures
30
35-
30-
Go.0
Sx
X
0.3
04
0.5
0.6
0.7 0a
D0 10
Expected reward under dotx m 1)
Figure 2: Bow graph and posterior reward density.
known quantities
prior uncertainty in their values. For example, given prior samples T" = {1b)) J = 1..... 500}
independently drawn from a source distribution pa (V(V) (and particular prior model over SCMs, to be discussed in Sec. 2.2), a posterior density over E Y, can be evaluated and sampled from, see Fig. 2 for an illustration, where theoretical bounds are shown with vertical lines.
From this perspective, the problem of doing inference on reward distributions given prior data and knowledge of structural discrepancies can be formulated as optimization problem, that is, evaluate,
| 5 8). such that VV #.5 ft = fi, P (uv) (uv),, (2)
PM--((*)) Eps [22]
where := {ū", ). v²
= (ol : = = 1...,,.,,, is a set of n, independent samples from P'(V). In words, the task is to evaluate distribution expected rewards under intervention over all deployment domains n* compatible with our knowledge prior to experimenting in π*
It remains question, however, how to define model and parameterization of SCMs. Remember that only prior data and selection diagrams are assumed to be available to the researcher; any choices on the distribution of exogenous variables P(U) or functional form of deterministic structural assignments F represent untestable assumptions that are difficult to justify in practice. Going forward we will restrict ourselves to SCMs with discrete endogenous variables (while exogenous variables may be arbitrarily defined, e.g. continuously-valuee with arbitrary probability density functions).
2.2 General parameterization of reward distributions
Systems of discrete observables have the distinctiveness of involving finite number of probabilities of the form p* (y.x,, i.e. one for each combination (ar,y). Reward distributions p* in any underlying SCM M, however complex P(U) and F. may be, can logically be equivalently expressed by a corresponding discrete SCM N in which P(U) is discrete and J is a discrete mapping between finite spaces [44, 6]. This observation is interesting because it allows to consistently and uniquely parameterize P(U) and F. without untestable choices on their form
Formally, we say there exists multiple SCMs Mi. M2 E A with functional dependencies defined by g*. consistent with prior data and selection diagrams, such that PM; (y=) Pat, (yz). MM(**) stands for the set SCMs whose functional dependencies are given by G*.
" similar reasoning does not apply for continuous endogenous variables that would require continuous exogenous variables and therefore (untestable) choice of parametric family for all variables.

---

Algorithm 1 TThomsoon Sampling with Transportability (tTS)
Input:
Selection diagrams {g * *, a. .... prior data (øa, 86 .......
decision variable X, reward variable Y, horizon T.
for rounds = 1, 1,2,. .............................. do
Approximate P (E, 0 0, (200)...: (a(t11)
Sample , ( P (E, 0 8, (2))),.... Uple 1))
(+) - arg max; Ex+ [Y g( 000
Take action (*) and observe Uat0) in end for
Corollary 1 (Proposition 2.7. [44]). For any causal graph G. let M be arbitrary SCM compatible with G. For any sets Y, x < V, the interventional distribution P(ya) could be parameterized as
Σ II a k
1
1LV
(pav.uv)
I Ous
UEÚ
where 02 := P(U = u) defines exogenous probabilities of discrete variables U e U with cardinality g(pav.ur) is a deterministic mapping between finite domains
dy ΠIvec [Ppa(v)): and each Ey Opav x Suu - fly.
For example, p* (ya) in Fig. I can be parameterized by
Σ
1Ky (w,)))
(m, y) 1 (/ w) w)
2)0 On, Paw
(4)
20 Ma
where, assuming X, Z, W are binary, On, is discrete distribution over a finite domain (1,2) since [v, = [[))l 1zzl = 2, 6.... is a distribution over (1, since [Dow! = [p](()) =
[xxl - [0z] = 4, and Ou,, is distribution over 32)] since [50xxl = [(2p(()) 112
(22l [0xl 19w1 |Szz| 1 32. Corol. guarantees that for any value of p* (*yx)) induced by an arbitrary SCM .M there exists a combination of parameters Eq. (4) that reaches that exact same value. In other words, this parameterization is sufficiently expressive to encode any underlying reward distribution.
Parameters that define reward distributions are specific to the deployment environment n* The key observation, however, is that some of them can be inferred with prior data whenever there exists an invariance in P(U) or F across environments as there exists a one-to-one relationship between model parameters and structural features of the underlying SCM. For example, given Fig. 1, the absence of a selection node into Y implies that both functional assignments and exogenous probabilities of Y agree across environments, that is Ey ε9, 0* uy
0a Both may thus be approximated with prior uy
data which in turn constraints or informs pa (yz) even if other parameters in its expression in Eq. (4) remain unknown. The result is a non-trivial distribution over reward probabilities that may be used to warm-start bandit algorithms, even before any experimentation takes place.
2.3 Bandit algorithms
To exploit non-trivial parameter distribution given prior data, a bandit algorithm can be designed to choose actions in proportion to the probability that an intervention leads to highest reward, also known as posterior or Thompson sampling [38, 2]. Specifically, at particular round f of experimentation in the deployment domain n* posterior parameter distributions P (E, evaluated to exactly capture uncertainty given both prior and experimental data up to round t. Action
Uga),- ..... Pga 1)) be
(r(() is then chosen according to the one that gives highest reward, i.e. arg max, Eps YYz g(t), @()),
where (t()) (t)) is an independent draw from its posterior distribution. In other words, the agent
'I will be useful to write & = (E(payy uv) V, Pav c V.Uv c U} and 0 = (0v : U to group all possible functional assignments and exogenous probability parameters, respectively. We will in general omit environment superscripts parameters lighten the notation.
5

---

performs natural Bayesian updates based on both the data available in source environments and its own experimentation as interventional samples Ug(1),.. (z(t-) become available, matching the intuition of most other Thompson sampling bandits in the literature. The full algorithm, called Thompson sampling with Transportability (t.S), is given in Alg. 1.
3 Regret guarantees conditional on prior data
We define information-theorriio regret bounds that aim to capture the exploration-exploitttio trade- off for Alg. I when prior information allows it to infer parts of the environment before experimentation takes place.
Performance in MABs is, to a large extent, intimately related with the agent's uncertainty about which action is optimal, represented by a random variable X S2g S2 - f2 where Ωg x Ωg defines the space of all models M((*) consistent with our knowledge of the deployment environment n² For example, PMr-M(g=(( (X = æ)
[Va] > Er [Yz]. Va' E [x\(2)) where PM-M(S*) is a probability mass function defined over M((*). It is reasonable to assume that one would only choose actions with large regret when it can reduce the uncertainty in X substantially. Following [35, Sec. 5], we define a scalar I'c such that the per-round regret can be bounded by information gain.
B|yx Yx V. & Tay Ir( (X: Vx
(5)
where Vj = (V (Vxa..... V denotes the agent's 's history of interactions with ग up to round (P(,)) (IX))))((())))) denotes the filtered mutual information defined
and Ip (p(X based on P (where DE is the Kullback-Leibhe divergence). Expectations, unless otherwise stated, taken with respect all random quantities. The following proposition, extended from [35, Prop. 11. shows that the Bayesian regret of an agent acting according to Alg. sub-linear with a dependency on the entropy of the optimal action X.
Proposition 1. Let RT denote the regret incurred by following Thompson sampling (Alg. 1). For any T' and I > To then
E[
σ)
T TV H(X B)T,
where H(X v) is the conditional entropy of X given ö.
Proofs are given in Appendix C.
This bound is interesting because it cleanly relates the regret with the uncertainty about the optimal action conditioned on prior data. On one extreme, if data from source environments fully characterizes the optimal action, the entropy equals O, and no further experimentation is required; on the other extreme, if data from source environments have relationship with the target query, the entropy equals log(1S2g [ ). and the bound reverts to conventional worst-case guarantees [35]. The entropy of the optimal action is often not sufficient to capture the information from ő as X may still have a uniform distribution even though posterior distributions over (0, {) have tightened. In other words, there is additional structure among different reward distributions that is not captured by the entropy of the optimal action. Such setting can be analyzed with different assumption on the per round regret that explicitly considers model parameters (0,E) to quantify information gain,
E[Yx
Yx Vr, 0] & ".V/PLIVV. e (0. E; Vx(e)) +
where > is an additional slack term. Accordingly, the following proposition provides an alternative bound using a conditional analogue of [25, Prop. 2].
Proposition 2. Let Rr denote the regret incurred following the policy defined by Alg. 1. For any Te N. if Eq. (7) holds with I for all
E[RT
6] (TT(po))) (0.VVV.. Vx VX(T))
E(e.).
(
$I', called the information ratio and quantifies the trade-off off between incurring low regret and gaining information about the optimal action. I' can always be upper- upper-bounded by [/2x/2 [35, Sec. 5J. We provide a derivation of bound for I' for specific set of environments example in Appendix C.3.

---

This proposition shows that if prior data allows the agent to concentrate (0, {) around some value, additional experimentation does not provide much more information and the regret should be small. In principle, it is possible to get precise per-round regret values by inferring values for T2 and ér through the construction of concentration inequalities for the reward variable, as done by Lu et al. in [25, Lem. 3]. We adapt this result using conditional information-theorrtiee quantities in the following proposition.
Proposition Fix 5 0 and choose T such that \Y= B[y; V1. ū] & 2 V.. for all æ e ftx simultaneously with probability greater than 1 - 6. Then Alg. I chooses actions X(t) that satisfy
V. Yo)
E Yxio Vv, Øj & I' 1p v) (.0 Vx.) + SB,
where B 3 O is such that supy y y & B.
4 Posterior approximations
This section describes a tractable algorithm to evaluate posterior distributions of the form P(E, 0 c, Ug(t)).... (=))-)) and its posterior updates when new data is collected. Priors on &, 0 may be defined such as to induce tractable conditional distributions that may be used within a Gibbs sampling framework. The Gibbs sampler starts with some initial value for all latent quantities (U.E. 0) in our target expected reward
Ep. [Ya]=
Σ vefly
yp (Y, -) ((3)
y Σ
II dy. VeViX
1 ([c(pav.uv) 20 1I 0a. UEU
(10)
Uet
and samples each one iteratively using their conditional distributions, each parameter conditioned on the current values of the remaining terms in the parameter vector and the available data [16]. As mentioned, what data point carries information about which parameters depends on the structural differences between environments.
Prior. For every V V, Vpav, uy, the functional assignment parameters EV <(pay.av) are drawn uniformly in the discrete domain Py. For every U, exogenous probabilities Or with dimension dy Ivecc [Rpa(V)] are drawn from a prior Dirichlet distribution (here chosen for conjugacy with the categorical distribution of U), Ou = (0I,...,
Dir(a)...,,áu)) with hyperparameters
Odg.
Posterior. In particular round the Gibbs sampler iterates over the following steps.
1. Sample u. We start by sampling a corresponding exogenous latent variable for each observed sample (n) (8, "g.,,..., (2()-1), l,..., ....,,,,++, ny. Let (ū, ug ( denote the corresponding set samples of U. Exogenous variables (7)) are mutually independent given V(n), g and thus we can sample each separately using the conditional
(pa (((")) = (()) (cv
(m (,m)),..0 oc (( (n)) (5) - II
On. (11) UEE
II
VeV
Sample &. Similarly, for fixed pay, uv parameters < c(pay.uv) are mutually independent given G, ug.),.... U2(t-1), U, ug())...... U, O. As mentioned, each parameter is updated with the subset of (Ø, Ug........ () U. u.(.)..... .,,,,...,,,.....)) associated with environments in which the functional assignment of V is invariant across source and deployment environ- ments. As they represent a mapping between variables, its conditional distribution is given by P(c)pay ((p(pa)
D. Ug(0y.... B2u-1), u, Ug(l)..... Ug((-)))
if there exists (rel-
evant) sample (x(x), pay u (n)) that fixes the mapping pay uv v(m), Otherwise, P(Ey p(e(pay.my)
(n)
(x) (n)
ö, Vy(1), Bgt 1), u, U,()), (g((e))) 17) is sampled uniformly from discrete distribution over Sy.
Sample O. Fix U E U. By conjugacy of Dirichlet distributions with the categorical distribution, its conditional distribution given all other quantities is given by Dirichlet distribution Oy
7

---

P( Mgon ... Pard
P(-1 F)
P( P. F Fa0D
1.0
Expected rewards
Action x
Action
0.8
0.6
0.6
0.4
Sz
Z
x
0.0
100
200
300
400
500
0.0
300 Rounds
Rounds
(a) ga.*
(b) Regret without prior data.
(c) Regret with prior data.
Figure 3: Performance figures related to Experiment
0, (.(1))-..3 (2(e-1); u. ... 1 Dir (31,-..,, Bdy) where Bj == 0g+ ag+ 1 {u(() " and, similarly, n iterates over the samples (ū, (g,()),-... gg associated with the subset of environments in which exogenous probabilities match the deployment environment.
This procedure eventually forms Markov chain with the invariant distribution E. v, ... gt 17). We plug in one of these samples E. P 0 | 0, Pg(1)..... ggt 1) into Eq. (10) for different æ to choose the next action x(()) This sample initializes chain for Plu, . (y(t)) in round ( of Alg. 1.
So far, we have described algorithms, approximations, and regret guarantees that pre-suppose the correct specification of causal and selection diagrams across multiple domains. Some degree of misspecification, however, can be tolerated without voiding guarantees on performance improvements. We discuss more details in Appendix B.
5 Experiments
We evaluate the proposed approach on several synthetic scenarios inspired by the literature on clinical trials and advertising. We compare Thompson sampling with additional data sources (tTS, Alg. 1) with Thompson sampling with uninformative priors (TS) [38], a KL-UCB [9] algorithm with uninformative priors (UCB), and as a baseline also include the algorithm that chooses actions uniformly at random (Un f For rm)) . For all algorithms, we measure their regrets Ry. averaged over 10 repetitions. Details on all data generating mechanisms and a discussion on mis-specification and limitations of the proposed approach can be found in Appendix D and Appendix B, respectively.
Experiment We start by evaluating the usefulness of prior data by comparing learned distributions of expected reward with and without access to prior data. We consider a bandit problem with action, reward and contextual variables X, Y. Z {0, 1}, respectively, characterized by Fig. 3a in which 1000 prior data samples are given from an environment T" that differs in the causal assignment of Z in comparison with the deployment environment Specifically, with this model,
P*()))
Σ
1 (e
y v) 2)0uu Oazyy
(12)
where (Cy, Ow..)) are invariant across environments while (Ez, Ow.) are specific to the deployment environment. We start by considering Fig. 3b that gives samples from Ep [P=[{x]] uym...... 2 function of experimentation rounds I, that without making use of prior data 6. Distributions of expected rewards under action æ 0 and æ = 1 overlap substantially until round = 300 at which point & 1 is inferred to lead to higher expected rewards. Fig. 3c gives similar plot with the exception that the left part of the plot gives prior samples Ep* [Y=] ö illustrating the shape of the expected reward distribution learned from prior data only. In particular, we observe Ep [Y-11] concentrated in the interval [0.3, 0.9] and Ep o= & concentrated in the interval [0.1, 0.8J. The
"In contrast to related work, causal bandit algorithms are designed single environments with multiple intervention targets, meta-learning bandit algorithms require experimentation multiple related environments, while in the setting considered in this paper, data from source environments are given as a batch. Both sets of methods thus focus different class of problems. See Appendix A for more details.

---

agent starts experimentation at round t = 0 with this prior and from then onward expected reward samples are drawn from Eps [y 8, (,()),...... 22(0) function of experimentation round The bandit algorithm with prior data is remarkably more efficient, being able to determine x 1 as the superior action after only rounds of experimentation. Overall, prior data leads the bandit algorithm to pull the optimal arm in 99% of time versus 93% of the time without prior data.
Experiment 2. We revisit our introductory example to quantify the benefit of leveraging historical patient data from various hospitals. In this example, the objective is to infer the optimal level of hypertension medication X. We are given a choice among 5 different levels, i.e. |92x| 5, and wish to increase the probability of the presence of a beneficial biomarker Y, i.e. |Sty] 2. in the clinical trial population x* given that we have prior observational data in different hospital n². The selection diagram describing this causal protocol is given in Fig. 1. Regret comparisons for all algorithms are given in Fig. 4 (I.H)). We observe a significant gain performance by tTS that chooses the optimal intervention in 67% of the rounds in contrast with 35% of the rounds for TS, and 28% of the rounds for UCB (and 17% for an algorithm choosing interventions at random).
We use this example also to illustrate empiri- cally the dependence between regret and prior entropy shown in Prop. (RHS). For this, we consider different prior beta distributions for (" = 1 z), specifically with increasing standard deviations around the true value of
303
290-
UCB Uniform
p* ( 1 .)) for each a fxx. A larger standard deviations implies less informative prior and higher entropy of the random vari- able X that denotes the optimal action. The entropy of X takes values in the interval [0.2, 1.4] for assumed Beta priors for P*( -1 x)) with standard deviations in the interval [0.001, 0.1]. Fig. 4 (KHS) demonstrates empirically the influence of the entropy X on the expected cumulative regret given in Prop. 1. In particular, narrower, more informative priors lead to better regret.
2000
4003
Rounds
0000
0000
10000
Square root of Entrapy
62
0.
0.6
Figure 4: Performance figures related to Experiment 2.
Experiment This example considers an advertiser seeking optimize which ads show visitors on particular website. For each visitor, we choose one out of a collection of 6 ads X, |Ωxl = 6, some of which will be more engaging than others, to ultimately optimize whether user clicks Y (0, 1). Each ad has some theoretical but unknown click tlick-through-rate p* (Ux).
In this example, data points from an ad recommendation sys- tem used ferent environment n² There, the effect of an add X on the number of clicks is con- founded by the user's age A, (here categorized into old and young such that Q2 = (0, and [2a] 2) and the user's product pref- erences level W, which interacts with current ad-recommendation system through a user's browsing history Z and location (not observed and therefore represented with a bi-directed edge be- tween W and X). Moreover, in this example, the relationship between W and Y is itself confounded by unobserved factors. The population visiting the website of interest * where the MAB will be deployed, is known to agree all causal components with Th except on the distribution of age A. This causal protocol as well as regret comparisons for this example are shown in Fig. 5. We observe noticeable improvements in regret with prior data and knowledge of structural differences TTS substantially improves over algorithms agnostic of prior data.
assume access to 500
CTS
T5
different website, i.e. dif-
202
Gur
Regget
150
100
SA
2002
4000
0002
30200
Figure 5: Performance figures related to Experiment 3.
Conclusions
This paper investigated the problem of improving the efficiency of multi-armed bandits using batch data from related enviromments. As source environments might differ, some knowledge of structure and (potential) discrepancies are necessary to extrapolate consistently. This paper demonstrated that knowledge of selection diagrams that encode causal influence as well as potential discrepancies

---

across source and target environments, without, however, explicit specification of functional form and distributions, is sufficient to consistently define an informative prior over reward distributions using data from arbitrary environments. The resulting algorithm guarantees improvements in regret comparison to algorithms agnostic of prior data. To our knowledge, this serves as one of the first principled approaches to consistently leverage prior data in the context of bandits and we hope it can pave the way for developing more general transfer learning methods in reinforcement learning.
References
[1] Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127-135. PMLR, 2013.
[3] Elias Bareinboim and Judea Pearl. Causal inference and the data-fusion problem. Proceedings of the National Academy of Sciences, 113(27)7345--352) 2016.
[4] Soumya Basu, Branislav Kveton, Manzil Zaheer, and Csaba Szepesvári. No regrets for learning the prior in bandits. Advances in Neural Information Processing Systems, 34:28029-2804 2021.
[5] Alexis Bellot and Elias Bareinboim. Partial transportabilityy for domain generalization. Technical Report R-88, Causal Al Lab, Columbia University, 2022.
[6] Alexis Bellot, Junzhe Zhang, and Elias Bareinboim. Scores for learning discrete causal graphs with unobserved confounders. Technical Report R-83, Causal Al Lab, Columbia University, 2022.
[7] Blair Bilodeau, Linbo Wang, and Daniel M Roy. Adaptively exploiting d-separators with causal bandits. arXiv preprint 22X::2202.05/00 100, 2022.
[8] Léon Bottou, Jonas Peters, Joaquin Quiñonero- Cuiñoneeo-Candela, Denis X Charles, D Max Chickering. Elon Portugaly, Dipankar Ray. Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14(11), 2013.
[9] Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback-Liiler upper confidence bounds for optimal sequential allocation. The Annals of Statistics, pages 1516-1541, 2013.
[10] Leonardo Cella and Massimiliano Pontil. Multi-task and meta-learning with sparse linear bandits. In Uncertainty in Artificial Intelligence, pages 1692-1702. PMLR, 2021.
[11] Juan Correa and Elias Bareinboim. General transportabiliity of soft interventions: Completeness results. Advances in Neural Information Processing Systems, 33:10902-11091 2020.
[12] Arnoud AWM de Kroon, Danielle Belgrave, and Joris M Mooij. Causal discovery for causal bandits utilizing separating sets. arXiv preprinl arXiv:2009.079) 2020.
[13] Aniket Anand Deshmukh, Urun Dogan, and Clay Scott. Multi-task learning for contextual bandits. Advances in neural information processing systems, 30, 2017.
[14] Alun Evans, Veikko Salomaa, Sangita Kulathinal, Kjell Asplund, François Cambien, Marco Ferrario, Markus Perola, Leena Peltonen, Denis Shields, Hugh Tunstall- et al. Morgam (an international pooling of cardiovascular cohorts). International journal of epidemiology, 34(1):21-27, 2005.
[15] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in Neural Information Processing Systems, 23, 2010.
[16] Alan E Gelfand. Gibbs sampling. Journal of the American statistical Association, 95(452): 1304, 2000.
10

---

[17] John C Gittins and David M Jones. A dynamic allocation index for the discounted multiarmed bandit problem. Biometrika, 66(3):561-565 1979.
[18] Limor Gultchin, Virginia Aglietti, Alexis Bellot, and Silvia Chiappa. Functional causal bayesian optimization. arXiv preprint (tth:23360064099 2023.
[19] Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 33:10753-10763 2020.
[20] Joey Hong, Branislav Kveton, Manzil Zaheer, and Mohammad Ghavamzadeh. Hierarchical bayesian bandits. In International Conference Artificial Intelligence and Statistics, pages 7724-7741. PMLR, 2022.
[21] Nathan Kallus and Angela Zhou. ronfounding-robust policy improvement. Advances in neural information processing systems, 31, 2018.
[22] Juha Karvanen. Study design in causal models. Scandinavian Journal of Statistics, 42(2):361-
377, 2015.
[23] Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: Learning good interven- tions via causal inference. Advances in Neural Information Processing Systems, 29, 2016.
[24] Sanghack Lee and Elias Bareinboim. Structural causal bandits with non-manipulable variables. In AAAI Conference on Artificial Intelligence, volume 33, pages 4164 4172, 2019.
[25] Xiuyuan Lu and Benjamin Van Roy. Information-thhoortic confidence bounds for reinforcement learning, Advances in Neural Information Processing Systems, 32, 2019.
[26] Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Causal bandits with unknown graph structure. arXiv preprint arXiv:2106. 006:2220060 02988, 2021.
[27] Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret analysis of bandit problems with causal background knowledge. In Conference on Uncertainty in Artificial Intelligence, pages 141-150. PMLR, 2020.
[28] Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and Zhenyu Yan. Regret analysis of causal bandit problems. arXiv preprint arXiv: 04.9938 2019.
[29] Alan Malek and Silvia Chiappa. Asymptotically best causal effect identification with multi- armed bandits. Advances in Neural Information Processing Systems, 34:21960-21971, 2021.
[30] Hyejin Park, Seiyun Shin, Kwang-Sung Jun, and Jungseul Ok. Transfer learning in bandits with latent continuity. 2021 IEEE International Symposium on Information Theory (ISIT), pages 1463- 1468. IEEE, 2021.
[31] Judea Pearl. Causality. Cambridge University Press, 2009.
[32] Judea Pearl and Elias Bareinboim. Transportability of causal and statistical relations: A formal approach. In Twenty-fifth AAAI conference on artificial intelligence, 2011.
[33] Amit Peleg, Naama Pearl, and Ron Meir. Metalearning linear bandits by prior update. In International Conference on Artificial Intelligence and Statistics, pages 2885-2926. PMLR, 2022.
[34] Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin the American Mathematical Society, 58(5):527-535, 1952.
[35] Daniel Russo and Benjamin Van Roy. An information-theereett amalysis of Thompson sampling. Journal of Machine Learning Research, 17(1):2442-2471, 2016.
[36] Rajat Sen, Karthikeyan Shanmugam, Alexandros G Dimakis, and Sanjay Shakkottai. Identifying best interventions through online importance sampling. In International Conference on Machine Learning, pages 3057-3066. PMLR, 2017.

---

[37] Ingmar Skoog and Deborah Gustafson. Update on hypertension and alzheimer's s disease. Neurological Research, (8(6):6056611 2006.
[38] William Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 2583-4);285-294, 1933.
[39] Jin Tian and Judea Pearl. general identification condition for causal effects. eScholarship, University of California, 2002.
[40] Zhi Wang, Chicheng Zhang, and Kamalika Chaudhuri. Thompson sampling for robust transfer multi-task bandits. arXiv preprint arXiv:2206.085. 08556, 2022.
[41] Zhi Wang, Chicheng Zhang, Manish Kumar Singh, Laurel Riek, and Kamalika Chaudhuri. Mul- titask bandit learning through heterogeneous feedback aggregation. In International Conference on Artificial Intelligence and Statistics, pages 1531-1539. PMLR, 2021.
[42] Kan Xu and Hamsa Bastani. Learning across bandits high dimension via robust statistics. arXiv preprint arXiv:2112.12233 2021.
[43] Junzhe Zhang and Elias Bareinboim. Transfer learning in multi-armed bandit: causal approach. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 1778-1780, 2017.
[44] Junzhe Zhang, Jin Tian, and Elias Bareinboim. Partial counterfactual identification from observational and experimental data. arXiv preprint arXiv:2110005699 2021.
12

---

Appendix for "Transportability for Bandits with Data from Different Environments"
This Appendix includes
Related work in Appendix A.
Discussion limitations and analysis of misspecification in Appendix B.
Proofs in Appendix C.
Details on the data generating mechanisms Appendix D.
Details the Gibbs sampler in Appendix E.
A Related work
In the bandit literature, problems of transfer learning in which existing experience and knowledge is used to improve the performance of an agent appear under the rubric of multi-task learning and meta-learning. Typically, in the context of multi-task learning the agent aims to solve a prescribed set of related bandit tasks with shared structure. For example, [41] consider the setting in which multiple players interact in an environment with the property that each player has slightly different associated reward distributions. [40] extend this approach to the Thompson sampling algorithm with an assumption that reward distribution between players are close but not identical. Similar ideas can be found in the contextual case in which, e-g. [13] propose to leverage similarities in contexts for different arms and improve prediction of reward distributions from contexts. In the context of meta-learning, the agent is designed work well on an arbitrary number of tasks from common environment (i.e. sampled from a prescribed distribution). relying on already completed tasks from the same environment. For example, [4, 20, 33] assume hierarchical bandit structure in which parameters governing multiple bandit instances are sampled i.i.d. from meta-prior. The authors demonstrate that updates on the meta-prior from one instance can benefit other instances and that regret bounds over sequence of instances can be established. [30] adopt a similar setting to infer Lipschitz continuity constant which can be used to derive scale free regret bounds. Others, e.g. [10, 42], have assumed that structural parameters of each instance can be decomposed into shared component and an mnstance-specifie component, and learned with high-dimensional regularization schemes.
Existing methods adopt relatively wide range of assumptions on the "relatedness" of different bandit instances or players that include, as surveyed above, the existence of a meta-distribution across bandit instances, assumptions on the pairwise similarities in the reward distributions of different players, assumptions on the decomposition of bandit parameters, and assumptions on the distribution of contextual variables and their association with rewards. The environment and causal structure typically remain invariant across bandit instances, and only small and specific set of changes in distribution are allowed across bandit instances.
The proposed approach aims to tackle more general setting in which we allow for arbitrary changes in the causal mechanisms underlying each environment as long their location can be established and encoded in selection diagrams, i.e. graphs that describe the difference in structure across domains without constraining their form. In the causality literature, these analyses fall under the transportability umbrella. Several authors have demonstrated the power of this approach to identify causal effects, predict counterfactual distributions and, more generally, make inference across different environments [3, 11, 32, 5]. In the bandit literature, there is also an extensive literature on various ways of exploiting knowledge of a causal graph for a single environment, known as causal bandits [23, 36, 28, 27, 24, 26. 12, 29, 7, 18]. Within this literature the causal graph specifies dependency structure between different actions that allows an agent to identify redundant actions and ultimately more efficient exploration, improving regret bounds by multiplicative factor. Practical examples of the use of causal graphs (within decision-makine problems) are prevalent in the contexts of clinical trials, healthcare, and advertising. We note, in particular, the examples in Figs. 2, 3. 4, in [22] that encode the design of case-cohort studies and clinical trials used in the MORGAM study [14] using causal graphs for the estimation of causal effects. Separately, [21] consider the
13

---

International Stroke Trial and the known causal associations between relevant features for policy optimization. In the context of advertising, [8] describes the use of causal methods with several detailed examples. Specifically, Figs. 3, 4, and 6 in [8] show examples of causal graphs that may be defined for particular computational advertising applications. See also [5] for bandit algorithm leveraging the computational advertising graphs in [8], and[36, Sec. 5.2] for similar causal treatments also the context of advertising. So far, however, all bandit algorithms exploiting causal knowledge have been studied in the "single environment" setting without access to prior data. Variations among existing proposals are due to the class of graphs or the extent of knowledge of the graph, egg. with without knowledge of the full causal graph, with or without unobserved confounding, etc. One may interpret the proposed approach as extending the causal bandit formalism to problems which data from multiple different environments is available prior to agent experimenting in target environment, all of which are, as in the causal bandit literature, described by underlying causal models.
14

---

60
101
20
50
50
bn Experted reward under doge mn
Pepected dodam
Pepected
Pxpeatedd under dofe
(a) PM (a) arbitrary.
(b) pM (a) e [0.2, 0.8).
(c) (*) [0.3,
(d) (*) [0.4.
Figure 6: Prior expected reward distributions under misspecification of Z.
B Limitations and further analysis
Knowledge of structure may detract from the appeal of active experimentation and might limit the extent to which the proposed approach can be applied. Although in practice several techniques can be used to alleviate this problem such causal discovery considering multiple causal graphs as potential causal explanations for the phenomenon of interest, significant domain knowledge will in general be necessary for consistently using prior data. This observation holds for causal bandits more generally.
B.1 Misspecification
Some degree of misspecification, however, can be handled without voiding guarantees performance improvements, especially when the assumed causal graphs and selection diagrams form super-models for the underlying phenomenon of interest.
Starting with causal graphs: a causal graph Ga.b defined as a graph (V, ) is said to be super-model of causal graph G (V.E) & = É. For any causal graph G it holds that adding an edge, creating new graph G, creates larger set of SCMs M(ğ) that subsumes M(g), i.e. M(G) M(),, and as a consequence any SCM with non-zero mass under (M(()) also has non-zero mass under P (M This ) remain valid whenever the causal graph is a super-model of the true underlying graph G as the space of models defined by G is included in the space of models defined G. For example, consider a scenario which source and target domains are equal with an underlying causal graph given by with knowledge of the graph and source data distribution P(x, y). reward probabilities under agent intervention can be uniquely computed, i.e. P(y do(x)) = P(y x)). However, if we are unsure about the presence of an unobserved confounder between X and Y, we may instead consider super- model {X Y, <----+ Y} under which reward probabilities under agent intervention can be determined to be distributed in the interval [P(x,, y), P(z, y) + 1 P(=)], that, in particular, includes the true value P(y do(z)) = P(y xt). Inference based on & instead of G leads to less informative reward probabilities but remains correct and informative with respect to methods not leveraging prior data as 0 & P(z, 3) P(y do(x)) & P(x, v) + P(x) 1.
implies that prior distributions P (M))( EpM [Y=]
{X Y). Prior to experimentation
similar reasoning can be applied selection diagrams and selec- tion nodes, as the latter only indicates potential discrepancy across domains. A selection diagram ga.b defined as a graph (V UV is said to be a super-model of a selection diagram go.b (V S.E)
Sy
x
S $ and E = E. In words, super-models can have more edges or selection nodes. causal mechanism differs or not, they may still conduct correct inference by being conservative and assuming that a discrepancy exists. Under these types of mis- specification, where assumed selection diagrams represent super-models of the underlying data generating process all claims and propositions hold and we can guarantee to never under-perfomn methods that do not consider prior data or their structure. For example, consider system with binary variables X, Y (0, whose causal association and differences across domains are given by Fig. 7. In reality, target and source environments coincide and, with access to batch data from the source environment n², one could uniquely identify expected rewards by computing EpsY, Y Σ,, y Σ, (2 2) (2).. However, suspect some degree of discrepancy in the
Figure 7: g
researcher unsure of whether
15

---

20.0
8 17.5
Run Uie (oRcorio)) 2.
3
12:5
10.0
7.5
10
100
500
1000 2000
5000
10000
Numbor actions
samples
(b)
Figure 9: Run time experiments.
causal assignment of Z across environments, and will consider inference of expected rewards under various degrees of discrepancy, e.g. one may explicitly assume that either P* (z) is arbitrary or
for example assume (=) E [a, bj. We illustrate various such scenarios Fig. Each panel, from right to left increases allows for a greater level of uncertainty that results in a correspondingly wider distribution of expected reward prior to experimentation. The corresponding regret of bandit algorithms that incorporate these bounds Z in _s to warm start the distribution of expected regret prior to experimentation are given in Fig. 8. We observe that the wider the prior the higher the corresponding regret, which illustrates how degrees of prior knowledge influence regret.
Using the same reasoning, holds that if instead the researcher misses edges or incorrectly assigns priors on the causal mechanisms to be expected in the target do- main, prior inference will be incorrect in general. For example, if distributions of expected reward in Fig. do not cover the true expected reward, then bandit algorithm will need to correct for such biased prior
10
(0)
[202
Regret
(0)) 0.7]
P" ('
and we can expect cumulative rewards to be lower than those of an algorithm that ignores prior data and structure.
The extent to which the corresponding regret of bandit algorithm incorrectly making assumptions on structure and discrepancies across environments will depend on the underlying causal graph and functional associations between variables.
25
50 75 100 Rounds
125
150
175 200
Figure 8: Reggret under misspecificatiin.
Most of the discussion in the main body of this paper has assumed knowledge of a discrepancy between environments without considering its magnitude, although the previous example shows that knowledge of bounds or distributions of some of the variables that differ in the target domain can be incorporated. It is worth noting that other kinds of domain knowledge may be available, such as in the functional form of an association in the target domain, specific magnitudes of differences expressed within such functional form, etc. It would be interesting task to consider how to use that information optimally.
B.2 Run time evaluations
Reward distributions P* (yzz) induced by any underlying SCM can be expressed by corresponding discrete SCM in which P(U) is discrete and F is a discrete mapping between finite spaces. The complexity of the corresponding parameterization depends on the underlying selection diagram and dimensionality of observed variables.
In particular, in given iteration of the Gibbs sampler, posterior updates are done for each parameter separately so that computational time is proportional to the parameter count, approximately. which in turn is determined by the cardinality of variables well as the structure of the graph. For fixed graph, assuming that each update requires a small constant amount of time to compute, we could therefore establish analytically how computational time scales with the cardinality of variables. For arbitrary graphs, an analytical result is in general more involved as the parameter count increases differently depending on the local structure of each variable.
an example for illustration, consider the graph in Fig. 9a where X is an action variable, Z is contextual variable, and Y is reward variable. Following the parameterization in Corol. 1, the cardinality of parameters is defined as follows: 10vl |2xl [zz) |1 Exl
[8xx - [8zl |, [Ezl 122x. [exl.1Ey) |22x [ΩZ |syl [Pz].
16

---

We would expect run time to increase linearly with the cardinality of variables X, Y and to ierrasse "slower than quadratically" with the cardinality of Z. Fig. 9b gives run time evaluations of the proposed bandit algorithm using 1000 rounds of experimentation as function of the number of actions. Fig. 9c evaluates the influence of the size of prior data on run time by plotting the time required for drawing 1000 samples from the prior P(- B) with increasing prior data size (in addition
to 1000 samples Gibbs samples that are discarded as burn-in). For both Figs. 9b and 9c we observe run time to scale approximately linearly with the cardinality of the action space and sample size.
17

---

C Theoretical results
C.1
Preliminaries
Counterfactuals and optimal actions We have defined in Sec. 1.1 the fact that intervening in an SCM results in new model that differs in the causal mechanisms subject to interventions. In this section, we extend this notion to consider models derived from interventions that replace causal mechanism with another function, not necessarily a constant. This gives consistent definitions for counterfactual random variables of the form Yx that appear in Sec. 3.
Definition 4 (Intervened model). Let M be an SCM, U = U, X V, and X Ü - Sxx a function. Then, Mx called the intervened model of M subject X, is identical to M, except that the function fx is replaced with the function X.
Uncertainty in Mx is similarly encoded by the distribution P(U) which when averaged over leads to random variables Y for Y E V that describes the random variable Y under a model M This definition is tightly related to that of potential outcome as define in Sec. 1.1, but the former explicitly allows for interventions that do not necessarily fix the variable to a constant value. Probabilities in this model can be computed using the chain rule
P(Yx = y)
- x)X = x)dr.
(13)
J2x
And similarly expectations are given by
[ Jty Jux
Ep(yx]
yP(Y, = X x(X xx)drdy.
(14)
In turn, which action is optimal is represented by a random variable X 22 x Gg - Ωx where Ωg No defines the space of possible models M := M(E, 0) _M{x**) that parameterize the deployment environment x². For example, PM-MiG, xX x) PM~MIG *) (Ep [Y,] > Ep., [Yz], Va' E Ω2x (x)) where PM-MiC,e) is probability mass function defined over the space of possible models M(
Information Theory Definitions This section provides a definition of all the information-thheoreicc terms used throughout and shows that they can be generalized to mixed quantities that include discrete and continuous random variables in consistent manner. For a discrete random variable X Ωxx. the Shannon entropy and its conditional counter parts are defined as
H(X)= == Σ
P(X = x)) log P(X x),,
H(X 2 = 2) = Σ
P(X = x. 7 2) log P(X x = 2) and,
xrf
H(X 1) = Σ
H(X Z = P(Z = z).
sef2
With a slight abuse of notation, we will define the filtered entropy as
H(X Ū) - Σ P(X x 8) log P(X = x 0),
zeX
where e is dataset.
Given two probability measures P and Q, where P is absolutely continuous w.r.t. Q so that the dP is well defined, the Kullback-Leibler divergence is Radon-Nikodym derivative aq
f log dP dP. dQ
DkI(PIIQ) =
which allows the standard definition of mutual information:
Ip(X;Y) Dr=((((XXX)II(X)))1
18

---

where the subscript P that denotes the probability distribution used is sometimes omitted if unam- biguous. Equivalently, we can define the mutual information and conditional mutual information by
I(x;)) =(X) H(X Y) and I(X;Y Z) H(X Z) - H(X 1Y,2),
and we will also need the filtered mutual information,
Ip() Y) = DKL(P
2 = 2) P(X P(Y Z = 2]);
where will typically evaluate PL e) = D( V, P) Vi, UY Vi, サ)) where recall V := (V (e-) } denotes the random variables associated with the agent's 's history of interactions with x² up to round t. The conditional mutual information is related to the filtered mutual information by an expectation: (2) P(Z). We will frequently use this fact to show that
I(X;Y) Z), with respect to
[(Tr(IV (X;
TP( (X;Y Vi),
where the expectation is taken with respect to P(V. 0). Perhaps the most important property of mutual information will be the chain rule,
[(: Zm) (X; + (X; Z2 Zi) + ... [(X; Zm Zi. 2m-
We will need to evaluate I(0. E; Z). where Z discrete random variable, e.g. o, or ( is continuous, and & is discrete. We can evaluate this mutual information by writing
I(0, 2) I(Z00,E)
I(Z;0) E(Z 0)
H(()) H(Z 0) + H(Z 0) H(Z E,
which are all well defined.
C.2 Proofs
For readability, we restate all propositions.
Proposition (restated). Let Rr denote the regret incurred by following Thompson sampling (Alg. 1). For any T e N and T > Fs, then
R
0 < H(X O)T,
where H(X 0) is the conditional entropy of X given ö.
Proof. This analysis extends [35, Prop. 1] to account for the case in which prior data is conditioned upon. We first bound the expected regret by using the law of total expectations and introducing the mutual information between the optimal action and the action observation tuple,
B R
E
Σ
x
Yxo
(15)
E
>
E Y
Yxus V.. 0l
(16)
1-1
Lxx Yxo
V., t
E
Σ
V (X (Xi:)))
Vx(es) v o) (X; (x
(17)
By using the KL divergence definition of mutual information and using the fact that Thompson sampling precisely chooses actions according the their probability of being optimal, it can be shown that,
E D - Yxml= = Σ P(A= x)
X = x]
Σ P(X x) zeix
Σ PE
X x YY,)),
xelix
19

---

where P(X z) = P(X z) by definition of the policy used by Thompson sampling. Let the information ratio is defined as an upperbound on the ratio
B
1xx Yx(o)
Vr, 5l
< TT.
o); Vx())
By writing r > rú, Vt, applying this bound yields
E Yx -x(e) V.
E R
1 = E
V (X: Vxio)
or (X: Vx(0))
I [P(IM))))X::V Vxi1)
TE
T 1 Vx())
T
TE
(x(:))
< TV TH(X 8),
where the second to last inequality follows from the Cauchy-Schwartz inequality and the last inequality follows from the fact that,
T
T Σ P(( (X; Vx(e) Vi)
E
I or
VxxV)())
(18)
t=1
t=1
(X: :xa,)):).V)))))
(19)
H(X ū) H(X Vxir,.... Vxa, D)
(20)
H(X e),
(21)
by the chain rule for the mutual information and given the non-negativity of the entropy.
Proposition 2 (restated), Let Rr denote the regret incurred following the policy defined by Alg. 1. For any T e N, if Eq. (7) holds with I 2 for all I,
E[Rr 0 & T TIp(p) (0. VV
Vx...... Vx
Σ Ela]
Proof. This proof uses different characterization of the per round regret to explicitly consider the influence model parameters (0, {) on information gain. Assume instead that there exists I, such that
E[yx - Yx Vi. t] & <Tiy IP(IV,,) (0. E; Vx(o) + E,,
(22)
20

---

where > 0 is an additional slack term. The proof strategy follows that of [25, Prop. 2] where unconditional regret bounds were shown. Given Eq. (22) the following derivation holds,
R
0
E
Σ Yx
Yx
by definition
E
Σ B V Yx(e) 10 Vil
by the law of iterated expectations
E
T'v (P(-VD.) (0,5: Vx(o)
by definition of I' and Et
T
T
E [PP()V.)) (0,E: Vx(o]] + Σ
by Cauchy-Schwarz's inequality by definition of the expectation of Ip by the chain rule for mutual information.
T
T
Σ m) (0,5: Vxo Vi) E
Σ ce
TV (TP(b) (0.5: ( "x.,...., Vx(r)) + E
Σ c
Proposition (restated). Fix > and choose F, such that IYz - E|Y, V,, b] < 2 V [P. YYYY,,,,,,) for all E Qx simultaneously with probability greater than 5. Then Alg. 1 chooses actions X that satisfy
Is
E - Yxwo Ve, 0] & Ip. Vx((: + QB,
where > such that sup yu -- B.
Proof. This proposition extends [25, Lem. 3] to account for the case in which prior data is conditioned upon. Thompson sampling, by definition, samples action according to its probability of being optimal with the current distribution of parameter values,
E|yg
Yxu
V1, tl
E Epg (Y
V.
Ep Sx,,eYxx) (Yxw) V., E].
where M = M(5 9) defines the SCM that is obtained with the current sample f P(g. 0 ü; 6) from the posterior distribution round f, while M,* refers the true underlying SCM of the environment. Expectations with respect to the distributions Pyr and ps are conditioned on specific model of the environment. Define.
E : (E,(E))) e Qg Qo (Y,,)(( EM~PMM MY & Tey
where Y,,M(E,0) refers the random variable Y in SCM M(S, 0) in which we intervene to set X to and Yr, refers the random variable Y in SCM M in which set X to
21

---

The probability matching property of Thompson sampling implies that P(ç, 0 E E 8z, 8) > 1- 8/2. It follows then, using the same proof strategy as [25, Lemma 3), that
F[Vx - Yxo
Ve,
Ep V.
1 (E, E](x(1,, vx(v,ar)
+ +BB
E Pl: V)
T. Σ 1(x(0) x)) =
+BB
zefxx
T Σ P(X x V. (0. (OEE:) 6B
reRx
Σ P(X(0 V. P. +B
refx
T Σ P(X V.
X(0) x) 5B
Bellx
Toy 1p (0,5: [ + 6B
-Fvy ppVV. (0,5: Y XxO, x()) + 6B,
where the last equalities follow from the conditional independence between (1) and (0, E) condi- tioned on V., Ø.
This proposition might guide us to obtain a per-period regret bound that in particular determines choice for the noise term 6, which results an additive term inProp. 2. A common choice for 6, is 1/T' where 7 is the number of experimentation rounds and therefore the additive term in the regret is simply a constant. This is also the choice made by [25]. In this way, the regret bound is tuned with knowledge of the horizon, which is common in online learning.
C,3 Information ratio computation for specitic example
The theoretical statements presented the main body of this work only implicitly relate bounds on regret with the assumed environment discrepancies assumed in selection diagrams. It is challenging in general to provide more explicit connections. Although similarity in structure between domains explicitly encoded in selection diagrams, the association between discrepancies and posterior distributions on parameters or reward probabilities learned from prior data for an arbitrary input selection diagram complex. For instance, it doesn't 't necessarily hold that few discrepancies lead to narrow reward probability posterior distributions, and conversely it doesn't 't necessarily hold that large discrepancies, e.g. many selection nodes, lead wide reward probability posterior distributions.
In particular, consider an extreme example which source and target domains are equal and described by G = {X - Y, X e---- Y). Even with infinite data and no discrepancy, it can be shown that posterior reward probabilities pa (yy do(x)) are bounded the interval [a(x, 3), P(z, 1- which might be arbitrarily wide depending with certain graphs in which source and target domains differ on an arbitrarily large set of causal mechanisms (that are, however, irrelevant for the computation of posterior reward probabilities) posterior reward probabilities could be made arbitrarily narrow with sufficient data.
the underlying SCM. In contrast, in other examples
The information ratio I' can highlight the trade-off between regret and graph structure. For specific graphs, a bound on the information ratio can be analytically computed and used convey some of the performance gains to be expected, for intuition. Recall that the information ratio is defined as scalar T such that,
E| Yxmo 0] = Te (X: Vx(.).
(23)
The information ratio can bounded: 1/2 & T, & [2x1/2, and describes how much information is revealed about reward distributions when an arm is pulled: on one end r, 1/2 in problems with full information arise when the outcome Y, perfectly revealed by observing Yz,, and on the other end P. 12xx/22 in problems where random variables Y, and Y, are independent for any
22

---

* z'. Bounds on the information ratio have also been shown for linear bandits [35]. With our parameterization of P (yx) the probability of exogeneous variables encoded in 0 is shared while is not, thus some information about reward distributions is expected to be gained on all arms in each MAB round, and 1/2 < D |2x1/2.
In the following we will quantify the amount of sharing between reward distributions and compute corresponding a smaller up- perbound for the information ratio for specific graph in which the computation is tractable following the proof strategy of [35, Proposition 5]. This illustrates more precisely the regret gains that can be expected from having a shared parameterization for reward distributions.
Sx
X
Figure 10: g
We consider the selection diagram with domain-specifie confounding given in Fig. 10 and the computation of (y | do(x)) = Egeng P" x, (*) given knowledge of (2 y, z). This graph is interesting because may directly parameterize the conditional distributions involved in Py do(x)) instead of considering its underlying SCM. Let Y be binary for simplicity (all arguments hold also more generally). For the purposes of this discussion,
will assume that
(a x, z) can be approximated arbitrarily well from sufficient prior data. It holds that
p* do(x))
Σ zERx
(" (2.1),))P*C
(24)
=<(x)
(25)
where (xx) R is a column vector with i-th entry Pa- 2 i) and p R/22l is column vector with i-th entry P(Z = i). The latter has some distribution in the interval [o, 1] and in particular we denote its mean by a == [[[] and its mean conditioned on the optimal action being zj
by My := E[p X = æz5]. Recall that X denotes the optimal action.
Let a; == P(X = xx)) and define M E R xxxxxx by its (i, entry,
Mr. : Vara
F[ X = x= =
(26)
(0xx;) TEEp! X = =x,]= - (xxx))EPpp) Elpl
(27)
X = 2,} Elp) T d(x;)
= Vayay
[Elp
(28)
All expectations are taken with respect to P(- V,, ö). M can therefore be written as product of two matrices of rank |/2x]. With this definition, was shown by [35, Proposition 5] that,
E [ Yxto
V., 5] Trace(M),
(29)
and that,
Pey. (8; Vx() > 2|
(30)
leading to the fact that the information ratio,
E [
Yxio Vi, 0] (X:
Rank(M)
[2zll 2
(31)
2
Now, [9z] << [2x] certain applications which shows that the information ratio may smaller than the worst-case value of [Ωx 1/2 due to sharing of P*(2) across different actions
23

---

D Details on the data generating mechanisms
Bow graph with domain-specific confounding. To generate source data we choose an SCM M compatible with the graph specified as follows: P(uz), P(ux, P(uy, P(uxy) are given by independent Gaussian distributions with mean and variance 1, and each observation (2, 22 y) is generated from (uz, ux, uy, uxY) using the structural assignments: 2 - luz < 1),
1( + uxy - ux > , - 1( 0.5z 2uxy > 0}.
The deployment domain x is given by a different SCM M that varies in the causal mechanism relat- ing Z. It is given by the following SCM: P(uz), P(ux, P(ay, P(uxy) are given by independent Gaussian distributions with mean 0 and variance 1, and each observation (z, æ, y) is generated from 1(uz < 0}. 1 uxy ux >
(uz), ux, uy, ) using the structural assignments:
03,8 / - 1[ 0.5z + 2uxy= > 0j.
Hypertension example. To generate data from the patient population лO we choose an SCM M compatible with the graph specified as follows: P(uz), P(uw. P(uxy) are given by independent Gaussian distributions with mean 0 and variance and each observation (2, x. w. y) is generated from (uz), ux, My, uxy) using the structural assignments:
< L(uz > 0}, O055 + (uxx > 0} 21 (uxy > 0] fux > 0) > 0} 21 fux > 1] + 1}, w (0.3r uw 0.8 > 07,9 - [ 0.5z + uxy > 0}. int(-) stands for the integer part of the content of the brackets.
The domain x in which the MAB is deployed is given by a different SCM M that varies in the causal mechanism relating Z and W with respect M and varies in W with respect to M is defined by: P(wz), P(ux, with mean 0 and variance and each observation (2, x. w. y) is generated from (uz), ux, uy, uxy)
are given by independent Gaussian distributions
using the structural assignments: 2 + 1uz > 0, I - int 0.52 + l(uxy > 0} + 21xxx > 1fux 0} fux > 1) + 1},
1(0.2r up 1.8 0}. y 1(w 0.5z + uxy > 0}.
Digital advertising example. This example considers data from two domains. Data from the source domain π" given by SCM M compatible with the graph that is specified as fol- lows: P(uz), P(ux, P(uw. P(uxw. P(uwy. P(uA) are given by independent Gaussian distri- butions with mean and variance 1, and each observation (z, r, w, 0,3) is generated from a sample uz, ux, uw; MXW, MWY, UA using the structural assignments: w <- 1/uxw + uwY 0), 1 [uA 0},x x int(0.5= 0.5a 1 > 03 > 0.5) 133-11 [ux > 0F 1+ 10.2r - 0.5a + "wY 1 > 0}.
1uuz+ > 03,
The domain ** in which the MAB is deployed is given by different SCM M that varies in the causal mechanism relating to A with respect to M It is defined by: P(uz), P(ux. P(uw. P(uxw, P(ux,, ((uwy,P(ua) are given by independent Gaussian distributions with mean 0 and variance 1, and each observation (2, w, y) is generated from a sample ux,ux, uw, uxw, uWY, UA using the structural assignments: w < 1(uxw + uwy 0},
1luz + w > 0).a - 1f2A > 0.5),22 x < int(0.5z 0.5a + L(uxW > 0} + 21(uxw > 0.5) - fux > 0} + ++11,00 y - 1 (0.2x 0.5a + uwy - 0).
24

---

E
Gibbs sampling
This section gives the derivation of all conditionals using our parameterization of causal effects for the bow graph with confounding example.
The query of interest is given by (y 1) which is first approximated using source data e and then updated using interventional data e2 ,...,.... collected by the MAB in the deployment environment n*
Its parameterization, following Corol. 1, is given by
p* [ye 1)
Σ M2z
= 1) (us)
=)0 Pu.,
(32)
where Ey (xy)) and Ou., parameters are shared across source and deployment environments, while 1622 = 2) and 0u. is specific to the deployment environment. We start by approximating the posterior of all relevant parameters, that <y ((e,2.uay) and fuzyy given 8. before interacting with the deployment environment π* Note that prior data i is not relevant for estimating 1 1(522) (w.)) 2)
and 0,, and thus we maintain uniform prior distributions over these parameters at this stage. In the following, we give the derivation of the complete conditionals over čy (2v) and Ours.
1. Sampling from P(ūay; u. e, &, 0). Let ūay = {usy
(x) n = N} and u = (
...... N denote N independent samples of Uay and Ug respectively, one corresponding each observation (m)) (a:(m) (,()) (()),, where is the number of prior data samples. The complete conditional can be derived following the functional dependencies in the underlying SCM given by the causal graph,
(n) u(n) (x) () P(uff) u!!) | B, E, = P(uly) ((n)) (()), .E,)) oc P(ufy)
P(y(")) 1m))) 2(1), (()) P(x(m) (())) u(() P((2(m) u(!") P((()))
115 1 200) any) y 11 (2 wln (n p1fc2 (2 s0 A,5
where we have replaced the probabilities with the corresponding parameters that are used to define them.
2. Sampling from P(g Ü, ū, 0). Similarly, for fixed 2, May. parameter Ey (. is mutually independent of any other parameter in & given 0, ü, and can be sampled separately. Recall that by definition of the underlying SCM cy (( represent a deterministic mapping between inputs I, 2, May and output y E fty The value <\ ((n,).)))) E Gy is therefore implicitly (n)
determined by the current values 0, ū: if there exists a tuple (I(()) x, (n) 2, May
May: (n)) = y) for some n = = N, then by definition 56 := with probability 1. If no such tuple exist, then the distribution of c ((r,2.0..)) remains uniform over its domain 2y as none of the data points carries information to the mapping (I., 2, Msy) y.
3. Sampling from P(On.y ū, u, 0). The conditional distribution over Ow., given ö, is given by Dirichlet distribution following the conjugacy of it with regard to categorical distributions of Uny and can be updated by adding the counts of each outcome ūzy of URY in the current sample to the corresponding prior concentration parameters of the Dirichlet prior distribution.
This process eventually forms a chain of samples from the correct posterior distribution of each parameter. At this stage, the MAB is deployed in x* and all parameters may be updated both with prior data as well as with additional samples Ug collected online in every round of experimentation. Offline and online data points are different in kind, and contribute to updating parameters differently. For shared parameters, both types of data may be used while for parameters specific to x only newly collected interventional data samples will be relevant in posterior computations.
Sy ((2,2,Mey) updated using the posterior P(ck (()
Ü, Dg()).... (g(t-1), ū, Ug()),... (zz(e-1)),
while (us) is updated using the posterior P(5
(uz) Ugtt)..... Vytt 13, ú, Ugll) ..., Ugit 11)
25

---

P(5Z (U1t))..... ............................ Dgtt-1,, 1), ug("),.... ()) 1)) using the same intuition described above. Simi- larly, Ouz, is updated using the posterior P(O u, Ug()),... Uz(+-1) while ou, updated using the posterior P(Ou, u. 2g00:..: pe 1) P(Ou, Ug(), 220 12).
26


Reviews:
[{"review_id": "lyqhqAm2Fm", "reviewer": "Reviewer_DogX", "summary": "This paper considers the online bandit problem with \nadditional batch/observational data, where \nthe additional data could be from different (but related) \nenvironments. The authors \npresent a representation of the interventional distribution, based on which one can sample from the posterior distribution \nof the SCMs and select an action based on the realized model. \nIt is shown that the resulting regret is sublinear, and \nthe improvement upon an algorithm without using prior data is explicitly \ndependent on the \"relevance\" of the other environments.", "questions": "1. I was wondering how the computation time scales with the cardinality of different variables. Appendix B.2 has briefly mentioned this --- I am curious if it would be possible to have an analytical result.\n2. It might also be helpful to compare the computational time of different methods \nin the simulations (in addition to the ones presented in Appendix B.2).\n\nMinor: \nIs there a typo in Algorithm 1? \"$\\mathcal{G} ** a$\"", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper considers an interesting problem: how to leverage observational \ndata to improve the online bandit algorithm. \n2. The proposed method makes use of prior data in a clean way, and the \ntheoretical result shows an explicit dependence on the relevance of \nthe environments from which the prior datasets are generated, while \nthe algorithm itself is agnostic to this knowledge. \n", "weaknesses": "1. This paper is rather notation-heavy, and it is a bit hard \nfor readers not familiar with the language used therein.\n2. The proposed method introduces an additional computational burden.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and feedback. We hope to have clarified your concerns in the following response, please let us know if you would like us to expand our discussion on any of it. Thanks for pointing out a typo in Algorithm 1!\n\n1. ”***I was wondering how the computation time scales with the cardinality of different variables. Appendix B.2 has briefly mentioned this --- I am curious if it would be possible to have an analytical result.***”\n\nIn a given iteration of the Gibbs sampler, posterior updates are done for each parameter separately so that computational time is proportional to the parameter count, approximately, which in turn is determined by the cardinality of variables as well as the structure of the graph. For a fixed graph, assuming that each update requires a small constant amount of time to compute, we could therefore establish analytically how computational time scales with the cardinality of variables. For arbitrary graphs an analytical result is in general more involved as the parameter count increases differently depending on the local structure of each variable.\n\nAs an example for illustration, consider the graph $\\mathcal G = (X\\rightarrow Z \\rightarrow Y, X\\leftrightarrow Y)$ where $X$ is an action variable, $Z$ is a contextual variable, and $Y$ is a reward variable. Following the parameterization in Cor. 1, the cardinality of parameters is defined as follows: $|\\boldsymbol{\\theta}_u|= |\\Omega_X|\\cdot|\\Omega_Z|\\cdot|\\Omega_Y|$, $|\\boldsymbol{\\xi}_X| = |\\Omega_X|\\cdot|\\Omega_Z|\\cdot|\\Omega_Y|$, $|\\boldsymbol{\\xi}_Z| = |\\Omega_X|$, $|\\boldsymbol{\\xi}_Y| = |\\Omega_X|\\cdot|\\Omega_Z|\\cdot|\\Omega_Y|\\cdot|\\Omega_Z|$. We would expect run time to increase linearly with the cardinality of variables $X,Y$ and to increase “slower than quadratically” with the cardinality of $Z$. \n\nWe will update the manuscript with a discussion.\n  \n2. \"***It might also be helpful to compare the computational time of different methods in the simulations (in addition to the ones presented in Appendix B.2).***\"\n\nWe appreciate the suggestion. Over a single run of $10,000$ experimentation rounds, empirically, the run times for experiment 2 are: TS$=1.2$ seconds, UCB$= 1.7$ seconds, Random$= 0.1$ seconds, tTS$= 5.4$ seconds; and for experiment 3:  TS$=1.3$ seconds, UCB$= 1.8$ seconds, Random$= 0.1$ seconds, tTS$= 5.8$ seconds. Run times of tTS include the prior step of 1,000 rounds of sampling from the posterior distribution of parameters given 1,000 samples of prior data. We will add these analyses in the updated document.\n"}, {"review_id": "wKeODGu235", "reviewer": "Reviewer_KpW6", "summary": "This paper considers the problem of leveraging data from many different environments to warm start a bandit algorithm. The paper assumes that the environments share the same variables, and the relationships between variables in related environments can be captured by structural causal models (SCMs). Taking a Bayesian perspective, the paper defines a probability distribution over unknown quantities in the target SCM and constrains the probability distribution using the information obtained from the related environments. This probability distribution is then used to warm-start a Thompson sampling algorithm. ", "questions": "1. In the motivating example in lines 42-60, it would be helpful if the authors could add a comment that this problem arises due to the fact that the clinical trial population and historical data population differ across observables (or unobservables).\n\n2. [Nit] $S_{Z}$ is not defined in the text until Section 2 but appears in Figure 1, which is referenced in Section 1.\n\n3. Would it be possible for the authors to contextualize their perspective on distribution shift within the broader literature on generalizability/transportability (e.g., Stuart, et. al. 2011, Tipton, et. al, 2013, Tipton et. al., 2014)? For example, can the different environments vary across unobservable attributes (confounders), or can they only differ in observable attributes?\n\n\nReferences:\n\nStuart, Elizabeth A., et al. \"The use of propensity scores to assess the generalizability of results from randomized trials.\" Journal of the Royal Statistical Society: Series A (Statistics in Society) 174.2 (2011): 369-386.\n\nTipton, Elizabeth. \"Improving generalizations from experiments using propensity score subclassification: Assumptions, properties, and contexts.\" Journal of Educational and Behavioral Statistics 38.3 (2013): 239-266.\n\nTipton, Elizabeth. \"How generalizable is your experiment? An index for comparing experimental samples and populations.\" Journal of Educational and Behavioral Statistics 39.6 (2014): 478-501.\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper has interesting theoretical contributions. The authors provide an algorithm that leverages data from related environments and are able to prove a sub-linear regret bound and the regret bound depends on a term that captures how informative the related environments are for the target environment.\n\n2. Compelling experimental results.\n\n3. The paper is overall clear and well-written.\n", "weaknesses": "1. This work relies on having quite detailed information from the related environments– the SCM and the selection diagrams for each environment. Having this type of information is somewhat unrealistic. Nevertheless, the contribution of the paper is conceptual/theoretical and may pave the way for future work that requires less detailed information.\n\n2. Furthermore, it is also somewhat unrealistic that any of the relationships between the variables in the related environment are exactly the same as the relationship as relationships in the target environment. Would it be possible to place looser restrictions from the prior data than the equality constraints in Eq 2? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and constructive comments. In the following, we address each point separately and hope to clarify all concerns that were raised. Please let us know if any issues remain.\n\n1. ”***It is also somewhat unrealistic that any of the relationships between the variables in the related environment are exactly the same as the relationships in the target environment. Would it be possible to place looser restrictions from the prior data than the equality constraints in Eq 2?***”\n\nRelaxations to the formalism in Eq. (2) are possible. One relevant example are settings in which instead it is plausible to assume that some of the causal mechanisms or probabilities are known to lie in some non-trivial interval. As each probability relates directly to some combination of model parameters, this constraint could be incorporated in posterior approximations. We discuss such a scenario in more details on lines 558-570 of the Appendix. There, specifically, instead of an equality across causal mechanisms that implies that $P^*(z) = P^a(z)$ we pose a looser restriction, e.g., $P^*(z) \\in I = [P^a(z) - 0.1, P^a(z) + 0.1]$. That is, $P^*(z) = \\sum_{u_z}\\mathbf 1(\\xi_Z^{(u_z)}=z)\\theta_{u_z} \\in I$, where $\\mathbf 1(\\cdot)$ denotes the indicator function, which defines a constraint on possible parameter values and is implemented with a rejection step while sampling from the posterior. \n\n2. ”***In the motivating example in lines 42-60, it would be helpful if the authors could add a comment that this problem arises due to the fact that the clinical trial population and historical data population differ across observables (or unobservables).***”\n\nThis observation is stated in the sentence starting line 50 and will be emphasized.\n\n3. ”***Would it be possible for the authors to contextualize their perspective on distribution shift within the broader literature on generalizability/transportability (e.g., Stuart, et. al. 2011, Tipton, et. al, 2013, Tipton et. al., 2014)? For example, can the different environments vary across unobservable attributes (confounders), or can they only differ in observable attributes?***”\n\nThank you for sharing these references, which we read with interest. Based on our reading, under two assumptions on the dependence of potential outcomes on treatment and domain indicators, propensity scores can be used to correct for distribution shift between target and source populations. Within the perspective of transportability (that uses selection diagrams to encode assumptions on differences and similarities between populations) this could be seen as a special case for which selection diagrams imply the independence assumptions. In general, selection diagrams may not imply this set of independencies and different weights may be applicable to correctly adjust for distribution shift. Further, we consider a generalization of this setting, so called partial transportability. In this generalization, the correct adjustment for distribution shift might not be uniquely identifiable and the goal, instead, is to infer a non-trivial interval for outcome distributions under intervention that could nevertheless provide some information to improve inference (Sec. 2.1).\n\nSelection diagrams may be used to encode differences in observable and unobservable attributes. \n"}, {"review_id": "z5BzS014Yn", "reviewer": "Reviewer_QDCf", "summary": "A framework is presented so that bandits can use data from different environments, by exploiting the causal relationship between those environments.", "questions": "cf above", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The contribution and problem statement are clear.", "weaknesses": "Experiments seem to be conducted on toy data only. How useful is the method in practice, on real data?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We address your question below. We are happy to engage further to address any remaining concerns on the practical usefulness of our method.\n\n1. ”***Experiments seem to be conducted on toy data only. How useful is the method in practice, on real data?***”\n\nTo our knowledge, it is typical in the literature to work with a synthetic set up as bandits require active experimentation. We believe that the environments discussed in the experiments and their motivation, e.g. inspired by the literature on clinical trials and advertising, are realistic, and expect therefore that a similar analysis could be conducted with real data. In particular, if the selection diagram is well-specified (under mild mispecification, Appendix B.1) we expect the use of offline data to enable the proposed approach to outperform bandit algorithms such as Thompson sampling (Sec. 3) in every application.\n"}, {"review_id": "U6eC4f16AE", "reviewer": "Reviewer_eikn", "summary": "The paper analyses how bandits can exploit causal similarities (need not be fully known functionally) across different environments to improve their regret bounds. In particular, previously collected data from related environments can improve learning.", "questions": "None", "limitations": "None identified.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strengths\n1. Use of domain discrepancy and selection diagrams to formally treat the different environments.\n2. The proposed tTS conforms nicely with how a bandit can use priors and recently tried arms to inform its posteriors.", "weaknesses": "None", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive assessment of our work. We would be happy to provide any clarification that could help further with the evaluation."}]

Author rebuttal:

Meta-review: The reviewers with the highest level of expertise were supportive of this paper's contributions. The following suggestions were made to improve contextualization and discussion of the results in the camera-ready version, which I strongly recommend the authors do:

- Emphasize that your approach can handle/can be adapted to handle some degree of misspecification of the transportability paradigm.
- There are particular applications where relationships between target/source distributions are encoded using SCMs and selection diagrams. The authors mention biological/medical applications and advertising in their rebuttal. It would be great to see some references for the same.
Decision: Accept (poster)