Valid Post-Contextual Bandit Inference

Valid Post-Contextual Bandit Inference

{12pt}

\begingroup \footnote{We thank Keisuke Hirano and participants at various seminars and conferences for their helpful feedback.} \addtocounter{footnote}{-1} \endgroup

\abstract{We establish an asymptotic framework for the statistical analysis of the stochastic contextual multi-armed bandit problem (CMAB), which is widely employed in adaptively randomized experiments across various fields. While algorithms for maximizing rewards or, equivalently, minimizing regret have received considerable attention, our focus centers on statistical inference with adaptively collected data under the CMAB model. To this end we derive the limit experiment (in the H\'ajek-Le Cam sense). This limit experiment is highly nonstandard and, applying Girsanov's theorem, we obtain a structural representation in terms of stochastic differential equations. This structural representation, and a general weak convergence result we develop, allow us to obtain the asymptotic distribution of statistics for the CMAB problem. In particular, we obtain the asymptotic distributions for the classical t-test (non-Gaussian), Adaptively Weighted tests, and Inverse Propensity Weighted tests (non-Gaussian). We show that, when comparing both arms, validity of these tests requires the sampling scheme to be translation invariant in a way we make precise. We propose translation-invariant versions of Thompson, tempered greedy, and tempered Upper Confidence Bound sampling. Simulation results corroborate our asymptotic analysis.} \\

Keywords: contextual multi-armed bandit, limit experiment, locally asymptotically quadratic, adaptive inference.

Introduction

Stochastic contextual multi-armed bandits (CMABs) are a cornerstone for adaptive randomized experiments and sequential decision-making under uncertainty. At each round, an agent observes a covariate vector $\boldsymbol{X}_t$ (the context), selects one of $K$ treatment arms, and receives a reward $Y_t$ drawn from that arm’s context-dependent distribution (without observing the counterfactual outcomes). CMABs now underpin real-world systems in dynamic pricing, news and ad recommendation, online education, and mobile health, amongst others.\footnote{bouneffouf2020survey provides a review of applications.} The standard objective is to minimize (expected) cumulative regret, which yields the classic exploration-exploitation dilemma. Often used sampling schemes, or policies, for MABs/CMABs include Thompson sampling (thompson1933likelihood, agrawal2013thompson), upper-confidence-bound (UCB) algorithms (lai1985asymptotically, auer2002finite, li2010contextual), $\epsilon$-greedy/tempered-greedy heuristics, and the recent exploration sampling of kasy2021adaptive. An extensive literature---initiated by lai1985asymptotically and surveyed by, amongst others, slivkins2019introduction and lattimore2020bandit---focuses on studying the (asymptotic) regret properties of policies.\footnote{While these policies aim to optimize expected cumulative regret, fan2024fragility and simchi2024simple show that this can lead to heavy-tailed regret, motivating alternative designs that limit tail risk.}

The same adaptivity that makes CMABs efficient, in the sense of minimizing the expected regret while conducting an experiment, complicates statistical inference. Data arising from a bandit experiment are not independent and identically distributed (i.i.d.), which can ruin the standard properties of estimators and test statistics. For example, the sample mean of the observations collected on a treatment arm is, in general, a biased estimator of the mean of the arm and asymptotically, has a non-Gaussian distribution. See deshpande2018accurate, nie2018adaptively and shin2019sample for detailed discussions and illustrations. As a result, naive statistical analyses that ignore the adaptive sampling generally lead to invalid statistical inference. This underscores the need for rigorous post-bandit statistical inference methods. zhang2020inference, zhang2021statistical and hadad2021confidence studied statistics that reweight the observations in classical estimators in order to recover asymptotic normality of estimators or other desired properties. bibaut2025demystifying surveys such approaches and discusses open questions.

The distribution of arm-pull frequencies and the regret strongly depend on the “gap” between the mean of the best arm and the means of the other arms. When one studies this behavior for $T\to\infty$, where $T$ denotes the number of rounds the bandit is run, one can consider the means of the arms to be constant or allow for gaps shrinking to zero. kuang2024weak and fan2025diffusion showed for arm means of size $O(T^{-1/2})$, “weak signal asymptotics”, that the limiting behavior of the arm-pull frequencies and the sample means can be described by a set of coupled Stochastic Differential Equations (SDEs) for several policies including Thompson sampling.\footnote{kuang2024weak extends their results, developed under weak signal asymptotics, to equal-arms asymptotics, which allows the common reward parameter $\mu$ to take non-zero values (with $\mu = 0$ corresponding to weak signal asymptotics), by replacing Thompson sampling by its translation-invariant version. This indicates that imposing $\mu = 0$ by those papers is not an innocent assumption for notational convenience.} Henceforth we will refer to these papers by KWFG. In a similar setup adusumilli2021risk studied the local asymptotic behavior of the regret.

This paper contributes to the literature on valid post-bandit statistical inference methods. Instead of focusing on a specific class of statistics as starting point, we will first consider the (statistical) limit experiment in the H\'ajek-Le Cam sense (see, for example, le1986asymptotic, hajek1970characterization, or van2000asymptotic) for the CMAB problem. While the derivation of a limit experiment requires some effort, it yields powerful tools. Firstly, if you know the asymptotic behavior of a statistic under a probability distribution, then the limit experiment (via Le Cam’s third lemma; see, for example, van2000asymptotic) immediately yields the asymptotic distribution under local alternatives (i.e., contiguous probability measures). In the context of analyzing a test statistic this means that we “only” need to derive its null distribution. The local asymptotic power function of the test statistic “easily” follows via the limit experiment. In this way tedious “triangular array arguments” are avoided. Secondly, the so-called Asymptotic Representation Theorem (see, for example, van2000asymptotic) can be used to derive bounds to the (asymptotic) performances (for example, power) of statistics, to study the asymptotic properties of existing inferential procedures, and to leverage insights from the limit to guide the development of new inferential tools.

The contributions of this paper are threefold. Firstly, this paper obtains the limit experiment for the CMAB problem. We prove that, for arm-means that are $O(T^{-1/2})$ apart, “equal-arms (local) asymptotics”, the log-likelihood ratios of a CMAB model converges to those of a Locally Asymptotically Quadratic (LAQ) experiment (Jeganathan1995).\footnote{While this limit experiment is LAQ, it is not of the familiar Locally Asymptotically Normal type (as one gets for smooth parametric models for i.i.d.\ data and sufficiently ergodic and stationary time series), and also not of the Locally Asymptotically Mixed Normal (LAMN) or Locally Asymptotically Brownian Functional (LABF) types (as one often gets for smooth parametric models for nonstationary time series).}$^{,}$\footnote{Although we do not consider the batched bandit setting in this paper, we would like to mention hirano2025asymptotic recently derived the limit experiment for the batched bandits. This experiment, however, is of a very different type compared to the one associate with (C)MAB problems under continuously updated policies. chen2023optimal develop inference procedures exploiting their limit experiment.} Using Girsanov’s theorem, we show that a system of coupled SDEs provides a structural description of the limit experiment. Secondly, we establish a weak convergence result for a general class of statistics in CMAB, under suitable regularity conditions, jointly with the likelihood ratio process. facilitates invoking the aforementioned Asymptotic Representation Theorem and Le Cam's third lemma for a wide range of statistics. As a result, the limiting behaviors of these statistics can be characterized by their associated SDEs. In the special case of the non-contextual bandit, our results yield the SDEs in KWFG. We thus i) provide an alternative proof for the “diffusion results” in KFWG, ii) extend these results to contextual bandits, and iii) enable the study of inference via the obtained SDEs.

Thirdly, we investigate the hypothesis, in two-armed MAB and CMAB problems, that both arms have equal (unknown) means. (For the two-armed MAB, we also consider a hypothesis on the mean of a single arm.) We analyze three inference procedures that have been considered in, for example, hadad2021confidence, zhang2021statistical, and bibaut2025demystifying: (i) the classical $t$-test, (ii) an Adaptively Weighted (AW) estimator, and (iii) an Inverse Probability Weighted (IPW) estimator.\footnote{In the case of comparing the two arms, we propose a two-sample version of the AW statistic.} It turns out that the null distribution of the t-test is “unstable” (see Sections (ref) and (ref) for details) in case standard policies such as Thompson sampling, UCB, or $\epsilon$-greedy/tempered-greedy are used. The reason is that such policies are not translation-invariant: adding a constant to all rewards---which is possible under our composite null---alters the sampling probabilities, thereby causing the distribution of the t-test to change. We 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 that satisfy this property.\footnote{Other popular policies like (a tempered version of) Explore-Then-Commit can also be analyzed within our framework.} This notion of translation invariance might be of independent interest, for instance, in regret analysis, which we leave to future work. For each aforementioned test statistic, we derive its asymptotic null distribution and show how critical value can be obtained. For the valid tests, we further derive local asymptotic power functions by exploiting the structural limit experiment in SDEs. While the two-sample AW test is appealing due to its asymptotic standard normal distribution under the null, the two-sample t-test (with a nonstandard limiting distribution) has significantly higher power for the policies we investigated. We corroborate the asymptotic results with Monte Carlo simulations.

Our paper is organized as follows. Section (ref) sets up the stochastic contextual multi-armed bandit problem. In Section (ref), we develop the CMAB limit experiment and its structural representation written in SDEs, along with those of a class of statistics intended for inference. These results are then applied to the analysis of hypothesis tests in Section (ref) and Section (ref), for the non-contextual and contextual bandits, respectively, with corresponding Monte Carlo studies presented in each section. Section (ref) concludes the paper and our findings.

Setup

Consider the following multi-armed contextual bandit problem. At the beginning of each time step $t$, where $t\in[T]\equiv\{1,\dots,T\}$, an agent observes an exogenous variable $\boldsymbol{X}_{t}$ collecting contextual information.\footnote{Non-contextual bandits can be embedded in this framework by using $\boldsymbol{X}_{t} = 1$.} We assume the contextual variables $\boldsymbol{X}_{t}\in\mathcal{X}\subset\mathbb{R}^{q}$, to be independently and identically distributed. We denote by $\nu_X$ the corresponding probability measure. Subsequently, on basis of previously collected observations (in a way that will be made precise below) and the new context $\boldsymbol{X}_{t}$, the agent chooses one of $K \geq 2$ possible arms, or treatments, $A_{t}\in[K]\equiv\{1,\dots,K\}$. Each arm is associated with an unknown probability distribution of outcomes. All outcomes are assumed to be mutually independent, both over arms and over time. Let $Z_{k,t}$ denote the $\mathbb{R}$-valued potential outcome of arm $k \in [K]$ at time $t$. The agent only observes $Y_{t} = Z_{A_{t},t}$.

For $k=1,\dots,K$, $Z_{k,t}$ given $\boldsymbol{X}_{t}$ has law $\mathcal{L}_{\boldsymbol{\theta}}(Z_k|\boldsymbol{X})$, where $\boldsymbol{\theta}$ is a common parameter in an open parameter space $\boldsymbol{\Theta}\subset\mathbb{R}^{p}$. We assume that, with respect to some $\sigma$-finite dominating measure $\nu$, densities $f_{k}(\cdot | \boldsymbol{x},\boldsymbol{\theta})$ of $\mathcal{L}_{\boldsymbol{\theta}}(Z_k|\boldsymbol{X}=\boldsymbol{x})$ exist, $\boldsymbol{x}\in\mathcal{X}$. Furthermore, we impose the following Differentiable in Quadratic Mean (DQM) condition on these densities.

The DQM condition (Assumption (ref)) implies that $\mathbb{E}\big[\dot{\boldsymbol{\ell}}_{\boldsymbol{\theta},k}(Z_{k}|\boldsymbol{X})|\boldsymbol{X}\big] = \boldsymbol{0}$ and the $p\times p$ Fisher information matrix $\boldsymbol{J}_{\boldsymbol{\theta},k}(\boldsymbol{X}) \equiv \mathbb{E}\big[\dot{\boldsymbol{\ell}}_{\boldsymbol{\theta},k}(Z_{k}|\boldsymbol{X})\dot{\boldsymbol{\ell}}_{\boldsymbol{\theta},k}(Z_{k}|\boldsymbol{X})^\prime|\boldsymbol{X}\big]$ exists (see van2000asymptotic), almost surely. Moreover, the moment condition on the score function in Assumption (ref) ensures that $\mathbb{E}[\boldsymbol{J}_{\boldsymbol{\theta},k}(\boldsymbol{X})]$ is finite.

The agent is allowed to update her sampling strategy according to all the information available at each moment $t$. Formally, we define the filtration $(\mathcal{F}_{t})_{t \geq 1}$ through

which collects the historical information of contexts, actions, and rewards up to and including time $t$. The agent chooses the $(t+1)$-th action $A_{t+1}$ via a draw from a multinomial distribution conditional on $\mathcal{F}_{t}$ and the newly observed context $\boldsymbol{X}_{t+1}$. We call a strategy feasible if it satisfies the following assumption.

Assumption (ref) basically states that the agent has no knowledge of the true value of $\boldsymbol{\theta}$. However, it is worth noting that the unconditional distribution of $A_{t}$ typically does depend on $\boldsymbol{\theta}$. In applications, the dependence of the conditional sampling probability $\pi_{t+1}$ on $\mathcal{F}_{t}$ is usually through some summary statistics. We also adopt this approach; see Assumption (ref) below.

In this paper, we focus on the inferential problem of $\boldsymbol{\theta}$, particularly the testing problems detailed in Section (ref) (for non-contextual bandits) and Section (ref) (for contextual bandits). In Section (ref), we first develop the limit experiment for the general case. This limiting framework, in turn, allows us to readily analyze the asymptotic behavior of the original sequence of bandit experiment---specifically, for our purpose, the asymptotic properties of statistics (see the end of Section (ref) for details). While our framework is primarily used for inference in the present paper, it can also be seamlessly applied to other tasks, such as designing sampling schemes, which we leave for future work.

Limit Experiment

We derive the limit experiment for the contextual bandit problem described in Section (ref) at some fixed point $\boldsymbol{\theta}\in\boldsymbol{\Theta}$, typically where the arms have equal expected rewards—we refer to this as the equal-arms asymptotics. It turns out that, given our parametric setup, we need to use $\sqrt{T}$ as localizing rate.

Quadratic expansion of likelihood ratios

Localizing the parameter of interest at $\boldsymbol{\theta}$ as

we denote by $\mathrm{P}^{(T)}_{\boldsymbol{\theta},\boldsymbol{h}}$ the law of $(\boldsymbol{X}_{1},A_{1},Y_{1},\dots,\boldsymbol{X}_{T},A_{T},Y_{T})$ generated by the aforementioned stochastic contextual $K$-armed bandit problem. Formally, we define the sequence of experiments as

where $\Omega^{(T)} = {\mathcal{X}}^{T}\otimes\mathbb{R}^{T}\otimes[K]^{T}$ and $\mathcal{F}^{(T)} = \mathcal{B}\left(\mathcal{X}^{T}\otimes\mathbb{R}^{T}\otimes[K]^{T}\right)$, the Borel $\sigma$-field.

From the previous arguments, using Assumptions (ref) and (ref), and using that the distribution of the contexts $\boldsymbol{X}_{t}$ does not depend on $\boldsymbol{\theta}$, the log-likelihood ratio equals

In the following proposition, we provide a quadratic expansion of this log-likelihood ratio which shows that the model exhibits the LAQ property (see Jeganathan1995, van2000asymptotic).

The proof of Proposition (ref), which exploits hallin2015quadratic, is provided in Appendix (ref).

Weak convergence of relevant processes

In order to derive the limit experiment for our contextual bandit problem, we establish weak convergence of the central sequence and the Fisher information appearing in Proposition (ref), jointly with some other statistics of interest. This will allow us to describe the limit experiment in Section (ref) and study commonly used inference methods in subsequent sections.

For this analysis, we need the joint limiting behavior of the following partial-sum processes, for $k\in[K]$:

for vector-valued functions $\boldsymbol{v}^{\circ}_k$ and $\boldsymbol{v}^{\star}_k$. Here, $\boldsymbol{U}_{t} \equiv ({\boldsymbol{V}^{\circ}_{t}}^\prime,{\boldsymbol{V}^{\star}_{t}}^\prime)^\prime$, with $\boldsymbol{V}^{\circ}_{t} \equiv \big({\boldsymbol{V}^{\circ}_{1,t}}^\prime,\dots,{\boldsymbol{V}^{\circ}_{K,t}}^\prime\big)^\prime$ and $\boldsymbol{V}^{\star}_{t} \equiv \big({\boldsymbol{V}^{\star}_{1,t}}^\prime,\dots,{\boldsymbol{V}^{\star}_{K,t}}^\prime\big)^\prime$. We denote by $m_1$ and $m_2$ the dimensions of $\boldsymbol{v}^{\circ}_k$ and $\boldsymbol{v}^{\star}_k$, respectively. For readability, we omit indexing $\boldsymbol{U}_{t}$ by $T$ and do not explicitly indicate the dimension $m = (m_1+m_2)\times K$ of the underlying components of $\boldsymbol{U}_{t}$.

We assume that $\boldsymbol{v}^{\circ}_k$ and $\boldsymbol{v}^{\star}_k$ satisfy, for all $k\in[K]$, $t = 1,\dots,T$, and under $\mathrm{P}^{(T)}_{\boldsymbol{\theta},\boldsymbol{0}}$,

and there exists $\delta > 0$ such that, for all $\boldsymbol{u}\in\mathbb{R}^{m}$,

Moreover, we impose the following assumption on the sampling policy, which states that $\boldsymbol{U}_{t-1}$ forms a sufficient statistic for the selection strategy at round $t$.

It is easily seen that, for each $T$, the process $\boldsymbol{U}_{t} = \boldsymbol{U}^{(T)}_{t}$, $t = 1,\dots,T$, is a time-homogeneous Markov chain, as $\boldsymbol{X}_{t}$ is independent of $\mathcal{F}_{t-1}$ and $Y_{t}$ is independent of $\mathcal{F}_{t-1}$ conditionally on $\boldsymbol{X}_{t}$ and $A_{t}$. In Proposition (ref), building on KWFG, we demonstrate that an appropriately time-changed version of $\boldsymbol{U}_{t}$ converges weakly to the solution of a system of stochastic differential equations.

We organize the proof for Proposition (ref) in Appendix (ref).

A sufficient condition for the existence of a unique solution to ((ref)) is that both $\boldsymbol{u} \mapsto \boldsymbol{\varpi}_k^{\star}(\boldsymbol{u})$ and $\boldsymbol{u} \mapsto \sqrt{\boldsymbol{\varpi}_k^{\circ}(\boldsymbol{u})}$ are Lipschitz continuous (see, e.g., Theorem 2.9 in Chapter 5.2 of karatzas2012brownian).

Likelihood representation of limit experiment

To fully leverage the limit experiment framework (see the detailed discussion at the end of this section), we establish joint convergence of the CMAB log-likelihood ratio, $\Lambda^{(T)}_{\boldsymbol{\theta},k}(\boldsymbol{h})$, along with the following two statistics

for $r_1, r_2\in\mathbb{R}$. Here, $\boldsymbol{U}^{\dagger}_{t} \equiv \left(({\boldsymbol{\Delta}_{k,t}}^\prime)_{k=1}^{K}, ({\boldsymbol{\mathcal{Q}}_{k,t}}^\prime)_{k=1}^{K}, ({\boldsymbol{C}_{r_1;k,t}}^\prime)_{k=1}^{K}, ({\boldsymbol{S}_{r_2;k,t}}^\prime)_{k=1}^{K}\right)^\prime$ collects all relevant statistics. These two statistics encompass both the quantities used by the sampling policy and those employed as test statistics in subsequent sections. For instance, in the non-contextual bandits setting (where $\boldsymbol{X}_{t} = 1$ for all $t$), $\boldsymbol{C}_{r_1=0;k,t}$ and $\boldsymbol{S}_{r_2=0;k,t}$ reduce to the re-scaled accumulated rewards and sampling frequencies, $R_{k, t}$ and $D_{k,t}$, respectively (see their definitions in ((ref)) below).

We define the sampling policy $\psi^{(T)}_k$ as a function of $\boldsymbol{U}^{\dagger}_{t}$ and the new incoming contextual observation $\boldsymbol{X}_{t+1}$. Applying Proposition (ref) then yields the following joint weak convergence result.

Part (a) demonstrates that the limiting log-likelihood ratio is quadratic in $\boldsymbol{h}$. Consequently, the limit experiment falls into the Locally Asymptotically Quadratic (LAQ) class of Jeganathan1995. However, due to the possible dependence between the integrand $\sqrt{\boldsymbol{\varpi}^{\vartriangle}_{k}(\tilde\boldsymbol{U}^{\dagger}(s))}$ and the integrator $\boldsymbol{W}_{k}(s)$, $\boldsymbol{\Delta}_{k}$ is generally not normally or mixed-normally distributed. Therefore, the limit experiment does not adhere to the traditional Locally Asymptotically Normal (LAN) or Locally Asymptotically Mixed Normal (LAMN) forms. This feature leads to non-standard behaviors of commonly-used test statistics, e.g., the Student's t-test, which phenomenon has been recently realized in the literature; see deshpande2018accurate, hadad2021confidence, and zhang2021statistical. Moreover, the limiting likelihood ratio does not satisfy the conditions for being Locally Asymptotically Brownian Functional (LABF) either, due to the presence of the $\boldsymbol{\mathcal{Q}}_k$-processes.

Structural representation of limit experiment

Part (c) of Proposition (ref) allows us to introduce a new collection of probability measures, denoted by $\mathbb{P}_{\boldsymbol{\theta},\boldsymbol{h}}$, with $\boldsymbol{h}\in\mathbb{R}^{p}$, via

i.e., the Radon-Nikodym derivative with respect to $\mathbb{P}_{\boldsymbol{\theta},\boldsymbol{0}}$. Now we formally define the limit experiment as

where the sample space is that of $\boldsymbol{W}_{k}$, $\boldsymbol{\mathcal{Q}}_{k}$, $\boldsymbol{W}_{\varepsilon_k}$, $\boldsymbol{C}_{r_1;k}$, and $\boldsymbol{S}_{r_2;k}$, defined as $\Omega \equiv C^{K}[0,1]$ and $\mathcal{F} \equiv \mathcal{B}(C^{K}[0,1])$, the Borel $\sigma$-field on $C^{K}[0,1]$.

Applying Girsanov's theorem, we have the following theorem.

Up to this point, we have developed the limit experiment for the bandit problem and its structural version formulated in SDEs. These results demonstrate that the bandit limit experiment $\mathcal{E}_{\boldsymbol{\theta}}$ corresponds to observing certain continuous-time processes $\boldsymbol{W}_{k}$, $\boldsymbol{\mathcal{Q}}_{k}$, $\boldsymbol{W}_{\varepsilon_k}$, and $\boldsymbol{S}_{r_2;k}$, $k\in[K]$, from a model $(\mathbb{P}_{\boldsymbol{\theta},\boldsymbol{h}} | \boldsymbol{h}\in\mathbb{R}^{p})$. We now illustrate how this limiting framework can be used to analyze the local asymptotic behavior of statistics and, consequently, the local asymptotic performance of inferential procedures. Such analyses typically require cumbersome `triangular array' limit theory. Fortunately, we can exploit the limit experiment to avoid this by invoking Le Cam's third lemma. This works as follows.

Suppose we are interested in studying the bandit problem around a specific value, $\boldsymbol{\theta}_0$, typically the value under the null hypothesis, though in some cases this choice may be inconsequential (see, e.g., the case of comparing arms in Sections (ref) and (ref)). To this end, we adopt the local reparameterization $\boldsymbol{\theta}_{T} = \boldsymbol{\theta}_0 + \boldsymbol{h}/\sqrt{T}$, which translates the hypotheses of the original bandit problem into those in the limit experiment derived above, $(\mathbb{P}_{\boldsymbol{\theta}_0,\boldsymbol{h}} | \boldsymbol{\theta}_0\in\boldsymbol{\Theta}, \boldsymbol{h}\in\mathbb{R}^{p})$, now characterized by $\boldsymbol{h}$. Consider a sequence of test statistics $\tau_T$ that satisfies, under $\mathrm{P}^{(T)}_{\boldsymbol{\theta}_0,\boldsymbol{0}}$ and for all $\boldsymbol{h}\in\mathbb{R}^p$,

for some functional $g$. Le Cam's third lemma (see, for example, van2000asymptotic) implies that, under $\mathrm{P}^{(T)}_{\boldsymbol{\theta}_0,\boldsymbol{h}}$,

In short, establishing ((ref)) for a given sequence of test statistics provides the full distributional behavior under local alternatives $\boldsymbol{h}$ via ((ref)). Notably, their asymptotic behaviors are explicitly described by the structural representation in ((ref)), expressed in SDEs, which can be readily simulated using an Euler scheme. In Sections (ref) and (ref) we will repeatedly leverage this property to study asymptotic validity and (local) asymptotic powers of commonly used and newly proposed test statistics.

Beyond facilitating the derivation of the (local) asymptotic behavior of test statistics, the limit experiment can also be used to obtain upper bounds on the (local) asymptotic power of asymptotically valid tests. The Asymptotic Representation Theorem (see, for example, van2000asymptotic) states that for any sequence of statistics that converges in distribution to a distribution $\mathcal{L}_{\boldsymbol{h}}$ under $\mathrm{P}^{(T)}_{\boldsymbol{h}}$ for all $\boldsymbol{h}$, there exists a (randomized) statistic $\tau$ in the limit experiment such that the distribution of $\tau$ under $\mathbb{P}_{\boldsymbol{h}}$ is given by $\mathcal{L}_{\boldsymbol{h}}$. Consequently, the best (asymptotic) procedure of $\mathcal{E}^{(T)}_{\boldsymbol{\theta}}$ are determined by the best procedure of $\mathcal{E}_{\boldsymbol{\theta}}$ for the same purpose. Building on this insight, we derive upper power bounds for both non-contextual and contextual bandit problems in the subsequent sections.

Statistical applications: non-contextual bandits

In this section, we consider the non-contextual multi-armed bandit (MAB) problem with two arms ($K = 2$). The potential outcomes for $k = 1,2$ are generated by

where the innovations $\varepsilon_{k,t}$ have mean zero, unit variance, and are independent across $k$ and $t$. Additionally, $\varepsilon_{k,t}$ are identically distributed across $t$. We denote the density of $\varepsilon_{k,t}$ by $f_k$ and impose Assumption (ref) on each $\mu \mapsto f_k(\cdot - \mu)$, with $\boldsymbol{\theta} = (\mu_1,\mu_2)$.

Our analysis focuses on equal-arms asymptotics, where the arms' (global) reward parameters $\mu_k$ are localized as

around a common value $\mu$. For $\mu = 0$, this corresponds to the weak-signal asymptotics in fan2025diffusion and kuang2024weak. We will see below that $\mu \neq 0$ leads to non-trivial adaptations in the asymptotic analysis relative to $\mu = 0$.

We consider two hypothesis testing problems. Section (ref) focuses on evaluating Arm $2$. Specifically, for a known $\mu_0\in\mathbb{R}$ such that $\mu_{1,T} = \mu_0 + \frac{m_1}{\sqrt{T}}$ and $\mu_{2,T} = \mu_0 + \frac{m_2}{\sqrt{T}}$, we aim to test

This hypothesis aims to detect small deviations from a known, common baseline mean $\mu_0$ for Arm $2$, while allowing Arm $1$ to exhibit small deviations, which can be interpreted as a robustness feature with respect to the local nuisance parameter $m_1$.\footnote{Instead of the one-sided alternative $m_2 > 0$, one could, of course, also consider $m_2 < 0$ or $m_2 \neq 0$. Additionally, one could consider a hypothesis in which $\mu_0$ is treated as a nuisance parameter. This, however, would complicate the analysis and is left for future research.} Section (ref) considers tests for comparing the two arms (e.g., treatment versus control). For that purpose, we introduce a convenient reparameterization, $\mu_{1,T} = \mu + \frac{m - \delta}{\sqrt{T}}$ and $\mu_{2,T} = \mu + \frac{m + \delta}{\sqrt{T}}$, at an unknown global parameter $\mu$. Then, $m$ and $\delta$ represents the common local reward parameter and the local difference parameter, respectively. The hypothesis of interest is

Section (ref) specializes the general results of Section (ref) to this non-contextual two-armed setting. Before moving on to inference, in Section (ref), we introduce the notion of translation-invariant sampling schemes in order to ensure that the sampling schemes $\psi^{(T)}_k$, $k=1,2$, satisfy Assumption (ref). Finally, we analyze and propose tests for the above two hypotheses. After discussing the test statistics, in Sections (ref) and (ref), we will also present an (asymptotic) upper bound on the power of (asymptotically) valid tests. Simulation results are presented separately for each case.

MAB limit experiment

Let $\mathrm{P}^{(T)}_{m_1,m_2}$ denote the law of $(A_{1},Y_{1},\dots,A_{T},Y_{T})$ under ((ref)), where for notational convenience we omit $\mu$ in our notation. The log-likelihood ratio is given by

By Proposition (ref), we have, for $k = 1,2$ and under $\mathrm{P}^{(T)}_{0,0}$,

with, for $t = 1,\dots,T$,

where, see Assumption (ref), $\dot\ell_{k} = -f^\prime_k/f_k$ and $J_{k} = \int_{\varepsilon}\dot\ell_{k}^2(\varepsilon)f_k(\varepsilon)\mathrm{d}\varepsilon$.

In this MAB problem, most existing sampling policies rely on the (re-scaled) accumulated rewards and arm pulls up to time $t$, defined as

respectively. That is, the probability of selecting Arm-$k$ at round $t+1$, given the information till time $t$, is a function of these statistics: $\pi_{t+1}(k|\mathcal{F}_{t}) = \psi_k^{(T)}(\boldsymbol{D}_{t}, \boldsymbol{R}_{t})$, where $\boldsymbol{R}_{t} = (R_{1,t},R_{2,t})^\prime$ and $\boldsymbol{D}_{t} = (D_{1,t},D_{2,t})^\prime$. Note that this structure may violate Assumption (ref) as $\boldsymbol{R}_{t}$ depends on the (unknown) parameter $\mu$. However, omitting the centering by $\mu$ from the definition of $\boldsymbol{R}_{t}$ is not feasible as our framework requires weak convergence of the input arguments $(\boldsymbol{D}_{t}, \boldsymbol{R}_{t})$ (embedded in an appropriate function space). To address this issue we impose, in Section (ref), a natural invariance condition on the sampling schemes. We also adjust classical sampling schemes to satisfy this condition and show, also by simulations, that the unadjusted versions lead to invalid tests in the sense that their size is not controlled.

The results of Section (ref) now imply that the two-armed bandit problem converges to a limit experiment with laws $\mathbb{P}_{m_1,m_2}$, as described below. In particular, we establish the joint convergence of the likelihood ratios with the following statistics,

where $\psi_{k,t}$ is a shorthand for $\psi_k^{(T)}(\boldsymbol{D}_{t-1}, \boldsymbol{R}_{t-1})$ and $r_1, r_2 \in \mathbb{R}$. These statistics serve as the non-contextual bandit counterparts of $\boldsymbol{C}_{r_1;k,t}$ and $\boldsymbol{S}_{r_2;k,t}$ defined in ((ref)), and are subsequently used to construct-test statistics in Sections (ref) and (ref). Note that $R_{k,t} = R^{\dagger}_{r_1=0;k,t}$ and $D_{k,t} = D^{\dagger}_{r_2=0;k,t}$ for all $k = 1,2$ and $t = 1,\dots,T$.

This limit experiment can, again following Section (ref), be described structurally in terms of stochastic differential equations.

To further streamline the exposition, the remainder of Section (ref) will focus on introducing the sampling scheme and statistics developed under the Gaussian assumption discussed in Remark (ref). Notably, the statistical properties generally hold without requiring Gaussianity. Although our results can be used to develop tests under more general distributional assumptions, this would involve more complicated notation and is left for future work.

Translation-invariant sampling schemes

Note that $\boldsymbol{R}_{t}$ depends on $\mu$ so that a sampling scheme based on $\boldsymbol{R}_{t}$ may inherently depend on $\mu$, thereby violating Assumption (ref). In order to satisfy Assumption (ref), we introduce the following translation-invariance restriction on the sampling schemes.

The translation invariant property in Definition (ref) leads to the following results.

One can easily derive a sufficient condition for a sampling scheme $\psi_k^{(T)}$ to be translation invariant. Observe

for any $c\in\mathbb{R}$. As a result, $\psi^{(T)}$ is translation invariant if, for $k=1,2$, $\psi_k^{(T)}\big(\boldsymbol{D}_{t},\boldsymbol{R}_{t}\big)$ is a function of $\boldsymbol{D}_{t}$ and $2\hat\delta_{t} \equiv R_{2,t}/D_{2,t} - R_{1,t}/D_{1,t}$ only. Note that $\hat\delta_{t}$ can be seen as an estimate for $\delta$ based on the data available at round $t$.

In Corollary (ref) below, we show that employing a sequence of translation-invariant sampling schemes $\psi_k^{(T)}$, $T\in\mathbb{N}$, based on $R_{2,t}/D_{2,t} - R_{1,t}/D_{1,t}$ also implies some distribution-freeness in the limit experiment.

Using these results, we can construct translation-invariant versions of classical Thompson, tempered-greedy, and tempered-UCB sampling. The prefix `tempered' refers to applying a softmax operation to the familiar greedy and UCB sampling schemes. Translation-invariant Thompson sampling has been used and discussed in kuang2024weak. The translation-invariant tempered-greedy sampling scheme is a modified version of the tempered-greedy scheme (see, e.g., kuang2024weak). In a similar fashion, we propose the translation-invariant tempered-UCB algorithm. To the best of our knowledge we are the first to formally introduce translation-invariant sampling schemes.

These algorithms are summarized in Table (ref), with detailed derivations provided in Appendix (ref). For all the three algorithms, we extend the definition of $\psi_k^{(T)}$ and $\psi_k$ to $\boldsymbol{d}\in[0,1]^2$ via continuous extension. Note that the pointwise convergence of $\psi_k^{(T)}$ to $\psi_k$ also holds true on the boundary. By applying Dini's theorem on suitable regions of $[0,1]^2\times\mathbb{R}^2$---i.e., on $\{ (d,r) : r_2 / d_2 - r_1 / d_1 > 0, d_1, d_2 > 0 \}$ and $\{ (d,r) : r_2 / d_2 - r_1 / d_1 < 0, d_1, d_2 > 0\}$---we can conclude that the convergence is uniform on compact subsets. In practice, we introduce a single initial draw from each arm in round $t = 1,2$ to ensure $D_{k,t} > 0$.

Hypothesis on a single arm

This subsection focuses on testing the hypothesis ((ref)) to evaluate Arm-$2$. Throughout this subsection and the next, which is dedicated to comparing arms, we impose the sequence of sampling schemes $\psi_k^{(T)}$, $k=1,2$, to be translation invariant as in Definition (ref). Again, for notational convenience, we abbreviate $\psi_k^{(T)}(\boldsymbol{D}_{t-1}, \boldsymbol{R}_{t-1})$---the sampling probability of Arm-$k$ for round $t$---as $\psi_{k,t}$, and $\psi_k(\boldsymbol{D}(u), \boldsymbol{R}(u))$ as $\psi_k(u)$ in this and the following subsection.

In Section (ref) we will exploit the structural MAB limit experiment (in ((ref))) and ((ref))--((ref)) in particular to study asymptotic distributions of commonly-used test statistics. We will analyze three test statistics that are natural to consider for the MAB problem: the classical Student's t statistic, the Adaptively-Weighted (AW) statistic by zhang2021statistical, and a statistic based on Inverse Propensity Weighting (IPW) as studied in, for example, hadad2021confidence.

It turns out that only the AW test statistic is asymptotically distribution-free with respect to $m_1\in\mathbb{R}$ under the null. For this test statistic it thus is trivial to obtain a critical value that yields an asymptotically valid test. For the other test statistics, the asymptotic null distribution depends on $m_1$ (which, being a parameter at the contiguity rate, cannot be estimated consistently). As such it is unclear, and perhaps even impossible, to obtain asymptotically valid tests from these statistics. Hence, perhaps surprisingly, the t-test and IPW test cannot be used---assuming one insists on (asymptotic) validity of tests---for testing hypothesis ((ref)). After our discussion of the test statistics, we will also present an upper bound to the (local) asymptotic power of asymptotically valid tests. Finally, in Section (ref), we will provide simulation results that corroborate our theoretical results.

Test statistics

Student's t-test

Using $\mu=\mu_0$ in the definition of $R_{2,T}$ (and exploiting known unit variance), the classical Student's t statistic is given by

Ancillary (ref) yields that the joint convergence in ((ref)) holds. Specifically, under $\mathrm{P}^{(T)}_{0,0}$, we have $\left(\tau_T^{\text{t}}, \log\left(\mathrm{d}\mathrm{P}^{(T)}_{m_1,m_2}/\mathrm{d}\mathrm{P}^{(T)}_{0,0}\right)\right) \Rightarrow \left(\tau^{\text{t}}, \log\left(\mathrm{d}\mathbb{P}_{m_1,m_2}/\mathrm{d}\mathbb{P}_{0,0}\right) \right)$, where $\tau^{\text{t}} \equiv R_2(1)/\sqrt{D_2(1)}$. Invoking Le Cam’s third lemma, see ((ref)), yields, under $\mathrm{P}^{(T)}_{m_1,m_2}$ for all $m_1,m_2\in\mathbb{R}$, $\tau_T^{\text{t}} \Rightarrow \tau^{\text{t}}$, where the behavior of $R_2$ and $D_2$ is characterized by the SDEs in ((ref)). The distribution of $\tau^{\text{t}}$ under $\mathbb{P}_{m_1,m_2}$ thus is

We make two observations: First, the distribution of $\tau^{\text{t}}$ is generally not normal. This is because, in $\int_0^1\sqrt{\psi_2(u)}\mathrm{d}B_{\varepsilon_2}(u)$, the integrand process $\sqrt{\psi_2(u)} = \sqrt{\psi_2(\boldsymbol{D}(u),\boldsymbol{R}(u))}$ depends on the process $\boldsymbol{R}(u)$, which in turn depends on the integrator process $B_{\varepsilon_2}(u)$. This is the same reason as why the MAB limit experiment is not normal. This result has been documented in recent literature, including deshpande2018accurate, zhang2020inference and hadad2021confidence. Second, under the null hypothesis where $m_2 = 0$ and $m_1\in\mathbb{R}$, $\tau^{\text{t}}$ is not distribution-free with respect to $m_1$, as $m_1$ influences $R_1(u)$, which in turn affects $\psi_2(\boldsymbol{D}(u),\boldsymbol{R}(u))$. We provide Monte Carlo evidence based on simulations of the SDEs in ((ref)), showing that the null distribution of $\tau^{\text{t}}$ indeed varies with $m_1$ (see Figure (ref) and Figure (ref)). To the best of our knowledge, we are the first to highlight this issue, which becomes evident through the structural limit experiment.

Adaptively-Weighted (AW) test

Adaptively-Weighted statistics for bandits were introduced, in the context of M-estimators, by zhang2021statistical. Using $\mu=\mu_0$ and $r_1 = 1/2$ in the definition of $R^{\dagger}_{r_1;2,T}$, we consider a simple version of AW test statistic defined as\footnote{The general version of the AW statistic is given by $\tau^{\text{AW}}_{T}(\varphi) \equiv \frac{1}{\widebar\varphi_2} \sum_{t=2}^{T}\sqrt{\frac{\varphi_2\left((t-1)/T \right)}{\psi_{2,t-1}}}(R_{2,t} - R_{2,t-1})$, where $\varphi_2: [0,1] \to [0,1]$ is a so-called variance stabilizing policy which is deterministic for which $\widebar\varphi_2 = \int_0^1\varphi_2(u)\mathrm{d}u$ is well-defined. In this sense, the simple version corresponds to $\varphi_1(u) = \varphi_2(u) = 1/2$, $u\in[0,1]$.} \[ \tau^{\text{AW}}_{T} \equiv R^{\dagger}_{r_1=\frac{1}{2};2,T} = \frac{1}{\sqrt{T}}\sum_{s=1}^{t} \frac{\mathbbm{1}_{\{A_{s} = k\}}}{\sqrt{\psi_{k,s}}}(Y_{s} - \mu) \] By Ancillary (ref), ((ref)) holds for the AW statistic. That is, under $\mathrm{P}^{(T)}_{0,0}$, $\big(\tau_T^{\text{AW}}, \log\big(\mathrm{d}\mathrm{P}^{(T)}_{m_1,m_2}/\mathrm{d}\mathrm{P}^{(T)}_{0,0}\big)\big) \Rightarrow \big(\tau^{\text{AW}}, \log(\mathrm{d}\mathbb{P}_{m_1,m_2}/\mathrm{d}\mathbb{P}_{0,0})\big)$, where

Then, invoking Le Cam's third lemma and according to ((ref)), the distribution of $\tau^{\text{AW}}$ under $\mathbb{P}_{m_1,m_2}$ can be represented by

Note that $B_{\varepsilon_2}$ is a standard Brownian motion for all $m_1, m_2\in\mathbb{R}$. Consequently, under the null ($m_2=0$), $\tau^{\text{AW}}$ follows a standard normal distribution regardless of the value of $m_1$, making it distribution-free (with respect to $m_1$). This makes it trivial to obtain a critical value that yields an asymptotically valid test. Moreover, ((ref)) demonstrates that the (local) asymptotic power increases with $m_2$, the local reward parameter, as well as $\int_0^1\sqrt{\psi_2(u)}\mathrm{d}u$, a random term that becomes larger when Arm $2$ is sampled more frequently. This random term leads, in general, to a non-Gaussian distribution for the AW statistic under the alternative (i.e., for $m_2\neq 0$).

Inverse Propensity Weighted (IPW) test

The last statistic we study is based on another commonly used idea, namely Inverse Propensity Weighting (IPW). Now using $r_1 = 1$ in the definition of $R^{\dagger}_{r_1;2,T}$, the IPW test for the hypothesis of interest is given by \[ \tau^{\text{IPW}}_T = R^{\dagger}_{r_1=1;2,T} = \frac{1}{\sqrt{T}}\sum_{s=1}^{t} \frac{\mathbbm{1}_{\{A_{s} = k\}}}{\psi_{k,s}}(Y_{s} - \mu) \] Again, Ancillary (ref) implies ((ref)). That is, under $\mathrm{P}^{(T)}_{0,0}$ and for all $m_1,m_2\in\mathbb{R}$, $\big(\tau_T^{\text{IPW}}, \log\big(\mathrm{d}\mathrm{P}^{(T)}_{m_1,m_2}/\mathrm{d}\mathrm{P}^{(T)}_{0,0}\big)\big) \Rightarrow \big(\tau^{\text{IPW}}, \log(\mathrm{d}\mathbb{P}_{m_1,m_2}/\mathrm{d}\mathbb{P}_{0,0})\big)$, where

Display ((ref)) implies that the asymptotic distribution of $\tau^{\text{IPW}}_T$ under $\mathrm{P}^{(T)}_{m_1,m_2}$ is given by

Based on the SDEs in ((ref)) and the same reasoning as for the Student's t statistic, the asymptotic distribution of $\tau_T^{\text{IPW}}$ under $\mathrm{P}^{(T)}_{m_1,0}$ appears to be neither normal nor distribution-free with respect to $m_1$ under the null hypothesis. A formal proof of these conjectures is, however, difficult to obtain. Figure (ref) presents a Monte Carlo approximation of the distribution of $\tau^{\text{IPW}}$ for $m_1=m_2=0$ and $m_1=10,$ $m_2=0$, providing clear evidence that the asymptotic null distribution indeed varies with $m_1$ and is non-Gaussian.

An upper bound to the (local) asymptotic power

Recall from the discussion at the start of this section that an upper bound to the power of valid tests in the limit experiment yields, via the asymptotic representation theorem, an upper bound to the local asymptotic power of asymptotically valid tests.

Consider, in the limit experiment and for fixed $\bar{m}_1,\bar{m}_2\in\mathbb{R}$, the auxiliary hypothesis $H_0 : (m_1,m_2) = (\bar{m}_1,0)$ versus $H_1 : (m_1,m_2) = (\bar{m}_1,\bar{m}_2)$. The Neyman-Pearson test statistic for this hypothesis is given by

Letting $\kappa^*_{\alpha}=\kappa^*_{\alpha}(\bar{m}_1, \bar{m}_2)$ denote the $1-\alpha$ quantile of $\tau^{\text{NP}}$ under $\mathbb{P}_{\bar{m}_1,0}$, the power, at $\mathbb{P}_{\bar{m}_1,\bar{m}_2}$, of $\tau^{\text{NP}}$ is given by

Since the Neyman-Pearson test is the most powerful test for the auxiliary hypothesis, it easily follows that the asymptotic power of an asymptotically valid test, under $\mathrm{P}^{(T)}_{m_1,m_2}$ with $m_2 > 0$ and $m_1\in\mathbb{R}$, is bounded from above by $\Upsilon_{\alpha}^*(m_1, m_2)$. However, it remains unclear whether this upper bound is sharp (i.e., attainable by some feasible asymptotically valid test). In Figure (ref) we will see that the local asymptotic power of the AW test lies very close to this upper bound.

Simulation results

In this section, we corroborate out theoretical results via Monte Carlo simulations. We study both the size and power properties of the test statistics. We consider $T = 200$ for the finite-sample distributions. To approximate distributions of statistics in the limit experiment (which reflect asymptotic distributions of statistics in the sequence), we simulate the SDEs ((ref)) via an Euler scheme on a grid with $100$ points. Throughout this analysis, we maintain a significance level of $\alpha = 5\%$ and all results are based on $50,000$ replications.

We consider the three translation-invariant sampling schemes introduced in Section (ref). Specifically, we implement the translation-invariant Thompson algorithm with $b = 1/20$, the translation-invariant tempered-greedy algorithm with $\alpha = 1$, and the translation-invariant tempered-UCB algorithm with $\alpha = 1$ and $\delta = 1$. Additionally, we include the original Thompson sampling scheme (also with $b = 1/20$) in order to show how non-translation-invariant algorithms may result in invalid tests.

Null distributions

Figure (ref) presents histograms of arm-pulling frequencies and the one-arm t, AW, and IPW statistics (from left to right) for the structural limit experiment under translation-invariant Thompson sampling scheme. The upper panel corresponds to the setting $(m_1,m_2) = (0,0)$, while the lower panel corresponds to $(m_1,m_2) = (10,0)$. Both settings are thus under the null $m_2 = 0$. The results confirm the two key observations in Section (ref). First, neither the t nor the IPW statistic follows a normal distribution when the data is adaptively collected. Second, comparing the upper and lower panels indicates that the distributions of the t and IPW statistics vary with changes in the nuisance parameter $m_1$, demonstrating that these statistics are not distribution-free w.r.t.\ $m_1$ under the null. In contrast, the AW statistic consistently exhibits a standard normal distribution, regardless of the value of $m_1$, corroborating our theoretical result that this statistic is distribution-free w.r.t.\ $m_1$.

To further illustrate these points, Figure (ref) plots the associated empirical cumulative distribution functions (CDFs) alongside the standard normal CDF (black dotted). Solid and dashed lines correspond to $(m_1,m_2) = (0,0)$ and $(m_1,m_2) = (10,0)$, respectively. We see a clear distinction of the red and blue solid lines compared to the dashed ones, showing that the t and IPW statistics are not distribution-free w.r.t.\ $m_1$, and all of them deviate from the standard normal CDF. Conversely, the CDF of the AW statistic (green) perfectly matches the standard normal CDF in both cases.

Finally, we present the same histograms but from a finite-sample two-armed bandit experiment with $T = 200$ rounds in Figure (ref), serving as the finite-sample counterpart to Figure (ref). A comparison of the two figures demonstrates that the limit experiment provides a good approximation of the finite-sample MAB experiments. Some noticeable deviations appear in the lower panel relative to its asymptotic counterpart in Figure (ref), mainly due to limited sampling of Arm-2, but additional (unreported) simulations confirm that increasing $T$ further diminishes these differences.

We report size results for the valid one-arm AW test in Table (ref) in Appendix (ref).

Power results

As only the AW test is asymptotically valid, we will only consider this statistic in the power analysis, together with the upper bound provided by the oracle NP test.

Figure (ref) displays the asymptotic power when the nuisance parameter $m_1 = 0$\footnote{Note that the AW test is distribution-free with respect to $m_1$ only under the null hypothesis; consequently, its power still depends on $m_1$.} of the AW test (dashed), alongside the power upper bound provided by the oracle NP test (solid lines), under the three translation-invariant algorithms introduced in Section (ref). First, we observe that the power varies across algorithms. Specifically, when an algorithm places greater emphasis on exploration (e.g., the TI Thompson sampling), the resulting power tends to be higher; conversely, more exploitative algorithms tend to yield lower power.\footnote{Unreported results, based on varying the tuning parameters within each sampling algorithm to adjust the exploration–exploitation trade-off, further support this observation.} Second, the AW test exhibits a slight loss in power compared to the oracle bound under all three algorithms, with this gap becoming slightly more pronounced as the algorithm leans toward exploitation (e.g., the tempered-greedy algorithm).

In Figure (ref), we examine how well the asymptotic power---simulated using the limit experiment---approximates that of the finite-sample MAB experiment. Specifically, for the three translation-invariant algorithms (in different colors), we consider sample sizes equal to $T=50$ (dotted), $T=100$ (dash-dotted), and $T=200$ (dashed). In all cases, we find that the asymptotic power closely approximates the finite-sample results, with the differences diminishing as the sample size increases. Notably, power convergence appears more immediate for TI Thompson sampling, which places greater weight on exploration, with the finite-sample and asymptotic powers nearly coinciding. That said, convergence is also rapid for the tempered-greedy and tempered-UCB algorithms: with just 200 observations, the finite-sample power already aligns with the asymptotic power curves. At last, we observe that the convergence of the finite-sample power curves to their asymptotic versions is not necessarily monotonic from below. While there is no theoretical reason that it should be, this seems to be yet another uncommon feature of the MAB problem.

Tests for comparing two arms

A potentially more intriguing question involves determining superior performance of one arm over the other (e.g., treatment versus control). Recall the reparameterization $m_1 = m - \delta$ and $m_2 = m + \delta$, we can rewrite the limit experiment SDEs ((ref)) associated with processes $R^{\dagger}_{r_1;k}$ as

For the hypothesis of interest in ((ref)), namely $H_0: \delta = 0$ against $H_1: \delta > 0$, treating the common local reward parameter $m$ as a nuisance parameter, we focus on test statistics that are distribution-free with respect to the unknown local parameter $m$. In particular, we first propose a family of such distribution-free test statistics, which gives rise to two-sample versions of the Student's t, AW, and IPW statistics. Notably, the finite-sample version of this family is, by design, also distribution-free with respect to the global common reward parameter $\mu$---a desirable property in practice. We also derive an upper bound on the power of asymptotically valid tests. All corresponding simulation results are reported in Section (ref).

Test statistics

Distribution-free two-sample statistic family

Let $r_1 = r_2 = r$ in definitions of $R^{\dagger}_{r_1;k,T}$ and $D^{\dagger}_{r_2;k,T}$ in ((ref)), the family of tests that is distribution-free with respect to $m$ is based on

which weakly converges to

The distribution-freeness with respect to $m$ is easily seen as, using ((ref)),

for $k = 1,2$, under any translation-invariant sampling scheme $\psi_k(u)$ (Corollary (ref)). Thus, $m$ cancels out in $\tau^{\text{TS-DF}}(r)$ for all $r\in\mathbb{R}$.

It is also easy to observe

Likewise, $\mu$ cancels out in ((ref)) for all $r\in\mathbb{R}$, making $\tau^{\text{TS-DF}}_{r;T}$ distribution-free with respect to the global common reward parameter $\mu$.

This class leads to distribution-free two-sample t, AW, and IPW tests, for the case of $r = 0$, $1/2$, and $1$, respectively, as follows.

Two-sample Student's t-test

The classical two-sample Student's t-test (with known, unit variances) corresponds to the case of $r = 0$, where $R^{\dagger}_{0;k,t} = R_{k,t}$, $D^{\dagger}_{0;k,t} = D_{k,t}$ and $\tau^{\text{TS-DF}}_{0;T} = R_{2,T}/D_{2,T} - R_{1,T}/D_{1,T}$. Specifically, define

which weakly converges to

The distribution of the numerator of $\tau^{\text{TS-t}}$ under $\mathbb{P}_{m_1,m_2}$ is given by \[ \mathcal{L}\left( 2\delta + \frac{\int_0^1\sqrt{\psi_2(u)}\mathrm{d}B_{\varepsilon_2}(u)}{\int_0^1\psi_2(u)\mathrm{d}u} - \frac{\int_0^1\sqrt{\psi_1(u)}\mathrm{d}B_{\varepsilon_1}(u)}{\int_0^1\psi_1(u)\mathrm{d}u} | \mathbb{P}_{m_1,m_2} \right). \] For the same reason of the one-arm t statistic---namely the dependence of processes $\sqrt{\psi_k}$ and $B_{\varepsilon_k}$ for both $k = 1,2$---$\tau^{\text{TS-t}}$ is generally not normally distributed.

Two-sample AW test

The two-sample AW statistic corresponds to $r = 1/2$, in particular, a standardized version of $\tau^{\text{TS-DF}}_{1/2;T}$. Define \[ \tau_T^{\text{TS-AW}} \equiv \left(\frac{R^{\dagger}_{1/2;2,T}}{D^{\dagger}_{1/2;2,T}} - \frac{R^{\dagger}_{1/2;1,T}}{D^{\dagger}_{1/2;1,T}}\right) \bigg/ \sqrt{\frac{1}{(D^{\dagger}_{1/2;2,T})^2} + \frac{1}{(D^{\dagger}_{1/2;1,T})^2}} \] which weakly converges to

The distribution of the nominator of $\tau^{\text{TS-AW}}$ under $\mathbb{P}_{m_1,m_2}$ is given by \[ \mathcal{L}\left( 2\delta + \frac{B_{\varepsilon_2}(1)}{\int_0^1 \psi_2^{-1/2}(u)\mathrm{d}D_{2}(u)} - \frac{B_{\varepsilon_1}(1)}{\int_0^1 \psi_1^{-1/2}(u)\mathrm{d}D_{1}(u)} | \mathbb{P}_{m_1,m_2} \right). \] After standardization by the denominator, we find the TS-AW statistic, $\tau^{\text{TS-AW}}$, to be (close to) normally distributed. However, a formal proof that its distribution is standard normal, is challenging to obtain. Therefore, we instead provide simulation evidence in the next subsection.

Two-sample IPW test

The two-sample IPW statistic, based on $\tau^{\text{TS-DF}}(1)$, is defined as

which weakly converges to

noting that the denominators equal one as $\int_0^1\psi_k^{-1}(u)\mathrm{d}D_{k}(u) = 1$ for $k = 1,2$.

The distribution of $\tau^{\text{TS-IPW}}$ under $\mathbb{P}_{m_1,m_2}$ is given by \[ \mathcal{L}\left( 2\delta + \int_0^1\psi_2^{-1/2}(u)\mathrm{d}B_{\varepsilon_2}(u) - \int_0^1\psi_1^{-1/2}(u)\mathrm{d}B_{\varepsilon_1}(u) | \mathbb{P}_{m_1,m_2} \right), \] which is generally not normal as the processes $\psi_k^{-1/2}$ and $B_{\varepsilon_k}$ are dependent.

An upper bound to asymptotic power of valid tests

For this case of comparing the two arms, we also provide an upper bound on the power of asymptotically valid tests. Specifically, consider the auxiliary hypothesis $H_0 : \delta = 0, \, m = \bar{m}$ versus $H_1 : \delta = \bar\delta, \, m = \bar{m}$. The associated Neyman-Pearson test statistic for this hypothesis is given by

Let $\kappa^{**}_{\alpha}$ denote the $1-\alpha$ quantile of $\tau^{\text{TS-NP}}$ under $\mathbb{P}_{\bar{m}, \bar{m}}$. Then the power of $\tau^{\text{TS-NP}}$ at $\mathbb{P}_{\bar{m}-\bar\delta,\bar{m}+\bar\delta}$ is given by

Then, the Neyman-Pearson lemma implies that the asymptotic power of an asymptotically valid test under $\mathrm{P}^{(T)}_{m-\delta,m+\delta}$, for $\delta > 0$ and $m\in\mathbb{R}$, is bounded above by $\Upsilon_{\alpha}^{**}(m, \delta)$. However, as is the case of evaluating Arm-$2$ (Section (ref)), it remains unclear whether this upper bound is sharp.

Simulation results

We validate the asymptotic results of the test statistics introduced in Section (ref) above through simulations. The setting is the same as in Section (ref).

Null distributions

Figure (ref) displays histograms of arm-pulling frequencies and the two-sample (TS) t, AW, and IPW statistics (from left to right), simulated under the structural limit experiment with translation-invariant Thompson sampling. The top and bottom panels correspond to $m = 0$ and $m = 50$, respectively, both under the null $\delta = 0$. We observe that all histograms remain unchanged as $m$ varies. This confirms that using translation-invariant Thompson sampling scheme makes these statistics distribution-free w.r.t.\ $m$. Among them, only the TS-AW statistic appears normally distributed, while the TS-t and TS-IPW statistics exhibit clear deviations from normality.

Figure (ref) examines the impact of non-translation-invariant sampling schemes on the test statistics. Specifically, we replicate the analysis from Figure (ref), but using classical Thompson sampling, which is not translation invariant (see the discussion in Section (ref)). We first observe that the arm-pulling frequency histogram changes substantially when $m$ shifts from $0$ to $50$. Moreover, the distributions of the TS-t and TS-IPW statistics exhibit significant changes. These findings underscore the importance of employing translation-invariant sampling schemes---in addition to distribution-free statistics---for valid post-inference. Notably, the two-sample AW statistic remains approximately normally distributed even under non-translation-invariant sampling schemes and across different values of $m$. We provide size results for the two-sample t-test, AW test, and IPW test in Table (ref) of Appendix (ref).

Power results

Figure (ref) plots the power curves of three two-sample distribution-free tests---namely, the TS-t-test (red), the TS-AW test (blue), and the TS-IPW test (green)---under translation-invariant Thompson sampling (dashed), the tempered-greedy algorithm (dash-dotted), and the tempered-UCB algorithm (dotted). The same observation made in the single-arm evaluation case holds here: sampling schemes that favor exploration lead to higher asymptotic power across all three tests. That said, the power gain of tempered-UCB over tempered-greedy is less pronounced in this two-arm comparison setting. Nonetheless, unreported simulation results indicate that increasing the degree of exploration (by adjusting the hyperparameter) in the tempered-UCB algorithm can improve its power performance.

Figure (ref) presents the asymptotic power (solid lines) and finite-sample power under $\boldsymbol{b} = (0,0)^\prime$ for $T=100$ (dotted), $T=200$ (dash-dotted), and $T=500$ (dashed) of the TS-t-test (red), the TS-AW test (blue), and the TS-IPW test (green), under translation-invariant Thompson sampling. Comparing the asymptotic powers, we find that the TS-t-test achieves significantly higher power than the other two, with the TS-IPW test as the runner-up, and the TS-AW test exhibiting the lowest power---likely due to the trade-off associated with achieving normality under the null hypothesis. Turning to power convergence, the finite-sample power of both the TS-t and TS-IPW tests approaches their asymptotic counterparts fairly quickly, especially for the TS-t-test, where the convergence is nearly immediate. In contrast, the TS-AW test requires a much larger sample size to approach its asymptotic power.

Statistical applications: contextual bandits

In this section, we consider a contextual two-armed bandit problem, where the potential reward of Arm-$k$ at round $t$ follows the linear model

Here, $\boldsymbol{X}_{t} = (X_{1,t},\dots,X_{p,t})^\prime$ represents i.i.d.\ contextual random variables with non-singular $\mathbb{E}\left[\boldsymbol{X}_t\boldsymbol{X}_t^\prime\right]$, and which are independent of the innovation term $\varepsilon_{k,t}$. As before, these $\varepsilon_{k,t}$ are independent across arms and rounds, with mean zero, unit variance, and density $f_k$. A constant term can be incorporated by setting $X_{1,t} = 1$ for all $t$, (for $p=1$ this yields the MAB setup studied in Section (ref)).

For this contextual bandit problem, we consider equal-arms asymptotics where the parameters $\boldsymbol{\beta}_{k}$ are localized around a common parameter vector $\boldsymbol{\beta}\in\mathbb{R}^p$ as

Using the reparameterization $\boldsymbol{b}_1 = \boldsymbol{b}$ and $\boldsymbol{b}_2 = \boldsymbol{b} + \boldsymbol{\zeta}$, in this linear CMAB problem, we focus on testing the following linear hypothesis to compare the two arms

for a given vector $\mathbf{G}\in\mathbb{R}^{p}$, while treating $\boldsymbol{b}$ as a nuisance parameter. This hypothesis is commonly used to compare the predictions $\mathbf{G}^\prime\boldsymbol{b}_1$ and $\mathbf{G}^\prime\boldsymbol{b}_2$---e.g., for treatment versus control in an individual with covariates (or features) recorded in vector $\mathbf{G}$.

As in Section (ref), we begin by applying our general results from Section (ref) to the contextual setting (Section (ref)), followed by the introduction of three translation-invariant sampling schemes (Section (ref)). We then study the testing problem in (ref) theoretically and support the findings with simulations in Section (ref).

CMAB limit experiment

Denote by $\mathrm{P}^{(T)}_{\boldsymbol{b}_1,\boldsymbol{b}_2}$ the law of $(\boldsymbol{X}_{1},\dots,\boldsymbol{X}_{T},A_{1},\dots,A_{T},Y_{1},\dots,Y_{T})$ generated by this linear CMAB problem. The log-likelihood ratio is

In case Assumptions (ref)--(ref) hold, by Proposition (ref), we have, under $\mathrm{P}^{(T)}_{\boldsymbol{0},\boldsymbol{0}}$,

with

for $t = 1,\dots,T$ and $k = 1,2$, where $\dot\ell_{k} \equiv -\dot{f_k}/f_k$ is again the score function for location and $J_k \equiv \int_\varepsilon\dot\ell_{k}(\varepsilon)^2f_k(\varepsilon)\mathrm{d}\varepsilon$ is its Fisher information.

In the linear CMAB problem, most existing sampling policies rely on

where $\boldsymbol{C}_{r_1;k,t}$ and $\boldsymbol{S}_{r_2;k,t}$ are defined in ((ref)) (with $\mathbb{E}_{\boldsymbol{\theta}}[Z_{k}] = \boldsymbol{X}_s^\prime\boldsymbol{\beta}$). In particular, applications often use $\hat\boldsymbol{b}_k \equiv \boldsymbol{S}_{k,t}^{-1}\boldsymbol{C}_{k,t}$ which can be interpreted as the estimate for $\boldsymbol{b}_k$ based on the information available at time $t$. This estimate, in turn, provides the predicted reward $\boldsymbol{X}_{t+1}^\prime\hat\boldsymbol{b}_k$ for round $t+1$. We impose that the probability of selecting Arm-$k$ at time $t+1$ is given by

where $\boldsymbol{C}_{t} = \left(\boldsymbol{C}_{1,t}^\prime,\boldsymbol{C}_{2,t}^\prime\right)^\prime$ and $\boldsymbol{S}_{t} = \left(\boldsymbol{S}_{1,t}^\prime,\boldsymbol{S}_{2,t}^\prime\right)^\prime$. Note, however, that $\boldsymbol{C}_{k,t}$ depends on $\boldsymbol{\beta}$, which may cause the resulting sampling policy to violate Assumption (ref). In order to satisfy Assumption (ref), we will impose a translation-invariance restriction on the sampling schemes in Section (ref). This mirrors the analysis of Section (ref).

The results in Section (ref) now imply that the two-armed contextual bandit problem converges to a limit experiment with laws $\mathbb{P}_{\boldsymbol{b}_1,\boldsymbol{b}_2}$, as described below.

Translation-invariant sampling schemes

We introduce the following translation-invariance requirement on sampling schemes for the linear contextual bandit problem. In Section (ref), we will demonstrate that this restriction helps to control the size of tests when comparing different arms.

We also identify a sufficient condition for a sampling scheme $\psi^{(T)}_k$ in this linear CMAB problem to be translation invariant. To illustrate this, consider algorithms based on difference $\boldsymbol{\beta}_{2,T} - \boldsymbol{\beta}_{1,T} = (\boldsymbol{b}_{2} - \boldsymbol{b}_{1})/\sqrt{T}$, which remains unchanged under any transformation that adds the same vector to both $\boldsymbol{\beta}_{1,T}$ and $\boldsymbol{\beta}_{2,T}$. Specifically, $\psi^{(T)}_k$ is translation invariant with respect to the common value $\boldsymbol{\beta}$ (where we localize our parameters) if it only depends on $\boldsymbol{X}_{t+1}$, $\boldsymbol{S}_{t}$, and $\hat\boldsymbol{\zeta}_{t} = \hat\boldsymbol{b}_{2,t} - \hat\boldsymbol{b}_{1,t} = \boldsymbol{S}_{2,t}^{-1}\boldsymbol{C}_{2,t} - \boldsymbol{S}_{1,t}^{-1}\boldsymbol{C}_{1,t},$ the latter being an estimate of $\boldsymbol{\zeta}$ ($= \boldsymbol{b}_{2} - \boldsymbol{b}_{1}$) based on the information available up to round $t$. Indeed, for any $\boldsymbol{e}\in\mathbb{R}^{p}$, we have

Similarly, we next state that using a sequence of translation-invariant sampling schemes $\psi_k^{(T)}$, $T\in\mathbb{N}$, based on $\hat\boldsymbol{\zeta}_{t}$, also leads to distribution-freeness with respect to $\boldsymbol{b}$ in the limit experiment. The proof is omitted, as it follows from arguments similar to those in Corollary (ref).

Building on these results, we propose---to the best of our knowledge, for the first time---translation-invariant versions of Thompson sampling, tempered-greedy, and tempered-LinUCB algorithms for the linear CMAB problem, as summarized in Table (ref). Detailed derivations are provided in Appendix (ref). Due to space constraints, we omit the fourth column showing the limiting policy functions $\psi_k$; these are simply the finite-sample policies $\psi_k^{(T)}$ with hyperparameters replaced by their limiting values according to the third column.

Tests for comparing the two arms

For the hypothesis of interest in ((ref)), namely, $H_0:\mathbf{G}^\prime\boldsymbol{\zeta} = 0, \, \boldsymbol{b}\in\mathbb{R}^{p} \textrm{~against~} H_1:\mathbf{G}^\prime\boldsymbol{\zeta} > 0, \, \boldsymbol{b}\in\mathbb{R}^{p},$ we focus on test statistics that are distribution-free, under the null hypothesis, with respect to the nuisance local common reward parameter $\boldsymbol{b}$. In particular, Section (ref) introduces the two-sample Wald and the Adaptively-Weighted (AW) Wald statistics, the latter of which is shown to be (close to) normally distributed in simulations. We omit the Inverse Propensity Weighted (IPW) version of the Wald statistic, as it tends to have lower power than the standard Wald test and does not exhibit the approximate normality of the AW-Wald statistic. We also omit the upper power bounds, which---as in the non-contextual bandit case in Section (ref)---lie well above the powers of tests that are distribution-free with respect to the nuisance parameter $\boldsymbol{b}$.

Test statistics

Two-sample Wald test

The classical two-sample Wald statistic for the linear model is given by

where $\hat\boldsymbol{\zeta}_{t} = \boldsymbol{S}_{2,t}^{-1}\boldsymbol{C}_{2,t} - \boldsymbol{S}_{1,t}^{-1}\boldsymbol{C}_{1,t}$ estimates $\boldsymbol{\zeta}$ based on data available up to round $t = 1,\dots,T$. From the joint convergence result in Ancillary (ref), we have $\hat\boldsymbol{\zeta}_{T} \Rightarrow \tilde\boldsymbol{\zeta}(1) \equiv \boldsymbol{S}_{2}(1)^{-1}\boldsymbol{C}_{2}(1) - \boldsymbol{S}_{1}(1)^{-1}\boldsymbol{C}_{1}(1)$. Consequently,

As shown in Section (ref), the limit statistic $\tau^{\text{TS-Wald}}$ is distribution free under the null hypothesis with respect to the nuisance local parameter $\boldsymbol{b}$.

Le Cam’s third lemma ((ref)) and the limit experiment ((ref)) yield, under $\mathbb{P}_{\boldsymbol{b},\boldsymbol{b}+\boldsymbol{\zeta}}$, $\tilde\boldsymbol{\zeta}(1)$ follows distribution

Thus, the distribution of $\tau^{\text{TS-Wald}}_T(\mathbf{G})$ under $\mathbb{P}_{\boldsymbol{b},\boldsymbol{b}+\boldsymbol{\zeta}}$ is characterized accordingly. However, this distribution is generally not normal, due to the nonzero correlation between the integrand process $\sqrt{\boldsymbol{\varpi}_k(u)} = \sqrt{\mathbb{E}[\psi_k(\boldsymbol{S}(u), \boldsymbol{C}(u), \boldsymbol{X})\boldsymbol{X}\boldsymbol{X}^\prime]}$ (here the expectation is only taken over $\boldsymbol{X}$) and the integrator Brownian motion $\boldsymbol{B}_{\varepsilon_k}(u)$.

Two-sample Adaptively-Weighted Wald test

The Adaptively-Weighted (AW) version of Wald statistics is based on statistics $\boldsymbol{C}_{\frac{1}{2};k,t}$ and $\boldsymbol{S}_{\frac{1}{2};k,t}$ (i.e., $r_1 = r_2 = \frac{1}{2}$), $k = 1,2$. Their asymptotic behavior, according to the limit experiment ((ref)), is characterized by

This motivates the (limiting) AW estimator for $\boldsymbol{\zeta}$, defined as

whose distribution under $\mathbb{P}_{\boldsymbol{b},\boldsymbol{b}+\boldsymbol{\zeta}}$ is given by

where $ \begingroup \def\mathaccent#\sqrt{\boldsymbol{\varpi}_{k}}##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sqrt{\boldsymbol{\varpi}_{k}}} \endgroup \equiv \int_0^1\sqrt{\boldsymbol{\varpi}_{k}(u)}\mathrm{d}u$ for $k = 1,2$.

Using this estimator, we define the two-sample AW-Wald statistic as

Simulation results in the next subsection indicate that this standardized statistic is (approximately) standard normal, although a formal theoretical justification remains an open question. The finite-sample version is given by

where $\hat\boldsymbol{\zeta}^{\text{AW}}_{T} \equiv \boldsymbol{S}_{\frac{1}{2};2,T}^{-1}\boldsymbol{C}_{\frac{1}{2};2,T} - \boldsymbol{S}_{\frac{1}{2};1,T}^{-1}\boldsymbol{C}_{\frac{1}{2};1,T}$ and $ \begingroup \def\mathaccent#\sqrt{\boldsymbol{\varpi}_{k,T}}##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sqrt{\boldsymbol{\varpi}_{k,T}}} \endgroup \equiv \boldsymbol{S}_{\frac{1}{2};1,T}\big(\sum_{t=1}^{T}\boldsymbol{X}_{t}\boldsymbol{X}_{t}^\prime\big)^{-1/2}$. The weak convergence $\tau^{\text{TS-AW-Wald}}_{T}(\mathbf{G}) \Rightarrow \tau^{\text{TS-AW-Wald}}(\mathbf{G})$ follows from Ancillary (ref).

Simulation results

In this section, we conduct a simulation study to assess the size and power properties of the tests for the linear CMAB experiment, introduced in Sections (ref). Our primary focus is on asymptotic results simulated via the limit experiment, where we still simulate SDEs ((ref)) via an Euler scheme on a grid with $200$ points. As in the non-contextual case, we maintain a significance level of $\alpha = 5\%$ throughout the analysis. All results are based on $50,000$ replications.

We consider a linear model, $Z_{k,t} = \beta_{k}^{\text{intercept}} + \beta_{k}^{\text{slope}}X_t + \varepsilon_{k,t}$, for $k = 1,2$, where $\varepsilon_{k,t}$ are i.i.d.\ standard normal innovations. This specification includes both a constant term and a scalar contextual variable. Our goal is to test whether $\zeta^{\text{intercept}} = \beta_{2}^{\text{intercept}} - \beta_{1}^{\text{intercept}}$ or $\zeta^{\text{slope}} = \beta_{2}^{\text{slope}} - \beta_{1}^{\text{slope}}$ equals zero, for which we use $\mathbf{G} = (1,0)^\prime$ and $\mathbf{G} = (0,1)^\prime$, respectively. In this setting, the TS-Wald and TS-AW-Wald statistics reduce to the TS-t and TS-AW statistics for testing the intercept and slope parameters.

We evaluate the three translation-invariant sampling schemes for the linear CMAB problem, introduced in Section (ref). Specifically, we implement the translation-invariant Thompson algorithm with $b = 1/20$, the translation-invariant tempered-greedy algorithm with $\alpha = 1$, and the translation-invariant tempered-LinUCB algorithm with $\alpha = 1$ and $\gamma = 1$. Additionally, we include the original Thompson sampling scheme (also with $b = 1/20$) to examine how non-translation-invariant algorithms can lead to invalid tests in this linear CMAB setting.

Null distributions

Figure (ref) presents histograms of arm-pulling frequencies, the TS-t, and TS-AW statistics for intercept and slope parameters in the CMAB limit experiment under the null $\boldsymbol{\zeta} = (0,0)^\prime$ and under translation-invariant Thompson sampling. The nuisance common local parameter is set to $\boldsymbol{b} = (0,0)^\prime$ (top) and $\boldsymbol{b} = (100,100)^\prime$ (bottom). The distributions for all statistics remain unchanged when $\boldsymbol{b}$ varies, as they are designed to be distribution-free, under the null hypothesis, with respect to $\boldsymbol{b}$. Notably, the TS-AW statistics follow nearly a standard normal distribution.

Figure (ref), the counterpart to Figure (ref) but under classical Thompson sampling, illustrates the impact of non-translation-invariant sampling schemes on the tests. We observe a dramatic change in arm-pulling frequencies when $\boldsymbol{b}$ changes from $(0,0)^\prime$ to $(100,100)^\prime$, which in turn alters the distributions of the TS-t statistics---the difference is small for the slope parameter, though notices in an unreported CDF plot---despite their intended distribution-free property with respect to $\boldsymbol{b}$. This again highlights the necessity of translation-invariant sampling schemes to ensure valid inference. An exception is the TS-AW statistic, which, by construction, remains nearly standard normally distributed regardless of the sampling scheme.

Power results

Turning to the power results, Figure (ref) shows the asymptotic powers of the TS-t and TS-AW tests for detecting differences in the intercept (left) and slope (right) parameters between the two arms, under $\boldsymbol{b} = (0,0)^\prime$ and under the same three translation-invariant sampling schemes. Similar to the non-contextual bandit case, we observe that the asymptotic power of each test depends on the underlying sampling scheme, with schemes that encourage more exploration, such as the TI Thompson sampling, tending to yield higher power. Interestingly, the relative power gains and losses across two fixed sampling schemes differ between the intercept and slope parameters. For instance, the TS-t-test under the TI tempered-LinUCB algorithm achieves asymptotic power nearly identical to that under TI tempered-greedy when testing the intercept parameter, whereas for the slope parameter, its power is more comparable to that under TI Thompson sampling.

Figure (ref) compares the power performance of the TS-t and TS-AW tests in terms of both asymptotic power and finite-sample powers at $\boldsymbol{b} = (0,0)^\prime$ for $T = 100$, $200$, and $500$ under translation-invariant Thompson sampling scheme. The TS-t-test consistently outperforms the AW test in power across all settings, highlighting the trade-off in power required to achieve (near) standard normality under the null for the TS-AW statistic. Moreover, the TS-t-test exhibits faster convergence of finite-sample power to its asymptotic counterpart: even with $T = 100$, the observed power is already close to the asymptotic level. In contrast, the TS-AW test requires substantially larger sample sizes---more than $T = 500$---to attain similar convergence.

Conclusion

We show that diffusion approximations that have been used in the literature to describe the limiting behavior of multi-armed bandit problems at fixed parameter value, can also be used as approximations in the H\'ajek-Le Cam sense of convergence of statistical experiments, in particular, for studying inference about unknown parameter values. Specifically, under the equal-arms asymptotics, where all arms have equal means, we develop the limit experiment for the (C)MAB problem, which incorporates a convergence result for a general class of statistics used for inferential purposes. Leveraging a structural representation of the CMAB limit experiment in terms of SDEs, we can readily study the asymptotic behavior of commonly-used test statistics. We establish that many such tests have non-constant size over the (composite) null hypothesis. To address this issue, we rigorously propose the notion of translation-invariant sampling schemes, including specific examples such as translation-invariant versions of Thompson, tempered-greedy and tempered-UCB/-LinUCB sampling for (C)MAB settings. Their regret analysis is left for future research.

We summarize our main findings, which apply to both MAB and CMAB settings. When testing the expected reward of a single arm (presented in the MAB case; see Section (ref)), we find that the t-test and IPW test are not only asymptotically non-normal---as recently noted in the literature--but moreover, not distribution-free with respect to the local reward parameter of the other arm, and are therefore 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. In the case of comparing two arms (e.g., treatment vs. control; see Section (ref) for MAB and Section (ref) for CMAB), the validity of a test requires distribution-freeness (w.r.t.\ the common local means of the arms) of its statistics and, perhaps less obviously, translation-invariance of the sampling schemes. On power performance, we find that (i) policies that emphasize exploration (e.g., TI Thompson sampling) generally yield higher power than those favoring exploitation (e.g., TI tempered-greedy), and (ii) when comparing arms, the two-sample t-test outperforms the two-sample AW and IPW tests in both power and power convergence speed. We therefore recommend using the two-sample t-test in conjunction with a translation-invariant sampling scheme for reliable inference.