Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study the problem of causal bandits with (arbitrary) combinatorial action spaces in both fixed-confidence and fixed-budget pure exploration (simple regret) settings.  The causal graph is assumed to be known and all variables are binary valued.  The authors consider two cases.  For the first, the causal model is parameterized, with which parameters for most actions can be estimated from observational data and the rest are estimated using interventions.  The algorithm is based on the LUCB algorithm.  For the second (more general) case, the causal model is not parameterized and hidden nodes are available; the proposed algorithm overall has a similar structure as in the first case.   The authors also show that the sample complexity of the latter algorithm is nearly minimax optimal.
strength_and_weaknesses: ### Major strengths

1. The authors showed that for a particular parametric class of models (BGLM with bounded derivatives), since the difficulty of estimating the conditional mean of Y can be characterized by graph properties in such a way that actions can be separated into “easy” and “hard” actions, an LUCB style algorithm can be employed that significantly improves the sample complexity.

2. The authors also generalize that strategy for the more general case with hidden nodes and for which the conditional distributions are not parameterized, and show the sample complexity of that algorithm is nearly minimax optimal.

### Minor strengths

1. The authors propose a fixed-budget pure exploration algorithm and analyze its regret (in supplementary material).

2. The authors include some toy experiments for their methods (in supplementary material).  

### Major weaknesses
1. The storage and per-round computational complexities can be exponential in $n$ even for parameterized setting with the BGLM model.  Separate statistics are maintained for each action (eg Alg. 1 line 2) and updated (eg Alg. 1 line 11).  The action set is allowed to be an arbitrary subset of the powerset of $X$.  

### Minor weaknesses
1. The assumptions for the BGLM model used are quite strong – $\theta$ parameters are non-negative, $f_X$ monotone, so that for any subset of nodes, it is immediate that the best intervention is to set all variables in that subset to value of 1.  Even for the slightly more general BGLM model without the same restrictions on \theta or $f_X$ (but with bounded derivatives), it seems non-trivial to modify Algorithm 1 short of treating each realization as a separate action, growing the action set (and consequently storage complexity and per-round computational complexities) exponentially.  

2. The readability could be improved by modifying notation or adding more verbal descriptors reminding the reader what notations refer to, especially those used sparingly -- eg $P_{S,Y}$ used to specify nodes along paths but P already used for probabilities; \sigma introduced on page 5 for expected values and used once in Lemma 2 but already have \mu notation for that.  The pseudocode of Alg 1 and 3 are heavy with notation and equations – the precise formulas could be discussed in the main text and referenced (or simplified).

3. The storage and per-round computational complexities of the methods were not formally discussed in the main sections.



### Questions 
1. Pg 3 Can you clarify what the sentence “To represent the native probability, …” means

2. Pg 3 Can you clarify why in the BLGM model the probability mass functions are random?  The X’s would be random even without the $e_X$ term.  More concerning to me is that you have an additive random term, but you are assuming that the sum is constrained in [0,1] to be a valid probability mass.  To me at least, that seems to induce a strange constraint of f_X and $e_X$ since if the terms are independent, then both need to be bounded.  If $e_X$ is bounded, then it is sub-Gaussian.

3. Pg 4 “We assume that Xi’s are Bernoulli random variables when we do not intervene any variables” – What does that assumption mean?  They would have marginal Bernoulli distributions since they are binary valued, but they would have joint dependence.  


clarity,_quality,_novelty_and_reproducibility: Quality: Overall the paper is good.

Clarity: Generally speaking, I found the writing and presentation clear.  

Originality: The authors employ strategies (LUCB alg.) and results (BLGM concentrations) from past works, but in a non-trivial manner.  

Reproducibility: The authors provided proofs in the supplementary material, and proof sketches in the main paper.  I did not check the supplementary material.  I did not spot any issues with correctness.

summary_of_the_review: Overall I think the submission is good.  The topic, at the intersection of causal inference and multi-armed bandits can be of interest to multiple communities.  The authors adapt the LUCB algorithm in an interesting way for the causal bandit problem.  I have concerns that the storage and per-round computational complexity of the algorithm may render the algorithm primarily of theoretical interest, but nonetheless think the submission is good.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors extend Lattimore 2016 to obtain a gap-dependent bound (not regret since they operate in the pure exploration setting) bandit for parallel bandit graph, and also extend it to arbitrary graphs, so long as there is an admissable set. For example, if there is a valid back-door adjustment for the actions. 
strength_and_weaknesses: They propose a solution to a very special case of a very hard problem. I think the results are still interesting. 

The linear setting is a bit restrictive especially when combined with the assumption that all parameters are nonnegative (can this assumption be removed?)

The general graph case is a bit rushed. For example, how often do we have that all candidate actions have valid admissable sets? What if only some of them do? The algorithm should have been robust to this. Is there a way to incorporate this? Also it would be good to draw some graphs where the assumptions hold. 
clarity,_quality,_novelty_and_reproducibility: The paper heavily relies on Feng & Chen (2022) for some reason, even pulling lemmas from that unpublished manuscript without proofs. 

Compared to Lattimore 2016, I think the contribution is novel. 
summary_of_the_review: Thank you for your submission. I did enjoy reading it. I have a few comments/questions below.

Why are the weights in the network always non-negative? Isn't it to very strong assumption that the algorithm always knows that setting values to 1s are the only possible optimal interventions?

The paper borrows several assumption and even lemmas from Feng & Chen (2022). But this is an unpublished manuscript on arxiv. Specifically for the borrowed lemmas, it would be good to have proofs of them self contained in this submission. I couldn't find these proofs are given in the Appendix either. 

Some intuition about the definition of Gap-dependent observation thershold would be nice to have, similar to the baseline m value borrowed from Lattimore.  

Please add some causal graphs with candidate action sets for which admissable sequences or adjustment sets exist with latent confounders.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: -Proposes gap-dependent bounds on adaptive pure exploration algorithms. 

-Algorithms do not require prior knowledge of causal inference distributions. 

-Allows combinatorial interventions.

-Applicable to causal graphs with hidden variables. 

-Studies sample complexity in both fixed confidence and fixed budget settings. 

-Proposes the gap-dependent observation threshold as an intuitive measure of problem difficulty. 

-Proposes adaptive algorithms that interleave observation and intervention for efficient sample learning of optimal interventions.

strength_and_weaknesses: -Analyses pure exploration of combinatorial casual bandits in a general setting. Extends the results of prior works to general graphs with the possibility of unobserved variables. 

-Provides gap-dependent bounds on the sample complexity for the binary generalized linear model (BGLM). Unlike prior works, whose complexity grows exponentially, for BGLM, their sample complexity scales only polynomially in the graph size. Full adaptivity of the algorithm by interleaving exploration and exploitation is a key contributor to this improvement. 

-Provides an analysis of the general case where hidden variables exist. 

-Shows a lower bound for parallel graphs, establishing the near minimax optimality of the combinatorial casual pure exploration algorithm.

clarity,_quality,_novelty_and_reproducibility: Quality and novelty: This paper resolves the combinatorial pure exploration in casual bandits. It proposes novel algorithms for BGLM and generalized graphs and provides gap-dependent upper bounds on the sample complexity, which are accompanied by gap-dependent lower bounds on sample complexity for parallel graphs. Overall, this is a solid piece of work. 

Clarity: Long pseudocodes in the main text do not provide intuition about what is going on. It might be better to move the pseudocode of Algorithm 3 to the appendix and use the opened-up space for numerical results or additional insights. 

Why does Algorithm 3 require a casual parallel graph G as input (line 1)?

summary_of_the_review: A good paper that addresses several important issues in the combinatorial pure exploration of casual bandits with solid theoretical results.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors extend Lattimore 2016 to to a larger classed of graphs (the graph could be arbitrary as long as there is an admissible set) for the setting of combinatorial action spaces in both fixed-confidence and fixed-budget pure exploration (simple regret) scenarios.

Although some of the reviewers were concerned about limitations in the model (say linearity of positivity fo the parameters), they found the results and the presentation overall convincing. 

justification_for_why_not_higher_score: I think there are still too many restrictive assumptions and this is not a paper that solves a broadly interesting open problem.
justification_for_why_not_lower_score: The results are interesting enough to merit publication/presentation.
Decision: Accept: poster