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
ProvedFiniteMemQL.Convergence.theorem_4_1Assume Assumption 4.1: actions are explored i.i.d. with a law charging every action; the hidden state is positive Harris recurrent under this exploration, with invariant probability measure ; the step sizes are at visits and otherwise; and every pair is visited infinitely often. Then
- the finite-window Q-learning iterates (4.1) converge almost surely to the solution of (4.5);
- for every policy with , used from time on after a policy has acted on the first steps, with the prior of ,
where and is the filter-stability term (3.9) for .
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 follows from positive Harris recurrence. The iteration starts at time , when the first window exists. In (ii) the conditioning on is read as the expectation over , as in Theorems 3.2 and 3.3, and the policy on the first steps is an arbitrary deterministic observation-history policy.
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
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.