Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.3 — Exact attainable mean set

Proved
XuDRMDP.Finite.lemma_3_3

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 state sss, the set of attainable local means is exactly

{∫x dμs(x):μs∈Cs}=P^s={∑i=1n(λi−λi−1)xi:xi∈Psi}.\left\{\int x\,d\mu_s(x):\mu_s\in C_s\right\}=\widehat P_s =\left\{\sum_{i=1}^n(\lambda_i-\lambda_{i-1})x_i:x_i\in P_s^i\right\}.{∫xdμs​(x):μs​∈Cs​}=Ps​={i=1∑n​(λi​−λi−1​)xi​:xi​∈Psi​}.

This is set equality in both directions for the full Borel-law class. Repeated confidence levels, zero increments, identical nested sets and singleton sets are included.

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
  • reading: Definition 3.2 displays (r,p) in the weighted sum but (p,r) in its membership condition → consistent (p,r) coordinates in the reduction set; reason: Lemma 3.3 and its proof fix the intended order; see insight I1
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_3 {n : ℕ} [NeZero n] {a : Fin n → ℕ} [∀ s, NeZero (a s)]
    (G : Setup n a) (U : Uncertainty G) (s : Fin n) :
    {x | ∃ μ ∈ localClass U s, localMean μ = x} = reducedSet U s := 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.3, 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 TTT, discount γ\gammaγ, stage map σ<T\sigma<Tσ<T, and initial state s0s_0s0​.
  • An uncertainty structure UUU consisting of:
    • L+1L+1L+1 confidence levels 0≤c0≤⋯≤cL=10\le c_0\le\dots\le c_L=10≤c0​≤⋯≤cL​=1;
    • for each state sss, sets Cs,0⊆Cs,1⊆⋯⊆Cs,LC_{s,0}\subseteq C_{s,1}\subseteq\dots\subseteq C_{s,L}Cs,0​⊆Cs,1​⊆⋯⊆Cs,L​ in Xs=RAs×[n]×RAs\mathcal X_s=\mathbb R^{A_s\times[n]}\times\mathbb R^{A_s}Xs​=RAs​×[n]×RAs​, each nonempty, convex and compact, all of whose points are valid local MDP coordinates at sss for GGG. 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.
  • A fixed state sss.

Let Ps\mathcal P_sPs​ be the set of measures μ\muμ on Xs\mathcal X_sXs​ (standard Borel σ-algebra) with:

  • μ\muμ a probability measure;
  • μ(Cs,L)=1\mu(C_{s,L})=1μ(Cs,L​)=1;
  • μ(Cs,i)≥ci\mu(C_{s,i})\ge c_iμ(Cs,i​)≥ci​ for every iii.

Let Δ0=c0\Delta_0=c_0Δ0​=c0​ and Δi=ci−ci−1\Delta_i=c_i-c_{i-1}Δi​=ci​−ci−1​ for 1≤i≤L1\le i\le L1≤i≤L.

Claim. The set of means of measures in Ps\mathcal P_sPs​ equals the weighted Minkowski sum:

{∫y dμ(y) : μ∈Ps}={∑i=0LΔi yi : yi∈Cs,i for each i}.\Big\{\int y\,d\mu(y)\ :\ \mu\in\mathcal P_s\Big\}=\Big\{\sum_{i=0}^L\Delta_i\,y_i\ :\ y_i\in C_{s,i}\ \text{for each } i\Big\}.{∫ydμ(y) : μ∈Ps​}={i=0∑L​Δi​yi​ : yi​∈Cs,i​ for each i}.

Means are vector-valued Bochner integrals, and operations on pairs (p,r)(p,r)(p,r) are componentwise.

Degenerate cases.

  • For L=0L=0L=0: c0=1c_0=1c0​=1, Δ0=1\Delta_0=1Δ0​=1. The claim reads: the means of probability measures giving Cs,0C_{s,0}Cs,0​ full mass are exactly the points of Cs,0C_{s,0}Cs,0​.
  • When some ci=0c_i=0ci​=0, the constraint μ(Cs,i)≥0\mu(C_{s,i})\ge0μ(Cs,i​)≥0 is vacuous and Δi\Delta_iΔi​ may be 000. A zero-weight layer contributes 000 to the sum, while yiy_iyi​ must still be chosen from the nonempty Cs,iC_{s,i}Cs,i​.
  • The Bochner integral is 000 for a non-integrable measure, and the left-hand set is formed under that convention.
  • The setup GGG enters only through the validity requirement built into UUU.
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