Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

TPG and reward-corrected estimators, QQQ-values and truncated policy values — eqs. (3), (7), (9)–(11), Appendices D–E

Definition
TPG_Estimators

by Wenqian Xing · Oct 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

causal-inferencemarkov-chainnonstationaritypolicy-gradienttreatment-effect

Estimators and population quantities of the source, built on the model of TPG_Model. Time is t=0,…,T−1t=0,\dots,T-1t=0,…,T−1 (the source's t+1t+1t+1), and Eθ\mathbb E_\thetaEθ​ is expectation under the Bernoulli randomization policy πθ\pi_\thetaπθ​.

  1. Score (score): sθ(z)=zθ−1−z1−θs_\theta(z)=\dfrac{z}{\theta}-\dfrac{1-z}{1-\theta}sθ​(z)=θz​−1−θ1−z​ for z∈{0,1}z\in\{0,1\}z∈{0,1}. At θ=1/2\theta=1/2θ=1/2 this is the weight 1{z=1}/(1/2)−1{z=0}/(1/2)\mathbf 1\{z=1\}/(1/2)-\mathbf 1\{z=0\}/(1/2)1{z=1}/(1/2)−1{z=0}/(1/2).

  2. TPG estimator (tpgEst θ T k), eqs. (3) and (11):

τ^θ,kTPG=1T∑u=0T−1sθ(Zu)∑t=umin⁡(u+k, T−1)Yt.\widehat\tau^{\mathrm{TPG}}_{\theta,k}=\frac1T\sum_{u=0}^{T-1}s_\theta(Z_u)\sum_{t=u}^{\min(u+k,\,T-1)}Y_t .τθ,kTPG​=T1​u=0∑T−1​sθ​(Zu​)t=u∑min(u+k,T−1)​Yt​.

The estimator τ^k\widehat\tau_kτk​ of the main text is the case θ=1/2\theta=1/2θ=1/2, and k=0k=0k=0 is the difference-in-means estimator.

  1. QQQ-values (Env.Q, Env.Qk), eqs. (7) and (10):
Qθu(z)=∑t=uT−1Eθ[Yt∣Zu=z],Qθu,k(z)=∑t=umin⁡(u+k, T−1)Eθ[Yt∣Zu=z].Q_\theta^{u}(z)=\sum_{t=u}^{T-1}\mathbb E_\theta[Y_t\mid Z_u=z],\qquad Q_\theta^{u,k}(z)=\sum_{t=u}^{\min(u+k,\,T-1)}\mathbb E_\theta[Y_t\mid Z_u=z].Qθu​(z)=t=u∑T−1​Eθ​[Yt​∣Zu​=z],Qθu,k​(z)=t=u∑min(u+k,T−1)​Eθ​[Yt​∣Zu​=z].
  1. Truncated policy value (Env.truncLaw, Env.Jk), eq. (9). For a reward time ttt, the hypothetical truncated policy uses treatment probability 1/21/21/2 at the times u<max⁡(0,t−k)u<\max(0,t-k)u<max(0,t−k) and θ\thetaθ from time max⁡(0,t−k)\max(0,t-k)max(0,t−k) on; Lθt,k\mathcal L_\theta^{t,k}Lθt,k​ is the law of YtY_tYt​ under it, and
Jk(θ)=1T∑t<TELθt,k[Yt].J_k(\theta)=\frac1T\sum_{t<T}\mathbb E_{\mathcal L_\theta^{t,k}}[Y_t].Jk​(θ)=T1​t<T∑​ELθt,k​​[Yt​].
  1. Matrix form for a general experimental allocation (Env.stateDist, Env.JkGen), Appendix D. With μqt=ρ⊤Pq0→t\mu_q^t=\rho^\top P_q^{0\to t}μqt​=ρ⊤Pq0→t​ the distribution of XtX_tXt​ under πq\pi_qπq​ and at=max⁡(0,t−k)a_t=\max(0,t-k)at​=max(0,t−k),
Jk,θ(q)=1T∑t<Tμθat Pqat→t rq.J_{k,\theta}(q)=\frac1T\sum_{t<T}\mu_\theta^{a_t}\,P_q^{a_t\to t}\,r_q .Jk,θ​(q)=T1​t<T∑​μθat​​Pqat​→t​rq​.
  1. Constants (Psi, Env.rDiffNorm): Ψk(γ)=∑j=0k−2(j+1)γj\Psi_k(\gamma)=\sum_{j=0}^{k-2}(j+1)\gamma^jΨk​(γ)=∑j=0k−2​(j+1)γj with Ψ0=Ψ1=0\Psi_0=\Psi_1=0Ψ0​=Ψ1​=0, and ∥r1−r0∥∞=sup⁡x∈S∣r(x,1)−r(x,0)∣\|r_1-r_0\|_\infty=\sup_{x\in S}|r(x,1)-r(x,0)|∥r1​−r0​∥∞​=supx∈S​∣r(x,1)−r(x,0)∣.

  2. Reward-corrected estimator (rcWeight, rcEst), Appendix E.1: with wθ(z)=(1−θ)zθ+θ(1−z)1−θw_\theta(z)=\dfrac{(1-\theta)z}{\theta}+\dfrac{\theta(1-z)}{1-\theta}wθ​(z)=θ(1−θ)z​+1−θθ(1−z)​,

τ^θ,kRC=1T∑u=0T−1sθ(Zu)[Yu+∑t=u+1min⁡(u+k, T−1)wθ(Zt) Yt].\widehat\tau^{\mathrm{RC}}_{\theta,k}=\frac1T\sum_{u=0}^{T-1}s_\theta(Z_u)\Bigl[Y_u+\sum_{t=u+1}^{\min(u+k,\,T-1)}w_\theta(Z_t)\,Y_t\Bigr].τθ,kRC​=T1​u=0∑T−1​sθ​(Zu​)[Yu​+t=u+1∑min(u+k,T−1)​wθ​(Zt​)Yt​].

These are the objects of Theorem 1 and Propositions 1–6.

Formalization Note Expectations given {Zu=z}\{Z_u=z\}{Zu​=z} are integrals against the conditional measure Pθ(⋅∣Zu=z)\mathbb P_\theta(\cdot\mid Z_u=z)Pθ​(⋅∣Zu​=z), which is the zero measure when Pθ(Zu=z)=0\mathbb P_\theta(Z_u=z)=0Pθ​(Zu​=z)=0; this happens only for θ∈{0,1}\theta\in\{0,1\}θ∈{0,1}. The truncated policy of item 4 keeps probability θ\thetaθ after time ttt, which does not affect the law of YtY_tYt​. In item 5, t−kt-kt−k is truncated subtraction of natural numbers, i.e. max⁡(0,t−k)\max(0,t-k)max(0,t−k). Scores and weights divide by θ\thetaθ and 1−θ1-\theta1−θ and are used only for θ∈(0,1)\theta\in(0,1)θ∈(0,1).

Definition code
import Mathlib
import Definitions.Def_TPG_Model

open MeasureTheory ProbabilityTheory
open scoped BigOperators ENNReal

namespace TPG

variable {S : Type} [Fintype S]

/-- Bernoulli assignment score `s_θ(z) = z/θ - (1 - z)/(1 - θ)`.
At `θ = 1/2` it is the weight `1{z = 1}/(1/2) - 1{z = 0}/(1/2)`. -/
noncomputable def score (θ : ℝ) (z : Bool) : ℝ :=
  if z then 1 / θ else -(1 / (1 - θ))

/-- Truncated policy gradient (TPG) estimator with truncation size `k` for data collected
under `π_θ`:
`(1/T) ∑_{u < T} s_θ(Z_u) ∑_{u ≤ t ≤ u + k, t < T} Y_t`.
The estimator `τ̂_k` of the main text is `tpgEst (1/2) T k`. -/
noncomputable def tpgEst (θ : ℝ) (T k : ℕ) (ω : Traj S T) : ℝ :=
  (1 / (T : ℝ)) * ∑ u : Fin T, score θ (Z u ω) *
    ∑ t : Fin T, if (u : ℕ) ≤ (t : ℕ) ∧ (t : ℕ) ≤ (u : ℕ) + k then Y t ω else 0

/-- `Q`-value of action `z` at time `u` under `π_θ`:
`Q_θ^u(z) = ∑_{u ≤ t < T} E_θ[Y_t | Z_u = z]`. -/
noncomputable def Env.Q [MeasurableSpace S] (E : Env S) (θ : ℝ) (T : ℕ) (u : Fin T)
    (z : Bool) : ℝ :=
  ∑ t : Fin T, if (u : ℕ) ≤ (t : ℕ) then
    ∫ ω, Y t ω ∂(ProbabilityTheory.cond (E.expLaw T θ) {ω | Z u ω = z}) else 0

/-- Truncated `Q`-value of action `z` at time `u` under `π_θ`:
`Q_θ^{u,k}(z) = ∑_{u ≤ t ≤ u + k, t < T} E_θ[Y_t | Z_u = z]`. -/
noncomputable def Env.Qk [MeasurableSpace S] (E : Env S) (θ : ℝ) (T k : ℕ) (u : Fin T)
    (z : Bool) : ℝ :=
  ∑ t : Fin T, if (u : ℕ) ≤ (t : ℕ) ∧ (t : ℕ) ≤ (u : ℕ) + k then
    ∫ ω, Y t ω ∂(ProbabilityTheory.cond (E.expLaw T θ) {ω | Z u ω = z}) else 0

/-- Law of the trajectory under the hypothetical truncated policy for reward time `t`:
actions at times `u` with `u + k < t` are treatment with probability `1/2`, and actions at
all later times are treatment with probability `θ`. -/
noncomputable def Env.truncLaw [MeasurableSpace S] (E : Env S) (T k t : ℕ) (θ : ℝ) :
    Measure (Traj S T) :=
  E.trajLaw T (fun u => if u + k < t then 1 / 2 else θ)

/-- Truncated policy value function
`J_k(θ) = (1/T) ∑_t E_{L_θ^{t,k}}[Y_t]`. -/
noncomputable def Env.Jk [MeasurableSpace S] (E : Env S) (T k : ℕ) (θ : ℝ) : ℝ :=
  (1 / (T : ℝ)) * ∑ t : Fin T, ∫ ω, Y t ω ∂(E.truncLaw T k (t : ℕ) θ)

/-- Row distribution `μ_q^t = ρᵀ P_q^{0 → t}` of the state at time `t` under `π_q`. -/
noncomputable def Env.stateDist [DecidableEq S] (E : Env S) (q : ℝ) (t : ℕ) : S → ℝ :=
  Matrix.vecMul E.ρ (E.PProd q 0 t)

/-- Hypothetical truncated policy value under the experimental allocation `θ`:
`J_{k,θ}(q) = (1/T) ∑_{t < T} μ_θ^{a_t} P_q^{a_t → t} r_q` with `a_t = max(0, t - k)`. -/
noncomputable def Env.JkGen [DecidableEq S] (E : Env S) (T k : ℕ) (θ q : ℝ) : ℝ :=
  (1 / (T : ℝ)) * ∑ t : Fin T,
    dotProduct
      (Matrix.vecMul (E.stateDist θ ((t : ℕ) - k)) (E.PProd q ((t : ℕ) - k) (t : ℕ)))
      (E.rMix q)

/-- `Ψ_k(γ) = ∑_{j=0}^{k-2} (j + 1) γ^j`, with `Ψ_0 = Ψ_1 = 0`. -/
noncomputable def Psi (k : ℕ) (γ : ℝ) : ℝ :=
  ∑ j ∈ Finset.range k, if j + 2 ≤ k then ((j : ℝ) + 1) * γ ^ j else 0

/-- `‖r_1 - r_0‖_∞ = sup_x |r(x, 1) - r(x, 0)|`. -/
noncomputable def Env.rDiffNorm (E : Env S) : ℝ :=
  ⨆ x : S, |E.r true x - E.r false x|

/-- Additional importance weight of the reward-corrected estimator,
`w_θ(z) = (1 - θ) z / θ + θ (1 - z) / (1 - θ)`. -/
noncomputable def rcWeight (θ : ℝ) (z : Bool) : ℝ :=
  if z then (1 - θ) / θ else θ / (1 - θ)

/-- Reward-corrected (RC) estimator
`(1/T) ∑_{u < T} s_θ(Z_u) [Y_u + ∑_{u < t ≤ u + k, t < T} w_θ(Z_t) Y_t]`. -/
noncomputable def rcEst (θ : ℝ) (T k : ℕ) (ω : Traj S T) : ℝ :=
  (1 / (T : ℝ)) * ∑ u : Fin T, score θ (Z u ω) *
    (Y u ω + ∑ t : Fin T,
      if (u : ℕ) < (t : ℕ) ∧ (t : ℕ) ≤ (u : ℕ) + k then rcWeight θ (Z t ω) * Y t ω else 0)

end TPG
Source
Johari, Peng, Xing, Estimation of Treatment Effects Under Nonstationarity via the Truncated Policy Gradient Estimator, revised manuscript of October 2026 (revision of arXiv:2506.05308v3, https://arxiv.org/abs/2506.05308); numbering follows the revised manuscript. eq. (3), p. 11 (TPG estimator); eq. (7), p. 13 (Q-values); eqs. (9)–(10), p. 15 (truncated policy value, truncated Q-values); Appendix D, pp. 31–32, eq. (11) (score, general-θ TPG, J_{k,θ}, Ψ_k); Appendix E.1, p. 33 (reward-corrected estimator).
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Read-back: definition file TPG_Estimators (namespace TPG)

Twelve declarations, in file order. Each block below is self-contained and restates everything it uses.


score (TPG.score). Inputs: a real number θ\thetaθ and a Boolean zzz. Output: the real number

scoreθ(true)=1θ,scoreθ(false)=−11−θ.\mathrm{score}_\theta(\mathsf{true})=\frac{1}{\theta},\qquad \mathrm{score}_\theta(\mathsf{false})=-\frac{1}{1-\theta}.scoreθ​(true)=θ1​,scoreθ​(false)=−1−θ1​.

There is no hypothesis on θ\thetaθ: it is an arbitrary real number, so θ=0\theta=0θ=0, θ=1\theta=1θ=1, θ<0\theta<0θ<0 and θ>1\theta>1θ>1 are all allowed. Division is the library's total division on R\mathbb{R}R, in which 1/0=01/0=01/0=0. Consequently score0(true)=0\mathrm{score}_0(\mathsf{true})=0score0​(true)=0 (while score0(false)=−1\mathrm{score}_0(\mathsf{false})=-1score0​(false)=−1), and score1(false)=0\mathrm{score}_1(\mathsf{false})=0score1​(false)=0 (while score1(true)=1\mathrm{score}_1(\mathsf{true})=1score1​(true)=1). For θ>1\theta>1θ>1 the value scoreθ(false)=−1/(1−θ)\mathrm{score}_\theta(\mathsf{false})=-1/(1-\theta)scoreθ​(false)=−1/(1−θ) is positive, and for θ<0\theta<0θ<0 the value scoreθ(true)=1/θ\mathrm{score}_\theta(\mathsf{true})=1/\thetascoreθ​(true)=1/θ is negative; the formulas are applied exactly as written. The definition involves no state space, no environment and no probability measure.


tpgEst (TPG.tpgEst). Inputs: a type SSS (implicit; the file's ambient context declares SSS to be a finite type, but this formula makes no use of finiteness and involves no σ\sigmaσ-algebra on SSS); a real number θ\thetaθ (no hypothesis: any real); natural numbers TTT and kkk (either may be 000); and a trajectory ω\omegaω of length TTT, meaning a function assigning to each index t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} a triple ω(t)=(Xt(ω),Zt(ω),Yt(ω))\omega(t)=(X_t(\omega),Z_t(\omega),Y_t(\omega))ω(t)=(Xt​(ω),Zt​(ω),Yt​(ω)) with Xt(ω)∈SX_t(\omega)\in SXt​(ω)∈S, Zt(ω)Z_t(\omega)Zt​(ω) a Boolean and Yt(ω)∈RY_t(\omega)\in\mathbb{R}Yt​(ω)∈R. Output: the real number

tpgEstθ,T,k(ω)=1T∑u=0T−1σθ(Zu(ω))⋅(∑t=umin⁡(u+k,T−1)Yt(ω)),\mathrm{tpgEst}_{\theta,T,k}(\omega)=\frac{1}{T}\sum_{u=0}^{T-1}\sigma_\theta\big(Z_u(\omega)\big)\cdot\Bigg(\sum_{t=u}^{\min(u+k,T-1)}Y_t(\omega)\Bigg),tpgEstθ,T,k​(ω)=T1​u=0∑T−1​σθ​(Zu​(ω))⋅(t=u∑min(u+k,T−1)​Yt​(ω)),

where σθ(true)=1/θ\sigma_\theta(\mathsf{true})=1/\thetaσθ​(true)=1/θ and σθ(false)=−1/(1−θ)\sigma_\theta(\mathsf{false})=-1/(1-\theta)σθ​(false)=−1/(1−θ) (the function score of the same file), with the convention 1/0=01/0=01/0=0.

Literally, the inner sum ranges over all indices t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} and keeps Yt(ω)Y_t(\omega)Yt​(ω) exactly when u≤tu\le tu≤t and t≤u+kt\le u+kt≤u+k (both inequalities non-strict), contributing 000 otherwise. So the inner sum includes the term t=ut=ut=u itself, has at most k+1k+1k+1 terms, and is cut off at the last index T−1T-1T−1: indices t≥Tt\ge Tt≥T do not exist and nothing replaces them. The addition u+ku+ku+k is ordinary addition of natural numbers. This is a deterministic function of the single trajectory ω\omegaω; no probability measure or expectation appears, and the state components Xt(ω)X_t(\omega)Xt​(ω) are not used.

Edge cases, as the formula literally evaluates:

  • T=0T=0T=0: the outer sum is empty and the prefactor is 1/0=01/0=01/0=0, so the value is 000.
  • k=0k=0k=0: the inner sum is the single term Yu(ω)Y_u(\omega)Yu​(ω).
  • k≥T−1k\ge T-1k≥T−1: the inner sum is ∑t=uT−1Yt(ω)\sum_{t=u}^{T-1}Y_t(\omega)∑t=uT−1​Yt​(ω) for every uuu.
  • θ=0\theta=0θ=0: σ0(true)=0\sigma_0(\mathsf{true})=0σ0​(true)=0 and σ0(false)=−1\sigma_0(\mathsf{false})=-1σ0​(false)=−1, so indices uuu with Zu(ω)=trueZ_u(\omega)=\mathsf{true}Zu​(ω)=true contribute 000.
  • θ=1\theta=1θ=1: σ1(true)=1\sigma_1(\mathsf{true})=1σ1​(true)=1 and σ1(false)=0\sigma_1(\mathsf{false})=0σ1​(false)=0, so indices uuu with Zu(ω)=falseZ_u(\omega)=\mathsf{false}Zu​(ω)=false contribute 000.
  • θ∉[0,1]\theta\notin[0,1]θ∈/[0,1]: allowed; the formula is used as written.

Env.Q (TPG.Env.Q). Inputs: a finite type SSS carrying a σ\sigmaσ-algebra (the σ\sigmaσ-algebra is an arbitrary parameter: it is not required to be discrete or to contain the singletons); an environment EEE on SSS; a real number θ\thetaθ (no hypothesis: any real); a natural number TTT; an index u∈{0,…,T−1}u\in\lbrace 0,\dots,T-1\rbraceu∈{0,…,T−1} (so the existence of uuu forces T≥1T\ge 1T≥1); and a Boolean zzz. Output: a real number.

What an environment is. An environment EEE on SSS consists of: (a) for every natural number sss (all of N\mathbb{N}N, with no horizon) and every Boolean bbb, a real matrix PsbP_s^{b}Psb​ with rows and columns indexed by SSS, all of whose entries are ≥0\ge 0≥0 and each of whose rows sums to one, ∑x′∈SPsb(x,x′)=1\sum_{x'\in S}P_s^{b}(x,x')=1∑x′∈S​Psb​(x,x′)=1 for every x∈Sx\in Sx∈S; (b) a function ρ:S→R\rho:S\to\mathbb{R}ρ:S→R with ρ(x)≥0\rho(x)\ge 0ρ(x)≥0 for every xxx and ∑x∈Sρ(x)=1\sum_{x\in S}\rho(x)=1∑x∈S​ρ(x)=1 (which forces SSS to be nonempty); (c) for every x∈Sx\in Sx∈S and every Boolean bbb, a Borel probability measure Rx,bR_{x,b}Rx,b​ on R\mathbb{R}R, about which nothing else (support, moments) is assumed.

The trajectory space and the law used. Let B={true,false}\mathbb{B}=\lbrace\mathsf{true},\mathsf{false}\rbraceB={true,false} and let ΩT\Omega_TΩT​ be the set of all functions ω\omegaω from {0,…,T−1}\lbrace 0,\dots,T-1\rbrace{0,…,T−1} to S×B×RS\times\mathbb{B}\times\mathbb{R}S×B×R, with the product σ\sigmaσ-algebra (the given one on SSS, the discrete one on B\mathbb{B}B, the Borel one on R\mathbb{R}R); write ω(t)=(Xt(ω),Zt(ω),Yt(ω))\omega(t)=(X_t(\omega),Z_t(\omega),Y_t(\omega))ω(t)=(Xt​(ω),Zt​(ω),Yt​(ω)). Each pair (x,b)(x,b)(x,b) with x∈STx\in S^{T}x∈ST, b∈BTb\in\mathbb{B}^{T}b∈BT gets the real weight

wθ(x,b)=ρ(x0)⋅∏s=0T−2Psbs(xs,xs+1)⋅∏s=0T−1β(bs),β(true)=θ,β(false)=1−θ,w_\theta(x,b)=\rho(x_0)\cdot\prod_{s=0}^{T-2}P_s^{b_s}(x_s,x_{s+1})\cdot\prod_{s=0}^{T-1}\beta(b_s),\qquad \beta(\mathsf{true})=\theta,\quad\beta(\mathsf{false})=1-\theta,wθ​(x,b)=ρ(x0​)⋅s=0∏T−2​Psbs​​(xs​,xs+1​)⋅s=0∏T−1​β(bs​),β(true)=θ,β(false)=1−θ,

and μθ\mu_\thetaμθ​ is the measure on ΩT\Omega_TΩT​

μθ=∑(x,b)∈ST×BTmax⁡(wθ(x,b),0)⋅⨂s=0T−1(δxs⊗δbs⊗Rxs,bs).\mu_\theta=\sum_{(x,b)\in S^{T}\times\mathbb{B}^{T}}\max\big(w_\theta(x,b),0\big)\cdot\bigotimes_{s=0}^{T-1}\Big(\delta_{x_s}\otimes\delta_{b_s}\otimes R_{x_s,b_s}\Big).μθ​=(x,b)∈ST×BT∑​max(wθ​(x,b),0)⋅s=0⨂T−1​(δxs​​⊗δbs​​⊗Rxs​,bs​​).

Under each summand the coordinates (Xs,Zs)(X_s,Z_s)(Xs​,Zs​) are the fixed values (xs,bs)(x_s,b_s)(xs​,bs​) and the YsY_sYs​ are independent with YsY_sYs​ distributed as Rxs,bsR_{x_s,b_s}Rxs​,bs​​. A negative weight is replaced by 000, with no renormalisation; since ρ\rhoρ and the matrices are entrywise nonnegative, this happens only if θ∉[0,1]\theta\notin[0,1]θ∈/[0,1], and then μθ\mu_\thetaμθ​ need not have total mass 111. For θ∈[0,1]\theta\in[0,1]θ∈[0,1] no clipping occurs and μθ\mu_\thetaμθ​ is a probability measure.

The definition. Put Au,z={ω∈ΩT:Zu(ω)=z}A_{u,z}=\lbrace\omega\in\Omega_T: Z_u(\omega)=z\rbraceAu,z​={ω∈ΩT​:Zu​(ω)=z} and let νu,z\nu_{u,z}νu,z​ be the conditional measure νu,z(B)=μθ(Au,z)−1⋅μθ(Au,z∩B)\nu_{u,z}(B)=\mu_\theta(A_{u,z})^{-1}\cdot\mu_\theta(A_{u,z}\cap B)νu,z​(B)=μθ​(Au,z​)−1⋅μθ​(Au,z​∩B). Then

Qθ,TE(u,z)=∑t=uT−1∫ΩTYt dνu,z.Q^{E}_{\theta,T}(u,z)=\sum_{t=u}^{T-1}\int_{\Omega_T}Y_t\ \mathrm{d}\nu_{u,z}.Qθ,TE​(u,z)=t=u∑T−1​∫ΩT​​Yt​ dνu,z​.

Literally the sum ranges over all t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} and the summand is the integral when u≤tu\le tu≤t (non-strict, so t=ut=ut=u is included) and 000 otherwise. The sum is not divided by TTT and has no upper cut-off other than T−1T-1T−1.

Conventions that decide the value in degenerate cases:

  • If μθ(Au,z)=0\mu_\theta(A_{u,z})=0μθ​(Au,z​)=0, the library's conditional measure νu,z\nu_{u,z}νu,z​ is the zero measure, every integral against it is 000, and so Qθ,TE(u,z)=0Q^{E}_{\theta,T}(u,z)=0Qθ,TE​(u,z)=0. This occurs for instance when θ=0\theta=0θ=0 and z=truez=\mathsf{true}z=true, and when θ=1\theta=1θ=1 and z=falsez=\mathsf{false}z=false. (For θ∈[0,1]\theta\in[0,1]θ∈[0,1] one has μθ(Au,true)=θ\mu_\theta(A_{u,\mathsf{true}})=\thetaμθ​(Au,true​)=θ and μθ(Au,false)=1−θ\mu_\theta(A_{u,\mathsf{false}})=1-\thetaμθ​(Au,false​)=1−θ.)
  • Each integral is a Bochner integral, which by convention equals 000 when YtY_tYt​ is not integrable with respect to νu,z\nu_{u,z}νu,z​. No integrability or boundedness of the measures Rx,bR_{x,b}Rx,b​ is assumed in this definition.
  • For θ∉[0,1]\theta\notin[0,1]θ∈/[0,1] the definition still applies, to the clipped measure μθ\mu_\thetaμθ​ described above.

Env.Qk (TPG.Env.Qk). Inputs: a finite type SSS carrying a σ\sigmaσ-algebra (an arbitrary parameter: not required to be discrete or to contain the singletons); an environment EEE on SSS; a real number θ\thetaθ (no hypothesis: any real); natural numbers TTT and kkk (kkk may be 000); an index u∈{0,…,T−1}u\in\lbrace 0,\dots,T-1\rbraceu∈{0,…,T−1} (so T≥1T\ge 1T≥1); and a Boolean zzz. Output: a real number.

What an environment is. An environment EEE on SSS consists of: (a) for every natural number sss (all of N\mathbb{N}N, with no horizon) and every Boolean bbb, a real matrix PsbP_s^{b}Psb​ with rows and columns indexed by SSS, all of whose entries are ≥0\ge 0≥0 and each of whose rows sums to one, ∑x′∈SPsb(x,x′)=1\sum_{x'\in S}P_s^{b}(x,x')=1∑x′∈S​Psb​(x,x′)=1 for every x∈Sx\in Sx∈S; (b) a function ρ:S→R\rho:S\to\mathbb{R}ρ:S→R with ρ(x)≥0\rho(x)\ge 0ρ(x)≥0 for every xxx and ∑x∈Sρ(x)=1\sum_{x\in S}\rho(x)=1∑x∈S​ρ(x)=1 (which forces SSS to be nonempty); (c) for every x∈Sx\in Sx∈S and every Boolean bbb, a Borel probability measure Rx,bR_{x,b}Rx,b​ on R\mathbb{R}R, about which nothing else is assumed.

The trajectory space and the law used. Let B={true,false}\mathbb{B}=\lbrace\mathsf{true},\mathsf{false}\rbraceB={true,false} and let ΩT\Omega_TΩT​ be the set of all functions ω\omegaω from {0,…,T−1}\lbrace 0,\dots,T-1\rbrace{0,…,T−1} to S×B×RS\times\mathbb{B}\times\mathbb{R}S×B×R, with the product σ\sigmaσ-algebra (the given one on SSS, the discrete one on B\mathbb{B}B, the Borel one on R\mathbb{R}R); write ω(t)=(Xt(ω),Zt(ω),Yt(ω))\omega(t)=(X_t(\omega),Z_t(\omega),Y_t(\omega))ω(t)=(Xt​(ω),Zt​(ω),Yt​(ω)). Each pair (x,b)(x,b)(x,b) with x∈STx\in S^{T}x∈ST, b∈BTb\in\mathbb{B}^{T}b∈BT gets the real weight

wθ(x,b)=ρ(x0)⋅∏s=0T−2Psbs(xs,xs+1)⋅∏s=0T−1β(bs),β(true)=θ,β(false)=1−θ,w_\theta(x,b)=\rho(x_0)\cdot\prod_{s=0}^{T-2}P_s^{b_s}(x_s,x_{s+1})\cdot\prod_{s=0}^{T-1}\beta(b_s),\qquad \beta(\mathsf{true})=\theta,\quad\beta(\mathsf{false})=1-\theta,wθ​(x,b)=ρ(x0​)⋅s=0∏T−2​Psbs​​(xs​,xs+1​)⋅s=0∏T−1​β(bs​),β(true)=θ,β(false)=1−θ,

and μθ\mu_\thetaμθ​ is the measure on ΩT\Omega_TΩT​

μθ=∑(x,b)∈ST×BTmax⁡(wθ(x,b),0)⋅⨂s=0T−1(δxs⊗δbs⊗Rxs,bs).\mu_\theta=\sum_{(x,b)\in S^{T}\times\mathbb{B}^{T}}\max\big(w_\theta(x,b),0\big)\cdot\bigotimes_{s=0}^{T-1}\Big(\delta_{x_s}\otimes\delta_{b_s}\otimes R_{x_s,b_s}\Big).μθ​=(x,b)∈ST×BT∑​max(wθ​(x,b),0)⋅s=0⨂T−1​(δxs​​⊗δbs​​⊗Rxs​,bs​​).

Under each summand the coordinates (Xs,Zs)(X_s,Z_s)(Xs​,Zs​) are the fixed values (xs,bs)(x_s,b_s)(xs​,bs​) and the YsY_sYs​ are independent with YsY_sYs​ distributed as Rxs,bsR_{x_s,b_s}Rxs​,bs​​. A negative weight is replaced by 000, with no renormalisation; this happens only if θ∉[0,1]\theta\notin[0,1]θ∈/[0,1], and then μθ\mu_\thetaμθ​ need not have total mass 111. For θ∈[0,1]\theta\in[0,1]θ∈[0,1] no clipping occurs and μθ\mu_\thetaμθ​ is a probability measure.

The definition. Put Au,z={ω∈ΩT:Zu(ω)=z}A_{u,z}=\lbrace\omega\in\Omega_T: Z_u(\omega)=z\rbraceAu,z​={ω∈ΩT​:Zu​(ω)=z} and let νu,z\nu_{u,z}νu,z​ be the conditional measure νu,z(B)=μθ(Au,z)−1⋅μθ(Au,z∩B)\nu_{u,z}(B)=\mu_\theta(A_{u,z})^{-1}\cdot\mu_\theta(A_{u,z}\cap B)νu,z​(B)=μθ​(Au,z​)−1⋅μθ​(Au,z​∩B). Then

Qθ,TE,k(u,z)=∑t=umin⁡(u+k,T−1)∫ΩTYt dνu,z.Q^{E,k}_{\theta,T}(u,z)=\sum_{t=u}^{\min(u+k,T-1)}\int_{\Omega_T}Y_t\ \mathrm{d}\nu_{u,z}.Qθ,TE,k​(u,z)=t=u∑min(u+k,T−1)​∫ΩT​​Yt​ dνu,z​.

Literally the sum ranges over all t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} and the summand is the integral when u≤tu\le tu≤t and t≤u+kt\le u+kt≤u+k (both non-strict) and 000 otherwise. So the window starts at t=ut=ut=u (included), contains at most k+1k+1k+1 indices, and is cut off at the last index T−1T-1T−1. The sum is not divided by TTT. The conditioning is on the single coordinate ZuZ_uZu​ and is the same for every ttt in the window. This is the same expression as Env.Q of the same file except for the extra upper constraint t≤u+kt\le u+kt≤u+k; for k≥T−1−uk\ge T-1-uk≥T−1−u the two coincide, and for k=0k=0k=0 the sum is the single term ∫Yu dνu,z\int Y_u\ \mathrm{d}\nu_{u,z}∫Yu​ dνu,z​.

Conventions that decide the value in degenerate cases:

  • If μθ(Au,z)=0\mu_\theta(A_{u,z})=0μθ​(Au,z​)=0, the library's conditional measure νu,z\nu_{u,z}νu,z​ is the zero measure, every integral against it is 000, and the value is 000. This occurs for instance when θ=0\theta=0θ=0 and z=truez=\mathsf{true}z=true, and when θ=1\theta=1θ=1 and z=falsez=\mathsf{false}z=false. (For θ∈[0,1]\theta\in[0,1]θ∈[0,1] one has μθ(Au,true)=θ\mu_\theta(A_{u,\mathsf{true}})=\thetaμθ​(Au,true​)=θ and μθ(Au,false)=1−θ\mu_\theta(A_{u,\mathsf{false}})=1-\thetaμθ​(Au,false​)=1−θ.)
  • Each integral is a Bochner integral, which by convention equals 000 when YtY_tYt​ is not integrable with respect to νu,z\nu_{u,z}νu,z​. No integrability or boundedness of the measures Rx,bR_{x,b}Rx,b​ is assumed in this definition.
  • For θ∉[0,1]\theta\notin[0,1]θ∈/[0,1] the definition still applies, to the clipped measure μθ\mu_\thetaμθ​ described above.

Env.truncLaw (TPG.Env.truncLaw). Inputs: a finite type SSS carrying a σ\sigmaσ-algebra (an arbitrary parameter: not required to be discrete or to contain the singletons); an environment EEE on SSS; three natural numbers TTT, kkk, ttt (in this order; ttt is an arbitrary natural number and is not required to be smaller than TTT); and a real number θ\thetaθ (no hypothesis: any real). Output: a measure on the trajectory space ΩT\Omega_TΩT​.

What an environment is. An environment EEE on SSS consists of: (a) for every natural number sss (all of N\mathbb{N}N, with no horizon) and every Boolean bbb, a real matrix PsbP_s^{b}Psb​ with rows and columns indexed by SSS, all of whose entries are ≥0\ge 0≥0 and each of whose rows sums to one, ∑x′∈SPsb(x,x′)=1\sum_{x'\in S}P_s^{b}(x,x')=1∑x′∈S​Psb​(x,x′)=1 for every x∈Sx\in Sx∈S; (b) a function ρ:S→R\rho:S\to\mathbb{R}ρ:S→R with ρ(x)≥0\rho(x)\ge 0ρ(x)≥0 for every xxx and ∑x∈Sρ(x)=1\sum_{x\in S}\rho(x)=1∑x∈S​ρ(x)=1 (which forces SSS to be nonempty); (c) for every x∈Sx\in Sx∈S and every Boolean bbb, a Borel probability measure Rx,bR_{x,b}Rx,b​ on R\mathbb{R}R, about which nothing else is assumed.

The trajectory space. Let B={true,false}\mathbb{B}=\lbrace\mathsf{true},\mathsf{false}\rbraceB={true,false} and let ΩT\Omega_TΩT​ be the set of all functions ω\omegaω from {0,…,T−1}\lbrace 0,\dots,T-1\rbrace{0,…,T−1} to S×B×RS\times\mathbb{B}\times\mathbb{R}S×B×R, with the product σ\sigmaσ-algebra (the given one on SSS, the discrete one on B\mathbb{B}B, the Borel one on R\mathbb{R}R).

The definition. Define a sequence of real numbers (qs)s∈N(q_s)_{s\in\mathbb{N}}(qs​)s∈N​ by

qs=12if s+k<t,qs=θif s+k≥t.q_s=\tfrac12\quad\text{if } s+k<t,\qquad q_s=\theta\quad\text{if } s+k\ge t.qs​=21​if s+k<t,qs​=θif s+k≥t.

Each pair (x,b)(x,b)(x,b) with x∈STx\in S^{T}x∈ST, b∈BTb\in\mathbb{B}^{T}b∈BT gets the real weight

w(x,b)=ρ(x0)⋅∏s=0T−2Psbs(xs,xs+1)⋅∏s=0T−1βs(bs),βs(true)=qs,βs(false)=1−qs,w(x,b)=\rho(x_0)\cdot\prod_{s=0}^{T-2}P_s^{b_s}(x_s,x_{s+1})\cdot\prod_{s=0}^{T-1}\beta_s(b_s),\qquad \beta_s(\mathsf{true})=q_s,\quad\beta_s(\mathsf{false})=1-q_s,w(x,b)=ρ(x0​)⋅s=0∏T−2​Psbs​​(xs​,xs+1​)⋅s=0∏T−1​βs​(bs​),βs​(true)=qs​,βs​(false)=1−qs​,

and the output is the measure

μT,k,t,θE=∑(x,b)∈ST×BTmax⁡(w(x,b),0)⋅⨂s=0T−1(δxs⊗δbs⊗Rxs,bs).\mu^{E}_{T,k,t,\theta}=\sum_{(x,b)\in S^{T}\times\mathbb{B}^{T}}\max\big(w(x,b),0\big)\cdot\bigotimes_{s=0}^{T-1}\Big(\delta_{x_s}\otimes\delta_{b_s}\otimes R_{x_s,b_s}\Big).μT,k,t,θE​=(x,b)∈ST×BT∑​max(w(x,b),0)⋅s=0⨂T−1​(δxs​​⊗δbs​​⊗Rxs​,bs​​).

Under each summand the state and Boolean coordinates at index sss are the fixed values (xs,bs)(x_s,b_s)(xs​,bs​) and the real coordinates are independent, the one at index sss distributed as Rxs,bsR_{x_s,b_s}Rxs​,bs​​.

Points the formula literally entails:

  • The number 12\tfrac1221​ is a constant written in the definition, not a parameter. It is used at exactly those indices sss with s+k<ts+k<ts+k<t (strict), i.e. the indices more than kkk steps before ttt. Every other index uses θ\thetaθ, including s=ts=ts=t and all indices after ttt.
  • If t≤kt\le kt≤k, no index satisfies s+k<ts+k<ts+k<t, so qs=θq_s=\thetaqs​=θ for all sss and the measure is the one with constant sequence θ\thetaθ.
  • Only q0,…,qT−1q_0,\dots,q_{T-1}q0​,…,qT−1​ enter the formula.
  • A negative weight is replaced by 000, with no renormalisation; this can happen only if θ∉[0,1]\theta\notin[0,1]θ∈/[0,1] (the value 12\tfrac1221​ never produces a negative factor), and then the total mass need not be 111. For θ∈[0,1]\theta\in[0,1]θ∈[0,1] the measure is a probability measure.
  • The factor ρ(x0)\rho(x_0)ρ(x0​) is present only when T≥1T\ge 1T≥1. For T=0T=0T=0 all products are empty, the weight is 111, Ω0\Omega_0Ω0​ is a single point, and the measure is the unit mass on it.

Env.Jk (TPG.Env.Jk). Inputs: a finite type SSS carrying a σ\sigmaσ-algebra (an arbitrary parameter: not required to be discrete or to contain the singletons); an environment EEE on SSS; natural numbers TTT and kkk (either may be 000); and a real number θ\thetaθ (no hypothesis: any real). Output: a real number.

What an environment is. An environment EEE on SSS consists of: (a) for every natural number sss (all of N\mathbb{N}N, with no horizon) and every Boolean bbb, a real matrix PsbP_s^{b}Psb​ with rows and columns indexed by SSS, all of whose entries are ≥0\ge 0≥0 and each of whose rows sums to one, ∑x′∈SPsb(x,x′)=1\sum_{x'\in S}P_s^{b}(x,x')=1∑x′∈S​Psb​(x,x′)=1 for every x∈Sx\in Sx∈S; (b) a function ρ:S→R\rho:S\to\mathbb{R}ρ:S→R with ρ(x)≥0\rho(x)\ge 0ρ(x)≥0 for every xxx and ∑x∈Sρ(x)=1\sum_{x\in S}\rho(x)=1∑x∈S​ρ(x)=1 (which forces SSS to be nonempty); (c) for every x∈Sx\in Sx∈S and every Boolean bbb, a Borel probability measure Rx,bR_{x,b}Rx,b​ on R\mathbb{R}R, about which nothing else is assumed.

The trajectory space. Let B={true,false}\mathbb{B}=\lbrace\mathsf{true},\mathsf{false}\rbraceB={true,false} and let ΩT\Omega_TΩT​ be the set of all functions ω\omegaω from {0,…,T−1}\lbrace 0,\dots,T-1\rbrace{0,…,T−1} to S×B×RS\times\mathbb{B}\times\mathbb{R}S×B×R, with the product σ\sigmaσ-algebra (the given one on SSS, the discrete one on B\mathbb{B}B, the Borel one on R\mathbb{R}R); write Yt(ω)Y_t(\omega)Yt​(ω) for the real component of ω(t)\omega(t)ω(t).

The definition. For each t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} define the sequence qs(t)=12q^{(t)}_s=\tfrac12qs(t)​=21​ if s+k<ts+k<ts+k<t and qs(t)=θq^{(t)}_s=\thetaqs(t)​=θ if s+k≥ts+k\ge ts+k≥t, the weights

w(t)(x,b)=ρ(x0)⋅∏s=0T−2Psbs(xs,xs+1)⋅∏s=0T−1βs(t)(bs),βs(t)(true)=qs(t),βs(t)(false)=1−qs(t),w^{(t)}(x,b)=\rho(x_0)\cdot\prod_{s=0}^{T-2}P_s^{b_s}(x_s,x_{s+1})\cdot\prod_{s=0}^{T-1}\beta^{(t)}_s(b_s),\qquad \beta^{(t)}_s(\mathsf{true})=q^{(t)}_s,\quad\beta^{(t)}_s(\mathsf{false})=1-q^{(t)}_s,w(t)(x,b)=ρ(x0​)⋅s=0∏T−2​Psbs​​(xs​,xs+1​)⋅s=0∏T−1​βs(t)​(bs​),βs(t)​(true)=qs(t)​,βs(t)​(false)=1−qs(t)​,

for x∈STx\in S^{T}x∈ST, b∈BTb\in\mathbb{B}^{T}b∈BT, and the measure on ΩT\Omega_TΩT​

μ(t)=∑(x,b)∈ST×BTmax⁡(w(t)(x,b),0)⋅⨂s=0T−1(δxs⊗δbs⊗Rxs,bs)\mu^{(t)}=\sum_{(x,b)\in S^{T}\times\mathbb{B}^{T}}\max\big(w^{(t)}(x,b),0\big)\cdot\bigotimes_{s=0}^{T-1}\Big(\delta_{x_s}\otimes\delta_{b_s}\otimes R_{x_s,b_s}\Big)μ(t)=(x,b)∈ST×BT∑​max(w(t)(x,b),0)⋅s=0⨂T−1​(δxs​​⊗δbs​​⊗Rxs​,bs​​)

(this is Env.truncLaw of the same file, evaluated at T,k,t,θT,k,t,\thetaT,k,t,θ). Then

JkE(T,θ)=1T∑t=0T−1∫ΩTYt dμ(t).J_k^{E}(T,\theta)=\frac{1}{T}\sum_{t=0}^{T-1}\int_{\Omega_T}Y_t\ \mathrm{d}\mu^{(t)}.JkE​(T,θ)=T1​t=0∑T−1​∫ΩT​​Yt​ dμ(t).

So the ttt-th summand integrates the ttt-th real coordinate against a measure that itself depends on ttt: in μ(t)\mu^{(t)}μ(t), the indices sss with s+k<ts+k<ts+k<t use the constant 12\tfrac1221​ (written in the definition, not a parameter) and all other indices, including s≥ts\ge ts≥t, use θ\thetaθ.

Points the formula literally entails:

  • For every t≤kt\le kt≤k the sequence q(t)q^{(t)}q(t) is constantly θ\thetaθ; in particular if k≥T−1k\ge T-1k≥T−1 every μ(t)\mu^{(t)}μ(t) is the measure with constant sequence θ\thetaθ.
  • T=0T=0T=0: the sum is empty and the prefactor is 1/0=01/0=01/0=0, so the value is 000.
  • Each integral is a Bochner integral, equal to 000 by convention when YtY_tYt​ is not μ(t)\mu^{(t)}μ(t)-integrable. No integrability or boundedness of the measures Rx,bR_{x,b}Rx,b​ is assumed in this definition.
  • A negative weight is replaced by 000 with no renormalisation; this happens only if θ∉[0,1]\theta\notin[0,1]θ∈/[0,1], and then μ(t)\mu^{(t)}μ(t) need not have total mass 111.

Env.stateDist (TPG.Env.stateDist). Inputs: a finite type SSS with decidable equality (a technical requirement, used to form identity matrices; no σ\sigmaσ-algebra on SSS is involved); an environment EEE on SSS; a real number qqq (no hypothesis: any real); and a natural number ttt. Output: a function S→RS\to\mathbb{R}S→R.

What an environment is. An environment EEE on SSS consists of: (a) for every natural number sss (all of N\mathbb{N}N, with no horizon) and every Boolean bbb, a real matrix PsbP_s^{b}Psb​ with rows and columns indexed by SSS, all of whose entries are ≥0\ge 0≥0 and each of whose rows sums to one, ∑x′∈SPsb(x,x′)=1\sum_{x'\in S}P_s^{b}(x,x')=1∑x′∈S​Psb​(x,x′)=1 for every x∈Sx\in Sx∈S; (b) a function ρ:S→R\rho:S\to\mathbb{R}ρ:S→R with ρ(x)≥0\rho(x)\ge 0ρ(x)≥0 for every xxx and ∑x∈Sρ(x)=1\sum_{x\in S}\rho(x)=1∑x∈S​ρ(x)=1 (which forces SSS to be nonempty); (c) for every x∈Sx\in Sx∈S and every Boolean bbb, a Borel probability measure Rx,bR_{x,b}Rx,b​ on R\mathbb{R}R (not used by this definition).

The definition. For each natural number sss let Msq=q⋅Pstrue+(1−q)⋅PsfalseM^{q}_s=q\cdot P_s^{\mathsf{true}}+(1-q)\cdot P_s^{\mathsf{false}}Msq​=q⋅Pstrue​+(1−q)⋅Psfalse​, a real S×SS\times SS×S matrix. The output is the row vector ρ\rhoρ multiplied on the right by the ordered matrix product M0qM1q⋯Mt−1qM^{q}_0M^{q}_1\cdots M^{q}_{t-1}M0q​M1q​⋯Mt−1q​ (factors in increasing order of index, from left to right):

stateDistq,tE(x′)=∑x∈Sρ(x)⋅(M0qM1q⋯Mt−1q)(x,x′)(x′∈S).\mathrm{stateDist}^{E}_{q,t}(x')=\sum_{x\in S}\rho(x)\cdot\Big(M^{q}_0M^{q}_1\cdots M^{q}_{t-1}\Big)(x,x')\qquad(x'\in S).stateDistq,tE​(x′)=x∈S∑​ρ(x)⋅(M0q​M1q​⋯Mt−1q​)(x,x′)(x′∈S).

For t=0t=0t=0 the product is empty and equals the identity matrix, so the output is ρ\rhoρ itself. Since qqq is unrestricted, for q∉[0,1]q\notin[0,1]q∈/[0,1] the matrices MsqM^{q}_sMsq​ can have negative entries and the output need not be nonnegative; the formula is used as written. The same qqq is used at every step.


Env.JkGen (TPG.Env.JkGen). Inputs: a finite type SSS with decidable equality (a technical requirement, used to form identity matrices; no σ\sigmaσ-algebra on SSS is involved); an environment EEE on SSS; natural numbers TTT and kkk (either may be 000); and two real numbers θ\thetaθ and qqq, in this order (no hypothesis on either: any reals). Output: a real number.

What an environment is. An environment EEE on SSS consists of: (a) for every natural number sss (all of N\mathbb{N}N, with no horizon) and every Boolean bbb, a real matrix PsbP_s^{b}Psb​ with rows and columns indexed by SSS, all of whose entries are ≥0\ge 0≥0 and each of whose rows sums to one, ∑x′∈SPsb(x,x′)=1\sum_{x'\in S}P_s^{b}(x,x')=1∑x′∈S​Psb​(x,x′)=1 for every x∈Sx\in Sx∈S; (b) a function ρ:S→R\rho:S\to\mathbb{R}ρ:S→R with ρ(x)≥0\rho(x)\ge 0ρ(x)≥0 for every xxx and ∑x∈Sρ(x)=1\sum_{x\in S}\rho(x)=1∑x∈S​ρ(x)=1 (which forces SSS to be nonempty); (c) for every x∈Sx\in Sx∈S and every Boolean bbb, a Borel probability measure Rx,bR_{x,b}Rx,b​ on R\mathbb{R}R, about which nothing else is assumed.

Ingredients. For a real number aaa and a natural number sss let Msa=a⋅Pstrue+(1−a)⋅PsfalseM^{a}_s=a\cdot P_s^{\mathsf{true}}+(1-a)\cdot P_s^{\mathsf{false}}Msa​=a⋅Pstrue​+(1−a)⋅Psfalse​. For a Boolean bbb and x∈Sx\in Sx∈S let rb(x)=∫Ry dRx,b(y)r_b(x)=\int_{\mathbb{R}}y\ \mathrm{d}R_{x,b}(y)rb​(x)=∫R​y dRx,b​(y) (a Bochner integral, equal to 000 by convention if Rx,bR_{x,b}Rx,b​ has no finite first moment), and let rˉq(x)=q⋅rtrue(x)+(1−q)⋅rfalse(x)\bar r_q(x)=q\cdot r_{\mathsf{true}}(x)+(1-q)\cdot r_{\mathsf{false}}(x)rˉq​(x)=q⋅rtrue​(x)+(1−q)⋅rfalse​(x). For t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} let mt=max⁡(t−k,0)m_t=\max(t-k,0)mt​=max(t−k,0); this is the truncated subtraction of natural numbers, so mt=0m_t=0mt​=0 whenever t≤kt\le kt≤k.

The definition. For each ttt, first form the row vector dt=ρ⋅M0θM1θ⋯Mmt−1θd_t=\rho\cdot M^{\theta}_0M^{\theta}_1\cdots M^{\theta}_{m_t-1}dt​=ρ⋅M0θ​M1θ​⋯Mmt​−1θ​ (this is Env.stateDist of the same file evaluated at θ\thetaθ and mtm_tmt​), then the row vector

Dt=dt⋅MmtqMmt+1q⋯Mt−1q,D_t=d_t\cdot M^{q}_{m_t}M^{q}_{m_t+1}\cdots M^{q}_{t-1},Dt​=dt​⋅Mmt​q​Mmt​+1q​⋯Mt−1q​,

all matrix products being taken with indices increasing from left to right, an empty product being the identity matrix. Then

JkGenT,kE(θ,q)=1T∑t=0T−1 ∑x∈SDt(x)⋅rˉq(x).\mathrm{JkGen}^{E}_{T,k}(\theta,q)=\frac{1}{T}\sum_{t=0}^{T-1}\ \sum_{x\in S}D_t(x)\cdot\bar r_q(x).JkGenT,kE​(θ,q)=T1​t=0∑T−1​ x∈S∑​Dt​(x)⋅rˉq​(x).

So in the ttt-th summand the first mtm_tmt​ steps (indices 0,…,mt−10,\dots,m_t-10,…,mt​−1) use the first real parameter θ\thetaθ, the last t−mt=min⁡(t,k)t-m_t=\min(t,k)t−mt​=min(t,k) steps (indices mt,…,t−1m_t,\dots,t-1mt​,…,t−1) use the second real parameter qqq, and the mixture rˉq\bar r_qrˉq​ at the end also uses qqq. This definition is built from matrices and the means rb(x)r_b(x)rb​(x) only; no measure on a trajectory space appears in it.

Points the formula literally entails:

  • For t≤kt\le kt≤k: mt=0m_t=0mt​=0, the θ\thetaθ-block is empty, and the ttt-th summand does not depend on θ\thetaθ. In particular if k≥T−1k\ge T-1k≥T−1 the whole value does not depend on θ\thetaθ.
  • For k=0k=0k=0: mt=tm_t=tmt​=t, the qqq-block is empty, all ttt steps use θ\thetaθ, and only rˉq\bar r_qrˉq​ involves qqq.
  • T=0T=0T=0: the sum is empty and the prefactor is 1/0=01/0=01/0=0, so the value is 000.
  • θ\thetaθ and qqq are unrestricted; for values outside [0,1][0,1][0,1] the matrices MsaM^{a}_sMsa​ can have negative entries and the formula is used as written.

Psi (TPG.Psi). Inputs: a natural number kkk and a real number γ\gammaγ (no hypothesis: any real, in particular not required to lie in [0,1)[0,1)[0,1)). Output: the real number

Ψ(k,γ)=∑j=0k−1cj,cj=(j+1)⋅γj  if j+2≤k,cj=0  otherwise.\Psi(k,\gamma)=\sum_{j=0}^{k-1}c_j,\qquad c_j=(j+1)\cdot\gamma^{j}\ \text{ if } j+2\le k,\qquad c_j=0\ \text{ otherwise}.Ψ(k,γ)=j=0∑k−1​cj​,cj​=(j+1)⋅γj  if j+2≤k,cj​=0  otherwise.

The index jjj ranges over the natural numbers 0,…,k−10,\dots,k-10,…,k−1, but the condition j+2≤kj+2\le kj+2≤k removes the last one, j=k−1j=k-1j=k−1; so the value equals

Ψ(k,γ)=∑j=0k−2(j+1)⋅γjfor k≥2,Ψ(0,γ)=Ψ(1,γ)=0.\Psi(k,\gamma)=\sum_{j=0}^{k-2}(j+1)\cdot\gamma^{j}\quad\text{for } k\ge 2,\qquad \Psi(0,\gamma)=\Psi(1,\gamma)=0.Ψ(k,γ)=j=0∑k−2​(j+1)⋅γjfor k≥2,Ψ(0,γ)=Ψ(1,γ)=0.

Thus Ψ(2,γ)=1\Psi(2,\gamma)=1Ψ(2,γ)=1, Ψ(3,γ)=1+2γ\Psi(3,\gamma)=1+2\gammaΨ(3,γ)=1+2γ, Ψ(4,γ)=1+2γ+3γ2\Psi(4,\gamma)=1+2\gamma+3\gamma^{2}Ψ(4,γ)=1+2γ+3γ2. The power γ0\gamma^{0}γ0 equals 111 for every real γ\gammaγ, including γ=0\gamma=0γ=0. The definition involves no state space, environment or measure.


Env.rDiffNorm (TPG.Env.rDiffNorm). Inputs: a finite type SSS (no σ\sigmaσ-algebra on SSS and no decidable equality are required) and an environment EEE on SSS. Output: a real number.

What an environment is. An environment EEE on SSS consists of: (a) for every natural number sss and every Boolean bbb, a real matrix PsbP_s^{b}Psb​ with rows and columns indexed by SSS, all of whose entries are ≥0\ge 0≥0 and each of whose rows sums to one (not used by this definition); (b) a function ρ:S→R\rho:S\to\mathbb{R}ρ:S→R with ρ(x)≥0\rho(x)\ge 0ρ(x)≥0 for every xxx and ∑x∈Sρ(x)=1\sum_{x\in S}\rho(x)=1∑x∈S​ρ(x)=1 (not used by the formula, but its existence forces SSS to be nonempty); (c) for every x∈Sx\in Sx∈S and every Boolean bbb, a Borel probability measure Rx,bR_{x,b}Rx,b​ on R\mathbb{R}R, about which nothing else is assumed.

The definition. For a Boolean bbb and x∈Sx\in Sx∈S let rb(x)=∫Ry dRx,b(y)r_b(x)=\int_{\mathbb{R}}y\ \mathrm{d}R_{x,b}(y)rb​(x)=∫R​y dRx,b​(y). Then

rDiffNorm(E)=sup⁡x∈S ∣rtrue(x)−rfalse(x)∣.\mathrm{rDiffNorm}(E)=\sup_{x\in S}\ \big\lvert r_{\mathsf{true}}(x)-r_{\mathsf{false}}(x)\big\rvert.rDiffNorm(E)=x∈Ssup​ ​rtrue​(x)−rfalse​(x)​.

The supremum is the library's real-valued supremum of a family, which by convention is 000 for an empty index set or a family unbounded above; here SSS is finite and nonempty, so it is the maximum over x∈Sx\in Sx∈S. Each rb(x)r_b(x)rb​(x) is a Bochner integral, equal to 000 by convention if Rx,bR_{x,b}Rx,b​ has no finite first moment; no integrability or boundedness of Rx,bR_{x,b}Rx,b​ is assumed in this definition.


rcWeight (TPG.rcWeight). Inputs: a real number θ\thetaθ and a Boolean zzz. Output: the real number

rcWeightθ(true)=1−θθ,rcWeightθ(false)=θ1−θ.\mathrm{rcWeight}_\theta(\mathsf{true})=\frac{1-\theta}{\theta},\qquad \mathrm{rcWeight}_\theta(\mathsf{false})=\frac{\theta}{1-\theta}.rcWeightθ​(true)=θ1−θ​,rcWeightθ​(false)=1−θθ​.

There is no hypothesis on θ\thetaθ: any real number is allowed. Division is the library's total division on R\mathbb{R}R, in which a/0=0a/0=0a/0=0. Consequently, at θ=0\theta=0θ=0 both values are 000 (rcWeight0(true)=1/0=0\mathrm{rcWeight}_0(\mathsf{true})=1/0=0rcWeight0​(true)=1/0=0 and rcWeight0(false)=0/1=0\mathrm{rcWeight}_0(\mathsf{false})=0/1=0rcWeight0​(false)=0/1=0), and at θ=1\theta=1θ=1 both values are 000 (rcWeight1(true)=0/1=0\mathrm{rcWeight}_1(\mathsf{true})=0/1=0rcWeight1​(true)=0/1=0 and rcWeight1(false)=1/0=0\mathrm{rcWeight}_1(\mathsf{false})=1/0=0rcWeight1​(false)=1/0=0). At θ=12\theta=\tfrac12θ=21​ both values are 111. For θ∉[0,1]\theta\notin[0,1]θ∈/[0,1] both values are negative. The definition involves no state space, environment or measure.


rcEst (TPG.rcEst). Inputs: a type SSS (implicit; the file's ambient context declares SSS to be a finite type, but this formula makes no use of finiteness and involves no σ\sigmaσ-algebra on SSS); a real number θ\thetaθ (no hypothesis: any real); natural numbers TTT and kkk (either may be 000); and a trajectory ω\omegaω of length TTT, meaning a function assigning to each index t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} a triple ω(t)=(Xt(ω),Zt(ω),Yt(ω))\omega(t)=(X_t(\omega),Z_t(\omega),Y_t(\omega))ω(t)=(Xt​(ω),Zt​(ω),Yt​(ω)) with Xt(ω)∈SX_t(\omega)\in SXt​(ω)∈S, Zt(ω)Z_t(\omega)Zt​(ω) a Boolean and Yt(ω)∈RY_t(\omega)\in\mathbb{R}Yt​(ω)∈R. Output: the real number

rcEstθ,T,k(ω)=1T∑u=0T−1σθ(Zu(ω))⋅(Yu(ω)+∑t=u+1min⁡(u+k,T−1)cθ(Zt(ω))⋅Yt(ω)),\mathrm{rcEst}_{\theta,T,k}(\omega)=\frac{1}{T}\sum_{u=0}^{T-1}\sigma_\theta\big(Z_u(\omega)\big)\cdot\Bigg(Y_u(\omega)+\sum_{t=u+1}^{\min(u+k,T-1)}c_\theta\big(Z_t(\omega)\big)\cdot Y_t(\omega)\Bigg),rcEstθ,T,k​(ω)=T1​u=0∑T−1​σθ​(Zu​(ω))⋅(Yu​(ω)+t=u+1∑min(u+k,T−1)​cθ​(Zt​(ω))⋅Yt​(ω)),

where

σθ(true)=1θ,σθ(false)=−11−θ,cθ(true)=1−θθ,cθ(false)=θ1−θ\sigma_\theta(\mathsf{true})=\frac{1}{\theta},\quad\sigma_\theta(\mathsf{false})=-\frac{1}{1-\theta},\qquad c_\theta(\mathsf{true})=\frac{1-\theta}{\theta},\quad c_\theta(\mathsf{false})=\frac{\theta}{1-\theta}σθ​(true)=θ1​,σθ​(false)=−1−θ1​,cθ​(true)=θ1−θ​,cθ​(false)=1−θθ​

(the functions score and rcWeight of the same file), with the convention a/0=0a/0=0a/0=0.

Literally, the inner sum ranges over all indices t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} and keeps cθ(Zt(ω))⋅Yt(ω)c_\theta(Z_t(\omega))\cdot Y_t(\omega)cθ​(Zt​(ω))⋅Yt​(ω) exactly when u<tu<tu<t (strict) and t≤u+kt\le u+kt≤u+k (non-strict), contributing 000 otherwise. So the term Yu(ω)Y_u(\omega)Yu​(ω) at the index uuu itself enters with coefficient 111 (no factor cθc_\thetacθ​), the later indices u+1,…,min⁡(u+k,T−1)u+1,\dots,\min(u+k,T-1)u+1,…,min(u+k,T−1) each enter with the factor cθc_\thetacθ​ evaluated at that later index's own Boolean Zt(ω)Z_t(\omega)Zt​(ω), and the whole bracket is multiplied by σθ\sigma_\thetaσθ​ evaluated at Zu(ω)Z_u(\omega)Zu​(ω). The window is cut off at the last index T−1T-1T−1. This is a deterministic function of the single trajectory ω\omegaω; no probability measure or expectation appears, and the state components Xt(ω)X_t(\omega)Xt​(ω) are not used.

Edge cases, as the formula literally evaluates:

  • T=0T=0T=0: the outer sum is empty and the prefactor is 1/0=01/0=01/0=0, so the value is 000.
  • k=0k=0k=0, or u=T−1u=T-1u=T−1: the inner sum is empty and the bracket is Yu(ω)Y_u(\omega)Yu​(ω).
  • θ=0\theta=0θ=0: σ0(true)=0\sigma_0(\mathsf{true})=0σ0​(true)=0, σ0(false)=−1\sigma_0(\mathsf{false})=-1σ0​(false)=−1, and c0c_0c0​ is identically 000, so the value is −1T∑u: Zu(ω)=falseYu(ω)-\frac{1}{T}\sum_{u:\ Z_u(\omega)=\mathsf{false}}Y_u(\omega)−T1​∑u: Zu​(ω)=false​Yu​(ω).
  • θ=1\theta=1θ=1: σ1(true)=1\sigma_1(\mathsf{true})=1σ1​(true)=1, σ1(false)=0\sigma_1(\mathsf{false})=0σ1​(false)=0, and c1c_1c1​ is identically 000, so the value is 1T∑u: Zu(ω)=trueYu(ω)\frac{1}{T}\sum_{u:\ Z_u(\omega)=\mathsf{true}}Y_u(\omega)T1​∑u: Zu​(ω)=true​Yu​(ω).
  • θ=12\theta=\tfrac12θ=21​: c1/2c_{1/2}c1/2​ is identically 111.
  • θ∉[0,1]\theta\notin[0,1]θ∈/[0,1]: allowed; the formula is used as written.
Human review
  • Endorsed by tianyipeng · Oct 12, 2026

  • Endorsed by Wenqian Xing · Oct 12, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me