TL;DR
Most causal bandit algorithms assume the underlying causal graph is known upfront, but learning the entire graph requires an expensive number of interventions. This paper introduces the RAndomized Parent Search (RAPS) algorithm, which directly identifies the direct parents of the reward variable without learning the rest of the graph, achieving provably optimal sublinear (and often logarithmic) intervention complexity.
What Problem Does This Paper Address?
In causal multi-armed bandits (MAB), actions are interventions on variables in a Directed Acyclic Graph (DAG) aimed at maximizing a designated reward node $R$. When the causal graph is known, the optimal intervention is simply the best configuration of the direct parents of $R$, denoted $\mathcal{P}$.
However, in real-world scenarios, the causal graph is rarely known. Fully recovering a DAG or its essential graph typically requires an intractable number of conditional independence tests or interventions. The authors ask: Can a learner bypass full graph learning and discover only the parent set $\mathcal{P}$ using a minimal, sublinear number of atomic interventions?
Methods
The authors introduce RAPS (RAndomized Parent Search):
- Divide-and-Conquer Search: Starting with the candidate set of all nodes $C = \mathcal{V}$, RAPS randomly samples a node $X \in C$ and intervenes on it.
- Descendant and Ancestor Pruning: Using statistical hypothesis tests on the interventional distribution versus the observational distribution:
- If intervening on $X$ changes the distribution of $R$, $X$ is identified as an ancestor of $\mathcal{P}$. The candidate set is pruned to descendants of $X$ ($D_C(X) \setminus \{X\}$).
- If $R$ does not change, $X$ is not an ancestor of $\mathcal{P}$. All descendants of $X$ ($D_C(X)$) can be safely pruned from $C$.
- Extension to Multiple Parents: Algorithm 2 generalizes RAPS by iteratively discovering parents in reverse topological order while conditioning on previously identified parents.
- Bandit Regret Minimization: Once $\mathcal{P}$ is identified, standard Upper Confidence Bound (UCB) runs exclusively over the $K^{|\mathcal{P}|}$ configurations of the parent set, rather than the exponential $K^n$ combinatorial action space.
Datasets
The authors evaluate their approach on synthetic probabilistic causal models (PCMs):
- Directed Binary Trees: Trees with $n = 20$ nodes where nodes propagate their parent's binary value with probability $0.9$ (and random noise with probability $0.1$).
- Erdős–Rényi Random DAGs: Random DAGs generated over $n = 10$ to $n = 1000$ vertices across varying edge connection probabilities $p$.
- No real-world datasets were used in this work.
Key Insights and Ideas
-
Exact Closed-Form Complexity: The authors prove the exact expected number of interventions to find a single parent $P$: $$\mathbb{E}[N(\mathcal{G}, P)] = \sum_{X \in \mathcal{V}} \frac{1}{|A(P) \Delta A(X) \cup \{X\}|}$$ where $A(\cdot)$ denotes the ancestor set and $\Delta$ represents the symmetric difference.
-
Universal Optimality: Using Yao’s minimax principle, the authors prove a matching universal lower bound, establishing that RAPS is minimax optimal for learners using atomic interventions.
- Two Operating Regimes:
- Fast Regime ($O(\log^k n)$): Achieved when candidate subgraphs contain sufficiently dense ancestor sets or "heavy" non-ancestor branches (e.g., Erdős–Rényi DAGs with edge probability $p \ge \Theta\left(\frac{k \log \log n}{\log^k n}\right)$).
- Slow Regime ($O(n / \log_d n)$): Achieved under milder connectivity assumptions (such as $d$-ary directed trees), still strictly sublinear compared to naive $\Omega(n)$ exploration.
Key Results
-
Cumulative Regret Bound: With probability at least $1 - \delta$, the combined RAPS + UCB algorithm achieves conditional cumulative regret bounded by: $$R^T \le \max\left\{\frac{1}{\Delta^2}, \frac{1}{\varepsilon^2}\right\} K^{|\mathcal{P}|+1} \mathbb{E}[N(\mathcal{G}, \mathcal{P})] \log\left(\frac{n K^n}{\delta}\right) + \sum_{x \in [K]^{|\mathcal{P}|}} \Delta_{\mathcal{P}=x} \left(1 + \frac{\log T}{\Delta^2_{\mathcal{P}=x}}\right)$$ Crucially, the second term depends only on $K^{|\mathcal{P}|}$ rather than $K^n$.
-
Empirical Validation:
- On 20-node binary trees ($T = 10^7$ rounds, 1 to 3 reward parents), RAPS + UCB significantly outperformed standard UCB in cumulative regret.
- On Erdős–Rényi DAGs ($n = 1000$), empirical intervention counts precisely matched the theoretical formula, scaling logarithmically for dense graphs and sublinearly ($n / \log n$) for sparse graphs.
Limitations and Future Work
- Sample Complexity Dependency: The intervention budget per candidate node scales with $1/\min\{\varepsilon, \Delta\}^2$, where $\varepsilon$ and $\Delta$ measure minimal distributional effect sizes. When these gaps decay rapidly with graph size $n$, RAPS exhibits high empirical variance.
- Phased vs. Integrated Exploration: The algorithm operates in two disjoint phases (parent discovery first, UCB optimization second). The authors note that simultaneously allocating pulls proportionally to reward gaps while discovering parents is an important direction for future work.
- Global Ancestral Identifiability: Assumption 1 assumes observable effects between any ancestor-descendant pair; relaxing this to bounded-length local paths remains open.
Summary updated