Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

UCRL2 expected regret bound with known rewards

Proved
BanditAlgorithm.mdp_ucrl2_expected_regret_known_reward_diam_ge_one

by Harry_Xu · Jul 30, 2026 · Mathlib c5ea003 (Lean v4.30.0)

banditsexpected-regretreinforcement-learningucrl2

There is a universal constant C>0C>0C>0 such that, for every positive number of states SSS, actions AAA, and rounds nnn, and every known reward function r:S×A→[0,1]r:\mathcal S\times\mathcal A\to[0,1]r:S×A→[0,1], some policy independent of the unknown transition matrix satisfies, for every communicating MDP MMM with reward function rrr, diameter D(M)≥1D(M)\ge1D(M)≥1, and every initial distribution,

E[R^n]≤1+CD(M)S2Anlog⁡n.\mathbb E[\widehat R_n] \le 1+C D(M)S\sqrt{2A n\log n}.E[Rn​]≤1+CD(M)S2Anlogn​.

This is the expected-regret form of UCRL2 obtained from the high-probability analysis with a horizon-dependent confidence level. It uses the same known-reward learning model as Theorem 38.6 and excludes only the zero-diameter degeneracy.

Formalization Note The policy may depend on the horizon and the known reward function, matching the quantifier order in the source analysis.

Preamble
import Definitions.Def_FiniteMDPLearning

open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.mdp_ucrl2_expected_regret_known_reward_diam_ge_one :
    ∃ C : ℝ, 0 < C ∧
      ∀ S A n : ℕ, 0 < S → 0 < A → 0 < n →
        ∀ r : Fin S → Fin A → ℝ, (∀ s a, r s a ∈ Set.Icc (0 : ℝ) 1) →
          ∃ π : MDPPolicy S A,
            ∀ M : FiniteMDP S A, M.r = r → M.IsCommunicating →
              1 ≤ mdpDiameter M →
              ∀ μ0 : MDPStateDistribution S,
                ∫ h, mdpRegret M n h ∂(mdpMeasure M μ0 π n) ≤
                  1 + C * mdpDiameter M * S *
                    Real.sqrt (2 * A * n * Real.log n) := by
  sorry
Source
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Eq. (38.12), printed p. 523 / PDF p. 532, derived from Theorem 38.6 in Exercise 38.18.

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