Far reference errors on a block: some far action has a small compensated cumulative loss difference
ProvedG26G.Sharp.far_probSetting. is a compact action set spanning , is a compact generator (), is the direction enumeration, and is a GIA-FTRL run of rounds (IsGIAFTRLRun) with cumulative loss estimate , run filtration , learning rate (gbeta) and magnitude constant (gB). The filtration used below is for and (Fx). The standing hypotheses Sharp hold: lies in the unit ball, , , is the unique minimizer of on , and the instance is sharp with modulus (H.sig): on . The corruption is bounded by : a.s. (IsCorruptedG). The projective body is and the cone body is ; , , and is the index of among the reference atoms (js).
Let , with , and let be a positive nondecreasing buffer with . Let with , , , for , , and for . Let , with , and . With (Dfar),
The compensated per-action variables are frozen at their first success and their inverse moments are controlled by the scalar interface with drift at least . A contraction argument on then passes from the per-point moments to a uniform statement. This is the "far" part of the reference block bound.
Formalization Note Rounds are 0-based.
import Mathlib
import Definitions.Def_IAFTRL_LinEnv
import Definitions.Def_IAFTRL_GIAFTRL
import Definitions.Def_IAFTRL_G26_body
import Definitions.Def_IAFTRL_G26_run
import Definitions.Def_IAFTRL_G26_window
open MeasureTheory ProbabilityTheory Set IAFTRL Matrix J11
open G26G
open G26 G26R
variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ} {θ astar : Fin d → ℝ}
variable {Ω : Type*} [mΩ : MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
{T : ℕ} {R : GRun d Ω}
open G26G.Sharp
variable (H : Sharp 𝒜 ℬ θ astar)
include Htheorem G26G.Sharp.far_prob (hR : IsGIAFTRLRun P 𝒜 ℬ e T R) {C : ℝ} (hC : 0 ≤ C)
(hcor : IsCorruptedG P 𝒜 θ C T R)
{τ : ℕ → ℝ} (hτpos : ∀ n, 0 < τ n) (hτmono : ∀ n, τ n ≤ τ (n + 1))
(hδ : ∀ n, τ (n + 1) - τ n ≤ 1) {m0 u : ℕ} (h2uT : 2 * u ≤ T) (hm0u : m0 ≤ u)
(hhalf : 2 * ((m0 : ℝ) + 1) ≤ (u : ℝ) + 1)
(hmP : ((4 * kk d : ℕ) : ℝ) + 1 ≤ 2 * ((m0 : ℝ) + 1))
(hτB : ∀ n, m0 ≤ n → gB d * (gbeta d (n + 1) + 3) ≤ τ n)
(hτm : 2 * (((4 * kk d : ℕ) : ℝ) + 1) ≤ τ m0)
(hτβ : ∀ n, m0 ≤ n → n < 2 * u →
40 * (((4 * kk d : ℕ) : ℝ) + 1) * gbeta d (n + 1) * ((n : ℝ) + 1) ≤ τ m0 ^ 2)
{ε : ℝ} (hε : 0 < ε) {hbv : ℝ} (hbC : hbv + 4 * C ≤ 2 * τ (2 * u))
{ρ : ℝ} (hρa : 4 * τ (2 * u) ≤ ρ) (hρb : 2 * (4 * C + 2 * τ (2 * u)) ≤ ρ) :
P.real {ω | ∃ s, u ≤ s ∧ s ≤ 2 * u ∧ ∃ a ∈ Dfar ℬ θ astar ε,
(a - astar) ⬝ᵥ R.cumEst s ω ≤ hbv} ≤
P.real (IW 𝒜 ℬ R θ astar C τ m0 (2 * u))ᶜ +
2 ^ (4 * kk d) * cK d * (((2 * u : ℕ) : ℝ) + 1) ^ (4 * kk d) / ρ ^ (4 * kk d) +
(2 * (4 * τ (2 * u))) ^ (4 * kk d) * (ρ / (4 * τ (2 * u))) ^ d *
(2 ^ (4 * kk d) * (4 / (((u : ℝ) + 1) * ε)) ^ (4 * kk d)) := by sorry