Learning Good Interventions in Causal Graphs via Covering Article Swipe

MAKE IMPACT

Ayush Sawarni , Rahul Madhavan , Gaurav Sinha , Siddharth Barman · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2305.04638

We study the causal bandit problem that entails identifying a near-optimal intervention from a specified set $A$ of (possibly non-atomic) interventions over a given causal graph. Here, an optimal intervention in ${A}$ is one that maximizes the expected value for a designated reward variable in the graph, and we use the standard notion of simple regret to quantify near optimality. Considering Bernoulli random variables and for causal graphs on $N$ vertices with constant in-degree, prior work has achieved a worst case guarantee of $\widetilde{O} (N/\sqrt{T})$ for simple regret. The current work utilizes the idea of covering interventions (which are not necessarily contained within ${A}$) and establishes a simple regret guarantee of $\widetilde{O}(\sqrt{N/T})$. Notably, and in contrast to prior work, our simple regret bound depends only on explicit parameters of the problem instance. We also go beyond prior work and achieve a simple regret guarantee for causal graphs with unobserved variables. Further, we perform experiments to show improvements over baselines in this setting.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2305.04638

PDF

https://arxiv.org/pdf/2305.04638

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4375959262

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4375959262

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2305.04638

Digital Object Identifier

Title

Learning Good Interventions in Causal Graphs via Covering

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2023

Year of publication

Publication date

2023-05-08

Full publication date if available

Authors

Ayush Sawarni, Rahul Madhavan, Gaurav Sinha, Siddharth Barman

List of authors in order

Landing page

https://arxiv.org/abs/2305.04638

Publisher landing page

PDF URL

https://arxiv.org/pdf/2305.04638

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2305.04638

Direct OA link when available

Concepts

Regret, Bernoulli's principle, Simple (philosophy), Mathematics, Combinatorics, Random variable, Psychological intervention, Variable (mathematics), Graph, Discrete mathematics, Computer science, Mathematical optimization, Statistics, Psychology, Psychiatry, Epistemology, Philosophy, Aerospace engineering, Mathematical analysis, Engineering

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload