Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 1 — trial visit frequencies

Proved
LeastSquaresTD.Absorbing.visit_frequencies

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

markov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reinforcement-learningtemporal-difference-learning

For an absorbing finite Markov chain started according to SSS, suppose every state is reachable from the positive support of SSS. Run independent trials by restarting from SSS after an absorbing state. Then there is a deterministic vector π\piπ such that almost surely every state is visited infinitely often and the empirical proportion of in-trial departures from each state xxx converges to πx\pi_xπx​. Moreover πx>0\pi_x>0πx​>0 for each non-absorbing state and πx=0\pi_x=0πx​=0 for each absorbing state.

1n#{k<n:Zk∈N, Zk=x}⟶πxalmost surely.\frac{1}{n}\#\{k<n:Z_k\in\mathcal N,\ Z_k=x\}\longrightarrow\pi_x\quad\text{almost surely}.n1​#{k<n:Zk​∈N, Zk​=x}⟶πx​almost surely.

These frequency properties supply the diagonal weights in Lemma 5 and the rank argument for Theorem 1.

Formalization Note The paper does not define “inaccessible”; it is reachability from the support of SSS. Its πx\pi_xπx​ is expected departures per trial, while the displayed limit uses restart-process steps. The two vectors differ by a common positive scaling factor, which cancels from the LS TD limit.

Preamble
import Definitions.Def_LeastSquaresTD_Absorbing_Estimator
Formal statement
namespace LeastSquaresTD.Absorbing

open MeasureTheory Filter Topology

/-- Proof of Theorem 1, p. 44, first two sentences. The paper calls `π x` the
expected number of departures from `x` per trial. With `n` indexing restart
steps, the limit here differs by one common positive time-scale factor;
the expression in Lemma 5 is invariant under that factor. -/
theorem visit_frequencies
    {X Ω : Type*} [Fintype X] [DecidableEq X] [Nonempty X]
    [MeasurableSpace X] [MeasurableSingletonClass X] [MeasurableSpace Ω]
    (μ : Measure Ω) [IsProbabilityMeasure μ]
    (C : Chain X) (S : X → ℝ) (Z : ℕ → Ω → X)
    (habs : C.IsAbsorbing) (hS_nonneg : ∀ x, 0 ≤ S x)
    (hS_sum : ∑ x, S x = 1) (haccess : C.AllAccessible S)
    (hlaw : HasRestartLaw C S μ Z) :
    ∃ π : X → ℝ,
      (∀ x : C.Nonabsorbing, 0 < π x.val) ∧
      (∀ x, C.P x x = 1 → π x = 0) ∧
      (∀ᵐ ω ∂μ, (∀ (x : X) (N : ℕ), ∃ n ≥ N, Z n ω = x) ∧
        (∀ x, Tendsto (fun n => outFrequency C (fun k => Z k ω) x n)
          atTop (𝓝 (π x)))) := by sorry

end LeastSquaresTD.Absorbing
Source
Bradtke and Barto, Linear Least-Squares Algorithms for Temporal Difference Learning, Machine Learning 22 (1996), https://doi.org/10.1023/A:1018056104778, p. 44, Proof of Theorem 1, first two sentences; p. 43, definition of π
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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