Proof of Lemma 2.5, p. 12 — given , , so
OpenLinParamBandits.LowerBound.posterior_direction_tailWork in the model of Section 2 (arms on the unit sphere of , , prior , i.i.d. standard normal noise, a fixed deterministic policy ), with and vectors as in Lemma 2.2 (orthonormal, orthogonal to , measurable functions of ). Fix and put
Claim (proof of Lemma 2.5, p. 12). Conditioned on , is normally distributed with mean zero and variance . Consequently, for every , with probability one,
where is the standard normal distribution function.
This is the step of the paper's proof of Lemma 2.5 that uses the Gaussian posterior: given the history, is Gaussian (the prior is Gaussian and the observations are linear in with Gaussian noise, the design being a deterministic function of past observations), so its projection on the history-measurable unit vector , centred at its conditional mean, is a centred normal with variance .
Formalization Note The conditional probability is Mathlib's conditional expectation of the indicator of with respect to the σ-algebra generated by under the joint law of ; is likewise Mathlib's conditional expectation. is cdf (gaussianReal 0 1) x. The identity holds almost surely, which does not depend on the versions chosen. The standing assumptions of Lemma 2.2 are kept as hypotheses for uniformity with Lemmas 2.2, 2.3 and 2.5 (orthonormality guarantees , which is needed; is needed for to be meaningful).
import Mathlib import Definitions.Def_LinParamBandits_LowerBound_Model open MeasureTheory ProbabilityTheory
namespace LinParamBandits.LowerBound
/-- Proof of Lemma 2.5, Rusmevichientong, Tsitsiklis, arXiv:0812.3465v2, p. 12: conditioned on
`H_T`, `(Z − Ẑ_T)′ S^k_T` is normal with mean zero and variance `Θ = E[Γ | H_T]`, where
`Γ = ((Z − Ẑ_T)′ S^k_T)²`; hence `Pr{Γ ≥ η Θ | H_T} = 2 (1 − Φ(√η))` almost surely.
Standing assumptions of Sec. 2 (p. 9) as in Lemma 2.2. -/
theorem posterior_direction_tail (r : ℕ) (hr : 2 ≤ r) (ψ : SpherePolicy r) (T : ℕ) (hT : 1 ≤ T)
(S : Fin (r - 1) → History r T → Vec r)
(hS_meas : ∀ k, Measurable (S k))
(hS_orth : ∀ h, Orthonormal ℝ (fun k => S k h))
(hS_perp : ∀ᵐ ω ∂(P r), ∀ k, inner ℝ (S k (hist ψ ω.1 ω.2 T)) (zhat ψ T ω) = 0)
(k : Fin (r - 1)) (η : ℝ) (hη : 0 ≤ η) :
∀ᵐ ω ∂(P r),
((P r)[{ω' : Ω r | η * ((P r)[fun ω'' : Ω r =>
(inner ℝ (ω''.1 - zhat ψ T ω'') (S k (hist ψ ω''.1 ω''.2 T))) ^ 2 | histSigma ψ T]) ω'
≤ (inner ℝ (ω'.1 - zhat ψ T ω') (S k (hist ψ ω'.1 ω'.2 T))) ^ 2}.indicator
(fun _ => (1 : ℝ)) | histSigma ψ T]) ω
= 2 * (1 - cdf (gaussianReal 0 1) (Real.sqrt η)) := by sorry
end LinParamBandits.LowerBound