Lemma 7 — the integral
ProvedEDPMBandit.lemma_7bandit-algorithmsmulti-armed-banditsp2o-gran-per-chapterp2o-plan-paperp2o-v1regret-boundsrisk-measures
For every real and integer ,
and if moreover , then
This computation turns the tail bound of Lemma 2 into the moment bounds of Lemma 6.
Formalization Note The improper integral is the Lebesgue integral over ; both claims form one conjunction.
Differences from the source: none.
Preamble
import Mathlib open MeasureTheory
Formal statement
namespace EDPMBandit
/-- Lemma 7, Cassel–Mannor–Zeevi, arXiv:1806.01380v3, pp.27–28: "For any real a > 0 and integer
m ≥ 0 we have that ∫_1^∞ x^{2m+1} exp(−ax²) dx = (exp(−a)/(2a^{m+1})) ∑_{j=0}^m (m!/j!) a^j. If
a ≥ 3 then we also have that ∫_1^∞ x^{2m+1} exp(−ax²) dx ≤ m! exp(−a)/2."
**Formalization Note.** The improper integral over `[1, ∞)` is the Lebesgue integral over
`Set.Ioi 1` (the integrand is integrable there). Both claims are one conjunction. -/
theorem lemma_7 (a : ℝ) (ha : 0 < a) (m : ℕ) :
(∫ x in Set.Ioi (1 : ℝ), x ^ (2 * m + 1) * Real.exp (-(a * x ^ 2))) =
Real.exp (-a) / (2 * a ^ (m + 1)) *
∑ j ∈ Finset.range (m + 1), ((m.factorial : ℝ) / (j.factorial : ℝ)) * a ^ j ∧
(3 ≤ a →
(∫ x in Set.Ioi (1 : ℝ), x ^ (2 * m + 1) * Real.exp (-(a * x ^ 2))) ≤
(m.factorial : ℝ) * Real.exp (-a) / 2) := by sorry
end EDPMBandit
Source
Cassel–Mannor–Zeevi, A General Framework for Bandit Problems Beyond Cumulative Objectives, arXiv:1806.01380v3, pp.27–28, Lemma 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.