Lemma 8, p. 19 — w.p. ≥ 1 − δ over ς ∼ Unif(0,ξ), {a : Q̂(s,a) > V̂(s) − ς} is unchanged for every Q within ξδ/(8|S||A|) of Q̂
ProvedBreakingSample.Conservative.lemma_8conservative-planningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitystability
Let , be finite with nonempty, let be any Q-function and its associated value function, and let , . Draw . Then with probability at least the following holds simultaneously for all Q-functions (with associated value function ) obeying
Consequently the conservative policy computed from does not change under small perturbations of , which is what allows it to be represented by policies independent of the samples of one pair .
Formalization Note The probability is the measure (outer measure if not measurable) of the failure event, bounded by . The quantifier over is inside the event.
Preamble
import Mathlib import Definitions.Def_BreakingSample_Perturbed_Sampling import Definitions.Def_BreakingSample_Conservative_Rule
Formal statement
namespace BreakingSample.Conservative
theorem lemma_8 {S A : Type} [Fintype S] [Fintype A] [Nonempty A]
(Qhat : S → A → ℝ) (ξ δ : ℝ) (hξ : 0 < ξ) (hδ : 0 < δ) :
BreakingSample.Perturbed.unifInterval ξ {ς : ℝ | ¬ ∀ Q : S → A → ℝ,
(∀ s a, |Q s a - Qhat s a| ≤ ξ * δ / (8 * (Fintype.card S : ℝ) * (Fintype.card A : ℝ))) →
∀ s, {a : A | maxQ Qhat s - ς < Qhat s a} = {a : A | maxQ Q s - ς < Q s a}}
≤ ENNReal.ofReal δ := by sorry
end BreakingSample.Conservative
Source
arXiv:2005.12900v8, Lemma 8, p. 19, (54)–(55); proof in App. B.7, pp. 33–34
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.