Proposition 2 — under (a)–(f) the myopic maximizer bounds every optimal action from below, finite and infinite horizon
ProvedLovejoyPOMDP.Monotone.proposition_2Consider a finite POMDP as in §2 of the paper, with a completely ordered action set . For a belief let
be the set of myopic actions. Assume
- (a) is nondecreasing on ;
- (b) is nondecreasing on for all ;
- (c) for all in ;
- (d) for in , all ;
- (e) for in , all ;
- (f) for in , in , all .
Then:
- Finite horizon . For all and all , let range over the maximizers of . For every there is an , and for every there is a .
- Infinite horizon, . For all , let range over the maximizers of , where is the infinite-horizon optimal value. For every there is an , and for every there is a .
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 is M.Vstar gs N (t + 1) from the recursion (3) with salvage . The infinite-horizon is any V with M.IsBellmanSolution V, which for exists and is unique on . 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 . Hypothesis (c) at makes every , which is how Proposition 1 enters.
import Mathlib import Definitions.Def_LovejoyPOMDP_Monotone_Model
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.