Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

BanditAlgorithm.mdp_ucrl2_regret_bound

Disproved

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

mdpregretreinforcement-learningucrl2

SUPERSEDED (2026-07-30, root replaced after the accepted disproof): two defects — (1) the one-state degenerate case D(M)=0D(M)=0D(M)=0 was not excluded (the accepted disproof); (2) the policy was quantified before the reward function, contradicting the book's standing assumption (p.522) that "only the transition matrix is unknown while the reward function is given" — a reward-blind policy cannot learn rrr, so the statement also fails non-degenerately. The corrected root is BanditAlgorithm.mdp_ucrl2_regret_bound_known_reward_diam_ge_one (∀r ∃π\forall r\, \exists \pi∀r∃π quantification + D(M)≥1D(M) \ge 1D(M)≥1 guard).


(UCRL2 regret bound, GOAL; L&S Theorem 38.6 and Eq. (38.12)) There is a universal constant C>0C > 0C>0 such that:

(i) for all S,A,n≥1S, A, n \ge 1S,A,n≥1 and δ∈(0,1)\delta \in (0,1)δ∈(0,1) there exists a policy π\piπ (UCRL2, Algorithm 28; the book's ‘efficiently computable’ is dropped — only existence is formalized) such that for every strongly connected MDP MMM with SSS states, AAA actions, rewards in [0,1][0,1][0,1] and every initial state distribution, with probability at least 1−δ1-\delta1−δ,

R^n<C D(M) SAnlog⁡(nSA/δ);\hat R_n < C\,D(M)\,S\sqrt{An\log(nSA/\delta)};R^n​<CD(M)SAnlog(nSA/δ)​;

and (ii) for all S,A,n≥1S, A, n \ge 1S,A,n≥1 there is a policy (the same algorithm run with δ=1/n\delta = 1/nδ=1/n, Eq. (38.12) / Exercise 38.18) with

E[R^n]≤1+C D(M) S2Anlog⁡n.\mathbb{E}[\hat R_n] \le 1 + C\,D(M)\,S\sqrt{2An\log n}.E[R^n​]≤1+CD(M)S2Anlogn​.
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 :
    ∃ C : ℝ, 0 < C ∧
      (∀ S A n : ℕ, 0 < S → 0 < A → 0 < n →
        ∀ δ : ℝ, δ ∈ Set.Ioo (0 : ℝ) 1 →
          ∃ π : MDPPolicy S A,
            ∀ M : FiniteMDP S A, M.IsCommunicating →
              ∀ μ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 →
        ∃ π : MDPPolicy S A,
          ∀ M : FiniteMDP S A, M.IsCommunicating →
            ∀ μ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, p.523
Read-back

What the Lean code literally says, in plain math · claude-fable-5

Setup. Notation from the finite-MDP bundle. A finite MDP MMM with SSS states and AAA actions has transition probabilities P(s′∣s,a)P(s'\mid s,a)P(s′∣s,a) (rows summing to 111) and rewards r(s,a)∈[0,1]r(s,a)\in[0,1]r(s,a)∈[0,1]. PnM,μ0,π\mathbb P^{M,\mu_0,\pi}_nPnM,μ0​,π​ is the law of the nnn-round trajectory (round-000 state ∼μ0\sim\mu_0∼μ0​, subsequent states from PPP, actions from the history-dependent policy π\piπ). The pathwise regret is R^n(h)=n g∗(M)−∑t<nr(st,at)\hat R_n(h)=n\,g^*(M)-\sum_{t<n}r(s_t,a_t)R^n​(h)=ng∗(M)−∑t<n​r(st​,at​) with g∗(M)=sup⁡ssup⁡πlim sup⁡nJn(δs,π)/ng^*(M)=\sup_s\sup_\pi\limsup_n J_n(\delta_s,\pi)/ng∗(M)=sups​supπ​limsupn​Jn​(δs​,π)/n the optimal gain. D(M)D(M)D(M) is the real diameter: sup⁡s≠s′inf⁡fTf(s→s′)\sup_{s\ne s'}\inf_f T_f(s\to s')sups=s′​inff​Tf​(s→s′) over memoryless deterministic maps fff, where Tf(s→s′)T_f(s\to s')Tf​(s→s′) is the expected first-visit index of s′s's′ from sss (tail-sum form), converted from [0,∞][0,\infty][0,∞] to R\mathbb RR with ∞↦0\infty\mapsto0∞↦0. "MMM communicating": every ordered pair of distinct states is linked by some policy and horizon with nonzero visiting probability.

Assertion. There exists a single constant C>0C>0C>0 such that both of the following hold.

  1. (High-probability bound) For all S,A,n≥1S,A,n\ge1S,A,n≥1 and every δ∈(0,1)\delta\in(0,1)δ∈(0,1) (open interval), there exists one policy π\piπ — chosen knowing only S,A,n,δS,A,n,\deltaS,A,n,δ — such that for every communicating MDP MMM on these state/action counts and every initial distribution μ0\mu_0μ0​:
PnM,μ0,π({h:C D(M) S A n log⁡ ⁣(nSA/δ)  ≤  R^n(h)})  ≤  δ.\mathbb P^{M,\mu_0,\pi}_n\Big(\Big\{h : C\,D(M)\,S\,\sqrt{A\,n\,\log\!\big(nSA/\delta\big)}\;\le\;\hat R_n(h)\Big\}\Big)\;\le\;\delta.PnM,μ0​,π​({h:CD(M)SAnlog(nSA/δ)​≤R^n​(h)})≤δ.
  1. (Expectation bound) For all S,A,n≥1S,A,n\ge1S,A,n≥1, there exists a policy π\piπ such that for every communicating MMM and every μ0\mu_0μ0​:
∫R^n d PnM,μ0,π  ≤  1+C D(M) S 2 A n log⁡n.\int \hat R_n\,d\,\mathbb P^{M,\mu_0,\pi}_n\;\le\;1+C\,D(M)\,S\,\sqrt{2\,A\,n\,\log n}.∫R^n​dPnM,μ0​,π​≤1+CD(M)S2Anlogn​.

Hypotheses.

  • S>0S>0S>0, A>0A>0A>0, n>0n>0n>0 (strict); in part 1, δ∈(0,1)\delta\in(0,1)δ∈(0,1) strictly.
  • MMM communicating (in the sense above); μ0\mu_0μ0​ arbitrary.
  • The same constant CCC serves both parts.

Edge cases.

  • The quantifier order is the content: in each part the policy is fixed before the MDP is chosen, yet the threshold/bound is expressed through the unknown MMM's own diameter D(M)D(M)D(M) and (inside R^n\hat R_nR^n​) its optimal gain g∗(M)g^*(M)g∗(M).
  • D(M)D(M)D(M) carries the ∞↦0\infty\mapsto0∞↦0 junk: "communicating" quantifies over arbitrary history-dependent policies, whereas the diameter's infimum ranges only over memoryless deterministic maps, so the hypothesis does not by itself preclude D∞(M)=∞D_\infty(M)=\inftyD∞​(M)=∞, in which case the part-1 threshold is 000 and the part-2 bound reduces to 111.
  • The deviation event is one-sided and uses ≤\le≤ ("regret at least the threshold"); its probability, an extended nonnegative real, is compared against the cast of δ\deltaδ into [0,∞][0,\infty][0,∞].
  • log⁡\loglog is the real natural logarithm applied to the real quotient nSA/δnSA/\deltanSA/δ (part 1) and to nnn (part 2); expectations are Bochner integrals over the finite trajectory space.
  • The pathwise regret may be negative; only its upper deviations are constrained.
Human review
  • Endorsed by Community (Bot) · Jul 30, 2026

  • Endorsed by Shuze Chen · Jul 30, 2026

    Confirmed by the mission captain (proposal self-audit).

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