Lemma 33 — Hoeffding's inequality uniformly over sample sizes and at a predictable random time
ProvedFoundationsRL.TailBounds.lemma_33concentration-inequalitiesmartingalesp2o-gran-per-chapterp2o-plan-bookp2o-v1reinforcement-learning
Let be i.i.d. real random variables with values in almost surely, and write for their common mean. For every the following two statements hold.
- With probability at least , simultaneously for all ,
- Let be a random variable with values in such that, for every , the event is determined by (for : it is trivial). Then with probability at least ,
The price of uniformity over all sample sizes is the factor inside the logarithm. The second statement lets an algorithm decide adaptively when to stop sampling and still use Hoeffding's bound at the random time it stops.
Formalization Note The bound is one-sided, as printed. The variables are indexed by , mutually independent, each with the law of . " is a measurable function of " is measurability of for the -algebra generated by . Probabilities are real numbers (μ.real).
Differences from the source:
- encoding: Z₁, …, Z_T i.i.d. with a generic copy Z, mean E[Z] → Z i for i ∈ {1, …, T} mutually independent, each identically distributed with Z 1; E[Z] = ∫ Z 1; reason: the notes' E[Z] is the common mean; same instances
- encoding: I{τ ≤ t} is a measurable function of Z₁, …, Z_{t−1} → {τ ≤ t} is measurable for the σ-algebra generated by Z₁, …, Z_{t−1} (trivial at t = 1); reason: a {0,1}-valued function is σ(Z₁..Z_{t−1})-measurable iff it is a measurable function of Z₁..Z_{t−1} (Doob–Dynkin); same instances
- encoding: T ≥ 1, implicit (a sample Z₁, …, Z_T) → T ∈ ℕ; reason: at T = 0 no instance changes: (A.1) quantifies over an empty range and no τ takes values in the empty [T], so both claims hold trivially
- encoding: δ ∈ (0, 1), implicit → δ > 0; reason: for δ ≥ 1 the probability bound 1 − δ ≤ 0 is trivial; only δ ≤ 0, where log(δ⁻¹) is undefined, is excluded
Preamble
import Mathlib open MeasureTheory ProbabilityTheory
Formal statement
namespace FoundationsRL.TailBounds
/-- **Lemma 33** (Hoeffding's inequality with adaptive stopping time). For i.i.d. `Z₁, …, Z_T`
with values in `[a, b]` almost surely, with probability at least `1 − δ`,
`(1/T′) ∑_{i=1}^{T′} Z_i − E[Z] ≤ (b − a) √(log(T/δ)/(2T′))` for all `1 ≤ T′ ≤ T` (A.1).
As a consequence, for any random `τ ∈ [T]` such that for all `t ∈ [T]` the indicator `I{τ ≤ t}`
is a measurable function of `Z₁, …, Z_{t−1}`, with probability at least `1 − δ`,
`(1/τ) ∑_{i=1}^{τ} Z_i − E[Z] ≤ (b − a) √(log(T/δ)/(2τ))` (A.2).
Foster & Rakhlin, *Foundations of Reinforcement Learning and Interactive Decision Making*,
arXiv:2312.16730v1, Lemma 33, (A.1)–(A.2), p. 156.
**Formalization Note.** The variables are `Z i` for `i ∈ {1, …, T}` (the values of `Z` at other
indices play no role); they are mutually independent and each has the law of `Z 1`, so
`E[Z] = ∫ Z 1`. The bound is one-sided, as printed. "`I{τ ≤ t}` is a measurable function of
`Z₁, …, Z_{t−1}`" is `{τ ≤ t}` measurable for the σ-algebra generated by `Z₁, …, Z_{t−1}`
(the trivial σ-algebra at `t = 1`). `δ > 0` is the only restriction on `δ`; for `δ ≥ 1` both
claims are trivial. Probabilities are `μ.real`. -/
theorem lemma_33 {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(T : ℕ) (Z : ℕ → Ω → ℝ)
(hindep : iIndepFun (fun i : Finset.Icc 1 T => Z i) μ)
(hid : ∀ i ∈ Finset.Icc 1 T, IdentDistrib (Z i) (Z 1) μ μ)
(a b : ℝ) (hab : ∀ i ∈ Finset.Icc 1 T, ∀ᵐ ω ∂μ, Z i ω ∈ Set.Icc a b)
(δ : ℝ) (hδ : 0 < δ) :
1 - δ ≤ μ.real {ω | ∀ T' ∈ Finset.Icc 1 T,
(1 / (T' : ℝ)) * ∑ i ∈ Finset.Icc 1 T', Z i ω - ∫ ω', Z 1 ω' ∂μ ≤
(b - a) * Real.sqrt (Real.log ((T : ℝ) / δ) / (2 * (T' : ℝ)))} ∧
∀ τ : Ω → ℕ, (∀ ω, τ ω ∈ Finset.Icc 1 T) →
(∀ t ∈ Finset.Icc 1 T,
MeasurableSet[⨆ i ∈ Finset.Ico 1 t, MeasurableSpace.comap (Z i) inferInstance]
{ω | τ ω ≤ t}) →
1 - δ ≤ μ.real {ω |
(1 / (τ ω : ℝ)) * ∑ i ∈ Finset.Icc 1 (τ ω), Z i ω - ∫ ω', Z 1 ω' ∂μ ≤
(b - a) * Real.sqrt (Real.log ((T : ℝ) / δ) / (2 * (τ ω : ℝ)))} := by sorry
end FoundationsRL.TailBounds
Source
Foster & Rakhlin, Foundations of Reinforcement Learning and Interactive Decision Making, arXiv:2312.16730v1, Lemma 33, (A.1)–(A.2), p. 156
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.