Proof of Proposition 6.2, p. 100 — θᵢ = Δeᵢ: regret Δ(1 − πᵢ) and D²_H(Mᵢ(π), Rad(0)) ≤ ¾Δ²πᵢ², the regret and information properties with uᵢ(π) = πᵢ, vᵢ(π) = πᵢ²
ProvedStatComplexityDM.LinearLB.ball_family_harddecision-estimation-coefficienthard-familylinear-banditsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be the Euclidean unit ball of , let be a maximizer selector for the linear mean reward over the ball, let and . Put , , and let be the model with parameter . Then for every :
- (regret property, )
- (information property, )
Together with the sum bounds and (for ), this makes a -family with respect to , the construction behind the lower bound of Proposition 6.2.
Formalization Note A parameter is passed as a point of the ball whose underlying vector equals . The first identity uses that the selector attains , which follows from the maximizer hypothesis. Here takes negative values, so the family satisfies Definition 5.1 only without its range conditions (see the restated Lemma 5.1 of this mission).
Preamble
import Mathlib import Definitions.Def_StatComplexityDM_LinearLB_Setting
Formal statement
namespace StatComplexityDM.LinearLB
/-- Proof of Proposition 6.2 (arXiv:2112.13487v3, p. 100): the models `M_i(π) = Rad(⟨θ_i, π⟩)`,
`θ_i = Δ·e_i`, satisfy the regret property with `u_i(π) = π_i` and the information property with
`v_i(π) = π_i²` and constant `¾Δ²`, with respect to `M̄ = Rad(0)`. -/
theorem ball_family_hard (d : ℕ) (piStar : Ball d → Ball d)
(hpiStar : IsBallArgmax piStar) (Δ : ℝ) (hΔ0 : 0 ≤ Δ) (hΔ1 : Δ ≤ 1)
(i : Fin d) (θ : Ball d)
(hθ : (θ : EuclideanSpace ℝ (Fin d)) = Δ • EuclideanSpace.single i 1) :
∀ π : Ball d,
gapLin piStar θ π = Δ * (1 - (π : EuclideanSpace ℝ (Fin d)) i) ∧
hellLin θ (ballZero d) π ≤ 3 / 4 * Δ ^ 2 * ((π : EuclideanSpace ℝ (Fin d)) i) ^ 2 := by sorry
end StatComplexityDM.LinearLB
Source
arXiv:2112.13487v3, proof of Proposition 6.2, App. E.1.1, p. 100
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.