Corollary B.1, p. 26 — Bernstein for bounded martingale differences: |Mₙ| ≤ 2√(Vₙ ln(n/δ)) + 3K ln(n/δ)
ProvedOptimisticPSRL.Concentration.corollaryB1_bernsteinbernstein-inequalityconcentrationmartingalep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be a probability space with a filtration , and let be a bounded martingale difference sequence: is -measurable, and . Put
If and , then with probability greater than ,
This is a Bernstein inequality with the random predictable variance in place of a deterministic variance bound, at the price of instead of . Agrawal and Jia derive it from a result of Seldin et al. (2012) and use it to prove Proposition 5.2.
Formalization Note Indices are shifted: is Z i for , measurable for ℱ i, with conditional expectation taken given ℱ (i-1). The bound is required almost surely. "With probability greater than " is the strict inequality , as printed.
Preamble
import Mathlib
Formal statement
namespace OptimisticPSRL.Concentration
open MeasureTheory
/-- **Corollary B.1** (Agrawal–Jia, arXiv:1705.07041v3, p. 26). Let `Z_1, …, Z_n` be a
martingale difference sequence for the filtration `ℱ` (`Z_i` is `ℱ_i`-measurable and
`E[Z_i | ℱ_{i−1}] = 0`) with `|Z_i| ≤ K`, `M_n = ∑_{i=1}^n Z_i` and
`V_n = ∑_{i=1}^n E[Z_i² | ℱ_{i−1}]`. For `n ≥ 96` and `δ ∈ (0, 1)`, with probability greater
than `1 − δ`, `|M_n| ≤ 2 √(V_n ln(n/δ)) + 3K ln(n/δ)`. -/
theorem corollaryB1_bernstein {Ω : Type*} {m0 : MeasurableSpace Ω} (μ : Measure Ω)
[IsProbabilityMeasure μ] (ℱ : Filtration ℕ m0) (Z : ℕ → Ω → ℝ) (K : ℝ) (n : ℕ) (δ : ℝ)
(hmeas : ∀ i < n, StronglyMeasurable[ℱ (i + 1)] (Z (i + 1)))
(hbdd : ∀ i < n, ∀ᵐ ω ∂μ, |Z (i + 1) ω| ≤ K)
(hmds : ∀ i < n, μ[Z (i + 1) | ℱ i] =ᵐ[μ] 0)
(hn : 96 ≤ n) (hδ0 : 0 < δ) (hδ1 : δ < 1) :
ENNReal.ofReal (1 - δ) <
μ {ω | |∑ i ∈ Finset.range n, Z (i + 1) ω| ≤
2 * Real.sqrt ((∑ i ∈ Finset.range n, (μ[fun ω' => Z (i + 1) ω' ^ 2 | ℱ i]) ω) *
Real.log (n / δ)) +
3 * K * Real.log (n / δ)} := by sorry
end OptimisticPSRL.Concentration
Source
Agrawal & Jia, Posterior sampling for reinforcement learning: worst-case regret bounds, arXiv:1705.07041v3, p. 26, Appendix B, Corollary B.1 (setting from Fact 3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.