Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits

Causal knowledge about the relationships among decision variables and a reward variable in a bandit setting can accelerate the learning of an optimal decision. Current works often assume the causal graph is known, which may not always be available a priori. Motivated by this challenge, we focus on the causal bandit problem in scenarios where the underlying causal graph is unknown and may include latent confounders. While intervention on the parents of the reward node is optimal in the absence of latent confounders, this is not necessarily the case in general. Instead, one must consider a set of possibly optimal arms/interventions, each being a special subset of the ancestors of the reward node, making causal discovery beyond the parents of the reward node essential. For regret minimization, we identify that discovering the full causal structure is unnecessary; however, no existing work provides the necessary and sufficient components of the causal graph. We formally characterize the set of necessary and sufficient latent confounders one needs to detect or learn to ensure that all possibly optimal arms are identified correctly. We also propose a randomized algorithm for learning the causal graph with a limited number of samples, providing a sample complexity guarantee for any desired confidence level. In the causal bandit setup, we propose a two-stage approach. In the first stage, we learn the induced subgraph on ancestors of the reward, along with a necessary and sufficient subset of latent confounders, to construct the set of possibly optimal arms. The regret incurred during this phase scales polynomially with respect to the number of nodes in the causal graph. The second phase involves the application of a standard bandit algorithm, such as the UCB algorithm. We also establish a regret bound for our two-phase approach, which is sublinear in the number of rounds.

Paper

Similar papers

Peer review

Reviewer FQKc7/10 · confidence 3/52024-07-10

Summary

The paper addresses causal bandits problem without prior knowledge of causal graph and in the presence of latent variables. Previous work shows that the best possible interventions form a set known as POMISs. The paper theoretically demonstrates that a partial discovery of the causal graph is sufficient to find POMISs. To tackle the main problem, the authors propose a randomized algorithm to identify POMISs without complete discovery and then use the UCB algorithm on the candidate set.

Strengths

1- The paper considers an important problem in the causal bandits area, in which the graph is unknown and latent variables exist.  2- To find optimal candidate interventions (POMISs) the paper demonstrated that a partial discovery of the main causal graph is sufficient. (Theorem 3.1) 3- A two-phased algorithm has been proposed for solving the causal bandit by providing a precise theoretical analysis.

Weaknesses

1- The proposed regret bound can become very large when either $\epsilon$ or $\gamma$ is small, which is a possible scenario. 2- It’s not clear whether the proposed algorithm and upper is optimal or not. No discussion has been provided. 3- There is not any discussion regarding the running time of algorithms.

Questions

Could you discuss the points mentioned above? 1- The algorithms (e.g., Algorithm 4.1) are using the values in assumptions 4.1 and 4.2. How is it possible to access this information? 2- How do you compare your algorithm (the regret bound) with a naive algorithm that blindly iterates over all possible interventions? Is it possible the latter performs better than your algorithm? If yes, which types of graphs do have this property? (I read Section A.15) 3- In algorithm 2, for each iteration, Should not set $W = \emptyset$?

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

Yes.

Authorsrebuttal2024-08-11

Re.

Thank you for your reply. The **main deciding factor** in the choice between vanilla UCB and our proposed algorithm is the number of nodes, $ n $, in the graph. The vanilla UCB may perform better for graphs with a small number of nodes. However, as the number of nodes increases, it becomes infeasible to run the naive algorithm that does not consider causal information due to the exponential growth of the action space. Our simulations demonstrate that once the number of nodes exceeds a certain threshold—around 17 or so—the number of arms for the vanilla UCB algorithm grows significantly larger than our regret bound, as shown in the plot in Fig. 3. Note that we set the gap parameters $ \gamma = \epsilon = 0.01 $ in our simulations. The number of arms for the vanilla UCB algorithm scales exponentially with the number of nodes $ n $, whereas our regret bound scales polynomially with respect to $ n $. **Impact of graph structure:** Regarding the graph structure, it depends on whether we have prior knowledge of the underlying graph structure before running the bandit algorithm. For instance, if we know that there is a confounder between every pair of nodes in the graph, causal discovery will not reduce the size of the action space, and it might be preferable to skip causal discovery and apply only the classic UCB. The key factor here is that the reduction of the action space using causal discovery depends on the density of latent confounders. If there are confounders between a large number of pairs of nodes, the reduction in the size of the action space becomes smaller. However, without prior knowledge of the graph's structure, one cannot make this distinction. We will include a simulation with a range of values for the parameter $\rho_L$, from $0.10$ to $1.00$, to demonstrate how the reduction in the size of the action space achieved through causal discovery—compared to vanilla UCB—varies with the density of latent confounders in the underlying graph. Note that the parameter $\rho_L$ controls the density of latent confounders in the sampled graph. We are grateful to the reviewer for highlighting this point and we believe it would be a valuable addition to our manuscript. **Impact of parametric assumptions (i.e., $\epsilon$ and $\gamma$):** Regarding the parametric gap assumptions, $\epsilon$ and $\gamma$, they are constants that do not depend on the number of nodes in the graphs. As discussed earlier, running UCB with an exponential number of arms, specifically $(K+1)^n$, will result in very large regret for large $n$. However, we can still make a basic comparison between vanilla UCB and our algorithm by comparing the sum of the first four terms in our regret bound with the regret bound or the number of arms in the vanilla UCB algorithm, similar to Figure 3 in our paper. This comparison will help inform our choice. We will include this discussion in the revised manuscript. We hope that we have addressed the reviewer’s question and would be happy to discuss further if there are any follow-up questions. If the reviewer has no further questions, we would kindly request them to reconsider our score, taking into account our rebuttal and the additions we have suggested.

Reviewer FQKc2024-08-11

Thank you for your comprehensive discussion. After reviewing the rebuttals and considering the comments from other reviewers, I intend to raise my score to 7.

Authorsrebuttal2024-08-11

Re.

We thank the reviewer for their insightful comments and suggestions to improve the clarity of our manuscript. We are also grateful to the reviewer for increasing our score.

Reviewer VRJg6/10 · confidence 3/52024-07-10

Summary

The authors extend the methodology in Lee and Bareinboim [2018] (L&B) for regret minimisation in a causal bandit setting with initially unknown causal structure and possible latent confounding. They identify the necessary and sufficient structural knowledge of latent confounding to identify possibly optimal minimal intervention sets (POMISs), given full knowledge of the observed causal graph, under similar modelling assumptions to L&B. While the conditions do not improve the number of test interventions needed in worst-case scenario, they can offer super-exponential speedup in other scenarios. The authors provide a finite sample POMIS-discovery algorithm with coverage guarantees of the true set of POMISs and derive regret upper bounds. Experiments, particularly figure 2, show a clear (regret) advantage over learning all latent confounders in a setting with random, triangulated DAGs.

Strengths

The authors present their contributions clearly, logically covering their motivation, theoretical results, algorithmic design, coverage guarantees, regret upper bounds, experimental design and experimental results. It is clear how their approach works in conjunction with other stages such as learning the observable graph and regret minimisation with the full set of POMISs. Experiments convincingly show the advantage of partial structure discovery over testing for all latent confounding in a class of random DAGs.

Weaknesses

(Latent structure assumption) A key modelling assumption, retained from L&B, is that latent variables are mutually independent and confound only a pair of measured variables each. This modelling assumption (why is it necessary? how restrictive is it mathematically? in what real-world setting could it be relevant?) was not sufficiently explored in L&B or by the authors. The assumption is especially relevant to the impact of the authors' contributions so should be discussed more thoroughly in the text.

Questions

(Latent structure assumption) What is the role of the assumed structure on latent confounding in your results and how restrictive actually are these assumptions? Can these assumptions be relaxed to some degree, say if latent confounders are allowed to confound up to n (e.g., 3) observed variables, or have bounded pairwise correlation? Is it permitted for three vertices $(V_1, V_2, V_3)$ to be confounded pairwise, i.e., for confounding between $(V_1, V_2)$, $(V_2,V_3)$ and $(V_1, V_3)$? Are the graphs generated for the simulation experiments - i.e., after triangulation - typically dense or sparse? Is this an important factor to understand the advantage of your method over learning all latent confounders? Perhaps a parameter sweep over $\rho$ and $\rho_L$, i.e., a property of the observed versus unobserved graphs, could be informative to this end. Was the triangulated structure of the observed graph important for your results?

Rating

6

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes - the authors state all underlying assumptions of their model. I would like to understand whether the latent structure assumption is limiting for real-world applications.

Reviewer MSdE7/10 · confidence 3/52024-07-13

Summary

This paper ooks into the problem of causal bandits without graph information and with unobserved variables. The paper presents both graph learning algorithms and causal bandit algorithms.

Strengths

This paper tackles the novel problem of causal bandits (CB) with unknown graphs and unobserved variables. Theorem 3.1 is particularly interesting, and the use of a randomized algorithm to sample-efficiently learn the causal graphs is notable.

Weaknesses

There are a few typos in the paper: - For the definition of transitive reduction, does it force $\mathcal{G}$ to be connected? Otherwise, the empty edge set is minimum. - For the d-separation defined in line 119, shouldn't it condition on $\mathbf{W}$? - Assumption 2.1 is defined on a mixture of hard intervention and stochastic intervention (in line 126)? - Line 4 in Algorithm 2, should it be $\mathcal{W}=\emptyset$?

Questions

- How is transitive reduction computed in Algorithm 2? Does it need to exhaust all possible sub-graphs? - Correct me if I am wrong: In Assumption 4.1 and Assumption 4.2, the assumption is made for **any** $\mathbf{w}\in [K]^{\mathbf{W}}$, which is stronger than the other causal bandit papers, e.g. [7], [9]. - For Algorithm 3, line 4, how is the set $\mathbf{W}$ determined as it is neither an input nor the output of LearnObservableGraph? Te $\mathbf{W}$ matrices in $\mathcal{I}Data$ does not share the same $\mathbf{W}$, and and line 6 seems to attempt to find $\mathbf{W}$.

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

4

Limitations

The paper assumes semi-Markovian causal models and stronger identification assumptions.

Reviewer FQKc2024-08-11

Thank you for your response. Regarding the comparison with Classic UCB, I understand that your algorithm reduces the action space before applying UCB. However, this typically incurs a cost (as reflected in the first four terms of your regret bound). My question was: under which graph structures and parametric assumptions (i.e., $\epsilon$ and $\gamma$) would it be preferable to skip causal discovery and apply only classic UCB? Could you discuss this?

Reviewer VRJg2024-08-12

Many thanks for the clarification and extended experiments. I maintain my score for a weak accept.

Authorsrebuttal2024-08-12

Re.

We thank the reviewer for their insightful comments and suggestions. We will include the extended experiments in the main paper following the reviewer's suggestion. We are also grateful to the reviewer for recommending acceptance of our work.

Reviewer MSdE2024-08-12

Thanks the the response and I also read the other insightful discussions. I believe it is a solid paper that contributes to the field and I'd like to raise the score from 6 to 7.

Authorsrebuttal2024-08-12

Re.

We thank the reviewer for their insightful comments and suggestions. We are also grateful to the reviewer for appreciating our work and increasing the score.

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC