Graph Learning is Suboptimal in Causal Bandits
This work addresses a fundamental issue in causal bandits for researchers and practitioners, revealing that existing graph-learning strategies are not optimal, which is incremental but impactful for algorithm design.
The paper tackles the problem of regret minimization in causal bandits with unknown causal structure, showing that learning the parent set is suboptimal because it conflicts with regret minimization, and proposes algorithms that bypass graph recovery to achieve near-optimal performance, with experiments confirming a large performance gap over baselines.
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.