Lemma B.4, p. 291 — close rewards and transitions imply values of s actions within ηs(s + 1)/2
ProvedQLearning.Convergence.lemmaB4_close_chains_close_valuesLet be a finite controlled Markov process with for all , where , and let . Let , (), be the transition matrices of Markov chains and reward functions, and let . Suppose that for and all ,
Let be the expected discounted reward of the actions in the concatenated chain (step uses and ) and their value in the real process, both with terminal reward. Then for every ,
This converts the convergence of the ARP's one-step model (Lemma B.3) into closeness of the values of actions.
Formalization Note The page assumes each entry within of ; with that hypothesis the printed constant fails once (e.g. , , gives at ). The statement uses closeness of rows in , under which the printed constant holds and which is what the proof's recursion uses. The case is excluded because both values are there and the strict inequality fails; the page's "" has .
import Mathlib import Definitions.Def_QLearning_Convergence_Setting open MeasureTheory ProbabilityTheory Filter Topology
namespace QLearning.Convergence
theorem lemmaB4_close_chains_close_values {X A : Type} [Fintype X] [DecidableEq X] [Fintype A] [DecidableEq A] [Nonempty A]
(M : FiniteMDP X A) (γ : ℝ) (hγ0 : 0 < γ) (hγ1 : γ < 1)
(Rbar : ℝ) (hRbar : 0 < Rbar) (hR : ∀ x a, |M.R x a| ≤ Rbar)
(Ps : ℕ → X → A → X → ℝ) (Rs : ℕ → X → A → ℝ) (η : ℝ) (hη : 0 < η)
(bs : List A) (hs : 1 ≤ bs.length)
(hPs_nonneg : ∀ i, 1 ≤ i → i ≤ bs.length → ∀ x a y, 0 ≤ Ps i x a y)
(hPs_sum : ∀ i, 1 ≤ i → i ≤ bs.length → ∀ x a, ∑ y, Ps i x a y = 1)
(hP : ∀ i, 1 ≤ i → i ≤ bs.length → ∀ x a, ∑ y, |Ps i x a y - M.P x a y| < η / Rbar)
(hRs : ∀ i, 1 ≤ i → i ≤ bs.length → ∀ x a, |Rs i x a - M.R x a| < η) :
∀ x, |chainValue Ps Rs γ 1 x bs - seqValue M γ x bs|
< (bs.length : ℝ) * (bs.length + 1) / 2 * η := by sorry
end QLearning.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.