Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.6, p. 12 — if every state-action pair has a sample δ-optimistic for every E^s, then D(M̃) ≤ D/(1−δ)

Proved
OptimisticPSRL.Diameter.lemma5_6_extended_diameter_le

by mikedeng1 · Oct 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

diameterextended-mdphitting-timemdpp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1posterior-samplingreinforcement-learning

Let M\mathcal MM be a finite MDP with states S\mathcal SS, actions A\mathcal AA, transition probability vectors Ps,aP_{s,a}Ps,a​ and diameter D=D(M)∈[0,∞]D=D(\mathcal M)\in[0,\infty]D=D(M)∈[0,∞] (Definition 2: the maximum over ordered pairs of distinct states s≠s′s\neq s's=s′ of the minimum over deterministic stationary policies of the expected number of steps from sss to s′s's′). For each target state sss let Es∈[0,∞]SE^{s}\in[0,\infty]^{\mathcal S}Es∈[0,∞]S be the vector of minimum expected times to reach sss, Es′s=min⁡πTs′→sπE^{s}_{s'}=\min_{\pi}T^{\pi}_{s'\to s}Es′s​=minπ​Ts′→sπ​.

Let ψ≥0\psi\ge 0ψ≥0 and let Qs,ajQ^{j}_{s,a}Qs,aj​, j=1,…,ψj=1,\dots,\psij=1,…,ψ, be probability vectors on S\mathcal SS, one family for every state-action pair, and let M~\tilde{\mathcal M}M~ be the extended MDP in which taking action aja^{j}aj in state sss moves according to Qs,ajQ^{j}_{s,a}Qs,aj​. Let δ∈[0,1)\delta\in[0,1)δ∈[0,1). Suppose that for every target state sss, every state s′s's′ and every action aaa there is a sample index jjj with

Qs′,aj⋅Es  ≤  Ps′,a⋅Es+δ.(16)Q^{j}_{s',a}\cdot E^{s} \;\le\; P_{s',a}\cdot E^{s}+\delta. \tag{16}Qs′,aj​⋅Es≤Ps′,a​⋅Es+δ.(16)

Then

D(M~)  ≤  D(M)1−δ.D(\tilde{\mathcal M}) \;\le\; \frac{D(\mathcal M)}{1-\delta}.D(M~)≤1−δD(M)​.

In the paper this lemma is what makes the sampled extended MDP of each epoch communicating with diameter of the same order as the true one; combined with Lemma 5.7, which shows that (16) holds with δ≤1/2\delta\le 1/2δ≤1/2 with high probability for the posterior samples, it yields D(M~k)≤2DD(\tilde{\mathcal M}^{k})\le 2DD(M~k)≤2D, an ingredient of the regret bound (Theorem 1).

Formalization Note. States, actions and samples are 0-based (Fin S, Fin A, Fin ψ); the extended MDP is extendedMDP M Q hQ, with action aja^{j}aj encoded as finProdFinEquiv (a, j) in Fin (A * ψ). Diameters are the platform's mdpDiameterENN in [0,∞][0,\infty][0,∞], EsE^{s}Es is minTravel M s, the inner products are ∑iQs′,aj(i)Eis\sum_i Q^{j}_{s',a}(i)E^{s}_i∑i​Qs′,aj​(i)Eis​ computed in [0,∞][0,\infty][0,∞] (with 0⋅∞=00\cdot\infty=00⋅∞=0), and D/(1−δ)D/(1-\delta)D/(1−δ) is division in [0,∞][0,\infty][0,∞] by the positive number 1−δ1-\delta1−δ. The printed (16) uses the letter sss both for the target of EsE^{s}Es and for the state of Ps,aP_{s,a}Ps,a​, quantified "for every s,as,as,a"; the proof applies it at the current state s≠s2s\neq s_2s=s2​ with target s2s_2s2​, so the target is quantified separately here (for every target, state and action). No communicating assumption is made: if D(M)=∞D(\mathcal M)=\inftyD(M)=∞ the bound holds trivially, so the statement generalizes the paper's. The sample vectors are arbitrary probability vectors; no positivity of their entries and no distributional assumption is made.

Preamble
import Mathlib
import Definitions.Def_FiniteMDPLearning
import Definitions.Def_OptimisticPSRL_Diameter_Setting
open BanditAlgorithm NNReal ENNReal
Formal statement
namespace OptimisticPSRL.Diameter
theorem lemma5_6_extended_diameter_le {S A ψ : ℕ} (M : FiniteMDP S A)
    (Q : Fin S → Fin A → Fin ψ → Fin S → ℝ≥0) (hQ : ∀ s a j, ∑ i, Q s a j i = 1)
    (δ : ℝ≥0) (hδ : δ < 1)
    (h16 : ∀ tgt s : Fin S, ∀ a : Fin A, ∃ j : Fin ψ,
      ∑ i, (Q s a j i : ℝ≥0∞) * minTravel M tgt i ≤
        ∑ i, (M.P s a i : ℝ≥0∞) * minTravel M tgt i + δ) :
    mdpDiameterENN (extendedMDP M Q hQ) ≤ mdpDiameterENN M / ((1 - δ : ℝ≥0) : ℝ≥0∞) := by sorry
end OptimisticPSRL.Diameter
Source
Agrawal & Jia, Posterior sampling for reinforcement learning: worst-case regret bounds, arXiv:1705.07041v3, p. 12, Lemma 5.6 (display (16)); proof pp. 12–13
Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 15, 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