📊 statistics

Efficient Inference after Directionally Stable Adaptive Experiments

This paper introduces the concept of directional stability to establish that estimators remain asymptotically normal and semiparametrically efficient for scalar targets under adaptive data collection, providing the first such efficiency guarantee for the LinUCB algorithm.

Original authors: Zikai Shen, Houssam Zenati, Nathan Kallus, Arthur Gretton, Koulik Khamaru, Aurélien Bibaut

Published 2026-02-26

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zikai Shen, Houssam Zenati, Nathan Kallus, Arthur Gretton, Koulik Khamaru, Aurélien Bibaut

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 aren't just passively observing the world; you are actively changing your investigation strategy based on what you find.

This is the world of Adaptive Experiments. Think of it like a smart video game character (a "bandit") that learns as it plays. If a certain path in the game gives you a lot of treasure, the character keeps going there. If another path is a dead end, it stops going there.

The problem? In statistics, we usually like to assume that every piece of data we collect is independent, like flipping a fair coin over and over. But in these adaptive experiments, the data is dependent. The character's past choices dictate its future choices. This dependence breaks the standard math tools statisticians use to say, "We are 95% sure this result is real."

Here is the simple breakdown of what this paper does, using some creative analogies.

1. The Old Problem: The "Rigid Map"

For a long time, statisticians tried to fix this broken math by demanding a "Full-Matrix Stability."

The Analogy: Imagine you are trying to draw a perfect map of a city. The old rule said: "To trust your map, you must have walked down every single street in the city an equal number of times."
The Reality: In a smart game (or a real-world recommendation system), the character doesn't want to walk down dead-end streets. It wants to go where the treasure is. Forcing it to walk down every street equally would ruin the game (it would lose points, or "regret").
The Result: Because the character ignores the "bad" streets, the old math tools fail. They say, "I can't trust this map because you didn't walk down every street!"

2. The New Idea: "Directional Stability"

The authors of this paper say: "Wait a minute. We don't need a map of the whole city. We only care about one specific street where the treasure is."

They introduce a new concept called Directional Stability.

The Analogy: Instead of demanding you walk every street, they say: "As long as you have walked down the Main Street (where the treasure is) enough times to get a clear picture, it doesn't matter if you ignored the alleyways."
The Magic: Even if the character ignores the alleyways (which creates a lopsided, "anisotropic" map), the math still works perfectly for the Main Street. The "instability" in the ignored directions doesn't break the math for the direction that matters.

3. The Solution: The "One-Step" Estimator

Usually, when data is messy and dependent, statisticians have to use complex, heavy-duty tools (like "propensity weighting") to try to force the data to look normal. It's like trying to flatten a crumpled piece of paper with a heavy iron.

The authors show that if you have Directional Stability, you don't need the heavy iron.

The Analogy: You can use the exact same simple tool you would use if you were just flipping a fair coin (i.i.d. data).
The Result: The "One-Step Estimator" (a standard, simple calculation) works perfectly. It remains efficient and accurate. You don't need to invent new, complicated math just because the data was collected adaptively.

4. The Real-World Test: LinUCB

The paper doesn't just talk theory; they test it on LinUCB, a very popular algorithm used in things like news recommendations and online ads.

The Challenge: LinUCB is famous for being "regret-minimizing," meaning it aggressively stops exploring bad options. This usually breaks statistical rules.
The Breakthrough: The authors proved that LinUCB does satisfy "Directional Stability." Even though it ignores bad options, it stabilizes the "Main Street" (the direction of the true answer) perfectly.
The Payoff: For the first time, we can say with mathematical certainty that we can trust the results from LinUCB without needing complex, ad-hoc corrections.

Summary: The "Golden Compass"

Think of the adaptive experiment as a hiker in a foggy forest.

Old View: "You can't trust your compass unless you've walked every path in the forest equally." (Impossible for a smart hiker).
New View (This Paper): "You only need to trust your compass if it points steadily toward the destination. As long as the path to the destination is stable, it doesn't matter if you skipped the other trails."

The Bottom Line:
This paper gives statisticians a "Golden Compass." It proves that as long as your adaptive algorithm is stable in the direction you care about, you can use simple, standard math to get reliable answers. You don't need to overcomplicate things just because the data collection was smart and adaptive.

1. Problem Statement

The paper addresses the challenge of performing valid statistical inference on scalar, pathwise differentiable targets (e.g., average treatment effects or linear coefficients) after data has been collected via adaptive experiments, such as contextual bandit algorithms (e.g., LinUCB, Thompson Sampling).

The Core Issue: In adaptive settings, actions are chosen based on past observations, inducing dependence between data points. This violates the standard independent and identically distributed (i.i.d.) assumption required for classical asymptotic normality.
Limitations of Existing Methods:
- Propensity Weighting: Methods that re-weight data using estimated propensity scores often require consistent estimation of these scores and can degrade efficiency or fail in high-dimensional regimes.
- Full-Matrix Stability: Previous theoretical frameworks (e.g., Lai and Wei, 1982) require the entire empirical covariance matrix (design matrix) to stabilize deterministically. However, modern regret-minimizing bandit algorithms deliberately concentrate sampling in "good" directions (anisotropic exploration), causing the design matrix to remain unstable in certain directions. This makes full-matrix stability too restrictive and often unattainable without sacrificing regret performance.

2. Methodology and Key Concepts

The authors propose a novel framework that relaxes the stability requirements by focusing on the specific direction of the target parameter.

A. Directional Stability

The central contribution is the introduction of Directional Stability.

Definition: A design is directionally stable with respect to a target $\Psi_T = \nu_T^\top \beta_T$ if the empirical design stabilizes only along the direction defined by the target vector $\nu_T$ .
Mechanism: Instead of requiring the full covariance matrix $\hat{\Sigma}_T$ to converge to a deterministic limit, the method requires that the projection of the design onto the Riesz representer of the target (denoted $\bar{\alpha}_T$ ) stabilizes.
Significance: This allows for instability in directions orthogonal to the target (where the bandit might be exploring or under-sampling) while ensuring the specific linear combination of interest behaves predictably. This is strictly weaker than full-matrix stability.

B. Trajectory-Level Canonical Gradient

The authors derive the canonical gradient (influence function) for the target functional within the context of the full bandit trajectory.

Unlike standard i.i.d. settings, the canonical gradient here takes a martingale form:
$D^*_T = \frac{1}{T} \sum_{t=1}^T \bar{\alpha}_T(Z_t) (Y_t - h_T(Z_t))$
Here, $\bar{\alpha}_T$ is the Riesz representer derived from the time-averaged population design matrix. The martingale structure arises naturally from the adaptive filtration.

C. The One-Step Estimator

The paper constructs a one-step estimator that is algebraically identical to the standard i.i.d. one-step estimator (augmented with a bias correction term).

Construction: It uses ridge-regularized estimators for both the outcome regression ( $h_T$ ) and the Riesz representer ( $\bar{\alpha}_T$ ).
Key Insight: Under directional stability, this standard estimator remains asymptotically normal and semiparametrically efficient. No propensity weighting or ad-hoc variance stabilization is required. In fact, the authors argue that propensity weighting would degrade efficiency in this setting.

3. Theoretical Results

A. Asymptotic Normality

Under the assumption of Directional Stability and a Lindeberg condition, the authors prove that the one-step estimator satisfies:
$\frac{\sqrt{T}}{\bar{\sigma}_T} (\hat{\Psi}_T - \Psi_T) \xrightarrow{d} \mathcal{N}(0, 1)$
where $\bar{\sigma}_T$ is the asymptotic standard deviation derived from the martingale's predictable quadratic variation. This holds even in high-dimensional regimes where the dimension $d_T$ grows with $T$ , provided $d_T$ scales appropriately relative to the effective dimension and the regularization.

B. Efficiency Theory (Convolution Theorem)

The paper establishes a convolution theorem for a sequence of horizon-indexed experiments.

They define regularity along a sequence of least favorable submodels.
They prove that any regular estimator's limiting distribution is a convolution of the efficient limit $\mathcal{N}(0,1)$ and an arbitrary noise distribution $M$ .
Result: The proposed one-step estimator attains the semiparametric efficiency bound (i.e., $M = \delta_0$ ), meaning it is the most efficient estimator possible among regular estimators.

C. Application to LinUCB

The authors instantiate their theory for the LinUCB algorithm.

They verify that LinUCB satisfies Directional Stability but fails Full-Matrix Stability due to anisotropic information accumulation.
By analyzing the eigendecomposition of the LinUCB design matrix, they show that the stability condition holds in the direction of the true signal ( $\beta_T$ ) while allowing instability in orthogonal directions.
Outcome: This yields the first semiparametric efficiency guarantee for a regular scalar target under LinUCB sampling.

4. Key Contributions

Directional Stability: A new, weaker stability condition that is sufficient for inference on scalar targets, compatible with the anisotropic exploration patterns of regret-minimizing bandits.
Efficiency without Propensity Weighting: Demonstrating that standard i.i.d.-style one-step estimators are optimal under adaptive sampling if directional stability holds, removing the need for complex propensity-weighting corrections.
High-Dimensional Validity: Providing asymptotic normality guarantees in high-dimensional settings where plug-in OLS estimators typically fail.
LinUCB Guarantee: Proving the first efficiency result for LinUCB, bridging the gap between online learning (regret minimization) and rigorous statistical inference.

5. Significance and Implications

Practical Impact: This work allows practitioners to use standard, efficient estimators for causal inference in online learning systems (like recommendation engines or clinical trials) without needing to design complex, custom inference procedures for every new bandit algorithm.
Theoretical Advancement: It refines the understanding of when adaptive data collection preserves classical statistical properties. It shifts the focus from "global" design stability to "target-specific" stability, aligning statistical theory more closely with the objectives of modern reinforcement learning (which prioritizes specific directions of information gain).
Robustness: The results suggest that for many practical targets, the "cost" of adaptivity (in terms of inference difficulty) is lower than previously thought, provided the target aligns with the directions where the algorithm naturally stabilizes.

In summary, the paper provides a rigorous mathematical foundation showing that directional stability is the "sweet spot" condition: it is weak enough to be satisfied by efficient bandit algorithms like LinUCB, yet strong enough to guarantee that standard, efficient estimators remain valid and optimal.