The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
117,933 characters
Inference on the Value of Policy Improvement in Adaptive Experiments
\maketitle
\begin{abstract}
In this paper, we develop an asymptotically normal estimator for the \textit{value of policy improvement (VPI)} under adaptively collected data.
This value, which is defined as the gap between the value of the best treatment policy in a class and that of a baseline policy, gauges whether or not it is worth deploying a personalized treatment policy.
Building an estimator for the VPI is naturally more difficult than estimating the value of a fixed policy.
This is because, in addition to contending with the correlated data and decaying propensities associated with adaptive experiments, any estimator must also handle the \textit{non-regularity}, or lack of pathwise differentiability, of the underlying estimand when the optimal policy is non-unique.
Our proposed estimator works by sequentially fitting a weighted empirical welfare maximizing policy on historical data and then evaluating it using inverse propensity weighting on future samples. We neither assume that the optimal policy is unique nor make a margin assumption on the underlying heterogeneous treatment effects. A key difficulty in analyzing our estimator is showing that the regret incurred through policy learning is asymptotically smaller than the standard error of the estimator. We accomplish this by showing faster regret rates for policy learning under decaying propensities, which may be of independent interest.
We not only evaluate the coverage of our estimator on a mix of synthetic and semi-synthetic data, but also employ it to estimate the VPI in an adaptive experiment evaluating the efficacy of job assistance programs in Jordan due to Caria et al.
Although our estimates are generally more conservative than their hierarchical Bayesian analysis, which assumes that the optimal policy is unique, we still corroborate the benefits of personalization amongst Syrian refugees.
\end{abstract}
\section{Introduction}
Researchers regularly conduct experiments in order to learn the effect of one or more interventions
(e.g., discounts or medications) on an outcome of interest (e.g., generated revenue or patient welfare). Given that assigning an individual to a suboptimal intervention can result in worse outcomes for both providers and patrons alike, some organizations are moving from traditional experiments (e.g., A/B tests) to \textit{contextual bandit} algorithms. By adapting treatment assignments as data are gathered, these algorithms can balance several objectives: they can direct data collection toward interventions or subgroups for which additional observations would be most informative, identify a best intervention or ``arm'', and prioritize beneficial outcomes for participants.
A common feature of contextual bandit algorithms is that suboptimal or inferior treatments are assigned with probabilities that decrease over the course of the experiment.
This flexibility
has resulted in the adoption of bandit algorithms in disparate domains from advertising/e-commerce \citep{li2010contextual, bottou2013counterfactual, sharma2022doordashbandit} to medicine/clinical trials~\citep{villar2015multi, varatharajah2022contextual, tewari2017ads}.
Given the ubiquitous adoption of adaptive experimentation across industries, it is only natural that one may want to perform statistical inference or learning \textit{post facto}, or ``after the fact'', on contextual bandit data.
However, it is precisely the ability of adaptive experiments to balance \textit{exploration} against \textit{exploitation} that makes such inference difficult.
In more detail, the correlation amongst the data alongside vanishing propensities can cause standard estimators to be biased and naive confidence intervals to miscover.
To counteract this, authors have developed a number of estimators that yield valid inference under adaptively collected data.
For instance, \citet{bibaut2021post}, \citet{zhan2021off}, and \citet{hadad2021confidence} have considered the problem of \textit{off-policy evaluation (OPE)}, developing estimators that leverage martingale central limit theorems to account for decaying propensities.
Likewise, \citet{bibaut2021risk}, \citet{zhan2024policy}, and \citet{girard2025online} study policy learning under decaying propensities, showing that certain weighted empirical welfare maximization (EWM) algorithms can yield vanishing regret.
Lastly, \citet{jia2024cramming} develop a ``cramming'' estimator for \textit{on-policy evaluation}, which provides valid confidence intervals for the value of the deployed bandit policy under sufficiently slow propensity decay and policy stability.
These results demonstrate that many policy learning-related tasks are still feasible under bandit logging data.
The existing literature, however, does leave a notable problem unaddressed. Suppose that, sometime after an adaptive experiment has concluded, a learner wants to determine whether or not it is worth deploying a new policy from a fixed policy class.
In this setting, they no longer want to perform inference on the value of a fixed policy (i.e., OPE) or the value of the final deployed policy (i.e., cramming). Rather, they might wish to understand \textit{the value of policy improvement (VPI)}, or the gap between the value of a best policy in a class $\Pi$ and some baseline policy, such as uniform randomization or an all control policy.
More formally, let $X \in \mathcal{X}$ represent an individual's characteristics drawn from some distribution, $Y(a)$ a unit's potential outcome under some categorical treatment $a \in \mathcal{A}$, and $q(a \mid x)$ a (potentially randomized) treatment policy.
The VPI is defined as
\begin{equation}
\label{eq:vpi}
\theta^\ast = \max_{\pi \in \Pi}V(\pi) - V(q), \quad \text{where}\;\; V(\pi) := \mathbb{E}\left[\sum_{a \in \mathcal{A}}\pi(a \mid X) Y(a)\right].
\end{equation}
A high-quality estimate of $\theta^\ast$ naturally informs the learner whether or not they should conduct policy learning. For instance, if the upper confidence bound for $\theta^\ast$ does not exceed the cost of developing/deploying a policy, then it is likely not worth a learner's efforts to build a personalized treatment regime. On the other hand, if the lower bound greatly exceeds costs, then constructing a personalized policy is worthwhile.
We note that the VPI fits into a longer line of estimands related to studying the effects of personalization, such as the \textit{value of personalization} considered in \citet{li2026statistical} and the population average prescriptive effect (PAPE) introduced by \citet{imai2023experimental}, which we discuss in Section~\ref{sec:intro:related}.
When there is a unique optimal treatment rule, performing inference on the VPI is relatively straightforward. In fact, in the setting of i.i.d.\ data, one can both learn and evaluate a policy on the entire dataset and still obtain asymptotically normal inference.\footnote{Of course, under the assumption that the policy class has well-behaved metric entropy. See \citet{carcamo2020directional} and \citet{fang2019inference} for a discussion of this.} However, in many empirical settings, the optimal policy or even best overall intervention may not be unique. For example, there may be groups of patients who do not respond to treatments, and hence would experience identical outcomes under treatment and control.
When the optimal policy is non-unique, \textit{the value of an optimal treatment policy} $V^\ast := \max_{\pi \in \Pi}\mathbb{E}\left[Y(\pi(X))\right]$ (the leading term in $\theta^\ast$) is \textit{non-regular}, or not pathwise differentiable in the semiparametric sense.
While a variety of estimators have been developed for tackling this non-regularity, these approaches either focus on unrestricted policy classes, yield non-Gaussian limiting distributions, or rely on conditions not established under adaptive logging with decaying propensities~\citep{luedtke2016statistical, whitehouse2025inference, fang2019inference, shi2022statistical, chernozhukov2013gaussian, chernozhukov2013intersection}.
We discuss these approaches in detail in Section~\ref{sec:intro:related} and Appendix~\ref{app:related}.
Notably, no existing approach yields general asymptotically normal inference when there is not a unique optimal policy and policy classes are restricted, even in the i.i.d.\ setting.
Further, existing proof techniques entirely break down when data are collected from a bandit policy with decaying propensities.
In sum, although the value of policy improvement is a naturally important quantity, it is clear that constructing estimators for it is non-trivial.
To develop such an estimator in the setting of the present paper, one needs to not only contend with decaying propensities, but also the general non-regularity of the estimand itself.
Given this subtlety, we make it our goal to construct a simple, asymptotically normal estimator for the value of policy improvement that remains valid even when data are collected from adaptive experimentation and optimal policies are non-unique.
\subsection{Our Contributions}
In this paper, we present an adaptive, inverse propensity weighted (IPW) estimator for the value of policy improvement given data logged from a contextual bandit algorithm. We briefly describe the estimator at this point to provide some intuition. Our estimator works by solving a weighted empirical risk minimization on all prefixes of data, down-weighting later samples proportionally to how aggressively the bandit logging policy exploits. The estimator then evaluates each learned policy on the next sample through inverse propensity weighting, contrasting the value with that of the fixed baseline policy.
This structure builds on the online estimator of \citet{luedtke2016statistical}, extending it to substantially different settings. In particular, we allow for contextual bandit data with vanishing propensities (as opposed to i.i.d.\ data with strong positivity), study restricted policy classes (versus unrestricted ones), and provide a concrete weighted empirical welfare maximization procedure whose regret is sufficiently small to enable valid inference.
Throughout, we operate under the assumption that propensities are bounded below by $t^{-\alpha}$ for some $\alpha \in [0, 1)$, where $t$ is the current round of adaptive data collection. When $\alpha = 0$, this corresponds to assuming strong positivity, and as $\alpha$ tends towards one, the bandit more aggressively exploits what has been learned from the data up to the current point in time.
In detail, our primary contributions are as follows.
\begin{itemize}
\item \textbf{An estimator for the value of policy improvement.} In Section~\ref{sec:estimator}, we formalize an
estimator for the value of policy improvement. In contrast to prior work, our estimator can be used with adaptively collected data and we do not assume optimal policy uniqueness. We prove the asymptotic normality of the estimator in Theorem~\ref{thm:clt}, describe a more computationally efficient batched version in Algorithm~\ref{alg:online-epoch}, and establish its convergence in Corollary~\ref{cor:epoch_estimator}. We emphasize that our estimator requires neither a margin condition on the blip effects nor uniqueness of the value-maximizing policy. To complement our estimator, we also prove the appropriate convergence of a natural predictable variance estimator. We note that our estimators (both for variance and the VPI) converge for $\alpha < 1$, whereas existing results focused instead on policy evaluation due to \citet{bibaut2021post}, \citet{zhan2021off}, and \citet{jia2024cramming} all require $\alpha \leq 1/2$ or stronger assumptions.
\item \textbf{Fast rates under decaying propensities.} In Section~\ref{sec:regret}, we show that regret of a policy $\widehat{\pi}$ obtained through weighted EWM satisfies
\[
\mathbb{E}\left[\mathrm{Reg}(\widehat{\pi})\right] := \mathbb{E}\left[V^\ast - V(\widehat{\pi})\right] = o\left(n^{(\alpha - 1)/2}\right)
\]
pointwise for every fixed data-generating process satisfying our assumptions. This is notably faster than (and does not contradict) the minimax optimal expected regret rates of $\Theta\left(n^{\frac{\alpha - 1}{2}}\right)$ provided by the current literature~\citep{zhan2024policy, bibaut2021risk}. Using this result, we can argue that the cumulative regret incurred from doing policy learning is \textit{lower order} than the width of our confidence intervals, thus enabling valid inference.
While our results are inspired by fast regret rates due to \citet{luedtke2020performance} from the i.i.d.\ setting, our bounds hold \textit{in expectation} versus \textit{in probability}, with the former being needed to show convergence. Further, our results do not require assuming that the natural empirical process associated with the data converges to a tight, limiting Gaussian process. Instead, our results follow from a direct analysis that leverages asymptotic localization arguments.
\item \textbf{Extensive empirical evaluation.}
We also empirically evaluate our estimator on a mix of synthetic, semi-synthetic, and real-world data.
On synthetic and semi-synthetic data (the latter being generated from the Jester dataset), we analyze various statistics of our estimator, such as coverage and confidence interval width, relative to several natural baselines.
We also empirically study the convergence rate of regret, confirming the faster regret rates shown in Theorem~\ref{thm:fast-regret} hold in practice.
We find that our estimator performs quite well across both scenarios, typically achieving nominal coverage while offering narrower confidence intervals than other baseline estimators.
Lastly, we revisit an adaptive experiment conducted by \citet{caria2024adaptive}, which was aimed at assessing the effectiveness of various interventions designed to help refugees in Jordan obtain employment.
As part of their work, the authors measure the effect of personalizing interventions using a Bayesian analogue of the VPI. Notably, their work assumes a unique optimal treatment policy.
We reanalyze the data using our frequentist, assumption-light estimator.
While we generally obtain more conservative estimates across the board than \citet{caria2024adaptive}, we do confirm the authors' finding that employment outcomes are better under personalization amongst the Syrian subpopulation in Jordan.
\end{itemize}
Our estimator is inspired by an earlier, online estimator due to \citet{luedtke2016statistical}. We note several important distinctions from the aforementioned work. First, our estimator operates in the far more flexible setting of contextual bandit data instead of imposing strong, i.i.d.\ assumptions. Second, we focus our attention on \textit{restricted policy classes}, versus unrestricted settings where any measurable policy is allowed.
Finally, instead of assuming access to a black-box policy learner that attains the target rates, we provide a \textit{precise, weighted welfare maximization procedure} that enjoys the necessary regret rates.
We close the introduction by noting what we believe to be the most important technical insight of the paper: the particular choice of estimand is critical in enabling valid inference. An alternative estimand more closely aligned with the aforementioned literature on nonregular statistical inference would be the value of the optimal treatment policy $V^\ast := \max_{\pi \in \Pi}V(\pi)$. While we believe the contrast $\theta^\ast$ is actually a more interpretable estimand (because it gives a value relative to some baseline), the contrast with a policy also serves to stabilize the variance of the IPW estimates for the values of the sequentially learned policies. This stabilization aids our analysis, not only allowing us to show that the accumulated regret from policy learning is negligible relative to the overall width of our confidence intervals, but also giving our estimator the flexibility to operate under any logging exponent $\alpha \in [0, 1)$.
\section{Related Work}
\label{sec:intro:related}
Our work is situated at the intersection of three technical bodies of literature. In particular, our analysis is built upon results on inference on optimal treatment regimes (i.e., the value of the optimal treatment policy), off policy evaluation, and policy learning. We provide a much more extensive related work section in Appendix~\ref{app:related}, and opt to just focus on the most closely related results here. We also briefly note the connection to the literature on personalization at the end of this section. A summary of our comparison to closely related results can be found in Table~\ref{tab:related-work-terse}, with a more thorough comparison being presented in Table~\ref{tab:related-work} in Appendix~\ref{app:related}.
Below, we focus our discussion primarily on the results provided by the cited papers. We postpone the detailed comparison of proof techniques for relevant sections of the paper/appendices.
\begin{table}[H]
\centering
\caption{A comparison of our results with the most closely related papers. We let $V^\ast$ denote the value of an optimal policy within a class $\Pi$ and $V^\circ$ the optimal value of \textit{any} policy. An extended comparison is shown in Table~\ref{tab:related-work} in Appendix~\ref{app:related}}
\label{tab:related-work-terse}
\small
\setlength{\tabcolsep}{3pt}
\begin{tabularx}{\textwidth}{
@{}
>{\raggedright\arraybackslash}p{0.155\textwidth}
>{\raggedright\arraybackslash}p{0.145\textwidth}
>{\raggedright\arraybackslash}p{0.17\textwidth}
>{\raggedright\arraybackslash}p{0.205\textwidth}
X
@{}
}
\toprule
Work
& Setting
& Target
& Result
& Key assumptions
\\
\midrule
\citet{luedtke2016statistical}
& i.i.d.\ data
& Unrestricted optimal value $V^\circ$
& Asymptotically normal estimator
& Propensity and regression nuisance convergence rates.
\\
\midrule
\citet{zhan2021off}
& Contextual bandit data
& Fixed-policy value $V(\pi)$
& Asymptotically normal estimator
& $\alpha<1/2$
\\
\midrule
\citet{bibaut2021post}
& Contextual bandit data
& Fixed-policy value $V(\pi)$
& Asymptotically normal estimator
& $\alpha\leq1/2$ ($\alpha \leq 1/3$ for variance convergence)
\\
\midrule
\textbf{This paper}
& Contextual bandit data
& Best in-class contrast $V^\ast -V(q)$
& Asymptotically normal estimator and expected regret
$o\!\left(n^{(\alpha -1)/2}\right)$
& Finite disagreement VC dimension; $\alpha<1$
\\
\bottomrule
\end{tabularx}
\end{table}
\paragraph{Inference on Optimal Treatment Regimes}
There is a rich literature focused on estimating the value of an optimal treatment policy within a class. These works can be roughly split into two buckets: approaches that assume \textit{unrestricted policy classes}\footnote{Meaning that a treatment policy can be \textit{any} measurable map from $\mathcal{X}$ to a distribution over $\mathcal{A}$.} and those that assume \textit{restricted classes} (e.g., VC classes or Donsker classes). There are many distinct estimation strategies for the first bucket: some papers involve repeatedly subsampling/refitting nuisances~\citep{shi2020breaking}, explicitly constructing smoothed surrogates for the target estimand~\citep{whitehouse2025inference, goldberg2014comment}, using bootstrapping methods to handle irregular limits~\citep{chakraborty2010inference, laber2014dynamic}, or assuming almost sure uniqueness of the optimal policy~\citep{chambaz2017targeted, van2015targeted}.
In the setting of restricted, well-behaved policy classes (e.g., Donsker or VC-like classes), authors have characterized the behavior of the ``double-dipping'' estimator that uses the full set of data to both learn and evaluate a policy.
If there is a unique optimal treatment policy, the results of \citet{carcamo2020directional} and \citet{fang2019inference} guarantee that double-dipping yields asymptotically normal estimates. Otherwise, the limiting distribution is generally the supremum of a limiting Gaussian process indexed by the class of optimal policies, for which authors have constructed directional and multiplier bootstrap methods for estimating quantiles~\citep{fang2019inference, chernozhukov2013gaussian, chernozhukov2013intersection,chernozhukov2023high,ponomarev2024lower}. The aforementioned \textit{unrestricted estimators} all make a \textit{margin assumption} on the underlying conditional average treatment effects (blip effects in the multi-treatment settings)~\citep{audibert2007fast}, while the \textit{restricted estimators} do not. Related work on the estimator of the value of personalization by \citet{li2026statistical} similarly assumes a unique optimal policy in the class for its semi-parametric efficiency results. In addition, all of the aforementioned papers (modulo \citet{chambaz2017targeted}) only yield valid inference under i.i.d.\ data, and none allows for decaying treatment propensities.
One further work that permits adaptively collected data is \citet{shen2024doubly}, who restrict their attention to linear models and assume a margin condition that implies that there is zero probability of units not responding to treatment.
We also note that none of the results from the restricted setting yields general, asymptotically normal estimators even in the i.i.d.\ setting, which will be an additional contribution of this paper.
The most closely related paper to the present work is an online/sequential estimator of \citet{luedtke2016statistical}, which works around nonregularity by progressively refitting nuisances (an outcome regression and propensity score) on prefixes of data. It then evaluates the policy associated with learned regression on subsequent samples using an augmented IPW off policy evaluation score.
While other estimators (e.g., that of \citet{shi2020breaking}) also use repeated nuisance refitting, this online estimator can get away with significantly fewer nuisance refits: with $\log(n)$ refits required under standard nuisance $L^2$ estimation rates and only a \textit{constant number of fits} if one can obtain mildly (say, a factor of $\log(n)$) faster rates.\footnote{Albeit the first $n/\log(n)$ samples will be lost to nuisance estimation.} While in principle this estimator permits the evaluation of an arbitrary, predictable policy on the $t$th sample, the expected regret of the policy must shrink as $o(n^{-1/2})$.\footnote{The initial publication of this paper stated $o_\mathbb{P}(n^{-1/2})$ regret rates sufficed, but was later corrected by the authors in~\citep{luedtke2021correction}.}
Existing regret analyses (due to \citet{luedtke2020performance}) yield regret that vanishes as $o_\mathbb{P}(n^{-1/2})$, which is notably insufficient for the estimator to yield valid coverage~\citep{bibaut2020sufficient}.
In this paper, we study an analogue of this estimator in the setting of contextual bandit data with vanishing propensities, showing convergence if the expected regret of the learned policy vanishes at $o(n^{(\alpha - 1)/2})$ rates. Unlike the estimator of \citet{luedtke2016statistical}, instead of assuming access to an abstract, black-box learner, our estimator includes a specific weighted welfare maximization objective whose solution satisfies the requisite regret rates (established in Theorem~\ref{thm:fast-regret}).
Thus, even with i.i.d.\ data, our analysis closes the loop on the validity of the sequential estimator, showing it can be used to obtain valid inference under restricted policy classes.
\paragraph{Off-Policy Evaluation}
We only discuss the most closely related works on OPE of a fixed policy in this section, deferring our discussion of more classical results from the i.i.d.\ or reinforcement learning settings for the appendices. One closely related result is due to \citet{hadad2021confidence}, who discuss inference on the value of a fixed policy under (non-contextual) bandit data. \citet{zhan2021off} extend these results to the contextual setting, discussing various predictable, contextual weights one can use to ensure asymptotic normality.
\citet{bibaut2021post} discuss a similar estimator for OPE (or more broadly, treatment effect estimation), which is closely related to the aforementioned estimator of \citet{luedtke2016statistical}. Unfortunately, this work only considers inference on the value of a \textit{fixed function}, and assumes the logging policy does not exploit too aggressively, requiring $\alpha \leq 1/2$ for convergence to hold (and $\alpha \leq 1/3$ to obtain a sufficiently quickly converging variance estimator). Lastly, we note high-probability bounds due to \citet{karampatziakis2021off} and \citet{waudby2024anytime}, who provide time-uniform, non-asymptotic bounds on the value of a treatment policy. The analyses of the estimators in these works, like the analyses conducted in this paper, all depend on concentration properties for martingales, whether they be martingale central limit theorems~\citep{brown1971martingale, hall2014martingale, ganssler1978central} for the former three estimators, or finite sample bounds based on Ville's inequality~\citep{howard2020time, howard2021time} for the latter two. We note that none of these works focuses on inference on the value of the optimal treatment policy.
We also mention the ``Cramming'' estimator of \citet{jia2024cramming}, which considers the related task of \textit{on-policy evaluation} instead of off-policy evaluation. This work provides inference for the value of the final, adaptively-chosen logging policy itself under a condition that the chosen policy stabilizes over time. This work may fail to give valid inference if the logging exponent satisfies $\alpha \geq 1/2$, and may also fail if the logging policy doesn't converge.\footnote{This may occur in practice, for instance, if the logging policy is chosen according to an empirical welfare maximization problem and there are multiple optimal policies.} On the other hand, our work places much weaker assumptions on $\alpha$, simply requiring $\alpha < 1$, and allows \textit{post facto} inference on the optimal value in some arbitrary class, not necessarily the policy class that was used for logging.
\paragraph{Policy Learning From Observational Data}
\citet{bibaut2021risk} and \citet{zhan2024policy} discuss how a weighted variant of empirical welfare maximization can be used to obtain $\Theta(n^{(\alpha - 1)/2})$ regret rates, respectively with high probability and in expectation, when the propensity of the logging bandit algorithm decays as $t^{-\alpha}$. \citet{zhan2024policy} also show that such expected regret bounds are \textit{minimax optimal}.
These two works operate under slightly different assumptions on the policy and logging policy classes, with the former assuming a bracketing entropy condition and the latter considering finite Natarajan dimension (the analogue of VC-dimension for multiclass settings, see \citet{natarajan1989learning}). We make an assumption equivalent to the latter throughout our work, and thus leverage similar chaining arguments to \citet{zhan2024policy} in our analysis. We also note recent work due to \citet{girard2025online}, which shows fast, high-probability regret bounds when a H\"olderian variance condition holds for the policy class. However, this paper requires stochastic policies, and the curvature assumption implies an \textit{almost surely unique optimal policy}. We make no such curvature or uniqueness assumptions in this paper. Our primary policy learning contribution is that we show the \textit{expected regret} vanishes at a rate of $o(n^{(\alpha - 1)/2})$, which can be viewed as infinitesimally faster than the rates noted above.
Another relevant paper to our regret rates is \citet{luedtke2020performance}. In this work, the authors show that, for Donsker classes of treatment policies and i.i.d.\ data, the regret obtained from performing empirical welfare maximization scales as $o_\mathbb{P}(n^{-1/2})$, slightly faster than the $\Theta(n^{-1/2})$ expected rates suggested by \citet{athey2021policy} and \citet{kitagawa2018should}. These results are not shown in a minimax framework, but rather in a pointwise sense, with the unknown constants depending inherently on the underlying data generating distribution.
More broadly, the authors show similar fast regret rates can hold under broader settings, so long as the empirical process associated with the gathered data and policy class converges to a tight Gaussian limit. We note two key differences between the aforementioned results and our own. First, our fast regret rates do not require asymptotic convergence of the empirical process to a Gaussian limit. Instead, we prove our results by leveraging finite sample chaining arguments, which can then be asymptotically localized to obtain the fast rates we desire.
Second, we show stronger \textit{in expectation} bounds rather than only the \textit{in probability} convergence bounds shown by \citet{luedtke2020performance}. Per results of \citet{bibaut2020sufficient}, the latter results are insufficient for the convergence of the online estimator.
\paragraph{Measuring the Effect of Personalization}
We conclude by briefly discussing the most closely related works on studying the effects of personalization. First, the VPI is similar to the \textit{value of personalization} proposed in recent work by~\citet{li2026statistical}, which is defined as $\max_{\pi \in \Pi}V(\pi) - \max_a V(a)$.\footnote{Here, we abuse notation and let $V(a)$ denote the value of the constant treatment policy that assigns all units to $a \in \mathcal{A}$.} We note that the setting considered in said paper is quite different from our own, as the authors assume i.i.d.\ data and uniqueness of the optimal treatment policy. In their setting, they present a semiparametrically efficient estimator for the value of personalization.
Also related to our work is that of \citet{imai2023experimental}, who define the \textit{population average prescriptive effect (PAPE)}, which evaluates a given individualized treatment rule relative to a non-personalized randomized rule assigning the same fraction of units to treatment. They develop randomization-based inference for both fixed rules and those learned via sample splitting and cross-validation. In particular, we note that the estimand does not involve a maximization over a class of policies, which is the fundamental technical difficulty addressed in this work.
\section{Background and Notation}
\label{sec:background}
In this section, we introduce the notation and assumptions that we will leverage throughout the sequel. Our setup largely follows that of works on off-policy evaluation \citep{bibaut2021post, zhan2021off} and policy learning~\citep{zhan2024policy} under contextual bandit data.
We first introduce assumptions needed for defining and identifying the value of policy improvement and then discuss assumptions made to enable estimation.
\paragraph{Assumptions for Identification}
Throughout, we represent each unit by a tuple $W_t = \big(X_t, \left\{Y_t(a) : a \in \mathcal{A}\right\}\big)$, where $X_t \in \mathcal{X}$ represents covariates, $\mathcal{A}$ denotes a finite treatment set, and $Y_t(a)$ represents a unit's potential outcome associated with treatment $a \in \mathcal{A}$. At round $t$, we assume the learner obtains a \textit{partial observation} of the form $Z_t = (X_t, A_t, Y_t)$, where $A_t \in \mathcal{A}$ denotes a realized treatment assignment. We let $(\mathcal{F}_n)_{n \geq 0}$ denote the natural filtration associated with the data, i.e., $\mathcal{F}_n = \sigma(Z_t : 1 \leq t \leq n)$.
\begin{ass}[Identifying Assumptions]
\label{ass:observations}
We assume that the following hold:
\begin{enumerate}
\item \textit{Stationarity.} There is some distribution $P_W$ over tuples $W = \big(X, \{Y(a) : a \in \mathcal{A}\}\big)$ such that $W_1, \dots, W_n \sim P_W$ are i.i.d.
\item \textit{Predictable Assignments.} There is a known sequence of transition kernels $p_t(a \mid x, \mathcal{F}_{t - 1})$ such that, conditional on $X_t$ and $\mathcal{F}_{t - 1}$, $A_t \sim p_t(\,\,\cdot \mid X_t, \mathcal{F}_{t - 1})$ independently of $\{Y_t(a) : a \in \mathcal{A}\}$ and future observations $W_{t + 1}, \dots, W_n$, and hence
\[
\mathbb{P}(A_t = a \mid X_t, \mathcal{F}_{t - 1}) = p_t(a \mid X_t, \mathcal{F}_{t - 1})\;\; \text{almost surely.}
\]
\item \textit{Consistency.} $Y_t = Y_t(A_t)$ for all $t \geq 1$.
\item \textit{Positivity.} For each $t \geq 1$ and $a \in \mathcal{A}$, we have $p_t(a \mid X_t, \mathcal{F}_{t - 1}) > 0$ almost surely.
\end{enumerate}
\end{ass}
Note that the first two parts of Assumption~\ref{ass:observations} imply conditional exogeneity for each $t \geq 1$:
\begin{equation}
\label{eq:conditional_exogeneity}
\left\{Y_t(a) : a \in \mathcal{A}\right\} \protect\mathpalette{\protect\independenT}{\perp} A_t \mid X_t, \mathcal{F}_{t - 1}.
\end{equation}
In the sequel, we write $p_t(a \mid x) := p_t(a \mid x, \mathcal{F}_{t - 1})$ for convenience. The above assumptions are largely standard and match the aforementioned works.
By a treatment policy, we mean either a \textit{deterministic} policy $\pi : \mathcal{X} \rightarrow \mathcal{A}$ or a \textit{randomized} policy $\pi : \mathcal{A} \times \mathcal{X} \rightarrow [0, 1]$, where $\pi(a \mid x)$ denotes the probability that a unit with features $x$ receives treatment $a$.\footnote{More formally, a randomized policy is actually a mapping $\pi : \mathcal{X} \rightarrow \Delta(\mathcal{A})$, where $\Delta(\mathcal{A})$ is the probability simplex on the set of treatments. Here, we would let $\pi(a \mid x)$ just denote the $a$th component of this vector.} We can view a deterministic policy $\pi(x)$ as a randomized one using the notation $\pi(a \mid x) := \mathbbm{1}\{\pi(x) = a\}$. Given any function $\pi : \mathcal{A} \times \mathcal{X} \rightarrow \mathbb{R}$ (not necessarily a treatment policy), we can define its value as $V(\pi) := \mathbb{E}\left[\sum_{a \in \mathcal{A}} \pi(a \mid X)Y(a)\right]$.
Under Assumption~\ref{ass:observations}, it is well understood that the value of any such function $\pi$ can be identified in two ways:
\[
V(\pi) \equiv \mathbb{E}\left[\sum_{a \in \mathcal{A}}\pi(a \mid X_t)\widetilde{Y}_t(a)\right] \equiv \mathbb{E}\left[\sum_{a \in \mathcal{A}}\pi(a \mid X) \mu_0(a, X)\right],
\]
where $\widetilde{Y}_t(a) := \frac{\mathbbm{1}\{A_t = a\}}{p_t(a \mid X_t)}Y_t$ is an inverse propensity weighted (IPW) pseudo-outcome for treatment $a \in \mathcal{A}$ and $\mu_0(a, x) := \mathbb{E}\left(Y(a) \mid X = x\right)$ is the outcome regression (which does not depend on $t$ due to stationarity).
Throughout, we let $\Pi \subset \big\{\pi : \mathcal{X} \rightarrow \mathcal{A}\big\}$ denote a fixed set of deterministic treatment policies, which we assume to be \textit{closed with respect to the disagreement metric} $d(\pi, \rho) := \mathbb{P}\big(\pi(X) \neq \rho(X)\big)^{1/2}$. Closedness is useful as, along with the complexity assumptions posited below, it ensures the value of an optimal treatment policy $V^\ast := \max_{\pi \in \Pi}V(\pi)$ is attained. We let $\Pi^\ast := \big\{ \pi \in \Pi : V(\pi) = V^\ast\big\} \subset \Pi$ denote the set of optimal policies, which may contain multiple (or even infinitely many) elements.\footnote{One could relax the closedness assumption (as done in \citet{luedtke2020performance}, for instance) at the cost of greatly complicating analysis.}
Given $\Pi$ and any function $q : \mathcal{A} \times \mathcal{X} \rightarrow [0, 1]$ (which may or may not be a treatment policy), we can formally define the \textit{value of policy improvement} as
\[
\theta^\ast := \max_{\pi \in \Pi}V(\pi) - V(q).
\]
Since the value $V(\pi)$ of any function $\pi$ is identified, it naturally follows that the value of policy improvement $\theta^\ast$ is identified as well.
\paragraph{Assumptions for Estimation}
We now present assumptions on the treatment policies, logging policies, and observations that will enable estimation. We start by qualifying the complexity of the deterministic class of treatment policies $\Pi$.
\begin{ass}
\label{ass:disagreement}
We assume the \textit{disagreement class} $\mathcal{D} := \Big\{g_{\pi, \rho}(x) := \mathbbm{1}\left\{ \pi(x) \neq \rho(x)\right\} : \pi, \rho \in \Pi \Big\}$ has VC-dimension $\mathfrak{v}$ for some $\mathfrak{v} > 0$.
\end{ass}
Under the assumption that $|\mathcal{A}| < \infty$, one can show that Assumption~\ref{ass:disagreement} is equivalent to positing that $\Pi$ has finite \textit{Natarajan dimension}.\footnote{We formally show this equivalence in Appendix~\ref{app:combinatorial-dimension}, and prefer to leverage VC dimension in the main body of the text as it is a more widely studied concept.}
This complexity assumption is not crucial to our central limit theorem, but rather to obtaining faster regret rates.
We note that \citet{zhan2024policy} make an equivalent assumption in their work (directly assuming finite Natarajan dimension), and \citet{bibaut2021risk} consider a similar condition based on bracketing entropy, which in general is neither stronger nor weaker than assuming finite VC dimension.
The next assumption imposes additional regularity on the potential outcomes.
\begin{ass}
\label{ass:estimation}
We assume that $Y(a) \in [0, 1]$ almost surely and that $ \mathrm{Var}(Y(a) \mid X) \geq \underline{\sigma}^2$ almost surely for some $\underline{\sigma} > 0$ and all $a \in \mathcal{A}$.
\end{ass}
The above assumptions are not likely minimal (e.g., boundedness of outcomes can likely be replaced with unbounded outcomes with sufficient moment control), but relaxing said assumptions would complicate analysis without adding much insight.
This assumption is in line with the broader literature on bandit optimization~\citep{lattimore2020bandit, slivkins2019introduction} and empirical welfare maximization~\citep{zhan2024policy, bibaut2021risk, kitagawa2018should, athey2021policy}, and boundedness enables the application of Freedman-style concentration inequalities for bounded random variables~\citep{freedman1975tail}.
The second assumption ensures that the variance of all potential outcomes is conditionally bounded below, which ensures that all units (regardless of strata) exhibit some variability in terms of their responses.
Next, we discuss assumptions on the collection of logging policies. We start by presenting assumptions on the rate of exploration of the bandit logging policy, which are akin to assumptions made in \citet{bibaut2021post} and \citet{zhan2021off, zhan2024policy}.
\begin{ass}
\label{ass:propensity}
We assume there are constants $\alpha \in [0, 1)$ and $\underline{c}, \overline{c} > 0$ such that, for all $t \geq 1$, we have
\[
\underline{c} t^{-\alpha} \leq \min_{a \in \mathcal{A}} p_t(a \mid X_t) \leq \overline{c} t^{-\alpha} \text{ almost surely.}
\]
\end{ass}
When $\alpha = 0$, the above is equivalent to the assumption of strong positivity, with larger $\alpha$ indicating increased exploitation. Examples of logging policies that can be shown to satisfy this assumption include contextual $\epsilon_t$-greedy algorithms. Static (non-adaptive) logging policies that randomly assign actions to contexts also immediately satisfy this assumption, as long as all actions have a positive probability of assignment in all contexts. Examples of algorithms that do not satisfy this assumption are algorithms that behave deterministically or have exponentially vanishing probabilities, such as upper confidence bound (UCB) or Thompson sampling algorithms. However, these approaches can be made to satisfy the propensity decay via clamping probabilities to a minimum floor~\cite{yao2021power} or adding a polynomially-decaying probability of uniform exploration~\citep{caria2024adaptive} ("tempering"). Notably, these algorithms will maintain their $O(\sqrt{n})$ minimax regret rates so long as the tempering probability scales like $t^{-\alpha}$ for some $\alpha \in [1/2, 1)$.
We conclude by positing an assumption on the rate of growth of the predictable variance of IPW pseudo-outcomes.
For any $\pi \in \Pi$, define the contrast $g_\pi(a \mid x) := \mathbbm{1}\{\pi(x) = a\} - q(a \mid x)$ and define the IPW pseudo-outcome for the contrast between $\pi$ and $q$ as
\begin{equation}
\label{eq:double-pseudo-outcome}
\widetilde{Y}_t(\pi, q) := \frac{g_\pi(A_t \mid X_t)Y_t}{p_t(A_t \mid X_t)}.
\end{equation}
We define the predictable variance of said contrast as
\begin{equation}
\label{eq:pred-var}
\sigma_t^2(\pi) := \mathrm{Var}\left(\widetilde{Y}_t(\pi, q) \mid \mathcal{F}_{t - 1}\right).
\end{equation}
We make the following assumption.
\begin{ass}
\label{ass:ipw_variance_scale}
There is some constant $c_\sigma > 0$ such that, for any $\pi \in \Pi$ and $t \geq 1$, we have $\sigma_t^2(\pi) \geq c_\sigma t^{\alpha}$.
\end{ass}
There are at least three natural settings in which the above assumption would hold, which we note in the following lemma.
\begin{lemma}
\label{lem:suff_conditions}
Suppose Assumptions~\ref{ass:observations}, \ref{ass:estimation}, and \ref{ass:propensity} hold. Then, if one of the following holds, Assumption~\ref{ass:ipw_variance_scale} holds as well.
\begin{enumerate}
\item \textit{Strictly Randomized Baseline.} There is a constant $\eta_q > 0$ such that $\inf_{\substack{a \in \mathcal{A} \\ x \in \mathcal{X}}}q(a \mid x) \geq \eta_q$.
\item \textit{Deterministic Baseline.} $\mathcal{A} = \{0, 1\}$, $ q(a \mid x) = \mathbbm{1}\{q(x) = a\}$ for some deterministic baseline $q : \mathcal{X} \rightarrow \{0, 1\}$, and $\eta_q := \inf_{\pi \in \Pi}\mathbb{P}(\pi(X) \neq q(X)) > 0$.
\item \textit{Non-Vanishing Exploration.} $\alpha = 0$, $q(a \mid x)$ is any function\footnote{Not necessarily a treatment policy.} taking values in $[0, 1]$, and there is some $\eta_g > 0$ satisfying
\[
\mathbb{E}\left(g_\pi(A_t \mid X_t)^2 \mid \mathcal{F}_{t - 1}\right) \geq \eta_g \;\; \forall \pi \in \Pi, t \geq 1.
\]
\end{enumerate}
\end{lemma}
We prove Lemma~\ref{lem:suff_conditions} in Appendix~\ref{app:additional}. The result follows largely from an application of the law of total variance. We now interpret each of the three aforementioned sufficient conditions. The first condition simply states that Assumption~\ref{ass:ipw_variance_scale} holds if the baseline policy is strictly randomized. An important example satisfying this condition is uniform randomization.
The next sufficient condition holds in the setting of binary treatments with deterministic baselines (when the policy class excludes the deterministic baseline), and as a special case corresponds to measuring the value of an optimal policy relative to the policy that does not change the status quo, i.e., assigns all units to control.\footnote{The assumption of $\Pi$ excluding the baseline $q$ could be weakened to allowing $q \in \Pi$ so long as $V(q) < V^\ast := \max_{\pi \in \Pi}V(\pi)$. However, this latter assumption is not verifiable. Given that $\Pi$ is chosen by the learner, we opt to just assume $q \notin \Pi$. }
Lastly, if we take $q(a \mid x) \equiv 0$ in the final setting, the conditional second moment bound trivially holds by the lower bound provided by Assumption~\ref{ass:propensity}. Thus, since $V(q) \equiv 0$, the VPI in the final setting reduces to the value of the optimal policy $V^\ast$.
In summary, Assumptions~\ref{ass:observations} and \ref{ass:estimation} are mild and common assumptions about the data generating process, and Assumption~\ref{ass:disagreement} simply states the disagreement class of the policy class considered has bounded VC dimension. Assumption~\ref{ass:propensity} is a stronger assumption on the data collection policy, that rules out certain popular algorithms but still includes other existing adaptive bandit algorithms (that often have been created to balance online adaptive regret minimization while preserving the data required for post collection inference). The final Assumption~\ref{ass:ipw_variance_scale} is less standard, and, as we lay out in Lemma ~\ref{lem:suff_conditions}, intuitively lays out the scenarios in which we provide policy improvement estimates, in terms of the underlying characteristics of the baseline policy.
\section{An Estimator for the Value of Policy Improvement}
\label{sec:estimator}
We now present our estimator for the value of policy improvement. We first describe our estimator, which is based on an online estimator due to \citet{luedtke2016statistical}. Then, we present our primary asymptotic normality result alongside a heuristic proof sketch, deferring the full argument to Appendix~\ref{app:clt_proof}. While our main theorem assumes one has access to black-box estimates of the predictable variance of the IPW pseudo-outcomes, we provide a theorem (Theorem~\ref{thm:variance-convergence}) in Subsection~\ref{sec:estimator:variance} that shows how one can build estimates of the predictable variance under a mild complexity assumption on the logging policy class. The rates we require on the variance estimate are much more lenient than those needed in \citet{bibaut2021post}, and as such we can show convergence under a wider range of logging exponents ($\alpha \in [0, 1)$ in our case versus $\alpha < 1/3$). We conclude by discussing computational considerations, presenting a more computationally efficient version of our estimator that uses geometric batching.
We start by describing our estimator, first in words. For each sample size $1 \leq t \leq n$, we use the first $t - 1$ samples to compute a weighted empirical welfare maximizing policy, where weights are determined according to the rate of decay of the propensity of the logging policy. We then perform IPW off-policy evaluation for the learned policy on the $t$th sample, and take the difference between this and the IPW estimate of the value of $q(a \mid x)$.
Inspired by \citet{luedtke2016statistical} and \citet{bibaut2021post}, we then take a combination of these evaluations weighted by inverse predictable standard deviation estimates.
We now describe this estimator more formally. First, for $1 \leq t \leq n$, we define the weighted empirical welfare maximizing (EWM) policy\footnote{For $t = 1$, we can take the first estimated policy $\widehat{\pi}_0$ to be an arbitrary element of $\Pi$.} using an objective outlined in \citet{zhan2024policy}:
\begin{equation}
\label{eq:ewm}
\widehat{\pi}_{t - 1} \in \arg\max_{\pi \in \Pi} \sum_{s = 1}^{t - 1} w_s \widetilde{Y}_s(\pi) = \arg\max_{\pi \in \Pi} \sum_{s = 1}^{t - 1} w_s \sum_{a \in \mathcal{A}}\pi(a \mid X_s)\widetilde{Y}_s(a),
\end{equation}
where we take $w_s = s^{-\alpha}$ and recall that $\widetilde{Y}_t(a) = \mathbbm{1}\{A_t = a\}Y_t/p_t(a \mid X_t)$ and $\widetilde{Y}_t(\pi) = \pi(A_t \mid X_t)Y_t/p_t(A_t \mid X_t)$.
Our estimator is defined to be
\begin{equation}
\label{eq:estimator}
\widehat{\theta}_n := \frac{\sum_{t = 1}^n \widehat{\sigma}_t^{-1}\widetilde{Y}_t\big(\widehat{\pi}_{t - 1}, q\big)}{\sum_{t = 1}^n \widehat{\sigma}_t^{-1}},
\end{equation}
where for each $t \geq 1$, the quantity $\widehat{\sigma}_t^2$ represents an estimate of the predictable variance $\sigma_t^2$ (defined in Equation~\eqref{eq:pred-var}) and $\widehat{Y}_t(\pi, q)$ is as defined in Equation~\eqref{eq:double-pseudo-outcome}.
Before presenting our main theorem, we provide some intuition as to what the estimator is accomplishing. First, we address the policy learning subroutine. Given the data collected up to time $t$, a reasonable estimate of the optimal policy would be to compute the best-in-class policy that maximizes the empirical welfare. However, when the logging exponent satisfies $\alpha > 0$, later inverse propensity weighted samples exhibit inherently higher variance than earlier ones. To account for this gradual increase in variance as samples are collected, we adopt an online policy learning approach of~\citet{zhan2024policy}, who show that down-weighting later observations according to the logging exponent yields minimax optimal regret.
The next step is determining how one should leverage an algorithm for learning high-quality policies to perform inference on the VPI. As proposed previously by~\citet{luedtke2016statistical} (who consider the setting of i.i.d.\ data and unrestricted policy classes), a reasonable approach is to construct a policy on the $t-1$ samples and then perform off-policy evaluation (OPE) on the $t$th sample to estimate its value for each $t \in \{1, 2, \dots, n\}$. The authors then show that these pointwise OPE estimates can be carefully averaged in order to enable valid inference. The ``right'' choice of weights for this average are inverse predictable standard deviation weights, as classical martingale central limit theorems~\citep{hall2014martingale,ganssler1978central, brown1971martingale} require summands to have roughly unit predictable variance.
While \citet{luedtke2016statistical} consider AIPW estimates, for simplicity, and because our focus is experimental domains where the propensity is known, our estimator uses IPW estimates.\footnote{We note that our results could naturally be extended to AIPW estimates as well. However, to guarantee convergence of the variance estimate, we would need to restrict the class of functions containing the regression model $\widehat{\mu}(a, x)$ to be of limited complexity, e.g., a class of finite pseudo-dimension. We choose to study IPW estimators for simplicity's sake.}
While the above paragraphs attempt to build intuition for the estimator, we note that showing convergence is still nontrivial. This is primarily driven by two factors. First, one cannot apply off-the-shelf high-probability regret bounds for weighted EWM, such as those due to \citet{zhan2024policy} and \citet{bibaut2021risk}. These works show that the regret of EWM decays, either in expectation or with high probability, as $O\left(n^{(\alpha - 1)/2}\right)$. Unfortunately, the standard error of our estimator (and, consequently, the width of our confidence intervals) scales at the same $n^{(\alpha - 1)/2}$ rate, which thus bars asymptotic normality. While the stated regret rates are \textit{minimax optimal}, we will see in Section~\ref{sec:regret} that performing weighted EWM actually yields marginally faster expected regret rates of $o(n^{(\alpha - 1)/2})$ \textit{pointwise} in the data generating distribution, which enables valid inference.
Second, constructing sufficiently consistent estimates of the predictable variance that satisfy the consistency assumption of our following theorem is not trivial. In fact, in existing works on OPE under bandit data, \citet{bibaut2021post} require $\alpha < 1/3$ in order to obtain sufficiently consistent estimates, which is significantly more stringent than the setting considered in the present work. We discuss the difficulties of variance estimation below in Section~\ref{sec:estimator:variance}.
With these subtleties in mind, we now present our primary result, which details the asymptotic normality of a studentized version of the estimator $\widehat{\theta}_n$. In what follows, we let $\theta(\pi) := V(\pi) - V(q)$ denote the gap between the value of policy $\pi$ and the baseline $q$. Note that $\theta^\ast = \theta(\pi^\ast)$ for any $\pi^\ast \in \Pi^\ast$.
\begin{theorem}
\label{thm:clt}
Suppose $(Z_n)_{n \geq 1}$ satisfies Assumptions~\ref{ass:observations}, \ref{ass:estimation}, \ref{ass:propensity}, and \ref{ass:ipw_variance_scale}, and that $\Pi$ satisfies Assumption~\ref{ass:disagreement} and is closed. Further, suppose that $\widehat{\sigma}_t$ is $\mathcal{F}_{t - 1}$-measurable and satisfies
\[
\frac{\widehat{\sigma}_t - \sigma_t}{\sigma_t} \xrightarrow[t \rightarrow \infty]{a.s.} 0 \qquad \text{and} \qquad \widehat{\sigma}_t \geq \kappa_t > 0, \forall t \geq 1,
\]
where $(\kappa_t)_{t \geq 1}$ is some sequence tending towards zero.
Then, we have $\frac{\sum_{t= 1}^n\widehat{\sigma}_t^{-1}}{\sqrt{n}}\left\{\widehat{\theta}_n - \theta^\ast\right\} \Rightarrow \mathcal{N}(0, 1)$. Thus, if $\gamma \in (0, 1)$ and $z_{1 - \gamma/2}$ is the $(1 - \gamma/2)$th quantile of a standard normal distribution, the interval
\[
C_{1 - \gamma} := \left[\widehat{\theta}_n - \frac{\sqrt{n}}{\sum_{t = 1}^n \widehat{\sigma}_t^{-1}}z_{1 - \gamma/2}, \widehat{\theta}_n + \frac{\sqrt{n}}{\sum_{t = 1}^n \widehat{\sigma}_t^{-1}}z_{1 - \gamma/2}\right]
\]
forms an asymptotically valid $1 - \gamma$ confidence interval for $\theta^\ast$.
\end{theorem}
To build intuition for the above result, we provide a high-level proof sketch. We present the full proof in Appendix~\ref{app:clt_proof} --- the sketch is just aimed at capturing the main arguments.
\begin{proof}[Proof Sketch for Theorem~\ref{thm:clt}]
The key to our proof is the following decomposition, which splits the difference between our estimate and the true value of policy improvement into two terms:
\begin{align}
\label{eq:clt_decomp}
\frac{\sum_{t = 1}^n \widehat{\sigma}_t^{-1}}{\sqrt{n}}\left\{\widehat{\theta}_n - \theta^\ast\right\} &= \underbrace{\frac{1}{\sqrt{n}}\sum_{t = 1}^n \widehat{\sigma}_t^{-1}\left\{\widetilde{Y}_t\big(\widehat{\pi}_{t - 1}, q\big) - \theta\big(\widehat{\pi}_{t - 1}\big)\right\}}_{\text{Martingale CLT Term}} \\
&\qquad + \underbrace{\frac{1}{\sqrt{n}}\sum_{t = 1}^n \widehat{\sigma}_t^{-1}\left\{\theta\big(\widehat{\pi}_{t - 1}\big) - \theta^\ast\right\}}_{\text{Cumulative Regret Term}}.\nonumber
\end{align}
For any fixed sample size $n$, the first term is a martingale under the natural filtration whose terms roughly have $\frac{1}{n}$ predictable variance. Under a martingale central limit theorem due to \citet{brown1971martingale} (Theorem~\ref{thm:martingale-clt}), one can show asymptotic normality under our variance convergence assumptions.
Next, the second, cumulative regret term represents the bias accumulated from performing OPE not on an optimal policy, but rather on a slightly suboptimal policy learned using weighted EWM. We can make this connection to regret explicit by noting that
\[
\frac{1}{\sqrt{n}}\sum_{t = 1}^n \widehat{\sigma}_t^{-1}\left\{\theta\big(\widehat{\pi}_{t - 1}\big) - \theta^\ast\right\} = -\frac{1}{\sqrt{n}}\sum_{t = 1}^n \widehat{\sigma}_t^{-1}\mathrm{Reg}\big(\widehat{\pi}_{t - 1}
\big).
\]
In Section~\ref{sec:regret}, we show that $\mathbb{E}\left[\mathrm{Reg}\big(\widehat{\pi}_{t - 1}\big)\right] = o(t^{(\alpha - 1)/2})$. Thus, by leveraging results on the convergence of Ces\`aro summations~\citep{bibaut2020sufficient} and noting that $\widehat{\sigma}_t \asymp t^{\alpha/2}$, we see that the entire cumulative regret term satisfies
\[
\frac{1}{\sqrt{n}}\sum_{t = 1}^n \mathbb{E}\left[\widehat{\sigma}_t^{-1}\mathrm{Reg}\big(\widehat{\pi}_{t - 1}
\big)\right] = o(1),
\]
and hence converges to zero in probability. Putting these two pieces together furnishes the desired result.
\end{proof}
\subsection{Consistently Estimating the Variance}
\label{sec:estimator:variance}
The previous subsection established our main central limit theorem for our estimator $\widehat{\theta}_n$. However, we have yet to show that there exists an estimator $\widehat{\sigma}_t^2$ of the predictable variance $\sigma_t^2$ that achieves the requisite convergence rates. Our focus in this subsection is to show that a natural plug-in estimate converges at the desired rate under a combinatorial assumption on the class of logging policies at each point in time.
Our variance estimator and corresponding analysis are largely based on those of \citet{bibaut2021post}, who consider the task of predictable variance estimation under adaptively collected data. We note that there are three primary difficulties that prevent us from directly leveraging the aforementioned estimator in our setting. First, said estimator is designed for a \textit{fixed policy} (more broadly, function) that is being evaluated under contextual bandit data, not one that is continually updated according to a welfare maximization problem. Second, our assumptions, which are based on finite combinatorial dimension, are not comparable to the bracketing entropy assumptions made in \citet{bibaut2021post}. These combinatorial assumptions require us to leverage a substantially different chaining argument for showing variance convergence than the one presented in the aforementioned paper, with the VC-like assumptions greatly complicating the bounding of error in finite-depth chaining.
We discuss the particulars of the proof technique in the relevant appendices (namely, Appendices~\ref{app:variance} and \ref{app:martingale-bounds}).
Third, and most problematically, is that the variance estimate in \citet{bibaut2021post} requires that $\alpha \leq 1/3$ in order to guarantee almost sure convergence. This limitation is particularly undesirable, as any minimax regret optimal logging policy must have a logging exponent of at least $\alpha \geq 1/2$. In this section, we circumvent this restriction by observing that, for performing inference on the value of policy improvement, a significantly weaker notion of variance convergence is permissible.
In more detail, our analysis actually allows the error in a predictable variance estimate to \textit{grow} with the sample size, so long as this error vanishes to zero almost surely when divided by $\sigma_t^2 \asymp t^{\alpha}$. This weaker convergence requirement will ultimately allow us to show variance consistency under logging policies with aggressive exploitation (i.e., $\alpha \approx 1$).
We now describe the variance estimator we consider. Using the contrast functions $g_\pi(a \mid x) := \mathbbm{1}\{\pi(x) = a\} - q(a \mid x)$ outlined earlier, we define the contrast under the (predictable) learned policy at time $t$ as $g_t(a \mid x) := g_{\widehat{\pi}_{t - 1}}(a \mid x)$. In terms of these contrasts, we can express the predictable variance $\sigma_t^2$ as
\begin{equation}
\label{eq:pred-variance}
\sigma_t^2 = \mathbb{E}\left(\frac{g_t(A_t \mid X_t)^2 Y_t^2}{p_t(A_t \mid X_t)^2} \mid \mathcal{F}_{t - 1}\right) - \mathbb{E}\left(\frac{g_t(A_t \mid X_t)Y_t}{p_t(A_t \mid X_t)} \mid \mathcal{F}_{t - 1}\right)^2.
\end{equation}
Using the above decomposition, we propose estimating $\sigma_t^2$ by estimating the first and second terms separately and then taking a difference. In more detail, we define the estimators for the first moment and the second moment as
\begin{equation}
\label{eq:linear-term}
\widehat{\Phi}_{1, t} := \frac{1}{t - 1}\sum_{s = 1}^{t - 1}\frac{g_t(A_s \mid X_s)}{p_s(A_s \mid X_s)}Y_s
\end{equation}
and
\begin{equation}
\label{eq:square-term}
\widehat{\Phi}_{2, t} := \frac{1}{t - 1}\sum_{s = 1}^{t - 1}\frac{g_t(A_s \mid X_s)^2}{p_s(A_s \mid X_s)p_t(A_s \mid X_s)}Y_s^2.
\end{equation}
Then, we define our estimator for the overall predictable variance at sample size $t$ as
\begin{equation}
\label{eq:pred-var-est}
\widetilde{\sigma}_t^2 := \widehat{\Phi}_{2,t} - \widehat{\Phi}_{1, t}^2,
\end{equation}
where we can let $\widetilde{\sigma}_1^2$ be arbitrary.
We only use the first $t - 1$ samples to construct our estimate of $\sigma_t^2$ in order to ensure the estimate is itself predictable, i.e.\ $\mathcal{F}_{t - 1}$-measurable. As noted above, this is exactly analogous to the variance estimator outlined in \citet{bibaut2021post}, modulo that we consider (i) contrasts in policy values and (ii) adaptively update the policy as more samples are gathered. Again, what will differ substantially is the form of our convergence guarantee and the structure of our analysis.
Under just our complexity assumption on the class $\Pi$, one can show the consistency of $\widehat{\Phi}_{1, t}$ using arguments based on empirical process theory. However, because the estimate $\widehat{\Phi}_{2, t}$ also depends on the (random) choice of logging policy at time $t$, we cannot hope for the estimate to converge unless we restrict the complexity of the set of valid logging policies. We leverage the following assumption, which restricts the \textit{pseudo-dimension} of the class in which the adaptive logging policy lies, which we denote by $d_P$. We define pseudo-dimension and its relationship to other notions of combinatorial dimension in Appendix~\ref{app:combinatorial-dimension}. This assumption should again be contrasted with the bracketing-type assumptions made in \citet{bibaut2021post}.
\begin{ass}[Logging Class Complexity]
\label{ass:logging}
For each $t \geq 1$, there is some bounded fixed class $\mathcal{P}_t$ such that (i) $t^{-\alpha}p_t^{-1} \in \mathcal{P}_t$ almost surely, (ii) $\sup_{t \geq 1}d_P(\mathcal{P}_t) \leq \mathfrak{p}$ for some $\mathfrak{p} > 0$, and (iii) $\sup_{\substack{t \geq 1 \\ r \in \mathcal{P}_t}} \|r\|_\infty \leq P$, for some constant $P > 0$.
\end{ass}
\begin{theorem}
\label{thm:variance-convergence}
Suppose Assumptions~\ref{ass:observations}, \ref{ass:disagreement}, \ref{ass:estimation}, \ref{ass:propensity}, \ref{ass:ipw_variance_scale}, and \ref{ass:logging} hold. Then, the following holds:
\begin{equation}
\label{eq:variance-rate}
\frac{\widetilde{\sigma}_t^2 - \sigma_t^2}{\sigma_t^2} \xrightarrow[t \rightarrow \infty]{a.s.} 0.
\end{equation}
\end{theorem}
We prove Theorem~\ref{thm:variance-convergence} in Appendix~\ref{app:variance}. Our argument relies on developing martingale concentration inequalities for infinite collections of martingales indexed by classes of finite pseudo-dimension. We detail and prove these inequalities in the first part of Appendix~\ref{app:martingale-bounds}. We then use high-probability bounds alongside the Borel-Cantelli lemma to obtain the scaled, almost sure convergence of $\widehat{\Phi}_{2, t}$ and $\widehat{\Phi}_{1, t}$.
We note that Theorem~\ref{thm:clt} actually requires the variance estimates to be bounded away from zero by some decreasing sequence $(\kappa_t)$. This can be accomplished by simply performing lower truncation on our variance estimate. In more detail, we can simply set our variance estimate to be $\widehat{\sigma}_t := \sqrt{\widetilde{\sigma}_t^2 \lor \kappa_t^2}$. Since $\sigma_t^2 \geq c_\sigma t^{\alpha}$ for sufficiently large $t$, the results of Theorem~\ref{thm:variance-convergence} imply truncation will only ever be applied to a finite number of sample sizes.
\subsection{A Batched Estimator}
The estimator described in Equation~\eqref{eq:estimator} involves repeatedly computing an empirical welfare maximizing policy on all prefixes of data, thus resulting in a number of fits proportional to the sample size.
In general, exactly solving the empirical risk minimization is a computationally expensive task, often requiring the use of enumeration or mixed integer programming (MIP) based methods. While efficient approximations for EWM policy learning exist (e.g., greedy splitting for policy trees), such methods are not guaranteed to converge to a population maximizer in the large sample limit.
Due to the costliness of exactly solving empirical welfare maximization, we propose a more efficient, batch-based version of our estimator in this section. The modified algorithm works by splitting time into geometrically spaced epochs and refitting a policy using historical data at the beginning of each epoch. The possibility of such batched estimators was discussed in Section 6.1 of~\citet{luedtke2016statistical} in the case of i.i.d.\ data, but was not formally worked out. We formalize these ideas in Algorithm~\ref{alg:online-epoch} and Corollary~\ref{cor:epoch_estimator} below, with a more detailed discussion in the remark following the corollary. We note that our algorithm/estimator also allows (but does not require) a burn-in period of $b_n$ samples for training the first policy, which is intended to prevent the use of poorly trained policies that may amount to random guessing in practice. The proof of the following result is exactly analogous to that of Theorem~\ref{thm:clt}, and so we do not include it.
\begin{algorithm}[t]
\caption{Batched Estimator for $\theta^\ast$}
\label{alg:online-epoch}
\begin{algorithmic}[1]
\Require Samples $Z_1, \dots, Z_n$, confidence parameter $\delta \in (0, 1)$, a policy class $\Pi$, burn-in period $b_n$, indices $b_n = \tau_1 < \tau_2 < \cdots < \tau_{H + 1} = n$, truncation levels $(\kappa_t)_{t \geq 1}$, baseline $q$.
\Ensure Estimate $\widehat{\theta}_n$ of $\theta^\ast := V^\ast - V(q)$, $(1- \delta)$-confidence interval $\mathcal{C}_{1 -\delta}$ for $\theta^\ast$.
\For{$h \in [H]$}
\State Compute $\widehat{\pi}_{h} := \arg\max_{\pi \in \Pi} \sum_{s = 1}^{\tau_h} s^{-\alpha}\frac{g_\pi(A_s \mid X_s)}{p_s(A_s \mid X_s)}Y_s$.
\State For $t \in \{\tau_h + 1, \dots, \tau_{h + 1}\}$, define $\widetilde{\sigma}_{t}^2$ by
\[
\widetilde{\sigma}_t^2 := \frac{1}{t - 1}\sum_{s = 1}^{t - 1}\frac{g_{\widehat{\pi}_h}(A_s \mid X_s)^2}{p_s(A_s \mid X_s)p_t(A_s \mid X_s)}Y_s^2 - \left(\frac{1}{t - 1}\sum_{s = 1}^{t - 1}\frac{g_{\widehat{\pi}_h}(A_s \mid X_s)}{p_s(A_s \mid X_s)}Y_s\right)^2
\]
\State Set $\widehat{\sigma}_t := \sqrt{\widetilde{\sigma}_t^2 \lor \kappa_t^2}$.
\EndFor
\State Compute estimate
\[
\widehat{\theta}_n := \frac{\sum_{h = 1}^{H}\sum_{t = \tau_h + 1}^{\tau_{h + 1}}\widehat{\sigma}_{t}^{-1}\frac{g_{\widehat{\pi}_h}(A_t \mid X_t)}{p_t(A_t \mid X_t)}Y_t}{\sum_{h = 1}^{H}\sum_{t = \tau_h + 1}^{\tau_{h + 1}}\widehat{\sigma}_t^{-1}}.
\]
\State Return the estimate $\widehat{\theta}_n$ and $(1 - \delta)$ confidence interval
\[
\mathcal{C}_{1 - \delta} := \left[\widehat{\theta}_n - \frac{\sqrt{n - b_n}}{\sum_{t = b_n + 1}^n \widehat{\sigma}_t^{-1}}z_{1 - \delta/2}, \widehat{\theta}_n + \frac{\sqrt{n - b_n}}{\sum_{t = b_n + 1}^n \widehat{\sigma}_t^{-1}}z_{1 - \delta/2}\right]
\]
\end{algorithmic}
\end{algorithm}
\begin{corollary}
\label{cor:epoch_estimator}
Suppose the assumptions of Theorem~\ref{thm:clt} hold and let $\widehat{\theta}_n$ be as defined in Algorithm~\ref{alg:online-epoch}. Further, suppose there are constants $c \in (0, 1)$ and $C > 0$ such that $\tfrac{\tau_{h + 1}}{\max\{\tau_h, 1\}} \leq C$ for each $h$ and that $n - b_n \geq c n$. Then, we have
\[
\frac{\sum_{t = b_n + 1}^{n}\widehat{\sigma}_t^{-1}}{\sqrt{n - b_n}}\left(\widehat{\theta}_n - \theta^\ast\right) \Rightarrow \mathcal{N}(0, 1),
\]
and hence $\mathcal{C}_{1 - \delta}$ is an asymptotically-valid $1 - \delta$ confidence interval for $\theta^\ast$.
\end{corollary}
We note that the consistency of the variance estimate described in Algorithm~\ref{alg:online-epoch} follows from the proof of Theorem~\ref{thm:variance-convergence}, as said proof establishes uniform convergence over a relevant class of functions.
\begin{rmk}
Corollary~\ref{cor:epoch_estimator} shows that our estimator still provides valid coverage if we refit a welfare-maximizing policy only on the order of $\log(n)$ times, where $n$ again denotes the sample size. One may wonder then if we could get away with a constant number of refits. For concreteness, we will speculate about the possibility of simply doing \textit{sample splitting}, where $b_n = o(n)$ samples are used to learn a policy, and the remaining $n - b_n$ are used for evaluation (obviously, we assume $b_n \rightarrow \infty$). Straightforward analysis yields that we would need regret to vanish at a rate of $\mathrm{Reg}\big(\widehat{\pi}_{b_n}\big) = o_\mathbb{P}\left(n^{(\alpha - 1)/2}\right)$, which under the assumption that $b_n = o(n)$ is strictly faster than the rates that we will show in Section~\ref{sec:regret} below. For instance, if $b_n = n/\log(n)$, one would need a regret rate of
\[
\mathrm{Reg}\big(\widehat{\pi}_{b_n}\big) = o_\mathbb{P}\left((b_n\log(b_n))^{(\alpha - 1)/2}\right).
\]
Such faster rates may indeed be possible under margin conditions on the conditional average treatment effect or blip effects, and \citet{girard2025online} discuss such high-probability rates in online settings. However, the margin condition discussed in the aforementioned paper implicitly requires a unique optimal policy, so deriving such faster rates under non-unique optimal policies would be an interesting direction for future work.
\end{rmk}
\begin{rmk}
We now conclude this subsection by briefly discussing the heuristic batching approach outlined in Section 6.1 of \citet{luedtke2016statistical}. In this subsection, the authors note that one can first estimate the nuisances (e.g., outcome regression and propensity in the unrestricted setting) on the first $b_n$ samples and then break the remaining $n - b_n$ into a constant number of chunks/batches. However, this approach actually requires that the nuisances estimated on the first batch of data converge at \textit{faster} than standard estimation rates, with the degree faster depending on the size of the burn-in period.
To illustrate this, we consider a concrete example in the binary treatment setting under i.i.d.\ data and unrestricted policy classes. Define the conditional average treatment effect as $\tau^\ast(x) := \mu_0(1, x) - \mu_0(0, x)$ and suppose that $\mathbb{P}(0 < |\tau^\ast(X)| \leq t) \lesssim t^\beta$ for some $\beta > 0$ and all $t \leq t_0$. If one refits nuisances at each step (or uses the geometric batching that we outline above), the estimate of the outcome regression would need to satisfy $\|\widehat{\mu}_n - \mu_0\|_{L^2} = o_\mathbb{P}\left(n^{-a_\beta}\right)$, where $a_\beta := \frac{2 + \beta}{4(1 + \beta)}$. If, however, one leverages just a constant number of fits and takes $b_n = n/\log(n)$ (as in the example above), the $L^2$ error in regression estimation would need to scale as $o_\mathbb{P}\left((b_n\log(b_n))^{-a_\beta}\right)$. We also note that setting $b_n = n/\log(n)$ actually sacrifices a large fraction of the samples even at moderate to large sample sizes, which empirically is likely to result in worse performance. If one instead wanted to take $b_n = \sqrt{n}$, a significantly faster nuisance estimation rate would be needed. In particular, one would need $\|\widehat{\mu}_{b_n} - \mu_0\|_{L^2} = o_\mathbb{P}\left(b_n^{-\frac{2 + \beta}{2(1 + \beta)}}\right)$.
This is thus one drawback of using a constant number of fits as outlined in \citet{luedtke2016statistical}.
\end{rmk}
\section{Faster Regret for Weighted Empirical Welfare Maximization}
\label{sec:regret}
To ensure the asymptotic normality of our estimator, we need to ensure that the ``bias'' accumulated from evaluating a learned policy is negligible relative to the width of the confidence intervals. As seen in our proof sketch, to show this accumulated bias is negligible, it suffices to show that the expected regret incurred through weighted EWM vanishes at rates faster than $n^{(\alpha - 1)/2}$, i.e.,
\[
\underbrace{\mathbb{E}\left[\mathrm{Reg}\big(\widehat{\pi}_{n}\big)\right] = o\big(n^{(\alpha - 1)/2}\big)}_{\text{Fast Expected Regret Rates}} \Longrightarrow \underbrace{\frac{1}{\sqrt{n}}\sum_{t = 1}^n \widehat{\sigma}_t^{-1}\left\{\theta\big(\widehat{\pi}_{t - 1}\big) - \theta^\ast\right\} = o_\mathbb{P}(1)}_{\text{Negligible Accumulated Bias}}.
\]
At first glance, obtaining regret rates such as the above may seem impossible. In their work, \citet{zhan2024policy} show that the weighted empirical welfare maximization procedure outlined in Equation~\eqref{eq:ewm} yields expected regret rates of $O\left(n^{(\alpha - 1)/2}\right)$, which is on the same order as the width of the confidence intervals outlined in Theorem~\ref{thm:clt}. Further, they show a matching lower bound --- the minimax expected regret of \textit{any learning algorithm} cannot decay faster than $\Omega\left(n^{(\alpha - 1)/2}\right)$. However, there is an important and subtle difference between our setting and that considered by \citet{zhan2024policy}. The aforementioned authors are considering a \textit{distribution uniform, finite sample} setting, obtaining upper bounds with known constants that hold regardless of the choice of data generating distribution and sample size. We instead aim to obtain convergence guarantees that hold \textit{pointwise} for the specific data generating distribution being considered, and we want \textit{asymptotic convergence guarantees}. In particular, the exact constants in our setting can actually depend on the distribution, and sample size at which regret starts becoming negligible can also be different for each distribution.
We are not the first to realize that such faster regret rates are possible. \citet{luedtke2020performance} study exactly this phenomenon in the setting of i.i.d.\ data. Under mild distributional assumptions, they show that the regret incurred through standard EWM actually vanishes as $o_\mathbb{P}(n^{-1/2})$ in a distributionally pointwise sense. This is notably (infinitesimally) faster than the $\Theta(n^{-1/2})$ minimax rates known in this setting~\citep{athey2021policy, zhan2024policy}. The authors also discuss more general settings under which such fast regret rates are possible, noting that such faster rates are possible under the assumption that the empirical process associated with the accumulated data and indexed by the policy class approaches a tight Gaussian limit.
Our contribution in this section is that we show fast expected regret rates hold under adaptively collected data with decaying propensities. Unlike the arguments made in \citet{luedtke2020performance}, our approach for showing convergence is constructive, relying on finite sample expectation and high-probability bounds for collections of martingales indexed by VC-classes alongside a localization argument. In particular, our results do not rely on the assumption that the empirical process converges to a tight Gaussian limit.\footnote{The verification of such convergence is non-obvious in our setting of adaptively collected data with decaying propensities.}
Further, our guarantees are actually stronger, as the aforementioned work only demonstrates ``in probability'' regret convergence, which as noted above is insufficient for the convergence of our estimator.
Showing convergence of the expectation requires arguing the uniform integrability of the \textit{scaled regret process} $\big(n^{(1 - \alpha)/2}\mathrm{Reg}(\widehat{\pi}_{n - 1})\big)_{n \geq 1}$. This, in turn, requires intricate, high-probability chaining-based bounds for collections of martingales. We detail these in Appendix~\ref{app:martingale-bounds}.
We now state the main contribution of this section, which is our theorem on fast expected regret convergence for weighted empirical welfare maximization.
\begin{theorem}
\label{thm:fast-regret}
Suppose $(Z_n)_{n \geq 1}$ are observations satisfying Assumptions~\ref{ass:observations}, \ref{ass:propensity}, and the first part of Assumption~\ref{ass:estimation}. Further, assume that $\Pi$ is a closed policy class satisfying Assumption~\ref{ass:disagreement}. Let $\widehat{\pi}_n$ be as defined in Equation~\eqref{eq:ewm}. Then
\[
\mathbb{E}\left[\mathrm{Reg}\big(\widehat{\pi}_n\big)\right] = o\left(n^{\frac{\alpha - 1}{2}}\right).
\]
\end{theorem}
We provide a full proof of the above theorem in Appendix~\ref{app:fast-regret}. To build intuition, we provide a heuristic proof sketch that shows $\mathrm{Reg}\big(\widehat{\pi}_n\big) = o_\mathbb{P}(n^{(\alpha - 1)/2})$, and leave the proof of uniform integrability fully to the appendix.
\begin{proof}[Proof Sketch of Theorem~\ref{thm:fast-regret}]
In this sketch, we consider the ``disagreement metric'' $d(\pi, \rho) := \mathbb{P}\left(\pi(X) \neq \rho(X)\right)^{1/2}$, under which policies are close if they agree with high probability. We also define $w_t := t^{-\alpha}$ and $S_{n, -\alpha} := \sum_{t = 1}^n w_t$ and the process
\[
M_n(\pi, \rho) := \sum_{t = 1}^n w_t \left\{\widetilde{Y}_t(\pi) - \widetilde{Y}_t(\rho) - \left(V(\pi) - V(\rho)\right)\right\},
\]
which is a martingale for any fixed $\pi, \rho \in \Pi$. We leverage two key ingredients in our proof:
\begin{itemize}
\item \textit{A Basic Inequality.} We can bound the regret as
\[
\mathrm{Reg}\big(\widehat{\pi}_n\big) \leq \frac{1}{S_{n, -\alpha}}\inf_{\pi^\ast \in \Pi^\ast}M_n\left(\widehat{\pi}_n, \pi^\ast\right) \leq \frac{1}{S_{n, -\alpha}}\sup_{d(\pi,\rho) \leq \delta}M_n(\pi, \rho),
\]
where the final inequality holds on the event $\Big\{d\big(\widehat{\pi}_n, \Pi^\ast\big) \leq \delta\Big\}$.
\item \textit{A Localized Bound.} The expectation of the above localized empirical process is well controlled:
\begin{equation*}
\mathbb{E}\left[\frac{1}{S_{n, -\alpha}}\sup_{d(\pi, \rho) \leq \delta}\left|M_n(\pi, \rho)\right|\right] \lesssim \delta n^{\frac{\alpha - 1}{2}}\sqrt{\mathfrak{v}\log\left(\frac{A}{\delta}\right)} + n^{\alpha - 1}\mathfrak{v}\log\left(\frac{A}{\delta}\right)\log(n)^2,
\end{equation*}
where again $\mathfrak{v}$ is the VC-dimension of the difference class and $A \geq e$ is some constant that may depend on $|\mathcal{A}|$.
\end{itemize}
Using the above ingredients, we can prove the target convergence in probability rate in three steps. First, noting that $\Big\{d\big(\widehat{\pi}_n, \Pi^\ast\big) \leq 1\Big\}$ has probability one, we can use the above basic inequality, the localized bound with $\delta = 1$, and Markov's inequality to show that
$\mathrm{Reg}\big(\widehat{\pi}_n\big) = o_\mathbb{P}(1)$.
Next, regret consistency and continuity of regret ensure $d\big(\widehat{\pi}_n, \Pi^\ast\big) = o_\mathbb{P}(1)$. In other words, the sequence of learned policies $(\widehat{\pi}_n)$ gets arbitrarily close to the optimal set $\Pi^\ast$, although they may not converge to any fixed policy.
Finally, the above convergence yields a sequence $(\delta_n)$ slowly tending towards zero such that
\[
\mathbb{P}\big(\mathcal{E}_n\big) \xrightarrow[n \rightarrow \infty]{} 1, \quad \text{where} \quad \mathcal{E}_n := \Big\{d\big(\widehat{\pi}_n, \Pi^\ast\big) \leq \delta_n\Big\}.
\]
Heuristically, $\mathcal{E}_n$ occurs with overwhelming probability for large $n$, and so Markov's inequality yields for any $\epsilon > 0$ that
\begin{align*}
&\mathbb{P}\left(\mathcal{E}_n \cap \Big\{n^{(1 - \alpha)/2}\mathrm{Reg}\big(\widehat{\pi}_n\big) \geq \epsilon\Big\}\right) \leq \frac{1}{\epsilon}\mathbb{E}\left[\frac{1}{\sqrt{S_{n, -\alpha}}}\sup_{d(\pi, \rho) \leq \delta_n} \left|M_n(\pi, \rho)\right|\right] \\
&\quad \leq \frac{1}{\epsilon}\left\{\delta_n\sqrt{\mathfrak{v}\log\left(\frac{A}{\delta_n}\right)} + n^{\frac{\alpha - 1}{2}}\mathfrak{v}\log\left(\frac{A}{\delta_n}\right)\log(n)^2\right\}.
\end{align*}
where we have leveraged the fact that $S_{n, -\alpha} \asymp n^{1 - \alpha}$.
The first term will always go to zero as $n \rightarrow \infty$. The second term will tend towards zero if $\delta_n$ decays sufficiently slowly.
The above steps, when formalized, guarantee the desired convergence rate in probability. While we do not sketch the argument for uniform integrability in this part of the paper, it follows in a similar manner. However, instead of using expectation bounds, we actually need to leverage and derive high-probability chaining bounds instead. We defer the discussion of this until the appendix.
\end{proof}
\begin{rmk}
\label{rmk:fast_regret}
We note that Theorem~\ref{thm:fast-regret} is simultaneously a very powerful and weak result. The result is strong in that it enables the asymptotic convergence of our estimator to the true value of policy improvement, which could not have been established via existing, distribution-uniform expected regret guarantees.
However, the result does not give a practitioner a quantitative measure of how rapidly the scaled regret process $n^{(1 - \alpha)/2}\mathrm{Reg}(\widehat{\pi}_n)$ tends towards zero as the sample size grows. In our experiments in the following section, we try to ascertain how quickly the above scaled quantity vanishes. We investigate this convergence both in fully synthetic and semi-synthetic data generating processes. Further, we study the convergence when the empirical welfare maximization problem is solved exactly or approximately (such as through greedy splits for policy trees).
While our empirical findings show favorable convergence rates, they naturally do not preclude slower decay of the scaled regret. We hypothesize that it is possible to construct data generating processes/policy classes such that the scaled regret converges arbitrarily slowly to zero, but we leave the exact construction of these objects for future work.
\end{rmk}
\section{Experiments}
\label{sec:exp}
We now study the empirical behavior of our estimator for the value of policy improvement. Our experiments in the sequel are aimed at evaluating the coverage of our estimator under data generating processes where there are multiple (in fact, infinitely many) optimal treatment policies.
We consider both synthetic experiments (Section~\ref{sec:exp:synthetic}), in which the true conditional average treatment effect is known and thus the optimal policy value can be computed exactly, semi-synthetic experiments (Section~\ref{sec:exp:semi-synthetic}) based on the \textit{Jester} dataset~\citep{goldberg2001eigentaste}, and then experiments on the impact of interventions on employment of Jordanians and Syrians given a prior study~\cite{caria2024adaptive}.
Before diving into our findings, we begin by describing our comparators, providing greater detail in Appendix~\ref{app:exp}. We compare our adaptively-weighted estimator (\texttt{AW}) against the natural baselines summarized in
\cref{tab:comparators}, all computed on identical adaptively-logged data. The
estimators of \citet{bibaut2021post} (\texttt{CADR}) and \citet{zhan2021off} (\texttt{StabVar}) are designed for
off-policy evaluation of a single \emph{fixed} policy; we turn them into estimators of policy
improvement by learning a policy on part of the data and evaluating it on the rest. In particular, we consider this sample splitting in two
regimes --- a sublinear burn-in regime where a vanishing fraction of the data is used for policy learning, and a $50/50$ split.
We also consider a double-dipping estimator (\texttt{DD}), which
learns and evaluates a policy on the entire sample. Interestingly, for policy classes satisfying the complexity assumptions of this paper, double dipping will yield asymptotically normal inference so long as there is a unique optimal treatment policy~\citep{fang2019inference, carcamo2020directional}. However, when there are multiple optimal policies, the limiting distribution is non-normal, and is instead characterized by the supremum of an empirical process indexed by the set of treatment policies.
We note that the convergence of the above sample splitting estimators is not a priori obvious, and requires the faster regret rates from this paper to hold.\footnote{For the $50/50$ sample-splitting estimators, the faster regret rates established in this paper ensure that the regret of the learned policy is negligible relative to the standard error of its estimated value. The sublinear burn-in versions need not enjoy the same guarantee and are included as heuristic comparators.}
\begin{table}[!htb]
\centering
\footnotesize
\setlength{\tabcolsep}{5pt}
\caption{A summary of comparators and the design choices that distinguish them. \texttt{CADR}{} and \texttt{StabVar}{} are each run in two modes: a sublinear burn-in
split consisting of $b_n = o(n)$ samples, and a $50/50$ split ($b_n = n/2$).}
\label{tab:comparators}
\begin{tabular}{l l l c c c}
\toprule
Estimator & Learns policy on & Evaluates on & Inv.-SD wt. & Refits & Out-of-sample \\
\midrule
\texttt{AW}{} (ours) & geometric epochs & future rounds & $\checkmark$ & $\checkmark$ & $\checkmark$ \\
\texttt{CADR}{} & prefix ($b_n$ or $n/2$) & remaining rounds & $\checkmark$ & $\times$ & $\checkmark$ \\
\texttt{StabVar}{} & prefix ($b_n$ or $n/2$) & remaining rounds & $\times$ & $\times$ & $\checkmark$ \\
\texttt{DD}{} & all $n$ & all $n$ (same data) & $\times$ & $\times$ & $\times$ \\
\bottomrule
\end{tabular}
\end{table}
\subsection{Synthetic Experiments}
\label{sec:exp:synthetic}
In this subsection, we evaluate the finite sample performance of our estimator on a synthetic data generating process with a binary treatment. We first describe our experimental setup, including our choice of data generating process and logging rates and policies. We then discuss our findings, which generally indicate that our estimator obtains better coverage than comparators while maintaining smaller confidence intervals. Throughout, the baseline policy will correspond to uniform randomization, i.e., $q(0 \mid x) = q(1 \mid x) = 1/2$ regardless of covariates $x$.
\paragraph{Policy Class.} In this section, we take the policy class $\Pi$ to be the set of all depth 2 policy trees.
When fitting these trees, we impose the empirical analogue, requiring at least 15\% of the training observations in each leaf.
We solve the welfare
maximization problem \emph{exactly} using the optimal policy-tree solver of
\citet{sverdrup2020policytree}.
One example of an optimal policy is a depth 1 tree that splits at $x_1 = 0.4$. This gives leaves of mass
$0.4$ and $0.6$, so the $15\%$ floor is not binding.
\paragraph{Data-generating process.} We propose a data generating process (DGP) with a binary treatment. First, covariates
$X = (X_1,\dots,X_5)$ are generated such that $X_j \stackrel{\mathrm{iid}}{\sim} \mathrm{Unif}(0,1)$.
The expected outcome of a unit under control is then given by $\mu_0(x) := 1 + 0.4\Bigl(x_2-\tfrac12\Bigr) + 0.3\Bigl(x_3-\tfrac12\Bigr)^2 - 0.2\,x_4 x_5$.
The conditional average treatment effect is given by:
\[
\tau_0(x) :=
\begin{cases}
+1, & x_1 \in [0,\,0.4),\\
\phantom{+}0, & x_1 \in [0.4,\,0.7),\\
-1, & x_1 \in [0.7,\,1].
\end{cases}
\]
The potential outcomes are $Y(a) := \mu_0(X) + a\tau_0(X) + 0.2\epsilon$ with
$\epsilon \sim \mathcal{N}(0,1)$ and $a \in \{0,1\}$, and the observed outcome is $Y := Y(A)$. Under this CATE there are in fact \textit{infinitely many} optimal depth 2 policy trees. We illustrate two such trees in Figure~\ref{fig:multiple-optima} in Appendix~\ref{app:exp:synth} below, but we note that any depth 1 tree that splits at $x_1 \in [0.4, 0.7]$ indeed attains the optimal value. The true VPI in this setting is $\theta^\ast = V^\ast -
V(q) = 0.350$.
\paragraph{Logging Policies.} Treatments are assigned per an $\epsilon_t$-greedy
logging policy with $\epsilon_t = t^{-\alpha}$. At round $t$, with probability $\epsilon_t$ the action is
drawn uniformly at random from $\mathcal{A} = \{0, 1\}$. Otherwise, the treatment is assigned greedily as the action with the highest empirical predictable mean, with ties broken lexicographically:
\begin{gather*}
\widehat{a}_t := \arg\max_{a \in \mathcal{A}}\widehat{\rho}_{t - 1}(a), \;\; \text{where}\quad \widehat{\rho}_{t - 1}(a) := \frac{1}{t - 1}\sum_{s = 1}^{t - 1}\widetilde{Y}_s(a) \\
A_t \sim p_t(\cdot \mid X_t) \qquad \text{where } p_t(a \mid x) = \frac{\epsilon_t}{2} + (1 - \epsilon_t)\mathbbm{1}\{a = \widehat{a}_t\}.
\end{gather*}
We adopt the convention that treatments are assigned uniformly at random when $t = 1$.
\paragraph{Evaluation.} We consider $\alpha \in \{0, 0.1, 0.25, 0.5\}$ and sample
sizes $n \in \{2000, 5000, 10000, 15000\}$ with respective sublinear burn-in periods $b_n \in \{500, 1000,
1500, 2000\}$. We fit \texttt{AW}{} using Algorithm~\ref{alg:online-epoch} with geometric epochs satisfying $\tau_{h + 1} - \tau_h \approx 1.5^h$, flooring the result in order to ensure batch size is an integer. For each configuration we run $250$ independent replications and
report coverage of the nominal $95\%$ intervals and the average interval width.
\paragraph{Findings.} We show the coverage of all estimators as a function of the sample size and logging coefficient $\alpha$ in Figure~\ref{fig:nu-cov-synth}.
Further, we compare the coverage and average confidence interval width of all estimators in Figure~\ref{fig:nu-pareto-synth}, thus showing tradeoffs between coverage and confidence interval width.
We show exact coverage numbers (with 95\% Wilson CIs) for our estimator alongside top comparators (\texttt{StabVar}{} and \texttt{CADR}{} with 50/50 splits) in~\Cref{tab:nu-cov-synth} of Appendix~\ref{app:exp:synth}.
We see that, due to non-uniqueness of the optimal treatment policy, the \texttt{DD}{} under-covers at every sample size, with
coverage hovering between roughly $0.51$ and $0.66$.
In contrast, \texttt{AW}{} and the two $50/50$ sample splits sit at or near the nominal level for $\alpha
\le 0.25$, with \texttt{AW}{} delivering the smallest confidence interval widths.
We note that all estimators exhibit diminished performance for $\alpha = 0.5$.
There, \texttt{AW}{}'s coverage dips to
$\approx 0.77$--$0.82$.
As evidenced in Section~\ref{sec:exp:regret}, the \textit{scaled regret} $\mathrm{Reg}(\widehat{\pi})/n^{(\alpha - 1)/2}$ vanishes slowly as $n$ grows for larger $\alpha$, thus indicating that larger sample sizes may be needed to meet the desired coverage. While \texttt{StabVar}{} has coverage that is similar to our \texttt{AW}, and better for $\alpha=0.5$, we also note that \texttt{StabVar}{} has confidence intervals that are around $1.5\times$ wider than \texttt{AW}{} in this setting, which may also aid in coverage.
In Figure~\ref{fig:nu-pareto-synth} we see that our \texttt{AW}{} presents the strongest balance of tighter confidence intervals and coverage.
\begin{figure}[!htbp]
\centering
\includegraphics[width=\linewidth]{figures/syn-cov-grid_minfrac=none.pdf}
\caption{Empirical coverage versus sample size in the synthetic DGP for all six
estimators at logging exponents $\alpha \in \{0, 0.1, 0.25, 0.5\}$. Error bars are Wilson $95\%$
intervals and the dashed line is the nominal $0.95$ coverage target. Double-dipping (\texttt{DD}, the lowest curve)
under-covers and does not recover with $n$, while \texttt{AW}{} and the $50/50$ estimators obtain nominal coverage except in the $\alpha = 0.5$ case.}
\label{fig:nu-cov-synth}
\end{figure}
\begin{figure}[!t]
\centering
\begin{subfigure}[t]{0.4\textwidth}
\includegraphics[width=\linewidth]{figures/synth_pareto_a0.png}
\caption{$\alpha = 0$.}
\end{subfigure}
\begin{subfigure}[t]{0.4\textwidth}
\includegraphics[width=\linewidth]{figures/synth_pareto_a1.png}
\caption{$\alpha = 0.1$.}
\end{subfigure}\hfill
\begin{subfigure}[t]{0.4\textwidth}
\includegraphics[width=\linewidth]{figures/synth_pareto_a25.png}
\caption{$\alpha = 0.25$.}
\end{subfigure}
\begin{subfigure}[t]{0.4\textwidth}
\includegraphics[width=\linewidth]{figures/synth_pareto_a5.png}
\caption{$\alpha = 0.5$.}
\end{subfigure}
\caption{The Pareto frontier of empirical coverage (x-axis) and confidence interval width (y-axis) in the synthetic DGP. We examine this frontier at $n = 15{,}000$ samples and logging exponents
$\alpha \in \{0, 0.1, 0.25, 0.5\}$. Estimators toward the lower right are better calibrated.}
\label{fig:nu-pareto-synth}
\end{figure}
\subsection{Semi-synthetic Experiments}
\label{sec:exp:semi-synthetic}
We now consider a substantially more realistic experiment based on raw user ratings from the Jester
joke-rating dataset of \citet{goldberg2001eigentaste}. The Jester dataset consists of 24,983 rows, each corresponding to a single user considered in the study. Each user was tasked with rating 100 jokes on a scale of -10.0 to 10.0, with the original study retaining the ratings of all units who rated more than 36 jokes. In the sequel, we consider the subset of 14,116 users who successfully rated all 100 jokes. We design a semi-synthetic data generating process on top of these rows based on sampling with replacement, where a user's expected rating of a joke is given by the true ratings in the dataset. We use a small number of jokes as treatments, letting a user's ratings of said jokes represent expected outcomes. A larger subset of jokes serves as covariates. We now describe our DGP in more detail.
\paragraph{DGP, Logging Policies, and Policy Class.}
We treat the five jokes with IDs $\mathcal{J} := \{16, 57, 41, 81, 50\}$ as
candidate treatments. We then set $\mathcal{A} := \mathcal{J} \cup \{50'\}$ as the treatment set, where $50'$ is an exact duplicate of arm $50$, i.e., has the same associated (expected) potential outcomes. These jokes are chosen so that no single joke is uniformly preferred over others. We display both marginal and pairwise diagnostics for the selected jokes (i.e., treatments) in Tables~\ref{tab:treatment-summary} and~\ref{tab:treatment-corr} in Appendix~\ref{app:exp:semi-synth}, with the former showing average ratings and win-rates for the chosen jokes, and the latter showing pairwise correlations between joke ratings. We then select 20 of the remaining 95 jokes to serve as covariates. We also detail the exact selection procedure and chosen jokes for covariates in Appendix~\ref{app:exp:semi-synth}.
We generate observations as follows. First, we randomly sample an individual from the 14,116 users retained, and take $X$ to be their ratings of the jokes selected as covariates. We then define their potential outcome associated with treatment $a \in \mathcal{A}$ to be
\[
Y(a) := \text{``User's raw rating for joke $a$''} + \xi_a, \;\; \text{where } \xi_a \sim \mathcal{N}(0, 4.0).
\]
We set $Y \equiv Y(A)$, where $A$ is generated from the same logging policy as in the synthetic experiment above, adjusted for the number of interventions. We note that, in the above formulation, although jokes $50$ and $50'$ share the same raw ratings, the added noise is independent.
Again, the policy class considered is all depth 2 policy trees, this time with a minimum of 15\% of the samples landing in any leaf.\footnote{That is, every leaf $L$ has $\mathbb{P}(X \in L) \geq 0.15$.}
\paragraph{Evaluation.}
Because of the larger number of covariates and treatments (20 and 6, respectively) we approximately solve the empirical welfare maximization problem via greedy splitting. In particular, we leverage the \texttt{PolicyTree} class from the \texttt{EconML} package~\citep{oprescu2019econml}. Our choice to adopt greedy approximations in this section is intentional --- many practitioners will likely use greedy or ML proxies for policy learning in practice. To approximate the optimal value $V^\ast$, we fit the \texttt{PolicyTree} class on the full $14{,}116$-user population without adding any noise.
Thus, although coverage in the semi-synthetic case will not be guaranteed by our theory, the results below suggest that greedy approximations for policy learning can work well in practice.
We consider
$\alpha \in \{0, 0.1, 0.25\}$ and $n \in \{2000, 5000, 8000, 10000, 15000, 20000\}$ with burn-in
periods $b_n$ of $500, 2000, 2500, 3000, 4000$, and $5000$, respectively. Again, we conduct our measurements over $250$
independent runs.
\paragraph{Findings.}
Figures~\ref{fig:nu-cov-semisynth} and \ref{fig:nu-pareto-semisynth} present analogues of the coverage and Pareto plots shown in the previous subsection. From both plots, we see that \texttt{AW}{} generally provides the best balance between coverage and confidence interval width. In particular, from these figures, we see that of all estimators that obtain nominal coverage at $n=20,000$ samples (after accounting for Wilson CIs), our estimator obtains the narrowest confidence intervals. The exact coverage of our estimator relative to the 50/50 split estimators based on \texttt{StabVar}{} and \texttt{CADR}{} can be found in Table~\ref{tab:nu-cov-semisynth} in Appendix~\ref{app:exp:semi-synth}. We note that double-dipping (\texttt{DD}) fails
catastrophically in the present setting: its coverage sits between roughly $0.02$ and $0.10$, with
average estimates of $2.46$--$3.73$ against the truth of $2.197$. Further, this approach shows no sign of
recovering as $n$ grows out to $20{,}000$. We hypothesize that this is likely because cloning the marginally best treatment results in a large space of equally promising policies, so double-dipping is actually capable of overfitting in this setting. Unlike the synthetic study, we do not report $\alpha = 0.5$ regime here.
\begin{figure}[htbp]
\centering
\includegraphics[width=0.8\linewidth]{figures/semi-cov-grid_greedy.pdf}
\caption{Empirical coverage versus sample size in the semi-synthetic DGP for all six
estimators at logging exponents $\alpha \in \{0, 0.1, 0.25\}$. Error bars are Wilson $95\%$
intervals and the dashed line is the nominal $0.95$ coverage target.}
\label{fig:nu-cov-semisynth}
\end{figure}
\begin{figure}[htbp]
\centering
\begin{subfigure}[t]{0.32\textwidth}
\includegraphics[width=\linewidth]{figures/semisynth_pareto_a0.png}
\caption{$\alpha = 0$.}
\end{subfigure}\hfill
\begin{subfigure}[t]{0.32\textwidth}
\includegraphics[width=\linewidth]{figures/semisynth_pareto_a1.png}
\caption{$\alpha = 0.1$.}
\end{subfigure}\hfill
\begin{subfigure}[t]{0.32\textwidth}
\includegraphics[width=\linewidth]{figures/semisynth_pareto_a25.png}
\caption{$\alpha = 0.25$.}
\end{subfigure}
\caption{The Pareto frontier of empirical coverage (x-axis) and confidence interval width (y-axis) in the semi-synthetic DGP. Here, we consider $n = 20{,}000$ samples and logging exponents
$\alpha \in \{0, 0.1, 0.25\}$.}
\label{fig:nu-pareto-semisynth}
\end{figure}
\newpage
\subsection{Regret Scaling}
\label{sec:exp:regret}
In Section~\ref{sec:regret}, we proved that the expected regret satisfies $\mathbb{E}[\mathrm{Reg}(\widehat{\pi})] = o(n^{(\alpha - 1)/2})$. This was sufficient to argue that the bias incurred via repeated policy fits was negligible, but did not tell us \textit{how much faster} regret decays than the width of the confidence intervals.
Here, we empirically show that the scaled regret $\frac{\mathrm{Reg}(\wh\pi)}{n^{(\alpha-1)/2}}$ tends to zero as $n$ grows large. We will see, however, that the scaled regret decays more slowly for large logging exponents $\alpha$, partially explaining why seemingly all estimators undercover when $\alpha = 0.5$ in the synthetic DGP.
\paragraph{Evaluation.} We consider both DGPs in this section. For $n \in \{2000, 5000,
10000, 15000, 25000\}$ and $\alpha \in \{0.0, 0.1, 0.25, 0.5\}$, we generate $n$ samples from each DGP using the above logging policies. We then solve (either exactly in the synthetic case or approximately in the semi-synthetic case) the weighted empirical welfare maximization on all $n$ samples, per Equation~\eqref{eq:ewm}. For the synthetic DGP, we estimate the true optimal policy value by sampling $300,000$ \textit{fully-observed} samples, computing the estimate \textit{without} inverse propensity weighting. For the semi-synthetic DGP, we just average over the 14,116 samples in the Jester dataset, which are treated as ground truth. We repeat our measurements over $M = 100$ runs for each $(n, \alpha, \texttt{DGP})$ triple.
\paragraph{Findings.} We report our findings in Figure~\ref{fig:scaled_regret}, which displays the decay of scaled regret for both the synthetic and semi-synthetic DGPs.
Under both DGPs, the scaled regret seemingly tends towards zero as the sample size grows. For larger logging exponents (e.g., $\alpha = 0.5$), the rate of convergence seems to be significantly slower. We note that regret even seems to vanish as a function of the sample size in the semi-synthetic DGP, which is interesting as we are not solving the empirical welfare maximization problem exactly.
Note that the convergence of the scaled regret in turn implies that the raw regret itself vanishes, showing that multiplicity of optimal policies does not impact the possibility of policy learning.
\begin{figure}[htbp]
\centering
\begin{subfigure}[t]{0.48\textwidth}
\includegraphics[width=\linewidth]{figures/regnf-scaled.png}
\caption{Synthetic DGP.}
\end{subfigure}\hfill
\begin{subfigure}[t]{0.48\textwidth}
\includegraphics[width=\linewidth]{figures/semisynth_scaled_regret.png}
\caption{Semi-Synthetic DGP.}
\end{subfigure}
\caption{A visualization of scaled regret against $n$ under various logging exponents $\alpha$. The shaded region gives a $95\%$ pointwise confidence interval over $M = 100$ independent runs. The synthetic panel leverages an exact solver, whereas the semi-synthetic one uses an approximate solution.}
\label{fig:scaled_regret}
\end{figure}
\section{Application: Revisiting Job Search Assistance for Refugees in Jordan}
\label{sec:case_study}
We now apply our estimator in estimating the value of policy improvement in an adaptive field experiment conducted by \citet{caria2024adaptive}. In this experiment, a mix of Syrian refugees (1,663 units) and low-skilled Jordanian citizens (2,107 units) aged 18--45 were chosen to participate in a job search assistance program. These units were \textit{adaptively} assigned to one of four treatments on a rolling basis between February 10th and November 30th of 2019 using a \textit{tempered} Thompson sampling algorithm, formally described below. The four treatments are referred to as \textit{control}, \textit{labeled cash transfer} (or \textit{cash} for short), \textit{information}, and \textit{nudge}, and are described in Table~\ref{tab:jordan_treatments}. As before, we let $\mathcal{A}$ denote the set of treatments throughout. The outcome of interest in the experiment is a binary indicator of employment status, which was measured at roughly six weeks, two months, and four months following treatment assignment.\footnote{As noted by the authors, overall attrition levels in the experiment were low, being 1.2\% at six weeks, 1.6\% at two months, and 4.2\% at four months.}
\begin{table}[htbp]
\centering
\caption{Interventions considered in the job assistance program.}
\label{tab:jordan_treatments}
\begin{tabular}{p{0.19\textwidth} p{0.72\textwidth}}
\toprule
\textbf{Treatment arm} & \textbf{Description} \\
\midrule
Control
&
Participants received a small cash infusion of 4 Jordanian dinars (approximately US \$5.60) and a basic informational pamphlet.
\\
\midrule
Cash
&
Participants received a larger cash transfer of 65 Jordanian dinars (approximately US \$92).
\\
\midrule
Information
&
Participants received more extensive information about preparing for job interviews, including in-person instruction.
\\
\midrule
Nudge
&
Participants received a behavioral job-search intervention consisting of a four-week planning calendar, an instructional video, face-to-face guidance, and optional SMS reminders.
\\
\bottomrule
\end{tabular}
\end{table}
One of the quantities estimated in the authors' work is a Bayesian equivalent of the VPI, which measures the gap between the value of the optimal covariate-dependent treatment policy and the policy that assigns all units to control. In more detail, the authors posit a hierarchical Bayesian model for potential outcomes and define a natural analogue of the VPI in terms of this model (we define both in the sequel).
They find that the Bayesian VPI is 1.7 pp (percentage points) at the six week point, with a 95\% credible set excluding zero. Further, using their Bayesian method, we compute even higher effects at two months (4.4 pp) and four months (2.7 pp) following treatment, also with credible intervals excluding zero.
Our application of their methods points to a high VPI amongst Syrian refugees at the two month mark, with a point estimate of 8.3 pp, indicating reasonable effectiveness of the job search program.
However, implicit in their model (and explicit in their paper) is a strong assumption: the optimal treatment is \textit{almost surely unique} for each covariate stratum. While the authors note in their supplement that such a Bayesian model does not suffer from a winner's curse, this is only true if the assumed model is correct. Under the assumed hierarchical Bayesian model, one can compute credible sets for the effect of each treatment relative to control. The authors do this at the six week mark in Figure A.8 of their supplement, finding that all credible sets contain zero. The same figure shows this holds when conditioning on whether the participant was Jordanian or Syrian as well. Further, Figure A.9 of their supplement shows that credible sets for all expected potential outcomes at the same horizon overlap. Therefore, in this dataset there is not yet evidence that the optimal policy is unique.
Given this, we seek to evaluate if similar benefits for intervening are estimated when
using an approach that is robust to non-unique optima.
\paragraph{Assumed Bayesian Model and Estimand.}
We now briefly recount the assumed Bayesian hierarchical prior and targeting effect estimand from \citet{caria2024adaptive}. First, we introduce notation. We again denote the set of treatments as $\mathcal{A}$, using the notation $0$ for the control treatment. The considered covariate strata are given by the following Cartesian product:
\[
\mathcal{X} := \texttt{\{Syrian, Jordanian\}}\times\texttt{\{F, M\}}\times\texttt{\{HS, No HS\}}\times\texttt{\{Never employed, Ever employed\}},
\]
where \texttt{M} and \texttt{F} denote \textit{male} and \textit{female}, respectively, and \texttt{HS} denotes high school education.
Days are indexed by $t \in \mathcal{T}$, $n_t$ denotes the number of units treated on day $t$, and $i \in [n_t]$ indexes units within a day. Each unit is associated with covariates $X_{i, t}$ and potential employment outcomes $Y_{i, t}(a) \in \{0, 1\}$, which are assumed to be generated by the following hierarchical prior:
\begin{gather*}
(\eta_a, \beta_a) \sim \nu, \;\;\forall a \in \mathcal{A} \quad \text{where } \nu(\eta, \beta) \propto (\eta + \beta)^{-2.5}\\
\mu_{a, x} \mid (\eta_a, \beta_a) \sim \mathrm{Beta}(\eta_a, \beta_a), \;\; \forall (a, x) \in \mathcal{A} \times \mathcal{X} \\
Y_{i, t}(a) \mid \big(X_{i, t} = x, \mu_{a, x}, \eta_a, \beta_a\big) \sim \mathrm{Bern}(\mu_{a, x}) \;\; \forall i \in [n_t], t \in \mathcal{T}, x \in \mathcal{X}, a \in \mathcal{A}.
\end{gather*}
We let $A_{i, t} \in \mathcal{A}$ denote the realized treatment for said unit, and $Y_{i, t} = Y_{i, t}(A_{i, t})$ denote the realized employment status at the desired followup horizon. We fully describe the tempered Thompson sampling algorithm, which ensures each treatment has at least a 5\% chance of being assigned in each round, in Appendix~\ref{app:exp:case_study}.
Let $\mathcal{D} := \left\{(X_{i, t}, A_{i, t}, Y_{i, t}) : i \in [n_t], t \in \mathcal{T}\right\}$ denote the entire dataset of observations. The authors choose their estimand to be the gap between the value of the policy that maximizes per-stratum expected posterior outcomes and the value of the all control policy. Letting $p_x$ denote the fraction of the sample with $X_{i, t} = x$, this estimand is given by
\[
\theta_{0, B} := \sum_{x \in \mathcal{X}}p_x\left[\max_{a \in \mathcal{A}}\mathbb{E}\left(\mu_{a, x} \mid \mathcal{D}\right) - \mathbb{E}\left(\mu_{0, x} \mid \mathcal{D}\right)\right].
\]
This estimand is different than the frequentist VPI outlined in Equation~\eqref{eq:vpi}. In particular, the frequentist quantity averages over the distribution of covariates and views the per-stratum expected outcomes as \textit{fixed}, not random. The Bayesian analogue instead uses empirical stratum weights and averages expected potential outcomes over the posterior distribution. In our analyses, we will compare our estimates of the \textit{frequentist} VPI to this Bayesian analogue.
\paragraph{Our Measurement Approach.}
We briefly describe our measurement approach. We run our analysis on the released set of 3,709 participants.\footnote{We note the entire experiment had 3,770 participants.} We detail the exact data sources used in Appendix~\ref{app:exp:case_study}. Our analyses at two and four months also drop units with missing outcomes. We apply our estimator with batched refitting as in Algorithm~\ref{alg:online-epoch}. Instead of taking geometric epochs as in our previous experiments, we opt to refit policies at the start of each day. This is particularly natural in the setting of this dataset as on any day multiple units receive treatment. We use a burn-in period that ensures at least 20\% of the data is used for fitting the first policy. Table~\ref{tab:burn20-cutoffs} in Appendix~\ref{app:exp:case_study} displays precisely how many samples were used in constructing the initial policy, the corresponding percentage of overall data used, and the first date of policy evaluation.
We take the policy class $\Pi$ to be the set of all deterministic policies excluding the all control policy, which has finite cardinality due to $\mathcal{X}$ being finite. The baseline policy $q(a \mid x)$ is taken to be the all control policy, as is done in \citet{caria2024adaptive}. We note that this setting is permissible by Lemma~\ref{lem:suff_conditions}, as $\gamma = 0.2$ ensures that each intervention has probability at least $0.05$ of being assigned in any round, and hence we have $\alpha = 0$.
We measure the overall value of policy improvement at the end of the experiment using the realized outcomes at the six week, two month, and four month marks. We compare our estimates with the Bayesian ones from \citet{caria2024adaptive}, which we compute using the publicly available data and Markov Chain Monte Carlo algorithm (written in pseudo-code in Algorithm~\ref{alg:caria-targeting-short} in Appendix~\ref{app:exp:case_study}). We compare these values in Table~\ref{tab:main-burn20}, and further present estimates broken down by nationality in Table~\ref{tab:subgroup-burn20}.
\paragraph{Our Findings.}
While the Bayesian method leveraged by~\citet{caria2024adaptive} yields a positive VPI at six weeks, two months, and four months following treatment assignment, our full-population confidence intervals for the VPI contain zero at all time horizons.\footnote{We again note that the two and four month estimates are not present in the original paper. We compute them using the authors' methods.} We note that our point estimates, which are detailed in Table~\ref{tab:main-burn20}, are all around 1.0--3.0 pp lower than their Bayesian counterparts. While our approaches are not directly comparable, we believe there are two competing forces at play. First, as noted above, the Bayesian approach assumes unique optimal treatments per stratum, and so would suffer from a winner's curse were said uniqueness to be violated. Further, due to the fact our approach leverages a policy learning subroutine, it generally yields conservative estimates in finite samples.
We emphasize that our findings \textit{do not preclude} the possibility of a positive VPI.
One interesting finding that our estimates do corroborate is that, at the two month mark, there \textit{is a significant benefit} for targeting amongst Syrians. We estimate that the value of policy improvement is around 7.12 pp, with a lower confidence bound of 1.25 pp. This is only mildly lower than the 8.30 pp estimate from the Bayesian procedure.
Lastly, we note that although the two estimators construct treatment policies in very different ways, the decisions made by the policies are broadly in alignment. We compare the \textit{final} learned policies from our adaptive estimator to the policy that assigns the treatment maximizing posterior expected outcomes in each stratum in Appendix~\ref{app:exp:case_study}, finding that at the two month mark (i.e., when the VPI/effect of targeting was highest), the cash treatment was more often than not the most effective option across many strata.
\begin{table}[ht]
\centering
\caption{Our frequentist \texttt{AW}{} VPI estimate, and the Bayesian estimates (which have formal properties under the assumption of a unique optimal policy~\citep{caria2024adaptive}) alongside 95\% credible/confidence intervals. Here, the baseline is the ``all control'' policy. Estimates of \texttt{AW}{} are produced using roughly 20\% of the sample for burn-in.}
\label{tab:main-burn20}
\begin{tabular}{lccc}
\toprule
Estimator & 6 weeks & 2 months & 4 months \\
\midrule
AW & 0.26 [-1.98, 2.51] & 2.09 [-1.53, 5.71] & -0.07 [-2.65, 2.50] \\
Bayes & 1.70 [0.07, 3.33] & 4.42 [1.97, 6.91] & 2.73 [0.59, 4.93] \\
\bottomrule
\end{tabular}
\end{table}
\begin{table}[ht]
\centering
\caption{VPI estimates restricted to the Jordanian and Syrian subpopulations alongside 95\% credible/confidence intervals.}
\label{tab:subgroup-burn20}
\begin{tabular}{llccc}
\toprule
Group & Estimator & 6 weeks & 2 months & 4 months \\
\midrule
Jordanian & AW & -0.05 [-2.99, 2.90] & -1.76 [-6.14, 2.62] & -2.46 [-5.51, 0.60] \\
Jordanian & Bayes & 1.94 [-0.39, 4.27] & 1.83 [-0.92, 4.72] & 1.01 [-2.06, 4.21] \\
Syrian & AW & 0.33 [-2.69, 3.34] & 7.12 [1.25, 12.99] & 3.36 [-0.74, 7.46] \\
Syrian & Bayes & 1.49 [-0.73, 3.87] & 8.30 [4.08, 12.61] & 4.97 [1.46, 8.74] \\
\bottomrule
\end{tabular}
\end{table}
\section{Conclusion}
\label{sec:conclusion}
In this paper, we developed a simple, sequential estimator for the value of policy improvement under adaptive experimentation. Our estimator, which was based on an estimator due to \citet{luedtke2016statistical}, works by repeatedly using prefixes of historical data to train a policy using a weighted empirical welfare maximization objective, then evaluating the learned policy on subsequent samples. We showed it could operate under either continual refitting or batched fitting, in which the EWM policy was only retrained after a geometrically growing number of steps. We proved that one can construct asymptotically valid confidence intervals for the VPI, and as part of this, showed that one can obtain marginally faster pointwise expected-regret rates for weighted empirical welfare maximization. In addition,
we evaluated the coverage of our estimator and corresponding confidence interval width across both synthetic and semi-synthetic data generating processes. We found that, when compared to natural sample-splitting and double-dipping baselines, our estimator generally offered the best tradeoff between coverage and confidence interval width. We also note that the convergence of the sample-splitting estimators requires our faster regret rates, and thus their validity can be viewed as an additional contribution of this work.
Finally, we applied our estimator to an adaptive experiment evaluating job-assistance programs in Jordan, obtaining generally more conservative estimates than the existing Bayesian analysis whose formal properties rely on the existence of a unique optimal policy (for which there is little evidence) while corroborating the benefits of personalization among Syrian refugees at the two-month horizon.
There are many natural open directions one could pursue related to the work in this paper.
One interesting direction would be to study the validity of \textit{smoothing-based} estimators for the value of policy improvement.
Smoothing-based estimators, such as those considered in \citet{whitehouse2025inference} and \citet{chen2023inference}, have recently emerged as compelling alternatives to the online estimator of \citet{luedtke2016statistical}, as they are not only more intuitive (replacing a non-smooth objective by a differentiable alternative) and provide canonical tie-breaking rules, but also require only a constant number of policy fits.
However, existing work on these estimators considers the setting of \textit{unrestricted policy classes}, wherein any measurable map of a unit's covariates is permitted as a treatment policy. Extending these estimators to a setting of restricted policy classes is non-trivial, and thus would require significant theoretical development. Further, it is unclear how to leverage such estimators alongside contextual bandit data.
Another natural route would be to develop estimators and confidence intervals directly for the \textit{value of an optimal treatment policy} within a class. Our focus on the value of policy improvement was deliberate: not only did we find the estimand to be more naturally motivated, but the contrast with a randomized baseline also served the technical purpose of stabilizing the variance of each step of IPW off-policy evaluation. Without this added stability, one could still show that our confidence interval covers a \textit{weighted average of the values of learned policies}, but arguing that the bias from policy learning (i.e., accumulated regret) vanishes sufficiently quickly is non-obvious. Likely, the underlying estimator would not need to change, but one would need to develop more refined, self-normalized regret bounds that naturally reflect the accumulated variance of off-policy evaluation rather than just the overall number of samples. It is unclear if such improved rates are possible when there are multiple optimal treatment policies within a class, and we thus leave this for future work. We again emphasize that this added stability from the contrast is not needed in the setting $\alpha = 0$, and thus our analysis also yields confidence intervals for the value of the optimal treatment policy in a class in this setting.
\paragraph{AI Usage Statement}
The authors used generative AI tools to check the correctness of theorem statements, identify and fix errors in proofs, write code for experimentation, produce initial figures and tables, and copyedit. The authors verified all AI-assisted output and remain responsible for the content of this manuscript.
\bibliography{bib}
\bibliographystyle{plainnat}