Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.1 — Averaged reward-to-go recursion

Proved
XuDRMDP.Finite.lemma_3_1

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.

Fix any policy π\piπ, admissible marginal family (μs)(\mu_s)(μs​), its global product law μ\muμ, and any admissible history hth_tht​ with t<Tt<Tt<T. Write (pˉ,rˉ)=Eμ(p,r)(\bar p,\bar r)=E_\mu(p,r)(pˉ​,rˉ)=Eμ​(p,r) and

Bh(xs)=∑a∈Asπh(a)[rxs(a)+γ∑j∈St+1pxs(j∣a)w(π,μ,(h,a,j))],s=s(h).B_h(x_s)=\sum_{a\in A_s}\pi_h(a)\left[r_{x_s}(a)+\gamma\sum_{j\in S_{t+1}}p_{x_s}(j\mid a)w(\pi,\mu,(h,a,j))\right],\qquad s=s(h).Bh​(xs​)=a∈As​∑​πh​(a)​rxs​​(a)+γj∈St+1​∑​pxs​​(j∣a)w(π,μ,(h,a,j))​,s=s(h).

Then both equalities hold:

w(π,μ,h)=∫Bh(xs) dμs(xs)=Bh(pˉs,rˉs).w(\pi,\mu,h)=\int B_h(x_s)\,d\mu_s(x_s)=B_h(\bar p_s,\bar r_s).w(π,μ,h)=∫Bh​(xs​)dμs​(xs​)=Bh​(pˉ​s​,rˉs​).

The history need not have positive probability under the chosen policy or any parameter realization.

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: Lemma 3.1 prints “we-” followed by “0 have” → the two displayed equalities with no extra condition; reason: this broken wording is visibly typography, not a mathematical hypothesis
  • encoding: sum over all next states S in equation (2) → sum restricted by an indicator to the next stage; reason: staged transition probabilities vanish at all other states, including for mean parameters; their impossible continuations contribute zero
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_1 {n : ℕ} [NeZero n] {a : Fin n → ℕ} [∀ s, NeZero (a s)]
    (G : Setup n a) (U : Uncertainty G) (π : Policy a)
    (μ : Marginals n a) (hμ : admissibleMarginals U μ)
    (h : History a) (hh : Admissible G h) (ht : G.stage h.state + 1 < G.horizon) :
    expectedFrom G π (productLaw μ) h =
      ∫ x, averagedStep G π (productLaw μ) h x ∂(μ h.state) ∧
    (∫ x, averagedStep G π (productLaw μ) h x ∂(μ h.state)) =
      averagedStep G π (productLaw μ) h (globalMean (productLaw μ) h.state) := 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.1, printed p. 291 (PDF p. 4).
Read-back

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

Data.

  • n≥1n\ge1n≥1 states [n]={0,…,n−1}[n]=\{0,\dots,n-1\}[n]={0,…,n−1} 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 σ:[n]→N\sigma:[n]\to\mathbb Nσ:[n]→N with σ<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 for each state nested nonempty convex compact sets Cs,0⊆⋯⊆Cs,LC_{s,0}\subseteq\dots\subseteq C_{s,L}Cs,0​⊆⋯⊆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​. Their points are valid local MDP coordinates: they equal some imported-type MDP's data at sss, have 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π: a probability vector π(h)\pi(h)π(h) on Astate(h)A_{\mathrm{state}(h)}Astate(h)​ for every history hhh, possibly depending on the whole past.
  • A marginal family (μs)s∈[n](\mu_s)_{s\in[n]}(μs​)s∈[n]​ that is admissible: each μs\mu_sμs​ is a probability measure on Xs\mathcal X_sXs​ with μ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.
  • A history hhh that is admissible, i.e. of the form ([(s0,b0),…,(sk−1,bk−1)],sk)([(s_0,b_0),\dots,(s_{k-1},b_{k-1})],s_k)([(s0​,b0​),…,(sk−1​,bk−1​)],sk​) with σ(si)=i\sigma(s_i)=iσ(si​)=i, whose current state s:=state(h)s:=\mathrm{state}(h)s:=state(h) satisfies σ(s)+1<T\sigma(s)+1<Tσ(s)+1<T.

Let ν=⨂s′μs′\nu=\bigotimes_{s'}\mu_{s'}ν=⨂s′​μs′​ be the product law on X=∏s′Xs′\mathcal X=\prod_{s'}\mathcal X_{s'}X=∏s′​Xs′​. Write points as x=(xs′)x=(x_{s'})x=(xs′​) with xs′=(ps′x,rs′x)x_{s'}=(p^x_{s'},r^x_{s'})xs′​=(ps′x​,rs′x​).

Return. For a history ggg with current state s′s's′ and K=T−1−σ(s′)K=T-1-\sigma(s')K=T−1−σ(s′), u(π,x,g)u(\pi,x,g)u(π,x,g) is the finite sum, over sequences (s0′′,b0),…,(sK−1′′,bK−1)(s''_0,b_0),\dots,(s''_{K-1},b_{K-1})(s0′′​,b0​),…,(sK−1′′​,bK−1​) and final states jjj, of

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

where:

  • sK′′:=js''_K:=jsK′′​:=j;
  • GtG_tGt​ is the history whose past is past(g)\mathrm{past}(g)past(g) followed by (s0′′,b0),…,(st−1′′,bt−1)(s''_0,b_0),\dots,(s''_{t-1},b_{t-1})(s0′′​,b0​),…,(st−1′′​,bt−1​), and whose current state is st′′s''_tst′′​.

Let E(g)=∫u(π,x,g) dν(x)E(g)=\int u(\pi,x,g)\,d\nu(x)E(g)=∫u(π,x,g)dν(x).

Averaged step. For a local point y=(p,r)∈Xsy=(p,r)\in\mathcal X_sy=(p,r)∈Xs​:

Φ(y)=∑b∈Asπ(h)(b)(r(b)+γ∑j: σ(j)=σ(s)+1p(b,j) E(h ⁣⋅ ⁣(b,j))),\Phi(y)=\sum_{b\in A_s}\pi(h)(b)\Big(r(b)+\gamma\sum_{j:\ \sigma(j)=\sigma(s)+1}p(b,j)\,E\big(h\!\cdot\!(b,j)\big)\Big),Φ(y)=b∈As​∑​π(h)(b)(r(b)+γj: σ(j)=σ(s)+1∑​p(b,j)E(h⋅(b,j))),

where h ⁣⋅ ⁣(b,j)h\!\cdot\!(b,j)h⋅(b,j) appends (s,b)(s,b)(s,b) to past(h)\mathrm{past}(h)past(h) and sets the current state to jjj. The continuation values EEE use the full product law ν\nuν, including its sss-coordinate.

Claim. Both of the following equalities hold:

∫u(π,x,h) dν(x)=∫XsΦ(y) dμs(y)\int u(\pi,x,h)\,d\nu(x)=\int_{\mathcal X_s}\Phi(y)\,d\mu_s(y)∫u(π,x,h)dν(x)=∫Xs​​Φ(y)dμs​(y)

and

∫XsΦ(y) dμs(y)=Φ(xˉs),xˉs=∫xs dν(x)∈Xs,\int_{\mathcal X_s}\Phi(y)\,d\mu_s(y)=\Phi(\bar x_s),\qquad \bar x_s=\int x_s\,d\nu(x)\in\mathcal X_s,∫Xs​​Φ(y)dμs​(y)=Φ(xˉs​),xˉs​=∫xs​dν(x)∈Xs​,

where xˉs\bar x_sxˉs​ is the sss-coordinate mean under the product law, a vector-valued Bochner integral.

Degenerate cases.

  • The hypothesis σ(s)+1<T\sigma(s)+1<Tσ(s)+1<T forces T≥2T\ge2T≥2. In particular the statement says nothing about histories at the last stage, nor about any history when T=1T=1T=1.
  • The structure UUU enters only through the admissibility of (μs)(\mu_s)(μs​).
  • All integrals are Bochner integrals, which by convention equal 000 (or the zero vector) when the integrand is not integrable. The equalities are asserted with that convention in force.
  • If no state has stage σ(s)+1\sigma(s)+1σ(s)+1, the inner sum in Φ\PhiΦ is empty and Φ(y)=∑bπ(h)(b)r(b)\Phi(y)=\sum_b\pi(h)(b)r(b)Φ(y)=∑b​π(h)(b)r(b).
  • If as=1a_s=1as​=1, π(h)\pi(h)π(h) is the point mass on the single action.
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