Proof of Proposition 5.2, p. 21 — (Σₜ Zₜ)/n = (p̂ − p)ᵀh
ProvedOptimisticPSRL.Concentration.proof_prop5_2_martingale_sum_eq_projectionLet , , and let , be as in the setting. Let , , be a sequence of trial outcomes each of which has positive probability, , with empirical vector and . With ,
This display is the first step of the proof of Proposition 5.2: the projection deviation is the average of the martingale differences , to which Bernstein's inequality is then applied.
Formalization Note This is the iid reading of the paper's display: the indicator equals one for every trial and the random count equals . The hypothesis holds almost surely and is needed for the middle expression, whose range omits the last state: when a zero-probability state is drawn the last term need not vanish. The three equalities are stated as a conjunction, in the paper's order. is needed because is an average.
import Mathlib import Definitions.Def_OptimisticPSRL_Concentration_Setting
namespace OptimisticPSRL.Concentration
/-- Proof of Proposition 5.2 (Agrawal–Jia, arXiv:1705.07041v3, p. 21, second display), iid
reading: for every outcome sequence `ω` of `n ≥ 1` trials whose outcomes all have positive
probability under `p`,
`(∑_t Z_t)/n = ∑_i c_i p̂_i − ∑_i (c_i p_i/(p_i+⋯+p_S))(p̂_i+⋯+p̂_S)
= ∑_{i=1}^{S−1} (ŷ_i − y_i)(p̂_i+⋯+p̂_S) c_i = (p̂ − p)ᵀh`. -/
theorem proof_prop5_2_martingale_sum_eq_projection {S n : ℕ} (p h : Fin S → ℝ)
(hp : IsProbVec p) (hn : 0 < n) (ω : Fin n → Fin S) (hω : ∀ t, 0 < p (ω t)) :
((∑ t, ∑ i, Zcoord p h i (ω t)) / n =
∑ i, cCoef p h i * phat ω i - ∑ i, cCoef p h i * p i / tail p i * tail (phat ω) i) ∧
(∑ i, cCoef p h i * phat ω i - ∑ i, cCoef p h i * p i / tail p i * tail (phat ω) i =
∑ i ∈ belowLast S, (yRatio (phat ω) i - yRatio p i) * tail (phat ω) i * cCoef p h i) ∧
(∑ i ∈ belowLast S, (yRatio (phat ω) i - yRatio p i) * tail (phat ω) i * cCoef p h i =
∑ i, (phat ω i - p i) * h i) := by sorry
end OptimisticPSRL.Concentration
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.