Causal Bandits with Unknown Graph Structure
Authors: Yangyi Lu, Amirhossein Meisami, Ambuj Tewari
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we develop novel causal bandit algorithms without knowing the causal graph. Our algorithms work well for causal trees, causal forests and a general class of causal graphs. The regret guarantees of our algorithms greatly improve upon those of standard multi-armed bandit (MAB) algorithms under mild conditions. Lastly, we prove our mild conditions are necessary: without them one cannot do better than standard MAB algorithms.Theoretically, we show under certain identifiability assumptions, the regret of our algorithm only scales logarithmically with the number of nodes n in the causal graph. To our knowledge, this is the first regret guarantee for unknown causal graph that provably outperforms standard MAB algorithms.Lastly, we provide lower bound results to justify the necessity of our assumptions on the causal effect identifiability and the reward identifiability. |
| Researcher Affiliation | Collaboration | Yangyi Lu Department of Statistics University of Michigan yylu@umich.eduAmirhossein Meisami Adobe Inc. meisami@adobe.comAmbuj Tewari Department of Statistics University of Michigan tewaria@umich.edu |
| Pseudocode | Yes | Algorithm 1 Central Node Upper Confidence Bound (CN-UCB) |
| Open Source Code | No | The paper does not provide any specific links to source code repositories nor an explicit statement about releasing the code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not present experiments that involve training on a specific dataset. Thus, no concrete access information for a publicly available or open dataset is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments that would require specific dataset split information (training/validation/test) for reproducibility. |
| Hardware Specification | No | The paper is theoretical and does not report on computational experiments that would require specific hardware details. No mention of CPU, GPU, or other hardware specifications was found. |
| Software Dependencies | No | The paper is theoretical and does not provide specific software dependency details with version numbers (e.g., Python 3.8, PyTorch 1.9, CPLEX 12.4) required to replicate any experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, therefore, it does not provide specific experimental setup details such as hyperparameter values, training configurations, or system-level settings. |