Adaptively Exploiting d-Separators with Causal Bandits
Authors: Blair Bilodeau
Linbo Wang
Daniel M. Roy
Venue: NeurIPS 2022 Accept (2022)
Keywords: bandit
causal bandit
adaptive
d-separation
online

Abstract: Multi-armed bandit problems provide a framework to identify the optimal intervention over a sequence of repeated experiments. Without additional assumptions, minimax optimal performance (measured by cumulative regret) is well-understood. With access to additional observed variables that d-separate the intervention from the outcome (i.e., they are a d-separator), recent "causal bandit" algorithms provably incur less regret. However, in practice it is desirable to be agnostic to whether observed variables are a d-separator. Ideally, an algorithm should be adaptive; that is, perform nearly as well as an algorithm with oracle knowledge of the presence or absence of a d-separator. In this work, we formalize and study this notion of adaptivity, and provide a novel algorithm that simultaneously achieves (a) optimal regret when a d-separator is observed, improving on classical minimax algorithms, and (b) significantly smaller regret than recent causal bandit algorithms when the observed variables are not a d-separator. Crucially, our algorithm does not require any oracle knowledge of whether a d-separator is observed. We also generalize this adaptivity to other conditions, such as the front-door criterion.

Adaptively Exploiting d-Separators with Causal Bandits
Blair Bilodeau" University of Toronto
Linbo Wang University of Toronto
Daniel M. Roy University of Toronto
Abstract
Multi-armed bandit problems provide a framework to identify the optimal inter- vention over sequence of repeated experiments. Without additional assumptions, minimax optimal performance (measured by cumulative regret) is well-understood. With access additional observed variables that d-separate the intervention from the outcome (i.e., they are a d-separator), recent "causal bandit" algorithms prov- ably incur less regret. However, practice it is desirable be agnostic whether observed variables are d-separator. Ideally, an algorithm should be adaptive; that is, perform nearly as well as an algorithm with oracle knowledge the presence or absence of d-separator. In this work, we formalize and study this notion of adaptivity, and provide a novel algorithm that simultaneously achieves (a) optimal regret when d-separator is observed, improving classical minimax algorithms, and (b) significantly smaller regret than recent causal bandit algorithms when the observed variables not d-separator. Crucially, our algorithm does not require any oracle knowledge of whether a d-separator is observed. We also generalize this adaptivity to other conditions, such the front-door criterion.
Introduction
Given set of interventions (actions) for specific experiment, are interested in learning the best one with respect to some outcome of interest. Without knowledge of specific causal structure relating the observed variables, this task impossible from solely observational data (c.f. Theorem 4.3.2 of [29]). Instead, we seek the most efficient way to sequentially choose interventions for i.i.d. repetitions of the experiment, where the main challenge that we cannot observe the counterfactual effect of interventions we did not choose. Without any structural assumptions beyond i.i.d., one can always learn the best intervention with high confidence by performing each intervention sufficient number of times [10]. In the presence of additional structure such causal graph on observables this strategy may result in performing suboptimal interventions unnecessarily often. However, the presence of such structure is often unverifiable, and incorrectly supposing that it exists may catastrophically mislead the experimenter. Thus, a fundamental question arises: Can we avoid strong, unverifiable assumptions while simultaneously performing fewer harmful interventions when advantagcous structure exists?
A natural framework in which to study this question is that of (multi-armed) bandit problems: Over sequence of interactions with the environment, the experimenter chooses an action using their experience of the previous interactions, and then observes the reward of the chosen action. The goal achieve comparable performance with what would have been achieved the experimenter had chosen the (unknown) optimal action in each interaction. Formally, performance is measured by regret, which the difference the cumulative reward incurred by experimenter compared to the optimal action. In this partial-information setting, regret induces the classical trade-off between exploration (choosing potentially suboptimal actions learn if they' 're optimal) and exploitation
"Correspondence blair.bilodeau @mailuttroonoo.c
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(choosing the action that empirically appears the best). In contrast, other measures of performance (e.g,, only identifying the average treatment effect or the best action at the end of all interactions) do not penalize the experimenter for performing suboptimal actions during exploration, and consequently are insufficient to study our question of interest.
For an action set A and a time horizon T, the minimax optimal regret for bandits without any assumptions on the data (worst-case) is Ō (A]T) [6]. and is achieved by many algorithms [19]. Recently, Lu et al. [24] showed that, under additional causal structure, a new algorithm (C-UCB) can achieve improved regret. In particular, if the experimenter has access to variable Z- --taking values in finite set tha d d-separates [29] the intervention and the reward, as well as the interventional distribution of Z for each a E A, C-UCB achieves T(y regret. However, as we show, the performance of C-UCB when the d-separation assumption fails is orders of magnitude worse than that of UCB. Is strict adaptation possible? That is, there an algorithm that recovers the guarantee of C-UCB when Z is d-separator and the guarantee of UCB in all other environments, without a d-separator?
advance knowledge of whether
As of yet, there is no general theory of adaptivity in the bandit setting. The closest we have to a general method is the Corral algorithm and its offisring [2. 4]. Corral uses online mirror descent to combine "base" bandit algorithms. but requires that each of the base algorithms is "stable" when operating on setoortanc-weightee reveal this not to be the case for C-UCB. This presents a barrier to adapting to causal structure via Corral-like techniques, and raises the question of whether there is a new way to achieve adaptivity.
observations. Unfortunately, while UCB is stable, simulations
Contributions. We introduce the conditionally benign property for bandit environments: informally, there exists a random variable Z such that the conditional distribution of the reward given Z is the same for each action a E A. We show that the conditionally benign property is (a) strietly weaker than the assumption of Lu et al. [24] (in their proofs, they actually assume that all causal parents of the reward are observed); (b) equivalent to Z being a d-separator when A is all interventions; and (c) implied by the front-door criterion [29] when A is all interventions except the null intervention (i.e., a pure observation). We then prove that any algorithm that achieves optimal worst-case regret must incur suboptimal regret for some conditionally benign environment, and hence strict adaptation to the conditionally benign property is impossible. Despite this, we introduce the hypothesis tested adaptive causal upper confidence bound algorithm (HAC-UCB), which provably (a) achieves non- vacuous (sublinear in T) regret at all times without any assumptions, (b) recovers the improved performance of C-UCB for conditionally benign environments, and (c) performs as well as UCB in certain environments where C-UCB and related algorithms (such as those studied in [25, 27]) incur linear regret. Empirically, we observe these performance improvements on simulated data.
Impact. Recently, multiple works have developed causal bandit algorithms that achieve improved performance in the presence of advantageous causal relationships (initiated by Bareinboim al. [7] and Lattimore et al. [17]; see Section 7 for more literature). Further, the last decade has seen a flurry of work in bandits on designing al algorithms that recover worst-case regret bounds while simultaneously performing significantly better in advantageous settings, without requiring advance knowledge of which case holds [e.g., 9, 31, 34, 26, 1]. However, to the best of our knowledge, no existing work studies algorithms that achieve adaptive regret guarantees with respect to causal structure. The present work provides framework that expands the study of adaptive decision making to the rich domain of causal inference.
2 Preliminaries
2.1 Problem Setting
We consider general extension of the usual bandit setting where, in addition to a reward correspond- ing to the action played, the experimenter observes some additional variables after choosing their action; we call this the post-action context. This is distinct from the contextual bandit problem, where the experimenter has access to side-infond and-informatiin before choosing their action.
Let y = [0, 1] be the reward space?, Z be a finite set of values for the post-action context to take, and (Z x Y)) denote the set of joint probability distributions. For any p (Z x )) and
"Our results hold for y IR using Gau--Gassiin rewards with bounded mean at the expense of constants.
2

---

(2, - random variable (Z, Y). let P(Z) and p(Y Z) denote the marginal and conditional distributions respectively. Let Ep and P denote expectation and probability operators under p.
The stochastic bandit problem with post-action contexts proceeds as follows: For each round E [T). the experimenter selects A, E A while simultaneously (Z) Yi(a)) sampled from the environment, which is any family of distributions y = {va : a E A] E (Z)) indexed by the action set. The experimenter only observes (Z,(A,), (A:)) and receives reward Y+(A)) From a causal perspective, (Z((a), YE(a))AEA corresponds to the potential outcome vector, and under causal consistency, (Z)( (A)) corresponds to the observed data (Z,, Y2) under the chosen intervention A,
A) are independently
The observed history up to round is the random variable H, (A2, (A,)). (A,)) se())) A policy is a sequence of measurable maps from the observed history to the action set, denoted
T π = (m))ETT E (1A, = II (AX
The experimenter chooses a policy in advance to select their action on each round according to A, = ()) Clearly, environment and policy together define a joint probability distribution on (A,, (a), Y (e)))) player). Let Ey,, denote expectation under this joint distribution. The performance of a policy under an environment is quantified by the regret
(which includes the "counterfactuals" not seen by the
T
R (T) = TT mmx Ev, [ E
Σ EvA, M
aEA
2.2 Specific Algorithms
Classical bandit algorithms take |A| and T as inputs. The dependence on T can often be dropped using the doubling trick or more sophisticated techniques such as decreasing learning rates, but we do not focus on these refinements in this work, instead allowing T as input. In order to account for the additional information provided by the post-action context, we also consider algorithms that take |z| as input. By restricting dependence to only the cardinality of A and Z, we explicitly suppose that there is no additional structure to exploit on these spaces; much work in the bandit literature has focused on such structure through linear or Lipschitz rewards, but defer these extensions to future work in favour of focusing on adaptivity. For notational simplicity, we denote algorithmic dependence A or Z even though the dependence is actually through their cardinality (i.e., the labellings of items in the sets are arbitrary).
In the causal bandit literature [17, 24, 27], it is common to suppose that the algorithm also receives distributional information relating actions to intermediate variables. In particular, if the (unknown) environment is prior work supposes that the algorithm has access to the (interventional) marginal distributions v(2) = (va(Z)= a E A). In this work, we suppose instead that the algorithm has access to collection of approximate marginal distributions i(Z) {v,(Z), a E A); for example, these could be an estimate v(Z) that was learned offline. Ideally, D(Z) will be close to v(Z), ) but novel method is entirely adaptive to this assumption: regardless of how well (Z) approximates v (Z), HAC-UCB incurs sublinear regret.
We now introduce additional notation to define the algorithms of interest in this work. Suppose that A, 2, DZZ), and T are all fixed in advance, as well as a confidence parameter 5 8r (0, 1). For each t E [T], E Z, and E A. define the number of the first t rounds on which was observed by T
2} (where V b max(a, b)), and similarly the number of rounds on which a was chosen by (a = 1v === 1v I(A, = a}. Further, define the empirical mean estimate for the reward under the distribution induced by choosing the action a as (a) = [T> (a)) E (T.A))((A. a} and the empirical conditional mean estimate for the YI
V. (A.)
reward given that was observed as (2) = (x)
2). Define UCB? (z) = A (x) + (log(2/)) and
UCBA (a) = (a) + /log(2/0)/(2T
(C) = E.ez UCB (z)P ( =
Using these objects, we define three algorithms, each of which produces actions that are measuuraabe.. The upper confidence bound algorithm (UCB, [6]) is defined by AUCE
3

---

argmax,E UCB, (a), and the causal upper confidence bound algorithm (C-UCB, [24]) is defined by A = arg ea UCB,(a), where ties are broken by using some predetermined ordering on combination of these two methods, which we call the hypothesis testeed
A. Finally, we define adaptive causal upper confidence bound algorithm (HAC-UCB) and describe precisely in Algorithm 1; we denote its actions by A
Algorithm 1: HAC-UCB(A, 2, ((z))
do Play each A for [4vT |A||] rounds, and let (Z) be the MLE of vo (Z) if suPac Σ=EZ Pv.! 1 =] Pe., lZ z] 27 1/4 ///////1 log T
replace (Z) - iZZ)
do Play each a E A for [VT / [A|] rounds
set flag True
while t _ T if flag
/* Check if either of the two conditions fail
set 1 (0) = UCB
UCB,-1(a) v log
T1/1
for a E A do
2 V VIAll log
if not -2 Σ ZE2
log
Po. 1Z = 2| < D (a) 2
log
T2 [2)(2
TA
(a)
11/4
set flag = False; break
/* If conditions pass, play C-UCB
if flag
set A AC:
else
set AlAC A
else
/* If conditions ever fail, play UCB forever
set AlAC
A
Heuristically, HAC-UCB has an initial exploration period ensure that i2) is sufficiently accurate- if not, it is replaced with the maximum likelihood estimate (MLE) of the marginals- and then optimistically plays C-UCB until there is sufficient evidence that the environment is not conditionally benign. The switch from C-UCB to UCB is decided by hypothesis test performed on each round, which uses the confidence intervals that will hold if the environment conditionally benign. When the arm mean estimates of UCB and C-UCB disagree, this provides evidence that the environment not conditionally benign, and the evidence is considered sufficient to switch when the size of the disagreement is large compared to the size of the confidence intervals themselves. As we illustrate in the proof of the regret bounds, with high probability this test will not induce a switch for a conditionally benign environment, and will sufficiently limit the regret incurred by C-UCB if the environment not conditionally benign.
3 Conditionally Benign Property
We now formalize the main property that HAC-UCB will adaptively exploit.
Definition 3.1. An environment E (2 A) is conditionally benign if and only if there exists p E (2 (Z )) such that for each A, (Z) < p(Z) and v, (Y 7) = p(Y Z) p-a.s.
This definition does not require any causal terminology to define or use for regret bounds, but we now instantiate it for the causal setting. For a collection of finite random variables V and a (potentially) continuous random variable Y. let Py be the set of all joint probability distributions with strictly positive marginal probabilities on V. Fix a DAG G on (V,Y) Y) such that Y is leaf and two disjoint sets Z C V and A C V such that Pag CVV Z. Let A be the set of all possible do interventions on A, and for each E let Pa denote the interventional distribution (Definition A.5). This structure suggests graphical analogue of the conditionally benign property.

---

Definition 3.2. For any DAG G and A' S A. (G. is conditionally benign if and only for all p E By that are Markov relative to g. {pa (Z. Y) A') is conditionally benign.
We now connect the conditionally benign property to d-separation (Definition A.6) and the front-door criterion (Definition A.8). All proofs are deferred Appendix A, along with standard notation and definitions from the causal literature.
Theorem 3.3. Z d-separates Y from A on 9 if and only if (G is conditionally benign.
This equivalence particular, to define conditionally benign, we need not require all possible interventions be allowed. Define Ao to be A with the null (observational) intervention removed, and let 9Λ denote 9 with all edges directed into A removed.
strict specialization of the conditionally benign property the causal setting. In
Theorem 3.4. Z d-xeparates from A on 9 if and only if (g) is conditionally benign.
The benefits of discarding the null intervention are demonstrated by the following fact.
Lemma 3.5. Z d-separates from A on A if satisfies the front-door criterion for (A, Y) on G.
We visualize the preceding results in Figure 1. In graph (a), d-separates the intervention from the reward, and hence any Markov relative distribution (Definition A.3) will induce a conditionally benign environment. Graph (b) corresponds a setting where one cannot hope always improve per- formance due to the direct effect of the intervention on the reward, and consequently the environment need not be conditionally benign. that Z does not d-separate the intervention from the reward. However, if the null intervention is not considered, the arrow from to A is never applicable, and hence any Markov relative distribution on the modified DAG will induce conditionally benign environment. Specifically, graph (c) satisfies the front-door criterion, revealing that the conditionally benign property captures that this setting is still benign for decision-making, even though the conditions assumed by Lu et al. [24] do not hold. Finally, in graph (d), the unobserved confounder U once again violates d-separation, but also the front-door criterion is not satisfied because of the back-door path from Z to Y. Hence, even discarding the null intervention does not guarantee that the environment will conditionally benign.
graph (c), the presence of the unobserved confounder U/ means
a
A
Z
Y
Z
Y
(c)
(d)
A
Z
Figure DAGs to illustrate the conditionally benign property. A is the intervention. Z is the post-action context, Y is the reward, and U is unobserved variable. (G,A) is conditionally benign for (a) but only (G, Au) is conditionally benign for (c). For (b) and (d) the environment need not be conditionally benign.
4 Analysis of Bandit Algorithms
We now study the impact of the conditionally benign property on regret. All proofs are deferred to Appendix B. First, recall the standard regret bound for UCB, with constants tuned to rewards in [o, 1).
Theorem 4.1 (Theorem 7.2 of [19]). For all A, Z, T, and E (1 2) if 2/T2
Rvjucu (T) S 2 |||
Second, we generalize the main result of et al. [24] by relaxing two assumptions: we only require that the environment is conditionally benign, and we allow for approximate marginal distributions using the following definition. Later, this will enable us to trade-off approximation error of ((Z) with online estimation of v(2) in order to ensure that HAC-UCB always incurs sublinear regret.
5

---

Definition 4.2. For any 2 0, (Z) and (Z) are E-close if
Pr. Z 2] Pv, 12 2| Ss.
sup a 2EZ
Theorem 4.3 (Refieed Theorem of [24]). For all >> 0, A, Z, T, and conditionally benign E (Z V)A (Z) and v(Z) are E-close and 2/TT then
(T) S 2 2 +6V Z / log (log v 2T 2c Vlog TYT.
Remark 4.4. Lu et al. [24] assume that = O. Our result implies that an approximation error of E
vl / /T is sufficient to achieve the optimal rate.
Next, we motivate our introduction of a new algorithm by showing that C-UCB can catastrophically fail when the environment not conditionally benign, incurring regret that is linear in T (which is as bad as possible for bounded rewards).
Theorem 4.5. For every A and with |A| 2 2, there exists v E P x V) such that even if iZZ) v(Z). for all possible settings of the confidence parameters. 8r,
RT,c(T) 2 1/120.
1im
Remark 4.6. This lower bound is specifically for C-UCB. However, any algorithm that relies on eliminating actions from consideration via assumption rather than data is susceptible such issue. In particular, this result is easily modified to apply for C-TS [24] and C-UCB-2 [27]. Other causal algorithms (e.g. Parallel Bandit [17]) also intuitively suffer from the issue that our construction exploits, although different argument must be made since these rely on different causal structure. <
We now state regret upper bound for
algorithm, HAC-UCB. In Theorem 6.2, we will show is impossible to always achieve the optimal regret without knowledge of whether a d-separator is observed, but the following theorem shows some adaptivity is always possible. Crucially, HAC-UCB achieves sublinear regret without any assumptions on v or (Z). For a more detailed breakdown of the constants, see Eq. (B.9).
Theorem 4.7 (Main Result). For all A, Z, T 2 25 3 VE P V)A and (Z) E (Z))
Ru,nAc (T) S 4 |A| 11 (log T) A Z 15 (IA) + 2 T 5(lgg T)VT.
For all T 1/4 | Z log if is conditionally benign and ((Z) and vl v(Z) are e-close then
Ry, (T) < |A| 2 |Z| + 6. / T log + 4(lgg T 2=(1 + Vlog TYT.
It is open problem whether the dependence on 3 is tight. In Theorem 6.2, we will show that it is impossible to obtain worst-case regret of size V|A/T while still achieving improved regret on conditionally benign environments. However, it may be possible to improve the dependence on T, and the role of logarithmic factors in how much improvement is possible remains to be understood. Towards improving this result, we now show that there exists an environment that forces C-UCB to incur linear regret yet HAC-UCB will switch to following UCB (and hence incurs ViA log T regret at worst). That is, HAC-UCB recovers the improved performance of C-UCB when the conditionally benign property holds, is never worse than C-UCB, and optimally outperforms C-UCB in some settings.
Theorem 4.8. There exists a constant C such that for any A and Z with [A] 2 2, there exists E (Z V)A that for any 8y used for C-UCB with (Z) v(Z).
RT)
lim
2 1/C,
T
T
and if ((Z) v(Z) is used for HAC-UCB then
Ry (T)
lim
Tog TIATT--TT (log TVTT S.
|
Remark 4.9. Theorem 4.8 could be stated with (Z)) only e-close to u v()), but for simplicity we have supposed E = 0 to highlight the role of the conditionally benign property.

---

5 Simulations
We now study the empirical performance of these algorithms in two key settings, corresponding to conditionally benign environment and the lower bound environment from Theorem 4.5. We compare our algorithm HAC-UCB with UCB [5], C-UCB [24], C-UCB-2 [27], and Corral (for which we use the learning rate and algorithm prescribed by [2] with the epoch-based, scale-sensitive UCB prescribed by [4]); for all algorithms, we use the parameters that are optimal as prescribed by existing theory. To focus solely on the impact of the conditionally benign property. we set ( = v(Z), The results of this section are a representative simulation demonstrating empirically that (a) for worst- case environments, both C-UCB and C-UCB-2 incur linear regret, while HAC-UCB successfully switches to incur sublinear regret to compete with Corral and UCB, and (b) for conditionally benign environments, HAC-UCB and C-UCB enjoy improved performance compared to UCB, Corral, and C-UCB-2, all three of which have regret growing like T. Implementation details are available in Appendix D and code can be found at http::/gihbb..ommmlliiiieeeeaadp baandaaaa.......aaaaaaaaaaaai...
5.1 Conditionally Benign Environment
First, we consider conditionally benign environment. Taking the gap A |A (log T)/T, the fixed conditional distribution for 2 = {0, is Y Z (1/2 + (1 A). Then, for a small (we take 0.0005), we set P LZ 0]
E and IP.,, 12 0] e for all other E A \ {1}. Thus, a = 1, and the actions are separated by A. In summary, each 2 E Z has positive probability of being observed, yet each action nearly deterministically fixes Z.
In Figure (left panel) we observe three main effects: (a) C-UCB and HAC-UCB perform simi- larly (their regret curves overlap), both achieving much smaller regret that remains unchanged by increasing |A,, (b) UCB grows at the worst-case rate of roughly /IA T T, not taking advantage of the conditionally benign property, and (c) neither Corral nor C-UCB-2 realize the benefits of the conditionally benign property, since the regret increases with |A| and empirically they perform worse than UCB. We note that the x-axis starts at T 500 satisfy the minor requirement of T 2
Conditionally Benign Environment (IAl=20, (Z)=2)
Worst Case Environment (IA)=20, IZ!=2)
700
UC3
600
Coral
1000
UDB
500
CLUCB.
UCC
800
Hagral(T)
Regrei(T)
400
600
300
400
200
100
200
0
1000
1500
3000
1000
Figure 2: Regret when the conditionally benign property holds (left) and when it fails (right).
5.2
Worst Case Environment
Second, we consider an environment that is not conditionally benign. We use the same general environment from our lower bound in Theorem 4.5, where the causal algorithms learn a biased estimate of which z E {0, 1} has a higher conditional mean since Z is not a d-separator, and consequently they concentrate onto bad action.
In Figure 2 (right panel), we again observe three main effects: (a) both C-UCB and C-UCB-2 incur linear regret, as prescribed by Theorem 4.5, (b) HAC-UCB achieves sublinear regret, although it is worse than UCB (we show in Theorem 6.2 that optimal adaptivity is impossible), and (c) Corral does not suffer linear regret, but appears still do worse than HAC-UCB for large T..
7

---

6 Adaptivity for Causal Structures
Thus far we have analyzed the regret of various algorithms in two cases: environments that either are or are not conditionally benign. Minimax algorithms (UCB) fail to achieve smaller regret for conditionally benign environments, while causal algorithms (C-UCB) fail catastrophically in environments that are not conditionally benign. In this section, we formalize the notion of strict adaptivity (adaptive minimax optimality) with respect the conditionally benign property, show that it is impossible to be adaptively minimax optimal with respect to the conditionally benign property, and discuss a relaxed notion of optimal adaptivity based on Pareto optimality.
6.1 Generic Algorithms
In order to describe adaptivity (and its impossibility) in the stochastic bandit problem with post- action contexts, we require a higher level of abstraction than a policy, which we achieve with algorithms. It is possible to define algorithms and the corresponding notion of adaptivity in abstract generality. However, we take the same perspective as Bilodeau et al. [8] (who define adaptive minimax optimality with respect to relaxations of the i.i.d. assumption), and sacrifice some generality by defining algorithms using the specific objects we study in this work. Formally, an algorithm is any map from the problem-specin inputs to the space of compatible policies, denoted by
a (A, Z.T,T - (A, (()) II(A, 2,T).
We denote the set of all algorithms by Ac MAB. and the subset of algorithms that are constant in (z, ((2) by AMAR: this subset contains the classical bandit algorithms that are agnostic to knowledge of post-action contexts, or more specifically, do not exploit causal structure.
6.2 Adaptive Minimax Optimality
Let (2 x D) + {0, 1 encode whether given environment satisfies a certain property of interest; in this work, it is always an indicator for whether is conditionally benign. Further, for every E (Z), denote the set of all environments with marginal q by IIx,2 (q) {u E P x ))) v(Z) 9). There are multiple ways one could define optimal adaptivity: we propose the following notion of strict adaptivity, which requires that the experimenter to do as well as they possibly could have if they had access to p(v) in advance, but without this knowledge.
Definition 6.1. An algorithm if there exists C > O such that for all A, Z, E (2)A, and
ACMAR is adaptively minimax optimal with respect P if and only
sup Bu
(T) SC
inf sup xEI(A.2.TT) veNl
Re (T)
(6.1)
=
and
sup ( P())=1
Rv.a(AZZ..ITT)))) S
inf sup =EIT(A,ZTT) vElL ((). p(o)-1
R
(6.2)
6.3 Impossibility of Striet Adaptivity
We now show it is impossible for any algorithm to always realize the benefits of the conditionally benign property while also recovering the worst-case rate of /IA T (e.g.. Theorems 9.1 and 15.2 of [19]), even when the algorithm has access to the true marginals. Our proof strategy is a modification of the finite-time lower bounds from Section 16.2 of Lattimore and Szepesvári [19]. Notably, the lower bounds of Lu et al. [24] already imply that any algorithm that does not take advantage of causal structure cannot be adaptively minimax optimal. We prove significantly stronger result: even algorithms that use Z and (Z)) = v(Z) cannot be adaptively minimax optimal!
Theorem 6.2. Let a Ac be such that there exists C > such that for all A. Z, and T,
sup Ry. (T) S SCVAT. (2x))
There exists a constant C' such that for all 2, and 2 |A], there exists conditionally benign E (Z x 4)A with
Ru..(AA.E.v22,))) (T) C² VAIT.
8

---

6.4 Pareto-Adaptive Minimax Optimality
In light of this impossibility result, it is of interest to characterize relaxations of strict adaptivity that are achievable. Koolen [15] and Lattimore [18] introduce the Pareto frontier of regret, which when applied to the conditionally benign property, all tuples of regret guarantees such that improving the regret in conditionally benign environments would necessarily force the worst-case regret to increase. We propose that it desirable for an algorithm to do as well as possible in the worst-case, subject to always realizing smaller regret on conditionally benign environments. Formally, let AC be the subset of a E ACMAn that satisfy Eq. (6.2) for some constant C.
Definition 6.3. An algorithm a' E A'eman is Pareto-adaptively minimax optimal with respect to p if and only if there exists C' >> 0 such that for all E ACCAA A. Z, q E ((Z) and T,
sup xE
(1.2,,1) SC sup
R (T. vellA,((1)
It remains an open problem to prove whether HAC-UCB is Pareto-adaptively minimax optimal, and more generally to identify the Pareto frontier for the causal bandit problem.
Related Work
Kocaoglu et al. [14] and Lindgren et al. [23] efficiently used interventions to learn causal graph under standard causal assumptions [29]. Hyttinen et al. [13] identified the minimal number of experiments needed to learn underlying causal structure of variables with only a linear structural assumption. Lee and Bareinboim [20, 22, 21] identified the minimal set of interventions that permit causal effect identification in the presence of known causal structure, while Kumor et al. [16] studied analogues of the back-door condition for identifying causal effects with unobserved confounders.
Bareinboim et al. [7] introduced causal bandits with a binary motivating example to demonstrate that empirically better performance can be achieved by exploiting a specific, known causal structure. Lattimore et al. [17] and Yabe et al. [35] studied best-arm identification, where the experimenter does not incur any penalty for exploration rounds. Given knowledge of the causal graph informing the interventions and response, they separately proved that exponential improvements in the dependence of the regret on the action set are possible provided the underlying distribution on the causal graph is sufficiently "balanced".
Sen et al. [32] obtained an instance- instance-dependent regret bound under causal assumptions, but obtained the wrong dependence on the arm gap (A -2 rather than A ''), and consequently in the worst- the dependence on T may still dwarf the structural benefits. Sen et al. [33] studied an alternative type of intervention, where rather than fixing node only the conditional probabilities are changed. This notion is easily stated our notation, since we allow for abstract families of distributions (indexed by abstract "interventions") to define environment. However, they focused on distribution depeddent guarantees under stronger causal assumptions, and hence our results are not directly comparable.
All of the above regret bounds heavily require assumptions about the causal graph, and without such assumptions the presumed information learned from non-intervening rounds can catastrophically mislead the experimenter in exactly the same way that C-UCB suffers in our Theorem 4.5. Hence, it remains an interesting open problem to study adaptivity in each of these variations of the causal bandit setting, and our work provides a stepping stone to do so.
Prior to the present work, Lu et al. [24] has already been extended in multiple directions. de Kroon et al. [12] observed that C-UCB can be reduced to requiring only a separating set, but only prove the regret is no worse than that of UCB if a separating set observed. The authors remark that a causal discovery algorithm could in principle be used to learn the separating set online, but observed in their experiments that they obtain biased estimates and hence there are no convergence guarantees. Lu et al. [25] replaced knowledge of the causal graph with the assumption that the causal graph has a tree structure, and incorporated the cost of learning the tree into the full regret bound. Nair et al. [27] provided an rnstance-dependens regret bound for an alternative algorithm to C-UCB, which they call C-UCB-2, in the presence of the full causal graph. While they demonstrated empirically that C-UCB-2 outperforms C-UCB for certain instances, we find that C-UCB-2 performs much worse when a d-separator is observed, and the provable linear lower bound (Theorem 4.5) also applies to C-UCB-2 2 when there are no observed d-separators.

---

8 Discussion
We have demonstrated that the improved regret possible when d-separator is observed also be realized in the multi-armed bandit problem by requiring only certain conditional independencies. which we have formalized using the conditionally benign property. We proved that it is impossible to optimally adapt to this property, but provided a new algorithm (HAC-UCB) that simultancously recovers the improved regret for conditionally benign environments and significantly improves on prior work when the conditionally benign property does not hold. Crucially, our algorithm requires no more assumptions about the world than vanilla bandit algorithms. We expect our results to spur future work on (a) improved adaptation to the conditionally benign property. (b) relaxations of the conditionally benign property for which optimal adaptation is possible, and (c) adaptation more general partial feedback settings.
In practice, HAC-UCB will be most useful in settings with large action space and intermediate variables that may plausibly satisty the conditionally benign property. In passing, we mention that one such example is learning the causal effect of genome edits (interventions) on disease phenotypes. Here, the post-action context could be gene expressions that are sometimes assumed to be a d-separator (e.g.. [3). We leave the implementation of our algorithm in clinical settings and collaboration with practitioners for future work.
Acknowledgements
BB is supported by an NSERC Canada Graduate Scholarship and the Vector Institute. DMR is supported in part by an NSERC Discovery Grant, Canada CIFAR Al Chair funding through the Vector Institute, and an Ontario Early Researcher Award. This material is based also upon work supported by the United States Air Force under Contract No. FA850-19-C-0511 Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Air Force. Part of this work was done while BB and DMR were visiting the Simons Institute for the Theory of Computing. We thank Zachary Lipton for suggesting to consider simultaneously adapting to estimation of the marginal distributions, and we thank Chandler Squires, Vasilis Syrgkanis, and Angela Zhou for helpful discussions.
References
[1] Y. Abbasi-Yadkort P. L. Bartlett, V. Gabillon, A. Malek, and M. Valko. Best of both worlds: Stochastic and adversarial best-arm identification. In Proceedings of the 31st Annual Conference on Learning Theory, 2018
[2] A. Agarwal, H. Luo, B. Neyshabur, and R. E. Schapire. Corralling a band of bandit algorithms. In Proceedings of the 30th Annual Conference on Learning Theory, 2017.
[3] H. F. Ainsworth and H. J. Cordell. Using gene expression data to identify causal pathways be- tween genotype and phenotype in a complex disease: Application to genetic analysis workshop 19. BMC Proceedings. 10(49), 2016.
[4] R. Arora, T. V. Marinov, and M. Mohri. Corralling stochastic bandit algorithms. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021.
[5] Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2):235-256, 2002.
[6] P. Auer, N. Cesa-Bianchi, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002.
[7] E. Bareinboim, A. Forney. and J. Pearl. Bandits with unobserved confounders: A causal approach. In Advances in Neural Information Processing Systems 28, 2015.
[8] B. Bilodeau, J. Negrea, and D. M. Roy. Relaxing the i.i.d. assumption: Adaptively minimax optimal regret via root-entropic regularization, 2020. arXiv:2007.0655::
[9] S. Bubeck and A. Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Proceedings of the 25th Conference on Learning Theory, 2012.
10

---

[10] S. Bubeck, R. Munos, and G. Stoltz. Pure exploration in
bandits problems. In Proceedings of the 20th International Conference Algorithmic Learning Theory, 2009.
[11] C. Canonne. short note on learning discrete distributions, 2020. arXiv:2002.11457.
[12] A. A. de Kroon, Belgrave, and M. Mooij. Causal bandits without prior knowledge using separating sets. In Proceedings of the 1st Conference on Cousal Learning and Reasoning, 2021.
[13] A. Hyttinen, F. Eberhardt, and P. O. Hoyer. Experiment selection for causal discovery. Journal of Machine Learning Research, 14:3041-307,, 2013.
[14] M. Kocaoglu, A. Dimakis, and Vishwanath. Cost-optimal learning of causal graphs. In Proceedings of the 34th International Conference Machine Learning, 2017.
[15] W. M. Koolen. The Pareto regret frontier. In Advances in Neural Information Processing Systems 27, 2013.
[16] D. Kumor, J. Zhang, and E. Bareinboim. Sequential causal imitation learning with unobserved confounders. In Advances in Neural Information Processing Systems 35, 2021.
[17] F. Lattimore, T. Lattimore, and M. D. Reid. Causal bandits: Learning good interventions via causal inference. In Advances in Neural Information Processing Systems 30, 2016.
[18] Lattimore. The Pareto regret frontier for bandits. In Advances in Neural Information Processing Systems 29, 2015.
[19] T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[20] S. Lee and E. Bareinboim. Structural causal bandits with non-manipulable variables. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019.
[21] S. Lee and E. Bareinboim. Causal effect identifiability under partial-observabilityy In Proceed- ings of the 37th International Conference on Machine Learning, 2020.
[22] S. Lee and E. Bareinboim. Characterizing optimal mixed policies: Where intervene and what to observe. In Advances in Neural Information Processing Systems 34, 2020.
[23] E. M. Lindgren, M. Kocaoglu, A. G. Dimakis, and S. Vishwanath. Experimental design for cost-aware learning of causal graphs. In Advances in Neural Information Processing Systems 32, 2018.
[24] Y. Lu, A. Meisami, A. Tewari, and Z. Yan. Regret analysis of bandit problems with causal background knowledge. In Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence, 2020.
[25] Y. Lu, A. Meisami, and A. Tewari. Causal bandits with unknown graph structure. In Advances Neural Information Processing Systems 35, 2021.
[26] Lykouris. V. Mirrokni, and Paes Leme. Stochastic bandits robust adversarial corruptions. In Proceedings of the 50th Anmual ACM SIGACT Symposium on Theory of Computing, 2018.
[27] V. Nair, V. Patil, and G. Sinha. Budgeted and non- budgetdd causal bandits. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021.
[28] Orabona. A modern introduction to online learning, 2019, 1rXiv:1912.13213.
[29] Pearl. Causality. Cambridge University Press, 2nd edition, 2009.
[30] Pearl, M. Glymour, and N. Jewell. Causal Inference in Statistics: Primer. Wiley, 2016.
[31] Y. Seldin and A. Slivkins. One practical algorithm for both stochastic and adversarial bandits.
In Proceedings of the 31 International Conference on Machine Learning, 2014.
[32] R. Sen, K. Shanmugam, M. Kocaoglu, A. Dimakis, and S. Shakkottai. Contextual bandits with latent confounders: NMF approach. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.

---

[33] R. Sen, K. Shanmugan, A. G. Dimakis, and S. Shakkottai. Identifying best interventions through online importance sampling, Proceedings of the 34th International Conference on Machine Learning, 2017.
[34] T. S. Thune and Y. Seldin. Adaptation to easy data in prediction with limited advice. In Advances in Neural Information Processing Systems 31, 2018.
[35] A. Yabe, D. Hatano, H. Sumita, S. Ito, N. Kakimura, T. Fukunaga, and K.-i. Kawarabayashi. Causal bandits with propogating inference. In Proceedings of the 35th International Conference on Machine Learning, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(C) Did you discuss any potential negative societal impacts of your work? [No] do not see any negative societal impacts of these theoretical results.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] All computations were done on
CPU on personal laptop computer.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "paygbYkJN9y", "reviewer": "Reviewer_KRsJ", "summary": "This paper proposes a novel algorithm for causal bandits that achieves “best of both worlds”: comparable performance to the benchmark C-UCB algorithm in conditionally benign environment while achieving a much better performance in the worst-case environment. In the causal bandit setting, the player observes some other post-action contexts after they play some action, rather than observing all contexts before they play an action. Under this setting, they introduce the conditional benign property which is closely tied with d-separability. They show that the benchmark C-UCB algorithm suffers linear regret when the environment is not conditionally benign, and it is impossible to achieve worst-case optimal regret and optimal regret in the conditional benign environment simultaneously. Then, they introduce the notion of Pareto optimality based on the Pareto frontier and show that their new algorithm, HAC-UCB, is Pareto optimal. \n", "questions": "None in addition to the above.", "limitations": "The author could discuss more on the limitations of their proposed algorithm, e.g. in which situation does it work well, and in which situation does it work poorly, in theory and in simulation? \n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In terms of originality, the paper provides several interesting contributons. Firstly, they introduce the idea of a \"post-action\" context. Secondly, they provide a novel algorithm, HACUCB to solve the post-action context problem with a specific application of causal bandits when observing a d-seperator of d-separators. Perhaps most interestingly is the new impossibility results for previous algorithms (C-UCB) which achieve optimality in the assumption of a conditional benign environment, and provide interesting lower bounds. \n\nOverall the paper is well written and easy to understand. The impossibility results are very surprising, including those about adaptive minimax adaptivity.  As far as the experiments, they are not extensive, however they demonstrate the advantage of HACUCB over CUCB in benign settings effectively. \n\nMy only comment is that although this paper is a direct extension to the existing literature Lu et al, it needs more justification to show the significance. For example, I would love to see some real applications of their algorithm.\n\nOverall, I would love to accept the paper based on the amount of work and technical contributions. I think this paper has interesting ideas and the paper is well written. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mYum_crvzL", "reviewer": "Reviewer_GygT", "summary": "This paper studies the problem of online learning in causal bandits, i.e., multi-armed bandit models compatible with a certain set of structural constraints encoded in a causal graph. Existing methods assume that the correct causal graph is provided. This paper studies an important generalization of this problem setting where the causal graph could be misspecified. The authors propose an algorithm that could achieve a sub-linear regret in the most general cases where the graph is incorrect. It is also able to exploit the existence of independence constraints to improve the learning performance when the graph is accurate. The authors further provide the worst-case analysis showing that any online learning algorithm is unable to achieve the optimal regret bound with and without the causal graph simultaneously when the graph misspecification is possible.", "questions": "In Definition 6.1, the constant C in Eqs 6.1 and 6.2 appear to be the same. While in Theorem 6.2, the negative result utilizes two different constraints C and C'. Is this a typo? Otherwise, Theorem 6.2 does not seem to show that \"it is impossible to be adaptively minimax optimal with respect to the conditionally benign property.\"", "limitations": "The authors have clearly stated the assumptions behind the proposed methods. This work is mainly theoretical, and its long-term societal impact is unclear to see.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is clearly written and well-organized. It attempts to address a challenging problem: online learning combined with hypothesis testing on pre-specified domain knowledge, which could possibly be misspecified. Existing methods in the causal bandit literature mostly assume the correct causal graph is provided. Therefore, I think this paper could have an impact on both reinforcement learning and causal inference. The proposed algorithm, HAC-UCB, appears sound and demonstrates some desirable properties. That is, the algorithm is able to achieve a sub-linear regret in the most general bandit model while improving the regret bound by exploiting underlying independence constraints when assumptions in the graph are accurate, represented in the form of a set of d-separators. \n\nWhile it is sub-linear, the regret bound of HAC-UCB is still worst than UCB in the general case. To understand this observation, the authors also provide the worst-case analysis of this learning setting. The result is interesting. It suggests that there exists no online learning algorithm that could achieve the optimal regret bound with and without knowing the correct causal graph simultaneously.  This suggests that the performance gap between HAC-UCB and UCB might be expected.\n\nAs for the weakness, I think the lower bound result in Theorem 6.2 does not suggest that the regret of HAC-UCB could not be improved. Theorem 6.2 states that one could not design an online algorithm achieving regret $\\mathcal{O}(\\sqrt{|A|T})$ (without graph) and $\\mathcal{O}(\\sqrt{|Z|T})$ (with graph) simultaneously. However, this does not mean that it is infeasible to design a robust online algorithm capable of graph misspecification while achieving the same regret as UCB, which is $\\mathcal{O}(\\sqrt{|A|T\\log(T)})$. The main reason is that the regret bound of UCB is not tight, containing a log factor $log(T)$. Therefore, the authors comment, \"In Theorem 6.2, we will show that, up to logarithmic factors, it is impossible to improve the $T^{3/4}$ n this bound to $\\sqrt{T}$ while still achieving the improved regret on conditionally benign environments\", is somewhat misleading, and should be removed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "U7jp9aTVRLG", "reviewer": "Reviewer_XZzq", "summary": "The paper addresses the multi-armed bandit problem where post-action contexts are observed and may or may not be a d-separator. When there is no d-separator, many algorithms including the UCB algorithm achieve the optimal regret. On the other hand when there is information on which variable is a d-separator, UCB style algorithms (such as C-UCB) have been proposed that achieve a regret bound that depends on the cardinality of the d-separator variable instead of the number of actions. \nHowever, there is no former algorithm that addresses the case where the learner does not know whether a post-action variable is a d-separator or not. A safe way would be to apply the original UCB algorithm, but this will achieve suboptimal regret in case there actually is a d-separator. On the other hand, authors prove that using the C-UCB algorithm can result in linear regret in case there is no d-separator. \nAn adaptive algorithm is required to identify the d-separator variables and decide whether to implement original UCB or C-UCB for action selection. Authors propose a new algorithm based on consecutive hypothesis tests that identify whether a variable is a d-separator. The algorithm achieves optimal regret when there actually is a d-separator, and sublinear (O(T^{3/4})) regret when there is no d-separator. Authors also prove that their bound cannot be shaved off by more than T^{1/4} order.\n", "questions": "Were the experiments performed repetively, or was it just one run?\n", "limitations": "I did not find any discussion on the societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The authors define the conditional benign property under which the proposed algorithm achieves optimal regret. This property is a weaker assumption than previous works. Also, the proposed algorithm does not require to know the exact marginal distribution of the d-separator variables. The optimal regret is achieved with approximate distributions as well.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GjpZpJCykqr", "reviewer": "Reviewer_tTqa", "summary": "The authors study adaptivity in the setting of causal bandits. They consider a bandit setting where after an action a is taken, a post-action context Z_a is observed. They propose a new property, a conditionally benign bandit environment that subsumes Z being a d-separator and other assumptions previously studied in the literature. They develop an algorithm that is adaptive to whether the bandit environment is conditionally benign. This allows the algorithm to obtain a regret bound matching C-UCB, a SOTA algorithm for causal bandits, when the bandit environment is conditionally benign and that has a sublinear regret otherwise. The authors also show that it is impossible to be minimax optimal at once for environments satisfying the conditionally benign property and violating the conditionally benign property. ", "questions": "What are real-world examples of the protocol?\n\nDo the authors believe the algorithm could make improvements on real-world problems? It would be nice to see the empirical performance of the algorithm on real-world problems or larger-scale simulations.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper initiates the study of adaptivity in causal bandits, a very important problem. \n\nThe authors give a set of strong and novel results. In particular, their impossibility result on strict adaptivity is interesting.\n\nThe proposed notion of conditionally benign environments seems like a nice and simple generalization of prior assumptions in the literature. \n\nThe authors give a very strong empirical validation of the theory. It is nice to see that existing algorithms do not adapt to the distinct settings, while the proposed algorithm does. \n\nWeaknesses:\n\nThe authors do not seem to give real-world examples of the bandit protocol, which may make it seem more like a mathematically convenient setting to study adaptivity in causal bandits. In what applications, would a post-action context be observed?\n\nWhile the problem itself it important and nice theoretical progress has been made, it is unclear to me that the proposed algorithm would lead to practical gains on real-world problems. In the particular, the initial burn-in time of playing each arm $O(\\sqrt{T}/|A|)$ times seems costly and the hypothesis test seems potentially loose. It would be nice to see the empirical performance of the algorithm on real-world problems or larger-scale simulations.\n\nThe algorithm uses fairly standard ideas in the literature. It uses a hypothesis test to determine whether the environment is conditionally benign. Therefore, the algorithmic novelty seems limited.\n\nAs the authors indicate, the rate $T^{3/4}$ may be suboptimal. I'm curious as to whether this result is tight for the algorithm and whether there may be an algorithm with an improved rate. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept