Adversarial Causal Bayesian Optimization

We thank the reviewer for their thorough review.

I think there is some ambiguity w.r.t. the first sentence: the DAG can be known but the relationships (the mechanisms) of the DAG unknown, or vice versa. Which one do you mean? In the original paper (Aglietti et al) the DAG was always assumed known but there are other settings where the DAG is assumed unknown.

We know the graph $G$ but not that mechanism (the $f_i$). The same as Aglietti et al. We think that this is clear from the paper itself. We can make this more explicit in the abstract by changing this sentence to “... on a structural causal model with known graph but unknown mechanisms…”.

If you are modelling a phenomena in an environment that is changing, why is it not possible to model that with a temporal DAG? Or dynamical DAG? There is plenty of that type of work being done.

Here we model a changing environment where we measure and react to potentially adversarial changes. Our understanding is that the use of a temporal or dynamical DAG requires an explicit probabilistic model for the changing environment, whereas we do not need to create a model for the adversary’s behavior. We believe that it is not obvious how one could concretely use temporal and dynamical DAG models in our setup and with the notion of regret we study.

Your blue nodes sound very much like standard non-manipulative variables

Assuming the reviewer refers to the non-manipulable variables studied in [1], these are variables in the graph that one cannot intervene on. As we describe in section 2, we consider a soft intervention model where the $a_i’$ are parameters of the soft intervention on observation $X_i$. Therefore, we don’t see a connection between $a’$ and non-manipulative variables, because the former are the parameters of an intervention (performed by an adversary).

[1] Lee, S., & Bareinboim, E. (2019). Structural Causal Bandits with Non-Manipulable Variables. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 4164-4172.

What is the reasoning behind using soft rather than hard interventions? What would happen if you used hard instead?

Thanks for your question. We note that one could still run CBO-MW with hard interventions without modifications. This would however be incompatible with some of the technical assumptions in the analysis (that all $\mu_i, \sigma_i$ are Lipschitz). Hence we have focused on the soft intervention model for simplicity.

There are as many actions as there are nodes m in the graph? But then you are also intervening on the reward variable which is non-manipulative?

We note that the learner is not necessarily allowed to intervene on the reward, in which case $\mid \cal{A_m} \mid = 1$ and all our results still go through. However, a soft intervention model generally allows the agent to directly intervene on the reward. Since soft interventions don’t break the causal relationship between a variable and it’s parents, it is still meaningful to consider cases where the reward can be intervened upon.

To check my understanding: actions are continuous, but there are a finite amount of continuous actions, the cardinality of the domain of each action is then K? Why isn't each action just continuous?

The reviewer is correct. The reason why we consider finitely many actions, though, is for the learner to tractably achieve no regret. Indeed, in the adversarial setting, the learner must randomize its decision and sample actions from a mixed strategy. Such a strategy is tractable to compute, and update (line 6 of algorithm 1), if there is a finite number of actions. In practice, however, continuous action spaces can be discretized.

"Contrary to standard CBO (where algorithms can choose actions deterministically), in adversarial environments such as ACBO randomization is necessary to achieve no-regret" - why is that the case?

Intuitively, because the adversary has access to the game history and to the learner’s algorithm, if such an algorithm was deterministic then the adversary could anticipate the learner’s moves and thus inflict positive regret at each round. This is a standard argument in adversarial online learning and multiplayer games.

How many times do you have to initialise the neural networks in algorithm 2 for this to work?

In our experiments we performed a single initialization.

It would be helpful if you gave an example of a Lipschitz continuous kernel

Many commonly used kernels over continuous domains are Lipschitz continuous. Two examples: linear kernel and squared exponential kernel. This is mentioned in the cited work that we defer to in our paper.

what the consequence would be if you did not make this continuity assumption

We note that such an assumption is only required for the analysis of our regret guarantee. It is not a required assumption to apply the algorithm in practice.

We would like to ask the reviewer whether our review responses and the revision clarify the reviewer’s concerns and change their score considerations. We are happy to provide further clarifications while the platform is still open for discussion, which is until the end of 22nd of November.

We thank the reviewer for their review. Below, we respond to the reviewer’s concerns.

Could you explain what the choice of the adversary's action is based on?

From the text: “We assume the adversary does not have the power to know $a_{:, t}$ when selecting $a′_{:,t}$, but only has access to the history of interactions until round $t$.” Additionally, yes, we assume the adversary can know the agent’s algorithm (we’ll add a note to make this clear in the text). Since the agent can play a mixed strategy, the adversary can at best know the distribution the agent will select actions from at each round. This is not as strong of an adversary as knowing the agent’s exact actions, and makes the problem more intricate as the learner can achieve no regret if it’s mixed strategy is updated suitably (as we propose in the CBO-MW algorithm). We remark that this is a standard setup for the adversary in adversarial online learning.

If the adversary at time $t$ could see the agent’s action $a_t$ before selecting $a_t’$, it would be a Stackelberg game. We could also model this in our framework by directly modeling the adversary’s action as an observation $X_i$, since it is a direct reaction to the action we chose. We describe this in appendix A.1.1.

Could you explain the difference between your model and a model that combines stochanstic and adversary bandit?

Here we request further information from the reviewer. It is not clear to us what the point of comparison is because it is not obvious what it means to just combine a stochastic and adversarial bandit. We think if the claim is that the contribution is limited, it would be easier for us to give a helpful response if the reviewer 1) refers to specific works in the literature and then 2) describes how the delta between our work and these is trivial. We think this would allow us to more concretely discuss the contribution.

I don't see any fundamental difference between the studied model and a standard bandit or Bayesian optimization problem, where part of the model is stochastic and part of it is controlled by an adversary.

We respectfully disagree with the reviewer and we hope that the points discussed below can further clarify the novelty of our approach. In particular, we believe there is significantly novelty compared to previous Bayesian optimization methods:

• Because some part of the model is adversarial, the learner must randomize its actions to achieve no regret. Although standard adversarial online learning algorithms (such as multiplicative weights) exist for this, they require full-information feedback which is not available in Bayesian optimization.
• The only Bayesian optimization approach that can provably achieve no regret in such a setting is GP-MW. However, this algorithm does not build a causal graph and can thus be highly sample inefficient, as we show.
• In light of the above, CBO-MW is the first Bayesian optimization algorithm which can: 1) achieve no regret using 2) the learning of a causal reward model. Similar to GP-MW, CBO-MW also computes optimistic estimates for the full information feedback. However, because such estimates are obtained through computing a counterfactual using a causal graph, we provide a practical subroutine to compute these (optimistic) counterfactuals in an efficient way (section 4.3).
• We provide a regret guarantee and can show significantly improved rates compared to GP-MW (section 5)
• We show how to implement CBO-MW in a distributed way to improve the computational efficiency (section 6) and demonstrate good empirical performance (section 7).

We hope the above points clarify the reviewer’s concerns. We are happy to expand more based on the reviewer’ feedback.

We would like to ask the reviewer whether our review responses and the revision clarify the reviewer’s concerns and change their score considerations. We are happy to provide further clarifications while the platform is still open for discussion, which is until the end of 22nd of November.

We thank the reviewer for their review.

Relation to CBO

We use ‘causal Bayesian optimization’ (CBO) to describe the general causal Bayesian optimization problem, which is separate from the specific algorithm proposed by Aglietti et al. There have been several works studying this CBO setting since the original work of Aglietti et al. These works consider multiple variations of their setting: including soft intervention models (instead of hard interventions) and the cumulative regret metric (instead of the simulated regret metric). These are technical differences within a conceptually very similar set of problems.

The paper claims to show a generalization of CBO, which it seems to be an algorithm

Thank you for pointing out that in Aglietti et al. the authors specifically distinguish between causal global optimization (CGO) as their setting, and causal Bayesian optimization (CBO) as their algorithm. Therefore when specifically describing the setting of Aglietti et al 2019 we will refer to it as CGO in our paper too. We will however continue to refer to the general problem of global optimization in the presence of a causal graph and prior over mechanisms as causal Bayesian optimization. We will also refer to the setting of our paper as ACBO. This is consistent with the wider BO literature where BO - global optimization with a prior - is used to describe a setting and usually the algorithm is described based on the specific acquisition function e.g. UCB, UEI etc. We note that the paper of MCBO, a baseline we compare to, also describes their setting as ‘CBO’. The main difference here is whether you consider the prior as part of the setting or the algorithm. In Aglietti et al. they use a prior as part of their solution to the CGO problem, but in many other parts of the BO literature, the prior is considered part of the problem setting.

...CBO, there are intervention sets and intervention values/levels

CBO as in Aglietti et al. considers a hard intervention model. As discussed in the setup we consider a soft intervention model as in MCBO. Our model includes interventions on multiple variables. This explains the difference to what you read in Aglietti et al. Again we see this as more of a technical difference.

the authors claim to compare using "previous CBO benchmarks", but there are no benchmarks actually from the CBO paper of Aglietti et al 2020

Firstly, CBO assumes hard interventions so cannot be directly applied at least to the experimental settings we consider. We compare against MCBO on the synthetic experiments. In the MCBO paper, MCBO is compared to CBO with hard interventions in the stochastic BO setting under the cumulative regret metric, and MCBO performs favorably. We say “adversarial versions of previously studied CBO benchmarks”, meaning that we modify some of the environments from the MCBO paper (a paper about CBO) for the adversarial setting.

We hope the above points clarify the reviewer’s concerns and any misunderstandings. We are happy to expand more on this based on the reviewer’ feedback.

We would like to ask the reviewer whether our review responses and the revision clarify the reviewer’s concerns and change their score considerations. In particular, our clarification over the naming of the algorithm and naming of the problem setting. We are happy to provide further clarifications while the platform is still open for discussion, which is until the end of 22nd of November.

Thanks for engaging.

Regarding the first two points, please make sure that readers will not be confused with these things. Yes the MCBO paper called CBO the problem as you said but it indeed confuses the literature. It would be better if you improved the literature and clarified things properly.

"Again we see this as more of a technical difference"

This technical difference makes a lot of difference. What do you mean by "Our model includes interventions on multiple variables" ? Do you have to select which variables to intervene as well or it is given ? Again this is a major difficulty in CBO since of course there are a lot of subsets of the DAG variables to search over.

"Firstly, CBO assumes hard interventions so cannot be directly applied at least to the experimental settings we consider"

Again this is why it is confusing to say you are generalizing CBO throughout. I understand basically you want to use this name because it's simple and easy to remember, and I think it's even fine; but since there was something in the literature well defined and called CBO, it should be clear to the reader that "CBO" here is essentially not "CBO" of Aglietti et al 2020.

The differences are not just technical but major (cumulative regret vs simple regret, no causal priors here like in CBO) and make a lot of difference in what the algorithms should be doing, what are the challenges etc., so they are basically "related" research areas but on a superficial level.

With the hope that authors will clarify significantly the next version I will increase my score to 6.

We thank the reviewer for their thorough review.

“The related work ignores causal bandit literature?” After the related work sentence “Agliettiet al.(2020) propose the first CBO setting with hard interventions and an algorithm that uses the do-calculus to generalise from observational to interventional data”, we will add “The CBO line of work builds off the causal bandit setting [cite Lattimore], which similarly incorporates causal graph knowledge into the bandit setting usually considering discrete actions with categorical observations or linear mechanisms with continuous observations [cite Varici]..”.

The problem is not well motivated. Why is SMS adversarial and not stochastic?

We mention this in the experiments: “After each day,we observe weather and demand data from the previous day which are highly non-stationary” but we will add a sentence to the introduction that makes this clear from the beginning. In the 4th paragraph we will add: “In the SMS application, we observe the demand and weather which can only be observed at the day’s end, and are highly non-stationary. For example, the weather distribution will vary seasonally.”

“The graph notations are confusing. The typical graph has 1 root node. But in causal graphs, we may have multiple nodes without parents.” We were not able to follow this comment. If you could expand on it we are happy to take a look. Based on one of your later comments (addressed below), we think you might be getting root and leaf node mixed up.

“The adversary cannot see the action taken by agent before taking its action. Is this adversary weak? You have considered that the agent can see adversary's action before choosing their own action set, but what about vice-versa?” If the adversary at time $t$ could see our action $a_t$ and then respond with $a_t’$, it would be a Stackelberg game and not a simultaneous action game. Our setting, algorithm, and guarantees can actually also model this Stackelberg game setting. Since the adversary would respond directly to our action $a_t$, we could model the adversary action as a function of $a_t$ (and therefore treat it as just another $X$ in the graph). We discuss this in appendix A.1.1.

“You have considered that the agent can see adversary's action before choosing their own action set” This is not true. We consider a setting where the agent selects $a_t$ simultaneously with the adversary selecting $a_t’$, so the agent does not observe the adversary action beforehand. We believe that this is unambiguous in the paper from section 2 under “Problem Statement”.

“The additive term Beta^{N+1} does seem high.” After the regret guarantee we compare our regret guarantee with a non-causal approach and give a strong case for why we have a significant improvement. We are also to our knowledge the first to give any kind of guarantee at all for this particular setting (besides the guarantee you get from applying GP-MW which uses no causal information).

“Note that "Causal Bandits for Linear Structural Equation Models" Varici et al 2023 show that the regret scales as length of the longest causal path in the graph for linear SCMs, whereas you consider N - length of path to root node. The former (not cited in your work), seems tighter.”

We think that it is not meaningful to directly compare the guarantees from our paper and Varici et al.. Here are the two key differences in the setups:

• They consider linear mechanisms. We consider much more general models for each mechanism where they can be modeled with a GP (come from an RKHS with bounded norm). Linear models are closed under composition, so for their model the reward is still a linear function of the actions. For our setting, GPs are not closed under composition, so we get this emergent complexity where the reward as a function of actions is a much more complicated function class than just a single GP (it is a deep GP [1]).
• They consider the stochastic setting and therefore a much “easier” notion of regret than the one we consider in the adversarial/non-stationary case (see equation 3).

[1] Damianou, Andreas, and Neil D. Lawrence. "Deep gaussian processes." Artificial intelligence and statistics. PMLR, 2013.

We compare our regret bound to the only baseline we know of that can achieve a guarantee in this setting (GP-MW) and give an argument for why our guarantee is favorable. Varici et al 2023 considers a less general problem and while we think it is a great result, it is for a different setting to our result.

We’ll add a citation of Varici et al 2023 to the related work (see comment above on causal bandits).

We would like to ask the reviewer whether our review responses and the revision clarify the reviewer’s concerns and change their score considerations. For example, our clarification of relation to the causal bandit literature and relation of the regret bound to prior work. We are happy to provide further clarifications while the platform is still open for discussion, which is until the end of 22nd of November.