Technical Summary: Graph Learning Is Suboptimal in Causal Bandits

Problem Statement

This paper investigates the problem of regret minimization in causal bandits under the assumption of causal sufficiency (no unobserved confounders), where the underlying causal graph structure is unknown to the agent. In this setting, an agent sequentially selects actions defined by interventions on subsets of variables (of size at most $m$) to maximize cumulative reward. The reward is determined by a specific node $Y$ in a Directed Acyclic Graph (DAG) over $n$ variables.

Prior literature has largely operated under the assumption that identifying the set of parents of the reward node ($Pa_Y$) is a necessary precursor to effective learning. Strategies typically involve a two-phase approach: first discovering the parent set (often via structural learning or sequential search), and then applying standard bandit algorithms (like UCB) restricted to interventions on these parents. Alternatively, some works attempt to learn parents and minimize regret simultaneously.

The central question addressed by this work is: Is identifying the parent set of the reward node a necessary or optimal strategy for minimizing cumulative regret?

Methodology and Theoretical Framework

1. The Trade-off Between Identification and Regret

The authors first establish a fundamental theoretical conflict between the objectives of parent identification and regret minimization.

• Construction of Counter-Examples: They construct a specific subclass of instances ($\mathcal{E}_0$) where the set of high-reward actions is disjoint from the set of actions that provide information about the parent set.
• Theorem 3.2 (Identification-Regret Trade-Off): The paper proves that for any policy that achieves exponentially low error rates in identifying the parent set (i.e., $\delta_T \in O(\exp(-T^\alpha))$), the cumulative regret must grow as $\Omega(T^\alpha)$. Conversely, achieving optimal regret rates precludes high-probability identification of the parent set.
• Implication: In worst-case scenarios, an agent cannot simultaneously learn the causal structure and minimize regret efficiently. The "informative" actions required to distinguish the true parent set often incur high regret, while the "optimal" actions provide no structural information.

2. Regret Lower Bounds

The authors derive novel information-theoretic lower bounds on the worst-case regret, which hold even if the agent has complete knowledge of the causal graph over non-reward variables ($G$). This demonstrates that knowledge of the graph structure (excluding the specific parent set of the reward) does not improve worst-case regret guarantees.

• Known Parent Size ($k$):
  • Case $m \ge k$: The lower bound is $\Omega\left(\sqrt{T \max\left(\frac{(\ell-1)^k \binom{n}{k}}{\binom{m}{k}}, \ell^k\right)}\right)$.
  • Case $m < k$: The lower bound is $\Omega\left(\sqrt{T \max\left((\ell-1)^m \binom{n}{m}, \ell^m\right)}\right)$.
  • These bounds capture the combinatorial complexity of the action space and show that the difficulty arises from the uncertainty of which subset of size $k$ constitutes the parents, not from the graph topology itself.
• Unknown Parent Size ($k$):
  • The paper establishes a lower bound on the product of regrets for different parent sizes ($k_1$ and $k_2$), proving that no single algorithm can uniformly achieve the optimal regret rates for all possible values of $k$. This necessitates a trade-off in performance across different problem instances.

3. Proposed Algorithms

Bypassing the need for explicit graph recovery, the authors propose two algorithms that achieve near-optimal regret bounds:

• Algorithm 1 (Known $k$):

  • Mechanism: Instead of learning the graph, the algorithm randomly samples a subset of actions ($A'$) from the space of all interventions of size $m$. The size of this subset is carefully chosen to ensure, with high probability, that it contains at least one optimal action.
  • Execution: It then runs a standard Upper Confidence Bound (UCB) algorithm exclusively on this reduced subset $A'$.
  • Performance: It achieves regret matching the derived lower bounds up to logarithmic factors, without requiring knowledge of the graph $G$ or the specific parent set.

• Algorithm 2 (Unknown $k$):

  • Mechanism: Designed to adapt to an unknown number of parents, this algorithm operates in phases. In each phase, it samples a random subset of actions, runs UCB, and constructs a "mixture arm" (a randomized action based on the empirical distribution of the phase).
  • Adaptivity: The phase length and sample size are adjusted dynamically (halving the sample size, doubling the phase length) to balance exploration across different potential parent set sizes.
  • Performance: The algorithm is shown to be rate-Pareto optimal. This means its regret vector (performance across all possible $k$) cannot be strictly dominated by any other policy; it achieves the best possible trade-off between performance on instances with small $k$ and large $k$.

Key Results and Contributions

1. Suboptimality of Graph Learning: The paper rigorously proves that learning the parent set is suboptimal for regret minimization in the worst-case setting. There exist instances where the objectives of structure learning and regret minimization are fundamentally conflicting.
2. Novel Lower Bounds: The authors provide the first lower bounds for causal bandits with unknown graphs that explicitly account for the combinatorial structure of the action space. Crucially, these bounds apply even when the agent knows the full graph $G$ (except for the reward's parents), proving that structural knowledge alone is insufficient to bypass the hardness of the problem.
3. Near-Optimal Algorithms:
   • For known $k$, the proposed algorithm achieves regret $\tilde{O}\left(\sqrt{T \ell^k \binom{n}{k} / \binom{m}{k}}\right)$, which matches the lower bound.
   • For unknown $k$, the adaptive algorithm achieves a regret vector that is Pareto optimal, effectively handling the uncertainty of $k$ without prior knowledge.
4. Empirical Validation: Experiments on synthetic Erdős–Rényi graphs demonstrate that the proposed methods (EmpKnownUCB+ and EmpUnknownUCB+) significantly outperform existing baselines, including:
   • RAPS: A state-of-the-art method that explicitly learns parents before minimizing regret.
   • Standard UCB: Applied to the full action space.
   • The proposed methods reduce regret by up to a factor of 20 compared to baselines, particularly in settings where the parent identification phase of RAPS would consume excessive resources.

Significance and Claims

The paper claims a paradigm shift in the approach to causal bandits with unknown structures. It argues that explicit causal discovery is unnecessary for achieving optimal regret rates. By demonstrating that structure learning and regret minimization can be conflicting objectives, the work suggests that algorithms should focus directly on the reward landscape rather than attempting to reconstruct the underlying causal graph.

The authors emphasize that their results hold under no distributional assumptions (e.g., linearity) and for hard interventions. They note that while structural information (the graph $G$) does not improve worst-case regret bounds, the proposed algorithms achieve these bounds without needing such information. The work concludes that for worst-case regret minimization, "bypassing graph and parent recovery" is not only viable but superior to traditional two-stage approaches.

Future work, as suggested by the authors, involves characterizing settings where these objectives might align, or investigating specific distributional assumptions that could allow for simultaneous optimization of structure learning and regret.