Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The geometric hard-edge certificate implies the stochastic regret tradeoff

Proved
BanditAlgorithm.partial_monitoring_tradeoff_of_geometric_alternatives

by Harry_Xu · Aug 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

banditsinformation-theorykullback-leiblerpartial-monitoring

Assume a finite partial-monitoring game admits the two geometric alternatives from Theorem 37.12: a feedback-invisible normalized perturbation direction, valid environments ua=u−Δqu_a=u-\Delta qua​=u−Δq and ub=u+Δqu_b=u+\Delta qub​=u+Δq, a uniform loss penalty for actions outside NabN_{ab}Nab​, and Eq. (37.10) for actions inside NabN_{ab}Nab​. Then there are constants ε,δ>0\varepsilon,\delta>0ε,δ>0 and C≥0C\ge0C≥0 such that, for every horizon n≥1n\ge1n≥1, some x≥0x\ge0x≥0 satisfies

ε2x+nΔn8exp⁡(−CΔn2x)≤2Rn∗(G),Δn=δn−1/3.\frac{\varepsilon}{2}x+ \frac{n\Delta_n}{8}\exp(-C\Delta_n^2x) \le 2R_n^*(G), \qquad \Delta_n=\delta n^{-1/3}.2ε​x+8nΔn​​exp(−CΔn2​x)≤2Rn∗​(G),Δn​=δn−1/3.

Here xxx is the expected number of actions played outside NabN_{ab}Nab​ under the first alternative. This theorem is precisely the KL chain-rule, Bretagnolle–Huber testing, stochastic-to-adversarial minimax layer of the hard-game lower bound.

Preamble
import Definitions.Def_PartialMonitoringGame
import Mathlib.Analysis.SpecialFunctions.Pow.Real
Formal statement
theorem BanditAlgorithm.partial_monitoring_tradeoff_of_geometric_alternatives
    {k d : ℕ} {𝕊 : Type*} [Fintype 𝕊] [MeasurableSpace 𝕊] [DecidableEq 𝕊]
    (G : PartialMonitoringGame k d 𝕊)
    (hgeom : ∃ a b : Fin k, ∃ u q : Fin d → ℝ, ∃ ε δ : ℝ,
      NeighbouringActions G a b ∧ 0 < ε ∧ 0 < δ ∧
      (∑ i, q i) = 0 ∧
      (∑ i, (G.L a i - G.L b i) * q i) = 1 ∧
      (∀ c : Fin k, c ∈ pmNeighbourhood G a b → ∀ σ : 𝕊,
        ∑ i ∈ Finset.univ.filter (fun i ↦ G.Φ c i = σ), q i = 0) ∧
      ∀ Δ : ℝ, 0 < Δ → Δ ≤ δ →
        let ua := fun i ↦ u i - Δ * q i
        let ub := fun i ↦ u i + Δ * q i
        ua ∈ pmCell G a ∧ ub ∈ pmCell G b ∧
        (∀ c : Fin k, c ∉ pmNeighbourhood G a b →
          ε / 2 ≤ ∑ i, (G.L c i - G.L a i) * ua i ∧
          ε / 2 ≤ ∑ i, (G.L c i - G.L b i) * ub i) ∧
        (∀ c : Fin k, c ∈ pmNeighbourhood G a b →
          (∑ i, (G.L c i - G.L a i) * ua i) +
          (∑ i, (G.L c i - G.L b i) * ub i) = Δ)) :
    ∃ ε C δ : ℝ, 0 < ε ∧ 0 ≤ C ∧ 0 < δ ∧
      ∀ (n : ℕ), 1 ≤ n → ∃ x : ℝ, 0 ≤ x ∧
        ε / 2 * x +
            (n : ℝ) * (δ * (n : ℝ) ^ (-(1 : ℝ) / 3)) / 8 *
              Real.exp (-C * (δ * (n : ℝ) ^ (-(1 : ℝ) / 3)) ^ 2 * x) ≤
          2 * pmMinimaxRegret G n := by
  sorry
Source
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), Theorem 37.12, Steps 2–3, printed pp. 490–491, Eqs. (37.8)–(37.10), followed by the Bretagnolle–Huber inequality (Theorem 14.2).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me