Combinatorial Pure Exploration of Causal Bandits
Authors: Nuoya Xiong, Wei Chen
ICLR 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide the first gap-dependent and fully adaptive pure exploration algorithms on two types of causal models the binary generalized linear model (BGLM) and general graphs. For BGLM, our algorithm is the first to be designed specifically for this setting and achieves polynomial sample complexity, while all existing algorithms for general graphs have either sample complexity exponential to the graph size or some unreasonable assumptions. For general graphs, our algorithm provides a significant improvement on sample complexity, and it nearly matches the lower bound we prove. Our algorithms achieve such improvement by a novel integration of prior causal bandit algorithms and prior adaptive pure exploration algorithms, the former of which utilize the rich observational feedback in causal bandits but are not adaptive to reward gaps, while the latter of which have the issue in reverse. Due to the space constraint, further materials including experimental results, an algorithm for the fixed-budget setting, and all proofs are moved to the appendix. |
| Researcher Affiliation | Collaboration | Nuoya Xiong Institute for Interdisciplinary Information Sciences, Tsinghua University Beijing, China xiongny20@mails.tsinghua.edu.cn Wei Chen Microsoft Research Beijing, China weic@microsoft.com |
| Pseudocode | Yes | Algorithm 1 CCPE-BGLM(G, A, ε, δ, M (1), M (2), κ, η, c) ... Algorithm 2 BGLM-estimate ... Algorithm 3 CCPE-General(G, A, ε, δ) |
| Open Source Code | No | The paper does not provide a link to open-source code for the methodology or state that it is being released. It only mentions that experimental results, an algorithm for the fixed-budget setting, and proofs are moved to the appendix. |
| Open Datasets | No | The main body of the paper is theoretical and does not describe the use of any specific datasets for training or provide access information for them. It mentions that experimental results are moved to the appendix, but does not provide details in the main text. |
| Dataset Splits | No | The main body of the paper is theoretical and does not provide any dataset split information (training, validation, test). It mentions that experimental results are moved to the appendix, but does not provide details in the main text. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used for experiments. |
| Software Dependencies | No | The paper does not provide specific version numbers for any software dependencies. |
| Experiment Setup | No | The paper does not provide specific details about the experimental setup, such as hyperparameters or training configurations. |