Lemma 3.9.4 - the optimal-value function is increasing in the state (corrected: the transition law is carried by the next period's state space)
ProvedSupermodularity.MDP.value_increasing_of_stochastically_increasing_v2Consider a nonstationary, discounted, finite-horizon, discrete-time Markov decision process with periods . In period the state ranges over ; given state , the decision is restricted to a finite nonempty set . Let . The expected net return of decision in state in period is , and is the distribution of next period's state given : a probability measure on that is carried by , i.e. for . With discount rate and , define from period backward
Suppose whenever in , is increasing in on the section for every and , and is stochastically increasing in on that same section for every and .
Then is increasing in on for every period .
This is Topkis's Lemma 3.9.4, proved by backward induction on the period: if is increasing on , then is increasing by stochastic monotonicity of the transition law, hence is increasing by the growing constraint sets. It is the base that Theorem 3.9.2 builds on.
Formalization Note. The retired version let the next-state law be an arbitrary probability measure on while was determined by the recursion only on ; a transition law putting mass outside then fed arbitrary (decreasing) values of into the Bellman integral, and the lemma was disproved. In the book is the distribution of the period- state, which lives in ; the new hypothesis hμsupp ( gives mass to the complement of for every , ) makes this standing assumption of the model explicit. With it the integral depends only on , so the recursion determines on and on uniquely and the statement, which quantifies over all satisfying the recursion, is the book's lemma. As in the retired version, the maximum defining is expressed as IsGreatest (attained since is finite and nonempty), the existence of the integrals is an explicit hypothesis (the book's returns are bounded), and the stochastic-monotonicity hypothesis uses the mission's StochasticallyIncreasingOn (monotone probability of every upward-closed set).
import Mathlib import Definitions.Def_Supermodularity_MDP_StochasticallyIncreasingOn open MeasureTheory
namespace Supermodularity.MDP
/-- Lemma 3.9.4 (Topkis, *Supermodularity and Complementarity*, p. 161–162), corrected.
A finite-horizon, nonstationary, discounted, discrete-time Markov decision process with
periods `i = 1, …, k`: state `t ∈ T i ⊆ ℝᵐ`, decision `x` restricted to the finite nonempty
set `X i t ⊆ ℝⁿ`, `S i = {(x,t) : t ∈ T i, x ∈ X i t}`, return `r i x t`, discount
`γ = 1/(1+β)`, and next-state distribution `μ i x t`, **a distribution of the period-`i+1`
state, i.e. carried by `T (i+1)`** (`hμsupp`). Starting from `g k x t = r k x t`, `f` and `g`
satisfy the backward recursion `f i t = max {g i x t : x ∈ X i t}` (3.9.1) and, for `i < k`,
`g i x t = r i x t + γ ∫ f (i+1) w dμ (i x t) w` (3.9.2). If `X i t' ⊆ X i t''` whenever
`t' ≤ t''` in `T i`, `r i x t` is increasing in `t` on the section of `S i` at `x` for all `x`
and `i`, and `F(x,t,i,·)` is stochastically increasing in `t` on that section for all `x` and
`i`, then `f i t` is increasing in `t` on `T i` for each `i`.
Correction to the retired version: it let `μ i x t` be any probability measure on `ℝᵐ`, so the
Bellman integral could read values of `f (i+1)` off `T (i+1)`, where the recursion does not
determine `f (i+1)`; the book's transition law is a distribution of the next state in
`T (i+1)`, which `hμsupp` makes explicit. With it, the recursion pins `g` on `S i` and `f` on
`T i` uniquely, so quantifying over all `f`, `g` satisfying it is the book's statement. -/
theorem value_increasing_of_stochastically_increasing_v2 {n m : ℕ} (k : ℕ)
(T : ℕ → Set (Fin m → ℝ)) (X : ℕ → (Fin m → ℝ) → Finset (Fin n → ℝ))
(S : ℕ → Set ((Fin n → ℝ) × (Fin m → ℝ)))
(hS : ∀ i, S i = {p : (Fin n → ℝ) × (Fin m → ℝ) | p.2 ∈ T i ∧ p.1 ∈ X i p.2})
(r : ℕ → (Fin n → ℝ) → (Fin m → ℝ) → ℝ)
(β : ℝ) (hβ0 : 0 ≤ β) (hβ1 : β ≤ 1)
(μ : ℕ → (Fin n → ℝ) → (Fin m → ℝ) → Measure (Fin m → ℝ))
(hμprob : ∀ i x t, IsProbabilityMeasure (μ i x t))
(hμsupp : ∀ i, 1 ≤ i → i < k → ∀ x t, (x, t) ∈ S i → μ i x t (T (i + 1))ᶜ = 0)
(f : ℕ → (Fin m → ℝ) → ℝ) (g : ℕ → (Fin n → ℝ) → (Fin m → ℝ) → ℝ)
(hgk : ∀ x t, g k x t = r k x t)
(hg : ∀ i, 1 ≤ i → i < k → ∀ x t, (x, t) ∈ S i →
g i x t = r i x t + (1 / (1 + β)) * ∫ w, f (i + 1) w ∂ (μ i x t))
(hfint : ∀ i, 1 ≤ i → i < k → ∀ x t, (x, t) ∈ S i → Integrable (f (i + 1)) (μ i x t))
(hf : ∀ i, 1 ≤ i → i ≤ k → ∀ t ∈ T i,
IsGreatest ((fun x => g i x t) '' (X i t : Set (Fin n → ℝ))) (f i t))
(hXne : ∀ i, 1 ≤ i → i ≤ k → ∀ t ∈ T i, (X i t).Nonempty)
(hXsub : ∀ i, 1 ≤ i → i ≤ k → ∀ ⦃t' t'' : Fin m → ℝ⦄, t' ∈ T i → t'' ∈ T i → t' ≤ t'' →
X i t' ⊆ X i t'')
(hrmono : ∀ i, 1 ≤ i → i ≤ k → ∀ x, MonotoneOn (fun t => r i x t) {t | (x, t) ∈ S i})
(hFmono : ∀ i, 1 ≤ i → i ≤ k → ∀ x,
Supermodularity.MDP.StochasticallyIncreasingOn {t | (x, t) ∈ S i} (μ i x)) :
∀ i, 1 ≤ i → i ≤ k → MonotoneOn (f i) (T i) := by sorry
end Supermodularity.MDP