Lemma 2.4 — for Z ~ N(0, I_r/r), Pr{θ ≤ ‖Z‖ ≤ β} ≥ 1 − 4θ² − 1/β²
ProvedLinParamBandits.LowerBound.norm_prob_boundconcentrationgaussianp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let be a multivariate normal vector in with mean and covariance matrix , the prior of Section 2.
Lemma 2.4. For any and ,
The lemma keeps away from and from with high probability; it is what turns the conditional bounds in the proof of Lemma 2.5 into an unconditional one.
Formalization Note is the Euclidean norm on EuclideanSpace ℝ (Fin r), and the prior is the law of with standard normal. As printed, may be zero or negative; the statement keeps that range. The hypothesis is the paper's standing assumption (p. 3) and is needed: for and small the probability that is about , which exceeds .
Preamble
import Mathlib import Definitions.Def_LinParamBandits_LowerBound_Model open MeasureTheory ProbabilityTheory
Formal statement
namespace LinParamBandits.LowerBound
/-- Lemma 2.4, Rusmevichientong, Tsitsiklis, arXiv:0812.3465v2, p. 11 (proof App. A.1, p. 27):
for `Z ~ N(0, I_r/r)` with `r ≥ 2`, any `θ ≤ 1/2` and `β > 0`,
`Pr{θ ≤ ‖Z‖ ≤ β} ≥ 1 − 4θ² − 1/β²`. -/
theorem norm_prob_bound (r : ℕ) (hr : 2 ≤ r) (θ β : ℝ) (hθ : θ ≤ 1 / 2) (hβ : 0 < β) :
1 - 4 * θ ^ 2 - 1 / β ^ 2 ≤ (prior r).real {z | θ ≤ ‖z‖ ∧ ‖z‖ ≤ β} := by sorry
end LinParamBandits.LowerBound
Source
Rusmevichientong, Tsitsiklis, Linearly Parameterized Bandits, arXiv:0812.3465v2, Lemma 2.4, p. 11; proof in App. A.1, p. 27
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.