Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2 — under (a)–(f) the myopic maximizer bounds every optimal action from below, finite and infinite horizon

Proved
LovejoyPOMDP.Monotone.proposition_2

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

dynamic-programminglikelihood-ratio-ordermonotone-policyp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pomdp

Consider a finite POMDP as in §2 of the paper, with a completely ordered action set AAA. For a belief π∈Π(S)\pi\in\Pi(S)π∈Π(S) let

α(π)=argmax⁡{∑i∈Sπig(i,a):a∈A}\alpha(\pi)=\operatorname{argmax}\Big\{\sum_{i\in S}\pi_i g(i,a) : a\in A\Big\}α(π)=argmax{i∈S∑​πi​g(i,a):a∈A}

be the set of myopic actions. Assume

  1. (a) gsg_sgs​ is nondecreasing on SSS;
  2. (b) g(⋅,a)g(\cdot,a)g(⋅,a) is nondecreasing on SSS for all a∈Aa\in Aa∈A;
  3. (c) Pa≥tpPa′P^a\ge_{tp}P^{a'}Pa≥tp​Pa′ for all a≥a′a\ge a'a≥a′ in AAA;
  4. (d) ra(j)≥rra(j′)r^a(j)\ge_r r^a(j')ra(j)≥r​ra(j′) for j≥j′j\ge j'j≥j′ in SSS, all a∈Aa\in Aa∈A;
  5. (e) ra(j)≥sra′(j)r^a(j)\ge_s r^{a'}(j)ra(j)≥s​ra′(j) for a≥a′a\ge a'a≥a′ in AAA, all j∈Sj\in Sj∈S;
  6. (f) rjkarj′ka′≥rjka′rj′kar^a_{jk}r^{a'}_{j'k}\ge r^{a'}_{jk}r^a_{j'k}rjka​rj′ka′​≥rjka′​rj′ka​ for a≥a′a\ge a'a≥a′ in AAA, j≥j′j\ge j'j≥j′ in SSS, all k∈Ok\in Ok∈O.

Then:

  1. Finite horizon N<∞N<\inftyN<∞. For all t=1,…,Nt=1,\dots,Nt=1,…,N and all π∈Π(S)\pi\in\Pi(S)π∈Π(S), let δt∗(π)\delta^*_t(\pi)δt∗​(π) range over the maximizers of a↦h(π,a,Vt+1∗)a\mapsto h(\pi,a,V^*_{t+1})a↦h(π,a,Vt+1∗​). For every δt∗(π)\delta^*_t(\pi)δt∗​(π) there is an α(π)≤δt∗(π)\alpha(\pi)\le\delta^*_t(\pi)α(π)≤δt∗​(π), and for every α(π)\alpha(\pi)α(π) there is a δt∗(π)≥α(π)\delta^*_t(\pi)\ge\alpha(\pi)δt∗​(π)≥α(π).
  2. Infinite horizon, 0<β<10<\beta<10<β<1. For all π∈Π(S)\pi\in\Pi(S)π∈Π(S), let δ∗(π)\delta^*(\pi)δ∗(π) range over the maximizers of a↦h(π,a,V∗)a\mapsto h(\pi,a,V^*)a↦h(π,a,V∗), where V∗V^*V∗ is the infinite-horizon optimal value. For every δ∗(π)\delta^*(\pi)δ∗(π) there is an α(π)≤δ∗(π)\alpha(\pi)\le\delta^*(\pi)α(π)≤δ∗(π), and for every α(π)\alpha(\pi)α(π) there is a δ∗(π)≥α(π)\delta^*(\pi)\ge\alpha(\pi)δ∗(π)≥α(π).

The easily computed myopic policy is thus a lower bound on an optimal policy of the partially observed problem, in both directions of the quantifiers. The ordering of the action set is what makes the bound meaningful.

Formalization Note Vt+1∗V^*_{t+1}Vt+1∗​ is M.Vstar gs N (t + 1) from the recursion (3) with salvage gsg_sgs​. The infinite-horizon V∗V^*V∗ is any V with M.IsBellmanSolution V, which for 0<β<10<\beta<10<β<1 exists and is unique on Π(S)\Pi(S)Π(S). The maximizer sets are argmaxSet. Hypothesis (a) concerns only the salvage value, so it is attached to part 1 (as ∀ gs, Monotone gs → …); part 2 does not involve gsg_sgs​. Hypothesis (c) at a=a′a=a'a=a′ makes every PaP^aPa TP2\mathrm{TP}_2TP2​, which is how Proposition 1 enters.

Preamble
import Mathlib
import Definitions.Def_LovejoyPOMDP_Monotone_Model
Formal statement
namespace LovejoyPOMDP.Monotone

/-- Lovejoy, *Some Monotonicity Results for Partially Observed Markov Decision Processes*, Oper. Res. 35(5):736–743 (1987), DOI 10.1287/opre.35.5.736, p. 741, Proposition 2 (with `α(π)` defined just above it).

Assume (b) `g(·, a)` is nondecreasing on `S` for all `a ∈ A`, (c) `P^a ≥tp P^{a'}` for all
`a ≥ a'` in `A`, (d) `r^a(j) ≥r r^a(j')` for `j ≥ j'` in `S`, all `a ∈ A`, (e) `r^a(j) ≥s r^{a'}(j)`
for `a ≥ a'` in `A`, all `j ∈ S`, and (f) `r^a_{jk} r^{a'}_{j'k} ≥ r^{a'}_{jk} r^a_{j'k}` for
`a ≥ a'` in `A`, `j ≥ j'` in `S`, all `k ∈ O`. Let `α(π)` range over the maximizers of
`a ↦ Σ_i π_i g(i, a)`.

1. `N < ∞`: for every salvage `g_s` satisfying (a) (`g_s` nondecreasing on `S`), all
   `t = 1, …, N` and all `π ∈ Π(S)`: for every maximizer `δ*_t(π)` of `a ↦ h(π, a, V*_{t+1})` there
   is an `α(π) ≤ δ*_t(π)`, and for every `α(π)` there is a `δ*_t(π) ≥ α(π)`.
2. `N = ∞`, `0 < β < 1`: for every bounded solution `V*` of the Bellman equation on `Π(S)` and all
   `π ∈ Π(S)`: for every maximizer `δ*(π)` of `a ↦ h(π, a, V*)` there is an `α(π) ≤ δ*(π)`, and for
   every `α(π)` there is a `δ*(π) ≥ α(π)`.

**Formalization Note.** `V*_{t+1}` is `M.Vstar gs N (t + 1)`, computed by the recursion (3); the
infinite-horizon `V*` is any `V` with `M.IsBellmanSolution V`, which for `0 < β < 1` exists and is
unique on `Π(S)`. Hypothesis (a) concerns only the salvage value, so it is attached to part 1. -/
theorem proposition_2 {S O A : Type*} [Fintype S] [Fintype O] [Fintype A]
    [LinearOrder S] [LinearOrder O] [LinearOrder A] [Nonempty S] [Nonempty O] [Nonempty A]
    (M : POMDP S O A)
    (hg : ∀ a, Monotone (fun i => M.g i a))
    (hP : ∀ a a' : A, a' ≤ a → TPGE (M.P a) (M.P a'))
    (hRd : ∀ a (j j' : S), j' ≤ j → MLRGE (M.R a j) (M.R a j'))
    (hRe : ∀ a a' : A, a' ≤ a → ∀ j, StochGE (M.R a j) (M.R a' j))
    (hRf : ∀ a a' : A, a' ≤ a → ∀ j j' : S, j' ≤ j → ∀ k,
      M.R a' j k * M.R a j' k ≤ M.R a j k * M.R a' j' k) :
    (∀ gs : S → ℝ, Monotone gs → ∀ N t : ℕ, 1 ≤ t → t ≤ N → ∀ π ∈ stdSimplex ℝ S,
      (∀ d ∈ argmaxSet (fun a => M.hOp π a (M.Vstar gs N (t + 1))),
          ∃ α ∈ argmaxSet (M.myopic π), α ≤ d) ∧
        (∀ α ∈ argmaxSet (M.myopic π),
          ∃ d ∈ argmaxSet (fun a => M.hOp π a (M.Vstar gs N (t + 1))), α ≤ d)) ∧
    (0 < M.β → M.β < 1 → ∀ V : (S → ℝ) → ℝ, M.IsBellmanSolution V → ∀ π ∈ stdSimplex ℝ S,
      (∀ d ∈ argmaxSet (fun a => M.hOp π a V), ∃ α ∈ argmaxSet (M.myopic π), α ≤ d) ∧
        (∀ α ∈ argmaxSet (M.myopic π), ∃ d ∈ argmaxSet (fun a => M.hOp π a V), α ≤ d)) := by sorry

end LovejoyPOMDP.Monotone
Source
Lovejoy, Some Monotonicity Results for Partially Observed Markov Decision Processes, Oper. Res. 35(5):736–743 (1987), DOI 10.1287/opre.35.5.736, p. 741, Proposition 2 (with the definition of α(π) above it)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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