Graph Learning is Suboptimal in Causal Bandits

Mohammad Shahverdikondori, Jalal Etesami, Negar Kiyavash
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3088-3096, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-shahverdikondori26a, title = { Graph Learning is Suboptimal in Causal Bandits }, author = {Shahverdikondori, Mohammad and Etesami, Jalal and Kiyavash, Negar}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3088--3096}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/shahverdikondori26a/shahverdikondori26a.pdf}, url = {https://proceedings.mlr.press/v300/shahverdikondori26a.html}, 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. } }
Endnote
%0 Conference Paper %T Graph Learning is Suboptimal in Causal Bandits %A Mohammad Shahverdikondori %A Jalal Etesami %A Negar Kiyavash %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-shahverdikondori26a %I PMLR %P 3088--3096 %U https://proceedings.mlr.press/v300/shahverdikondori26a.html %V 300 %X 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.
APA
Shahverdikondori, M., Etesami, J. & Kiyavash, N.. (2026). Graph Learning is Suboptimal in Causal Bandits . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3088-3096 Available from https://proceedings.mlr.press/v300/shahverdikondori26a.html.

Related Material