Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
89,721 characters · 29 sections · 66 citation commands
How to sample and when to stop sampling: The generalized Wald problem and minimax policies
Acquiring information is expensive. Experimenters need to carefully choose how many units of each treatment to sample and when to stop sampling. This paper seeks to develop techniques for incorporating the cost of information into experimental design. Specifically, we focus our analysis of costly experimentation within the context of comparative trials where the aim is to determine the best of two treatments.
In the computer science literature, such experiments are referred to as A/B tests. Technology companies like Amazon, Google and Microsoft routinely run hundreds of A/B tests a week to evaluate product changes, such as a tweak to a website layout or an update to a search algorithm. However, experimentation is expensive, especially if the changes being tested are very small and require evaluation on large amounts of data; e.g., deng2013improving state that even hundreds of millions of users were considered insufficient at Google to detect the treatment effects they were interested in. Clinical or randomized trials are another example of A/B tests. Even here, reducing experimentation costs is a key goal. In fact, this has been a major objective for the FDA since 2004 when it introduced the `Critical Path Initiative' for streamlining drug development; this in turn led the FDA to promote sequential designs in clinical trials (see, e.g., FDApolicybrief, for the current guidance, which was influenced by the need to reduce experimentation costs). For this reason, many recent clinical trials, such as the ones used to test the effectiveness of Covid vaccines (e.g., baden2021efficacy), now use multi-stage designs where the experiment can be terminated early if a particularly positive or negative effect is seen in early stages.
In practice, the cost of experimentation directly or indirectly enters the researchers' experimental design when they choose an implicit or explicit stopping time (note that we use stopping time interchangeably with the number of observations in the experiment). For instance, in testing the efficacy of vaccines, experimenters stop after a pre-determined number of infections. In other cases, a power analysis may be used to determine sample size before the start of the experiment. But if the aim is to maximize social welfare (or profits), neither of these procedures is optimal.\footnote{See, e.g., manski2016sufficient for a critique on the common use of power analysis for determining the sample size in randomized control trials. }
In this paper, we develop optimal experimentation designs that maximize welfare while also taking into account the cost of information. In particular, we study optimal sampling and stopping rules in sequential experiments where sampling is costly and the decision maker (DM) aims to determine the best of two treatments by: (1) adaptively allocating units to one of these treatments, and (2) stopping the experiment when the expected welfare, inclusive of sampling costs, is maximized. We term this the generalized Wald problem, and use minimax regret (manski2021econometrics), a natural choice criterion under ambiguity aversion, to determine the optimal decision rule.\footnote{We do not consider the minimax risk criterion as it leads to a trivial decision: the DM should never experiment and always apply the status quo treatment. }
We first derive the optimal decision rule in continuous time, under the so-called diffusion regime fan2021diffusion,wager2021diffusion where information arrives gradually in the form of (continuous) Gaussian increments. Then, we show that analogues of this decision rule are also asymptotically optimal under parametric and non-parametric distributions of outcomes. The asymptotics, which appear to be novel, involve taking the marginal cost of experimentation to $0$ at a specific rate. Section (ref) delves into the rationale behind these `small cost asymptotics', and argues that they are practically quite relevant. It is important to clarify here that `small costs' need not literally imply the monetary costs of experimentation are close to $0$. Rather, it denotes that these costs are small compared to the benefit of choosing the best treatment for full-scale implementation.
The optimal decision rule has a number of interesting, and perhaps, surprising properties. First, the optimal sampling rule is history independent and also independent of sampling costs. In fact, it is just the Neyman allocation, which is well known in the Randomized Control Trial (RCT) literature as the (fixed) sampling strategy that minimizes estimation variance; our results state that one cannot do better than this even when allowing for adaptive strategies. Second, it is optimal to stop when the difference in average outcomes between the treatments, multiplied by the number of observations collected up to that point, exceeds a specific threshold. The threshold depends on sampling costs and the standard deviation of the treatment outcomes. Finally, at the conclusion of the experiment, the DM chooses the treatment with the highest average outcomes. The decision rule therefore has a simple form that makes it attractive for applications.
Our results also apply to the best arm identification problem with two arms.\footnote{The results for best arm identification were previously circulated in an unpublished note by the author, accessible from ArXiV at \href{https://arxiv.org/abs/2204.05527}{https://arxiv.org/abs/2204.05527}. The current paper subsumes these results.} Best arm identification shares the same aim of determining the best treatment but the number of observations is now exogenously specified, even as the sampling strategy is allowed to be adaptive. Despite this difference, we find Neyman allocation to be the minimax-regret optimal sampling rule in this context as well. However, by not stopping adaptively, we lose on experimentation costs. Compared to best arm identification, we show that the use of an optimal stopping time allows us to attain the same regret, exclusive of sampling costs, with $40\%$ fewer observations on average (under the least-favorable prior); this is independent of model parameters such as sampling costs and outcome variances.
For the most part, this paper focuses on constant sampling costs (i.e., constant per observation). This has been a standard assumption since the classic work of wald1947sequential, see also arrow1949bayes and fudenberg2018speed, among others. In fact, many online marketplaces for running experiments, e.g., Amazon Mechanical Turk, charge a fixed cost per query/observation. Note also that the costs may be indirect: for online platforms like Google or Microsoft that routinely run thousands of A/B tests, these could correspond to how much experimentation hurts user experience. Still, one may wonder whether and how our results change under other cost functions and modeling choices, e.g., when data is collected in batches, or, when we measure regret in terms of nonlinear or quantile welfare. We asses this in Section (ref). Almost all our results still go through under these variations. We also identify a broader class of cost functions, nesting the constant case, in which the form of the optimal decision stays the same.
The question of when to stop sampling has a rich history in economics and statistics. It was first studied by wald1947sequential and arrow1949bayes with the goal being hypothesis testing, specifically, optimizing the trade-off between type I and type II errors, instead of welfare maximization. Still, one can place these results into the present framework by imagining that the distributions of outcomes under both treatments are known, but it is unknown which distribution corresponds to which treatment. This paper generalizes these results by allowing the distributions to be unknown. For this reason, we term the question studied here the generalized Wald problem.
chernoff1959sequential studied the sequential hypothesis testing problem under multiple hypotheses, using large deviation methods. The asymptotics there involve taking the sampling costs to 0, even as there is a fixed reward gap between the treatments. More recently, the stopping rules of chernoff1959sequential were incorporated into the $\delta$-PAC (Probably Approximately Correct) algorithms devised by garivier2016optimal and qin2017improving for best arm identification with a fixed confidence. The aim in these studies is to minimize the amount of time needed to attain a pre-specified probability, $1-\delta$, of selecting the optimal arm. However, these algorithms do not directly minimize a welfare criterion, and the constraint of pre-specifying a $\delta$ could be misplaced, if, e.g., there is very little difference between the first and second best treatments. In fact, under the least-favorable prior, our minimax decision rule mis-identifies the best treatment about 23% of the time. qin2022adaptivity study the costly sampling problem under fixed reward gap asymptotics using large deviation methods. The present paper differs in using local asymptotics and in appealing to a minimax regret criterion. However, unlike the papers cited above, we only study binary treatments.
A number of papers (colton1963model,lai1980sequential,chernoff1981sequential) have studied sequential trials in which there is a population of $N$ units, and at each period, the DM randomly selects two individuals from this population, and assigns them to the two treatments. The DM is allowed to stop experimenting at any point and apply a single treatment on the remainder of the population. The setup in these papers is intermediate between our own and two-armed bandits: while the aim, as in here, is to minimize regret, acquiring samples is not by itself expensive and the outcomes in the experimentation phase matter for welfare. This literature also does not consider optimal sampling rules.
The paper is also closely related to the growing literature on information acquisition and design, see, hebert2017rational,fudenberg2018speed,morris2019wald,liang2022dynamically, among others. fudenberg2018speed study the question of optimal stopping when there are two treatments and the goal is to maximize Bayes welfare (which is equivalent to minimizing Bayes regret) under normal priors and costly sampling. While their approach relies on an exogenously specified sampling rule, liang2022dynamically extend this line of inquiry by allowing for endogenous selection of the sampling rule. In fact, for constant sampling costs, the setup in liang2022dynamically is similar to ours but the welfare criterion is different: their framework adopts a Bayesian perspective with normal priors. Although the Neyman allocation plays a key role in the optimal sampling rules under both frameworks, the optimal stopping times have very different qualitative and quantitative properties. A detailed comparison is provided in Section (ref). These differences in stopping times arise because the minimax regret criterion corresponds to a least-favorable prior with a specific two-point support. Thus, our results highlight the important role played by the prior in determining even the qualitative properties of optimal decisions. This motivates the need for robust decision rules, and the minimax regret criterion is one way to obtain them.
Our results also speak to the literature on drift-diffusion models (DDMs), which are widely used in neuroscience and psychology to study choice processes luce1986response,ratcliff2008diffusion,fehr2011neuroeconomic. DDMs are based on the classic binary state hypothesis testing problem of wald1947sequential. fudenberg2018speed extend this model to allow for continuous states, using Gaussian priors, and show that the resulting optimal decision rules are very different, even qualitatively, from the predictions of DDM. In this paper, we show that if the DM is ambiguity averse and uses the minimax regret criterion, then the predictions of the DDM model are recovered even under continuous states. In other words, decision making under ignorance can bring us back to DDM.
Finally, the results in this paper are unique in regards to all the above strands of literature in showing that any discrete time parametric and non-parametric version of the problem can be reduced to the diffusion limit under small cost asymptotics. Diffusion asymptotics were introduced by fan2021diffusion and wager2021diffusion to study the properties of Thompson sampling in bandit experiments. The techniques for showing asymptotic equivalence to the limit experiment build on, and extend, previous work on sequential experiments by adusumilli2021risk. Relative to that paper, the novelty here is two-fold: first, we derive a sharp characterization of the minimax optimal decision rule for the Wald problem. Second, we introduce `small cost asymptotics' that may be of independent interest in other, related problems where there is a `local-to-zero' cost of continuing an experiment.
Following fudenberg2018speed and liang2022dynamically, we start by describing the problem under a stylized setting where time is continuous and information arrives gradually in the form of Gaussian increments. In statistics and econometrics, this framework is also known as diffusion asymptotics adusumilli2021risk,fan2021diffusion,wager2021diffusion. The benefit of the continuous time analysis is that it enables us to provide a sharp characterization of the minimax optimal decision rule; this is otherwise obscured by the discrete nature of the observations in a standard analysis. Section (ref) describes how these asymptotics naturally arise under a limit of experiments perspective when we employ small-cost asymptotics and a local-to-zero scaling for the treatment effect.
The setup is as follows. There are two treatments $0,1$ corresponding to unknown mean rewards $\bm{\mu}:=(\mu_{1},\mu_{0})$ and known variances $\sigma_{1}^{2},\sigma_{0}^{2}$. It is without loss of generality to take $\sigma_{1}^{2},\sigma_{0}^{2}$ to be known in the current setting, as they could otherwise be completely determined in an instant from the quadratic variations of the signal processes $x_{1}(\cdot)$ and $x_{0}(\cdot)$, defined below in ((ref)). The aim of the decision maker (DM) is to determine which treatment to implement on the population. To guide her choice, the DM conducts a sequential experiment, while paying a flow cost $c$ as long as the experiment is in progress. At each time-point $t$, the DM samples a treatment according to the sampling rule $\pi_{a}(t)\equiv\pi(A=a\vert\mathcal{F}_{t}),a\in\{0,1\}$, which specifies the probability of selecting treatment $a$ given some filtration $\mathcal{F}_{t}$. The DM then keeps track of the signals, $x_{1}(t),x_{0}(t)$ from the two treatments, as well as the fraction of times, $q_{1}(t),q_{0}(t)$ each treatment was sampled so far:
Here, $W_{1}(t),W_{0}(t)$ are independent one-dimensional Wiener processes. The experiment ends in accordance with an $\mathcal{F}_{t}$-adapted stopping time, $\tau$. At the conclusion of the experiment, the DM chooses an $\mathcal{F}_{\tau}$ measurable implementation rule, $\delta\in\{0,1\}$, specifying which treatment to implement on the population. The DM's decision thus consists of the triple $\bm{d}:=(\pi,\tau,\delta)$.
Denote $s(t)=(x_{1}(t),x_{0}(t),q_{1}(t),q_{0}(t))$ and take $\mathcal{F}_{t}\equiv\sigma\{s(u);u\le t\}$ to be the filtration generated by the state variables $s(\cdot)$ until time $t$.\footnote{As in liang2022dynamically, we restrict attention to sampling rules $\pi_{a}$ for which a weak solution to the functional SDEs ((ref)), ((ref)) exists. This is true if either $\pi_{a}:\left\{ s(z):z\le t\right\} \to[0,1]$ is continuous, see karatzas2012brownian, or, if it is any deterministic function of $t$.} Let $\mathbb{E}_{\bm{d}\vert\bm{\mu}}[\cdot]$ denote the expectation under a decision rule $\bm{d}$, given some value of $\bm{\mu}$. We evaluate various decision rules by the maximum regret criterion, defined as
To understand this expression, consider an oracle decision rule $\{\tau=0,\delta=\mathbb{I}\{\mu_{1}>\mu_{0}\}\}$, which has full knowledge of $\bm{\mu}$. The oracle would achieve a realized welfare of $\max\{\mu_{1},\mu_{0}\}$. In contrast, a given decision rule $\bm{d}$ generates a realized welfare of $\mu_{0}+(\mu_{1}-\mu_{0})\delta-c\tau$. The difference between these two welfares, $\max\{\mu_{1}-\mu_{0},0\}-(\mu_{1}-\mu_{0})\delta+c\tau$, is referred to as regret. The quantity $V(\bm{d},\bm{\mu})$ therefore represents the `frequentist regret', i.e., the expected regret of $\bm{d}$ given $\bm{\mu}$. The decision rule, $\bm{d}^{*}$, that minimizes $V_{\max}(\bm{d})$ is known as the minimax-regret optimal decision rule.
Minimax regret is a commonly used decision theoretic criterion when the DM faces ambiguity over the values of $\bm{\mu}$. In contrast, a Bayesian DM would place some prior $p_{0}$ over $\bm{\mu}$ and aim to minimize Bayes regret, defined as
We can relate max-regret to Bayes regret as $V_{\max}(\bm{d})=\sup_{p_{0}\in\mathcal{P}}V(\bm{d},p_{0})$, where $\mathcal{P}$ denotes the set of all possible probability distributions over $\bm{\mu}$. This suggests a multiple prior interpretation for the minimax regret criterion. As we show in Section (ref), minimax regret can be viewed as the value of a zero-sum game played between nature and the DM, where nature chooses the prior $p_{0}$ and the DM chooses the decision rule $\bm{d}$. The minimax-regret optimal rule, $\bm{d}^{*}$, is then Bayes optimal under nature's regret-maximizing choice of the prior, also known as the least-favorable prior.
The decision rules $\bm{d}$ are dynamic since they are history dependent. But as stated, the max-regret criterion $V_{\max}(\bm{d})$ is `static' since it ranks decision rules only at $t=0$; it implicitly assumes the DM can fully commit to the course of action prescribed by $\bm{d}^ {}$. Nonetheless, the criterion admits a dynamically consistent extension, $V_{\max}(\bm{d};t)$, which allows for a consistent conditional ranking of $\bm{d}$ given any history $\mathcal{F}_{t}$. This extension is possible because the space of priors $\mathcal{P}$ is unrestricted and therefore `rectangular' in the sense of epstein2003recursive. As in epstein2003recursive, rectangularity implies existence of a $V_{\max}(\bm{d};t)$ with a recursive structure, such that $V_{\max}(\bm{d};0)=V_{\max}(\bm{d})$,
where $\mathbb{E}_{p_{0}}\left[\left.\cdot\right|\mathcal{F}_{t}\right]$ is the expectation with respect to the posterior of $p_{0}$ given $\mathcal{F}_{t}$. Thus, $\bm{d}^{*}$ is dynamically optimal under $V_{\max}(\bm{d};t)$, the dynamically consistent extension of $V_{\max}(\bm{d})$.
In any event, dynamic consistency is arguably less relevant in the context of the A/B testing examples that are the focus of this paper. In these examples, it is quite reasonable to suppose that the DM is able to commit to the chosen decision rule. For instance, in clinical trials, regulatory agencies explicitly require and enforce adherence to a pre-specified experimental strategy, see, e.g., FDA's guidance for adaptive experiments us2019guidance.
The best arm identification problem is a special case of the generalized Wald problem where the stopping time is fixed beforehand and set to $\tau=1$ without loss of generality. This is equivalent to fixing the number of observations before the start of the experiment; in fact, we show in Section (ref) that a unit time interval corresponds to a pre-specified number of observations, $n$, in a discrete time analysis. Thus, decisions now consist only of $\bm{d}=(\pi,\delta)$, but $\pi$ is still allowed to be adaptive. If we further restrict $\pi$ to be fixed (i.e., non-adaptive), we get back to the typical setting of Randomized Control Trials (RCTs).
Despite these differences, we show in Section (ref) that the minimax-regret optimal sampling and implementation rules are the same in all cases; the optimal sampling rule is the Neyman allocation $\pi_{a}^{*}(t)=\sigma_{a}/(\sigma_{1}+\sigma_{0})$, while the optimal implementation rule is to choose the treatment with the higher average outcomes. Somewhat surprisingly, then, there is no difference in the optimal strategy between best arm identification and standard RCTs (under minimax regret). The presence of $\tau$, however, makes the generalized Wald problem fundamentally different from the other two. We provide a relative comparison of the benefit of optimal stopping in Section (ref).
It is convenient to first describe minimal regret under the Bayesian approach, given a prior $p_{0}$. As noted earlier, we can characterize minimax regret as Bayes regret under a least-favorable prior.
Let $p(\bm{\mu}\vert s)$ denote the posterior density of $\bm{\mu}$ given the current state $s=(x_{1},x_{0},q_{1},q_{0})\in\mathbb{R}^{4}$. By standard results in stochastic filtering, (here, and in what follows, $\propto$ denotes equality up to a normalization constant)
where $\mathcal{N}(\cdot\vert\mu,\sigma^{2})$ is the normal density with mean $\mu$ and variance $\sigma^{2}$, and the second proportionality follows from the fact $W_{1}(\cdot),W_{0}(\cdot)$ are independent Wiener processes.
Define $V^{*}(s;p_{0})$ as the minimal expected Bayes regret given state $s$, i.e., \[ V^{*}(s;p_{0})=\inf_{\bm{d}\in\mathcal{D}}\mathbb{E}_{\bm{\mu}\vert s}\left[V\left(\bm{d},\bm{\mu}\right)\right], \] where $\mathcal{D}$ is the set of all decision rules that satisfy the measurability conditions set out previously. The minimal (ex-ante) Bayes regret, following ((ref)), is then related to $V^{*}(\cdot;p_{0})$ as $\inf_{\bm{d}\in\mathcal{D}}V(\bm{d},p_{0})=V^{*}(s_{0};p_{0})$, where $s_{0}:=(0,0,0,0)$ represents the initial state. In principle, one could characterize $V^{*}(\cdot;p_{0})$ as a Hamilton-Jacobi-Bellman Variational Inequality (HJB-VI; oksendal2003stochastic), compute it numerically and characterize the optimal Bayes decision rules. However, this can be computationally expensive, and moreover, does not provide a closed form characterization of the optimal decisions. Analytical expressions can be obtained under two types of priors:
In this case, the posterior is also Gaussian and its mean and variance can be computed analytically. liang2022dynamically derive the optimal decision rule in this setting. See Section (ref) for a comparison with our proposal. Additional details are provided in Appendix H.
Two point priors are closely related to hypothesis testing and the sequential likelihood ratio procedures of wald1947sequential and arrow1949bayes. More importantly for us, the least-favorable prior for minimax regret, described in the next section, has a two point support.
Suppose the prior over $\bm{\mu}\equiv(\mu_{1},\mu_{0})$ is supported on the two points $(\bar{a},\bar{b}),(\underline{a},\underline{b})$. Let $\lambda=1$ represent the event $\bm{\mu}=(\bar{a},\bar{b})$ and $\lambda=0$ the event $\bm{\mu}=(\underline{a},\underline{b})$. Also, let $(\Omega,\mathcal{F},\mathbb{P}_{\pi})$ denote the relevant probability space given a (possibly) randomized policy $\pi$, where $\mathcal{F}:=\cup_{t=1}^{\infty}\mathcal{F}_{t}\cup\sigma(\lambda)$ is the $\sigma$-field generated by $\lambda$ and the filtration $\{\mathcal{F}_{t}\}_{t}$ defined previously, and $\mathbb{P}_{\pi}$ is the joint probability distribution over $\bm{\mu}$ and the sample paths of $s(t)$ under $\pi$. Set $P_{\pi}^{0},P_{\pi}^{1}$ to be the probability measures $P_{\pi}^{0}(A):=\mathbb{P}_{\pi}(A\vert\lambda=0)$ and $P_{\pi}^{1}(A):=\mathbb{P}_{\pi}(A\vert\lambda=1)$ for any $A\in\mathcal{F}$.
Clearly, the likelihood ratio process $\varphi^{\pi}(t):=\mathbb{E}_{P_{\pi}^{0}}\left[\left.\frac{dP_{\pi}^{1}}{dP_{\pi}^{0}}\right|\mathcal{F}_{t}\right]$ is a sufficient statistic for $\lambda$.\footnote{Note that $\frac{dP_{\pi}^{1}}{dP_{\pi}^{0}}$ is a random variable, being the Radon-Nikodym derivative of $P_{\pi}^{1}$ with respect to $P_{\pi}^{0}$. } An application of the Girsanov theorem, noting that $W_{1}(\cdot),W_{0}(\cdot)$ are independent of each other, gives (see also shiryaev2007optimal)
Let $m_{0}$ denote the prior probability that $\lambda=1$. Additionally, given a sampling rule $\pi$, let $m^{\pi}(t)=\mathbb{P}(\lambda=1\vert\mathcal{F}_{t})$ denote the belief process describing the posterior probability that $\lambda=1$. Following shiryaev2007optimal, $m^{\pi}(t)$ can be related to $\varphi^{\pi}(t)$ as
The Bayes optimal implementation rule at the end of the experiment is
The superscript on $\delta$ highlights that the above implementation rule is conditional on a given choice of $(\pi,\tau)$. Relatedly, the Bayes regret at the implementation phase of the experiment (from employing the optimal implementation rule) is
Hence, for a given sampling rule $\pi$, the Bayes optimal stopping time $\tau^{\pi}$, can be obtained as the solution to the optimal stopping problem
where $\mathcal{T}$ is the set of all $\mathcal{F}_{t}$ measurable stopping times, and $\mathbb{E}_{\pi}[\cdot]$ denotes the expectation under the sampling rule $\pi$.
The minimax regret value can be written as
Following wald1945statistical, we can characterize minimax regret as the value of a zero-sum game played between nature and the DM. Nature's action involves choosing a prior $p_{0}\in\mathcal{P}$ over $\bm{\mu}$, while the DM chooses the decision rule $\bm{d}$. The equilibrium action of nature is termed the least-favorable prior, and that of the DM, the minimax decision rule. Note that nature's action in the game is static, as it only chooses a prior $p_{0}$ at the beginning of the experiment. In contrast, the DM selects a dynamic decision rule $\bm{d}$ that, to be a best response to nature's choice, must be Bayes optimal with respect to that choice of prior. Consequently, the minimax-regret optimal rule $\bm{d}^{*}$ must be consistent with Bayesian updating of the least-favorable prior throughout the experiment.
The following is the main result of this section: Let $\gamma_{0}^{*}\approx0.536357$, $\Delta_{0}^{*}\approx2.19613$ denote universal constants derived from solving a univariate minimax problem ((ref)) described later in this section. Also, define $\eta:=\left(\frac{2c}{\sigma_{1}+\sigma_{0}}\right)^{1/3}$, $\gamma^{*}=\gamma_{0}^{*}/\eta$ and $\Delta^{*}=\eta\Delta_{0}^{*}$.
Theorem (ref) makes no claim as to the uniqueness of the Nash equilibrium.\footnote{In fact, this would depend on the topology defined over $\mathcal{D}$ and $\mathcal{P}$.} Even if multiple equilibria were to exist, however, the value of the game $V^{*}=\inf_{\bm{d}\in\mathcal{D}}\sup_{p_{0}\in\mathcal{P}}V(\bm{d},p_{0})$ would be unique, and $\bm{d}^{*}$ would still be minimax-regret optimal.
The optimal strategies under best arm identification can be derived in the same manner as Theorem (ref), but the proof is simpler as it does not involve a stopping rule. Let $\Phi(\cdot)$ denote the CDF of the standard normal distribution.
The main challenge with analyzing the game ((ref)) is that the action spaces $\mathcal{P},\mathcal{D}$ of both nature and the DM are infinite dimensional. Therefore, to prove Theorem (ref), we first restrict the action spaces of both players and then show that a Nash equilibrium exists within this restricted class.
For nature, we employ the restricted action space, $\mathcal{P}_{\textrm{rest}}:=\{p_{\Delta}:\Delta\in\mathbb{R}^{+}\}$, consisting of all `indifference priors' indexed by $\Delta\in\mathbb{R}$. Specifically, each `indifference prior' $p_{\Delta}$ is a two-point prior supported on $(\sigma_{1}\Delta/2,-\sigma_{0}\Delta/2),(-\sigma_{1}\Delta/2,\sigma_{0}\Delta/2$), with a prior probability of $0.5$ at each support point. As for the DM, we employ the restricted action space \[ \mathcal{D}_{\textrm{rest}}:=\left\{ \tilde{\bm{d}}_{\gamma}=(\pi^{*},\tau_{\gamma},\delta^{\tau_{\gamma}}):\gamma\in\mathbb{R}^{+}\right\} , \] where
We demonstrate that for each $p_{\Delta}\in\mathcal{P}_{\textrm{rest}}$, there exists a unique $\gamma\in\mathbb{R}^{+}$ such that $\tilde{\bm{d}}_{\gamma}$ is an unconstrained best response of the DM to $p_{\Delta}$. In other words, $\tilde{\bm{d}}_{\gamma}$ is a best response within the unrestricted class $\mathcal{D}$, not just within $\mathcal{D}_{\textrm{rest}}$. Similarly, for each $\tilde{\bm{d}}_{\gamma}\in\mathcal{D}_{\textrm{rest}}$, there exists a $\Delta\in\mathbb{R}^{+}$ such that $p_{\Delta}$ is an unconstrained best response of nature to $\tilde{\bm{d}}_{\gamma}$. These results imply that any Nash equilibrium within the restricted action space $\mathcal{P}_{\textrm{rest}}\times\mathcal{D}_{\textrm{rest}}$ would also be a Nash equilibrium within the unrestricted action space $\mathcal{P}\times\mathcal{D}$. We then formally demonstrate the existence of a Nash equilibrium in the restricted setting and characterize the equilibrium set of actions.
We elaborate on these steps below:
The term `indifference priors' indicates that these priors make the DM indifferent between any sampling rule $\pi$. The intuitive explanation is as follows: Let $\lambda=1$ represent the event $\bm{\mu}=(\sigma_{1}\Delta/2,-\sigma_{0}\Delta/2)$ and $\lambda=0$ the event $\bm{\mu}=(-\sigma_{1}\Delta/2,\sigma_{0}\Delta/2)$. These support points are configured in such a way that both treatments provide equal information about $\lambda$, making the choice of treatment irrelevant. To illustrate, assume $\sigma_{1}=\sigma_{0}=1$. If the DM samples arm 1 for a period of time $\delta t$, she would observe the signal process $x_{1}(t)=(2\lambda-1)\frac{\Delta}{2}t+W_{1}(t)$ over that time-period, with a drift of either $\Delta/2$ or $-\Delta/2$ depending on whether $\lambda=1$ or $\lambda=0$. Alternatively, sampling arm 0 yields $x_{0}(t)=-(2\lambda-1)\frac{\Delta}{2}t+W_{0}(t)$, with an exactly opposite drift. Since $W_{1}(\cdot),W_{0}(\cdot)$ are independent Wiener processes, both sampling strategies are equally informative about $\lambda$ in the Blackwell sense.
We now describe the formal argument. For both support points of $p_{\Delta}$, ((ref)) implies
Suppose $\lambda=1$. By ((ref)) and ((ref))
where $\tilde{W}(\cdot)$, defined as $d\tilde{W}(t):=\sqrt{\pi_{1}(t)}dW_{1}(t)-\sqrt{\pi_{0}(t)}dW_{0}(t)$, is a one dimensional Wiener process, being a linear combination of two independent Wiener processes with $\pi_{1}(t)+\pi_{0}(t)=1$. Plugging the above into ((ref)) gives \[ d\ln\varphi^{\pi}(t)=\frac{\Delta^{2}}{2}dt+\Delta d\tilde{W}(t). \] In a similar manner, we can show under $\lambda=0$ that $d\ln\varphi^{\pi}(t)=-\frac{\Delta^{2}}{2}dt+\Delta d\tilde{W}(t).$ Thus, the evolution of the log-likelihood ratio process, $\ln\varphi^{\pi}(t)$, can be decomposed into two parts: a drift term $(2\lambda-1)\frac{\Delta^{2}}{2}dt$ that depends on the state of the world $\lambda\in\{0,1\}$, and noise $\Delta d\tilde{W}(t)$. Different sampling rules, $\pi$, induce the same drift and leave unchanged the distribution of noise, $\tilde{W}(\cdot)$. Therefore, the choice of $\pi$ does not affect the sample-path distribution of $\varphi^{\pi}(\cdot)$, and consequently, has no bearing on the sample-path distribution of the belief process $m^{\pi}(\cdot)$.
Crucially, this invariance to the choice of $\pi$ holds at every time point during the experiment, even as $p_{\Delta}$ is revised through Bayesian updating. The key to this invariance lies in the fact that Bayesian updating does not alter the support points of the prior, and it is solely these support points, together with $\pi$, that govern the evolution of $\varphi^{\pi}(\cdot)$ under Wiener process noise. Now, the precise form of the support points of $p_{\Delta}$ ensures the drift of $\varphi^{\pi}(t)$ is independent of $\pi$. Then, the linearity property of Wiener processes implies that a linear combination of such processes remains a Wiener process, thereby preserving the independence of the noise process from the choice of $\pi$ as well.
As the distributions of $\varphi^{\pi}(\cdot),m^{\pi}(\cdot)$ do not depend on $\pi$, the Bayes optimal stopping time in ((ref)) is also independent of $\pi$ for indifference priors (standard results in optimal stopping, see e.g., oksendal2003stochastic, imply that the optimal stopping time in ((ref)) is a function only of $m^{\pi}(t)$ which is now independent of $\pi$). In fact, it has the same form as the optimal stopping time in the Bayesian hypothesis testing problem of arrow1949bayes, analyzed in continuous time by shiryaev2007optimal and morris2019wald. An adaptation of their results (see, Lemma (ref) in Appendix (ref)) shows that the Bayes optimal stopping time corresponding to $p_{\Delta}$ is
where $\gamma(\Delta)$ is defined in Lemma (ref). By ((ref)) and ((ref)), the corresponding Bayes optimal implementation rule is seen to be $\delta^{\tau_{\gamma(\Delta)}}$, as defined in ((ref)). Hence, the decision rule $\tilde{\bm{d}}_{\gamma(\Delta)}$ is a best response of the DM to nature's choice of $p_{\Delta}$.
Lemma (ref) in Appendix (ref) shows that the frequentist regret $V\left(\tilde{\bm{d}}_{\gamma},\bm{\mu}\right)$, given some $\bm{\mu}=(\mu_{1},\mu_{0})$, depends only on $\vert\mu_{1}-\mu_{0}\vert$. To understand this result, observe that
Clearly, $\tau_{\gamma},\delta^{\tau_{\gamma}}$ depend on the data only through the stochastic process $\sigma_{1}^{-1}x_{1}(\cdot)-\sigma_{0}^{-1}x_{0}(\cdot)$. Under the Neyman allocation, ((ref)) and ((ref)) imply
for any $\bm{\mu}\in\mathbb{R}^{2}$, where $\tilde{W}(\cdot):=\sqrt{\frac{\sigma_{1}}{\sigma_{1}+\sigma_{0}}}W_{1}(\cdot)-\sqrt{\frac{\sigma_{0}}{\sigma_{1}+\sigma_{0}}}W_{0}(\cdot)$ is a standard one-dimensional Wiener process. Consequently, the distributions of $\tau_{\gamma},\delta^{\tau_{\gamma}}$ depend on $\bm{\mu}$ only through $\mu_{1}-\mu_{0}$. This in turn implies, based on ((ref)), that $V\left(\tilde{\bm{d}}_{\gamma},\bm{\mu}\right)$ depends on $\bm{\mu}$ only through $\mu_{1}-\mu_{0}$. This dependence can be further reduced to $\vert\mu_{1}-\mu_{0}\vert$ by symmetry since interchanging the treatment labels $0,1$ would not affect the frequentist regret of $\tilde{\bm{d}}_{\gamma}$.
Since $\bm{\mu}$ affects $V\left(\tilde{\bm{d}}_{\gamma},\bm{\mu}\right)$ only through $\vert\mu_{1}-\mu_{0}\vert$, it is maximized at $\vert\mu_{1}-\mu_{2}\vert=(\sigma_{1}+\sigma_{0})\Delta(\gamma)/2$, where $\Delta(\gamma)$ is some function of $\gamma$. Thus, the best response of nature to $\tilde{\bm{d}}_{\gamma}$ is to pick any prior that is supported on $\left\{ \bm{\mu}:\vert\mu_{1}-\mu_{0}\vert=(\sigma_{1}+\sigma_{0})\Delta(\gamma)/2\right\} $. Therefore, the two-point prior $p_{\Delta(\gamma)}$ is a best response to $\tilde{\bm{d}}_{\gamma}$.
The use of Neyman allocation is essential for the above conclusion. With a different sampling rule, the distributions of $\tau_{\gamma},\delta^{\tau_{\gamma}}$ would depend not only on $\mu_{1}-\mu_{0}$, but also on the individual levels of $\mu_{1},\mu_{0}$. In such cases, nature could drive the max-regret of the corresponding decision rule to $\infty$ through an adversarial choice of $\bm{\mu}$, as we show in Appendix B. This explains why only the Neyman allocation is minimax optimal, even though the DM is indifferent to any sampling rule under $p_{\Delta}$: it is needed to ensure nature's choice of $p_{\Delta}$ is supported as a best response to $\tilde{\bm{d}}_{\gamma}$.
The above observations imply that the overall Nash equilibrium to ((ref)) is the same as the Nash equilibrium in the restricted sub-problem where nature chooses an indifference prior, $p_{\Delta}$, indexed by $\Delta\in\mathbb{R}^{+}$, and the DM chooses a decision rule $\tilde{\bm{d}}_{\gamma}$, indexed by $\gamma\in\mathbb{R}^{+}$. Thus, the action spaces of nature and the DM in this sub-problem are scalar. Lemma (ref) in Appendix (ref) formally demonstrates existence of a Nash equilibrium in the sub-problem using Sion's minimax theorem sion1958general. The equilibrium values of $\Delta,\gamma$ can be computed numerically by writing down the relevant first order conditions for a Nash equilibrium (see, also, Figure (ref) for the best response functions). The universal constants, $\gamma_{0}^{*},\Delta_{0}^{*}$ used in Theorem (ref) are derived in this manner. Specifically, Lemma (ref) demonstrates that these constants solve the following minimax problem, which characterizes the Nash equilibrium in the restricted sub-problem when $\eta=1$:
Perhaps the most striking aspect of the sampling rule is that it is just the Neyman allocation. This rule is non-adaptive (i.e., it is history independent), and is also independent of sampling costs. In fact, Corollary (ref) shows that the sampling and implementation rules are identical to those used in the best arm identification problem.
The Neyman allocation is well known in the RCT literature for being the sampling rule that minimizes the estimation variance of the treatment effect $\mu_{1}-\mu_{0}$. armstrong2022asymptotic shows that it retains its optimality for estimating $\mu_{1}-\mu_{0}$ even when adaptive sampling strategies are allowed. While Armstrong's armstrong2022asymptotic result does not apply to best arm identification, Corollary (ref) confirms that Neyman allocation is optimal in this context as well. Hence, practitioners should continue using the randomization designs employed in standard (i.e., non-sequential) experiments, even when adaptivity is allowed.
By way of comparison, the optimal sampling rule under Gaussian priors is also non-adaptive, but it varies deterministically with time liang2022dynamically. In fact, after a set time point $t^{*}$ that depends on $(\sigma_{1},\sigma_{0})$ and the prior variance, it too becomes equal to the Neyman allocation; see Appendix H for a detailed description. There are likely priors for which the Bayes optimal sampling rule is adaptive, but analyzing optimal decision rules under general classes of priors (beyond Gaussian or two-point priors) presents a challenging stochastic-filtering problem. As such, it appears difficult to provide any general claims on what priors lead to adaptive sampling.
The stopping time $\tau^{*}$ is adaptive but has a simple form: the DM ends the experiment when $\rho(t):=\sigma_{1}^{-1}x_{1}(t)-\sigma_{0}^{-1}x_{0}(t)$ exceeds $(\frac{\sigma_{1}+\sigma_{0}}{2c})^{1/3}\gamma_{0}^{*}$ in absolute value. The threshold is decreasing in $c$ and increasing in $\sigma_{1}+\sigma_{0}$. Let $\bar{x}_{a}(t):=x_{a}(t)/q_{a}(t)$ denote the sample average of outcomes from treatment $a$ at time $t$. Since $q_{a}(t)=\sigma_{a}t/(\sigma_{1}+\sigma_{0})$ under $\pi^{*}$, we can rewrite the optimal stopping rule as \[ \tau^{*}=\inf\left\{ t:t\left|\bar{x}_{1}(t)-\bar{x}_{0}(t)\right|\ge(\sigma_{1}+\sigma_{0})\gamma^{*}\right\} , \] meaning the experiment is stopped when the difference in average outcomes multiplied by the duration $t$ exceeds $(\sigma_{1}+\sigma_{0})\gamma^{*}$. Furthermore, from the definition of $\tau^{*}$ and ((ref)), we can infer that earlier stopping is indicative of larger reward gaps $\mu_{1}-\mu_{0}$, with the average length of the experiment being longest when $\mu_{1}-\mu_{0}=0$.
In contrast, fudenberg2018speed show that when $\sigma_{1}=\sigma_{0}$, the Bayes optimal stopping time under the independent Gaussian prior $\bm{\mu}\sim\mathcal{N}(0,\varsigma)\times\mathcal{N}(0,\varsigma)$ has the form $\tau_{\textrm{Bayes}}=\mathbb{I}\left\{ \vert\rho(t)\vert\ge b^{*}(t;c,\sigma_{1},\varsigma)\right\} $, where the threshold $b^{*}(t;\cdot)$ is now time-varying. The following intuition, adapted from fudenberg2018speed, helps explain the difference: Suppose that $\rho(t)\approx0$ for some large $t$. Under the Gaussian prior, this likely indicates that $\mu_{1}-\mu_{0}$ is close to $0$, suggesting no significant difference between the treatments, so the DM should terminate the experiment straightaway. Conversely, under the least-favorable prior $p_{\Delta^{*}}$, which has a two-point support, $\rho(t)\approx0$ would be interpreted as noise, so the DM should proceed henceforth as if starting the experiment from scratch. Thus, the properties of the stopping time are very different depending on the prior. The above intuition also suggests that the relation between $\mu_{1}-\mu_{0}$ and stopping times is more complicated under Gaussian priors, and not monotone as under minimax regret.
The stopping time, $\tau^{*}$, induces a specific probability of mis-identification of the optimal treatment under the least-favorable prior. By Lemmas (ref) and (ref), this probability is
Interestingly, $\alpha^{*}$ is independent of the model parameters $c,\sigma_{1},\sigma_{0}$. This is because the least-favorable prior adjusts the reward gap in response to these quantities.
Another remarkable property, following from fudenberg2018speed, is that the probability of mis-identification is independent of the stopping time for any given value of $\bm{\mu}$, i.e., $\mathbb{P}(\delta^{*}=1\vert\tau^{*},\bm{\mu}=\bm{b})=\mathbb{P}(\delta^{*}=1\vert\bm{\mu}=\bm{b})$ for any $\bm{b}\in\mathbb{R}^{2}$. This is again different from the setting with Gaussian priors, where earlier stopping is indicative of a higher probability of selecting the best treatment.
In both best arm identification and standard RCTs, the number of units of experimentation is specified beforehand. As we have seen previously, the Neyman allocation is minimax optimal under both adaptive and non-adaptive experiments. The benefit of the decision rule, $\bm{d}^{*}$, however, is that it enables one to stop the experiment early, thus saving on experimental costs. To quantify this benefit, fix some values of $\sigma_{1},\sigma_{0},c$, and suppose that nature chooses the least-favorable prior, $p_{\Delta^{*}}$, for the generalized Wald problem. Note that $p_{\Delta^{*}}$ is in general different from the least-favorable prior for the best arm identification problem.\footnote{However, the two coincide if the parameter values are such that $\eta:=\left(\frac{2c}{\sigma_{1}+\sigma_{0}}\right)^{1/3}=\bar{\Delta}_{0}^{*}/\Delta_{0}^{*}\approx0.484$, where $\Delta_{0}^{*},\bar{\Delta}_{0}^{*}$ are universal constants defined in the contexts of Theorem (ref) and Corollary (ref). }
Let \[ R^{*}:=\int\mathbb{E}_{\bm{d}^{*}\vert\bm{\mu}}\left[\max\{\mu_{1}-\mu_{0},0\}-(\mu_{1}-\mu_{0})\delta\right]dp_{\Delta^{*}} \] denote the Bayes regret, under $p_{\Delta^{*}}$, of the minimax decision rule $\bm{d}^{*}$ net of sampling costs. In fact, by symmetry, the above is also the frequentist regret of $\bm{d}^{*}$ under both the support points of $p_{\Delta^{*}}$. Now, let $T_{R^{*}}$ denote the duration of time required in a non-adaptive experiment to achieve the same Bayes regret $R^{*}$ (also under the least-favorable prior and net of sampling costs). Then, making use of some results from shiryaev2007optimal, we show in Appendix B.2 that
In other words, the use of an adaptive stopping time enables us to attain the same regret with $40\%$ fewer observations on average. Interestingly, the above result is independent of $\sigma_{1},\sigma_{0},c$, though the values of $\mathbb{E}[\tau^{*}]$ and $T_{R^{*}}$ do depend on these quantities (it is only the ratio that is constant). Admittedly, ((ref)) does not quantify the welfare gain from using an adaptive experiment - this will depend on the sampling costs - but it is nevertheless useful as an informal measure of how much the amount of experimentation can be reduced.
We now turn to the analysis of parametric models in discrete time. As before, the DM is tasked with selecting a treatment for implementation across a population. To this end, the DM experiments sequentially in periods $j=1,2,\dots$ after paying an `effective sampling cost' $C$ per period. Let $1/n$ denote the time interval between successive time periods. To analyze asymptotic behavior in this context, we introduce small cost asymptotics, wherein $C=c/n^{3/2}$ for some $c\in(0,\infty)$, and $n\to\infty$.
Are small cost asymptotics realistic? We contend they are, as $C$ is not the actual cost of experimentation, but rather characterizes the tradeoff between these costs and the benefits from full-scale implementation following the experiment. Indeed, one way to motivate this asymptotic regime is to imagine there are $n^{3/2}$ population units in the implementation phase, so the benefit of applying treatment $a$ is $n^{3/2}\mu_{a}$, but we divide by $n^{3/2}$ throughout. The actual cost of sampling an additional unit is $c$, which becomes $c/n^{3/2}$ after the division. Moreover, time $t$ is measured in units of $n$. This framework aligns with the practical observation that sampling costs are relatively small compared to population size, as seen in both online platforms (Deng et al., 2013) and clinical trials.
For example, in Phase 3 clinical trials, the per-unit cost of treatment is relatively high - moore2018estimated estimate the median cost per patient to be around 41,000\$. However, the potential welfare implications for the population are even more substantial, as the decisions from these trials impact millions of people and firms can expect to earn billions of dollars from successful blockbuster drugs. The effective marginal cost of each observation, obtained by dividing the monetary cost by the population size, is therefore quite small and falls well within our asymptotic framework. More generally, our scaling suggests that if the population size is $n^{3/2}$, one should aim to experiment on a sample size of the order $n$ to achieve optimal welfare. This naturally leads to small cost asymptotics.
As with any asymptotic regime, small-cost asymptotics only provide an approximation to the finite sample properties of decision rules (unless the outcomes are truly Gaussian, in which case they would be exact). The actual finite sample performance needs to be assessed using simulations. Nonetheless, asymptotic analysis offers a valuable benchmark: while there may exist decision rules that outperform our proposal in finite samples, it would be difficult to justify using one that is asymptotically inefficient.
In each period, the DM assigns a treatment to a single unit of observation according to some sampling rule $\pi_{j}(\cdot)$. The treatment assignment is a random draw $A_{j}\sim\textrm{Bernoulli}(\pi_{j})$. This results in an outcome $Y^{(a)}\sim P_{\theta}^{(a)}$, with $P_{\theta}^{(a)}$ denoting the population distribution of outcomes under treatment $a$. In this section, we assume that this distribution is known up to some unknown $\theta^{(a)}\in\mathbb{R}^{d}$. It is without loss of generality to assume $Y^{(1)},Y^{(0)}$ are mutually independent (conditional on $\theta^{(1)},\theta^{(0)}$) as we only ever observe the outcomes from one treatment anyway. After observing the outcome, the DM can decide either to stop sampling, or call up the next unit. At the end of the experiment, the DM prescribes a treatment to apply on the population.
We use the `stack-of-rewards-representation' for the outcomes from each arm (lattimore2020bandit). Specifically, $Y_{i}^{(a)}$ denotes the outcome for $i$-th data point corresponding to treatment $a$. Also, ${\bf y}_{nq}:=\{Y_{i}^{(a)}\}_{i=1}^{\left\lfloor nq\right\rfloor }$ denotes the sequence of outcomes after $\left\lfloor nq\right\rfloor $ observations from treatment $a$. We can imagine that prior to the experiment, nature draws an infinite stack of outcomes, ${\bf y}^{(a)}:=\{Y_{i}^{(a)}\}_{i=1}^{\infty}$, corresponding to each treatment $a$, and at each period $j$, if $A_{j}=a$, the DM observes the outcome at the top of the stack (this outcome is then removed from the stack corresponding to that treatment).
Recall that $t$ is the number of periods elapsed divided by $n$. Let \[ q_{a}(t):=\frac{1}{n}\sum_{j=1}^{\left\lfloor nt\right\rfloor }\mathbb{I}(A_{j}=a), \] and take $\mathcal{F}_{t}$ to be the $\sigma$-algebra generated by
the set of all actions and rewards until period $nt$. The sequence of $\sigma$-algebras, $\{\mathcal{F}_{t}\}_{t\in\mathcal{T}_{n}}$, where $\mathcal{T}_{n}:=\{1/n,2/n,\dots\}$, constitutes a filtration. We require $\pi_{nt}(\cdot)$ to be $\mathcal{F}_{t-1/n}$ measurable, the stopping time, $\tau$, to be $\mathcal{F}_{t-1/n}$ measurable, and the implementation rule, $\delta$, to be $\mathcal{F}_{\tau}$ measurable. The set of all decision rules $\bm{d}\equiv(\{\pi_{nt}\}_{t\in\mathcal{T}_{n}},\tau,\delta)$ satisfying these requirements is denoted by $\mathcal{D}_{n}$. As unbounded stopping times pose technical challenges, we generally work with $\mathcal{D}_{n,T}\equiv\left\{ \bm{d}\in\mathcal{D}_{n}:\tau\le T\ \textrm{a.s}\right\} $, the set of all decision rules with stopping times bounded by some arbitrarily large, but finite, $T$.
The mean outcomes under a parameter $\theta$ are denoted by $\mu_{a}(\theta):=\mathbb{E}_{P_{\theta}^{(a)}}[Y_{i}^{(a)}]$. Following hirano2009asymptotics, for each $a\in\{0,1\}$, we consider local perturbations of the form $\{\theta_{0}^{(a)}+h_{a}/\sqrt{n};h_{a}\in\mathbb{R}^{d}\}$, with $h_{a}$ unknown, around a reference parameter $\theta_{0}^{(a)}$. As in that paper, $\theta_{0}^{(a)}$ is chosen such that $\mu_{1}(\theta_{0}^{(1)})=\mu_{0}(\theta_{0}^{(0)})=0$; the last equality, which sets the quantities to $0$, is not necessary and is simply a convenient re-centering. This choice of $\theta_{0}^{(a)}$ defines the hardest instance of the generalized Wald problem. When $\mu_{1}(\theta_{0}^{(1)})\neq\mu_{0}(\theta_{0}^{(0)})$, determining the best treatment is trivial under large $n$, and many decision rules, including the one we propose here (in Section (ref)), would achieve zero asymptotic regret.
Let $P_{h}^{(a)}:=P_{\theta_{0}^{(a)}+h/\sqrt{n}}^{(a)}$ and take $\mathbb{E}_{h}^{(a)}[\cdot]$ to be its corresponding expectation. We assume $P_{\theta}^{(a)}$ is differentiable in quadratic mean around $\theta_{0}^{(a)}$ with score functions $\psi_{a}(Y_{i})$ and information matrices $I_{a}:=\mathbb{E}_{0}^{(a)}[\psi_{a}\psi_{a}^{\intercal}]$. For each $h\in\mathbb{R}^{d}$, denote \[ \mu_{n,a}(h):=\mu_{a}(\theta_{0}^{(a)}+h/\sqrt{n})\approx\dot{\mu}_{a}^{\intercal}h/\sqrt{n}, \] where $\dot{\mu}_{a}:=\nabla_{\theta}\mu_{a}(\theta_{0}^{(a)})$. To reduce some notational overhead, we set $\theta_{0}^{(1)}=\theta_{0}^{(0)}=\theta_{0}$, and also suppose that $\mu_{n,a}(h)=-\mu_{n,a}(-h)$ for all $h$. The latter is always true asymptotically. Both simplifications can be easily dispensed with, at the expense of some additional notation: we emphasize that our results do not fundamentally require $\theta_{0}^{(1)},\theta_{0}^{(0)}$ to be the same or even have the same dimension.
Let $P_{n,h}^{(a)}$ denote the joint probability over ${\bf y}_{nT}^{(a)}:=\left\{ Y_{1}^{(a)},\dots,Y_{nT}^{(a)}\right\} $ - the largest possible (under $\tau\le T$) iid sequence of outcomes that can be observed from treatment $a$ - when $Y^{(a)}\sim P_{h}^{(a)}$. Define $\bm{h}:=(h_{1},h_{0})$, take $P_{n,\bm{h}}$ to be the joint probability $P_{n,h_{1}}^{(1)}\times P_{n,h_{0}}^{(0)}$, and $\mathbb{E}_{n,\bm{h}}[\cdot]$ its corresponding expectation. The frequentist regret of decision rule $\bm{d}$ is defined as
where the multiplication by $\sqrt{n}$ in the second line of the above equation is a normalization ensuring $V_{n}(\bm{d},\bm{h})$ converges to a non-trivial quantity.
Let $\nu$ denote a dominating measure over $\{P_{\theta}:\theta\in\Theta\}$, and define $p_{\theta}:=dP_{\theta}/d\nu$. Also, take $M_{0}$ to be some prior over $\bm{h}$, and $m_{0}$ its density with respect to some other dominating measure $\nu_{1}$. By adusumilli2021risk, the posterior density (wrt $\nu_{1}$), $p_{n}(\cdot\vert\mathcal{F}_{t})$, of $\bm{h}$ depends only on ${\bf y}_{nq_{a}(t)}^{(a)}=\{Y_{i}^{(a)}\}_{i=1}^{\left\lfloor nq_{a}(t)\right\rfloor }$ for $a\in\{0,1\}$. Hence,
The fixed $n$ Bayes regret of a decision $\bm{d}$ is given by $V_{n}(\bm{d},m_{0}):=\int V_{n}(\bm{d},\bm{h})dm_{0}(\bm{h})$.
Following definition ((ref)), let $\xi_{\tau}$ denote the set of all actions and rewards generated over the course of the experiment. From the form of $V_{n}(\bm{d},\bm{h})$, it is clear that the Bayes optimal implementation rule is $\delta^{*}(\xi_{\tau})=\mathbb{I}\left\{ \mu_{n,1}(\xi_{\tau})\ge\mu_{n,0}(\xi_{\tau})\right\} $, and the resulting Bayes regret at the terminal state is
where $\mu_{n,a}(\xi_{\tau}):=\mathbb{E}_{\bm{h}\vert\xi_{\tau}}[\mu_{n,a}(h_{a})]$ and $\mu_{n}^{\max}(\xi_{\tau}):=\mathbb{E}_{\bm{h}\vert\xi_{\tau}}[\max\{\mu_{n,1}(h_{1}),\mu_{n,0}(h_{0})\}]$. We can thus associate each combination, $(\pi,\tau)$, of sampling rules and stopping times with the distribution $\mathbb{P}_{\pi,\tau}$ that they induce over $(\varpi_{n}(\xi_{\tau}),\tau)$. Thus, \[ V_{n}\left(\bm{d},m_{0}\right)=\mathbb{E}_{\pi,\tau}\left[\sqrt{n}\varpi_{n}(\xi_{\tau})+c\tau\right]. \] For any given $T<\infty$, the minimal Bayes regret in the fixed $n$ setting is therefore \[ V_{n,T}^{*}(m_{0})=\inf_{\bm{d}\in\mathcal{D}_{n,T}}\mathbb{E}_{\pi,\tau}\left[\sqrt{n}\varpi_{n}(\xi_{\tau})+c\tau\right]. \]
While our interest is in minimax regret, $V_{n,T}^{*}:=\inf_{\bm{d}\in\mathcal{D}_{n,T}}\sup_{\bm{h}}V_{n}(\bm{d},\bm{h})$, the minimal Bayes regret is a useful theoretical device as it provides a lower bound, $V_{n,T}^{*}\ge V_{n,T}^{*}(m_{0})$ for any prior $m_{0}$.
We impose the following assumptions (here, and in what follows, $\vert\cdot\vert$ denotes the Euclidean norm):
\begin{asm1} (i) The class $\{P_{\theta}^{(a)};\theta\in\mathbb{R}^{d}\}$ is differentiable in quadratic mean around $\theta_{0}$ for each $a\in\{0,1\}$. (ii) $\mathbb{E}_{0}^{(a)}[\exp\vert\psi_{a}(Y_{i}^{(a)})\vert]<\infty$ for $a\in\{0,1\}$. (iii) There exist $\dot{\mu}_{1},\dot{\mu}_{0}$ and $\epsilon_{n}^{(1)},\epsilon_{n}^{(0)}\to0$ s.t $\sqrt{n}\mu\left(P_{h}^{(a)}\right):=\sqrt{n}\mu_{n,a}(h)=\dot{\mu}_{a}^{\intercal}h+\epsilon_{n}^{(a)}\vert h\vert^{2}$ for each $a\in\{0,1\}$ and $h\in\mathbb{R}^{d}$.\end{asm1}
The assumptions are standard, with the only onerous requirement being Assumption 1(ii), which requires the score function to have bounded exponential moments. This is needed due to the proof techniques, which are adapted from adusumilli2021risk.
Let $V^{*}$ denote the asymptotic minimax regret, defined as the value of the minimax problem in ((ref)).
It is straightforward to extend Theorem (ref) to best arm identification. We omit the formal statement for brevity. The proof proceeds as follows: Let $\sigma_{a}^{2}:=\dot{\mu}_{a}^{\intercal}I_{a}^{-1}\dot{\mu}_{a}$, \[ h_{a}^{*}:=\frac{\sigma_{a}\Delta^{*}}{2\dot{\mu}_{a}^{\intercal}I_{a}^{-1}\dot{\mu}_{a}}I_{a}^{-1}\dot{\mu}_{a}, \] and take $m_{0}^{*}$ to be the symmetric two-prior supported on $(h_{1}^{*},-h_{0}^{*})$ and $(-h_{1}^{*},h_{0}^{*}$). This is the parametric counterpart to the least-favorable prior described in Theorem (ref). Clearly, there exist subsets $\mathcal{J}$ such that \[ \inf_{\bm{d}\in\mathcal{D}_{n,T}}\sup_{\bm{h}\in\mathcal{J}}V_{n}(\bm{d},\bm{h})\ge\inf_{\bm{d}\in\mathcal{D}_{n,T}}V_{n}(\bm{d},m_{0}^{*}). \] In Appendix (ref), we show
To prove ((ref)), we build on previous work in adusumilli2021risk. Standard techniques, such as asymptotic representation theorems van2000asymptotic, are not easily applicable here due to the continuous time nature of the problem. We instead employ a three step approach: First, we replace $P_{n,\bm{h}}$ with a simpler family of measures whose likelihood ratios (under different values of $\bm{h}$) are the same as those under Gaussian distributions. Then, for this family, we write down a HJB-Variational Inequality (HJB-VI) to characterize the optimal value function under fixed $n$. PDE approximation arguments then let us approximate the fixed-$n$ value function with that under continuous time. The latter is shown to be $V^{*}$.
The definition of asymptotic minimax risk used in Theorem (ref) is standard, see, e.g., van2000asymptotic, apart from the $\lim_{T\to\infty}$ operation. The theorem asserts that $V^{*}$ is a lower bound on minimax regret under any bounded stopping time. The bound $T$ can be arbitrarily large. Our proof techniques require bounded stopping times as various approximation results, e.g., the SLAN property (see, equation ((ref)) in Appendix (ref)), are only valid when the experiment is of bounded duration.\footnote{For any given $\hm{h}$, the dominated convergence theorem implies $\lim_{T\to\infty}\inf_{\bm{d}\in\mathcal{D}_{n,T}}V_{n}(\bm{d},\bm{h})=\inf_{\bm{d}\in\mathcal{D}_{n}}V_{n}(\bm{d},\bm{h})$. However, to allow $T=\infty$ in Theorem (ref), we need to show that this equality holds uniformly over $n$. In specific instances, e.g., when the parametric family is Gaussian, this is indeed the case, but we are not aware of any general results in this direction. } Nevertheless, we conjecture that there is no loss in setting $T=\infty$ in practice.
We now describe a decision rule $\bm{d}_{n}=(\pi_{n},\tau_{n},\delta_{n})$ that is asymptotically minimax optimal. Let $\sigma_{a}^{2}=\dot{\mu}_{a}^{\intercal}I_{a}^{-1}\dot{\mu}_{a}$ for each $a$ and \[ \rho_{n}(t):=\frac{x_{1}(t)}{\sigma_{1}}-\frac{x_{0}(t)}{\sigma_{0}},\ \textrm{where}\quad x_{a}(t):=\frac{\dot{\mu}_{a}^{\intercal}I_{a}^{-1}}{\sqrt{n}}\sum_{i=1}^{\left\lfloor nq_{a}(t)\right\rfloor }\psi_{a}(Y_{i}^{(a)}). \] Note that $x_{a}(t)$ is the efficient influence function process for estimation of $\mu_{a}(\theta)$. We assume $\dot{\mu}_{a},I_{a},\sigma_{a}$ are known; but in practice, they should be replaced with consistent estimates (from a vanishingly small initial sample) so that they do not require knowledge of the reference parameter $\theta_{0}$. As described in the next section, this can be done without affecting the asymptotic results.
Take $\pi_{n}$ to be any sampling rule such that
for some $B<\infty$ and $b_{0}>1/2$. To simplify matters, we suppose that $\pi_{n}$ is deterministic, e.g., $\pi_{n,1}(t)=\mathbb{I}\left\{ q_{1}(t)\le t\sigma_{1}/(\sigma_{1}+\sigma_{0})\right\} $. Fully randomized rules, $\pi_{n,1}(t)=\sigma_{1}/(\sigma_{0}+\sigma_{1})$, do not satisfy the `fine-balance' condition ((ref)) and we indeed found them to perform poorly in simulations. We further employ \[ \tau_{n,T}=\inf\left\{ t:\left|\rho_{n}(t)\right|\ge\gamma^{*}\right\} \wedge T \] as the stopping time, and as the implementation rule, set $\delta_{n,T}=\mathbb{I}\left\{ \rho_{n}(\tau_{n,T})\ge0\right\} $.
Intuitively, $\bm{d}_{n,T}=(\pi_{n},\tau_{n,T},\delta_{n,T})$ is the finite sample counterpart of the minimax optimal decision rule $\bm{d}^{*}$ from Section (ref). The following theorem shows that it is asymptotically minimax optimal in that it attains the lower bound of Theorem (ref).
An important implication of Theorem (ref) is that the minimax optimal decision rule only involves one state variable, $\rho_{n}(t)$. This is even though the state space in principle includes all the past observations until period $i$, for a total of at least $2i$ variables. The theorem thus provides a major reduction in dimension.
Replacing $\sigma_{1},\sigma_{0}$ (and other population quantities) with consistent estimates has no effect on asymptotic regret. We suggest two approaches to attain the minimax lower bounds when these parameters are unknown.
The first approach uses `forced exploration' (see, e.g., lattimore2020bandit): we set $\pi_{n}^{*}(t)=1/2$ for the first $\bar{n}=n^{a}$ observations, where $a\in(0,1)$. This corresponds to a time duration of $\bar{t}=n^{a-1}$. We use the data from these periods to obtain consistent estimates, $\hat{\sigma}_{1}^{2},\hat{\sigma}_{0}^{2}$ of $\sigma_{1}^{2},\sigma_{0}^{2}$. From $\bar{t}$ onwards, we apply the minimax optimal rule $\bm{d}_{n,T}$ after plugging-in $\hat{\sigma}_{1},\hat{\sigma}_{0}$ in place of $\sigma_{1},\sigma_{0}$. Note that when applying $\bm{d}_{n,T}$, we should start $x_{1}(\cdot),x_{0}(\cdot)$ from their values at $\bar{t}$ to ensure the information accrued before $\bar{t}$ is also taken into account. This strategy is asymptotically minimax optimal for any $a\in(0,1)$.
Our second suggestion is to place a prior on $\sigma_{1},\sigma_{0}$, and continuously revise their values using the posterior means. We recommend using an inverse-gamma prior and computing the posterior by treating the scores $\psi_{a}(Y_{i}^{(a)})$ as Gaussian (which is justified asymptotically). This approach has the advantage of not requiring any tuning parameters.
Admittedly, both proposals treat estimation of $\sigma_{1},\sigma_{0}$ as separate and somewhat less critical than the estimation of the population mean parameters. However, this merely reflects the significant asymmetry in the complexity of estimating these parameters in the continuous time setting. As noted in Section (ref), $\sigma_{1},\sigma_{0}$ can be learnt instantly in continuous time from the quadratic variations of $x_{1}(t),x_{0}(t)$. Conversely, running the sequential experiment for a brief period would only marginally update the prior over $\bm{\mu}$.
Furthermore, in the finite $n$ setting, it is important to recognize that $\theta^{(a)}$ characterizes the entire distribution of $Y^{(a)}$, including its mean and variance. The quantities $\sigma_{1},\sigma_{0}$ do not represent the variances of the underlying probability distributions - which are subject to change anyway under the local sequence $\theta_{0}^{(a)}+h_{a}/\sqrt{n}$ - but are rather the information matrices evaluated at the reference parameters $\theta_{0}^{(1)},\theta_{0}^{(0)}$. Conceptually, under local asymptotics, these reference parameters are assumed to be known in advance. While one would aim, in practice, to construct procedures that adapt to or are invariant to these quantities, the impact of estimating them cannot be accounted for in the local asymptotic framework itself. This is not to diminish the importance of efficiently estimating $\sigma_{1},\sigma_{0}$; rather, the issue lies outside the scope of first-order asymptotic theory, which is just too coarse an approximation for this purpose. Addressing this would require employing higher-order asymptotics.
A/B testing is commonly used in online platforms for optimizing websites. Consequently, to assess the finite sample performance of our proposed policies, we run a Monte-Carlo simulation calibrated to a realistic example of such an A/B test. Suppose there are two candidate website layouts, with exit rates $\gamma_{0},\gamma_{1}$, and we want to run an A/B test to determine the one with the lowest exit rate.\footnote{The exit rate is defined as the fraction of viewers of a webpage who exit from the website it is part of (i.e., without viewing other pages in that website).} The outcomes are binary, $Y^{(a)}\sim\textrm{Bernoulli}(\gamma_{a})$. This is a parametric setting with score functions $\psi_{a}(Y_{i}^{(a)})=Y_{i}^{(a)}$. We calibrate $\gamma_{0}=0.4$, which is a typical value for an exit rate. The cost of experimentation is normalized to $c=1$ and we consider various values of $n$, corresponding to different `population sizes' (recall that the benefit during implementation is scaled as $n^{3/2}\gamma_{a}$). We then set $\gamma_{1}=\gamma_{0}+\Delta/\sqrt{n}$, and describe the results under varying $\Delta$. Local asymptotics provide a good approximation in practice because raw performance gains are generally small - typically, $\vert\gamma_{1}-\gamma_{0}\vert$ is of the order 0.05 or less (see, e.g., deng2013improving) - but these gains can translate into large profits when applied at scale, i.e., when $n$ is large.
Since $\sigma_{a}=\sqrt{\gamma_{a}(1-\gamma_{a})}$ is unknown, we employ `forced sampling' with $\bar{n}=\max(50,0.05n)$, i.e., using about 5% of the sample, to estimate $\sigma_{1},\sigma_{0}$. Note that the asymptotically optimal sampling rule is always $1/2$ in the Bernoulli setting, so forced sampling is in fact asymptotically costless. We also experimented with a beta prior to continuously update $\sigma_{a}$, but found the results to be somewhat inferior, (see Appendix C for details). Figure (ref), Panel A plots the finite sample frequentist regret profiles of our policy rules $\bm{d}_{n}:=\bm{d}_{n,\infty}$ (with $T=\infty$) for various values of $n$, along with that of the minimax optimal policy $\bm{d}^{*}$ under the diffusion regime; the regret profile of the latter is derived analytically in Lemma (ref). Diffusion asymptotics provide a very good approximation to the finite sample properties of $\bm{d}_{n}$, even for such relatively small values of $n$ as $n=1000$. In practice, A/B tests often involve tens, even hundreds, of thousands of observations. The max-regret of $\bm{d}_{n}$ is also very close to the asymptotic lower bound $V^{*}$ (the max-regret of $\bm{d}^{*}$).
Figure (ref), Panel B displays some summary statistics for the Bayes regret of $\bm{d}_{n}$ under the least-favorable prior, $p_{\Delta^{*}}$. The regret distribution is positively skewed and heavy tailed. The finite sample Bayes regret is again very close to $V^{*}$.
Appendix C reports additional simulation results using Gaussian outcomes.
We now consider various modifications of the basic setup and analyze if, and how, the optimal decisions change. Appendix G discusses extensions to multiple treatments.
In practice, it may be that data is collected in batches instead of one at a time, and the DM can only make decisions after processing each batch. Let $B_{n}$ denote the number of observations considered in each batch. In the context of Section (ref), this corresponds to a time duration of $B_{n}/n$. An analysis of its proof shows that Theorem (ref) continues to hold as long as $B_{n}/n\to0$. Thus, $\bm{d}_{n,T}$ remains asymptotically minimax optimal in this scenario.
Even for $B_{n}/n\to m\in(0,1)$, the optimal decision rules remain broadly unchanged. Asymptotically, we have equivalence to Gaussian experiments, so we can analyze batched experiments under the diffusion framework by imagining that the stopping time is only allowed to take on discrete values $\{0,1/m,2/m,\dots\}$. It is then clear from the discussion in Section (ref) that the optimal sampling and implementation rules remain unchanged. The discrete nature of the setting makes determining the optimal stopping rule difficult, but it is easy to show that the decision rule $(\pi^{*},\tau_{m}^{*},\delta^{\tau_{m}^{*}})$, where \[ \tau_{m}^{*}:=\inf\left\{ t\in\{0,1/m,2/m,\dots\}:\left|\frac{x_{1}(t)}{\sigma_{1}}-\frac{x_{0}(t)}{\sigma_{0}}\right|\ge\gamma^{*}\right\} \] and $\delta^{\tau_{m}^{*}}:=\mathbb{I}\left\{ \sigma_{1}^{-1}x_{1}(\tau_{m}^{*})-\sigma_{0}^{-1}x_{0}(\tau_{m}^{*})\ge0\right\} $, while not being exactly optimal, has a minimax regret that is arbitrarily close to $V^{*}$ for large enough $m$ (note that no batched experiment can attain a minimax regret that is lower than $V^{*}$).
All our results so far were derived under constant sampling costs. The same techniques apply to other types of flow costs as long as these depend only on $\rho(t):=\sigma_{1}^{-1}x_{1}(t)-\sigma_{0}^{-1}x_{0}(t)$. In particular, suppose that the frequentist regret is given by \[ V\left(\bm{d},\bm{\mu}\right)=\mathbb{E}_{\bm{d}\vert\bm{\mu}}\left[\max\{\mu_{1}-\mu_{0},0\}-(\mu_{1}-\mu_{0})\delta+\int_{0}^{\tau}c(\rho(t))dt\right], \] where $c(z)$ is the flow cost of experimentation when $\rho(t)=z$. We require $c(\cdot)$ to be (i) positive, (ii) bounded away from $0$, i.e., $\inf_{z}c(z)\ge\underline{c}>0$, and (iii) symmetric, i.e., $c(z)=c(-z)$. By ((ref)), $(\sigma_{1}+\sigma_{0})\rho(t)/t$ is an estimate of the treatment effect $\mu_{1}-\mu_{0}$, so the above allows for situations in which sampling costs depend on the magnitude of the estimated treatment effects. While we are not aware of any real world examples of such costs, they could arise if there is feedback between the observations and sampling costs, e.g., if it is harder to find subjects for experimentation when the treatment effect estimates are higher. When there are only two states, the `ex-ante' entropy cost of sims2003implications is also equivalent to a specific flow cost of the form $c(\cdot)$ above, see morris2019wald.\footnote{However, we are not aware of any extension of this result to continuous states.}
For the above class of cost functions, we show in Appendix D that the minimax optimal decision rule $\bm{d}^{*}$ and the least-favorable prior $p_{\Delta}^{*}$ have the same form as in Theorem (ref), but the values of $\gamma^{*},\Delta^{*}$ are different and need to be calculated by solving the minimax problem \[ \min_{\gamma}\max_{\Delta}\left\{ \left(\frac{\sigma_{1}+\sigma_{0}}{2}\right)\frac{\left(1-e^{-\Delta\gamma}\right)\Delta}{e^{\Delta\gamma}-e^{-\Delta\gamma}}+\frac{\left(e^{\Delta\gamma}-1\right)\zeta_{\Delta}(\gamma)+\left(1-e^{-\Delta\gamma}\right)\zeta_{\Delta}(-\gamma)}{e^{\Delta\gamma}-e^{-\Delta\gamma}}\right\} , \] where \[ \zeta_{\Delta}(x):=2\int_{0}^{x}\int_{0}^{y}e^{\Delta(z-y)}c(z)dzdy. \]
Beyond this class of sampling costs, however, it is easy to conceive of scenarios in which the optimal decision rule differs markedly from the one we obtain here. For instance, Neyman allocation would no longer be the optimal sampling rule if the costs for sampling each treatment were different. Alternatively, if $c(\cdot)$ were to depend on $t$, the optimal stopping time could have a very different form. The analysis of these cost functions is not covered by the present techniques.
In Appendix E, we extend Theorems (ref) and (ref) to the non-parametric setting, where there is no a-priori information about the distributions $P^{(1)},P^{(0)}$ of $Y_{i}^{(1)}$ and $Y_{i}^{(0)}.$ The minimax optimal rule retains the same form as in Section (ref), but with $x_{a}(t)$ now defined as $n^{-1/2}\sum_{i=1}^{\left\lfloor nq_{a}(t)\right\rfloor }Y_{i}^{(a)}$, and $\sigma_{a}^{2}$ as the variance of $Y_{i}^{(a)}$ at some reference distribution $P_{0}^{(a)}$ (as in Section (ref), $P_{0}^{(1)},P_{0}^{(0)}$ are to be chosen such that $\mathbb{E}_{P_{0}^{(1)}}[Y_{i}^{(1)}]=\mathbb{E}_{P_{0}^{(0)}}[Y_{i}^{(0)}]$). One can obtain these same results by simply assuming the outcomes to be Gaussian.
The above results can also be extended to different regret measures. Specifically, instead of $\mu(\cdot)$ denoting the mean functional in the definition of regret $\max\{\mu(P^{(1)})-\mu(P^{(0)}),0\}-(\mu(P^{(1)})-\mu(P^{(0)}))\delta+c\tau$, it can denote other functionals of the outcome distribution in the implementation phase (we still need costs to be linear and additively separable). For instance, $\mu(\cdot)$ could be the quantile function. In Appendix E.4, we show that the decision rule $\bm{d}_{n.T}$ from Section (ref) is still minimax optimal if we just redefine $x_{a}(t)$ to now be the efficient influence function process $n^{-1/2}\sum_{i=1}^{\left\lfloor nq_{a}(t)\right\rfloor }\psi_{a}(Y_{i}^{(a)})$, where $\psi_{a}(\cdot)$ is the efficient influence function corresponding to $\mu(P^{(a)})$.
This paper proposes a minimax-regret optimal procedure for determining the best treatment when sampling is costly. The optimal sampling rule is simply the Neyman allocation, while the optimal stopping rule advises that the experiment be terminated when the average difference in outcomes multiplied by the number of observations exceeds a specific threshold. While these rules were derived under diffusion asymptotics, it is shown that finite sample counterparts of these rules remain optimal under both parametric and non-parametric regimes. The form of these rules is robust to a number of different variations of the original problem, e.g., under batching, different cost functions etc. Given the simple nature of these rules, and the potential for large efficiency gains (requiring, on average, 40% fewer observations than standard approaches), we believe they hold a lot of promise for practical use.
The data and code underlying this article are available in Zenodo, at \href{https://doi.org/10.5281/zenodo.14792035}{https://doi.org/10.5281/zenodo.14792035}.