Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — backward DP computes v0(s,τ)=max⁡πQτπ[∑k<Trk]v_0(s,\tau)=\max_\pi Q^\pi_\tau[\sum_{k<T}r_k]v0​(s,τ)=maxπ​Qτπ​[∑k<T​rk​] (corrected: strict quantile budget in OPT)

Proved
QuantileMDP.theorem_2

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamic-programmingmarkov-decision-processp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantilerisk-measures

Let MMM be a finite-horizon Markov decision process with finite state set S\mathcal SS, finite action set A\mathcal AA, non-stationary transition laws Pt(⋅∣s,a)P_t(\cdot\mid s,a)Pt​(⋅∣s,a), rewards rt(s,a,s′)r_t(s,a,s')rt​(s,a,s′) and nonempty admissible action sets. Let T∈NT\in\mathbb NT∈N be a horizon. Put vT(s,τ)=0v_T(s,\tau)=0vT​(s,τ)=0 for all s∈Ss\in\mathcal Ss∈S and τ∈[0,1]\tau\in[0,1]τ∈[0,1], and compute iteratively, for t=T−1,…,0t=T-1,\dots,0t=T−1,…,0,

vt(s,τ)=max⁡a OPT(s,τ,a,vt+1(⋅,⋅)),v_t(s,\tau)=\max_a\ \mathrm{OPT}\bigl(s,\tau,a,v_{t+1}(\cdot,\cdot)\bigr),vt​(s,τ)=amax​ OPT(s,τ,a,vt+1​(⋅,⋅)),

with OPT\mathrm{OPT}OPT the problem (8) with the budget ∑ipiqi<τ\sum_ip_iq_i<\tau∑i​pi​qi​<τ or ∑ipiqi=0\sum_ip_iq_i=0∑i​pi​qi​=0. Then for every start state sss and every τ∈[0,1]\tau\in[0,1]τ∈[0,1],

v0(s,τ)=max⁡π∈ΠQτπ[∑k=0T−1rk(Sk,ak,wk)],v_0(s,\tau)=\max_{\pi\in\Pi}Q^\pi_\tau\Bigl[\sum_{k=0}^{T-1}r_k(S_k,a_k,w_k)\Bigr],v0​(s,τ)=π∈Πmax​Qτπ​[k=0∑T−1​rk​(Sk​,ak​,wk​)],

where Π\PiΠ is the set of all admissible deterministic history-dependent policies and the quantile is that of the cumulative reward from S0=sS_0=sS0​=s; the maximum is attained.

This is the main result of the paper: the quantile-optimal value of a finite-horizon MDP is computed by a backward dynamic program over the pair (state, quantile level), even though the optimal policy itself is in general history dependent.

Differences from the source:

  • correction: budget ∑ipiqi≤τ\sum_ip_iq_i\le\tau∑i​pi​qi​≤τ in OPT → ∑ipiqi<τ\sum_ip_iq_i<\tau∑i​pi​qi​<τ or ∑ipiqi=0\sum_ip_iq_i=0∑i​pi​qi​=0; reason: the printed statement is false — S={s1,s2}\mathcal S=\{s_1,s_2\}S={s1​,s2​}, one action, T=1T=1T=1, P0(s1∣s1,a)=P0(s2∣s1,a)=1/2P_0(s_1\mid s_1,a)=P_0(s_2\mid s_1,a)=1/2P0​(s1​∣s1​,a)=P0​(s2​∣s1​,a)=1/2, r0(s1,a,s1)=0r_0(s_1,a,s_1)=0r0​(s1​,a,s1​)=0, r0(s1,a,s2)=10r_0(s_1,a,s_2)=10r0​(s1​,a,s2​)=10 (Assumption 1 holds with W=SW=\mathcal SW=S, f0(s,a,w)=wf_0(s,a,w)=wf0​(s,a,w)=w, l0(s,a,s′)=s′l_0(s,a,s')=s'l0​(s,a,s′)=s′), τ=1/2\tau=1/2τ=1/2: the printed recursion gives v0(s1,1/2)=10v_0(s_1,1/2)=10v0​(s1​,1/2)=10 via q=(1,0)q=(1,0)q=(1,0), while the only policy's reward is 000 or 101010 with probability 1/21/21/2 each, whose 1/21/21/2-quantile is 000.
  • encoding: ftf_tft​, wtw_twt​, ltl_tlt​ of Assumption 1 → kernels Pt(⋅∣s,a)P_t(\cdot\mid s,a)Pt​(⋅∣s,a) and rewards rt(s,a,s′)=rt(s,a,lt(s,a,s′))r_t(s,a,s')=r_t(s,a,l_t(s,a,s'))rt​(s,a,s′)=rt​(s,a,lt​(s,a,s′)); reason: every model of Assumption 1 induces such a pair with the same joint law of states, actions and rewards, and every kernel model is one (W=SW=\mathcal SW=S, ft(s,a,w)=wf_t(s,a,w)=wft​(s,a,w)=w, lt(s,a,s′)=s′l_t(s,a,s')=s'lt​(s,a,s′)=s′).
  • encoding: policies on Ht=(S0,a0,…,St)H_t=(S_0,a_0,\dots,S_t)Ht​=(S0​,a0​,…,St​) → deterministic functions of the state history; reason: for deterministic policies past actions are functions of past states.
  • generalization: admissible set At\mathcal A_tAt​ → At(s)\mathcal A_t(s)At​(s), depending on the state; reason: the paper's case is At(s)=At\mathcal A_t(s)=\mathcal A_tAt​(s)=At​.
  • encoding: Q0=inf⁡{X}Q_0=\inf\{X\}Q0​=inf{X}, Q1=sup⁡{X}Q_1=\sup\{X\}Q1​=sup{X} → the essential infimum and supremum of footnote 1, valued in the extended reals; reason: footnote 1 gives the precise form.
  • encoding: the law of ∑k<Trk\sum_{k<T}r_k∑k<T​rk​ given S0=sS_0=sS0​=s → a finite sum of Dirac masses over state paths from sss weighted by their probabilities; reason: it is that law.
  • encoding: "max⁡π∈Π\max_{\pi\in\Pi}maxπ∈Π​" → the value is the greatest element of the set of quantiles attained by admissible policies; reason: that is what the maximum asserts.
  • encoding: admissible sets At\mathcal A_tAt​ and the data Pt,rtP_t,r_tPt​,rt​ for t<Tt<Tt<T → nonempty sets and data for every t∈Nt\in\mathbb Nt∈N; reason: an empty At\mathcal A_tAt​ leaves no policy and the maximum undefined, and the data at t≥Tt\ge Tt≥T is never used.
  • encoding: the maxima over aaa and qqq in the recursion → suprema in the extended reals in the definition of the recursion; reason: same values: only the value of each step enters the recursion.
Preamble
import Mathlib
import Definitions.Def_QuantileMDP_quantile
import Definitions.Def_QuantileMDP_Model
import Definitions.Def_QuantileMDP_dpValue
Formal statement
namespace QuantileMDP

/-- Theorem 2 (Optimal Value Function), corrected budget: let `v_T(s, τ) = 0` and compute
`v_t(s, τ) = max_a OPT(s, τ, a, v_{t+1}(·,·))` for `t = T-1, …, 0`. Then `v_0(s, τ)` is the maximum,
over all admissible history-dependent policies `π`, of `Q^π_τ[∑_{k=0}^{T-1} r_k(S_k, a_k, w_k)]`
from `S_0 = s`, for every `τ ∈ [0,1]`.
Li, Zhong, Brandeau, *Quantile Markov Decision Processes*, arXiv:1711.05788v5, §3.3, Theorem 2,
p.12.

**Formalization Note** `OPT` is `opt` with the corrected budget `∑ p_i q_i < τ ∨ ∑ p_i q_i = 0`
(the printed `≤ τ` gives `10` instead of `0` at `τ = 1/2` for one step to two equally likely
states with rewards `0` and `10`). "max" is `IsGreatest`: the value is attained by an admissible
policy and no admissible policy does better. Every horizon `T` (including `0`) and every
`τ ∈ [0,1]`, endpoints included. -/
theorem theorem_2 {S A : Type*} [Fintype S] [Fintype A] (M : Model S A) (T : ℕ) (s : S) (τ : ℝ)
    (hτ : τ ∈ Set.Icc (0 : ℝ) 1) :
    IsGreatest {x : EReal | ∃ π : Policy S A, M.Admissible π ∧
        x = quantile (rewardLaw M T π s) τ} (dpValue M T 0 s τ) := by sorry

end QuantileMDP
Source
Li, Zhong, Brandeau, Quantile Markov Decision Processes, arXiv:1711.05788v5, §3.3, Theorem 2, p.12
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 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