Truncating a trajectory law to a shorter horizon
ProvedBanditAlgorithm.mdp_measure_map_restrictLet be a finite MDP, a policy and an initial state distribution, and let denote the law of the trajectory produced by their interconnection. For , the pushforward of along the restriction map that keeps only the first rounds is :
In other words the finite-horizon laws of Lattimore and Szepesvári, Figure 38.1, are consistent, so a quantity depending only on the first rounds has the same expectation at every horizon . This is what makes it legitimate to compute, inside a single horizon- expectation, probabilities of events such as "the target state has not been visited during the first rounds", whose natural home is the horizon- measure; it is used in that way when the accumulated Bellman inequality is summed against the marginals that define the travel time of Definition 38.1.
The proof reduces to the one-round case by induction, since restricting from to is restricting from to after forgetting the last round. The one-round case holds because is by construction the pushforward along of the composition-product of with the step kernel, and the first marginal of a composition-product with a Markov kernel is the first factor.
import Definitions.Def_FiniteMDPLearning import Mathlib.Probability.Kernel.Composition.IntegralCompProd open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.mdp_measure_map_restrict {S A : ℕ} (M : FiniteMDP S A)
(μ0 : MDPStateDistribution S) (π : MDPPolicy S A) {m n : ℕ} (hmn : m ≤ n) :
(mdpMeasure M μ0 π n).map (fun (h : MDPTrajectory S A n) (t : Fin m) ↦
h (Fin.castLE hmn t))
= mdpMeasure M μ0 π m := by
sorry