Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem, p. 282 — with |r_n| ≤ ℛ, 0 ≤ α_n < 1 and (3), Q_n(x, a) → Q*(x, a) for all x, a with probability 1

Proved
QLearning.Convergence.theorem_q_learning_converges

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

convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1q-learningreinforcement-learningstochastic-approximation

Let (X,A,R,P)(X,\mathfrak A,\mathcal R,P)(X,A,R,P) be a finite controlled Markov process with a nonempty action set, let 0<γ<10<\gamma<10<γ<1, and let Q∗Q^*Q∗ be its optimal action-value function, i.e. the solution of

Q∗(x,a)=Rx(a)+γ∑yPxy[a]max⁡bQ∗(y,b).Q^*(x,a)=\mathcal R_x(a)+\gamma\sum_y P_{xy}[a]\max_b Q^*(y,b).Q∗(x,a)=Rx​(a)+γy∑​Pxy​[a]bmax​Q∗(y,b).

On a probability space with a filtration (Fn)(\mathcal F_n)(Fn​), let the episodes (xn,an,yn,rn,αn)n≥1(x_n,a_n,y_n,r_n,\alpha_n)_{n\ge1}(xn​,an​,yn​,rn​,αn​)n≥1​ satisfy:

  1. the state xnx_nxn​, action ana_nan​ and learning rate αn\alpha_nαn​ of episode nnn are Fn−1\mathcal F_{n-1}Fn−1​-measurable, and the outcome (yn,rn)(y_n,r_n)(yn​,rn​) is Fn\mathcal F_nFn​-measurable;
  2. Pr⁡[yn=y∣Fn−1]=Pxny[an]\Pr[y_n=y\mid\mathcal F_{n-1}]=P_{x_ny}[a_n]Pr[yn​=y∣Fn−1​]=Pxn​y​[an​] for every yyy, and E[rn∣Fn−1]=Rxn(an)\mathbb E[r_n\mid\mathcal F_{n-1}]=\mathcal R_{x_n}(a_n)E[rn​∣Fn−1​]=Rxn​​(an​);
  3. the rewards are bounded, ∣rn∣≤R|r_n|\le\mathcal R∣rn​∣≤R, and the learning rates satisfy 0≤αn<10\le\alpha_n<10≤αn​<1;
  4. with probability 111, for every pair (x,a)(x,a)(x,a), writing ni(x,a)n^i(x,a)ni(x,a) for the episode of the iii-th visit to (x,a)(x,a)(x,a),
∑i=1∞αni(x,a)=∞,∑i=1∞[αni(x,a)]2<∞.(3)\sum_{i=1}^\infty\alpha_{n^i(x,a)}=\infty,\qquad\sum_{i=1}^\infty\bigl[\alpha_{n^i(x,a)}\bigr]^2<\infty.\tag{3}i=1∑∞​αni(x,a)​=∞,i=1∑∞​[αni(x,a)​]2<∞.(3)

Let QnQ_nQn​ be the Q-learning iterates (1) from given initial values Q0Q_0Q0​. Then with probability 111,

Qn(x,a)→Q∗(x,a)as n→∞, for all x,a.Q_n(x,a)\to Q^*(x,a)\quad\text{as }n\to\infty,\ \text{for all }x,a.Qn​(x,a)→Q∗(x,a)as n→∞, for all x,a.

This is the convergence theorem of tabular Q-learning: an agent that tries every action in every state infinitely often, with suitably decreasing learning rates, learns the optimal action values without a model of the process.

Formalization Note The paper states the probability model only in words. The statement pins the reading under which the theorem is known to hold (Tsitsiklis 1994; Jaakkola, Jordan and Singh 1994): the agent chooses the next state, action and learning rate from the past (predictable choices), the next state has law Pxn⋅[an]P_{x_n\cdot}[a_n]Pxn​⋅​[an​] and the reward has mean Rxn(an)\mathcal R_{x_n}(a_n)Rxn​​(an​) given the past. Episodes with states, actions and learning rates fixed in advance and independent outcomes are a special case. Condition (3) is written as a sum over episodes of the learning rate charged to (x,a)(x,a)(x,a), which equals the sum over visits and forces infinitely many visits. Lean index nnn is the paper's episode nnn; index 000 of the data is unused and Q0Q_0Q0​ is deterministic.

Preamble
import Mathlib
import Definitions.Def_QLearning_Convergence_Setting
open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace QLearning.Convergence

theorem theorem_q_learning_converges {X A : Type} [Fintype X] [DecidableEq X] [Fintype A] [DecidableEq A] [Nonempty A]
    [MeasurableSpace X] [DiscreteMeasurableSpace X] [MeasurableSpace A] [DiscreteMeasurableSpace A]
    (M : FiniteMDP X A) (γ : ℝ) (hγ0 : 0 < γ) (hγ1 : γ < 1)
    (Qstar : X → A → ℝ) (hQ : IsOptimalQ M γ Qstar) (Q0 : X → A → ℝ)
    {Ω : Type*} [mΩ : MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
    (ℱ : Filtration ℕ mΩ)
    (xs : ℕ → Ω → X) (as : ℕ → Ω → A) (ys : ℕ → Ω → X) (rs αs : ℕ → Ω → ℝ)
    (hxs : ∀ n, Measurable[ℱ n] (xs (n + 1)))
    (has : ∀ n, Measurable[ℱ n] (as (n + 1)))
    (hαs : ∀ n, Measurable[ℱ n] (αs (n + 1)))
    (hys : ∀ n, Measurable[ℱ (n + 1)] (ys (n + 1)))
    (hrs : ∀ n, Measurable[ℱ (n + 1)] (rs (n + 1)))
    (htrans : ∀ n y, μ[fun ω => if ys (n + 1) ω = y then (1 : ℝ) else 0 | ℱ n]
      =ᵐ[μ] fun ω => M.P (xs (n + 1) ω) (as (n + 1) ω) y)
    (hrew : ∀ n, μ[rs (n + 1) | ℱ n] =ᵐ[μ] fun ω => M.R (xs (n + 1) ω) (as (n + 1) ω))
    (Rbar : ℝ) (hbdd : ∀ n ω, |rs n ω| ≤ Rbar)
    (hα : ∀ n ω, 0 ≤ αs n ω ∧ αs n ω < 1)
    (h3 : ∀ᵐ ω ∂μ, ∀ x a,
      Tendsto (fun N => ∑ n ∈ Finset.range N,
        visitRate (fun k => xs k ω) (fun k => as k ω) (fun k => αs k ω) x a (n + 1)) atTop atTop ∧
      Summable (fun n =>
        visitRate (fun k => xs k ω) (fun k => as k ω) (fun k => αs k ω) x a (n + 1) ^ 2)) :
    ∀ᵐ ω ∂μ, ∀ x a,
      Tendsto (fun n => qIter γ Q0 (fun k => xs k ω) (fun k => as k ω) (fun k => ys k ω)
          (fun k => rs k ω) (fun k => αs k ω) n x a) atTop (𝓝 (Qstar x a)) := by sorry

end QLearning.Convergence
Source
Watkins & Dayan, Technical Note: Q-Learning, Machine Learning 8 (1992), p. 282, Theorem; proof §3 and Appendix, pp. 282–291
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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