2025-01-14-feng25a.md

title	Combinatorial Causal Bandits without Graph Skeleton
booktitle	Proceedings of the 16th Asian Conference on Machine Learning
year	2025
volume	260
series	Proceedings of Machine Learning Research
month	0
publisher	PMLR
pdf	https://raw.githubusercontent.com/mlresearch/v260/main/assets/feng25a/feng25a.pdf
url	https://proceedings.mlr.press/v260/feng25a.html
openreview	OOpOpCzsuU
abstract	In combinatorial causal bandits (CCB), the learning agent chooses a subset of variables in each round to intervene and collects feedback from the observed variables to minimize expected regret or sample complexity. Previous works study this problem in both general causal models and binary generalized linear models (BGLMs). However, all of them require prior knowledge of causal graph structure or unrealistic assumptions. This paper studies the CCB problem without the graph structure on binary general causal models and BGLMs. We first provide an exponential lower bound of cumulative regrets for the CCB problem on general causal models. To overcome the exponentially large space of parameters, we then consider the CCB problem on BGLMs. We design a regret minimization algorithm for BGLMs even without the graph skeleton and show that it still achieves $O(\sqrt{T}\ln T)$ expected regret, as long as the causal graph satisfies a weight gap assumption. This asymptotic regret is the same as the state-of-art algorithms relying on the graph structure. Moreover, we propose another algorithm with $O(T^{\frac{2}{3}}\ln T)$ regret to remove the weight gap assumption.
layout	inproceedings
issn	2640-3498
id	feng25a
tex_title	Combinatorial Causal Bandits without Graph Skeleton
firstpage	271
lastpage	286
page	271-286
order	271
cycles	false
bibtex_editor	Nguyen, Vu and Lin, Hsuan-Tien
editor	given family Vu Nguyen given family Hsuan-Tien Lin
bibtex_author	Feng, Shi and Xiong, Nuoya and Chen, Wei
author	given family Shi Feng given family Nuoya Xiong given family Wei Chen
date	2025-01-14
address
container-title	Proceedings of the 16th Asian Conference on Machine Learning
genre	inproceedings
issued	date-parts 2025 1 14
extras	label link Supplementary PDF https://raw.githubusercontent.com/mlresearch/v260/main/assets/assets/feng25a/feng25a-supp.pdf