Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.1 — the greedy policy of the R² optimal value is the unique optimal R² policy

Proved
TwiceRegMDP.R2Bellman.theorem_5_1

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

bellman-operatormarkov-decision-processoptimal-policyp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1regularizationrobust-mdp

Consider a finite discounted MDP with nonempty state and action sets, nominal kernel P0P_0P0​, nominal reward r0r_0r0​, discount γ∈(0,1)\gamma\in(0,1)γ∈(0,1), nonnegative radii αsr,αsP\alpha^r_s,\alpha^P_sαsr​,αsP​, and suppose Assumption 5.1 holds with witnesses ϵs>0\epsilon_s>0ϵs​>0. Then:

  1. the R² optimality operator T∗,R2T^{*,\mathrm R^2}T∗,R2 has a unique fixed point v∗,R2v^{*,\mathrm R^2}v∗,R2, the R² optimal value function;
  2. for every policy π\piπ, the R² evaluation operator Tπ,R2T^{\pi,\mathrm R^2}Tπ,R2 has a unique fixed point vπ,R2v^{\pi,\mathrm R^2}vπ,R2, the R² value function of π\piπ;
  3. a greedy policy π∗,R2\pi^{*,\mathrm R^2}π∗,R2 for v∗,R2v^{*,\mathrm R^2}v∗,R2 (one with Tπ∗,R2v∗,R2=T∗,R2v∗,R2T^{\pi^{*},\mathrm R^2}v^{*,\mathrm R^2}=T^{*,\mathrm R^2}v^{*,\mathrm R^2}Tπ∗,R2v∗,R2=T∗,R2v∗,R2) exists; every such policy satisfies, for all π∈ΔAS\pi\in\Delta^{\mathcal S}_{\mathcal A}π∈ΔAS​,
vπ∗,R2,R2=v∗,R2 ≥ vπ,R2;v^{\pi^{*,\mathrm R^2},\mathrm R^2}=v^{*,\mathrm R^2}\ \ge\ v^{\pi,\mathrm R^2};vπ∗,R2,R2=v∗,R2 ≥ vπ,R2;

and every policy whose R² value equals v∗,R2v^{*,\mathrm R^2}v∗,R2 (that is, every optimal R² policy) is greedy for v∗,R2v^{*,\mathrm R^2}v∗,R2; 4. if moreover αsr>0\alpha^r_s>0αsr​>0 for every state sss, the greedy policy for v∗,R2v^{*,\mathrm R^2}v∗,R2 is unique, hence it is the unique optimal R² policy.

This is the R² analogue of the fundamental theorem of discounted dynamic programming: acting greedily with respect to the R² optimal value yields an optimal policy, which is what justifies the R² modified policy iteration algorithm.

Formalization Note. Assumption 5.1 is not in the theorem's sentence on p. 8, but its proof (p. 24) assumes it, and without it the fixed points need not exist. Uniqueness (clause 4) needs a positive weight in the regularizer: with ∣S∣=1|\mathcal S|=1∣S∣=1, two actions, r0≡0r_0\equiv0r0​≡0 and αr=αP=0\alpha^r=\alpha^P=0αr=αP=0 every policy is greedy and optimal; αsr>0\alpha^r_s>0αsr​>0 is assumed for clause 4 only. The existence and uniqueness of the fixed points (clauses 1–2) are stated so that the value functions of Definition 5.2 are well defined. Norms inside the operators are ℓ2\ell_2ℓ2​-norms; the inequality ≥\ge≥ is pointwise.


Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.

Preamble
import Mathlib
import Definitions.Def_FoundationsML_ReinforcementLearning_IsTransitionKernel
import Definitions.Def_TwiceRegMDP_R2Bellman_MDP
import Definitions.Def_TwiceRegMDP_R2Bellman_R2Ops
Formal statement
namespace TwiceRegMDP.R2Bellman

/-- Theorem 5.1, R² optimal policy (Derman–Geist–Mannor, arXiv:2110.06267v1, p. 8; proof App. C.2,
p. 24). Under Assumption 5.1 (with witnesses `ϵ`; the proof assumes it):
1. `T^{∗,R²}` has a unique fixed point `v^{∗,R²}` (Definition 5.2 (ii) is well posed);
2. for every policy `π`, `T^{π,R²}` has a unique fixed point `v^{π,R²}` (Definition 5.2 (i));
3. a greedy policy for `v^{∗,R²}` exists; every greedy policy `π^∗` has `v^{π^∗,R²} = v^{∗,R²}`;
   every policy has `v^{π,R²} ≤ v^{∗,R²}`; and every policy whose R² value equals `v^{∗,R²}`
   (i.e. every optimal policy) is greedy for `v^{∗,R²}`;
4. if moreover `α^r_s > 0` for every `s`, the greedy policy for `v^{∗,R²}` is unique, so it is the
   unique optimal R² policy. -/
theorem theorem_5_1 {S A : Type} [Fintype S] [DecidableEq S] [Nonempty S] [Fintype A] [DecidableEq A]
    [Nonempty A]
    (γ : ℝ) (hγ0 : 0 < γ) (hγ1 : γ < 1)
    (P₀ : S → A → S → ℝ) (hP₀ : FoundationsML.ReinforcementLearning.IsTransitionKernel P₀)
    (r₀ : S → A → ℝ)
    (αr αP : S → ℝ) (hαr : ∀ s, 0 ≤ αr s) (hαP : ∀ s, 0 ≤ αP s)
    (ϵ : S → ℝ) (hasm : BoundedRadius γ P₀ αP ϵ) :
    ∃ vstar : S → ℝ,
      optOpR2 γ P₀ r₀ αr αP vstar = vstar ∧
      (∀ v : S → ℝ, optOpR2 γ P₀ r₀ αr αP v = v → v = vstar) ∧
      (∀ π : S → A → ℝ, TwiceRegMDP.RobustReg.IsPolicy π → ∃! v : S → ℝ, evalOpR2 γ P₀ r₀ αr αP π v = v) ∧
      (∃ π : S → A → ℝ, IsGreedy γ P₀ r₀ αr αP vstar π) ∧
      (∀ πstar : S → A → ℝ, IsGreedy γ P₀ r₀ αr αP vstar πstar →
        ∀ v : S → ℝ, evalOpR2 γ P₀ r₀ αr αP πstar v = v → v = vstar) ∧
      (∀ π : S → A → ℝ, TwiceRegMDP.RobustReg.IsPolicy π →
        ∀ v : S → ℝ, evalOpR2 γ P₀ r₀ αr αP π v = v → v ≤ vstar) ∧
      (∀ π : S → A → ℝ, TwiceRegMDP.RobustReg.IsPolicy π →
        (∀ v : S → ℝ, evalOpR2 γ P₀ r₀ αr αP π v = v → v = vstar) →
        IsGreedy γ P₀ r₀ αr αP vstar π) ∧
      ((∀ s, 0 < αr s) →
        ∀ π₁ π₂ : S → A → ℝ, IsGreedy γ P₀ r₀ αr αP vstar π₁ →
          IsGreedy γ P₀ r₀ αr αP vstar π₂ → π₁ = π₂) := by sorry

end TwiceRegMDP.R2Bellman
Source
Derman, Geist and Mannor, Twice regularized MDPs and the equivalence between robustness and regularization, arXiv:2110.06267v1, p. 8, Theorem 5.1 and Definition 5.2; proof in App. C.2, p. 24
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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