Technical Summary: Estimation of Treatment Effects Under Nonstationarity via the Truncated Policy Gradient Estimator

1. Problem Statement

Randomized experiments (A/B tests) are standard tools for evaluating interventions in dynamic systems such as recommendation platforms, marketplaces, and digital health. However, in these environments, interventions often induce carryover effects (or temporal interference), where an action at time $t$ influences system states and outcomes at future times $t' > t$. This violates the standard assumption of unit-level independence.

The challenge is exacerbated by nonstationarity: system dynamics (transition kernels and reward distributions) vary over time due to factors like evolving user preferences, seasonal trends, or external shocks. In such nonstationary Markovian settings, existing estimation approaches face significant limitations:

• Naive estimators (e.g., Difference-in-Means) ignore temporal dependencies, leading to substantial bias.
• Stationary Off-Policy Evaluation (OPE) methods (e.g., Difference-in-Q's or DQ estimators) assume a stationary environment. When applied to nonstationary data, they suffer from high bias and variance because they rely on assumptions (e.g., stationary observability, multiple independent trajectories) that do not hold.
• Complex experimental designs (e.g., switchback experiments) can mitigate interference but are difficult to implement and require careful tuning of interval lengths.

The central problem addressed is the estimation of the Global Average Treatment Effect (GATE) from a single trajectory of a nonstationary system under a Bernoulli randomized policy, without requiring knowledge of the state space or multiple independent runs.

2. Methodology: The Truncated Policy Gradient (TPG) Estimator

The authors propose the Truncated Policy Gradient (TPG) estimator, which modifies the standard Difference-in-Means (DM) approach by aggregating outcomes over a short, fixed horizon $k$ rather than using instantaneous rewards.

2.1 Formal Framework

The system is modeled as a nonstationary Markov Decision Process (MDP) with a finite horizon $T$.

• State/Action: $X_t \in \mathcal{X}$ (state), $Z_t \in \{0, 1\}$ (control/treatment).
• Dynamics: Transitions are governed by time-dependent kernels $P^t_z$. The system satisfies a mixing time assumption (Assumption 1), where the influence of past actions decays exponentially at rate $\gamma \in (0, 1)$.
• Target: The GATE $\tau = \frac{1}{T} \sum_{t=1}^T (\mathbb{E}[Y_t | \pi_1] - \mathbb{E}[Y_t | \pi_0])$, where $\pi_1$ and $\pi_0$ are the always-treatment and always-control policies.
• Data: A single trajectory generated under a Bernoulli randomization policy $\pi_{1/2}$.

2.2 The Estimator

The TPG estimator $\hat{\tau}_k$ is defined as:
$$\hat{\tau}_k := \frac{1}{T} \sum_{u=1}^T \left( \frac{\mathbb{I}\{Z_u = 1\}}{1/2} - \frac{\mathbb{I}\{Z_u = 0\}}{1/2} \right) \sum_{t=u}^{\min(u+k, T)} Y_t$$
When $k=0$, this reduces to the naive DM estimator. For $k \ge 1$, it sums rewards over a window of size $k$.

2.3 Theoretical Interpretation

The paper establishes that $\hat{\tau}_k$ is an unbiased estimator of a truncated policy gradient $\nabla J_k(1/2)$.

• Policy Gradient View: The standard policy gradient $\nabla J(1/2)$ is a first-order Taylor approximation of the GATE. In nonstationary settings, the full gradient estimator (where $k=T$) suffers from bias scaling quadratically with $T$ ($O(T^2)$).
• Truncation: By truncating the horizon to $k$, the estimator approximates the gradient of a hypothetical policy that switches to treatment or control only for the last $k$ steps.
• Bias Decomposition: The bias of $\hat{\tau}_k$ relative to the true GATE decomposes into:
  1. Taylor Error: The error from approximating the GATE with the gradient. This scales as $O(k^2)$ (much better than $O(T^2)$).
  2. Mixing Bias: The error from the difference between the truncated policy value and the true GATE. This decays geometrically with $k$ due to the mixing time assumption.

2.4 Variance Estimation and Inference

The paper derives a Central Limit Theorem (CLT) for the TPG estimator under nonstationarity. To support statistical inference, the authors develop a consistent nonstationary HAC (Heteroskedasticity and Autocorrelation Consistent) variance estimator. This estimator allows for the construction of confidence intervals using single-trajectory data, overcoming the "curse of horizon" that plagues standard OPE methods in nonstationary environments.

3. Key Contributions

1. Novel Estimator: Introduction of the TPG estimator, which balances bias and variance by truncating the reward horizon. It requires no state observability and works with a single trajectory.
2. Theoretical Guarantees:
   • Bias-Variance Trade-off: Theorem 1 provides bounds showing that for $k \ge 1$, the TPG estimator achieves a favorable trade-off. The bias is controlled by the mixing rate $\gamma$ and kernel deviation $\delta$, while variance is bounded and does not explode with $T$ (unlike the untruncated estimator).
   • Asymptotic Normality: Theorem 2 establishes the CLT for $\hat{\tau}_k$ and proves the consistency of the proposed HAC variance estimator under mild regularity conditions (Cesàro-$L^2$ mean stability).
3. Practical Heuristic: A data-driven algorithm (Appendix B) is proposed to select the truncation size $k$ post-experiment by monitoring the stability of the estimate relative to its variance.
4. Empirical Validation: The method is validated on two realistic case studies:
   • A queueing simulator based on nonstationary patient arrival data.
   • A large-scale NYC ride-sharing simulator using real taxi data.

4. Results

• Two-State MDP: In simulations, the naive DM estimator ($k=0$) exhibited ~50% Mean Absolute Error (MAE). The untruncated policy gradient ($k=T$) had incorrect signs and massive variance. The TPG estimator with small $k$ (e.g., $k=1$ to $5$) significantly reduced bias while maintaining low variance.
• Queueing Case Study: Compared to stationary DQ, LSTD-OPE, and bias-corrected switchback estimators, the TPG estimator (with $k=4$ or $5$) closely approximated the ground-truth GATE. The proposed HAC variance estimator achieved near-nominal 95% coverage.
• Ride-Sharing Case Study: In a complex, non-stationary environment with real NYC data, the TPG estimator consistently reduced bias across various switchback intervals (10 to 60 minutes). It outperformed state-of-the-art switchback estimators (which were sensitive to interval choice) and stationary OPE methods (which failed to learn reliable Q-values). The TPG estimator with $k=2$ or $3$ produced estimates very close to the true GATE.

5. Significance and Claims

The paper claims that the TPG estimator offers a simple, practical, and theoretically grounded solution for causal inference in nonstationary dynamic systems. Its primary significance lies in:

• Robustness: It achieves a favorable balance between bias and variance in settings where existing methods (naive DM, stationary OPE) fail.
• Feasibility: It operates on single-trajectory data without requiring knowledge of the state space, making it applicable to real-world platforms where full state observability is often impossible.
• Inference: It provides the first consistent variance estimator and CLT for treatment effect estimation in single-trajectory nonstationary Markovian settings, enabling valid statistical inference.
• Flexibility: It can be applied as a post-processing tool to improve estimates from standard Bernoulli A/B tests or more complex designs like switchbacks.

The authors conclude that the policy-gradient perspective, specifically through truncation, provides a powerful framework for designing effective estimators under complex, nonstationary dynamics.