Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Lemma 5.6, p. 13, (17) — 1 + Q†E ≤ E + δ1 implies E ≥ (1 − δ)Ẽ for the expected travel times Ẽ

Proved
OptimisticPSRL.Diameter.travelTime_le_of_supersolution

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

absorbing-chaincomparisonhitting-timemarkov-chainmdpp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let M′\mathcal M'M′ be a finite MDP (in the application, the extended MDP M~\tilde{\mathcal M}M~) with transition probability vectors Qs,aQ_{s,a}Qs,a​, let π~\tilde\piπ~ be a deterministic stationary policy, s2s_2s2​ a target state, δ∈[0,1)\delta\in[0,1)δ∈[0,1), and E=(Es)s∈SE=(E_s)_{s\in\mathcal S}E=(Es​)s∈S​ a vector with entries in [0,∞][0,\infty][0,∞]. Write Qπ~†Q^{\dagger}_{\tilde\pi}Qπ~†​ for the (S−1)×(S−1)(S-1)\times(S-1)(S−1)×(S−1) matrix with entries Qs,π~(s)(s′)Q_{s,\tilde\pi(s)}(s')Qs,π~(s)​(s′), s,s′≠s2s,s'\neq s_2s,s′=s2​. Suppose that for every s≠s2s\neq s_2s=s2​

1+∑s′≠s2Qs,π~(s)(s′) Es′  ≤  Es+δ,1+\sum_{s'\neq s_2} Q_{s,\tilde\pi(s)}(s')\,E_{s'} \;\le\; E_s+\delta,1+s′=s2​∑​Qs,π~(s)​(s′)Es′​≤Es​+δ,

that is, 1+Qπ~†E≤E+δ1\mathbf 1+Q^{\dagger}_{\tilde\pi}E\le E+\delta\mathbf 11+Qπ~†​E≤E+δ1 (equivalently (I−Qπ~†)E≥(1−δ)1(I-Q^{\dagger}_{\tilde\pi})E\ge(1-\delta)\mathbf 1(I−Qπ~†​)E≥(1−δ)1, display (17)). Then the expected numbers of steps E~s=Ts→s2π~\tilde E_s=T^{\tilde\pi}_{s\to s_2}E~s​=Ts→s2​π~​ to reach s2s_2s2​ in M′\mathcal M'M′ under π~\tilde\piπ~ satisfy

(1−δ) E~s  ≤  Esfor every s≠s2.(1-\delta)\,\tilde E_s \;\le\; E_s\qquad\text{for every } s\neq s_2.(1−δ)E~s​≤Es​for every s=s2​.

This is the comparison step of the proof of Lemma 5.6: with EEE the vector of minimum expected times of the true MDP and π~\tilde\piπ~ the policy that, in each state, picks a sample satisfying (16), it gives E≥(1−δ)E~E\ge(1-\delta)\tilde EE≥(1−δ)E~, hence E~s1≤D/(1−δ)\tilde E_{s_1}\le D/(1-\delta)E~s1​​≤D/(1−δ).

Formalization Note. States are Fin S (0-based) and E~s\tilde E_sE~s​ is the platform's mdpTravelTime M' g s s₂. The hypothesis is the left half of (17), E≥1+Qπ~†E−δ1E\ge \mathbf 1+Q^{\dagger}_{\tilde\pi}E-\delta\mathbf 1E≥1+Qπ~†​E−δ1, with δ\deltaδ moved to the other side because [0,∞][0,\infty][0,∞] has no subtraction; the conclusion is E≥(1−δ)E~E\ge(1-\delta)\tilde EE≥(1−δ)E~ without the matrix inverse (I−Qπ~†)−1(I-Q^{\dagger}_{\tilde\pi})^{-1}(I−Qπ~†​)−1. Unlike the paper's argument, the statement does not assume that the entries of QQQ are strictly positive (the paper derives this from the Dirichlet law of the samples); the transition vectors are arbitrary. Values may be ∞\infty∞; sums and products are in [0,∞][0,\infty][0,∞], and 1−δ1-\delta1−δ is computed in R≥0\mathbb R_{\ge0}R≥0​ (positive since δ<1\delta<1δ<1).

Preamble
import Mathlib
import Definitions.Def_FiniteMDPLearning
open BanditAlgorithm NNReal ENNReal
Formal statement
namespace OptimisticPSRL.Diameter
theorem travelTime_le_of_supersolution {S A' : ℕ} (M' : FiniteMDP S A') (g : Fin S → Fin A')
    (tgt : Fin S) (E : Fin S → ℝ≥0∞) (δ : ℝ≥0) (hδ : δ < 1)
    (hsuper : ∀ s, s ≠ tgt →
      1 + ∑ s' ∈ Finset.univ.erase tgt, (M'.P s (g s) s' : ℝ≥0∞) * E s' ≤ E s + δ) :
    ∀ s, s ≠ tgt → ((1 - δ : ℝ≥0) : ℝ≥0∞) * mdpTravelTime M' g s tgt ≤ E s := by sorry
end OptimisticPSRL.Diameter
Source
Agrawal & Jia, Posterior sampling for reinforcement learning: worst-case regret bounds, arXiv:1705.07041v3, p. 13, proof of Lemma 5.6, display (17) and the following display (E ≥ (1 − δ)Ẽ)
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