Weighted failure sum under a delayed cover of events
ProvedBanditAlgorithm.tsum_weight_of_tail_coverbanditssequential-analysis
Let be a probability measure and let , be families of events. Suppose that off a null set the failures of are covered by delayed failures of : for every ,
Then
A first weighted moment on one side costs a second on the other, and the delay is what buys the extra power. The mechanism is an exchange of the two sums, which in needs no summability side condition: a single failure of at round can spoil only the rounds with , whose total weight is
The null set is not decoration: in the intended application the covering holds only on the trajectories a sampling rule actually produces, and a policy cannot constrain the rest of a canonical trajectory space.
Preamble
import Definitions.Def_TrackAndStop open MeasureTheory ENNReal Filter Topology
Formal statement
theorem BanditAlgorithm.tsum_weight_of_tail_cover {α : Type*} [MeasurableSpace α]
{ν : MeasureTheory.Measure α} [MeasureTheory.IsProbabilityMeasure ν]
{A B : ℕ → Set α} {G : Set α} (hG : ν Gᶜ = 0)
{θ : ℝ} (hθ : 0 < θ) {N₀ : ℕ}
(hcover : ∀ n : ℕ, N₀ ≤ n →
(A n)ᶜ ∩ G ⊆ ⋃ m : {m : ℕ // ⌈θ * (n : ℝ)⌉₊ ≤ m}, (B (m : ℕ))ᶜ)
(hB : ∑' m : ℕ, ((m : ℝ≥0∞) + 1) ^ 2 * ν (B m)ᶜ ≠ ⊤) :
∑' n : ℕ, ((n : ℝ≥0∞) + 1) * ν (A n)ᶜ ≠ ⊤ := by
sorrySource
The exchange behind the settling-time estimate of Garivier & Kaufmann, Optimal Best Arm Identification with Fixed Confidence, COLT 2016, Proposition 13; stated measure-theoretically.