Theorem 6.2, (72), p. 45 — posterior sampling certifies dec^Sq_γ(µ, M̄) ≤ inf_{Δ>0}{2Δ + 24·sup_M θ(F_M − f^M, Δ, γ⁻¹; ρ_µ)·log²(γ)/γ} for γ ≥ e
ProvedStatComplexityDM.Disagreement.posterior_sampling_sq_dec_disagreementLet be the class of mean-reward functions of a model class . Let be a finitely supported prior over , where each has mean reward and optimal decision . Let be a reference model, not necessarily in , with mean reward . The posterior sampling strategy plays , the law of under . Then for all it certifies
that is, the objective of (70),
with and independent, is at most the right-hand side. Here is the disagreement coefficient of Definition 6.3.
Theorem 6.2 is a prior-dependent upper bound on the dual square-loss Decision-Estimation Coefficient. Combined with a bound of the disagreement coefficient by the star number or the eluder dimension (Lemma 6.1) and the minimax theorem, it yields the paper's Theorem 6.1, which recovers the eluder-dimension regret bound of Russo and Van Roy as a special case.
Formalization Note The infimum over is stated as a bound for every , and the supremum over as a bound for every upper bound of over all ; both forms are equivalent to the page's and avoid Lean's default values for empty or unbounded infima and suprema. The bound is stated for the posterior sampling distribution itself, which upper-bounds the infimum over in (70). Priors and are finite weighted families (footnote 5 of the paper); models enter only through their mean rewards and optimal decisions, which is all the square-loss DEC depends on. is the natural logarithm and .
import Mathlib import Definitions.Def_StatComplexityDM_Disagreement_Coefficient
namespace StatComplexityDM.Disagreement
/-- Theorem 6.2, (72), p. 45 (arXiv:2112.13487v3). For a class `F_M ⊆ (Π → [0, 1])` of mean-reward
functions, a finitely supported prior `µ = Σ_i w i · δ_{M_i}` over models with `fM i = f^{M_i} ∈ F_M`
and `piM i = π_{M_i} ∈ arg max f^{M_i}`, and a reference model `M̄` (not necessarily in `M`) with
`fbar = f^{M̄} ∈ [0, 1]`, the posterior sampling strategy `ρ_µ(π) = µ({π_M = π})` (the weighted
family `Σ_j w j · δ_{piM j}`) certifies, for all `γ ≥ e`,
`dec^Sq_γ(µ, M̄) ≤ inf_{Δ>0} {2Δ + 24 sup_{M∈M} θ(F_M − f^M, Δ, γ⁻¹; ρ_µ) log²(γ)/γ}`:
the objective of (70) at `p = ρ_µ` is at most `2Δ + 24Θ log²(γ)/γ` for every `Δ > 0` and every
upper bound `Θ` of `θ(F_M − g, Δ, γ⁻¹; ρ_µ)` over all `g = f^M ∈ F_M`. -/
theorem posterior_sampling_sq_dec_disagreement {ι 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))
(fbar : Act → ℝ) (hfbar : ∀ π, 0 ≤ fbar π ∧ fbar π ≤ 1) (γ : ℝ) (hγ : Real.exp 1 ≤ γ) :
∀ Δ : ℝ, 0 < Δ → ∀ Θ : ℝ,
(∀ g ∈ FM, disagreementCoeff (shiftClass FM g) Δ γ⁻¹ w piM ≤ Θ) →
sqDecObjective w fM piM fbar γ w piM ≤ 2 * Δ + 24 * Θ * Real.log γ ^ 2 / γ := by sorry
end StatComplexityDM.Disagreement
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.