One-round peel of a trajectory integral
ProvedBanditAlgorithm.mdp_integral_trajectory_succLet be a finite MDP, a policy and an initial state distribution. For every and every on trajectories of rounds,
where is the law of the trajectory produced by the interconnection of with , and is the kernel that draws the next state from (from when ) and then the action from given the history.
This is the Markov property of the interaction protocol of Lattimore and Szepesvári, Figure 38.1, in the form in which every argument about MDP trajectories consumes it: it is the induction step for any quantity accumulated along a trajectory, and in particular for the accumulation of the Bellman inequality and for the martingale-difference term of the UCRL2 regret decomposition.
No integrability hypothesis is needed: the trajectory space is finite, so every function on it is integrable against a finite measure. The proof is the change of variables along the map that appends the last round, followed by the Fubini property of the composition-product of a measure with a kernel.
import Definitions.Def_FiniteMDPLearning import Mathlib.Probability.Kernel.Composition.IntegralCompProd open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.mdp_integral_trajectory_succ {S A : ℕ} (M : FiniteMDP S A)
(μ0 : MDPStateDistribution S) (π : MDPPolicy S A) (n : ℕ)
(F : MDPTrajectory S A (n + 1) → ℝ) :
∫ h, F h ∂(mdpMeasure M μ0 π (n + 1))
= ∫ h, (∫ p, F (Fin.snoc h p) ∂(mdpStepKernel M μ0 π n h))
∂(mdpMeasure M μ0 π n) := by
sorry