Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.6 — weakly continuous P and total-variation-continuous Q make the COMDP satisfy Assumption (W*)

Proved
FeinbergPOMDP.WStar.theorem_3_6

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

belief-mdpk-inf-compactp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pomdptotal-variationweak-feller

Let X,Y,A\mathbb X, \mathbb Y, \mathbb AX,Y,A be Borel subsets of Polish spaces and consider a POMDP with transition kernel P(dx′∣x,a)P(dx' \mid x, a)P(dx′∣x,a), observation kernel Q(dy∣a,x)Q(dy \mid a, x)Q(dy∣a,x) and one-step cost c:X×A→R∪{+∞}c : \mathbb X \times \mathbb A \to \mathbb R \cup \{+\infty\}c:X×A→R∪{+∞}. Its belief MDP (COMDP) has state space P(X)\mathbb P(\mathbb X)P(X) with the weak topology, action set A\mathbb AA, cost cˉ(z,a)=∫c(x,a) z(dx)\bar c(z, a) = \int c(x, a)\,z(dx)cˉ(z,a)=∫c(x,a)z(dx) (3.8) and transition q(⋅∣z,a)q(\cdot \mid z, a)q(⋅∣z,a), the law of the posterior H(z,a,y)H(z, a, y)H(z,a,y) when y∼R′(⋅∣z,a)y \sim R'(\cdot \mid z, a)y∼R′(⋅∣z,a) (3.5).

Assume:

  1. either Assumption (D) holds (0≤α<10 \le \alpha < 10≤α<1), or Assumption (P) holds (c≥0c \ge 0c≥0 and 0≤α≤10 \le \alpha \le 10≤α≤1);
  2. ccc is Borel, bounded below and K\mathbb KK-inf-compact on X×A\mathbb X \times \mathbb AX×A;
  3. PPP is weakly continuous;
  4. QQQ is continuous in the total variation.

Then the COMDP satisfies Assumption (W*):

  1. cˉ\bar ccˉ is bounded below by every lower bound of ccc, and cˉ\bar ccˉ is K\mathbb KK-inf-compact on P(X)×A\mathbb P(\mathbb X) \times \mathbb AP(X)×A;
  2. q(⋅∣z,a)q(\cdot \mid z, a)q(⋅∣z,a) is weakly continuous in (z,a)∈P(X)×A(z, a) \in \mathbb P(\mathbb X) \times \mathbb A(z,a)∈P(X)×A: for every filter HHH satisfying (3.3), z(n)→zz^{(n)} \to zz(n)→z weakly and a(n)→aa^{(n)} \to aa(n)→a imply
∫g dq(⋅∣z(n),a(n))→∫g dq(⋅∣z,a)for every bounded continuous g:P(X)→R.\int g\,dq(\cdot \mid z^{(n)}, a^{(n)}) \to \int g\,dq(\cdot \mid z, a)\quad\text{for every bounded continuous } g : \mathbb P(\mathbb X) \to \mathbb R .∫gdq(⋅∣z(n),a(n))→∫gdq(⋅∣z,a)for every bounded continuous g:P(X)→R.

Assumption (W*) is the hypothesis under which the general theory of MDPs with weakly continuous transitions (Feinberg et al. 2012) yields optimality equations, convergence of value iterations and stationary optimal policies, so the theorem gives these for the POMDP in terms of its primitive data.

Formalization Note. The cost is written c=ℓ+fc = \ell + fc=ℓ+f with ℓ∈R\ell \in \mathbb Rℓ∈R and fff Borel with values in [0,∞][0, \infty][0,∞]; K\mathbb KK-inf-compactness is the published FeinbergLiang.ACOE.KInfCompact. The state space is nonempty and standard Borel, as in the paper's setup with an initial prior; a filter satisfying (3.3) therefore exists, so the quantified transition clause is substantive. Assumption (a) of Theorem 3.2 is stated with the discount factor α\alphaα: (D) is 0≤α<10 \le \alpha < 10≤α<1, while (P) is c≥0c \ge 0c≥0 and 0≤α≤10 \le \alpha \le 10≤α≤1. The paper's tail "and therefore statements (i)–(vi) of Theorem 3.1 hold" is not stated: it is Theorem 2.1 applied to the COMDP, which the paper cites from Feinberg et al. [14, Theorem 2] and does not prove.

Preamble
import Mathlib
import Definitions.Def_FeinbergLiang_ACOE_MDP
import Definitions.Def_FeinbergPOMDP_WStar_Model

open scoped ENNReal NNReal Topology
open MeasureTheory ProbabilityTheory Filter FeinbergLiang.ACOE
Formal statement
namespace FeinbergPOMDP.WStar

/-- Feinberg, Kasyanov, Zgurovsky, arXiv:1401.2168v2, **Theorem 3.6**, its Assumption (W*)
conclusion (p. 12): if (D) or (P) holds, the POMDP cost `c` is bounded below and
`𝕂`-inf-compact on `𝕏 × 𝔸`, the transition kernel `P(dx′ | x, a)` is weakly continuous and the
observation kernel `Q(dy | a, x)` is continuous in the total variation, then the COMDP
`(ℙ(𝕏), 𝔸, q, c̄)` satisfies Assumption (W*): `c̄` is bounded below by every lower bound of `c` and
`𝕂`-inf-compact on `ℙ(𝕏) × 𝔸`, and `q(· | z, a)` is weakly continuous in `(z, a)`.

Formalization Note. `𝕏, 𝕐, 𝔸` are Borel subsets of Polish spaces (p. 4), encoded as separable metrizable spaces with
their Borel σ-algebras (`PolishSpace` is not assumed). The cost `c : 𝕏 × 𝔸 → ℝ ∪ {+∞}`, bounded below and Borel (p. 4), is written `c(x, a) = lower + f x a`
with `lower : ℝ` and `f : 𝕏 → 𝔸 → [0, ∞]` Borel; every bounded-below `ℝ ∪ {+∞}`-valued Borel
function has this form. Then `c̄(z, a) = lower + beliefCost f z a` (3.8). `𝕂`-inf-compactness is the
published `FeinbergLiang.ACOE.KInfCompact` of `f` (nonempty compact `K`, levels in `ℝ≥0`; equivalent
to the paper's definition on p. 6, since `lower + ·` shifts levels).
`q` is defined from a filter `H` satisfying (3.3); the paper notes (p. 8) that the choice of `H` does
not affect `q`, so the weak continuity is stated for every such `H`. The standard Borel and nonempty
instances on `𝕏` ensure that the paper's filtering kernel exists, so this clause is not vacuous.
Assumption (a) of Theorem 3.2 is stated explicitly: either (D), with `0 ≤ α < 1`, or
(P), with a nonnegative cost and `0 ≤ α ≤ 1`. The bounded-below part of (D) is built into
`lower + f`.
The tail "and therefore statements (i)–(vi) of Theorem 3.1 hold" is not stated: it is Theorem 2.1,
cited from Feinberg et al. [14, Theorem 2] and not proved in the paper. -/
theorem theorem_3_6 {X Y A : Type*}
    [TopologicalSpace X] [TopologicalSpace.MetrizableSpace X] [SecondCountableTopology X]
    [MeasurableSpace X] [BorelSpace X]
    [TopologicalSpace Y] [TopologicalSpace.MetrizableSpace Y] [SecondCountableTopology Y]
    [MeasurableSpace Y] [BorelSpace Y]
    [TopologicalSpace A] [TopologicalSpace.MetrizableSpace A] [SecondCountableTopology A]
    [MeasurableSpace A] [BorelSpace A]
    [StandardBorelSpace X] [Nonempty X]
    (P : Kernel (X × A) X) [IsMarkovKernel P] (Q : Kernel (A × X) Y) [IsMarkovKernel Q]
    (lower α : ℝ) (f : X → A → ℝ≥0∞) (hf : Measurable (Function.uncurry f))
    (hDP : (0 ≤ α ∧ α < 1) ∨
      ((∀ (x : X) (a : A), (0 : EReal) ≤ (lower : EReal) + (f x a : EReal)) ∧
        0 ≤ α ∧ α ≤ 1))
    (hK : KInfCompact f)
    (hP : IsWeaklyContinuous (kernelPM P)) (hQ : IsTVContinuous (kernelPM Q)) :
    (∀ K : ℝ, (∀ (x : X) (a : A), (K : EReal) ≤ (lower : EReal) + (f x a : EReal)) →
        ∀ (z : ProbabilityMeasure X) (a : A),
          (K : EReal) ≤ (lower : EReal) + (beliefCost f z a : EReal)) ∧
    KInfCompact (beliefCost f) ∧
    ∀ H : ProbabilityMeasure X → A → Y → ProbabilityMeasure X,
      IsFilter P Q H → BeliefTransitionWeaklyContinuous P Q H := by sorry

end FeinbergPOMDP.WStar
Source
Feinberg, Kasyanov, Zgurovsky, Partially Observable Total-Cost Markov Decision Processes with Weakly Continuous Transition Probabilities, arXiv:1401.2168v2, Theorem 3.6, p. 12, with assumptions (a), (b) of Theorem 3.2, p. 11
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

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