Proposition 2 — bias and variance of the untruncated PG estimator, without mixing
ProvedTPG.proposition_2_untruncated_pgSetting. 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 .
The global average treatment effect is . The kernel deviation is with , and .
Let be the untruncated policy gradient estimator under ,
Proposition. No mixing assumption is imposed. There is an absolute constant , not depending on the state space, the environment, or , such that for every :
- ;
- the same bound holds for the derivative of itself, , hence for every unbiased estimator of ;
- .
This is the untruncated counterpart of Theorem 1: without mixing and truncation the bias bound grows quadratically and the variance bound linearly in the horizon.
Formalization Note The of the source is rendered by an existentially quantified constant chosen before the state space and the environment. Item 2 is stated for every real number that is a derivative of at .
import Mathlib import Definitions.Def_TPG_Model import Definitions.Def_TPG_Estimators open MeasureTheory ProbabilityTheory open scoped BigOperators ENNReal
namespace TPG
theorem proposition_2_untruncated_pg :
∃ C : ℝ, 0 < C ∧
∀ (S : Type) [Fintype S] [MeasurableSpace S] [MeasurableSingletonClass S]
(E : Env S) (T : ℕ) (M : ℝ),
0 < T → E.RewardBound M →
|(∫ ω, tpgEst (1 / 2) T T ω ∂(E.expLaw T (1 / 2))) - E.gate T|
≤ C * ((T : ℝ) ^ 2 * (E.delta T) ^ 2 * M)
∧ (∀ g : ℝ, HasDerivAt (fun θ : ℝ => E.J T θ) g (1 / 2) →
|g - E.gate T| ≤ C * ((T : ℝ) ^ 2 * (E.delta T) ^ 2 * M))
∧ variance (tpgEst (1 / 2) T T) (E.expLaw T (1 / 2))
≤ 2 * 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.proposition_2_untruncated_pg.
Logical form. The statement asserts: there exists a single real number with such that for all of the data listed below, if the two hypotheses (H1)–(H2) hold, then the three assertions (a) and (b) and (c) all hold. The constant is chosen first and everything else is universally quantified after it, so is absolute: it may not depend on the set , on the environment , on or on . The same is used in (a) and in (b). Assertion (c) contains no unspecified constant.
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 .
-
A natural number .
-
A real number .
Hypotheses.
- (H1) .
- (H2) ("reward bound ") For every and every Boolean : .
There is no other hypothesis. In particular no contraction or mixing condition on the matrices is assumed.
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 measure with constant parameter , defined for every real . 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 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 . For some weights are negative and are replaced by , and is then a finite measure that need not have total mass .
The estimator. For ,
This is the code's windowed estimator with window length parameter set equal to . Since every time index satisfies , the condition is the same as , so
The comparison quantity (called gate in the code).
The function . For every real ,
This is a function (for it is computed with the clipped measure described above).
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 (H2) every lies in almost surely for each of the measures above, so all integrands here are almost surely bounded.)
Conclusion. Under (H1)–(H2), all three of the following hold.
(a)
(b) For every real number : if the function has derivative at the point (ordinary two-sided derivative, i.e. as ), then
(c)
All inequalities are non-strict. The estimator's parameter and the sampling law's parameter in (a) and (c) are both the fixed number , and the derivative in (b) is taken at ; no other value of the parameter is covered.
Boundary and degenerate cases as the statement literally has them.
- Assertion (b) is conditional. It does not assert that is differentiable at . It says that any real number which is a derivative of at satisfies the bound; if had no derivative at , (b) would hold with nothing to check. (A derivative, when it exists, is unique, so (b) is a statement about at most one .) Only the values of near matter for this hypothesis, and for in no weight is clipped.
- 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, (H2) cannot hold, and nothing is asserted. For , (H2) says every is the point mass at , and all three right-hand sides are .
- Which matrices are constrained and which are used. The measures involve only for . The quantity involves for , i.e. it also involves , which does not enter any of the measures. The matrices with appear nowhere. In particular for no transition matrix enters the measures, while is computed from and .
- What measures. Only the transition matrices enter ; the measures and do not. When the right-hand sides of (a) and (b) are , so (a) then asserts equality and (b) asserts that any derivative equals .
- Form of the bounds. The right-hand side of (a) and (b) is times the product , with regarded as a real number. The right-hand side of (c) is ; it is not divided by and does not involve or .
- 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).