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
ProvedQLearning.Convergence.theorem_q_learning_convergesLet be a finite controlled Markov process with a nonempty action set, let , and let be its optimal action-value function, i.e. the solution of
On a probability space with a filtration , let the episodes satisfy:
- the state , action and learning rate of episode are -measurable, and the outcome is -measurable;
- for every , and ;
- the rewards are bounded, , and the learning rates satisfy ;
- with probability , for every pair , writing for the episode of the -th visit to ,
Let be the Q-learning iterates (1) from given initial values . Then with probability ,
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 and the reward has mean 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 , which equals the sum over visits and forces infinitely many visits. Lean index is the paper's episode ; index of the data is unused and is deterministic.
import Mathlib import Definitions.Def_QLearning_Convergence_Setting open MeasureTheory ProbabilityTheory Filter Topology
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.