Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — v~t(s,τ,a)=OPT(s,τ,a,vt+1)\tilde v_t(s,\tau,a)=\mathrm{OPT}(s,\tau,a,v_{t+1})v~t​(s,τ,a)=OPT(s,τ,a,vt+1​) (corrected: strict quantile budget in OPT)

Proved
QuantileMDP.theorem_1

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

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

Let MMM be a model with finite state set S={s1,…,sn}\mathcal S=\{s_1,\dots,s_n\}S={s1​,…,sn​} and finite action set, TTT a horizon, t<Tt<Tt<T, sss a state, a∈At(s)a\in\mathcal A_t(s)a∈At​(s) an admissible action and τ∈[0,1]\tau\in[0,1]τ∈[0,1]. Let vt+1v_{t+1}vt+1​ be the optimal value function (5) at time t+1t+1t+1 and v~t\tilde v_tv~t​ the intermediate value function. Then

v~t(s,τ,a)=OPT(s,τ,a,vt+1(⋅,⋅))=sup⁡q min⁡i∈{i : qi≠1}[vt+1(si,qi)+rt(s,a,lt(s,a,si))],\tilde v_t(s,\tau,a)=\mathrm{OPT}\bigl(s,\tau,a,v_{t+1}(\cdot,\cdot)\bigr) =\sup_q\ \min_{i\in\{i\,:\,q_i\neq1\}}\bigl[v_{t+1}(s_i,q_i)+r_t(s,a,l_t(s,a,s_i))\bigr],v~t​(s,τ,a)=OPT(s,τ,a,vt+1​(⋅,⋅))=qsup​ i∈{i:qi​=1}min​[vt+1​(si​,qi​)+rt​(s,a,lt​(s,a,si​))],

the supremum being over q∈[0,1]nq\in[0,1]^nq∈[0,1]n with ∑i=1npiqi<τ\sum_{i=1}^np_iq_i<\tau∑i=1n​pi​qi​<τ or ∑i=1npiqi=0\sum_{i=1}^np_iq_i=0∑i=1n​pi​qi​=0, where pi=P(St+1=si∣St=s,at=a)p_i=P(S_{t+1}=s_i\mid S_t=s,a_t=a)pi​=P(St+1​=si​∣St​=s,at​=a). The supremum is attained by some such qqq, and the maximum defining v~t(s,τ,a)\tilde v_t(s,\tau,a)v~t​(s,τ,a) is attained by an admissible policy with μt(s)=a\mu_t(s)=aμt​(s)=a.

Together with (6) this is the dynamic-programming step of the quantile MDP: the time-ttt value function is computed from the time-(t+1)(t+1)(t+1) value function as a function of both the state and the quantile level.

Differences from the source:

  • correction: budget ∑ipiqi≤τ\sum_ip_iq_i\le\tau∑i​pi​qi​≤τ → ∑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, t=0t=0t=0, 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, τ=1/2\tau=1/2τ=1/2: q=(1,0)q=(1,0)q=(1,0) gives 101010, while the only policy's reward is 000 or 101010 with probability 1/21/21/2 each and v~0(s1,1/2,a)=0\tilde v_0(s_1,1/2,a)=0v~0​(s1​,1/2,a)=0.
  • reading: "maxa_aa​" and the admissible actions → hypothesis a∈At(s)a\in\mathcal A_t(s)a∈At​(s); reason: for a non-admissible aaa no policy has μt(s)=a\mu_t(s)=aμt​(s)=a, and the paper's maximum ranges over admissible actions (p.8).
  • 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: 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, and every kernel model is one.
  • 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.
  • encoding: S={s1,…,sn}\mathcal S=\{s_1,\dots,s_n\}S={s1​,…,sn​} and real values → the finite type S\mathcal SS as index set, values in the extended reals; reason: same instances.
  • encoding: the process from time ttt → the model shifted by ttt, started at its time 000, with a fresh policy; reason: the paper's histories Hk′H'_kHk′​ begin with StS_tSt​ (p.10).
  • 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 qqq in OPT and over policies in v~t\tilde v_tv~t​ → suprema in the extended reals together with clauses saying each is attained; reason: that is what the maxima assert.
Preamble
import Mathlib
import Definitions.Def_QuantileMDP_quantile
import Definitions.Def_QuantileMDP_opt
import Definitions.Def_QuantileMDP_Model
import Definitions.Def_QuantileMDP_optValue
Formal statement
namespace QuantileMDP

/-- Theorem 1 (Value Function Dynamic Programming), corrected budget: for `t < T` and an
admissible action `a`, `ṽ_t(s, τ, a) = OPT(s, τ, a, v_{t+1}(·,·))`, where
`OPT = max_q min_{i : q_i ≠ 1} [v_{t+1}(s_i, q_i) + r_t(s, a, l_t(s, a, s_i))]` with
`p_i = P(S_{t+1} = s_i | S_t = s, a_t = a)` and `v_{t+1}` the optimal value function (5). Both
maxima are attained: the one over `q` in `OPT` and the one over policies in `ṽ_t`.
Li, Zhong, Brandeau, *Quantile Markov Decision Processes*, arXiv:1711.05788v5, §3.2, Theorem 1 (8),
p.11.

**Formalization Note** `OPT` is `opt` with the corrected budget `∑ p_i q_i < τ ∨ ∑ p_i q_i = 0`
(the printed `≤ τ` fails at `τ = 1/2` for one step to two equally likely states with rewards
`0` and `10`). The state space is indexed by the type `S` itself. The maximum over actions in the
paper ranges over admissible actions, so `a ∈ adm t s` is assumed. -/
theorem theorem_1 {S A : Type*} [Fintype S] [Fintype A] (M : Model S A) (T t : ℕ) (ht : t < T)
    (s : S) (a : A) (ha : a ∈ M.adm t s) (τ : ℝ) (hτ : τ ∈ Set.Icc (0 : ℝ) 1) :
    optValueAct M T t s τ a =
        opt (fun s' => (M.P t s a s').toReal)
          (fun s' q => optValue M T (t + 1) s' q + ((M.r t s a s' : ℝ) : EReal)) τ ∧
      OptAttained (fun s' => (M.P t s a s').toReal)
        (fun s' q => optValue M T (t + 1) s' q + ((M.r t s a s' : ℝ) : EReal)) τ ∧
      ∃ π : Policy S A, (M.shift t).Admissible π ∧ π 0 (fun _ => s) = a ∧
        quantile (rewardLaw (M.shift t) (T - t) π s) τ = optValueAct M T t s τ a := by sorry

end QuantileMDP
Source
Li, Zhong, Brandeau, Quantile Markov Decision Processes, arXiv:1711.05788v5, §3.2, Theorem 1 (8), p.11
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