Theorem 6.2 (proof), p. 106 — Lemma E.2 for F_M − f^{M̃} at γ/4: E_µ[f^M(π_M) − f^{M̃}(π_M)] ≤ 2Δ + 24θ log²(γ ∨ e)/γ + (γ/4)E[(f^M − f^{M̃})²]
ProvedStatComplexityDM.Disagreement.ps_fixed_shift_bounddecouplingdisagreement-coefficientp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1posterior-sampling
Let be a class of mean-reward functions , and let be a finitely supported prior over models with and . Let , , be the posterior sampling distribution. Fix a model with , and let . Then for every ,
where and are independent and is the disagreement coefficient of Definition 6.3.
This is Lemma E.2 applied to the shifted class with parameter ; averaging it over gives Theorem 6.2.
Formalization Note The infimum over is stated as a bound for every . The prior and are finite weighted families; models enter only through their mean rewards and decisions. The page derives this display inside the proof of Theorem 6.2, whose standing range is .
Preamble
import Mathlib import Definitions.Def_StatComplexityDM_Disagreement_Coefficient
Formal statement
namespace StatComplexityDM.Disagreement
/-- Proof of Theorem 6.2, p. 106 (arXiv:2112.13487v3), Lemma E.2 applied with the class `F_M − f^{M̃}`
and parameter `γ/4`: for a class `F_M ⊆ (Π → [0, 1])`, a finitely supported prior
`µ = Σ_i w i · δ_{M_i}` with `fM i = f^{M_i} ∈ F_M` and `piM i = π_{M_i}`, posterior sampling
`p = ρ_µ = Σ_j w j · δ_{piM j}`, a fixed `M̃ ∈ M` with mean reward `g = f^{M̃} ∈ F_M`, `γ ≥ e` and
every `Δ > 0`,
`E_{M∼µ}[f^M(π_M) − f^{M̃}(π_M)] ≤ 2Δ + 24 θ(F_M − f^{M̃}, Δ, γ⁻¹; ρ_µ) log²(γ ∨ e)/γ
+ (γ/4) · E_{π∼p, M∼µ}[(f^M(π) − f^{M̃}(π))²]`. -/
theorem ps_fixed_shift_bound {ι Act : Type*} [Fintype ι] (FM : Set (Act → ℝ))
(hF : ∀ f ∈ FM, ∀ π, 0 ≤ f π ∧ f π ≤ 1) (w : ι → ℝ) (hw : StatComplexityDM.LowerBound.IsDist w) (fM : ι → Act → ℝ)
(hfM : ∀ i, fM i ∈ FM) (piM : ι → Act) (hpiM : ∀ i π, fM i π ≤ fM i (piM i))
(g : Act → ℝ) (hg : g ∈ FM) (γ : ℝ) (hγ : Real.exp 1 ≤ γ) (Δ : ℝ) (hΔ : 0 < Δ) :
∑ i, w i * (fM i (piM i) - g (piM i))
≤ 2 * Δ + 24 * disagreementCoeff (shiftClass FM g) Δ γ⁻¹ w piM
* Real.log (max γ (Real.exp 1)) ^ 2 / γ
+ γ / 4 * ∑ j, w j * ∑ i, w i * (fM i (piM j) - g (piM j)) ^ 2 := by sorry
end StatComplexityDM.Disagreement
Source
arXiv:2112.13487v3, App. E.2.2, proof of Theorem 6.2, p. 106 ("We now apply Lemma E.2 with the class F_M − f^M̃ and parameter γ/4")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.