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.
| Comments: | 32 pages, accepted at AISTATS 2026 |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2510.16811 [cs.LG] |
| (or arXiv:2510.16811v3 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2510.16811 arXiv-issued DOI via DataCite |
From: Mohammad Shahverdikondori [view email]
[v1]
Sun, 19 Oct 2025 12:34:27 UTC (1,463 KB)
[v2]
Tue, 30 Dec 2025 13:55:02 UTC (1,463 KB)
[v3]
Thu, 7 May 2026 14:57:22 UTC (1,430 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。