Valid Post-Contextual Bandit Inference

summary

The gist

We establish an asymptotic framework for the statistical analysis of the stochastic contextual multi-armed bandit problem…

In short

The paper establishes a framework for statistically analyzing stochastic contextual multi-armed bandit problems by deriving a limit experiment using stochastic differential equations. This allows researchers to find valid asymptotic distributions for various tests, such as t-tests and Inverse Propensity Weighted tests, especially when using translation-invariant sampling schemes.

Key concepts

Limit Experiment
This is the theoretical ideal experiment that the actual bandit problem converges to in a specific sense (Hajek-Le Cam). The authors show that for certain arm means, this ideal experiment behaves like a Locally Asymptotically Quadratic (LAQ) experiment, which simplifies the statistical analysis significantly.
Stochastic Differential Equations (SDEs)
The authors use SDEs to create a structural representation of the limit experiment. This mathematical description allows them to study the asymptotic behavior of complex statistics without needing tedious calculations, characterizing how observed processes evolve over time.
Translation Invariance
This property means that the sampling policies used (like Thompson Sampling or UCB) do not depend on an unknown parameter (theta). By modifying these policies to be translation-invariant, the authors ensure that the resulting statistical tests satisfy a key assumption required for valid inference in CMAB.
Adaptively Weighted (AW) Test
This specific test statistic is shown to be asymptotically distribution-free with respect to the nuisance local parameter (the mean of the other arm) under certain conditions. When using translation-invariant sampling, this test becomes standard normally distributed under the null hypothesis, making it a reliable comparison tool.

Terminology used across episodes

This episode discusses

The paper

Valid Post-Contextual Bandit Inference · Read on arXiv

Ramon van den Akker, Bas J.M. Werker, Bo Zhou

Tilburg University · Virginia Tech

Contextual multi-armed bandits (CMAB) are increasingly used as adaptively sampled experiments, after which researchers test hypotheses about treatment effects. We derive the Hájek-Le Cam limit experiment for multi-armed contextual bandits under equal-arms (weak-signal) asymptotics. It is Locally Asymptotically Quadratic, but not a (mixed) Gaussian shift experiment. Girsanov's theorem gives it a structural representation in stochastic differential equations. Together with a general weak convergence result, this yields the asymptotic null distribution and local asymptotic power of often-used test statistics. Two kinds of nuisance parameters threaten size control: the common reward level of the arms of interest and the rewards of the arms not of interest. The first threat is removed by translation-invariant sampling. We propose Regularized Translation-Invariant (RTI) versions of Thompson, tempered-greedy, tempered-(Lin)UCB, and exploration sampling. The second threat calls for appropriate pivots. The structural representation of the limit experiment is key to overcome the inferential challenges arising from adaptive sampling. Simulations corroborate the theory.

Transcript

Introduction to the show: ident: Economics. The day in economics: theory, mechanisms and the evidence beneath them.

Ruth: We're looking at the paper: "Valid Post-Contextual Bandit Inference".

Warren: Here's the gist of the paper. Valid Post-Contextual Bandit Inference establishes an asymptotic framework for statistical analysis of stochastic contextual multi-armed bandit problems by deriving a limit experiment and structural representation in terms of stochastic differential equations The authors show that this framework allows for the asymptotic distribution of statistics like the classical t-test, Adaptively Weighted tests, and Inverse Propensity Weighted tests under adaptively collected data Limit Experiment Derivation The paper develops the limit experiment for the CMAB problem in the H´ajek-Le Cam sense They prove that for arm-means that are O(T−1/2) apart, “equal-arms (local) asymptotics”, the log-likelihood ratios of a CMAB model converge to those of a Locally Asymptotically Quadratic (LAQ) experiment Using Girsanov’s theorem, they show that a system of coupled SDEs provides a structural description of the limit experiment Structural Representation and Convergence The authors establish a weak convergence result for a general class of statistics in CMAB under suitable regularity conditions, jointly with the likelihood ratio process This facilitates invoking the Asymptotic Representation Theorem and Le Cam’s third lemma for a wide range of statistics The limiting behaviors of these statistics can be characterized by their associated SDEs Inference on Single Arm Means When testing the hypothesis that both arms have equal (unknown) means in two-armed MAB and CMAB problems, they analyze three inference procedures: (i) the classical t-test, (ii) an Adaptively Weighted (AW) estimator, and (iii) an Inverse Probability Weighted (IPW) estimator It turns out that the null distribution of the t-test is “unstable” in case standard policies such as Thompson sampling, UCB, or ϵ-greedy/tempered-greedy are used because these policies are not translation-invariant Role of Translation Invariance The authors rigorously introduce translation invariance of policies for the MAB/CMAB problem and propose modified policies for Thompson sampling, tempered-greedy, and a newly introduced tempered-UCB/tempered-LinUCB algorithm to satisfy this property The translation-invariant versions of these sampling schemes are shown to satisfy Assumption 2 Test Statistics and Power Analysis In the MAB case, they find that the t-test and IPW test are not only asymptotically nonnormal but also not distribution-free with respect to the local reward parameter of the other arm, making them invalid The only valid test in this case is the AW test, whose statistic is standard normally distributed under the null, regardless of the expected reward of the other arm The paper concludes that for reliable inference, validity requires distribution-freeness (w.r.t.

Ruth: the common local means of the arms) of its statistics and, perhaps less obviously, translation-invariance of the sampling schemes They recommend using the two-sample t-test in conjunction with a translation-invariant sampling scheme for reliable inference Pruning redundant reasoning tokens The authors show that diffusion approximations used to describe limiting behavior can also be used as approximations in the H´ajek-Le Cam sense of convergence of statistical experiments Leveraging a structural representation of the CMAB limit experiment in terms of SDEs, they can readily study the asymptotic behavior of commonly used test statistics How the training signal is built The structural representation of the CMAB limit experiment is described in terms of stochastic differential equations The authors derive a system of SDEs that describe the limiting log-likelihood ratio and other relevant statistics These SDEs allow for the characterization of the limiting experiment in terms of observed continuous-time processes like Wk, Qk, Wεk, Cr1;k, and Sr2;k Where the gains come from The analysis demonstrates that many such tests have non-constant size over the (composite) null hypothesis The only valid test in this case is the AW test, whose statistic is standard normally distributed under the null, regardless of the expected reward of the other arm They recommend using the two-sample t-test in conjunction with a translation-invariant sampling scheme for reliable inference How the training signal is built The authors establish that many such tests have non-constant size over the (composite) null hypothesis The only valid test in this case is the AW test, whose statistic is standard normally distributed under the null, regardless of the expected reward of the other arm Where the gains come from The authors recommend using the two-sample t-test in conjunction with a translation-invariant sampling scheme for reliable inference The paper is organized as follows: Section 2 sets up the stochastic contextual multi-armed bandit problem, Section 3 develops the CMAB limit experiment and its structural representation in SDEs, Sections 4 and 5 apply these results to hypothesis tests in non-contextual and contextual bandits respectively Pruning redundant reasoning tokens

Title and authors: Ruth: We’ve been talking about the "Valid Post-Contextual Bandit Inference" paper. To get into it again, the title tells you exactly what they’re tackling: establishing a framework for statistical analysis in contextual multi-armed bandit problems after data has been collected adaptively.

Warren: The authors focus on deriving this limit experiment and its structural representation using stochastic differential equations to characterize the asymptotic behavior of various statistics under adaptively collected data. It sounds like they are providing the mathematical backbone for doing reliable inference in this complex area.

Iris: They start by developing the limit experiment in the H´ajek-Le Cam sense, which is a specific way to view statistical experiments, and then apply Girsanov’s theorem to get that structural description involving coupled SDEs. This structural representation is what allows them to study how things behave asymptotically.

Ruth: It’s about moving away from just looking at the immediate regret and instead building this deeper mathematical structure that describes the entire process of data collection and inference simultaneously. They show this general weak convergence result, which lets them apply Le Cam’s third lemma for a wide range of statistics.

Warren: That general result is powerful because it allows you to characterize the limiting behaviors of these various statistics by looking at their associated SDEs, which is a very concrete way to study the long-term behavior without having to rely on tedious triangular array arguments.

Iris: I’m interested in how they handle the actual tests. They analyze things like the classical t-test and IPW tests, showing their asymptotic distributions under certain conditions. The key finding here is that these tests often fail because of issues related to translation invariance when standard policies are used for sampling.

Ruth: So, while they derive this deep structural representation using SDEs, the immediate practical implication is that you have to be careful about the policy you pick—it has to be translation-invariant if you want a stable test.

Warren: If we use Thompson sampling or UCB, the t-test becomes unstable because those policies aren't translation-invariant in this context. So they spend a lot of effort proposing modified versions of these sampling schemes, like tempered Thompson sampling or tempered UCB, to fix that issue and satisfy Assumption two <ref:2505.13897#pg1>.

The paper's summary: Ruth: To summarize the paper, "Valid Post-Contextual Bandit Inference" establishes an asymptotic framework for statistical analysis of the CMAB problem by deriving a limit experiment and its structural representation in terms of stochastic differential equations. They then show this allows for the asymptotic distribution of statistics like the classical t-test, Adaptively Weighted tests, and Inverse Propensity Weighted tests under adaptively collected data.

Warren: So they are saying that even with adaptively collected data, we can obtain meaningful asymptotic distributions for these standard statistical tools if we use this new structural description derived from the limit experiment. That’s a big step because it tackles the non-standard nature of CMAB inference directly.

Iris: They develop this limit experiment in the H´ajek-Le Cam sense, and then they use Girsanov’s theorem to get a structural representation involving coupled SDEs that describe the limiting log-likelihood ratio and other relevant statistics like Wk, Qk, Wεk.

Ruth: These SDEs are used to characterize the CMAB limit experiment in terms of observed continuous-time processes, which is what gives them the tools to study test statistics asymptotically. They can readily study things like the asymptotic behavior of these tests using diffusion approximations applied in the H´ajek-Le Cam sense.

Warren: This approach is a way to get around having to run through complicated proofs for every single statistic individually. By having this structural representation, you just plug in your statistic and you can read off its limiting behavior from the SDEs.

Iris: And they establish a weak convergence result for a general class of statistics jointly with the likelihood ratio process, which is what lets them invoke the Asymptotic Representation Theorem and Le Cam’s third lemma for a wide range of statistics. This links everything together nicely.

Ruth: So, in essence, they provide a comprehensive mathematical roadmap that uses SDEs to describe the CMAB limit experiment, giving us tools to understand how our tests perform when we collect data adaptively in this environment.

The paper's improvements: Warren: Now let’s talk about what the authors suggest as improvements for this framework. They focus heavily on fixing the issues with standard sampling schemes and proposing translation invariant versions of Thompson sampling, tempered-greedy, and a new tempered-UCB or tempered-LinUCB algorithm.

Iris: The key improvement here is that these translation invariant versions of the sampling schemes are shown to satisfy Assumption two of the CMAB framework <ref:2505.13897#pg1>. This is what makes the statistical results valid under their model assumptions.

Ruth: That’s significant because it means we can actually use those statistical tools reliably, not just theoretically. It moves us from theory into a setting where we can actually get good inference when things are collected adaptively in a realistic way.

Warren: They also showed that the Adaptively Weighted (AW) test statistic is asymptotically distribution-free with respect to the nuisance local parameter m under the null hypothesis in both MAB and CMAB settings, specifically when using those translation invariant sampling schemes.

Iris: That AW test being standard normal under the null, regardless of the other arm's mean, is a huge win for practical testing because it makes it a reliable statistic for comparing arms. It’s not dependent on the expected reward of the other arm at all.

Ruth: So, in short, they suggest using this AW test when you’re running an experiment and you want to compare arms reliably, provided you use a translation invariant sampling scheme to make that work.

Conclusion: Ruth: Wrapping up this paper on "Valid Post-Contextual Bandit Inference," the main implication is that for reliable inference in CMAB settings, we need distribution-freeness with respect to the common local means of the arms and translation invariance in our sampling schemes.

Warren: And they recommend using the two-sample t-test in conjunction with a translation-invariant sampling scheme for reliable inference. This gives us a concrete procedure that combines existing tools with their structural insights into how to use them effectively.

Iris: From my view, this AW test being standard normal under the null is the strongest result because it shows it doesn't care about the other arm’s mean, which is a major simplification for us when we have unknown parameters.

Ruth: So we have a solid framework now that uses SDEs to describe the CMAB limit experiment and gives us tools to study test statistics asymptotically in this setting. We should keep an eye on how this approach applies to more complex bandit problems next.

Warren: Indeed, they’ve given us a solid foundation for understanding the statistical side of adaptive experiments in these systems. This paper "Valid Post-Contextual Bandit Inference" is a key piece for anyone working on the theory behind adaptive inference here.

More episodes

← Home