Improving the Estimation of Lifetime Effects in A/B Testing via Treatment Locality

Improving the Estimation of Lifetime Effects in A/B Testing via Treatment Locality

\ifRMP \RUNAUTHOR{Anonymous Authors} \else \RUNAUTHOR{Chen, Simchi-Levi, and Wang} \fi

\RUNTITLE{Experimenting with Treatment Locality}

\TITLE{Improving the Estimation of Lifetime Effects in A/B Testing via Treatment Locality} \ifRMP \ARTICLEAUTHORS{ \AUTHOR{Anonymous Authors}} \else \ARTICLEAUTHORS{ \AUTHOR{Shuze Chen} \AFF{Graduate School of Business, Columbia University, New York, NY 10027, \EMAIL{[email removed]} } \AUTHOR{David Simchi-Levi} \AFF{Institute for Data, Systems, and Society, Department of Civil and Environmental Engineering, and Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA 02139, \EMAIL{[email removed]}} \AUTHOR{Chonghuan Wang} \AFF{ Naveen Jindal School of Management, University of Texas at Dallas, Richardson, TX 75080, \EMAIL{[email removed]}} }

\fi \ABSTRACT{ Utilizing randomized experiments to evaluate the effect of short-term treatments on the short-term outcomes has been well understood and become the golden standard in industrial practice. However, as service systems become increasingly dynamical and personalized, much focus is shifting toward maximizing long-term outcomes, such as customer lifetime value, through lifetime exposure to interventions. Our goal is to assess the impact of treatment and control policies on long-term outcomes from relatively short-term observations, such as those generated by A/B testing. A key managerial observation is that many practical treatments are local, affecting only targeted states while leaving other parts of the policy unchanged. This paper rigorously investigates whether and how such locality can be exploited to improve estimation of long-term effects in Markov Decision Processes (MDPs), a fundamental model of dynamic systems. We first develop optimal inference techniques for general A/B testing in MDPs and establish corresponding efficiency bounds. We then propose methods to harness the localized structure by sharing information on the non-targeted states. Our new estimator can achieve a linear reduction with the number of test arms for a major part of the variance without sacrificing unbiasedness. It also matches a tighter variance lower bound that accounts for locality. Furthermore, we extend our framework to a broad class of differentiable estimators, which encompasses many widely used approaches in practice. We show that all such estimators can benefit from variance reduction through information sharing without increasing their bias. Together, these results provide both theoretical foundations and practical tools for conducting efficient experiments in dynamic service systems with local treatments.

}

\KEYWORDS{Customer Lifetime Value, Randomized Experiments, Local Treatment}

Introduction

Randomized experiments, commonly known as A/B testing, have emerged as an indispensable tool, enabling organizations across various sectors—including service, retail, manufacturing, and healthcare—to empirically test and refine their strategies for enhancing customer engagement and satisfaction (imbens2015causal,kohavi17the,Kohavi_Tang_Xu_2020, koning22exp). In particular, A/B testing is well-established and widely used to compare short-term or immediate outcomes (e.g., whether a customer clicks on an advertisement) resulting from short-term treatments (e.g., displaying a new version of the advertisement).

However, as service systems grow more complex and dynamic, the focus is increasingly shifting from immediate or short-term outcomes to long-term effects on customers or users who are continually exposed to new interventions. For example, online retailers may employ strategies such as regular coupon distribution or cash back, aiming to trade-off short-term profit reductions for potential life-time revenue gains (simester06dynamic). Similarly, user interface updates on web platforms tend to have continual exposure to customers after their launches, thus impacting user experience and engagement over extended periods (huang2023estimating,maystre2023optimizing). These practical scenarios require estimating the impact of long-term treatments on long-term outcomes, such as customer lifetime value, using relatively short-term observations from randomized experiments.

In this work, we investigate the randomized experiments on Markov Decision Processes (MDPs), which are widely used to model dynamic service systems over extended time horizons including customer relationships (pfeifer2000modeling), inventory control (gong23bandits), two-sided platforms (ramesh22tsr), mobile health (zhang2023statistical) and many others. Additionally, as modern systems become increasingly complex with numerous states, the practical challenges of implementing entirely new global policies intensify. Such policies could be overly aggressive, in terms of posing significant risks and requiring substantial infrastructure changes. Consequently, many treatments in practice are becoming more fine-grained and localized. This means that the new treatments may only apply on a small number of targeted states locally. For instance, in the customer relationships, the customer's states are referring to her recent behaviors or other contextual factors. An online marketplace or service platform might offer a “welcome-back" coupon to the customer only when she has not engaged with the service for an extended period (e.g., Sephora’s Welcome Back Event danielle20sephora). If she is a daily active user, she might not receive it. Similarly, physical retail locations like pharmacies and markets may provide incentives like cash back to the customer only when she makes in-store purchases (e.g., Bed Bath & Beyond rafi15bed). Likewise, a typical intervention for recommender systems may involve precise exposure, only taking effect when user click into certain pages such as banners or author profiles, without altering other system components throughout the iterative recommendation process (e.g., Spotify maystre2023optimizing and Douyin). These localized treatments are strategic, usually aiming to optimize the lifetime value of customers by tailoring experiences and offers to individual needs and histories. Given the prevalence of local treatments in practice, our research goal is to explore the potential of leveraging treatment locality to optimize data utilization for efficient A/B testing on long-term effects within an MDP environment.

An Illustrative Example: Customer Lifetime Value

To be more concrete about our research question, we further introduce an application example on improving customer lifetime value, adapted from a seminal work in the marketing literature by pfeifer2000modeling and closely related to customer retention and churn management (hamilton2023churning,lemmens20managing, kan24managing). This example will be revisited throughout the paper.

Overview of Main Results

To demonstrate our results, we start with what is arguably the most fundamental and illustrative scenario: the new local treatment available in only one specific state. We refer to such a local treatment as Single-State Treatment (SST). In this setup, the treatment policy of interest applies the new SST whenever possible and adheres to the control policy in all other states. Our objective is to estimate and infer the Average Treatment Effect (ATE), which quantifies the difference in long-term cumulative rewards between the treatment policy and the control policy. We summarize and highlight our main results in detail below.

First, we design an efficient estimator of ATE in general A/B testing on MDPs, where the treatment does not need to be local. Specifically, we show that the two principal approaches from the reinforcement learning (RL) literature, the model-based estimation and temporal difference (TD) learning, remain effective for estimating ATE if the data are split correctly. Our proposed estimator is asymptotically normal and unbiased. Moreover, we show that no unbiased estimator can achieve a smaller variance without considering treatment locality. This result builds on a new efficiency proof framework via the constrained Cramér-Rao bound.

We then introduce an estimator that incorporates the SST structure by sharing data collected from states where the new treatment is not applied. While data sharing naturally increases the sample size for both the treatment and control policies, it also introduces additional correlations that complicate the overall variance. Fortunately, we are able to show that this estimator can always achieve a smaller variance compared to the original estimator that does not share data. Our analysis further reveals that the variance reduction arises specifically from the component of the variance associated with the states that share data. Importantly, when extending to multiple test arms, we illustrate that a major part of the asymptotic variance can be reduced linearly with the number of test arms compared to the estimator that does not use the SST structure. Additionally, we derive another variance lower bound for all unbiased estimators even with the knowledge of the SST, which confirms the optimality of our proposed estimator.

While we have focused on the unbiased estimator for a specific ATE, decision-makers can have many other design choices for A/B testing in dynamic systems. For example, in practice, a slight bias may be acceptable if it substantially reduces variance. Motivated by this, we define a broad class of estimators, called differentiable estimators, which includes many existing estimators in the literature (e.g., farias2022markovian,farias2023correcting,huang2023estimating). We show that information sharing universally reduces variance without increasing bias for all differentiable estimators. Consequently, any proposed differentiable estimators, regardless of its specific design objective, could immediately benefit from the variance reduction through information sharing if the treatment is local. When there are multiple testing arms, a major component of the variance can also get a linear reduction in the number of arms. These results further illustrate the power of treatment locality.

Having demonstrated the variance reduction achieved through SST, we also expand our framework and generalize the results to cover more general local treatments, which are applicable to multiple states, broadening the scope and applicability of our results. We also test the effectiveness of our design on a synthetic environment as well as a Sepsis simulator based on real-world data. Finally, we reveal that under SST, the treatment effect remains consistently positive (or negative) for all states before and after the intervention. This indicates that if the new treatment benefits one state, it benefits all others as well.

Related Works

\noindentStructure-aware Experiment Design. Experimental design originated in economics with basically model-free methods. In recent years, researchers in operations research and management science instead realize that there are many useful structures in operations scenarios to understand, analyze and improve experimentation. bojinov23design,hu2022switchback,ni2023design,jia2023clustered,xiong2024data consider the switchback design under various scenarios, from temporal interference to spatial interference, from stationary environment to non-stationary environment, and from theory driven perspective to data driven perspective. glynn2020adaptive,munro2024treatmenteffectsmarketequilibrium,wagner21experimenting,bajari2021multiplerandomizationdesigns,ramesh22tsr, zhu2024seller,weng24exp study the experiments happening on two-sided markets and a common practice is to model the system as a continuous-time Markov chain. chen2025b investigate the A/B testing in e-commerce where the product stock-out can introduce extra bias. chen2025bias analyze the bias of experiments for inventory control policies. li15thevalue leverage the sparsity structure of cross-product demand elasticities to greatly reduce the number of experiments required. li2023experimenting carefully take the queuing structure into account and propose efficient estimators under the stochastic congestion. xiong2023optimal investigate multi-unit settings with varying treatment starting times. zhan2021off, zhan23policy study the post-experiment inference for contextual bandits, which does not capture the state transition as our MDPs. simester20efficiently pioneer at considering treatment structures and suggest comparing outcomes only for customers exposed to different treatment and control actions to improve efficiency empirically. Compared to theirs, we further incorporate complex transition dynamics and provide theoretical guarantees of estimations. The long-term effect with the long-term treatment under the short-term measurement is recently studied by huang2023estimating. This paradigm of structure-aware experiment design has witnessed great success in theory and practice in above works with either significant reduction of bias or substantial improvement of efficiency.

\noindentExperimenting on MDPs with General Treatments. Experimenting on MDPs is more relevant to our work. Many works adopt MDPs to capture the dynamical system and investigate the long-term outcomes (pfeifer2000modeling,Murphy_2003,simester06dynamic,tran2023inferring, shi2021statistical,shi2023dynamic, farias2022markovian, farias2023correcting), where most previous works consider general treatment, i.e. a treatment will be posed to every state of MDP. The seminal work by farias2022markovian studies the average reward setting. They prove the asymptotic lower bound for unbiased inference on MDPs and show that this lower bound can sometimes grow exponentially with the number of states. They also construct an LSTD(0)-type OPE estimator that is efficient and achieves this lower bound. In our work, we show that similar phenomena can also be observed in the discounted reward settings. Moreover, farias2022markovian study the bias of a Naive estimator and propose an alternative estimator that achieves a notable bias-variance trade-off with an upper bound of asymptotic variance. In the sequel, we demonstrate all three estimators studied in farias2022markovian fall into a general class of differentiable estimator and can thus all benefit from the variance reduction leveraging treatment locality. Finally, some recent work like shi2023dynamic,zhang2023statistical considers asymptotic results with linear function approximation. In contrast, this paper focuses on a fundamental split of the experimental data and is therefore orthogonal to previous literature on estimator design.

In addition, there is another line of work including syrgkanis2023postepisodic, cheikhi23on, shi2021statistical, khamaru21istemp, tran2023inferring that considers asymptotic inference on MDPs but under episodic setting or with the assumption of a generative model, which means the MDP can be independently simulated many times. In contrast, we consider estimations that can only sample one trajectory from a non-episodic MDP, which restricts our access to the data and thus imposes additional challenges.

Structures and Notations

In Section (ref), we formally introduce the model and the formulation, introducing the MDP, the treatment policy and the control policy, and the average treatment effect that we care about. Section (ref) presents the estimation methods for the long-term cumulative rewards of a single, specific policy. In Section (ref), we discuss the idea of classical A/B testing in our setting and how to estimate the long-term cumulative rewards for the treatment and control policies from A/B testing. Section (ref) provides a new estimator based on the idea of information sharing for the local treatment. Section (ref) generalizes the analysis to the general local treatments. Section (ref) introduces the differentiable estimators, which can always benefit from the information sharing. In Section (ref), we provide some numerical results verifying the idea of information sharing including the real-world sepsis simulation results. Section (ref) covers the discussion on some useful properties of the local treatment as well as future work. We conclude our paper in Section (ref).

We denote for any $N\in\mathbb{Z}^+, [N]=\{1,2,\cdots,N\}$. For any vector $x$ and matrix ${\bm{A}}$, we define the semi-norm induced by the matrix $A$ as $\|x\|_{\bm{A}}\coloneqq \sqrt{x^\top {\bm{A}} x}$. Additionally, for any function on the state space $f\colon {\mathcal{S}} \to \mathbb{R}$, we denote $\operatorname{Diag}_{s\in{\mathcal{S}}}(f(s))\coloneqq \operatorname{Diag}(f(s^1),\cdots,f(s^K))\in\mathbb{R}^{K\times K}$. Moreover, we define $a\vee b\coloneqq\max\{a,b\}$ and $a\land b\coloneqq\min\{a,b\}$.

Model

We start with the general definition of experimenting on MDPs and then specify the Single-State Treatment (SST), which serves as a simple yet illustrative example of local treatment. In Section (ref), we generalize this concept to broader local treatment scenarios.

Consider a (non-episodic, finite-state, infinite-horizon) MDP with state space ${\mathcal{S}}:=\{s^{i}\}_{i\in [K]}$ with cardinality $K$. At time $t\in\mathbb{N}$, we denote the state of the MDP by $s_t\in{\mathcal{S}}$. Associated with each state is a set of available actions, ${\mathcal{A}}$, which influence the state transitions through the transition probability function $P: {\mathcal{S}}\times {\mathcal{A}}\times{\mathcal{S}} \rightarrow [0,1]$. Here, the next state $s_{t+1}$ follows the distribution $s_{t+1} \sim P(\cdot\mid s_t,a_t)$. For each state-action pair $(s,a)$, the instant reward $r$ earned is independently generated by a Gaussian distribution\footnotemark, i.e., $r\sim {\mathcal{N}}(r(s,a), \sigma_r^2(s,a))$, where we assume $\sigma^2_r(s,a)<\infty$ for all $(s,a)$ pairs. \footnotetext{With standard arguments, our results can be extended to the setting where the second moment of the noise is finite.} A policy $\pi: {\mathcal{S}} \rightarrow {\mathcal{A}}$ maps states to (random) actions. The value function is defined as the cumulative discounted reward starting from state $s\in{\mathcal{S}}$ under a policy $\pi$,

where $0\le \gamma<1$ is a discount factor that reflects the trade-off between instant and future rewards. The value function has been widely applied to quantify long-term outcomes in various fields including marketing (pfeifer2000modeling, simester06dynamic), ride-hailing platforms (shi2023dynamic), and video streaming service (tran2023inferring, maystre2023optimizing). We further use ${\bm{V}}^\pi \in \mathbb{R}^K \coloneqq (V^\pi(s^1),\cdots,V^\pi(s^K))^\top$ to denote value functions of all states under policy $\pi$. Moreover, associated with each $\pi$, ${\bm{r}}^\pi\in\mathbb{R}^K$ is the expected reward under each state, defined as ${\bm{r}}^\pi(s) \coloneqq \sum_{a\in{\mathcal{A}}}r(s,a)\pi(a\mid s)$ for $s\in{\mathcal{S}}$. ${\bm{P}}^\pi\in \mathbb{R}^{K\times K}$ is the transition matrix under $\pi$ with ${\bm{P}}^\pi(s,s^\prime)\coloneqq \sum_{a\in{\mathcal{A}}}P(s^\prime\mid s,a)\pi(a\mid s)$ for $s,s^\prime\in{\mathcal{S}}$.

We now introduce a special class of treatment policies that we call the Single-State Treatment (SST). Specifically, there exists a pre-determined “crucial" state, which without loss of generality, we assume to be $s^1$. The treatment of interest is applied exclusively when the system's state, $s_t$, coincides with $s^1$. Formally, we assume that ${\mathcal{A}}=\{{\mathfrak{c}},{\mathfrak{t}}\}$ regardless of states, while the action ${\mathfrak{t}}$, representing the new treatment, is only applicable in the crucial state $s^1$, while ${\mathfrak{c}}$ denotes the control or default action. This restriction ensures that the treatment is targeted and its effects are isolated to the crucial state.

Building on the definition of SST, we next define two policies and the corresponding treatment effect we aim to assess.

The treatment effect that we are interested in is the difference of the value function under the treatment policy and the control policy. For simplicity, we specially abbreviate the value functions under $\pi^{\mathfrak{t}}$ and $\pi^{\mathfrak{c}}$, $V^{\pi^{\mathfrak{t}}}(s)$ and $V^{\pi^{\mathfrak{c}}}(s)$, as $V^{{\mathfrak{t}}}(s)$ and $V^{{\mathfrak{c}}}(s)$, respectively. Specifically, for a given initial state $s$, the estimand of our interest is the average treatment effect (ATE),

For all the states, we write the treatment effect in a more compact way as ${\bm{\Delta}} \coloneqq {\bm{V}}^{{\mathfrak{t}}}-{\bm{V}}^{{\mathfrak{c}}}$, where ${\bm{V}}^{{\mathfrak{t}}}$ and ${\bm{V}}^{{\mathfrak{c}}}$ are abbreviations of ${\bm{V}}^{\pi^{\mathfrak{t}}}$ and ${\bm{V}}^{\pi^{\mathfrak{c}}}$, respectively. The central research question of our paper is to estimate the ATE, and especially, how the SST structure can be taken into account and utilized.

Preliminaries: Inference under a Fixed Policy

In this section, we briefly introduce how to perform inference on the value function under a fixed policy $\pi$ which is not a new task in the literature, as an important cornerstone. There are two streams of methods, both of which are reliant on the well-known Bellman Equation, i.e.,

The first stream of methods, known as model-based estimation, is detailed in Algorithm (ref). Model-based estimation $\widehat{\bm{V}}^{\textnormal{MB}}$ utilizes the reformulation of the Bellman Equation as ${\bm{V}}^\pi=({\bm{I}}-\gamma{\bm{P}}^\pi)^{-1} {\bm{r}}^\pi$, where ${\bm{I}}$ is the identity matrix. This method estimates ${\bm{V}}^\pi$ by plugging in the estimations of the MDP parameters including ${\bm{r}}^\pi$ and ${\bm{P}}^\pi$. Such an estimation is based on the comprehensive understanding of all model parameters, hence it is termed model-based.

The second methodology, referred to as model-free estimation, is outlined in Algorithm (ref). It directly estimates the value function without estimating the model's parameters. Specifically, for a given tuple $(s_i,a_i,s_{i+1},r_i)$, $r_i+\gamma V(s_{i+1})$ is an unbiased estimation of $V(s_i)$ according to the Bellman Equation. Thus, we obtain the estimator $\widehat{\bm{V}}^{\textnormal{TD}}$ following the well-known least square temporal difference (TD) algorithm, which solves

The two inference algorithms are refereed as Algorithm (ref) and (ref). Despite of the difference in nature, $\widehat{\bm{V}}^{\textnormal{MB}}$ and $\widehat{\bm{V}}^{\textnormal{TD}}$ are actually providing the same point estimation of the value function ${\bm{V}}$ under very mild assumptions.

With such an equivalence, establishing a property for one estimator inherently confirms it for the other. It is important to emphasize that this equivalence does not imply that the model-based approach and TD learning are identical across all scenarios. We are only talking about finite-space and finite-action MDPs without function approximations in this work. There has been a long debate in the RL literature between model-based learning and TD learning, and we refer to the more relevant surveys and textbooks like moerland2023model and Sutton18RL.

Under mild technical conditions, $\widehat {\bm{V}}^{\textnormal{MB}}$ and $\widehat {\bm{V}}^{\textnormal{TD}}$ can be shown to enjoy asymptotic normality.

Here uniform ergodicity is a common technical assumption also used in farias2022markovian,hu2022switchback,jones04CLT and will be specified in Appendix (ref) along with the detailed form of $\Sigma_{\mathrm{MB}}$. While we expected this result to have been established previously in the RL literature, we were unable to locate an exact reference. For completeness, we provide a full proof in Appendix (ref). In addition, we highlight another important result, the asymptotic efficiency of these two classical estimators, which may be of independent interest to the RL literature. Specifically, $\Sigma_{\mathrm{MB}}$ is essentially the smallest variance that can be obtained by any unbiased estimator. The proof is given in Appendix (ref).

A/B Testing on MDPs

In the previous section, we have established the inference results with the trajectory generated by a fixed policy $\pi$. To infer the ATE, however, it is necessary to simultaneously estimate ${\bm{V}}^{\mathfrak{t}}$ and ${\bm{V}}^{\mathfrak{c}}$ from a single trajectory. A commonly employed method for this purpose is A/B testing, where, at any given state $s$, a fair coin flip determines whether to apply $\pi^{\mathfrak{t}}$ or $\pi^{\mathfrak{c}}$. For simplicity, we introduce the experimental policy $\pi^{1/2}$, defined such that $\pi^{1/2}(a\mid s)\coloneqq {1}/{2}\cdot \pi^{\mathfrak{t}}(a\mid s)+{1}/{2}\cdot \pi^{\mathfrak{c}}(a\mid s)$ for any $(s,a)$ pair. Assume that the experimenter executes $\pi^{1/2}$ for $T$ epochs and obtains the trajectory $\tau = \left\{{(s_i,a_i,s_{i+1},r_i)}\right\}_{i\in[T]}$. An example of a realized trajectory might include sequences such as: \[\textcolor{blue}{(s^1, {\mathfrak{t}}, s^3, r_1)}\quad \textcolor{orange}{(s^3, {\mathfrak{c}}, s^3, r_2)} \quad \textcolor{blue}{(s^3, {\mathfrak{c}}, s^1, r_3)} \quad \textcolor{orange}{(s^1, {\mathfrak{c}}, s^2, r_4)} \quad\textcolor{orange}{(s^2, {\mathfrak{c}}, s^4, r_5)} \quad\textcolor{blue}{(s^4, {\mathfrak{c}}, s^5, r_6)} \cdots \] The blue and orange pairs are the observations generated by the treatment policy $\pi^{\mathfrak{t}}$ and the control policy $\pi^{\mathfrak{c}}$, respectively. Given that we are considering the SST, action ${\mathfrak{t}}$ is exclusively available at state $s^1$, while action ${\mathfrak{c}}$ is the only option in all other states, regardless of the policy applied. Without considering the SST structure—that is, treating $\pi^{\mathfrak{t}}$ and $\pi^{\mathfrak{c}}$ as two completely distinct and general policies—a straightforward approach would involve splitting the trajectory $\tau$ into two separate datasets based on the policy implemented at each time step: \[\textcolor{blue}{{\mathcal{D}}^{\mathfrak{t}}_\mathrm{AB}} = \{\textcolor{blue}{(s_i,a_i,s_{i+1}, r_i)}: \pi_i=\pi^{\mathfrak{t}},i\in [T]\}\,,\qquad\textcolor{orange}{{\mathcal{D}}^{\mathfrak{c}}_\mathrm{AB}} = \{\textcolor{orange}{(s_i,a_i,s_{i+1}, r_i)}: \pi_i =\pi^{\mathfrak{c}}, i\in [T]\}\,, \] where $\pi_i$ denotes policy used at time $i$. Leveraging the Markov property of the system, unbiased estimations of ${\bm{V}}^{\mathfrak{t}}$ and ${\bm{V}}^{\mathfrak{c}}$ can be derived from ${\mathcal{D}}^{\mathfrak{t}}$ and ${\mathcal{D}}^{\mathfrak{c}}$ respectively, using either Algorithm (ref) or Algorithm (ref). The corresponding algorithm is outlined in Algorithm (ref). Although the idea is straightforwards, the estimator can perform in our desired way. More specifically, we can establish the asymptotic normality.

The term $\rho^\pi_{s^1}(s)$ is also called the discounted state-visitation measure defined and widely used in the RL literature (Agarwal2019ReinforcementLT). The asymptotic variance $\sigma_{\mathrm{AB}}^2(s^1)$ is influenced not only by the state $s^1$ itself but also by all the other states. This is consistent with our understanding that our objective is the long-term value and the samples are drawn from an MDP. Although the variance depends on all states, we want to specially highlight that $\sigma^2_{\mathrm{AB}}(s^1)$ can be divided into two groups: one associated exclusively with $\pi^{\mathfrak{t}}$ and the other with $\pi^{\mathfrak{c}}$. Each group has $|{\mathcal{S}}|$ distinct terms, where each term corresponds almost exclusively to one state. Furthermore, each term is inversely proportion to the stationary probability $\mu_{1/2}(s)$. This implies that states which are less frequently visited pose greater challenges in sampling, potentially leading to increased variance. Additionally, each term has two parts, $\sigma_\pi^2(s)$ and $\left\|{\gamma{\bm{V}}^\pi}\right\|_{\Sigma_{p^\pi(s)}}^2$, which correspond to the (short-term) variance of the instant rewards and the (long-term) variance related to transitions to the other states.

Finally, we want to remind that Theorem (ref) is applicable for any general $\pi^{\mathfrak{t}}$ and $\pi^{\mathfrak{c}}$. Our approach segments the trajectory solely based on whether the policy $\pi^{\mathfrak{t}}$ or $\pi^{\mathfrak{c}}$ is used at each step, independent of what exactly $\pi^{\mathfrak{t}}$ and $\pi^{\mathfrak{c}}$ are. Consequently, this estimator can be readily extended to estimate ATE for a broader range of treatment policies $\pi^{\mathfrak{t}}$, beyond those confined to SST.

Variance Lower Bound for General A/B Testing on MDPs

In this subsection, we demonstrate that if we ignore the structure of SST, or if the treatment does not adhere to SST principles at all, then the asymptotic variance $\Sigma_{\textrm{AB}}$ given in Theorem (ref) is almost optimal for any unbiased estimator of the ATE ${\bm{\Delta}}$. The proof is delayed to Appendix (ref).

This lower bound effectively implies that asymptotic variance of A/B testing cannot be further reduced under general treatment pattern. In recent literature, farias2022markovian derive a similar efficiency result for a similar unbiased A/B testing approach on average-reward MDPs. Their ATE is defined as the difference between average rewards for $\pi^{\mathfrak{t}}$ and $\pi^{\mathfrak{c}}$, i.e. ${\bm{\mu}}^{{\mathfrak{t}}^\top}{\bm{r}}^{\mathfrak{t}} - {\bm{\mu}}^{{\mathfrak{c}}^\top}{\bm{r}}^{\mathfrak{c}}$. Compared to theirs, our study further incorporates reward variance. From a technical perspective, we employs a distinct proof framework via the constrained Cramér-Rao bound.

Variance Reduction: Information Sharing between Test Arms

In this section, we explore how the structure of SST can be leveraged to reduce variance. The underlying principle is that, thanks to the Markov property, the state transitions and reward signals of states $s_t\ne s^1$ can be shared across different test arms. To illustrate this, let us revisit the trajectory in Section (ref). Although $(s^3,{\mathfrak{c}},s^3,r_2)$ is generated by $\pi^{\mathfrak{c}}$, it can also be seen as having been generated by $\pi^{\mathfrak{t}}$ since $\pi^{\mathfrak{t}}(s^3)=\pi^{\mathfrak{c}}(s^3)={\mathfrak{c}}$. This observation suggests a potential strategy to use such samples for estimating both ${\bm{V}}^{\mathfrak{t}}$ and ${\bm{V}}^{\mathfrak{t}}$. Consequently, we recolor the trajectory with additional purple on the samples that can be shared between the two policies. \[\textcolor{blue}{(s^1, {\mathfrak{t}}, s^3, r_1)}\quad \textcolor{purple}{(s^3, {\mathfrak{c}}, s^3, r_2)} \quad \textcolor{purple}{(s^3, {\mathfrak{c}}, s^1, r_3)} \quad \textcolor{orange}{(s^1, {\mathfrak{c}}, s^2, r_4)} \quad\textcolor{purple}{(s^2, {\mathfrak{c}}, s^4, r_5)} \quad\textcolor{purple}{(s^4, {\mathfrak{c}}, s^5, r_6)} \cdots \] Accordingly, we can construct two datasets,

Applying either Algorithm (ref) or Algorithm (ref) on the datasets ${\mathcal{D}}^{\mathfrak{t}}_\textrm{IS}$ and ${\mathcal{D}}^{\mathfrak{c}}_\textrm{IS}$ yields two new estimators $\widehat{\bm{V}}^{\mathfrak{t}}_{\textrm{IS}}$ and $\widehat{\bm{V}}^{\mathfrak{c}}_{\textrm{IS}}$ respectively. Subsequently, the estimator for ATE, denoted as $\widehat {\bm{\Delta}}^\mathrm{IS}$, is calculated as $\widehat{\bm{V}}^{\mathfrak{t}}_{\textrm{IS}}-\widehat{\bm{V}}^{\mathfrak{c}}_{\textrm{IS}}$. We will always use “IS" to denote information sharing.

To assess whether information sharing can effectively reduce the variance, we first derive the central limit theorem with the information sharing. The full proof is delayed to Appendix (ref).

Analysis of Variance Reduction with Two Test Arms

In this subsection, we dive into the comparison between the asymptotic variance of general A/B testing derived in Theorem (ref) and that of A/B testing with information sharing in Theorem (ref). For simplicity, we restrict our focus to the crucial state $s^1$. Decomposing the variance based on whether the state is the crucial state or not, we can reorganize the asymptotic variance of A/B testing in Theorem (ref) as

The $\Sigma^{\mathrm{het}}_{\mathrm{AB}}$ part is the variance directly related to the crucial state $s^1$, and the superscript het reflects that state $s^1$ is the only state where $\pi^{\mathfrak{t}}$ and $\pi^{\mathfrak{c}}$ may be heterogeneous under SST. The $\Sigma^{\mathrm{hom}}_{\mathrm{AB}} $ part represents the variance associated with all other states $s\ne s^1$ where $\pi^{\mathfrak{t}}$ and $\pi^{\mathfrak{c}}$ are homogeneous. We want to remind that under SST, the variances $\sigma^2_{\mathfrak{t}}(s)$ and $\sigma^2_{\mathfrak{c}}(s)$ are the same for all the other state $s$ except the crucial state $s^1$.

Similarly, we can decompose the asymptotic variance of information sharing, $\sigma_{\mathrm{IS}}^2(s^1)$, in the same fashion,

The above decomposition demonstrates clear structures of asymptotic variance of both estimators. Formally, the following Theorem (ref) compares $\sigma_{\mathrm{AB}}^2(s^1)$ and $\sigma_{\mathrm{IS}}^2(s^1)$.

Theorem (ref) reveals that IS achieves at least an equivalent level of performance to the general A/B testing in terms of asymptotic variance. It aligns with our intuition that the variances associated with $s^1$ remain unchanged, as information sharing is not feasible in state $s^1$ due to the potential differences in the transition matrix and rewards. Consequently, the observed reduction in variance primarily results from the sharing of information across all other states $s\ne s^1$. We would like to highlight that, interestingly, each term of the sum in $\Sigma^{\mathrm{hom}}_{\mathrm{IS}}$ can be directly related to each term of the sum in $\Sigma^{\mathrm{hom}}_{\mathrm{AB}}$ through two Cauthy-Schwarz inequalities. More specifically, for any $s\ne s^1$,

where the sum of LHS over $s\ne s^1$ constitutes the $\Sigma^{\mathrm{hom}}_{\mathrm{IS}}$ and the sum of RHS forms $\Sigma^{\mathrm{hom}}_{\mathrm{AB}}$. Such a claim leading to the inequality in \Eqref{eq: VR-Compare}. To achieve equality in $\Sigma^{\mathrm{hom}}_{\mathrm{IS}}\le\Sigma^{\mathrm{hom}}_{\mathrm{AB}}$, the two Cauthy-Schwarz inequalities above must be equal for all $s\ne s^1$, which seems to be highly restrictive. In fact, Proposition (ref) presents the necessary condition for the equality to hold.

The proof is delayed to Appendix (ref). This proposition effectively implies that for the equality to hold: either the MDP is trivial with fixed zero reward at every state, or the discounted state visitation measure has to satisfy linear dependence before and after the treatment.

More importantly, we want to highlight that if the new treatment ${\mathfrak{t}}$ is identical to the control ${\mathfrak{c}}$ such that for all states $s$, $\rho^{\mathfrak{t}}_{s^1}(s)=\rho^{\mathfrak{c}}_{s^1}(s)$ and ${\bm{V}}^{\mathfrak{t}}={\bm{V}}^{\mathfrak{c}}$, the term $\Sigma^{\mathrm{hom}}_{\mathrm{IS}}$ will be zero. In contrast, $\Sigma^{\mathrm{hom}}_{\mathrm{AB}}$ is a value that can be strictly large than zero. This finding is particularly relevant in contexts like A/A testing. Such an observation is somewhat surprising. With information sharing, the amount of data used to estimate the transition probabilities and the rewards can be thought to be doubled, and thus it seems reasonable to conjecture that IS can at most reduce $\Sigma^{\mathrm{hom}}_{\mathrm{AB}}$ to a half, i.e., $\Sigma^{\mathrm{hom}}_{\mathrm{IS}}\ge \frac{1}{2} \Sigma^{\mathrm{hom}}_{\mathrm{AB}}$. However, with the example of A/A testing, the conjecture may not always hold true, suggesting that $\Sigma^{\mathrm{hom}}_{\mathrm{IS}}$ could sometimes be significantly smaller than $\Sigma^{\mathrm{hom}}_{\mathrm{AB}}$.

Variance Lower Bound for Experimentation with SST

In this subsection, we show that IS, though intuitive and simple, is the optimal way to harness treatment locality for consistent A/B testing. Specifically, we present the variance lower bound of any unbiased estimator taking the SST structure into account, which reflects the intrinsic difficulty of A/B testing with SST.

Theorem (ref) indicates that our estimator $\widehat {\bm{\Delta}}^\mathrm{IS}$ is asymptotically efficient. While Theorem (ref) highlights that IS does not reduce the variance associated with the crucial state $s^1$, Theorem (ref) affirms that this variance is, in fact, optimal and fundamental.

(More) Power of IS with Multiple Test Arms

In previous sections, we have shown that IS can do at least as well as A/B testing with two test arms. A practical experiment often contains more than two test arms, such as A/B/n Testing (Kohavi_Tang_Xu_2020, russac2021b) or bandit experiments (david23multi). In this subsection, we generalize our study of the variance reduction of IS to SST with more than two test arms and show that IS becomes even more powerful in reducing the variance comparing with traditional A/B/n testing. For rigor, we start with the definition of SST with $n$ test arms.

Consider an MDP with state space ${\mathcal{S}}\coloneqq\left\{{s^i}\right\}_{i\in [K]}$, where $s^1$ is still assumed to be the crucial state of treatment. Unlike the previous model in Section (ref) with two test arms, the action set ${\mathcal{A}}=\left\{{{\mathfrak{t}}^j}\right\}_{j\in[n]}$ now includes $n$ possible actions. Without loss of generality, we let ${\mathfrak{t}}^1$ denote the control action. Recall Example (ref), a plausible experiment might involve the company testing multiple coupon values to determine which one maximizes customer lifetime value. This implies $n$ SST polices $\Pi\coloneqq\left\{{\pi^i}\right\}_{i\in[n]}$ with each $\pi^i$ satisfying: $\pi^i(s^1)\equiv {\mathfrak{t}}^i$ (i.e., $\pi^i({\mathfrak{t}}^i \mid s^1)=1$) and $\pi^i(s)\equiv {\mathfrak{t}}^1$ (i.e., $\pi^i({\mathfrak{t}}^1 \mid s)=1$) for all $s\in{\mathcal{S}}\setminus s^1$. Additionally, each SST policy is associated with its own transition matrix ${\bm{P}}^{{\mathfrak{t}}^i}$ and mean reward ${\bm{r}}^{{\mathfrak{t}}^i}$.

The primary objective of experimentation in such a setting is to understand the long-term outcome differences among various test arms. Formally, for any pair of SST polices $(\pi^{i}, \pi^{j})_{i,j\in[n]}$, we define the ATE as $\Delta_{i,j} (s)= V^{i}(s)-V^{j}(s)$, for given state $s\in{\mathcal{S}}$. For simplicity, throughout this subsection, we restrict our interest to $\Delta_{i,j} (s^1)$, the ATE under the crucial state $s^1$. For A/B/n testing, the experimental policy becomes $\pi^{1/n}(a\mid s)\coloneqq \frac{1}{n}\sum_{i\in[n]}\pi^{i}(a\mid s)$ for any $(s,a)$ pair, meaning that we apply each policy in $\Pi$ with equal probability.

After collecting data, the traditional A/B/n testing would split the trajectory according to different polices and obtain dataset ${\mathcal{D}}^{j}_{\mathrm{ABn}}\coloneqq\{(s_i,a_i,s_{i+1}, r_i):\pi_i=\pi^j, i\in [T]\}$ for each policy $\pi^j$. With information sharing, the observations with $s_i\ne s^1$ among all $n$ test arms can be shared for all SST polices $\pi$. Then, IS yields the corresponding dataset ${\mathcal{D}}^{j}_{\mathrm{ISn}}\coloneqq\{(s_i,a_i,s_{i+1}, r_i):(s_i,a_i)\ne (s^1, {\mathfrak{t}}^k), \forall k\ne j, i\in [T]\}$ for each policy $\pi^j$. Applying Algorithm (ref) or Algorithm (ref) to fit ${\bm{V}}^j$ with ${\mathcal{D}}^{j}_{\mathrm{ABn}}$ and ${\mathcal{D}}^{j}_{\mathrm{ISn}}$ respectively can produce two estimators $\widehat {\bm{V}}^{\textnormal{ABn}}_j$ and $\widehat {\bm{V}}^{\textnormal{ISn}}_j$. The estimators for the treatment effect become $\widehat {\bm{\Delta}}_{i,j}^{\textnormal{ABn}}=\widehat {\bm{V}}^{\textnormal{ABn}}_i-\widehat {\bm{V}}^{\textnormal{ABn}}_j$ and $\widehat {\bm{\Delta}}_{i,j}^{\textnormal{ISn}}=\widehat {\bm{V}}^{\textnormal{ISn}}_i-\widehat {\bm{V}}^{\textnormal{ISn}}_j$. The following Corollary (ref) generalizes Theorems (ref) and (ref) revealing the asymptotic normality of these two estimators on the crucial state $s^1$.

We ensure that the both two estimators $\widehat \Delta_{i,j} ^{\mathrm{ABn}}(s^1)$ and $\widehat \Delta_{i,j} ^{\mathrm{ISn}}(s^1)$ enjoy the asymptotic normality, but with different asymptotic variances. Similar as before, the variance can be decomposed according to states. Theorem (ref) below characterizes the variance reduction of IS for multiple test arms demonstrating the more power that IS has when facing multiple test arms.

This result underscores the effectiveness of IS in leveraging the structure of SST to significantly reduce the variance compared to traditional A/B/n testing. Particularly, we demonstrate that the variance associated with all other states $s \ne s^1$, where the control policy is always employed, can be reduced at least linearly with the number of test arms. Thus, the more test arms we have, the greater the reduction in variance achieved by IS. When $n=2$, Theorem (ref) replicates the findings of Theorem (ref). When $n\ge 3$, Theorem (ref) consistently ensures a substantially reduced variance. Remarkably, with $n\ge 4$, IS is expected to cut the variance associated with the non-crucial states by at least half. Similar to Theorem (ref), the variance associated with crucial state $s^1$ is the same as A/B/n testing, as information about this state cannot be shared. Additionally, the equality condition in the inequality of \Eqref{eq: VR_n_arm} remains as elusive as before, largely because one necessary condition for equality is the absence of noise in the observed rewards.

From SST to Local Treatment

In practice, a local treatment policy may affect more than a single state. Consequently, we generalize the SST concept to accommodate Local Treatment. In this expanded framework, a treatment action is applied to a specific segment of the state space rather than a single state. This approach allows for a more flexible and realistic modeling of interventions in complex MDPs. To illustrate, recall Example (ref). The company now wants to test a new strategy: posting advertisements to customers when their recency is relatively high—for instance, when it exceeds 2. Such a treatment policy is a Local Treatment, as it is applied only to a specific segment ($s^3,s^4,s^5$) of the state space. The remaining states ($s^1,s^2$), representing lower recency, are not subject to this treatment.

We then establish the model for Local Treatment. Specifically, there exists a pre-determined “crucial" subset ${\mathcal{S}}^{\mathfrak{t}}\subseteq {\mathcal{S}}$. The treatment policy $\pi^{\mathfrak{t}}$ and control policy $\pi^{\mathfrak{c}}$ will only vary at state $s\in{\mathcal{S}}^{\mathfrak{t}}$. Formally, we define

Notice that when the size of the crucial subset $|{\mathcal{S}}^{\mathfrak{t}}|=1$, we recover the definition of SST. The average treatment effect ${\bm{\Delta}}$ follows the same definition as section (ref).

Having demonstrated the effectiveness of IS for variance reduction under SST, we can now extend these results to Local Treatment scenarios. It can be expected that we are able to establish similar results to Theorem (ref), (ref). Compared to SST, the heterogeneous part of the system becomes a subset ${\mathcal{S}}^{\mathfrak{t}}$ instead of the single just state $s^1$. As a result, we can only share information of state $s\in {\mathcal{S}}\setminus {\mathcal{S}}^{\mathfrak{t}}$. The following theorem characterizes this extension from SST.

Recall in SST, $\Sigma_{\Gamma}^{\mathrm{het}}$ is associated with the single crucial state $s^1$, while now we generalize it to the crucial subset ${\mathcal{S}}^{\mathfrak{t}}$. For the asymptotic relative efficiency of three estimators, we then have the following generalization of Theorem (ref).

Theorem (ref) replicates Theorem (ref). The difference is that now we generalize $\Sigma_{\Gamma}^{\mathrm{het}}$ to variance associated with the crucial subset ${\mathcal{S}}^{\mathfrak{t}}$ rather than single crucial state $s^1$ in SST. This demonstrates that the effectiveness of IS diminishes as the number of states that can share information (i.e. the homogeneous part) decreases. In the extreme case of a general treatment where ${\mathcal{S}}^{\mathfrak{t}}={\mathcal{S}}$, meaning all states are treated and no states to share information, IS will reduce to A/B testing. Finally, we can derive a similar generalization to local treatment with multiple test arms as Theorem (ref). We delay the details to the Appendix (ref).

Information Sharing Always Improves Efficiency for Differentiable Estimators

In the previous sections, we have established the optimal asymptotically unbiased estimators for local treatments in MDPs. In practice, however, decision-makers can have many other design choices. For example, a slight bias may be acceptable if it substantially reduces variance. Moreover, beyond long-term cumulative outcomes, practitioners may also be interested in other long-term treatment effects, such as average or point outcomes. This raises a fundamental question: does information sharing always improve performance regardless of the estimating approach or estimand? To address this, we introduce a broad class of estimators, differentiable estimators, which includes many widely used methods and, importantly, always benefits from information sharing.

Differentiable Estimators

We now define the differential estimators in the vanilla A/B testing without information sharing. For any piece of data we collect $X_i=(s_i,a_i, s_{i+1}, r_i)$ and $a\in \{{\mathfrak{t}},{\mathfrak{c}}\}$, we denote

where ${\bm{E}}_{s_i,s_{i+1}}\in\mathbb{R}^{n\times n}$ is a matrix with all entries equal to zero except for a one at the $(s_i,s_{i+1})$ entry and ${\bm{e}}_{s_i}\in\mathbb{R}^n$ is the standard basis vector with a one in the $s_i$-th position and zeros elsewhere. Using these definitions, we can have the IPW estimators for $\operatorname{Diag}({\bm{\mu}}_{1/2}) {\bm{P}}^a$ and $\operatorname{Diag}({\bm{\mu}}_{1/2}){\bm{r}}^a$,

Note that although our previous ATE $\Delta$ is defined as the difference between two value functions, the estimand ${\bm{\Delta}}^{\mathrm{AB}}$ of differentiable estimator $\widehat{{\bm{\Delta}}}^{\mathrm{AB}}$ can be more general. It can also represent, for example, the difference in average rewards, the difference in finite-horizon rewards, or even the difference in advantage functions. Moreover, the function $f$ need not yield unbiased estimators, and we impose no restrictions beyond differentiability.

Furthermore, we highlight that Definition (ref) and \Eqref{eq: general est} subsumes many existing and widely used estimators for MDPs, including:

This demonstrates that our framework provides a unifying perspective on several strands of the recent literature.

Variance Reduction for Differentiable Estimators

Applying the information-sharing idea to differentiable estimators, we again observe a linear reduction in variance for the non-treated states, without introducing additional bias. For clarity, we focus on the SST case, and the extension to general local treatments follows naturally. In particular, information sharing modifies the estimation of model parameters at every state except $s^1$. In particular, for $X_i=(s_i,a_i, s_{i+1},r_i)$ and $a\in \{{\mathfrak{t}},{\mathfrak{c}}\}$, we have

And similarly, we denote $\overline{ {\bm{K}}^a_\mathrm{IS}} \coloneqq \frac{1}{T}\sum_{i=1}^T {\bm{K}}^a(X_i)$ and $ \overline{{\bm{R}}^a_\mathrm{IS}} \coloneqq \frac{1}{T}\sum_{i=1}^T {\bm{R}}^a(X_i)$. Finally, we plug in the estimators into the same $f$ and obtain our information sharing estimator, \[\widehat{{\bm{\Delta}}}^{\textrm{IS}}=f(\overline{ {\bm{K}}^{\mathfrak{t}}_\mathrm{IS}},\overline{ {\bm{K}}^{\mathfrak{c}}_\mathrm{IS}},\overline{{\bm{R}}^{\mathfrak{t}}_\mathrm{IS}},\overline{{\bm{R}}^{\mathfrak{c}}_\mathrm{IS}})\,.\] An immediate observation is that both $\overline{ {\bm{K}}^a_\mathrm{IS}}$ and $\overline{ {\bm{K}}^a_\mathrm{AB}}$ converge almost surely to $\operatorname{Diag}({\bm{\mu}}_{1/2}) {\bm{P}}^a$ for $a\in \{{\mathfrak{t}},{\mathfrak{c}}\}$. Similarly, $\overline{{\bm{R}}^a_\mathrm{IS}}$ and $\overline{{\bm{R}}^a_\mathrm{AB}}$ converge almost surely to $\operatorname{Diag}({\bm{\mu}}_{1/2}){\bm{r}}^a$. Since $f$ is differentiable (and thus continuous), ${\bm{K}}^a_\mathrm{AB}(X_i)$ and ${\bm{K}}^a_\mathrm{IS}(X_i)$ have exactly the same asymptotic bias. More formally, and of greater importance, we have the following variance analysis.

Following Theorem (ref), the term $\Sigma^{\mathrm{het}}_{\Gamma}$ captures the variance associated with the non-treated states, while $\Sigma^{\mathrm{hom}}_{\Gamma}$ reflects the variance of the state targeted by the SST. The new term introduced here is $\Sigma^{\mathrm{cov}}_{\Gamma}$, which represents the covariance across time. Because the system operates under an MDP, future states depend on the past states and actions. Compared with Theorem (ref), we can learn that selecting an appropriate functional form of $f$ can eliminate temporal correlation.

For general estimators to A/B/n testing, we can also rigorously show that information sharing can linearly reduce part of the variance. The asymptotic variance can be similarly decomposed as $\Sigma_\Gamma(i,j)=\Sigma^{\mathrm{het}}_\Gamma(i,j) + \Sigma^{\mathrm{hom}}_\Gamma(i,j)+\Sigma^{\mathrm{cov}}_\Gamma(i,j)$ where

We defer the formal statement and proofs to Appendix (ref).

Simulations

Synthetic Data: Customer Lifetime Value

We revisit the example of customer lifetime value (Example (ref)), with a synthetic transition matrix detailed in Appendix (ref). We assume that under the control policy, when the customer makes a purchase, the company will receive a net income of $30$ while the income in all other states is $0$. Specifically, the transition matrix and the reward under the control policy are set as follows. \[{\bm{P}}^{\mathfrak{c}}=

\,,\qquad {\bm{r}}^{\mathfrak{c}}=

\,.\]

We consider the following two types of treatment:

We additionally introduce another benchmark for comparison, called perfect information (PI), where the decision-makers have the access to the perfect information of the control arm. The PI estimators can always serve as the lower bound of the variance (i.e., the necessary variance). The detailed description of the PI estimators and their properties are provided in Appendix (ref).

We run experiments for each candidate value under both cases treatment possible values, aiming to identify the optimal coupon value which are 4 and 2. In each experiment, we run all three estimators over 1,000 independent trajectories and record their empirical mean and standard error. The experiment horizon is adjusted so that the IS estimator's standard error is smaller than its empirical mean. In Figure (ref), we present the simulation results.

\noindentUnbiasedness across all estimators: The empirical means for all three estimators in both experiments demonstrate negligible bias. This aligns with our theoretical results of the consistency of all three estimators.

\noindentVariance reduction by IS: In both examples, we observe a significant reduction in variance by at least half through the application of IS. The variance of IS is closer to the variance provided by PI. This illustrates the effectiveness of IS in overcoming the lower bound of original A/B testing by utilizing the local structure. Also, the more states the information can be shared, the closer the variance of IS estimator is to the PI estimator.

While ATEs in both experiments are close, the local treatment case requires a substantially longer horizon for the standard error of IS estimator to decay comparing with the SST case. This discrepancy aligns with the intuition that the SST allows information sharing for more states than the local treatment case. This observation showcases that the efficacy of IS increases with the number of shared states.

A Real-World Sepsis Simulator

To evaluate our method in a more realistic setting, we employ a simulator of sepsis treatment for intensive care unit (ICU) patients (komorowski2018artificial,oberst2019counterfactual, tran2023inferring). Our focus is on experimenting with various combinations of treatments applicable to patients in critical conditions. The primary objective is to understand the long-term effects of these treatment strategies.

The Environment: The physiological status of patients can be captured by a underlying MDP. The state space encompasses discrete measurements of vital signs (heart rate, blood pressure, oxygen concentration, and glucose levels), categorized into levels (e.g., low, normal, high), along with records of previous treatments. The size of the state space size 720. The reward function assigns values of -1, 0, or +1 based on the number of abnormal vital signs exhibited by a patient. In the absence of treatment intervention, patient signals fluctuate according to specified transition probabilities, reflecting the dynamic nature of the health condition.

The Local Treatment: When patients enter a critical state—characterized by all signals being abnormal—three treatment options become available: antibiotics, vasopressors, and mechanical ventilation. This results in $n=8$ test arms, corresponding to the possible combinations of these treatments. The application of these interventions alters the transition probabilities of the various signals. In our experimental setting, the total number of treated states amounts to 128, representing approximately 18% of the overall state space.

The Simulation: Unlike the previous synthetic example, real-world constraints limit our ability to conduct extended experiments on one individual patient. Instead, we adopt a common practice in sepsis studies: assuming patients with similar contexts follow the same MDP. We pool observation data from a group of non-diabetic patients to estimate the average long-term effect of treatments. Our simulator generates observed trajectories of length 100 for each patient. These patients are initialized according to a state distribution learned a priori.

We run the simulations for $N=250$ patients over $100$ independent runs and then demonstrate the inference results of each estimators. We additionally introduce two more benchmarks, the Naive and Difference-in-Q (DQ) estimators, from farias2022markovian, which is originally designed for the general treatment policies on MDPs with two test arms. For the Naive estimators, we naively take the average on the rewards collected under the treatment policy and the control policy, ignoring the interference of state transitions. The DQ estimator strikes a balance between bias and variance under general and global treatment policies in MDPs. In Appendix (ref), we generalize the DQ theory and provide the expression of DQ estimator for multiple test arms.

Figure (ref) summarizes the simulation results as well as the Mean Square Error (MSE) curve with the number of patients. We have the following observations.

\noindentVariance Reduction of IS: We observe a significant reduction in variance through the application of IS while still obtaining negligible bias comparing with the A/B testing estimator. The variance of IS is even close to the PI estimator. The IS and PI estimators also enjoy fast decay of MSE compared to all other estimators. This confirms the effectiveness of IS and demonstrates the power of leveraging treatment structure to obtain striking efficiency improvement.

\noindentUnbiasedness of IS: Although the Naive estimator has smaller variance than IS, its bias is non-negligible. Furthermore, the Naive estimator struggles to exclude the null effect, potentially resulting in insufficient statistical power. In contrast, the IS and PI estimators are centered around the true ATE.

\noindentDQ exhibits bias-variance trade-offs: DQ demonstrates a notable bias-variance trade-off when compared to A/B testing and Naive estimators. DQ achieves variance reduction at the cost of introducing small bias, resulting in a faster decay of MSE. However, DQ fails to leverage the inherent local structures of the treatments, leading to significantly higher MSE compared to IS and PI. As we have discussed that DQ belongs to the general differentiable estimators, we can expect that Is can improve performance over the original DQ formulation.

Discussion

Fairness and Welfare: The Monotonicity of SST

MDPs are complex systems with interconnected states. Therefore, out of fairness and welfare concern, it would be the best for the decision-makers to ensure that a new treatment improves long-term outcomes for customers across all states, rather than benefiting some at the expense of others. Fortunately, we have a theorem that guarantees the “monotonicity" of SST policies.

This ensures that the treatment effect remains consistently positive (or negative) for all states before and after the intervention. Furthermore, when the treatment effect is negative, all states except the crucial state will experience a welfare loss strictly less than $\gamma \Delta(s^1)$, where $\gamma\in[0,1)$ is the discount factor. Notably, this monotonicity theorem holds true regardless of the underlying Markov chain's structure.

Technically, we provide two different proofs for Theorem (ref) in Appendix (ref). The first proof is based on an important observation that the treatment effect ${\bm{\Delta}}$ is an eigenvector of a special matrix associated with the transition probability under the control policy. The second proof offers another perspective to characterize ${\bm{\Delta}}$ using the advantage function, derived from the well-knwon Performance Difference Lemma (Kakade2002ApproximatelyOA, Agarwal2019ReinforcementLT) in RL theory. We believe these techniques may be of independent interest to the RL literature.

Other Applications of Information Sharing

While this paper has mainly focused on A/B testing on a non-episodic MDP under the tabular setting, we believe it's interesting directions to extend our framework to various other RL settings. \newline\noindentFunction Approximations. Modern practical reinforcement learning often faces the curse of dimensionality, i.e. a prohibitively large or infinite state space. This may render our previous tabular methods of fitting value functions unrealistic. However, one can resort to any estimation methods designed for function approximation while still leveraging the information sharing idea. For example, consider a parameterized class of value functions $V_{\Theta}=\{V_{{\bm{\theta}}}\colon {\bm{\theta}}\in\Theta\}$, where common function approximations include linear (tsitsiklis96analysis,jalaj21afinite) or neural networks (cai19neural). Given a trajectory $\tau = \{(s_i,a_i,s_{i+1}, r_i)\}_{i\in[T]}$, typical TD algorithms solve \[{\bm{\theta}} = \argmin_{{\bm{\theta}}\in\Theta} \sum_{s\in{\mathcal{S}}} \left({\sum_{s_i=s} r(s_i,a_i)+\gamma V_{{\bm{\theta}}}(s_{i+1})- V_{{\bm{\theta}}}(s_i) }\right)^2,\] which can be viewed as a parameterized version of \Eqref{eq: LSTD}. When it comes to A/B testing, it's then evident that one can split trajectories to fit the value function by solving this optimization problem. Additionally, information can still be shared for local treatments, allowing the construction of richer datasets and improving efficiency. \newline\noindentEpisodic Setting. Another commonly used framework is the episodic MDP. In this scenario, multiple independent samples of the MDP can be obtained. In section (ref), each patients can be viewed as one such independent MDP. We thus empirically demonstrate that IS is also effective for episodic MDPs and brings about substantial variance reduction. We leave it to future work to derive rigorous theoretical guarantees for information sharing under episodic MDPs. \newline\noindentPolicy Optimization. Most RL literature on finding optimal policy (e.g. azar2017minimax,jin2018qlearning,li2024q) does not impose structural assumption on the action set. Given our modeling of treatment locality, a natural question is whether this structure can also be leveraged to improve the sample efficiency for policy optimization.

Concluding Remarks

This paper systematically explores how treatment structure can be utilized to improve the estimation of life-time effects. By exploiting treatment locality, our proposed estimators achieve substantial variance reduction, linear in the number of test arms, without sacrificing unbiasedness. We further show that a broad class of differentiable estimators can universally benefit from information sharing. These results not only establish new theoretical benchmarks but also highlight the practical value of local interventions for efficient experimentation in dynamic systems.

Finally, we want to highlight the trade-off between Robustness and Efficiency. The efficiency gain from information sharing relies heavily on the local structure of the new treatment. If the new local treatment on some states also influences transitions and rewards of the other states, our information sharing approach could introduce bias. In contrast, the inference methods that do not utilize the local structure, as introduced in Section (ref), are always robust and valid, though potentially at the cost of reduced efficiency.

\ECSwitch

Notation

Let ${\bm{e}}_i\in\mathbb{R}^n$ be a vector with all entries 0 but $i$-th entry 1 and ${\bm{E}}_{ij}\in\mathbb{R}^{n\times n}$ be a matrix with all elements 0 but $i,j$-th element 1. For any vector $x$ and matrix ${\bm{A}}$, the matrix norm $\|x\|_{\bm{A}}\coloneqq \sqrt{x^\top {\bm{A}} x}\,.$ For any matrix ${\bm{A}}=({\bm{a}}_1,{\bm{a}}_2,\ldots,{\bm{a}}_n)\in \mathbb{R}^{m\times n}$, we define the vectorization operator \[\operatorname{vec} ({\bm{A}})\coloneqq

\in\mathbb{R}^{mn}\] as the concatenation of its columns.

Fixed Policy Evaluation Algorithms

We formally give the two policy evaluation algorithms for reference.

Proofs of Asymptotic Normality

In this section, we will discuss the proof framework for asymptotic normality on Markov chains. We will start with the warm-up from of fixed policy inference in Proposition (ref). Then for A/B testing, we will directly prove Theorem (ref) for general differentiable estimators, which implies the results for unbiased estimators in Theorem (ref) and (ref).

Proof of Proposition (ref)

We introduce the following technical assumption on Markov chain, which is commonly used in literature (e.g. farias2022markovian,hu2022switchback,jones04CLT).

Now we present the detailed version of Proposition (ref).

\paragraph{Step 1: Markov Chain CLT} To start with, for $X_i=(s_i,a_i, s_{i+1}, r_i)$, define

And denote

We also have$ \overline{ K_T} \xrightarrow{a.s.} {\bm{K}}_{{\bm{\mu}}^{\pi}} \coloneqq \operatorname{Diag}_{s\in{\mathcal{S}}}({{\bm{\mu}}^{\pi}}(s)) {\bm{P}}^\pi$ and $ \overline{R_T} \xrightarrow{a.s.} {\bm{r}}_{{{\bm{\mu}}^{\pi}}} \coloneqq \operatorname{Diag}_{s\in{\mathcal{S}}}({{\bm{\mu}}^{\pi}}(s)){\bm{r}}^\pi$. Then by Markov CLT in Lemma (ref) it holds \[\sqrt{T}\left({

-

}\right)\xrightarrow{d} {\mathcal{N}}({\bm{0}}, \Sigma)\,,\]for some covariance matrix $\Sigma$.

\paragraph{Step 2: Delta Method} To estimate $\widehat {{\bm{P}}^\pi}$, notice that $\widehat {{\bm{P}}^\pi}_{ij} = \overline{K_T}(i,j)/(\sum_k \overline{K_T}(i,k))$. Then $\widehat {{\bm{P}}^\pi}$ is actually a function of $\overline{K_T}$. Similarly, to estimate $\widehat {{\bm{r}}^\pi}$, we have $\widehat {{\bm{r}}^\pi}(i) = \overline{R_T}(i)/(\sum_k \overline{K_T}(i,k))$. Recall the model-based estimation, we have $\widehat{\bm{V}}^{\mathrm{MB}} = ({\bm{I}}-\widehat {{\bm{P}}^\pi})^{-1}\widehat {{\bm{r}}^\pi} = g(\overline{ K_T}, \overline{R_T})$. We then apply delta method and obtain \[\sqrt{T}(g(\overline{ K_T}, \overline{R_T}) - g({\bm{K}}_{{\bm{\mu}}^{\pi}}, {\bm{r}}_{{\bm{\mu}}^{\pi}}))\xrightarrow{d}{\mathcal{N}}({\bm{0}}, \nabla g^\top \Sigma \nabla g)\,.\]

\paragraph{Step 3: Linearization} In general, $\Sigma$ is hard to compute. We thus apply the linearization technique introduced in farias2022markovian. Specifically, define the linearized part

Then by Lemma (ref), we have \[\mathrm{Var}\left({\frac{1}{T}\sum_{i=1}^TG(X_i)}\right) = \nabla g^\top \Sigma \nabla g\,.\] It's easy to see that the Linear-Reward as \[\sum_{a=1}^n \left.\frac{\partial g}{\partial R(a)} \right\vert_{{\bm{K}}_{{\bm{\mu}}^{\pi}}, {\bm{r}}_{{\bm{\mu}}^{\pi}}} R(X_i)(a) = ({\bm{I}}-\gamma {\bm{P}}^\pi)^{-1}\operatorname{Diag}_{s\in{\mathcal{S}}}(1/{{\bm{\mu}}^{\pi}}(s))R(X_i)\,.\] For the Linear-Transition term, it holds

Then we have

It remains to compute $\Sigma_G$. Note that $\mathbb{E}\left[{G(X_k)\mid X_1}\right] = {\bm{0}}$ for $k\geq 2$, thus we have $\mathrm{Cov}[G(X_1), G(X_k)]= \mathrm{Cov}[G(X_k), G(X_1)] = {\bm{0}}$. Then it holds

with the last equation due to the fact that $\mathbb{E}[G_2(X_1)\mid X_1]={\bm{0}}\,.$

To see $\mathrm{Var}(G_2(X_1))$, we have

For $\mathrm{Var}(G_2(X_1))$, it holds

Hence the final covariance matrix is given by \[\Sigma_{\mathrm{MB}} = ({\bm{I}}-\gamma {\bm{P}}^\pi)^{-1} \operatorname{Diag}_{s\in{\mathcal{S}}}\left({\sigma_\pi^2(s)/{{\bm{\mu}}^{\pi}}(s) + \left\|{\gamma{\bm{V}}^\pi}\right\|_{\Sigma_p(s)}^2/{{\bm{\mu}}^{\pi}}(s)}\right) ({\bm{I}}-\gamma {\bm{P}}^\pi)^{-\top}\,.\]

Proof of Proposition (ref)

We notice that for both estimation $\overline{ K^a_\Gamma},\overline{ R^a_\Gamma}$ defined in section (ref), it holds $a\in\{t,c\}$

Thus, it is clear that $\widehat{\Delta}^{\textrm{AB}}$ and $\widehat{\Delta}^{\textrm{IS}}$ shares the same asymptotic bias. We then focus on the asymptotic variance. Let \[{\bm{u}}_\Gamma(X_i)\coloneqq

\,.\] By Markov chain CLT, we can have \[\sqrt{T}\left(\frac{1}{T}\sum_{i=1}^T{\bm{u}}(X_i)-\mathbb{E}[{\bm{u}}(X_1)]\right)\xrightarrow{d}{\mathcal{N}}(0,\Sigma_{\bm{u}})\] where $\Sigma_{\bm{u}}=\mathrm{Var}_{X_1\sim\mu} \left[{{\bm{u}}(X_1)}\right] + \sum_{i=1}^\infty \mathrm{Cov}_{X_1\sim\mu}\left[{{\bm{u}}(X_1), {\bm{u}}(X_{1+i})}\right] + \sum_{i=1}^\infty \mathrm{Cov}_{X_1\sim\mu}\left[{{\bm{u}}(X_{1+i}), {\bm{u}}(X_{1})}\right]$. Given that $f$ is differentiable, we can apply delta method, which can lead to that $\widehat{\Delta}^{\Gamma}$ is asymptotically normal for both $\Gamma\in\{\textrm{AB},\textrm{IS}\}$. The variance is given by \[\Sigma_f^\Gamma= \nabla f^\top\Sigma_{\bm{u}}^\Gamma\nabla f\,.\] It suffices to compare $\Sigma_f^\textrm{AB}$ and $\Sigma_f^\textrm{IS}$. For $a_i=a\in\{{\mathfrak{t}},{\mathfrak{c}}\}$, we denote \[{\bm{L}}^a_i\coloneqq{\bm{L}}^a(X_i)\coloneqq

\] and we can rewrite \[{\bm{u}}_\mathrm{AB}(X_i)=

\,,\qquad {\bm{u}}_\mathrm{IS}(X_i)=

\,.\] For the original A/B testing where we do not share data, we have

and for $k\geq 2$,

Then for information-sharing, we further denote ${\bm{l}}^a_j = {\bm{L}}^a(s^j)$ and we have

and for $k\geq 2$,

Note that

where $(i)$ follows from the definition of SST such that $P(s^\prime\mid s,{\mathfrak{t}})=P(s^\prime\mid s,{\mathfrak{c}})$ for all state $s\in s^{-1}$. Similarly, one can verify that the two covariance for $\mathrm{AB}$ and $\mathrm{IS}$ are the same, i.e. $\mathrm{Cov}({\bm{u}}_\mathrm{AB}(X_1),{\bm{u}}_\mathrm{AB}(X_k))=\mathrm{Cov}({\bm{u}}_\mathrm{IS}(X_1),{\bm{u}}_\mathrm{IS}(X_k))$. In other words, information-sharing will not shave off these covariance and we only need to focus on $\mathrm{Var}({\bm{u}}_\mathrm{AB}(X))$ and $\mathrm{Var}({\bm{u}}_\mathrm{IS}(X))$. Notice that $\mathbb{E}[{\bm{l}}^a_1{\bm{l}}_{-1}^\top]={\bm{0}}$, we have

Hence we conclude that all the row and columns and rows associated with the crucial state $s^1$ turns out to be $0$. In other words, variance associated with $s^1$ cannot be reduced. This matches the previous result in Theorem (ref) where we focus on a specific unbiased estimator.

For the variance associated with all other state $s^{-1}$, one can easily verify \[\mathrm{Var}({\bm{u}}_\mathrm{AB}(X))-\mathrm{Var}({\bm{u}}_\mathrm{IS}(X))\succeq 0\,.\] This demonstrates that information sharing can always reduce variance for any differentiable estimators. Finally, we conclude our results in the following theorem. We can similarly extend our result for general estimators to A/B/n testing,

Proof of Theorem (ref)

We first carefully state the detailed version of Theorem (ref) and then show the proof.

Following the Step 2 in Appendix (ref), for $a\in\{{\mathfrak{t}},{\mathfrak{c}}\}$, define

Following the similar framework as argued in Appendix (ref), one can verify that linearized part is $G(X_i)= G^t(X_i)-G^c(X_i)$. Again, it can be verified again that $\mathbb{E}\left[{G(X_k)\mid X_1}\right] = {\bm{0}}$ for $k\geq 2$, thus we have $\mathrm{Cov}[G(X_1), G(X_k)]= \mathrm{Cov}[G(X_k), G(X_1)] = {\bm{0}}$. Then it holds $\Sigma_G = \mathrm{Var} (G(X_1)).$

To see $\mathrm{Var}\left({G(X_1)}\right)$, it holds

Hence the final covariance matrix is given by \[\sigma_{\mathrm{AB}}^2(s^1) = {\bm{e}}_1^\top\Sigma_G {\bm{e}}_1 = 2 \sum_{s\in{\mathcal{S}}}\frac{\rho^{\mathfrak{t}}_{s^1}(s)^2}{\mu_{1/2}(s)}\Big(\sigma_{\mathfrak{t}}^2(s) + \left\|{\gamma{\bm{V}}^{\mathfrak{t}}}\right\|_{\Sigma_{p^{\mathfrak{t}}}(s)}^2\Big) + 2 \sum_{s\in{\mathcal{S}}}\frac{\rho^{\mathfrak{c}}_{s^1}(s)^2}{\mu_{1/2}(s)}\left({\sigma_{\mathfrak{c}}^2(s) + \left\|{\gamma{\bm{V}}^{\mathfrak{c}}}\right\|_{\Sigma_{p^{\mathfrak{c}}}(s)}^2}\right) \,.\]

Proof of Theorem (ref)

The asymptotic variance $\Sigma_\mathrm{IS}$ is given by

where ${{\bm{\rho}}^a}(s) = [\rho^a_{s^1}(s), \rho^a_{s^2}(s),\ldots,\rho^a_{s^K}(s)]^\top$ for any $s\in{\mathcal{S}}$ and $a\in\{{\mathfrak{t}},{\mathfrak{c}}\}\,.$

Following the Step 2 in Appendix (ref), for $a\in\{{\mathfrak{t}},{\mathfrak{c}}\}$, define

Following similar argument of unbiased A/B testing, one can verify that linearized part is $G(X_i)= G^{\mathfrak{t}}(X_i)-G^{\mathfrak{c}}(X_i)$. It can be verified again that $\mathbb{E}\left[{G(X_k)\mid X_1}\right] = {\bm{0}}$ for $k\geq 2$, thus we have $\mathrm{Cov}[G(X_1), G(X_k)]= \mathrm{Cov}[G(X_k), G(X_1)] = {\bm{0}}$. Then it holds $\Sigma_G = \mathrm{Var} (G(X_1))$

To see $\mathrm{Var}\left({G(X_1)}\right)$, it holds

where ${{\bm{\rho}}^a}(s) = [\rho^a_{s^1}(s), \rho^a_{s_1}(s),\ldots,\rho^a_{s_n}(s)]^\top$ for any $s\in{\mathcal{S}}$ and $a\in\{t,c\}\,.$

Hence the final covariance matrix is given by

Variance Comparison: Proof of Theorem (ref)

The first equation $\Sigma^{\mathrm{het}}_{\mathrm{IS}} = \Sigma^{\mathrm{het}}_{\mathrm{AB}}$ is straightforwards. For the second inequality, we have for any $s\in{\mathcal{S}}\setminus s^1$,

since $\Sigma_{p^{\mathfrak{c}}}(s)$ is positive semi-definite. And \[(\rho^{\mathfrak{t}}_{s^1}(s)-\rho^{\mathfrak{c}}_{s^1}(s))^2< 2\rho^{\mathfrak{t}}_{s^1}(s)^2+2\rho^{\mathfrak{c}}_{s^1}(s)^2\,,\] since $\rho^{\mathfrak{t}}_{s^1}(s),\rho^{\mathfrak{c}}_{s^1}(s)>0$ for ergodic chains. Finally, under SST we have $\Sigma_{p^{\mathfrak{t}}}(s)=\Sigma_{p^{\mathfrak{c}}}(s)$ and $\sigma_{\mathfrak{t}}^2(s)=\sigma_{\mathfrak{c}}^2(s)$, giving the result.

For the equality to hold, it's easy to see one necessary condition is that all reward of state $s\in{\mathcal{S}}\setminus s^1$ are fixed, i.e. $\sigma_{\mathfrak{c}}^2(s)=0$ for all $s\ne s^1$.

On the other hand, for $\left\|{\gamma\rho^{\mathfrak{t}}_{s^1}(s){\bm{V}}^{\mathfrak{t}} + \gamma\rho^{\mathfrak{c}}_{s^1}(s){\bm{V}}^{\mathfrak{c}}}\right\|_{\Sigma_{p^{\mathfrak{c}}}(s)}^2 = 0$ to hold, we have for all $s\ne s^1$, there exists some constant $\alpha_s\in\mathbb{R}$ such that $\rho^{\mathfrak{t}}_{s^1}(s){\bm{V}}^{\mathfrak{t}} + \rho^{\mathfrak{c}}_{s^1}(s){\bm{V}}^{\mathfrak{c}}=\alpha_s \mathbf{1}$, where $\mathbf{1}$ is the all-ones vector. We can write this constraint as

where $\rho^a_{s^1}(s^{2:K})\coloneqq[\rho^{\mathfrak{t}}_{s^1}(s^2) ,\rho^{\mathfrak{t}}_{s^1}(s^3) , \ldots , \rho^{\mathfrak{t}}_{s^1}(s^K)]$ for $a\in\{{\mathfrak{t}},{\mathfrak{c}}\}.$

A trivial case is ${\bm{V}}^{\mathfrak{t}}={\bm{V}}^{\mathfrak{c}} = {\bm{0}}$, which corresponds to the trivial MDP with all reward zeros. When MDP is non-trivial, by Sylvester’s rank inequality, we derive a necessary condition condition for \Eqref{eq: condition of equality} to hold: either $\mathrm{rank}({\bm{V}}^{\mathfrak{t}},{\bm{V}}^{\mathfrak{c}}) = 1 $ or $\mathrm{rank}( \rho^{\mathfrak{t}}_{s^1}(s^{2:K})^\top, \rho^{\mathfrak{c}}_{s^1}(s^{2:K})^\top) = 1 $. The second one implies the linear dependence of $\rho$.

We are then interested in the case where the second condition is not satisfied, which implies $\mathrm{rank}({\bm{V}}^{\mathfrak{t}},{\bm{V}}^{\mathfrak{c}}) = 1 $. That is, there exists some constant $\beta\ne 0$ such that ${\bm{V}}^{\mathfrak{t}} = \beta{\bm{V}}^{\mathfrak{c}}$. Recall $\rho^{\mathfrak{t}}_{s^1}(s){\bm{V}}^{\mathfrak{t}} + \rho^{\mathfrak{c}}_{s^1}(s){\bm{V}}^{\mathfrak{c}}=(\rho^{\mathfrak{t}}_{s^1}(s)\beta + \rho^{\mathfrak{c}}_{s^1}(s)){\bm{V}}^{\mathfrak{c}} = \alpha_s \mathbf{1}$. Then it implies ${\bm{V}}^{\mathfrak{c}} = \phi \mathbf{1}$ for some $\phi\ne 0$. Since in this case ${\bm{V}}^{\mathfrak{t}}$ and ${\bm{V}}^{\mathfrak{c}}$ are linear dependent, we have ${\bm{\Delta}} = \phi^\prime \mathbf{1}$. This will contradict the Monotonicity Theorem (ref) unless $\phi^\prime=0$, that effectively corresponds to the A/A testing case. And in A/A testing, we have $\rho^{\mathfrak{t}}_{s^1}(s^{2:K}) = \rho^{\mathfrak{c}}_{s^1}(s^{2:K})$, which contradicts the condition that the second condition does not hold.

In conclusion, the necessary condition is given by the linear dependence of $\rho$.

Proof of Asymptotic Efficiency

In this section, we will discuss the proof framework for asymptotic efficiency via constrained Cramer-Rao Bound. We will again start with the warm-up from of fixed policy inference in Proposition (ref). We then discuss the asymptotic results in A/B testing.

Proof of Proposition (ref)

The MDP system is controlled by parameters ${\bm{\theta}} = ({\bm{P}}^\pi,{\bm{r}}^\pi)$. Since we assume the initial distribution is ${\bm{\mu}}^\pi$, the observations $(s_i,a_i,s_{i+1},r_i)$ in $\tau$ can be seen as i.i.d. By Constrained Cramer-Rao Bound, Lemma (ref) shows for one single observation $X =(s,a,s^\prime,r)$, we have \[\mathrm{CCRB}({\bm{P}}^\pi, {\bm{r}}^\pi) =

\,.\]

Also note that

and

By Lemma (ref), the Constrained Cramer-Rao Bound for ${\bm{V}}^\pi$ is given by

\proof{Proof.} For the first row ${\bm{P}}(1) = (P(1,i))_{i\in[n]}$ and reward ${\bm{r}}(1)$, it holds for observation $X = (s_1 = 1,a_1,s_2=s,r_1)$,

The constraint for ${\bm{P}}(1),{\bm{r}}(1)$ is $f_1({\bm{P}}(1),{\bm{r}}(1)) = \sum_{i\in[n]} P(1,i)-1=0$, then we have \[\nabla f_1 = [1,1,\ldots, 1,0]\,.\] Following Lemma (ref), we construct \[{\bm{U}}_1=

\,.\] It can be verified that \[\mathrm{CCRB}({\bm{P}}(1),{\bm{r}}(1))= {\bm{U}}_1 ({\bm{U}}_1^\top {\bm{I}}({\bm{P}}(1)) {\bm{U}}_1)^{-1} {\bm{U}}_1^\top =

\,.\] One fuhrer notice that \[{\bm{I}}({\bm{P}},{\bm{r}}) = \operatorname{Diag}({\bm{I}}({\bm{P}}(i),{\bm{r}}(i))\,,\quad \nabla f =

\,,\quad {\bm{U}} =

\,,\] and the final Constrained Cramer-Rao Bound is \[\mathrm{CCRB}({\bm{P}}, {\bm{r}}) =

\,.\] \Halmos \endproof

Proof of Theorem (ref)

The MDP system is controlled by parameters ${\bm{\theta}} = ({\bm{P}}_0,{\bm{P}}_1, {\bm{r}}_0,{\bm{r}}_1)$. Since we assume the initial distribution is ${\bm{\mu}}_{1/2}$, the observations $(s_i,a_i,s_{i+1},r_i)$ in $\tau$ can be seen as i.i.d. A similar argument to Lemma (ref) can show \[\mathrm{CCRB}({\bm{\theta}}) = 2\operatorname{Diag}(\Sigma_{p^0}/\mu_{1/2}, \Sigma_{p^1}/\mu_{1/2}, \sigma_0^2/\mu_{1/2}, \sigma_1^2/\mu_{1/2})\,,\] where $\Sigma_{p^i}/\mu_{1/2} = [\Sigma_{p^i}(s^1)/\mu_{1/2}(s^1), \Sigma_{p^i}(s^2)/\mu_{1/2}(s^2),\ldots,\Sigma_{p^i}(s_K)/\mu_{1/2}(s^K)]^\top$ and $\sigma_0^2/\mu_{1/2} = [\sigma_0^2(s^1)/\mu_{1/2}(s^1), \sigma_0^2(s^2)/\mu_{1/2}(s^2),\ldots, \sigma_0^2(s^K)/\mu_{1/2}(s^K)]^\top$ for $i=0,1$.

Also note that

and

And similar results hold for $\frac{\partial {\bm{\Delta}}}{\partial P_1(i,j)}$ and $\frac{\partial {\bm{\Delta}}}{\partial r_1(i)}$. By Lemma (ref), the Constrained Cramer-Rao Bound for ${\bm{V}}$ is given by

Proof of Theorem (ref)

We denote $s_{i:j}\coloneqq (s_i,s_{i+1},\ldots,s_j)$. The MDP system is controlled by parameters ${\bm{\theta}} = ({\bm{P}}_1(s^1),{\bm{P}}_0, r(s^1,1), {\bm{r}}_0)$. Since we assume the initial distribution is ${\bm{\mu}}_{1/2}$, the observations $(s_i,a_i,s_{i+1},r_i)$ in $\tau$ can be seen as i.i.d. A similar argument to Lemma (ref) can show

Also note that for state $s^1$,

And similar results hold for $\frac{\partial {\bm{\Delta}}}{\partial P_1(1,j)}$.

For state $s\ne s^1$,

One can also calculate the gradient for the reward part.

By Lemma (ref), the Constrained Cramer-Rao Bound for ${\bm{V}}$ is given by

Extension to multiple test arms

The proof follows the same manner of the previous section.

Generalization to Local Treatment

For clarity, we denote ${\mathcal{S}}^{\mathfrak{c}}\coloneqq {\mathcal{S}}\setminus{\mathcal{S}}^{\mathfrak{t}}$.

The proof can be easily adapted from the proof of Theorem (ref), (ref) and (ref).

Local Treatment with Multiple Test Arms

We first define the model for local treatment with $n$ test arms, which can be extended from the model of SST with $n$ test arms in Section (ref). In particular, there exists a pre-determined crucial subset ${\mathcal{S}}^{\mathfrak{t}}\subseteq {\mathcal{S}}$. For each treatment policy $\pi^i\in \Pi\coloneqq\{\pi^j\}_{j\in[n]}$, $\pi^i(s)\equiv {\mathfrak{t}}^i$ for all $s\in{\mathcal{S}}^{\mathfrak{t}}$ and $\pi^i(s)\equiv {\mathfrak{t}}^1$ for all $s\in{\mathcal{S}}\setminus {\mathcal{S}}^{\mathfrak{t}}$. Additionally, each local treatment policy is associated with its own transition matrix ${\bm{P}}^{{\mathfrak{t}}^i}$ and mean reward ${\bm{r}}^{{\mathfrak{t}}^i}$.

The objective is still to infer the ATE between any pair of policies $(\pi^i,\pi^j)$, i.e. ${\bm{\Delta}}_{i,j}={\bm{V}}^i-{\bm{V}}^j$. We apply similar ideas of A/B testing, IS and PI and obtain the following generalization of Corollary (ref),

Similarly, we can derive the following generalization of Theorem (ref),

This corollary justifies that the linear variance reduction of IS with the number of test arms keeps to take effect for local treatments.

Estimation with Perfect Information about the Control Arm

In this section, we explore the information-sharing concept further by considering scenarios where we have Perfect Information (PI) about the control arm. Typically, the control arm represents a default policy that may have been operational for an extended period within the system, allowing the organization to accumulate a substantial dataset and develop a thorough understanding of this baseline. Extending Example (ref), the company might already possess ample historical data on customer behaviors, enabling it to accurately determine the customers' transition matrices when not offering coupon. We assume the historical data accurately characterizes the customer's behavior (the same transition) at present. In other words, there is no distribution shift between the offline dataset and the current trial. Access to extensive historical user data is a common strategy in marketing, utilized to optimize selling policies (simester06dynamic,jeremy24targeting), predict future purchases (jacobs16model), or gauge customer responses (das23using). Similarly, the assumption of having an offline dataset is prevalent in other domains involving MDPs, such as offline reinforcement learning (levine2020offline), reinforcement learning with human feedback (RLHF, chang2024dataset), and healthcare applications (yu21reinforce, hu24fast).

Formally, we assume that the experimenter has access to both the precise transition matrix ${\bm{P}}^{\mathfrak{c}}$ and the exact mean reward ${\bm{r}}^{\mathfrak{c}}$ of control policy $\pi^{\mathfrak{c}}$. With this perfect information, she can directly computing ${\bm{V}}^{\mathfrak{c}}$ using the Bellman equation. Consequently, her primary focus during experimental periods becomes gathering data on the new treatment policy $\pi^{\mathfrak{t}}$, applying it consistently. Moreover, since $\pi^{\mathfrak{t}}$ is SST, a substantial amount of information from ${\bm{r}}^{\mathfrak{c}}$ and ${\bm{P}}^{\mathfrak{c}}$, especially those associated with the non-crucial states, can be shared when estimating ${\bm{V}}^{\mathfrak{t}}$. More specifically, after consistently applying $\pi^{\mathfrak{t}}$, she only needs to estimate the transitions and mean reward associated with the crucial state $s^1$, which is

For all the other components in $\widehat{{\bm{P}}}_{\textrm{PI}}^{{\mathfrak{t}}}$ and $\widehat{{\bm{r}}}_{\textrm{PI}}^{{\mathfrak{t}}}$, we directly plug in those in ${\bm{P}}^{\mathfrak{c}}$ and ${\bm{r}}^{\mathfrak{c}}$, i.e., $\widehat{{\bm{P}}}^{{\mathfrak{t}}}_{\textrm{PI}}(s,s')={\bm{P}}^{\mathfrak{c}}(s,s')$ and $\widehat{r}_{\textrm{PI}}^{\mathfrak{t}}(s)= r^{\mathfrak{c}}(s)$ for all $s\neq s^1$ and any $s'\in\mathcal{S}$. Applying $\widehat{{\bm{P}}}_{\textrm{PI}}^{{\mathfrak{t}}}$ and $\widehat{{\bm{r}}}_{\textrm{PI}}^{{\mathfrak{t}}}$ to the Bellman equation generates an estimator $\widehat{{\bm{V}}}^{\mathfrak{t}}_{\textrm{PI}}$. Then, the difference between $\widehat{{\bm{V}}}^{\mathfrak{t}}_{\textrm{PI}}$ and ${{\bm{V}}}^{\mathfrak{c}}$ yields an estimator $\widehat {\bm{\Delta}}^\mathrm{PI}$ of the treatment effects. The following theorem presents the central limit theorem of our estimator. The detailed proof is delayed to Appendix (ref).

Since we are implementing a fixed policy $\pi^{\mathfrak{t}}$ during the experimental periods, it is logical that the asymptotic variance $\Sigma_\mathrm{PI}$ and $\sigma^2_\mathrm{PI}(s^1)$ exhibit similar structures with $\Sigma_{\mathrm{MB}}$ and $\sigma^2_{\mathrm{MB}}(s^1)$ from the model-based estimator under a fixed policy discussed in Section (ref). Unlike the approach in that section, which requires estimating transitions for every state, here we only need to estimate the transitions and rewards associated with the crucial state $s^1$. With PI, $\sigma^2_{\textrm{PI}}(s^1)$ only keeps the variance linked to the crucial state $s^1$. This reduction aligns with our expectations, given the complete information on the transitions and rewards for non-crucial states now at our disposal.

We now would like to compare the variance with A/B testing, both with and without information sharing, as discussed in Sections (ref) and (ref). In addition to the perfect information about the control arm, as we are running $\pi^{\mathfrak{t}}$ all the time instead of the mixed policy like A/B testing, we naturally accumulate more data specific to $\pi^{\mathfrak{t}}$. Hence it's natural to anticipate a further reduction of variance associated with crucial state $s^1$. To facilitate a detailed comparison and ensure consistency in our analysis, we introduce two notations, albeit redundant, $\Sigma^{\mathrm{het}}_{\mathrm{PI}}$ and $\Sigma^{\mathrm{hom}}_{\mathrm{PI}}$. These notations are designed to differentiate the parts of $\sigma^2_{\mathrm{PI}}(s^1)$ related to the crucial states $s^1$ and all other states, respectively. Thus, $\Sigma^{\mathrm{het}}_{\mathrm{PI}}=\sigma^2_{\mathrm{PI}}(s^1)$ and $\Sigma^{\mathrm{hom}}_{\mathrm{PI}}=0$ since $\sigma^2_{\mathrm{PI}}(s^1)$ is only related to $s^1$. Formally, we have the following theorem characterizing the variance reduction of PI, whose detailed proof is delayed to Appendix (ref).

The parameter $\delta$ measures the difference between the transition probabilities under the treatment and the control. One of the reasons that such a parameter takes an effect is that the denominators in $\Sigma^{\mathrm{het}}_{\mathrm{AB}}$ and $\Sigma^{\mathrm{het}}_{\mathrm{PI}}$ are $\mu_{1/2}(s^1)$ and $\mu^{{\mathfrak{t}}}(s^1)$ respectively, which are the stationary probabilities of the crucial state $s^1$. A little difference in the transition probability may have an significant impact on the reciprocal of the stationary probability. Also, recall that $\Sigma^{\mathrm{het}}_{\mathrm{AB}}=\Sigma^{\mathrm{het}}_{\mathrm{IS}}$, and Theorem (ref) confirms that PI can always strictly outperform A/B testing even with information sharing. Moreover, if the shift of transition probability $\delta$ is small or the Markov chain mixes fast enough, Theorem (ref) indicates that PI can approximately halve the variance compared to A/B testing for the heterogeneous component. To reiterate, PI eliminates uncertainty stemming from all non-crucial states.

Similar ideas can also be generalized to SST with multiple test arms, where the perfect information about control arm is available. Following the notations in Section (ref), assume there are $n$ test arm with the first arm serving as the control. Consequently, sampling is required only for the $n-1$ test arms excluding the control arm, such that $\pi^{1/(n-1)}(a\mid s)\coloneqq \frac{1}{n-1}\sum_{i\ne 1}\pi^{i}(a\mid s)$ for any $(s,a)$ pair. For all the test arms, we estimate only ${\bm{P}}^{{\mathfrak{t}}^i}(s^1,\cdot)$ and $r^{{\mathfrak{t}}^i}(s^1)$ using sample means, while inheriting the other values from the known control arm. Using the Bellman equation, we derive the estimator $\widehat{{\bm{V}}}^{{\mathfrak{t}}^i}$ for each SST, leading to the estimator of $\Delta_{i,j}(s^1)$ by taking the difference. In Corollary (ref), we establish the asymptotic normality for the estimation of $\Delta_{i,j}(s^1)$, confirming the statistical robustness of our approach under these settings.

With $n$ test arms, PI continues to yield asymptotically normal estimators and significant variance reduction. Moreover, the term $ \left\{{1\land \frac{n-1}{n}\left({1+\frac{2\delta L}{n}}\right) }\right\}$ is almost non-decreasing with increasing $n$. This pattern indicates that as $n$ grows, the relative benefit of variance reduction for $\Sigma^{\mathrm{het}}_{\mathrm{PIn}}(i,j)$ diminishes. Such an observation aligns with the intuition that as the number of test arms grows, the data available for each test arm decreases, potentially becoming a limiting factor in further reducing variance.

Proofs of Theorem (ref)

For $X_i=(s_i,a_i,s_{i+1},r_i)$, define

and denote $Y(X_i)\coloneqq [Z(X_i),R(X_i)]^\top$.

We have the following CLT \[\sqrt{T}\left({\overline{Y_T} -

}\right)\xrightarrow{d}{\mathcal{N}}({\bm{0}}, \frac{1}{\mu^{\mathfrak{t}}(s^1)}\Sigma_Y)\,,\] where the covariance matrix is given by \[\Sigma_Y =

=

\,,\] with ${\bm{p}}_{s^1} = [ P(s^1\mid s^1), P(s^2\mid s^1), \ldots, P(s^K\mid s^1)]^\top$ and $\sigma_{\mathfrak{t}}^2(s^1)$ the variance of reward.

To apply the Delta Method, let \[g(\overline{Y_T})={\bm{e}}_1^\top \left({{\bm{I}}-\gamma

}\right)^{-1}

\,.\]

Taking the gradient gives

One can verify that

Then the final variance is given by \[\sigma^2 = \frac{\rho^{\mathfrak{t}}_{s^1}(s^1)^2}{\mu^{\mathfrak{t}}(s^1)}\left({\left\|{\gamma{\bm{V}}^{\mathfrak{t}}}\right\|^2_{\Sigma_{p}(s^1)}+\sigma_{\mathfrak{t}}^2(s^1)}\right)\,.\]

PI with Multiple Test Arms

The variance of PIn is given by

Asymptotic Relative Efficiency: Proof of Theorem (ref)

Recall \[\Sigma^{\mathrm{het}}_{\mathrm{AB}} = 2\left({\frac{\rho^{\mathfrak{t}}_{s^1}(s^1)^2}{\mu_{1/2}(s^1)}\left\|{\gamma{\bm{V}}^{\mathfrak{t}}}\right\|_{\Sigma_{p^{\mathfrak{t}}}(s^1)}^2 + \frac{\rho^{\mathfrak{c}}_{s^1}(s^1)^2}{\mu_{1/2}(s^1)}\left\|{\gamma{\bm{V}}^{\mathfrak{c}}}\right\|_{\Sigma_{p^{\mathfrak{c}}}(s^1)}^2 }\right)\,,\] and \[\Sigma^{\mathrm{het}}_{\mathrm{PI}}=\frac{\rho^{\mathfrak{t}}_{s^1}(s^1)^2}{\mu_1(s^1)}\left\|{\gamma{\bm{V}}^{\mathfrak{t}}}\right\|^2_{\Sigma_{p^{\mathfrak{t}}}(s^1)}\,.\] By Lemma (ref), it holds

where ${\bm{\delta}}(s^1) = [P^1(s|s^1)-P^{1/2}(s|s^1)]_{s\in{\mathcal{S}}}^\top$ and note that the treatment only happens on state $s^1$.

Multiply by ${\bm{e}}_1$ to both sides,

By Lemma (ref), it holds $\mu_{1/2}(s^1)< \mu_1(s^1) (1+\delta L)\,.$ And this implies $\Sigma^{\mathrm{het}}_{\mathrm{PI}}< \frac{1+\delta L}{2}\Sigma^{\mathrm{het}}_{\mathrm{AB}}$.

Similarly, one can derive \[\mu_{1/2}(s^1) = \mu_0(s^1)\left({1+{\bm{\delta}}(s^1)^\top({\bm{I}}-{\bm{P}}_{1/2})^\sharp {\bm{e}}_1}\right)\,.\] Subtract with (ref) and obtain \[{\bm{\delta}}(s^1)^\top({\bm{I}}-{\bm{P}}_{1/2})^\sharp {\bm{e}}_1 = \frac{\mu_1(s^1)-\mu_0(s^1)}{\mu_1(s^1)+\mu_0(s^1)}\in(-1,1)\,.\] This indicates $\mu_{1/2}(s^1)< 2\mu_1(s^1)$ and $\Sigma^{\mathrm{het}}_{\mathrm{PI}}< \Sigma^{\mathrm{het}}_{\mathrm{AB}}$.

When there are $n$ arms, one can verify

where ${\bm{\delta}} = \frac{1}{n}\sum_{i=2}^n {\bm{p}}^1-{\bm{p}}^i$ and \[{\bm{\delta}}^\top({\bm{I}}-{\bm{P}}_{1/n})^\sharp {\bm{e}}_1 = \frac{\mu_1(s^1)-\mu_{1/(n-1)}(s^1)}{\mu_1(s^1)+1/(n-1)\mu_{1/(n-1)}(s^1)} < 1\,,\] finishing the proof.

Additional Proofs

Proof of Proposition (ref)

Let $N(s^i)>0$ be the number of visitations to state $s^i\in{\mathcal{S}}$ in $\tau$. Then the optimization problem in Algorithm (ref) can be rewritten as

where $\widehat {\bm{r}} \in\mathbb{R}^K$ is the empirical average reward with $\widehat {\bm{r}}(s) = \sum_{i=1}^T\mathbf{1}[s_i=s]r(s_i,a_i)/N(s)$ for $s\in{\mathcal{S}}$ and $\widehat{\bm{P}}\in\mathbb{R}^{K\times K}$ is the empirical transition matrix with $\widehat {\bm{P}}(s,s^\prime) = \sum_{i=1}^T\mathbf{1}[s_i=s, s_{i+1}=s^\prime]/N(s)$ for all $s,s^\prime\in{\mathcal{S}}$.

It is worth noting that any estimation $\widehat {\bm{P}}$ is always a transition matrix. Thus the matrix $({\bm{I}}-\gamma \widehat{\bm{P}})$ is always non-singular. Therefore one can verify that the unique solution to \Eqref{eq: opt_rewrite} is $\widehat {\bm{V}}^{\textnormal{TD}} = ({\bm{I}}-\gamma \widehat{\bm{P}})^{-1}\widehat {\bm{r}}\,,$which matches $\widehat {\bm{V}}^{\textnormal{MB}}$.

Proofs of Theorem (ref)

Proof 1: a Pure Algebraic Proof

For $s\ne s^1$, we have

Denote $S^\prime = S\setminus s^1$, ${\bm{\Delta}}=(\Delta(s^1),\Delta(S^\prime))^\top$ and ${\bm{P}}^c=

$. Then following \Eqref{eq: advs}, we have

Further denote ${\mathcal{G}}=

\,,$ and \Eqref{eq: Geigen} indicates that ${\mathcal{G}}$ has eigenvalue $1$.

On the other hand, it is known that the eigenvalues $\{\lambda_i\}_{i\in[|S|]}$ satisfy \[\max_{i\in[|S|]}|\lambda_{i}| \leq \|{\mathcal{G}}\|_{\infty}=\max_i\sum_j {\mathcal{G}}_{ij}=1\,.\] This implies that $1$ is the spectral radius of ${\mathcal{G}}$. Notice that ${\mathcal{G}}$ is non-negative matrix, then by Perron-Frobenius Theorem meyer01, it admits a non-negative eigenvector of $1$.

It remains to show that $\textnormal{dim}(\textnormal{ker}({\mathcal{G}}-I))=1\,.$ Since ${\mathcal{G}}$ and ${\mathcal{G}}^\top$ share exactly the same characteristic polynomial, this is equivalent to $\textnormal{dim}(\textnormal{ker}({\mathcal{G}}^\top-I))=1\,.$ Assume for some ${\bm{h}}=(h(s^1),\ldots,h(s^K))^\top\in \mathbb{R}^{K},{\bm{h}}\ne {\bm{0}}$ such that

Notice that \Eqref{eq: Gtopeigen} holds for any $h(s^1)\in\mathbb{R}$. Then by denoting ${\bm{h}}^\prime=(h(s^2), \ldots, h(s^K))^\top$, we can refine \Eqref{eq: Gtopeigen} as

We further denote ${\mathcal{T}}\coloneqq

$, then we have

However, the eigenvalues $\{\mu_i\}_{i\in[|S^\prime|]}$ of ${\mathcal{T}}$ must satisfy \[\max_{i\in[|S^\prime|]}|\mu_{i}| \leq \|{\mathcal{T}}\|_{1}=\max_i\sum_j {\mathcal{T}}_{ji}\leq1<\frac{1}{\gamma}\,.\] This implies ${\bm{h}}^\prime = {\bm{0}}\,.$ and hence $\textnormal{dim}(\textnormal{ker}({\mathcal{G}}^\top-I))=\textnormal{dim}(\textnormal{ker}({\mathcal{G}}-I))=1\,.$ Recall $\Delta(s^1)> 0$, then $\Delta(s)\geq 0$ for all $s\in S$.

Moreover, let $\Delta(s_i)=\max_{s\ne s^1}\Delta(s)$. It holds that

If ${\bm{P}}^{\mathfrak{c}}(i,1)=0$, then \Eqref{eq: maxAsi} shows $\Delta(s_i)\leq \gamma \Delta(s_i)$, which implies $\Delta(s_i)=0$. It's hence evident that $\Delta(s)< \gamma \Delta(s^1)$ for all $s\ne s^1$. Otherwise if ${\bm{P}}^{\mathfrak{c}}(i,1)>0$, then

which completes the proof for $\Delta(s^1)>0$. Similar proof can be derived for $\Delta(s^1)<0$ by setting $\Delta(s_i)=\min_{s\ne s^1}\Delta(s)\,.$

Proof 2: Performance Difference Lemma

We draw insights from reinforcement learning theory and apply the well-known performance difference lemma Kakade2002ApproximatelyOA to our single-point treatment scenario

This lemma clearly characterizes the treatment effect using the advantage function. In particular, the treatment effect of all states all determined by the advantage function at state $s^1$, multiplied by some non-negative measure. Consequently, the monotonicity property follows directly from this relationship.

Technical Tools

Markov Chain Central Limit Theorem

Perturbation Bounds

Constrained Cramer-Rao Bounds

Experiment Details

All implementations can be found on Github.

Customer Lifetime Value

We simulate a synthetic example of Example (ref). The code is available on Github. For both SST and local treatment, the control transition matrix and the reward is given by \[{\bm{P}}^{\mathfrak{c}}=

\,,\qquad {\bm{r}}^{\mathfrak{c}}=

\,.\]

The discounted factor $\gamma$ is set to be $1/1.2\approx0.83$ aligned with pfeifer2000modeling.

Sepsis Simulator

\noindentEnvironment. The state transition follows from complex fluctuation and treatment impacts. Hence the transition matrices are learned via Monte-Carlo samplings. The learning process will generate the transition matrices for all possible actions at all states as well as the initial state distribution of patients. We assume the initial state distribution is known a prior to the estimators, which is a common for discounted reward RL. The discount factor is set to 0.9 aligned with tran2023inferring.

\noindentAlgorithms. For A/B testing, IS and PI, the transition matrices are learned by model-based methods. However, the large state space may hinder the visitation of all states. To mitigate this issue, we initialize all transition matrix as uniform distribution.

The Naive estimator follows from the generalization of DQ theory to discounted reward case, given by\[\widehat {\bm{\Delta}}^{\textrm{Naive}}_{ij}\coloneqq \left({{\bm{I}}-\gamma \widehat{\bm{P}}_{1/n}}\right)^{-1}\left({\widehat{\bm{r}}_i-\widehat{\bm{r}}_j}\right)\,.\]

The DQ estimator is originally designed for A/B testing. We generalize the DQ estimator to multiple test arms via Taylor expansion, \[\widehat{{\bm{V}}}^{\rm{DQ}}_i=({\bm{I}}-\gamma {\bm{P}}_{1/n})^{-1}\left[{{\bm{I}}+\gamma ({\bm{P}}_i-{\bm{P}}_{1/n}) ({\bm{I}}-\gamma {\bm{P}}_{1/n})^{-1}}\right]{\bm{r}}_i\,.\] and $\widehat{\Delta}_{ij}^{\rm{DQ}}=\widehat{{\bm{V}}}^{\rm{DQ}}_i-\widehat{{\bm{V}}}^{\rm{DQ}}_j$. Notice that when $n=2$ we recover the original DQ estimator in farias2022markovian,farias2023correcting and one can show similar ${\mathcal{O}}(\delta^2)$ bias bounds for our generalized estimator.

\noindentResults. The MSE curve is the average of 100 independent runs and each MSE is given by $\sum_{i=1}^{100}\left({\hat{\rm{ATE}}-\rm{ATE}}\right)^2/\rm{ATE}^2$ where $\rm{ATE}$ is the true ATE.

Bias-Variance Trade-off

farias2022markovian introduces the DQ estimator for the average reward setting, achieving notable bias-variance trade-offs. farias2023correcting extends this work, generalizing the DQ theory to other reward settings and proposing a unified framework for Taylor series expansions. We review the DQ theory for the discounted reward setting.

We begin by examining the naive estimator, which can be viewed as the zeroth-order expansion, given by, \[\widehat {\bm{\Delta}}^{\textrm{Naive}}\coloneqq \left({{\bm{I}}-\gamma \widehat{\bm{P}}_{1/2}}\right)^{-1}\left({\widehat{\bm{r}}({\mathfrak{t}})-\widehat{\bm{r}}({\mathfrak{c}})}\right)\,.\] By Corollary 1 in farias2023correcting, the bias for the naive estimator is bounded by ${\mathcal{O}}(\delta/(1-\gamma)^2)$. Then, the DQ estimator is defined as the first order expansion, \[\widehat {\bm{\Delta}}^{\textrm{DQ}}\coloneqq \left({{\bm{I}}-\gamma \widehat{\bm{P}}_{1/2}}\right)^{-1}\left({\widehat {\bm{Q}}^{\pi_{1/2}}({\mathfrak{t}})- \widehat {\bm{Q}}^{\pi_{1/2}}({\mathfrak{c}}) }\right)\,,\] where the ${\bm{Q}}^{\pi_{1/2}}(a) = \widehat {\bm{r}}(a) + \gamma \widehat {\bm{P}}(a) \widehat V^{\pi_{1/2}}$ for $a\in\{{\mathfrak{t}},{\mathfrak{c}}\}$. The bias of DQ is bounded by ${\mathcal{O}}(\delta^2/(1-\gamma)^3)$. When $\delta$ is small enough, DQ can outperform naive estimator for the bias. DQ intuitively trades a small bias for substantially lower variance compared to unbiased estimators. This intuition is well-justified in the average reward setting in farias2022markovian. However, the performance of naive and DQ estimators in terms of variance remains unclear in the discounted reward setting.

Moreover, we can apply the idea of information sharing to the learning of Q-functions to reduce variance. Specifically, information sharing enables us to obtain better estimation of $\widehat {\bm{r}}(a)$ and $\widehat {\bm{P}}(a)$ for $a\in\{{\mathfrak{t}},{\mathfrak{c}}\}$. We call this estimator DQ-IS, taking advantage of orthogonal ideas of DQ and IS.

We then further implement Naive, DQ and DQ-Is in the same simulation environment of Example (ref) and the results are concluded in Figure (ref).

\noindentDQ trades-off variance for bias compared to Naive. The simulation results first verify the DQ theory of bias. In particular DQ, the first order expansion, exhibits smaller variance than Naive, the zeroth order expansion. \newline\noindentIS is compatible with DQ. The simulation results demonstrate that both DQ and DQ-IS exhibit negligible bias. However, DQ-IS shows a significantly reduced variance compared to the original DQ method. These findings validate the orthogonal application of the information sharing idea. \newline\noindentDQ exhibits minimal bias-variance trade-off with SST. A more surprising result is that both DQ and DQ-IS exhibit negligible bias, while their variances are comparable to that of two unbiased estimator, A/B testing and IS. This suggests that the structure of treatments may potentially impact the performance of bias-variance trade-off estimators . We believe this phenomenon warrants further study, as it may be of independent interest to DQ theory and the broader field of bias-variance trade-offs in RL.