Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.2 — Evaluation at mean parameters

Proved
XuDRMDP.Finite.lemma_3_2

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

distributionally-robust-optimizationmarkov-decision-processp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let SSS be a finite nonempty staged state set with finite nonempty action sets AsA_sAs​, initial stage consisting of sinis^{ini}sini alone, finite horizon T≥1T\ge1T≥1, zero terminal rewards and discount 0<γ≤10<\gamma\le10<γ≤1. Assume the nested local parameter sets Ps1⊆⋯⊆PsnP_s^1\subseteq\cdots\subseteq P_s^nPs1​⊆⋯⊆Psn​ (n≥1n\ge1n≥1) are nonempty, convex and compact sets of valid transition/reward vectors. Local sets may couple all actions. Let 0=λ0≤λ1≤⋯≤λn=10=\lambda_0\le\lambda_1\le\cdots\le\lambda_n=10=λ0​≤λ1​≤⋯≤λn​=1. The local class CsC_sCs​ consists of all Borel probability laws supported on PsnP_s^nPsn​ with μs(Psi)≥λi\mu_s(P_s^i)\ge\lambda_iμs​(Psi​)≥λi​, and CSC_SCS​ consists of their statewise product laws. Policies are all history-dependent randomized policies on state/action histories, including null histories. Returns are the independent finite trajectory expectations, subsequently integrated against the parameter law.

For every policy π\piπ and every μ∈CS\mu\in C_Sμ∈CS​, let (pˉ,rˉ)=Eμ(p,r)(\bar p,\bar r)=E_\mu(p,r)(pˉ​,rˉ)=Eμ​(p,r). Then

W(π,μ)=u(π,pˉ,rˉ).W(\pi,\mu)=u(\pi,\bar p,\bar r).W(π,μ)=u(π,pˉ​,rˉ).

The left side integrates the independently defined trajectory return. The right side evaluates that same path sum at the mean parameter vector. No optimality, Markov property, or deterministic-action restriction is imposed on π\piπ.

Differences from the source:

  • encoding: finite states and state-dependent actions, one-based staged histories, and expected discounted trajectory returns → nonempty Fin types, zero-based stages, total policy extensions on unused histories, and explicit finite trajectory sums followed by Bochner integration; reason: finite relabeling and unused extensions preserve all source instances; compact outer support ensures integrability and finite bounded returns
Preamble
import Definitions.Def_XuDRMDP_Finite_Setup
import Definitions.Def_XuDRMDP_Finite_Policies
import Definitions.Def_XuDRMDP_Finite_Ambiguity
import Definitions.Def_XuDRMDP_Finite_Returns
import Definitions.Def_XuDRMDP_Finite_Robustness
open MeasureTheory
Formal statement
namespace XuDRMDP.Finite

theorem lemma_3_2 {n : ℕ} [NeZero n] {a : Fin n → ℕ} [∀ s, NeZero (a s)]
    (G : Setup n a) (U : Uncertainty G) (π : Policy a)
    (ν : Measure (Parameters n a)) (hν : ν ∈ globalClass U) :
    performance G π ν = totalReturn G π (globalMean ν) := by sorry

end XuDRMDP.Finite
Source
Xu and Mannor (2012), Distributionally Robust Markov Decision Processes, Mathematics of Operations Research 37(2), 288–300, DOI:10.1287/moor.1120.0540. Published basis; printed page = PDF page + 287. Lemma 3.2, printed p. 292 (PDF p. 5).
Read-back

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

Data.

  • n≥1n\ge1n≥1 states [n][n][n] and actions As={0,…,as−1}A_s=\{0,\dots,a_s-1\}As​={0,…,as​−1} with every as≥1a_s\ge1as​≥1.
  • A setup GGG: horizon T≥1T\ge1T≥1, discount γ∈(0,1]\gamma\in(0,1]γ∈(0,1], stage map σ<T\sigma<Tσ<T, and initial state s0s_0s0​, the unique state of stage 000.
  • An uncertainty structure UUU: confidence levels 0≤c0≤⋯≤cL=10\le c_0\le\dots\le c_L=10≤c0​≤⋯≤cL​=1, and nested nonempty convex compact sets Cs,0⊆⋯⊆Cs,LC_{s,0}\subseteq\dots\subseteq C_{s,L}Cs,0​⊆⋯⊆Cs,L​ of valid local MDP coordinates in Xs=RAs×[n]×RAs\mathcal X_s=\mathbb R^{A_s\times[n]}\times\mathbb R^{A_s}Xs​=RAs​×[n]×RAs​. Valid means the point equals some imported-type MDP's data at sss, has zero rewards if σ(s)=T−1\sigma(s)=T-1σ(s)=T−1, and otherwise zero transition entries to states not at stage σ(s)+1\sigma(s)+1σ(s)+1.
  • An arbitrary policy π\piπ, assigning to every history a probability vector on the current state's actions.
  • A measure ν\nuν on X=∏sXs\mathcal X=\prod_s\mathcal X_sX=∏s​Xs​ in the global class, i.e. ν=⨂sμs\nu=\bigotimes_s\mu_sν=⨂s​μs​ for some family with each μs\mu_sμs​ a probability measure, μs(Cs,L)=1\mu_s(C_{s,L})=1μs​(Cs,L​)=1 and μs(Cs,i)≥ci\mu_s(C_{s,i})\ge c_iμs​(Cs,i​)≥ci​ for all iii.

Total return. For a parameter x=(psx,rsx)sx=(p^x_s,r^x_s)_sx=(psx​,rsx​)s​, the total return u(π,x)u(\pi,x)u(π,x) is the finite sum, over sequences (s0′,b0),…,(sT−2′,bT−2)(s'_0,b_0),\dots,(s'_{T-2},b_{T-2})(s0′​,b0​),…,(sT−2′​,bT−2​) (bt∈Ast′b_t\in A_{s'_t}bt​∈Ast′​​) and final states j∈[n]j\in[n]j∈[n], of

1[σ(st′)=t ∀t; s0′=s0 (T≥2); σ(j)=T−1] ∏t<T−1π(Ht)(bt) pst′x(bt,st+1′)⋅∑t<T−1γtrst′x(bt),\mathbf 1\big[\sigma(s'_t)=t\ \forall t;\ s'_0=s_0\ (T\ge2);\ \sigma(j)=T-1\big]\ \prod_{t<T-1}\pi(H_t)(b_t)\,p^x_{s'_t}(b_t,s'_{t+1})\cdot\sum_{t<T-1}\gamma^t r^x_{s'_t}(b_t),1[σ(st′​)=t ∀t; s0′​=s0​ (T≥2); σ(j)=T−1] t<T−1∏​π(Ht​)(bt​)pst′​x​(bt​,st+1′​)⋅t<T−1∑​γtrst′​x​(bt​),

where:

  • sT−1′:=js'_{T-1}:=jsT−1′​:=j;
  • HtH_tHt​ is the history with past (s0′,b0),…,(st−1′,bt−1)(s'_0,b_0),\dots,(s'_{t-1},b_{t-1})(s0′​,b0​),…,(st−1′​,bt−1​) and current state st′s'_tst′​.

Mean parameter. xˉ\bar xxˉ is the parameter with xˉs=∫xs dν(x)\bar x_s=\int x_s\,d\nu(x)xˉs​=∫xs​dν(x), a vector-valued Bochner integral.

Claim.

∫u(π,x) dν(x)=u(π,xˉ).\int u(\pi,x)\,d\nu(x)=u(\pi,\bar x).∫u(π,x)dν(x)=u(π,xˉ).

Degenerate cases.

  • If T=1T=1T=1, both sides are 000: the sum runs over the single empty sequence with zero reward.
  • Integrals are Bochner integrals, equal by convention to 000 (or the zero vector) for non-integrable integrands. The identity is asserted with that convention.
  • xˉ\bar xxˉ is not required to lie in any Cs,iC_{s,i}Cs,i​ or to be valid.
  • The transition factors are raw real coordinates with no normalisation required by the statement.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 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