Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper investigates the problem of 'causal bandits,’ a sequential decision problem where the agent can intervene on a causal DAG (setting the value of a variable) and receives a reward associated with an unknown variable’s value.  Unlike prior works, in this paper, only partial prior knowledge of the structure is known (essential graph).  In addition to the reward, the agent also observes the realization of all the variables; that information with the essential graph helps inform the agent of where in the graph the reward-generating variable is.   Although the agent need not learn the full causal structure for the task, prior work on causal structure learning provides an algorithmic foundation for approaching the causal bandits problem.  Regret bounds for the algorithms are provided for trees, forests, and then general graphs (which satisfy certain topological constraints).  Lower bounds are also provided.  
main_review: Major Comments
•	Overall I found the paper quite interesting.  As the authors are upfront about, the algorithm design largely builds on central-node procedures for learning the causal structure.  Especially for trees and forests, that approach is at a high-level intuitive and the authors demonstrate effective.  As the authors point out, for the causal bandit problem, you only need to learn enough about the structure to identify with high confidence what region of the graph contains that variable; eg it is suboptimal to have one stage where you fully learn the graph and then search for reward-generating variable.  
•	In terms of contribution, if the focus were just on trees, that might not have been enough, but the authors extend the algorithms to a class of general graphs, though point out limitations of central-node procedures in that case. 
•	There are no empirical results, which I think is ok given the analyses, though even simple experiments could further improve.
•	The paper adopts terminology and notation from Greenewald et al., but it should nonetheless be self-contained; for instance, q() shows up in Definition 2 without any description beyond being ‘a distribution over nodes’; `a weight of a branch’ not explained, what a ‘central node’ is and why it changes is confusing at first (the nodes themselves are not; eg topology is static). While the high-level search strategy is communicated (Fig 1 is helpful), I don’t think some of the important details of how that is done are.

Minor comments
•	line 6-7 ‘In this paper, we develop novel causal bandit algorithms without knowing the causal graph. Our algorithms work well for causal trees, causal forests and a general class of causal graphs.’  Slightly misleading, should qualify in abstract that the algorithm knows the essential graph.  
•	For causal bandits, while it looks common to assume there is a single reward-generating variable, it sounds quite limiting.  The authors discuss this in part in Footnote 2 – the statement does not seem obvious to me though if they mean there is a single reward that depends on multiple variables.  If they mean that there are multiple observable rewards, each of which depends on a distinct single variable, then it is trivial.   If the former is meant, wouldn’t the reward function need to have quite special properties?
•	Minor issue, but line 140 discusses optimal intervention before the objective function introduced, line 143 uses Y which is not introduced, $X_t$ not defined
•	(very minor) Assumptions 2 and 3 – it is clear that both properties are needed, though I was a bit surprised that Assumption 2 does not imply Assumption 3 (though the dependence of \Delta on \epsilon, the graph topology, and P may be complicated).  I did not look at the appendix for the lower bound proof that contains an example, but if there is a simple high level explanation of why not, it might be worth mentioning.   
•	(minor) Claim 1 is imprecise – what does it mean to be ‘determined’ or for the subtree to be ‘found’?  that there is a number of interventions that is sufficient for exact structure recovery  with high probability ?
•	(very minor) $B$ used for branch in graph and algorithm parameter (Theorem 1)
•	Lastly, I think some discussion, even high level, of per-round computational complexity would be beneficial.

limitations_and_societal_impact: Yes (while there are potential applications of this idea to the sciences, this work itself is theoretical)
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper presents a causal bandit algorithm for graphs with unkown causal structure (but no unobserved confounders). It is based on a couple of recent results in learning causal graphs using interventions, and previous causal graph work. 
main_review: Authors provide an algorithm for causal bandits with logarithmic regret with a graph of unknown structure. Unlike causal graph setting, where the goal is to learn the whole graph, in causal bandit setting it is unnecessary, which is one major difference between this and previous work on causal graph structure. I am not aware of the previous causal bandit work that can achieve this on unknown graphs. Thus combining the two approaches is the novelty of the paper.

 Their assumptions are:

-Standard graphical causality assumptions

-No hidden confounders (also standard -- while most applications will have hidden confounders, proving anything in their presence gets much harder).

-Underlying graph's clique tree has intersection-incomparible property. This last assumption is the least common of the three, and something that would be great to relax if possible or further justify. It is also present in previous work on causal graphs which this work is based on.

I did not check the proofs in the Appendix carefully, and assumed for this review that proofs hold. They seem to hold "intuitively", so I would be surprised if they do not, but can not vouch for that.

limitations_and_societal_impact: Societal impact: similar to other papers in the field, so I don't think much new has to be said.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: The authors present a novel approach to tackle so-called causal bandit problems where the structure of the underlying graph is unknown. The algorithm is based on a ‘central node’ approach to find the direct parent of the reward as soon as possible. Under certain restrictions various regret bounds are derived for this algorithm that show the asymptotic behaviour outperforms standard multi-arm bandits by a significant margin, though no experimental verification is provided.

main_review: The problem considered in the paper is indeed challenging and relevant, and has so far not received the attention it deserves. 

Unfortunately, despite some nice results on regret bounds, the execution in the paper falls far short of what is promised at the outset. The end result is very disappointing and I consider it a missed opportunity.

On the plus side, the paper technically does provide a causal bandit approach for unknown causal structure that outperforms standard MABs, and it does offer some nice results on regret bounds. However it does so by invoking such strong restrictions and assumptions that it effectively kills the problem it set out to solve.

- Essentially it is a standard ‘balanced split’ search method that is then presented as a ‘causal bandit approach’ by restricting the class of allowable causal models so far that the proposed search method works. These restrictions/assumptions reduce the problem to a trivial case (tree like where all ancestors have measurable impact on the reward) with little hope for any real-world situation to fit the problem. And there is little hope of adapting the method to more realistic causal structures, as the core of the method has little to do with causality or causal structures in the first place.

- The ‘with unknown graph structure’ from the title turns out to involve full knowledge of the equivalence class representation of the model after all. And then it is supposed to be of a very specific type as well. 

- The ‘causal sufficiency’ part of assumption 1 is disappointing as in practice the larger the graph the more likely we are missing some relevant confounders. For a principled causal bandit approach this should not erven be necessary, but ok. Causal faithfulness is not needed for the current task (provided assumption 2 holds).

- The assumed ‘causal tree / forest’ structures are extremely limiting cases of the general class of all  possible causal structures (with or without sufficiency). Worse, the then introduced ‘general class of causal graphs’  (section 5) turns out to be almost as restrictive. In other words: only if the causal bandit system under investigation happens to satisfy an extreme configuration can we apply the method presented here. And for large graphs the chance that any random causal structure will satisfy this condition is virtually negligible.

- Assumption 3 however is the most extreme and completely unrealistic in practice, especially if the (assumed) tree graph is large. It states that all ancestors of the reward function have a measurable impact on it. However, in practice long directed chains tend to result in extremely weak dependencies that will remain undetectable even with huge amounts of data. 

- Even worse: under the extremely strong assumptions in the paper the problem can be solved much more quickly than with the algorithm presented, because as soon as there is an intervention on ANY of the ancestors of the reward function in stage 2 of the algorithm, its single direct parent can be found immediately by virtue of assumption 3: it will simply be the variable that shows the strongest dependence with the actual reward. No other tests are needed … which also indicates how niche and limiting the current setup is.


originality: novel approach but still fairly derivative
quality: main results (Theorems 1-3 and CN-UCB algorithm) are technically correct. However the method is seriously miss-sold as a ‘general approach under mild conditions’, and despite the ‘unknown graph structure’ claim in the title, the first line of the algorithm starts with having the graphical equivalence class representation of the true causal structure: that is just not good enough. Also no experimental evaluation is provided. 
clarity: writing is ok, with some minor flaws. Some good examples, but far too much emphasis on the straightforward ‘tree/forest’ case (7 pages) leaving nowhee near enough space for the general case (5.2) and lower bounds (section 6). 
significance: the approach is too niche and weirdly restrictive, making it unlikely to generate much interest from the (causal) bandit community. In fact it hardly deserves the moniker ‘causal’ at all, and is in many respects a missed opportunity.


minor comments:
p3.125: ‘Every directed edge in E(D) is within a v-structure’ => this is wrong. It is true that every v-structure corresponds to a directed edge in E(D), but other invariant directed edges are also possible.
limitations_and_societal_impact: No direct societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: Authors propose using the existing adaptive causal discovery algorithms to identify the reward variable in a causal graph efficiently and then run the existing bandit algorithms on this very small space of actions (interventions). They use the ideas from central node algorithm of Kristjan et al.: Identify a central node, either eliminate ~half the graph or find the subtree including the target node. They then have to check each child separately since either one of them can be the target node - which also serves as a method to check if central node itself is the target node. This takes ~dlogn interventions which can easily be converted to sample-complexity with the resorted assumptions. 

main_review: The two assumptions that are somewhat restrictive are the tree and in the next section intersection comparability assumption which was made by Squires et al. and that there is only a single node that affects the reward function. Despite these, I think this is a very nicely done first effort in this space of combining causal discovery with bandit algorithms. 

Authors also show necessity of the assumptions by constructing counterexamples based on Lattimore's results. I think these are very important and insightful results and I am glad the authors included those. 

Minor comments:
- Footnote seems to be hinting at that single X_R assumption is wlog. Is this true? Please elaborate on what fails or if it is. Discussion at the end seems to suggest this is only a tentative idea. Please clarify in the text as well.
- Causal faithfulness definition is not precise, please check. It should say "... has ONLY the independence relations". missing only completely changes meaning here. 
- Directed tree assumption is indeed motivated by essential graph here but this is not explicitly stated in page 3 which makes the assumption look more restrictive than it actually is. 
- Essential graph definition in page 3 has an issue: It doesn't only involve edges that are part of v-structures but also those implied by Meek rules. E.g. X->Y->T + Z->T is the DAG and the essential graph since Z->T can be identified by the first Meek rule. 
- abstract: MAB bandit->MAB.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper gives low-regret algorithms for the causal bandits problem when the graph structure is unknown. The main contribution is in combining use of some recent results on efficient causal structure discovery with traditional UCB approaches. Some minimax results are given to demonstrate the necessity of the assumptions made. 
main_review: ### Originality
+ The use of the causal discovery results by Greenewald et al. (19) and Squires et al. (20) within the context of a targeted structure discovery problem is a very nice idea. An assumption on there being some kind of tree structure (either a graph that is a forest or junction tree), allows the proposed algorithm to be more efficient than a naive application of these structure learning approaches, because they disregard parts of the tree as soon as they are found not relevant to the reward. 
+ To my knowledge this is the only work on causal bandits where the causal graph structure is unknown. 

### Quality
+ The assumptions are intuitive and the results of section 6 reinforce their importance. 
- No consideration is given regarding the computational complexity of selecting each intervention. This seems like something that could at least be commented on for the various stages of Algorithm 1. 
- Would be nice to see a comment on how well these ideas might extend to continuous random variables, in particular linear bandits. 
- Other works I've seen on this area have included some experimental results on simulated data. I think there would certainly be some value in those here: demonstrating practical implementation of the proposed algorithms; considering the effect of graph structure on performance; performance when the identifiability assumptions break; performance when the intersection-incomparable assumption doesn't hold on the clique graph. Relevant baselines would be UCB and existing algorithms that get given the graph structure. 

### Clarity
+ Description of the results, especially for tree graphs, is very clear and easy to follow. Figure 1 is great for following the algorithm explanation. 
- It could be made more clear exactly what assumptions are allowing us to improve over UCB in terms of sample efficiency. It seems that it is because of both the assumptions on having some non-degenerate graph structure and that we get side feedback on the values of nodes, which is not present in the typical bandit problem. These assumptions are just as important to understanding the results as the well emphasised assumptions on identifiability. 
- I think it is worth acknowledging that whilst previous works are limited in assuming knowledge of the causal graph, they do also address various settings which would be considered natural extensions to this paper. For example Lu et al. (19) consider interventions on multiple variables simultaneously, and the linear bandit setting. 
- line 350: does -> do. 

### Significance
+ Causal bandits is a problem area that has received a fair bit of attention in the last few years, and good guarantees for the setting of an unknown graph structure is a significant contribution to the field. 
+ The minimax results also offer progress on understanding what assumptions are necessary to achieve interesting regret bounds for causal bandits when the graph structure is not known. 
limitations_and_societal_impact: No broader impact statement is given here but it isn't really necessary in this case.  The scope of the work was generally clear and some nice directions for future work were given.
review_title: null

Meta-review: All reviews are extremely favorable except one dissenting review.

This paper produced a very long discussion and engagement between dissenting reviewer, other reviewers and authors. I would like to thank all reviewers (especially the dissenting reviewer) for participating in the discussion.

I would like to state the main points of the dissenting review  and I feel that the discussion and authors final responses does address most of the serious concerns raised. Therefore, I am recommending acceptance. 

Particularly, this is the first paper (I am aware of) that solves regret minimization problem for causal bandits when only the equivalence class is known. The authors leverage existing structure learning results to obtain an algorithm that ensures non trivial regret (non trivial regret guarantee holds under some technical conditions).

Main points from the dissenting review - followed by paraphrased answers from either the authors/other reviewers.

a) First step requires having the full equivalence class graph available

A) many other works in active structure learning literature makes these assumptions. This paper considers a harder problem of regret minimization without full structure knowledge, this would be not be a major penalizing factor. Besides, interventionally it does not cost anything to assume one has enough observational samples. Therefore, it is a resonable assumption.

b) "unknown graph then needs to satisfy some extremely restrictive properties"

A)  Authors assume intersection incomparable property on the clique tree decomposition of the observational markov equivalence class. The property assumed can be tested with only the equivalence class which is an input to the bandit.

 Nevertheless, this is a popular assumption - both in structure learning and some prior literature. Another reviewer even hinted that in a random graph, this may be satisfied even with high probability (or at least depends on random graph model assumptions). This is satisfied with popular chordal graph sub families.

Other aspect is that the bandit algorithm would run irrespective of the assumption. It would halt at a specific line and then the bandit part of the algorithm would commence with potentially large number of arms.

*Note to authors*: I would urge the authors to note this point explicitly in camera ready and provide a complete algorithm with the halting conditions etc...

Not withstanding the above, it is an assumption to avoid a 'pathology' (in my opinion) in the clique tree.

c) The claimed regret bounds in Thm2+3 are misleading in that an order N dependence is hidden in a constant that actually scales with N

A) All regret bounds in MAB problems scale with problem parameters - ambient dimension in linear bandits, number of arms in multi armed bandits, some graph parameter when DAG is known in causal bandits. Here, this is number of chain components in the chordal graph which is a parameter that depends on the EC. If all nodes are isolated this would reduce to standard MAB and therefore such a regret scaling would be unavoidable.



Decision: Accept (Poster)