PaperlayerView exact revision on arXiv

Source-linked AI summary

Causal Bandits: Learning Good Interventions via Causal Inference

Finnian Lattimore, Tor Lattimore, Mark D. Reid

arXiv:1606.03203v1stat.MLcs.LG

TL;DR

The paper asks how causal models can improve online learning of good interventions when feedback includes post-intervention covariates. It formalizes causal bandits and develops algorithms that exploit this feedback, obtaining simple-regret rates governed by causal difficulty and better than ignoring the additional information.

  • Problem

    Standard bandit formulations use a single reward signal, while this work studies intervention learning with additional observations from a known causal model.

  • Method

    The paper treats interventions as bandit arms and uses causal-graph structure with post-intervention observations to estimate rewards across actions.

  • Results

    The proposed algorithms achieve simple regret O(√(m/T)) up to logarithmic factors, where m depends on causal structure and is less than N.

  • Takeaways & Limitations

    Exploiting causal feedback can yield strictly better simple-regret guarantees than treating interventions as independent arms and ignoring non-reward observations.

  • Takeaways & Limitations

    The general algorithm requires the conditional interventional distributions P(PaY|a) for all allowed actions, while estimating these distributions optimally remains future work.

Abstract

from arXiv · show

We study the problem of using causal models to improve the rate at which good interventions can be learned online in a stochastic environment. Our formalism combines multi-arm bandits and causal inference to model a novel type of bandit feedback that is not exploited by existing approaches. We propose a new algorithm that exploits the causal feedback and prove a bound on its simple regret that is strictly better (in all quantities) than algorithms that do not use the additional causal information.

1 Introduction

The paper introduces causal bandits, where interventions are chosen as arms and post-intervention observations from a known causal model provide additional feedback. It develops algorithms for parallel and general causal structures that achieve simple-regret guarantees depending on causal-model difficulty rather than only the number of interventions.

  • Motivation: Causal bandits augment reward feedback with observations of covariates drawn from a probabilistic causal model.The framework targets sequential experimental settings such as medical testing, policy setting, and scientific experimentation.
  • Motivation: The farmer example illustrates choosing among interventions on temperature, soil nutrient, or moisture while observing non-intervened variables and crop yield.The goal is to identify the single highest-yielding intervention within a limited number of seasons.
  • Framework: The framework includes classical bandits and contextual stochastic bandits, then focuses on observations revealed after each intervention.Unlike contextual bandits, these observations cannot guide intervention selection before the action.
  • Parallel bandits: Parallel bandits use N independently affecting factors and 2^N interventions, enabling a causal algorithm with simple regret approximately ˜Θ(√(m/T)) where m may be much smaller than N.Existing best-arm identification algorithms incur Ω(√(N/T)) simple regret, up to the stated comparison and logarithmic factors.
  • General causal graphs: For general causal graphs, an importance-sampling-inspired algorithm achieves regret O(√(m/T)) up to logarithmic factors, with m determined by causal structure and smaller for easier problems.The paper states that m is always less than the number of interventions N and equals the parallel-bandit notion in that special case.
  • Related work: Prior approaches either ignore causal observations, use pre-action context, target cumulative regret, or require known factor likelihoods rather than learning them online.These differences motivate exploiting post-intervention causal feedback for simple-regret best-arm identification.

2 Problem Setup

A causal bandit repeatedly selects interventions on a fixed causal model and observes the reward plus all non-intervened variables. Its objective is pure exploration: after T rounds, output an action with low simple regret.

  • Causal model: A causal model consists of a directed acyclic graph G and a joint distribution P that factorizes over G.Interventions set selected variables and remove their incoming edges, defining the post-intervention distribution over the remaining variables.
  • Interaction protocol: In each round, the learner selects an allowed intervention, then observes sampled values for all non-intervened variables, including the binary reward Y.The final action estimate is based on observations collected over T rounds.
  • Objective: The expected reward of action a is μ_a, the optimal expected reward is μ*, and simple regret measures the gap between μ* and the expected reward of the selected estimate.This is a pure-exploration or best-arm-identification objective suited to settings with a fixed experimental budget.
  • Variants: The framework reduces to stochastic contextual bandits when non-intervened variables are observed before choosing an intervention.Even without round-level observations, the causal model may support offline pruning of allowable interventions.
  • Relationship to classical bandits: Classical K-armed stochastic bandits arise as a one-variable causal model, while any causal bandit can be reduced to independent arms by ignoring non-reward observations.The causal formulation is therefore a generalization that can use extra structure and observations.

3 Regret Bounds for Parallel Bandit

Parallel bandits exploit causal structure to focus exploration on interventions whose observational estimates are unreliable, achieving simple-regret guarantees that depend on the causal difficulty m(q) rather than all 2^N interventions.

  • Parallel Bandit Model: The parallel bandit has N independent binary causes of a binary reward, with empty and single-variable interventions as allowable actions.Each round either observes all variables or intervenes on one variable; non-intervened variables are generated by independent Bernoulli distributions.
  • Parallel Bandit Algorithm: The algorithm spends T/2 rounds collecting observational data, then evenly samples actions whose intervention values occur infrequently.Because each cause directly affects the reward, observational data estimates returns for high-probability interventions, while the second phase targets low-probability actions.
  • Parallel Bandit Algorithm: The causal difficulty m(q) depends on how many variables are unbalanced, trading off the number of low-probability actions against their identification difficulty.The threshold τ determines which variables are treated as unbalanced and is tuned to minimize worst-case simple regret.
  • Regret Bounds: m(q) can range from 2 for balanced variables to N when all variables are maximally unbalanced.The paper gives m(q)=2 for q=(1/2,…,1/2) and m(q)=N for q=(0,…,0).
  • Regret Bounds: The analysis includes an upper-bound theorem and a matching worst-case lower-bound theorem for the parallel-bandit setting.The paper states that Algorithm 1 is effectively optimal and that, for all T and q, some reward function yields the lower bound.
  • Regret Bounds: The algorithm achieves minimax-optimal simple regret up to logarithmic factors, scaling as ˜Θ(√(m/T)), while standard best-arm methods incur Ω(√(N/T)).The causal algorithm effectively explores only the m(q) difficult actions instead of all 2^N actions.

4 Regret Bounds for General Graphs

For arbitrary known causal graphs, the paper uses truncated importance weighting to estimate all intervention returns while allocating samples through an optimized distribution. The resulting guarantee depends on a causal-structure quantity m(η), which is bounded by the number of interventions and matches the parallel-bandit notion up to constants.

  • General causal graphs: General graphs require estimators that combine information from every intervention because observational correlations may not identify interventional effects.The paper highlights deterministic dependencies as a case where some parent configurations are never observed, preventing reliable estimation from naive observational data.
  • General causal graphs: The algorithm assumes the conditional interventional distributions P{PaY|a} are known, while estimating the full returns P{Y|a}.These conditional distributions may come from experimental or observational data under identifiability constraints; estimating them optimally is left for future work.
  • Algorithm and allocation: Samples drawn from η estimate the returns µa for all interventions simultaneously using a truncated importance weighted estimator.The distribution η determines sample allocation, and truncation controls heavy-tailed importance weights at the cost of estimator bias.
  • Regret bounds: Theorem 3 sets truncation using B_a = √(m(η)T log(2T|A|)), yielding a regret bound with the same form as the parallel-bandit result after replacing m(q) by m(η).The authors believe the optimally tuned general-graph algorithm is close to minimax optimal, but leave lower bounds for future work.
  • Algorithm and allocation: m(η) is convex and represents the minimum achievable worst-case variance of the importance weighted estimator when η is optimized.The optimal sampling distribution is the minimizer of m(η), making the allocation problem amenable to standard convex optimization techniques.
  • Regret bounds: m(η*) ≤ |A|, so the optimized difficulty measure is bounded by the number of available interventions.This bound follows by comparing the optimum with uniform sampling over actions.
  • Regret bounds: In the parallel-bandit setting, the optimized general measure satisfies m(η*) ≤ 2m(q), linking the general-graph analysis to the specialized lower-bound setting.The paper also notes that larger truncation thresholds can improve performance when importance-weight ratios lack heavy tails.

5 Experiments

Experiments compare causal algorithms with Successive Elimination on parallel bandit problems under varying causal difficulty and reward gaps. Causal methods generally benefit from smaller effective difficulty m, though the specific regression estimator performs best in this setting.

  • Experimental setup: Across 10,000 simulations, the experiments compare Algorithms 1 and 2 with Successive Elimination under varied conditions.Error bars show three standard errors.
  • Varying causal difficulty: As m increases, causal algorithms’ regret rises approximately with √m, while Successive Elimination remains constant because it ignores causal structure.The causal advantage is reduced as m approaches N.
  • Varying the horizon: For sufficiently large T, regret decays exponentially, with causal algorithms having a larger decay constant because they obtain more effective samples.This behavior is reported for fixed N and ε.
  • Estimator comparison: In the parallel bandit problem, the regression estimator in Algorithm 1 outperforms Algorithm 2’s truncated importance-weighted estimator.This holds despite Algorithm 1 needing to estimate q from data.

6 Discussion & Future Work

The discussion characterizes the general algorithm’s causal-structure-dependent guarantees and identifies practical limitations and extensions. Future work includes using reward information, cumulative regret, unknown causal models, and non-observable variables.

  • General causal bandits: Algorithm 2 estimates all intervention rewards using a sampling distribution η and achieves simple regret O(√(m(η)/T)) up to logarithmic factors.Here m(η) is a uniform variance bound for the reward estimators and is always less than N.
  • Limitations: The main practical drawback is that Algorithm 2 requires the conditional distributions P {PaY |a} to construct its estimator and optimal sampling distribution.The optimal distribution η* minimizes m(η).
  • Future work: The algorithm ignores reward information during sampling, and incorporating adaptive reward-based elimination is proposed as a way to improve performance when m is large.The discussion specifically notes poor relative performance against successive rejection in that regime.
  • Future work: Near-optimal cumulative-regret guarantees are suggested for the parallel bandit problem through a modification of existing side-information analyses.The paper’s main analysis, however, focuses on simple regret.
  • Open problems: Estimating unknown interventional distributions while minimizing simple regret remains an open problem, including when variables are non-observable.Known interventional distributions would allow the existing analysis to apply unchanged.
  • Open problems: Completely unknown causal graphs or graphs known only up to a model class are identified as a more difficult generalization.Observational data and causal-discovery methods are discussed as possible components of future algorithms.
  • Open problems: Simultaneously learning a completely unknown causal model and estimating intervention rewards without a large observational dataset would be much more challenging.

7 Proof of Theorem 1

The proof of Theorem 1 controls the empirical estimates of intervention probabilities and shows that the estimated causal difficulty remains comparable to the true difficulty. These bounds support sufficient sampling of difficult and infrequently observed actions.

  • Setup: The proof assumes q1 ≤ q2 ≤ … ≤ qN ≤ 1/2 without loss of generality because variables are independent and can be permuted into the reward function.
  • Concentration bounds: Chernoff and Hoeffding bounds control empirical frequencies and estimation errors across the variables, with union bounds limiting the overall failure probability.
  • Difficulty estimate: The proof establishes 2m(q)/3 ≤ m(ˆq) ≤ 2m(q), showing that the empirical causal-difficulty estimate is within constant factors of the true value.
  • Sampling guarantee: Actions classified as difficult receive at least T/(4m) samples, enabling Hoeffding-based control of their reward estimates.
  • Sampling guarantee: For actions outside the difficult set, empirical probabilities are bounded below by 1/(2m), supporting their treatment through observed frequencies.
  • Conclusion: The resulting bounds complete the proof of Theorem 1.

8 Proof of Theorem 2

The proof of Theorem 2 constructs multiple environments with different optimal interventions and bounds how distinguishable they are from observations collected over T rounds. It uses intervention counts and information divergence to establish a lower-bound argument.

  • Lower-bound construction: The proof constructs environments with different optimal arms that cannot all be statistically separated within T rounds.
  • Lower-bound construction: For each environment, the argument defines the expected simple regret and the probability measure over all observations generated during T rounds.
  • Information bound: The total number of interventions setting variable Xi to 1 is used to relate sampling effort to the KL divergence between observation distributions.The divergence is bounded using the chain rule and a χ-squared-distance bound.
  • Hard instances: The proof identifies variables receiving at most 2T/m interventions in a reference environment, forming a set used to select hard-to-distinguish alternatives.
  • Conclusion: Choosing ε subject to the stated constraints yields the final lower-bound step.

9 Proof of Theorem 3

The proof analyzes truncated rewards, relating their expectation to the true mean through a negative bias and controlling deviations with concentration inequalities. It then applies this analysis to the parallel bandit action set, separating actions by their probability threshold and obtaining a bound involving m(q).

  • Proof of Theorem 3: Truncated rewards satisfy |Z_at| ≤ B_a, and their expectation equals the action mean minus a negative bias.The proof defines Z_a(X_t) using the truncation indicator and writes E_Q[Z_at] = μ_a − β_a.
  • Proof of Theorem 3: Markov’s inequality bounds the truncation bias in terms of m(η).
  • Proof of Theorem 3: A union bound and Bernstein’s inequality control the probability of deviations over the relevant time and action indices.The displayed bounds involve logarithmic factors in T and |A|.
  • Proof of Theorem 3: On the high-probability event, the selected action is compared with the true optimal action a* = arg max_a∈A μ_a using the truncated expectations.
  • Proof of Theorem 3: The parallel bandit action set contains the observational action do() and binary interventions do(X_i = j).
  • Proof of Theorem 3: Actions are split according to whether η_a is positive or zero, with the resulting bound stated as ≤ 2m(q) for all actions.The η_a > 0 case includes do() and interventions with P{X_i = j} < 1/m(q); the η_a = 0 case covers interventions with probability at least 1/m(q).
Loading 1606.03203v1…