Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1, p. 15 — finite-window Q-learning converges a.s. to Q* of (4.5), and its greedy policy loses at most 2‖c‖∞/(1−β) Σ βᵗ L_t

Proved
FiniteMemQL.Convergence.theorem_4_1

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

almost-sure-convergencefilter-stabilityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pomdpq-learning

Assume Assumption 4.1: actions are explored i.i.d. with a law σ\sigmaσ charging every action; the hidden state is positive Harris recurrent under this exploration, with invariant probability measure π∗\pi^*π∗; the step sizes are αt(I,u)=1/(1+∑k≤t1{(Ik,Uk)=(I,u)})\alpha_t(I,u)=1/(1+\sum_{k\le t}\mathbb 1\{(I_k,U_k)=(I,u)\})αt​(I,u)=1/(1+∑k≤t​1{(Ik​,Uk​)=(I,u)}) at visits and 000 otherwise; and every pair (I,u)(I,u)(I,u) is visited infinitely often. Then

  1. the finite-window Q-learning iterates (4.1) converge almost surely to the solution Q∗Q^*Q∗ of (4.5);
  2. for every policy γN\gamma^NγN with Q∗(I,γN(I))=min⁡uQ∗(I,u)Q^*(I,\gamma^N(I))=\min_uQ^*(I,u)Q∗(I,γN(I))=minu​Q∗(I,u), used from time NNN on after a policy has acted on the first NNN steps, with π0−\pi_0^-π0−​ the prior of X0X_0X0​,
E[Jβ(z^0,γN)−Jβ∗(z^0)]≤2∥c∥∞1−β∑t=0∞βtLt,E\bigl[J_\beta(\hat z_0,\gamma^N)-J^*_\beta(\hat z_0)\bigr]\le\frac{2\|c\|_\infty}{1-\beta}\sum_{t=0}^\infty\beta^tL_t,E[Jβ​(z^0​,γN)−Jβ∗​(z^0​)]≤1−β2∥c∥∞​​t=0∑∞​βtLt​,

where z^0=(π0−,I0N)\hat z_0=(\pi_0^-,I_0^N)z^0​=(π0−​,I0N​) and LtL_tLt​ is the filter-stability term (3.9) for π∗\pi^*π∗.

Finite-memory Q-learning thus converges without a belief computation, and the policy it learns is near optimal whenever the filter is stable.

Formalization Note Assumption 4.1.2 is assumed for the i.i.d. exploration actually run, not for every stationary exploration policy; uniqueness of π∗\pi^*π∗ follows from positive Harris recurrence. The iteration starts at time NNN, when the first window exists. In (ii) the conditioning on I0NI_0^NI0N​ is read as the expectation over I0NI_0^NI0N​, as in Theorems 3.2 and 3.3, and the policy on the first NNN steps is an arbitrary deterministic observation-history policy.

Preamble
import Mathlib
import Definitions.Def_TotalVariationDist
import Definitions.Def_RiskSensMDP_AverageCost_HarrisRecurrence
import Definitions.Def_FiniteMemQL_Convergence_Model
import Definitions.Def_FiniteMemQL_Convergence_Setting
import Definitions.Def_FiniteMemQL_Convergence_Learning

open MeasureTheory ProbabilityTheory Filter Finset Topology
Formal statement
namespace FiniteMemQL.Convergence

/-- Theorem 4.1, p. 15 (arXiv:2103.12158v4). Under Assumption 4.1 (step sizes as in `qIter`;
positive Harris recurrence of the state under the i.i.d. exploration `σ`, with invariant law `π*`;
every `(I, u)` visited infinitely often):
(i) the finite-window Q-learning iterates (4.1) converge almost surely to `Q*` of (4.5);
(ii) for every policy `γ^N` greedy for `Q*`, started at time `N` after a history policy `γ₀` has
acted on the first `N` steps, in expectation over the first window `I₀ᴺ`,
`E[ J_β((π₀, I₀ᴺ), γ^N) − J*_β(π₀, I₀ᴺ) ] ≤ 2‖c‖∞ / (1 − β) Σ_t β^t L_t`. -/
theorem theorem_4_1 {X Y U : Type*} [MeasurableSpace X] [StandardBorelSpace X]
    [Fintype Y] [DecidableEq Y] [Nonempty Y] [MeasurableSpace Y] [DiscreteMeasurableSpace Y]
    [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [DiscreteMeasurableSpace U]
    (M : POMDP X Y U)
    (N : ℕ) (σ : Measure U) [IsProbabilityMeasure σ] (hσ : ∀ u : U, 0 < σ {u})
    (hHarris : RiskSensMDP.AverageCost.IsPositiveHarrisRecurrent (explKernel M σ))
    (πs : Measure X) [IsProbabilityMeasure πs] (hπs : Kernel.Invariant (explKernel M σ) πs) :
    (∀ (μ : Measure X), IsProbabilityMeasure μ → ∀ Q₀ : Window Y U N → U → ℝ,
      (∀ᵐ ω ∂pathMeasure M μ σ, ∀ (I : Window Y U N) (u : U),
        ∃ᶠ t in atTop, winAt (N := N) ω t = I ∧ (ω t).2.2 = u) →
      ∀ᵐ ω ∂pathMeasure M μ σ, ∀ (I : Window Y U N) (u : U),
        Tendsto (fun n : ℕ => qIter M Q₀ ω n I u) atTop (𝓝 (qStar M πs I u))) ∧
    (∀ (π₀ : Measure X), IsProbabilityMeasure π₀ → ∀ (γ₀ : HistPolicy Y U)
      (γN : Window Y U N → U), (∀ I : Window Y U N, qStar M πs I (γN I) = ⨅ u : U, qStar M πs I u) →
      ∑ ys : Fin (N + 1) → Y, histMass M π₀ γ₀ ys *
          (Jpol M γN (π₀, ((ys, histActs γ₀ ys) : Window Y U N)) -
            JstarW M π₀ ((ys, histActs γ₀ ys) : Window Y U N)) ≤
        2 * cNorm M / (1 - M.β) * ∑' t : ℕ, M.β ^ t * Lterm M πs π₀ N t) := by sorry

end FiniteMemQL.Convergence
Source
Kara, Yüksel, Convergence of finite memory Q learning for POMDPs and near optimality of learned policies under filter stability, arXiv:2103.12158v4, p. 15, §4, Theorem 4.1 with Assumption 4.1 (proof pp. 16–18, Appendix A)
Human review
  • Endorsed by Shuze Chen · Oct 23, 2026

    Confirmed by the moderator at approval.

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