Algorithm density

We define a density function that allows obtaining the law of the history under one algorithm from the law of the history under another algorithm when they are interacting with the same environment. This also requires one algorithm to be absolutely continuous with respect to another, a concept that we also introduce here.

Main definitions

• AbsolutelyContinuous alg alg₀: alg is absolutely continuous with respect to alg₀ (also denoted alg ≪ₐ alg₀) when, in every situation, a set of actions with probability zero under alg₀ also has probability zero under alg. Intuitively, alg never acts in a way that alg₀ would never act.
• density alg alg₀ n: a density function that allows obtaining the law of the history at time n under alg from the law of the history at time n under alg₀ when they are interacting with the same environment and alg ≪ₐ alg₀.

Main results

• absolutelyContinuous_map_hist: the law of the history at time n under alg is absolutely continuous with respect to the law of the history at time n under alg₀ when they are interacting with the same environment and alg ≪ₐ alg₀.
• hasLaw_history_withDensity: the law of the history at time n under alg is the law of the history at time n under alg₀ with density alg.density alg₀ n when they are interacting with the same environment and alg ≪ₐ alg₀.

structure Learning.Algorithm.AbsolutelyContinuous {𝓞 : Type u_1} {𝓐 : Type u_2} {𝓨 : Type u_3} [MeasurableSpace 𝓞] [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] (alg alg₀ : Algorithm 𝓞 𝓐 𝓨) : Prop

For every time and history, the distribution over actions according to alg is absolutely continuous with respect to the distribution over actions according to alg₀.

• policy (n : ℕ) (h : Hist 𝓞 𝓐 𝓨 n × 𝓞) : ((alg.policy n) h).AbsolutelyContinuous ((alg₀.policy n) h)

def Learning.Algorithm.«term_≪ₐ_» : Lean.TrailingParserDescr

For every time and history, the distribution over actions according to alg is absolutely continuous with respect to the distribution over actions according to alg₀.

Equations

• One or more equations did not get rendered due to their size.

theorem Learning.Algorithm.AbsolutelyContinuous.p0 {𝓞 : Type u_1} {𝓐 : Type u_2} {𝓨 : Type u_3} [MeasurableSpace 𝓞] [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] {alg alg₀ : Algorithm 𝓞 𝓐 𝓨} (h : alg.AbsolutelyContinuous alg₀) (o : 𝓞) : (alg.p0 o).AbsolutelyContinuous (alg₀.p0 o)

noncomputable def Learning.Algorithm.density {𝓞 : Type u_1} {𝓐 : Type u_2} {𝓨 : Type u_3} [MeasurableSpace 𝓞] [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] [MeasurableSpace.CountablyGenerated 𝓐] (alg alg₀ : Algorithm 𝓞 𝓐 𝓨) (n : ℕ) : Hist 𝓞 𝓐 𝓨 n → ENNReal

If the algorithm alg is absolutely continuous with respect to the algorithm alg₀ and they are both interacting with the same environment, then the law of the history before time n under alg is the law of the history before time n under alg₀ with density alg.density alg₀ n.

Equations

• One or more equations did not get rendered due to their size.
• alg.density alg₀ 0 x_2 = 1

@[simp]

theorem Learning.Algorithm.density_zero {𝓞 : Type u_1} {𝓐 : Type u_2} {𝓨 : Type u_3} [MeasurableSpace 𝓞] [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] [MeasurableSpace.CountablyGenerated 𝓐] (alg alg₀ : Algorithm 𝓞 𝓐 𝓨) (h : Hist 𝓞 𝓐 𝓨 0) : alg.density alg₀ 0 h = 1

theorem Learning.Algorithm.measurable_density {𝓞 : Type u_1} {𝓐 : Type u_2} {𝓨 : Type u_3} [MeasurableSpace 𝓞] [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] [MeasurableSpace.CountablyGenerated 𝓐] (alg alg₀ : Algorithm 𝓞 𝓐 𝓨) (n : ℕ) : Measurable (alg.density alg₀ n)

theorem Learning.IsAlgEnvSeq.absolutelyContinuous_map_history {𝓞 : Type u_1} {𝓐 : Type u_2} {𝓨 : Type u_3} [MeasurableSpace 𝓞] [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] {Ω : Type u_4} [MeasurableSpace Ω] {alg : Algorithm 𝓞 𝓐 𝓨} {env : Environment 𝓞 𝓐 𝓨} {O : ℕ → Ω → 𝓞} {A : ℕ → Ω → 𝓐} {Y : ℕ → Ω → 𝓨} {P : MeasureTheory.Measure Ω} [MeasureTheory.IsProbabilityMeasure P] {Ω₀ : Type u_5} [MeasurableSpace Ω₀] {alg₀ : Algorithm 𝓞 𝓐 𝓨} {O₀ : ℕ → Ω₀ → 𝓞} {A₀ : ℕ → Ω₀ → 𝓐} {Y₀ : ℕ → Ω₀ → 𝓨} {P₀ : MeasureTheory.Measure Ω₀} [MeasureTheory.IsProbabilityMeasure P₀] (h : IsAlgEnvSeq O A Y alg env P) (h₀ : IsAlgEnvSeq O₀ A₀ Y₀ alg₀ env P₀) (hc : alg.AbsolutelyContinuous alg₀) (n : ℕ) : (MeasureTheory.Measure.map (history O A Y n) P).AbsolutelyContinuous (MeasureTheory.Measure.map (history O₀ A₀ Y₀ n) P₀)

theorem Learning.IsAlgEnvSeq.hasLaw_history_withDensity {𝓞 : Type u_1} {𝓐 : Type u_2} {𝓨 : Type u_3} [MeasurableSpace 𝓞] [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] {Ω : Type u_4} [MeasurableSpace Ω] {alg : Algorithm 𝓞 𝓐 𝓨} {env : Environment 𝓞 𝓐 𝓨} {O : ℕ → Ω → 𝓞} {A : ℕ → Ω → 𝓐} {Y : ℕ → Ω → 𝓨} {P : MeasureTheory.Measure Ω} [MeasureTheory.IsProbabilityMeasure P] {Ω₀ : Type u_5} [MeasurableSpace Ω₀] {alg₀ : Algorithm 𝓞 𝓐 𝓨} {O₀ : ℕ → Ω₀ → 𝓞} {A₀ : ℕ → Ω₀ → 𝓐} {Y₀ : ℕ → Ω₀ → 𝓨} {P₀ : MeasureTheory.Measure Ω₀} [MeasureTheory.IsProbabilityMeasure P₀] [MeasurableSpace.CountablyGenerated 𝓐] (h : IsAlgEnvSeq O A Y alg env P) (h₀ : IsAlgEnvSeq O₀ A₀ Y₀ alg₀ env P₀) (hc : alg.AbsolutelyContinuous alg₀) (n : ℕ) : ProbabilityTheory.HasLaw (history O A Y n) ((MeasureTheory.Measure.map (history O₀ A₀ Y₀ n) P₀).withDensity (alg.density alg₀ n)) P