Lemma B.1, p. 289 — the value of s actions with and without a continuation policy differ by at most γ^s ℛ/(1 − γ)
ProvedQLearning.Convergence.lemmaB1_discounting_taildiscountingdynamic-programmingmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite controlled Markov process with for all , and let . For a stationary policy , a state and actions , let be the expected discounted reward of the actions with terminal reward and the expected discounted reward of the same actions followed by . Then
In particular the difference tends to as , uniformly in , and the actions, which is the statement of Lemma B.1; the bound is the display in its proof, used in §3.2 to choose .
Formalization Note The page prints strict inequalities and ; with only holds (a constant reward gives equality), so the bound is stated with . "Any arbitrary policy" is taken over stationary deterministic policies .
Preamble
import Mathlib import Definitions.Def_QLearning_Convergence_Setting open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace QLearning.Convergence
theorem lemmaB1_discounting_tail {X A : Type} [Fintype X] [DecidableEq X] [Fintype A] [DecidableEq A] [Nonempty A]
(M : FiniteMDP X A) (γ : ℝ) (hγ0 : 0 < γ) (hγ1 : γ < 1)
(Rbar : ℝ) (hR : ∀ x a, |M.R x a| ≤ Rbar)
(π : X → A) (x : X) (bs : List A) :
|seqThenPolicy M γ π x bs - seqValue M γ x bs| ≤ γ ^ bs.length * (Rbar / (1 - γ)) := by sorry
end QLearning.Convergence
Source
Watkins & Dayan, Technical Note: Q-Learning, Machine Learning 8 (1992), p. 289, Lemma B.1 and the display in its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.