Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 38.6: UCRL2 regret O(DSAnlog⁡(nSA/δ))O(DS\sqrt{An\log(nSA/\delta)})O(DSAnlog(nSA/δ)​) (corrected root)

Proved
BanditAlgorithm.mdp_ucrl2_regret_bound_known_reward_diam_ge_one

by Shuze Chen · Jul 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

mdpregret-boundsreinforcement-learningucrl2

(UCRL2 regret bound, GOAL, Theorem 38.6 + Eq. (38.12); corrected root — supersedes the Disproved BanditAlgorithm.mdp_ucrl2_regret_bound.) Knowledge model (L&S pp. 522-523, standing assumption of §38.4-38.5: "we assume that only the transition matrix is unknown while the reward function is given"): the reward function r:S×A→[0,1]r : \mathcal S \times \mathcal A \to [0,1]r:S×A→[0,1] is quantified before the policy, so the learner may depend on rrr (UCRL2 uses it) but not on the transition function; its observed history of state-action pairs then determines every received reward.

Let S,A,nS, A, nS,A,n be positive and δ∈(0,1)\delta \in (0,1)δ∈(0,1). For every reward function rrr there is a policy π\piπ such that for every strongly connected MDP M=(S,A,P,r)M = (\mathcal S, \mathcal A, P, r)M=(S,A,P,r) with SSS states, AAA actions, diameter D(M)≥1D(M) \ge 1D(M)≥1, and every initial state distribution, with probability at least 1−δ1-\delta1−δ the random regret R^n=nρ∗−∑t=1nrAt(St)\hat R_n = n\rho^* - \sum_{t=1}^n r_{A_t}(S_t)R^n​=nρ∗−∑t=1n​rAt​​(St​) satisfies

R^n<C D(M) SAnlog⁡(nSAδ),\hat R_n < C\, D(M)\, S \sqrt{A n \log\left(\frac{n S A}{\delta}\right)},R^n​<CD(M)SAnlog(δnSA​)​,

encoded as P(R^n≥CD(M)SAnlog⁡(nSA/δ))≤δ\mathbb P\big(\hat R_n \ge C D(M) S \sqrt{A n \log(nSA/\delta)}\big) \le \deltaP(R^n​≥CD(M)SAnlog(nSA/δ)​)≤δ. Moreover (Eq. (38.12), the same algorithm run with δ=1/n\delta = 1/nδ=1/n), for every rrr there is a policy with

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

Both claims share one universal constant C>0C > 0C>0.

Nondegeneracy guard. The hypothesis D(M)≥1D(M) \ge 1D(M)≥1 is automatically satisfied by every strongly connected MDP with at least two states (travelling between distinct states takes at least one step). It excludes the degenerate one-state case D(M)=0D(M) = 0D(M)=0, where the purely multiplicative bound is 000 and even the book's literal statement fails — the accepted disproof of the previous root instantiates exactly that case. It also excludes the junk value D(M)=0D(M) = 0D(M)=0 that the real-valued diameter assigns to non-strongly-connected MDPs (book: D(M)=∞D(M) = \inftyD(M)=∞).

This is the capstone of Chapter 38: the price of learning an unknown transition structure under the average-reward criterion, complemented in this mission by the Ω(DSAn)\Omega(\sqrt{DSAn})Ω(DSAn​) lower bound (Theorem 38.7).

Preamble
import Definitions.Def_FiniteMDPLearning
import Mathlib.Data.Real.Sqrt
import Mathlib.Analysis.SpecialFunctions.Log.Basic


open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.mdp_ucrl2_regret_bound_known_reward_diam_ge_one :
    ∃ C : ℝ, 0 < C ∧
      (∀ S A n : ℕ, 0 < S → 0 < A → 0 < n →
        ∀ δ : ℝ, δ ∈ Set.Ioo (0 : ℝ) 1 →
          ∀ 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,
                  mdpMeasure M μ0 π n
                      {h | C * mdpDiameter M * S *
                          Real.sqrt (A * n * Real.log (n * S * A / δ)) ≤
                        mdpRegret M n h} ≤
                    ENNReal.ofReal δ) ∧
      (∀ 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
L&S Theorem 38.6 + Eq. (38.12), pp.522-523 (knowledge model: p.522 "only the transition matrix is unknown while the reward function is given")

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