about
Adaptively Exploiting D-Separators with Causal Bandits (arxiv.org)
2 points by Anon84 on Feb 14, 2022 | hide | past | pdf | discuss on HN

In plain words: A trial-and-error picker uses measured variables to predict rewards, but only when they block every causal path to the outcome, so nobody must say when. It matches the best possible regret when such variables exist, and loses far less than causal bandit methods when they don't.

Abstract · Adaptively Exploiting d-Separators with Causal Bandits

Multi-armed bandit problems provide a framework to identify the optimal intervention over a sequence of repeated experiments. Without additional assumptions, minimax optimal performance (measured by cumulative regret) is well-understood. With access to additional observed variables that d-separate the intervention from the outcome (i.e., they are a d-separator), recent "causal bandit" algorithms provably incur less regret. However, in practice it is desirable to be agnostic to whether observed variables are a d-separator. Ideally, an algorithm should be adaptive; that is, perform nearly as well as an algorithm with oracle knowledge of the presence or absence of a d-separator. In this work, we formalize and study this notion of adaptivity, and provide a novel algorithm that simultaneously achieves (a) optimal regret when a d-separator is observed, improving on classical minimax algorithms, and (b) significantly smaller regret than recent causal bandit algorithms when the observed variables are not a d-separator. Crucially, our algorithm does not require any oracle knowledge of whether a d-separator is observed. We also generalize this adaptivity to other conditions, such as the front-door criterion.

Blair Bilodeau, Linbo Wang, Daniel M. Roy
arXiv:2202.05100 · stat.ML, cs.LG · submitted Feb 10, 2022 · updated Oct 26, 2022
abstract · pdf · html · 29 pages, 3 figures. Camera ready version

add comment on HN