Lemma 1.2, part 1 (“if” direction) — MLR-ordered observation rows make T(π, a, k) MLR-nondecreasing in k
ProvedLovejoyPOMDP.Monotone.lemma_1_2_1bayesian-updatelikelihood-ratio-orderp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pomdp
Consider a finite POMDP as in §2 of the paper, with , and fix an action . If the rows of the observation matrix are MLR-ordered,
then for every belief the Bayes update is MLR-nondecreasing in the observation:
Higher observations are evidence for higher states. This is the step of the proofs of Propositions 1 and 2 that makes nondecreasing.
Formalization Note The paper states this part as "if and only if". The "only if" direction is false as printed: with , both rows of equal to and , , every posterior is , so the conclusion holds while fails. Only the "if" direction is stated; it is the direction the paper uses.
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. 738, Lemma 1.2, part 1 — the "if" direction.
Fix `a ∈ A`. If `r^a(j) ≥r r^a(j')` for all `j ≥ j'` in `S`, then for every `π ∈ Π(S)`,
`T(π, a, k) ≥r T(π, a, k')` for all `k ≥ k'` in `O`.
**Formalization Note.** The paper states "if and only if". The "only if" direction is false as
printed: with `n = m = 2`, both rows of `P^a` equal to `(1, 0)`, `T(π, a, k) = (1, 0)` for every
`π` and `k`, so the left side holds, while `r^a(1) = (0.1, 0.9)`, `r^a(2) = (0.9, 0.1)` violate
`r^a(2) ≥r r^a(1)`. Only the "if" direction is stated; it is the direction used in the proofs of
Propositions 1 and 2. -/
theorem lemma_1_2_1 {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) (a : A)
(hR : ∀ j j' : S, j' ≤ j → MLRGE (M.R a j) (M.R a j'))
{π : S → ℝ} (hπ : π ∈ stdSimplex ℝ S) {k k' : O} (hkk' : k' ≤ k) :
MLRGE (M.bayes π a k) (M.bayes π a k') := 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. 738, Lemma 1.2, part 1 (the "if" direction)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.