Theorem 1 — bias and variance bounds for the TPG estimator
ProvedTPG.theorem_1_bias_variance_boundsSetting. 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.
import Mathlib import Definitions.Def_TPG_Model import Definitions.Def_TPG_Estimators open MeasureTheory ProbabilityTheory open scoped BigOperators ENNReal
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 TPGRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back of TPG.theorem_1_bias_variance_bounds.
Logical form. The statement asserts: there exist two real numbers and , with and , such that for all of the data listed below, if the six hypotheses (H1)–(H6) hold, then both inequalities (I) and (II) hold. The two constants are chosen first and everything else is universally quantified after them, so and are absolute: they may not depend on the set , on the environment , or on , , , .
Universally quantified data, in this order.
-
A set (a type in the lowest universe) which is finite, equipped with a -algebra in which every singleton is measurable. (As is finite, this forces every subset of to be measurable.) Non-emptiness of is not assumed as a hypothesis.
-
An environment on . This is a package consisting of:
- for every natural number and every Boolean value (here and below = true, = false), a real matrix with all entries and every row summing to : for all ;
- a function with for all and ;
- for every and every Boolean , a Borel probability measure on .
-
Natural numbers and .
-
Real numbers and .
Hypotheses.
- (H1) .
- (H2) .
- (H3) .
- (H4) .
- (H5) ("mixing with parameter up to ") For every natural number with , every Boolean , and every pair of functions that are both probability vectors (all values and values summing to ),
- (H6) ("reward bound ") For every and every Boolean : .
Objects used in the conclusion.
Trajectory space. , the set of sequences indexed by the times , with the product -algebra (the given one on , the discrete one on , the Borel one on ). The coordinate maps are written , , for the three components of .
Trajectory law with constant parameter . For a state sequence and a Boolean sequence define the real weight
(The code writes this as three products over all time indices with indicator conditions "" and ""; for it equals the displayed expression. The transition from time to time uses the matrix with time index and the Boolean .) The measure on is the finite mixture
where is the unit point mass at and is the product measure over the time coordinates. A negative weight is replaced by . For (the only values used in this theorem are ) all weights are non-negative and sum to , and is the probability law under which: has distribution ; are independent of and i.i.d. with ; given the past, is drawn from row of ; and, given the whole sequences and , the are independent with . For the weight is . For the weight is unless every ; for it is unless every .
The estimator. For ,
The inner sum runs over the times from to .
The comparison quantity (called gate in the code).
The quantity (called delta in the code).
i.e. the largest, over times and states , of half the -distance between row of and row of . (The supremum is the real-number supremum with the convention that an empty supremum is ; under (H1), and because an environment can only exist on a non-empty , both index sets are finite and non-empty, so this is a maximum, and it lies in .)
Integral and variance. denotes the Lebesgue (Bochner) integral, which by convention is for a non-integrable integrand. The variance of a function under a measure is
computed as an integral with values in and then converted to a real number, with the value converted to . (Under (H6) every lies in almost surely for each of the measures above, so all integrands here are almost surely bounded.)
Conclusion. Under (H1)–(H6), both of the following hold.
(I)
(II)
Both inequalities are non-strict. The estimator's parameter and the sampling law's parameter are both the fixed number ; no other value of the parameter is covered.
Boundary and degenerate cases as the statement literally has them.
- Empty . If is empty there is no environment on (the condition cannot hold), so nothing is asserted for empty .
- Sign of . ranges over all reals. For the interval is empty, (H6) cannot hold, and nothing is asserted. For , (H6) says every is the point mass at , and both right-hand sides are .
- is allowed. Then the inner sum of the estimator is the single term , , and the right-hand side of (I) is .
- Large . For the window condition is just , so and give the same estimator; the right-hand sides still depend on . Values are excluded by (H2).
- Range of . is strictly between and ; and are excluded, so no denominator vanishes.
- Which matrices are constrained and which are used. The law involves only for . Hypothesis (H5) and the quantity involve for , i.e. they also involve , which does not enter the law. The matrices with appear nowhere. In particular for no transition matrix enters the law, while (H5) and concern .
- What measures. Only the transition matrices enter ; the measures and do not. When the right-hand side of (I) is , so (I) then asserts equality of the two quantities.
- The mixing hypothesis is a one-step condition imposed separately for each and each Boolean , over pairs of probability vectors only. If has exactly one element it holds for every (both sides are ).
- The last Boolean coordinate. enters no transition factor of the weight; it affects only the law of .
Confirmed by the mission captain (proposal self-audit).