Estimation of Treatment Effects Under Nonstationarity via the Truncated Policy Gradient EstimatorResearch Paper
Why short-horizon outcome windows
Randomized experiments (A/B tests) on ride-sharing marketplaces, recommendation systems and digital-health services assign each arriving user to treatment or control. The assignment changes the system state seen by later users, so observations are not independent: this is temporal interference, or carryover. The difference-in-means estimator ignores it, and in Markovian models its bias can be as large as the treatment effect itself (Farias, Li, Peng, Zheng 2022; Hu, Wager 2022). Corrections based on off-policy evaluation or on differences of -values assume a stationary environment, while real systems have time-varying dynamics and the experimenter observes a single trajectory.
Johari, Peng and Xing propose the truncated policy gradient (TPG) estimator: each instantaneous outcome in the difference-in-means estimator is replaced by the sum of the next outcomes. The paper shows that this estimates, without bias, the derivative of a truncated policy value, and derives bias and variance bounds, a central limit theorem and a consistent variance estimator in nonstationary Markovian environments. This mission formalizes those statements.
Setting
Time is (the paper's time ). The state space is finite and the action is control or treatment. For each time and action there is a transition matrix with ; the matrices may change arbitrarily with , which is the nonstationarity. The initial state has distribution . The reward is drawn from a distribution on , independently of everything else given , and for all . Write .
The policy assigns treatment with probability at every time, independently of everything else. is all-treatment, is all-control, and the experiment runs . Write and for expectation under . The value function and the global average treatment effect (GATE) are
The TPG estimator with truncation size is
so is the difference-in-means estimator.
Two quantities control the bounds. The mixing assumption (Assumption 1) asks for with for all , all and all probability vectors on , where . The kernel deviation is .
Formalization targets
Goal: Theorem 1, bias and variance of the TPG estimator
There are absolute constants such that for every environment, every , every and every and as above,
The constants are left unspecified, as in the paper's statement, so an improvement of the constants does not invalidate the goal.
Explicit constants: Propositions 5 and 6
For data collected under with , the paper gives both bounds with explicit constants, for the TPG estimator and for a reward-corrected variant. At , Proposition 5 reads
with .
Policy-gradient identities: Propositions 1–4
and its truncated analogue are differentiable at , with derivative equal to the horizon average of differences of (-truncated) -values, and equals the corresponding derivative for every . Without the mixing assumption, the untruncated estimator satisfies and .
Asymptotics: Theorem 2, Lemmas 1–5 and Corollary 1
For fixed , under mixing at all times, a positive limit of the normalized variance (Assumption 2) and a Cesàro mean-stability condition (Assumption 3),
where is a Newey–West estimator with bandwidth , . The supporting statements are a covariance inequality under strong mixing, the bound on the mixing coefficients of the experimental process and its consequence for the summands of the estimator, the central limit theorem alone, and consistency of the ideal and of the feasible variance estimators.
What the results give
Theorem 1 separates two error sources: a term of second order in that does not grow with , and a term that decays geometrically in . Together with Proposition 2 it shows what truncation buys: a variance bound of order instead of order , at the price of a bias term of order . Theorem 2 supplies standard errors for the estimator from a single nonstationary trajectory.
All results of the paper are proved on paper; none has a machine-checked proof. The work of this mission is the formal proofs of the stated results. The definition layer (a finite-state nonstationary Markov decision process with real rewards, its trajectory law under time-varying randomization, total-variation contraction, strong-mixing windows, a Newey–West estimator) can be reused for other results on experiments with Markovian interference.
Where the difficulty lies
The first idea is to bound by the second derivative of on . Every pair of times contributes to that second derivative, so this route gives the of Proposition 2 and nothing uniform in the horizon. Theorem 1 is uniform in , and its bound has no term of first order in beyond the truncation term; Proposition 5 shows that such a term is present at every allocation . Formal proofs have to handle ordered products of time-varying stochastic matrices and signed measures of total mass zero, with a contraction that is assumed one step at a time.
The variance bound and Theorem 2 concern a dependent, non-identically distributed sequence observed once. Mathlib has no central limit theorem for nonhomogeneous Markov chains and no covariance inequality for strongly mixing sequences; the paper relies on Arlotto and Steele (2016) for the former and on an inequality from Doukhan (1994) for the latter.
Formalization scope
TPG.Env S packages for a finite type S. Kernels are real matrices with nonnegative entries and rows summing to one, indexed by all ; a statement with horizon uses only the times below . A trajectory is a function Fin T → S × Bool × ℝ, and Env.trajLaw is its law for an arbitrary sequence of treatment probabilities, built as a finite mixture over state and action paths of product reward laws. , , and the -values are defined from this law, and expectations given are taken under the conditional measure. Rewards are bounded through the hypothesis E.RewardBound M; the standing assumptions of the paper enter each theorem as hypotheses, and S carries the discrete measurable structure.
Statements require and , as in the paper. Asymptotic statements compute the law of each statistic under the horizon- measure: convergence in distribution is tested against bounded continuous functions, and convergence in probability is stated for each . The limit is a parameter constrained by Assumption 2. For the law of is not a probability law and no statement depends on it. The hypotheses are satisfiable for every , and : an environment with one state and a nonzero constant reward satisfies all of them, including Assumptions 2 and 3, so no statement is vacuous.
Not included: Definition 1 and Lemma 6 of the paper (Dobrushin coefficients and the Arlotto–Steele theorem on general Borel state spaces), the stationary difference-in- discussion of Appendix C, the constant-reward example showing that the variance order is attained, and the numerical studies. Formal statements of those, and auxiliary lemmas about Env.trajLaw, ordered matrix products and total-variation contraction, are welcome contributions.
Selected references
- R. Johari, T. Peng, W. Xing, Estimation of Treatment Effects Under Nonstationarity via the Truncated Policy Gradient Estimator, arXiv preprint, 2025–2026. https://arxiv.org/abs/2506.05308
- V. F. Farias, A. A. Li, T. Peng, A. Zheng, Markovian Interference in Experiments, Advances in Neural Information Processing Systems 35, 2022. https://arxiv.org/abs/2206.02371
- Y. Hu, S. Wager, Switchback Experiments under Geometric Mixing, arXiv preprint, 2022. https://arxiv.org/abs/2209.00197
- A. Arlotto, J. M. Steele, A Central Limit Theorem for Temporally Nonhomogeneous Markov Chains with Applications to Dynamic Programming, Mathematics of Operations Research 41(4), 2016. https://doi.org/10.1287/moor.2016.0784
- P. Doukhan, Mixing: Properties and Examples, Lecture Notes in Statistics 85, Springer, 1994. https://doi.org/10.1007/978-1-4612-2642-0