Stopped relative entropy is approximated by bounded stopping times
ProvedBanditAlgorithm.klDiv_stopped_le_iSup_truncationsRun the same adaptive bandit policy in two environments, producing trajectory laws and , and let be a stopping time with finite expectation under . Write for the stopped sigma-algebra and . Then the relative entropy of the stopped experiment is bounded by the supremum of the relative entropies of its bounded truncations:
This is the measure-theoretic truncation principle needed to pass finite-horizon likelihood calculations to an integrable, possibly unbounded stopping time. It is useful beyond best-arm identification whenever an adaptive experiment is observed at a random horizon.
Formalization Note The trajectory measures are restricted with Measure.trim to Mathlib's stopped measurable spaces. The supremum is represented as an ENNReal indexed supremum.
import Definitions.Def_BanditTrajectory open MeasureTheory ProbabilityTheory InformationTheory ENNReal
theorem BanditAlgorithm.klDiv_stopped_le_iSup_truncations
{k : ℕ} (ν ν' : StochasticBandit k) (π : BanditPolicy k)
(τ : (ℕ → Fin k × ℝ) → ℕ∞) (hτ : IsBanditStoppingTime τ)
(hfinite : ∫⁻ ω, (τ ω : ℝ≥0∞) ∂banditTrajMeasure ν π < ⊤) :
@klDiv (ℕ → Fin k × ℝ) hτ.measurableSpace
((banditTrajMeasure ν π).trim hτ.measurableSpace_le)
((banditTrajMeasure ν' π).trim hτ.measurableSpace_le) ≤
⨆ n : ℕ,
@klDiv (ℕ → Fin k × ℝ) (hτ.min_const n).measurableSpace
((banditTrajMeasure ν π).trim (hτ.min_const n).measurableSpace_le)
((banditTrajMeasure ν' π).trim (hτ.min_const n).measurableSpace_le) := by
sorry