Lemma 5.6.1 — one-step evaluation preserves bounded values
ProvedPutermanMDP.MarkovPolicies.one_step_boundedLet be a nonempty finite or countable state space. Suppose the real reward satisfies a uniform bound for all available actions. Let , let be a bounded real function on , and let be an admissible randomized Markov decision rule. With and its expected reward and transition operator,
where is the space of bounded real functions on .
This establishes that a single policy-evaluation step remains in the value-function space.
Formalization Note Membership in is expressed by existence of a uniform nonnegative real bound; no norm structure is assumed. The endpoint is included, as on the page.
import Mathlib import Definitions.Def_PutermanMDP_MarkovPolicies_RewardCriteria
namespace PutermanMDP.MarkovPolicies
/-- Lemma 5.6.1: the randomized one-step operator maps V into V. -/
theorem one_step_bounded {S A : Type*} [Countable S] [Nonempty S]
(M : Model S A) (hM : RewardBounded M) (β : ℝ)
(hβ0 : 0 ≤ β) (hβ1 : β ≤ 1)
(u : S → ℝ) (hu : BoundedValue u)
(d : (s : S) → PMF {a : A // a ∈ M.actions s}) :
BoundedValue (oneStep M d β u) := by sorry
end PutermanMDP.MarkovPolicies
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting and hypotheses.
- is a countable, nonempty type of states. is an arbitrary type of actions.
- is a model with nonempty admissible action sets , transition PMFs for , and real rewards .
- has bounded rewards: there is with for all and all .
- is a real number with .
- is bounded: there is with for all .
- is any rule giving, for each state , a PMF on .
Conclusion. The function
is bounded. That is, there is some with absolute value at most at every state. Probabilities are converted to real numbers. Each is an unconditional infinite sum, defined to be when its family is not summable. The conclusion is about the function computed with that convention. The statement gives no explicit value or formula for .
Degenerate cases. Both endpoints and are allowed. At the function is . may have a single element, and is necessarily nonempty. does not depend on time. No assumption is made on beyond being a PMF on admissible actions at each state.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.