Graph Learning Is Suboptimal in Causal Bandits

AI summary

Overview

Research area: Causal bandits — sequential decision-making where the arms correspond to interventions on a causal graph, combining causal inference with multi-armed bandit theory.

Technical level: Advanced. The paper is a theory paper built on regret lower bounds, combinatorial counting arguments, and Pareto-optimality notions; the prose is accessible but the results are stated in information-theoretic form.

Scope (one sentence): The paper asks whether the standard causal-bandit strategy of first identifying the parents of the reward node and then running a bandit algorithm is optimal, and answers no by proving that parent identification and regret minimization can be conflicting objectives.

What This Paper Is About

In a causal bandit, an agent intervenes on subsets of variables in a causal graph and observes a reward node (plus the non-intervened variables). A large body of prior work assumes the graph is unknown and proceeds in two steps: identify the parents of the reward node, then apply a classic bandit algorithm to the identified parent set. This paper asks whether that two-step recipe is actually the right thing to do. The authors show that for hard interventions, under causal sufficiency (no unobserved variables), and with no distributional assumptions, learning the parent set is suboptimal: there are instances where the actions that earn high reward and the actions that reveal the parents are disjoint sets, so any algorithm that identifies parents efficiently must pay for it in regret.

Key Contributions

1. A trade-off theorem separating regret minimization from parent identification. The authors construct a class of instances in which regret minimization and parent identification are fundamentally at odds, and prove that any policy whose parent-misidentification probability decays as O(exp(−T^α)) must incur worst-case regret of Ω(T^α). Setting α = 1 — matching what uniform sampling achieves — implies linear regret.
2. Novel regret lower bounds in both the m ≥ k and m < k regimes when k is known. These bounds capture the combinatorial structure of the action space and hold even when the agent has complete knowledge of the causal graph over the non-reward variables, for any such graph.
3. A nearly optimal algorithm (Algorithm 1) that never recovers the graph or the parents. With knowledge of only k, it samples a uniformly random subset of the size-m intervention actions, sized to contain an optimal action with high probability, and runs standard UCB on that subset. It matches the lower bounds up to logarithmic factors when ℓ ∈ Ω(k).
4. An adaptive algorithm (Algorithm 2) for unknown k, proven near rate-Pareto optimal. With no prior knowledge at all (information set ℐ = {}), it adapts across all parent-set sizes, and is rate-Pareto optimal up to logarithmic factors when the agent can intervene on all variables each round (m = n); in the general case it is Pareto optimal up to a multiplicative gap of m/n.
5. Experiments showing a large gap to baselines, with regret reduced by up to a factor of 20 across environments.

Main Findings

• Parent identification is suboptimal for regret minimization. Under causal sufficiency and with no assumptions on the generating model, no algorithm achieving the optimal regret rate can simultaneously identify the parent set with high probability. The intuition: in the constructed instance, the unique high-reward action sets the first k variables to 1, which simultaneously forces all other variables to 1, so it reveals nothing about which variables actually influence the reward; identifying the parents instead requires playing suboptimal actions that incur regret.

• The trade-off is absent for simple regret. The authors contrast their result with the simple-regret objective, for which it is established that no fundamental trade-off with cumulative regret exists — algorithms optimal for cumulative regret can be optimal for simple regret up to constant factors.

• The trade-off weakens under a non-degeneracy condition. If every variable takes any value with probability at least ε > 0 under any parent configuration, then in the regime T ≫ 1/ε a learner playing the optimal action still observes alternative configurations "for free," which can reveal that those variables do not affect the reward. The authors state that the trade-off would then be weaker, and that the degenerate construction is used intentionally to make the phenomenon clear.

• Known-k lower bound (m ≥ k). For any policy π ∈ Π({k, 𝒢}), any n ≥ m ≥ k, and any causal graph 𝒢: R_T(π, ℰ) ∈ Ω( sqrt( T · max( (ℓ−1)^k · binom(n,k)/binom(m,k), ℓ^k ) ) ). The bound holds even with full knowledge of 𝒢.

• Known-k lower bound (m < k). For any π ∈ Π({k, 𝒢}) and n ≥ k > m: R_T(π, ℰ) ∈ Ω( sqrt( T · max( (ℓ−1)^m · binom(n,m), ℓ^m ) ) ). Since ℓ^m · binom(n,m) is exactly the number of actions in 𝒜_m, no algorithm can beat a standard UCB over 𝒜_m in this regime.

• Lower bounds hold despite graph knowledge. Both bounds remain valid under the additional assumption that the agent knows 𝒢, the causal graph over the non-reward variables — so knowing 𝒢 does not improve worst-case regret guarantees.

• Algorithm 1 is optimal up to logarithmic factors. Its regret is Õ( sqrt( T · ℓ^k · binom(n,k)/binom(m,k) ) ) for m ≥ k and Õ( sqrt( T · ℓ^m · binom(n,m) ) ) for m < k. When ℓ ∈ Ω(k), these match the lower bounds. It requires only k, not 𝒢.

• With m = n, full graph knowledge gives no advantage. The lower and upper bounds match up to logarithmic factors at Õ( sqrt(T · ℓ^k) ), which is exactly the regret of an agent who knows Pa_Y and runs standard regret minimization over the ℓ^k possible arms. As the authors put it, the regret with full knowledge of the graph (including the parents) equals that with no knowledge when the agent can intervene on all variables each round.

• Unknown k forces a penalty. For any graph 𝒢, any policy π ∈ Π(𝒢), and any n ≥ m ≥ k₂ > k₁, the product of regrets satisfies R_T(π, ℰ(n,ℓ,k₁)) × R_T(π, ℰ(n,ℓ,k₂)) ∈ Ω( T · max( (ℓ−1)^{k₂} · binom(n−k₁, k₂−k₁)/binom(m−k₁, k₂−k₁), ℓ^{k₂} ) ). Improving performance at one parent size necessarily worsens it at a larger one.

• Algorithm 2 adapts to unknown k. Its regret is Õ( sqrt(T · m/n) · ℓ^{k−1/2} · binom(n,k)/binom(m,k) ) for m ≥ k and Õ( sqrt(T · m/n) · ℓ^{m−1/2} · binom(n,m) ) for m < k. It needs neither 𝒢 nor k.

• Algorithm 2 is near rate-Pareto optimal. When m = n it is rate-Pareto optimal for Π(𝒢) up to logarithmic factors. In the general case with ℓ ∈ Ω(m), a modified regret vector (with entries scaled by m/n for k ≥ 2) is rate-Pareto optimal for Π(𝒢), and up to logarithmic terms coincides with Algorithm 2's regret vector at k = 1.

• Even with unknown k, knowing the graph 𝒢 does not help much. The lower bound applies to any policy in Π({𝒢}), while Algorithm 2 works without knowledge of 𝒢 yet stays close to Pareto optimal within that class.

• Empirical gap. Experiments report that the proposed methods outperform existing baselines and reduce regret by up to a factor of 20. The truncated text shows average regret over time for action sizes m = 3 and m = 6, using Erdős–Rényi random graphs with edge probability p = 2/n and a binary reward whose mean is chosen uniformly at random from [0,1] for each possible combination of parents. Full experimental details beyond this point are not included in the available content.

Methodology in Plain English

The paper is theoretical. The authors first formalize the causal bandit with fixed-size interventions: n variables each taking values in [ℓ], a reward node with k parents, hard interventions on at most m variables, and 1-sub-Gaussian rewards with means in [0,1]. They define regret as the cumulative gap between the optimal action's expected reward and the played actions'. They note a useful structural fact — under causal sufficiency, there is always an optimal action among the interventions of maximum size m.

To show that graph learning is suboptimal, they build a deliberately degenerate instance: n binary variables, each equal to 0 unless intervened upon, the first k variables are parents of all the others, and setting all k of them to 1 makes every remaining variable 1 deterministically. The reward has mean 0 for every action except the one setting the first k variables to 1, which yields expected reward 1. In this instance, the single high-reward action is uninformative about the parent set, and the informative actions are suboptimal — so the two objectives pull in opposite directions. They then prove a lower bound that quantifies this: a policy with parent-misidentification error O(exp(−T^α)) pays Ω(T^α) regret.

For the known-k setting, instead of assuming a particular graph or distribution, they take a worst-case information-theoretic route: fix a neutral instance (empty graph, reward always N(0,1)), track how often a policy visits each (subset, value assignment) pair, and maximize over candidate sub-collections of size k+1 to obtain the bounds. The upper bounds come from a simple algorithm: pick a random subset of size-m actions just large enough to contain an optimal action with high probability (a counting/combinatorial argument), then run standard UCB on it.

For the unknown-k setting, they change the performance measure to a regret vector indexed by k, define rate-Pareto domination and optimality, and prove a product lower bound across two parent sizes. The adaptive algorithm borrows a phasing idea from the literature on bandits with multiple optimal arms: in each phase it draws a random subset of arms, halves the subset size and doubles the phase length over time, runs UCB, and compresses each phase's exploration into a single "mixture arm" that is carried forward.

Why This Matters

Impact on research. This is a negative result with constructive consequences: it closes off a natural research direction (causal discovery then bandits) as a route to optimal regret, and it supplies lower bounds that hold even with graph knowledge, effectively relocating the value of prior knowledge from the graph structure to the parent set — and then showing that even the parent set need not be recovered to attain near-optimal regret. It also puts causal bandits under the same lens as the broader question of which exploration objectives conflict with cumulative regret.

Real-world applications:

• Recommendation systems, where interventions correspond to forcing item exposure and the reward is a user response.
• Clinical trials, where treatments can be assigned and outcomes measured on patients.
• A/B testing, where an experimenter manipulates a set of configuration variables and measures a conversion metric.
• Sequential decision-making in structured environments generally, including any setting where the experimenter can intervene on only a limited number of variables per round.

Industry relevance. The practical message is that practitioners with a limited intervention budget do not need to spend rounds on causal discovery or parent identification. They can sample a random subset of the maximum-size interventions and run an off-the-shelf UCB algorithm on it, and — when m = n — knowing the full graph, including the reward's parents, buys nothing in the worst case. The reported regret reduction of up to a factor of 20 against existing baselines is the concrete argument for adopting these methods.

Future Directions

• Non-degenerate models. The paper's construction is intentionally degenerate, and the authors state that establishing similar lower bounds for non-degenerate models would require more involved constructions and might yield a weaker trade-off. Quantifying that weaker trade-off is an open task.
• Other classes of interventions. The authors explicitly note that their results are specific to hard interventions, and that conclusions may not directly extend to interventions that modify conditional distributions (soft interventions).
• Closing the Pareto gap in the general unknown-k case. Algorithm 2 is exactly rate-Pareto optimal only when m = n; in the general case the guarantee holds up to a multiplicative gap of m/n for larger k, leaving room for tighter results or improved algorithms.
• Learning the graph versus minimizing regret as an explicit objective. Since the paper shows regret minimization does not require parent recovery, an open question is what, if anything, the extra observational and interventional data observed under the causal bandit protocol is useful for beyond the reward.

Target Audience

Researchers and graduate students in machine learning theory, causal inference, and sequential decision-making who work on bandit algorithms, causal bandits, or the sample complexity of causal discovery. It is also relevant to practitioners who deploy bandit-style experimentation on systems with known or partially known causal structure and who currently allocate exploration budget to learning that structure, and to anyone interested in the general question of when pure-exploration objectives conflict with cumulative regret.

Authors’ abstract

We study regret minimization in causal bandits under causal sufficiency where the underlying causal structure is not known to the agent. Previous work has focused on identifying the reward's parents and then applying classic bandit methods to them, or jointly learning the parents while minimizing regret. We investigate whether such strategies are optimal. Somewhat counterintuitively, our results show that learning the parent set is suboptimal. We do so by proving that there exist instances where regret minimization and parent identification are fundamentally conflicting objectives. We further analyze both the known and unknown parent set size regimes, establish novel regret lower bounds that capture the combinatorial structure of the action space. Building on these insights, we propose nearly optimal algorithms that bypass graph and parent recovery, demonstrating that parent identification is indeed unnecessary for regret minimization. Experiments confirm that there exists a large performance gap between our method and existing baselines in various environments.