Proposition 5.3.1 — geometric horizon equals discounting
ProvedPutermanMDP.MarkovPolicies.geometric_discountConsider a stationary model on a nonempty finite or countable state space, with uniformly bounded rewards on available actions. Let be any admissible randomized history-dependent policy. For , let the independent horizon satisfy for . For every starting state ,
Thus geometric termination and discounting give the same expected reward for each fixed policy.
Formalization Note The random-horizon expectation is the mixture of the fixed-horizon expected returns, with zero terminal reward. This encodes the independence convention directly. The endpoint gives one reward period, not zero periods.
import Mathlib import Definitions.Def_PutermanMDP_MarkovPolicies_RewardCriteria
namespace PutermanMDP.MarkovPolicies
/-- Proposition 5.3.1, including β=0 and a horizon supported on 1,2,... . -/
theorem geometric_discount {S A : Type*} [Countable S] [Nonempty S]
(M : Model S A) (hM : RewardBounded M) (π : HistoryPolicy M)
(β : ℝ) (hβ0 : 0 ≤ β) (hβ1 : β < 1) :
∀ s : S, geometricReturn M π (PMF.pure s) β =
discountedReturn M π (PMF.pure s) β := 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 on with nonempty admissible action sets , transition PMFs for admissible , and real rewards .
- has bounded rewards: there is with for all and all .
- is any history policy, that is, any PMF on for every history . Here is a finite list of past state–action pairs and is the current state.
- is a real number with .
Conclusion. For every state , write for the initial distribution that puts all its mass on . Then
Here is the expected reward at time :
is the state–action law generated by from . Concretely:
- Start from history .
- Repeat times: draw an action from given the current history, draw the next state from , and prepend the (state, action) pair to the list.
- Then draw one more action from given the current history , and record the pair .
Every is defined to be when its family is not summable. The equality is between these conventionally defined values.
Degenerate cases. is allowed. With , both sides then reduce to , the expected immediate reward. is excluded. may have a single element. is necessarily nonempty, because is nonempty and each is nonempty. The statement concerns only point-mass initial distributions, not general . The policy is unrestricted: it may depend on the entire history.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.