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.
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 .
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.
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 .
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 .
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.
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.
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.
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.
namespace TPG
theorem theorem_1_bias_variance_bounds :
∃ C₁ C₂ : ℝ, 0 < C₁ ∧ 0 < C₂ ∧
∀ (S : Type) [Fintype S] [MeasurableSpace S] [MeasurableSingletonClass S]
(E : Env S) (T k : ℕ) (γ M : ℝ),
0 < T → k ≤ T → 0 < γ → γ < 1 → E.Mixing T γ → E.RewardBound M →
|(∫ ω, tpgEst (1 / 2) T k ω ∂(E.expLaw T (1 / 2))) - E.gate T|
≤ C₁ * ((1 - γ ^ k) / (1 - γ) ^ 2 * (E.delta T) ^ 2 * M
+ γ ^ k / (1 - γ) * E.delta T * M)
∧ variance (tpgEst (1 / 2) T k) (E.expLaw T (1 / 2))
≤ C₂ * (((k : ℝ) + 1) ^ 2 * M ^ 2 / (T : ℝ)
+ γ * ((k : ℝ) + 1) * M ^ 2 / ((T : ℝ) * (1 - γ))) := by sorry
end TPGSetting. is a finite state space and the action is control or treatment. Time is , which is the source's time . Under action at time the state moves according to a transition matrix , i.e. ; the matrices may depend on arbitrarily. The initial state has distribution , and the reward has distribution on , with for all and conditional independence from everything else given . Under the policy every action is treatment with probability , independently of everything else; , and refer to the law of the trajectory under .
Assumption 1 (mixing time) with constant : for every time , every action and every pair of probability vectors on , , where . The kernel deviation is .
The global average treatment effect is .
Let be the truncated policy gradient (TPG) estimator with truncation size , computed from one trajectory generated under the experimental policy :
Theorem. There are absolute constants , not depending on the state space, the environment, or , such that under Assumption 1, for every and every truncation size ,
The first term of the bias bound is the Taylor error of approximating a difference of policy values by a derivative, and the second is the mixing bias due to truncation. This is the main result of the source; it quantifies how the truncation size trades bias against variance.
Formalization Note The source states both bounds with . The formal statement renders this with two existentially quantified constants chosen before the state space, the environment and all parameters.
No open leaves. Every sub-goal is proved or awaiting decomposition.