Lemma 2.2 — Risk(T, ψ) ≥ ½ Σ_k E[‖Z‖ Σ_t (U_t′S^k_T)² + (T/‖Z‖)((Z − Ẑ_T)′S^k_T)²]
ProvedLinParamBandits.LowerBound.risk_decompositionWork in the model of Section 2: arms on the unit sphere of (), prior , standard normal noise, and a fixed policy with arms . Let , and let be orthonormal vectors, orthogonal to , each a measurable function of the history .
Lemma 2.2 (Risk Decomposition). For any ,
The first term inside the expectation measures how much the policy explored in the direction , the second the squared estimation error in that direction; the lemma bounds the risk below by both.
Formalization Note The expectations on the right are lower Lebesgue integrals of nonnegative quantities, valued in . On the event , which has prior probability zero, Lean's convention applies. Orthogonality to is required almost surely, since is defined up to null sets; orthonormality is required for every history.
import Mathlib import Definitions.Def_LinParamBandits_LowerBound_Model open MeasureTheory ProbabilityTheory
namespace LinParamBandits.LowerBound
/-- Lemma 2.2 (Risk Decomposition), Rusmevichientong, Tsitsiklis, arXiv:0812.3465v2, p. 9.
Standing assumptions of Sec. 2 (p. 9): arms on the unit sphere, prior `N(0, I_r/r)`; the vectors
`S k` (the paper's `S^1_T, …, S^{r-1}_T`) are orthonormal, orthogonal to `Ẑ_T`, and functions of
the history `H_T`. At `Z = 0` (prior probability zero) Lean's `T / 0 = 0`. -/
theorem risk_decomposition (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) :
2⁻¹ * ∑ k, ∫⁻ ω, ENNReal.ofReal
(‖ω.1‖ * ∑ t ∈ Finset.range T, (inner ℝ (arm ψ ω.1 ω.2 t) (S k (hist ψ ω.1 ω.2 T))) ^ 2
+ (T : ℝ) / ‖ω.1‖ * (inner ℝ (ω.1 - zhat ψ T ω) (S k (hist ψ ω.1 ω.2 T))) ^ 2) ∂(P r)
≤ risk ψ T := by sorry
end LinParamBandits.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.