Causal Bandits without Graph Learning

Mikhail Konobeev, Jalal Etesami, Negar Kiyavash
1/26/2023
stat.MLcs.LG

No official code found. Best implementation: BorealisAI/raps (3 stars, last commit 2023-05-26).

Abstract

We study the causal bandit problem when the causal graph is unknown and develop an efficient algorithm for finding the parent node of the reward node using atomic interventions. We derive the exact equation for the expected number of interventions performed by the algorithm and show that under certain graphical conditions it could perform either logarithmically fast or, under more general assumptions, slower but still sublinearly in the number of variables. We formally show that our algorithm is optimal as it meets the universal lower bound we establish for any algorithm that performs atomic interventions. Finally, we extend our algorithm to the case when the reward node has multiple parents. Using this algorithm together with a standard algorithm from bandit literature leads to improved regret bounds.

View on arXivView PDF

Code Implementations(1)

BorealisAI/rapsCommunity100%

Code for the paper "Causal Bandits without Graph Learning"

30Shell, PythonMay 24, 20233 years agoNOASSERTION
bandit-algorithmscausality

Similar Papers

Graph Learning is Suboptimal in Causal Bandits

91% match2025

Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits

91% match2024

Additive Causal Bandits with Unknown Graph

90% match1 repo52023

Learning Good Interventions in Causal Graphs via Covering

89% match2023

Asymmetric Graph Error Control with Low Complexity in Causal Bandits

89% match2024

Linear Causal Bandits: Unknown Graph and Soft Interventions

88% match1 repo2024

Cite this paper

@article{konobeev2023causal,
  title  = {Causal Bandits without Graph Learning},
  author = {Mikhail Konobeev and Jalal Etesami and Negar Kiyavash},
  year   = {2023},
  eprint = {2301.11401},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2301.11401v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2301.11401.svg)](https://codeofpaper.com/paper/2301.11401)

Discussion