🤖 machine learning

Information-Directed Sampling for Causal Bandits

This paper proposes Bayesian Thompson Sampling and Information-Directed Sampling algorithms for contextual causal bandits with non-manipulable variables, establishing entropy-dependent sublinear regret bounds and demonstrating superior performance over baselines by effectively leveraging shared causal mechanisms to accelerate high-reward decision identification.

Original authors: Muhammad Qasim Elahi, Murat Kocaoglu, Mahsa Ghasemi

Published 2026-07-20

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Muhammad Qasim Elahi, Murat Kocaoglu, Mahsa Ghasemi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but you can't just ask the suspect anything you want. Some clues are locked behind glass—you can see them, but you can't touch them. This is the world of "causal bandits," a branch of artificial intelligence where a computer learns to make the best decisions by experimenting. In a standard game, if you try one move and get a reward, you only learn about that specific move. But in the real world, actions are connected like dominoes; pushing one might knock over several others. Causal bandits use these hidden connections to learn faster: if you learn how a domino falls, you can guess how the next one will fall without even touching it. However, a major problem arises when some of those dominoes are "non-manipulable." You might be able to push a lever (an action), but you can't change the patient's age or the weather (non-manipulable variables), even though those things heavily influence the outcome. The challenge is figuring out how to learn the best strategy when some of the most important clues are out of your control.

This paper tackles that exact puzzle by introducing two new, smarter ways for an AI to play this game. The authors, working with the idea that the "map" of how things connect is known, propose a method where the AI treats the unknown parts of the system like a mystery box filled with probability. Instead of just guessing, the AI uses a technique called "Information-Directed Sampling" (IDS). Think of IDS as a detective who doesn't just pick the clue they think will solve the case right now, but also picks the clue that will teach them the most about the whole mystery, even if it doesn't solve it immediately. The paper shows that by using this approach, the AI can share information across different experiments much better than older methods.

The researchers developed two specific strategies for this. The first is a twist on "Thompson Sampling," which is like flipping a weighted coin to decide which experiment to run next, where the weight is based on how likely that experiment is to be the best. They proved mathematically that this method gets better and better over time, with the "mistakes" it makes growing very slowly. The second, and more complex, strategy is their new version of IDS. Because the math for IDS is incredibly hard to solve perfectly on a computer, they had to use a "Monte Carlo" method—basically, running thousands of simulated scenarios in their heads to get a good guess. The paper's big finding is that even with these guesses, the method still works incredibly well. They proved that the errors introduced by these simulations are small and controllable. In their tests on made-up scenarios, these new methods beat both the old causal methods and the non-causal ones, showing that when you can't touch everything, the best way to learn is to carefully choose which experiments teach you the most about the whole picture.

Technical Summary: Information-Directed Sampling for Causal Bandits

Problem Formulation

This paper addresses the problem of contextual causal bandits in environments containing non-manipulable variables. In standard multi-armed bandit problems, actions are selected to maximize rewards with unknown distributions. In causal bandits, actions correspond to interventions ($do(X=x)$) on a structural causal model (SCM), where rewards are coupled through shared causal mechanisms.

The specific challenge tackled here arises when certain variables in the causal graph influence the reward but cannot be directly manipulated (e.g., demographic attributes, genetic characteristics, or macroeconomic conditions). While these variables cannot be intervened upon, they serve as context variables observed before action selection and as observed variables after intervention. The goal is to select a feasible intervention from a set of candidate arms to maximize the context-dependent expected reward, $\mu_x(c) = E[Y | do(x), C=c]$ , while efficiently sharing information across different interventions.

The authors assume:

A known causal graph $G$ with no latent confounders.
A set of non-manipulable variables $N \subseteq V \setminus \{Y\}$ .
Context variables $C$ are observed prior to action selection and are closed under ancestry (i.e., $An(C)=C$).
The observational distribution is unknown, parameterized by conditional probability tables (CPTs).

Methodology

1. Bayesian Formulation and Parameterization

The authors adopt a Bayesian framework where the unknown parameter $\theta$ consists of the conditional probability tables of the observational distribution. Under the assumption of no latent confounders, interventional distributions are identifiable from the observational distribution via the truncated factorization formula.

Parameter Independence: The parameter vector $\theta$ is decomposed into local vectors $\theta_{ij}$ corresponding to the CPTs of each variable given its parent configurations.
Posterior Updates: Assuming conjugate Dirichlet priors, the posterior distribution over $\theta$ is updated analytically based on observed data. This allows samples collected under one intervention to update estimates for other interventions by refining the shared CPTs.

2. Identification of Candidate Arms

To handle non-manipulable variables, the paper utilizes the concept of Possibly Optimal Minimal Intervention Sets (POMISs) derived from Lee and Bareinboim [2019].

Projection: The original graph is projected onto a graph $H$ containing only manipulable variables. Latent confounding induced by non-manipulable variables is represented by bidirected edges in $H$ .
Arm Selection: The set of candidate arms $\mathcal{A}$ is generated by enumerating the POMISs of the projected graph $H$ . This ensures that the algorithm only considers interventions that are theoretically optimal under the manipulability constraints.

3. Proposed Algorithms

The paper proposes two causal variants of standard bandit algorithms:

A. Causal Thompson Sampling (TS)

Mechanism: At each round $t$ , given context $C_t=c_t$ , the algorithm samples a parameter $\theta_t$ from the context-conditioned posterior $P(\theta | F_t, C_t=c_t)$ . It then selects the action $a_t$ that maximizes the expected reward under the sampled parameter: $a_t = \arg\max_{a \in \mathcal{A}} E[Y_a | \theta_t, c_t]$ .
Regret Analysis: The authors establish a sublinear Bayesian regret bound dependent on the entropy of the optimal action mapping, $H(\Pi^*)$ . The bound scales as $O(\sqrt{T |A| |C| \log |A|})$ .

B. Causal Information-Directed Sampling (IDS)

Mechanism: IDS selects a distribution over actions that minimizes the information ratio, defined as the squared expected instantaneous regret divided by the expected information gain about the optimal action.
- Regret Term: $\Delta_t(\pi | c_t) = \sum \pi(a) E[Y_{\Pi^*(c_t)} - Y_a]$ .
- Information Gain Term: $g_t(\pi | c_t) = \sum \pi(a) D_{KL}(P(\Pi^*, Y_a) || P(\Pi^*)P(Y_a))$ .
Monte Carlo Approximation: Since the posterior expectations required to compute the information ratio are analytically intractable in continuous parameter spaces, the algorithm approximates them using $N$ Monte Carlo samples from the posterior.
Error Control: The authors derive high-probability concentration bounds (Lemmas 3 and 4) for the Monte Carlo estimates of both the expected regret and the information gain. These bounds explicitly quantify the additional error introduced by the approximation.

Key Contributions

Bayesian Framework for Non-Manipulable Variables: The paper formulates contextual causal bandits with non-manipulable variables by treating the observational CPTs as the unknown parameter. This formulation enables information sharing across interventions through shared causal mechanisms, even when some variables cannot be intervened upon.
Causal Thompson Sampling with Regret Guarantees: The authors propose a causal TS algorithm and prove an entropy-dependent sublinear Bayesian regret bound. This extends TS guarantees to settings with structural constraints and context.
Causal IDS with Approximation Analysis: The paper develops a causal IDS algorithm that balances regret minimization and information acquisition. Crucially, it derives a regret bound that explicitly separates the standard information-theoretic term from the error introduced by Monte Carlo approximation. When the information ratio is computed exactly (oracle version), the standard sublinear IDS rate is recovered.
Concentration Bounds for Monte Carlo Estimates: The authors provide high-probability confidence bounds for the Monte Carlo estimates of expected instantaneous regret and contextual information gain. These results quantify the impact of posterior-sampling error on the algorithm's performance guarantees.

Results and Evaluation

The proposed methods were evaluated on multiple synthetic causal bandit tasks, including structured examples and randomly generated causal graphs.

Performance: The experiments demonstrate that the proposed Causal TS and Causal IDS algorithms outperform both causal and non-causal baselines.
Mechanism: The superior performance is attributed to the algorithms' ability to more effectively exploit information shared across different interventions via the shared causal structure, particularly in the presence of non-manipulable variables.

Significance

The paper claims significance in providing a principled framework for decision-making in causal environments where full control over variables is impossible. By integrating non-manipulable variables into the causal bandit framework and offering algorithms with rigorous regret bounds (including analysis of approximation errors), the work bridges the gap between theoretical causal inference and practical sequential decision-making. The explicit handling of Monte Carlo approximation errors in IDS is highlighted as a key theoretical advancement, ensuring that the benefits of information-directed sampling are preserved even when exact computation is infeasible.