Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Hard partial-monitoring lower bound from the information–regret tradeoff

Proved
BanditAlgorithm.partial_monitoring_hard_lower_of_tradeoff

by Harry_Xu · Aug 5, 2026 · Mathlib c5ea003 (Lean v4.30.0)

banditsinformation-theorypartial-monitoring

Let GGG be a finite partial-monitoring game. Suppose there are game-dependent constants ε,δ>0\varepsilon,\delta>0ε,δ>0 and C≥0C\ge0C≥0 such that, for every n≥1n\ge1n≥1, some x≥0x\ge0x≥0 satisfies

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

Then there is a constant cG>0c_G>0cG​>0 for which

Rn∗(G)≥cGn2/3R_n^*(G)\ge c_G n^{2/3}Rn∗​(G)≥cG​n2/3

for every horizon nnn. This formal bridge isolates the final optimization in the proof of the hard partial-monitoring lower bound from the preceding geometric and information-theoretic construction.

Preamble
import Definitions.Def_PartialMonitoringGame
import Theorems.Thm_BanditAlgorithm_partial_monitoring_hard_tradeoff_analytic

open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.partial_monitoring_hard_lower_of_tradeoff
    {k d : ℕ} {𝕊 : Type*} [Fintype 𝕊] [MeasurableSpace 𝕊]
    (G : PartialMonitoringGame k d 𝕊)
    (htrade : ∃ ε 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) :
    ∃ c : ℝ, 0 < c ∧
      ∀ n : ℕ, c * (n : ℝ) ^ ((2 : ℝ) / 3) ≤ pmMinimaxRegret G n := by sorry
Source
Formal bridge for Lattimore and Szepesvári, Bandit Algorithms, Chapter 37, Theorem 37.12 proof, printed p. 491, last three displays and Exercise 37.7; it invokes the separately proved p.491 analytic optimization theorem.

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