Bandits.TS.integral_regret

`integral_regret_le`🔗

TheoremBandits.TS.integral_regret_le

Details

If Thompson sampling has the correct prior over environments and every environment has K actions, each of which has a corresponding reward between l and u that is sub-Gaussian with variance proxy σ2 after its mean is subtracted, then the Bayesian regret at time n is at most (2 * K + 1) * (u - l) + 8 * √(σ2 * K * n * Real.log n).

theorem

Bandits.TS.integral_regret_le.{u_1, u_2} {K : ℕ} [Nonempty (Fin K)]
  {l u σ2 : ℝ} {Ω : Type u_1} [MeasurableSpace Ω] {𝓔 : Type u_2}
  [MeasurableSpace 𝓔] [StandardBorelSpace 𝓔] [Nonempty 𝓔]
  {Q : MeasureTheory.Measure 𝓔} [MeasureTheory.IsProbabilityMeasure Q]
  {κ : ProbabilityTheory.Kernel (𝓔 × Fin K) ℝ}
  [ProbabilityTheory.IsMarkovKernel κ] {E : Ω → 𝓔} {A : ℕ → Ω → Fin K}
  {R : ℕ → Ω → ℝ} {P : MeasureTheory.Measure Ω}
  [MeasureTheory.IsProbabilityMeasure P] (hK : 0 < K)
  (h : Learning.IsBayesAlgEnvSeq Q κ (tsAlgorithm hK Q κ) E A R P)
  (hlu : l ≤ u)
  (hm : ∀ (e : 𝓔) (a : Fin K), ∫ (x : ℝ), id x ∂κ (e, a) ∈ Set.Icc l u)
  (hσ2 : 0 < σ2)
  (hs :
    ∀ (e : 𝓔) (a : Fin K),
      ProbabilityTheory.HasSubgaussianMGF
        (fun x => x - ∫ (x : ℝ), id x ∂κ (e, a)) ⟨σ2, ⋯⟩ (κ (e, a)))
  (n : ℕ) :
  ∫ (x : Ω), Learning.IsBayesAlgEnvSeq.regret κ E A n x ∂P ≤
    (2 * ↑K + 1) * (u - l) + 8 * √(σ2 * ↑K * ↑n * Real.log ↑n)
Bandits.TS.integral_regret_le.{u_1, u_2}
  {K : ℕ} [Nonempty (Fin K)] {l u σ2 : ℝ}
  {Ω : Type u_1} [MeasurableSpace Ω]
  {𝓔 : Type u_2} [MeasurableSpace 𝓔]
  [StandardBorelSpace 𝓔] [Nonempty 𝓔]
  {Q : MeasureTheory.Measure 𝓔}
  [MeasureTheory.IsProbabilityMeasure Q]
  {κ :
    ProbabilityTheory.Kernel (𝓔 × Fin K)
      ℝ}
  [ProbabilityTheory.IsMarkovKernel κ]
  {E : Ω → 𝓔} {A : ℕ → Ω → Fin K}
  {R : ℕ → Ω → ℝ}
  {P : MeasureTheory.Measure Ω}
  [MeasureTheory.IsProbabilityMeasure P]
  (hK : 0 < K)
  (h :
    Learning.IsBayesAlgEnvSeq Q κ
      (tsAlgorithm hK Q κ) E A R P)
  (hlu : l ≤ u)
  (hm :
    ∀ (e : 𝓔) (a : Fin K),
      ∫ (x : ℝ), id x ∂κ (e, a) ∈
        Set.Icc l u)
  (hσ2 : 0 < σ2)
  (hs :
    ∀ (e : 𝓔) (a : Fin K),
      ProbabilityTheory.HasSubgaussianMGF
        (fun x =>
          x - ∫ (x : ℝ), id x ∂κ (e, a))
        ⟨σ2, ⋯⟩ (κ (e, a)))
  (n : ℕ) :
  ∫ (x : Ω),
      Learning.IsBayesAlgEnvSeq.regret κ E
        A n x ∂P ≤
    (2 * ↑K + 1) * (u - l) +
      8 * √(σ2 * ↑K * ↑n * Real.log ↑n)

Code

theorem integral_regret_le (hK : 0 < K) (h : IsBayesAlgEnvSeq Q κ (tsAlgorithm hK Q κ) E A R P)
    (hlu : l ≤ u) (hm : ∀ e a, (κ (e, a))[id] ∈ (Set.Icc l u)) (hσ2 : 0 < σ2)
    (hs : ∀ e a, HasSubgaussianMGF (fun x ↦ x - (κ (e, a))[id]) ⟨σ2, hσ2.le⟩ (κ (e, a))) (n : ℕ) :
    P[IsBayesAlgEnvSeq.regret κ E A n]
      ≤ (2 * K + 1) * (u - l) + 8 * √(σ2 * K * n * Real.log n)

Type uses (3)

Body uses (6)

Actions: Source · Open Issue

Proof

by
  by_cases hn : n = 0
  · simp [hn, IsBayesAlgEnvSeq.regret, Bandits.regret]
    nlinarith
  have hδ : (0 : ℝ) < 1 / n ^ 2 := by positivity
  calc P[IsBayesAlgEnvSeq.regret κ E A n]
      = _ :=
        integral_regret_eq_add hK h hm n
    _ ≤ _ :=
        add_le_add
          (integral_sum_range_actionMean_bestAction_sub_ucb_bestAction_le h hlu hm hσ2 hs hδ n)
          (integral_sum_range_ucb_action_sub_actionMean_action_le h hlu hm hσ2 hs hδ n)
    _ = K * (u - l) + (K + 1) * (u - l) * ((n - 1) / n)
          + 4 * √((2 : ℝ) ^ 2 * (σ2 * K * n * Real.log n)) := by
        field_simp
        rw [Real.log_pow]
        ring_nf
    _ = K * (u - l) + (K + 1) * (u - l) * ((n - 1) / n) + 8 * √(σ2 * K * n * Real.log n) := by
        rw [Real.sqrt_mul (by positivity), Real.sqrt_sq (by norm_num)]
        ring
    _ ≤ K * (u - l) + (K + 1) * (u - l) * 1 + 8 * √(σ2 * K * n * Real.log n) := by -- loose
        have : 0 ≤ u - l := sub_nonneg.2 hlu
        gcongr
        rw [div_le_one (by positivity)]
        linarith
    _ = _ := by
        ring

`IsBayesAlgEnvSeq`🔗

StructureLearning.IsBayesAlgEnvSeq

Details

IsBayesAlgEnvSeq Q κ alg E A Y P states that there is a measure P : Measure Ω such that the parameter E : Ω → 𝓔 has law Q and that the sequences of actions A : ℕ → Ω → 𝓐 and feedbacks Y : ℕ → Ω → 𝓨 are generated by the algorithm alg : Algorithm 𝓐 𝓨 interacting with an underlying environment that depends on E and κ (stationaryEnv (κ.sectR (E ω))).

structure

Learning.IsBayesAlgEnvSeq.{u_1, u_2, u_3, u_4} {𝓔 : Type u_1}
  {𝓐 : Type u_2} {𝓨 : Type u_3} {Ω : Type u_4} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] [MeasurableSpace Ω]
  (Q : MeasureTheory.Measure 𝓔) (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) 𝓨)
  (alg : Algorithm 𝓐 𝓨) (E : Ω → 𝓔) (A : ℕ → Ω → 𝓐) (Y : ℕ → Ω → 𝓨)
  (P : MeasureTheory.Measure Ω) [MeasureTheory.IsFiniteMeasure P] : Prop
Learning.IsBayesAlgEnvSeq.{u_1, u_2, u_3,
    u_4}
  {𝓔 : Type u_1} {𝓐 : Type u_2}
  {𝓨 : Type u_3} {Ω : Type u_4}
  [MeasurableSpace 𝓔] [MeasurableSpace 𝓐]
  [MeasurableSpace 𝓨] [MeasurableSpace Ω]
  (Q : MeasureTheory.Measure 𝓔)
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) 𝓨)
  (alg : Algorithm 𝓐 𝓨) (E : Ω → 𝓔)
  (A : ℕ → Ω → 𝓐) (Y : ℕ → Ω → 𝓨)
  (P : MeasureTheory.Measure Ω)
  [MeasureTheory.IsFiniteMeasure P] : Prop

Code

structure IsBayesAlgEnvSeq
    (Q : Measure 𝓔) (κ : Kernel (𝓔 × 𝓐) 𝓨) (alg : Algorithm 𝓐 𝓨)
    (E : Ω → 𝓔) (A : ℕ → Ω → 𝓐) (Y : ℕ → Ω → 𝓨)
    (P : Measure Ω) [IsFiniteMeasure P] : Prop where
  measurable_param : Measurable E := by fun_prop
  measurable_action n : Measurable (A n) := by fun_prop
  measurable_feedback n : Measurable (Y n) := by fun_prop
  hasLaw_env : HasLaw E Q P
  hasCondDistrib_action_zero : HasCondDistrib (A 0) E (Kernel.const _ alg.p0) P
  hasCondDistrib_feedback_zero : HasCondDistrib (Y 0) (fun ω ↦ (E ω, A 0 ω)) κ P
  hasCondDistrib_action n :
    HasCondDistrib (A (n + 1)) (fun ω ↦ (E ω, history A Y n ω))
      ((alg.policy n).prodMkLeft _) P
  hasCondDistrib_feedback n :
    HasCondDistrib (Y (n + 1)) (fun ω ↦ (history A Y n ω, E ω, A (n + 1) ω))
      (κ.prodMkLeft _) P

Type uses (2)

Used by (22)

Actions: Source · Open Issue

`tsAlgorithm`🔗

DefinitionBandits.tsAlgorithm

Details

The Thompson sampling algorithm with actions in Fin K, where Q : Measure 𝓔 is a prior distribution over parameters, and κ : Kernel (𝓔 × Fin K) ℝ is a Markov kernel that defines the stationary environment stationaryEnv (κ.sectR e) that corresponds to a parameter e : 𝓔.

At every time n, the Thompson sampling policy uses the posterior over the parameters given the history up to time n to derive the probability of each action being optimal. The action for time n is sampled according to these probabilities.

def

Bandits.tsAlgorithm.{u_1} {K : ℕ} {𝓔 : Type u_1} [MeasurableSpace 𝓔]
  [StandardBorelSpace 𝓔] [Nonempty 𝓔] (hK : 0 < K)
  (Q : MeasureTheory.Measure 𝓔) [MeasureTheory.IsProbabilityMeasure Q]
  (κ : ProbabilityTheory.Kernel (𝓔 × Fin K) ℝ)
  [ProbabilityTheory.IsMarkovKernel κ] : Learning.Algorithm (Fin K) ℝ
Bandits.tsAlgorithm.{u_1} {K : ℕ}
  {𝓔 : Type u_1} [MeasurableSpace 𝓔]
  [StandardBorelSpace 𝓔] [Nonempty 𝓔]
  (hK : 0 < K)
  (Q : MeasureTheory.Measure 𝓔)
  [MeasureTheory.IsProbabilityMeasure Q]
  (κ :
    ProbabilityTheory.Kernel (𝓔 × Fin K)
      ℝ)
  [ProbabilityTheory.IsMarkovKernel κ] :
  Learning.Algorithm (Fin K) ℝ

Code

noncomputable
def tsAlgorithm (hK : 0 < K) (Q : Measure 𝓔) [IsProbabilityMeasure Q] (κ : Kernel (𝓔 × Fin K) ℝ)
    [IsMarkovKernel κ] : Algorithm (Fin K) ℝ where
  policy := TS.policy hK Q κ
  p0 := TS.initialPolicy hK Q κ

Type uses (1)

Algorithm

Body uses (4)

Used by (4)

Actions: Source · Open Issue

`regret`🔗

DefinitionLearning.IsBayesAlgEnvSeq.regret

Details

A random variable that gives the regret at time n.

def

Learning.IsBayesAlgEnvSeq.regret.{u_1, u_2, u_4} {𝓔 : Type u_1}
  {𝓐 : Type u_2} {Ω : Type u_4} [MeasurableSpace 𝓔] [MeasurableSpace 𝓐]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) ℝ) (E : Ω → 𝓔) (A : ℕ → Ω → 𝓐)
  (n : ℕ) (ω : Ω) : ℝ
Learning.IsBayesAlgEnvSeq.regret.{u_1,
    u_2, u_4}
  {𝓔 : Type u_1} {𝓐 : Type u_2}
  {Ω : Type u_4} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) ℝ)
  (E : Ω → 𝓔) (A : ℕ → Ω → 𝓐) (n : ℕ)
  (ω : Ω) : ℝ

Code

noncomputable
def regret (κ : Kernel (𝓔 × 𝓐) ℝ) (E : Ω → 𝓔) (A : ℕ → Ω → 𝓐) (n : ℕ) (ω : Ω) : ℝ :=
  Bandits.regret (κ.sectR (E ω)) A n ω

Body uses (1)

regret

Used by (6)

Actions: Source · Open Issue

`Algorithm`🔗

StructureLearning.Algorithm

Details

A stochastic, sequential algorithm.

structure

Learning.Algorithm.{u_4, u_5} (𝓐 : Type u_4) (𝓨 : Type u_5)
  [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] : Type (max u_4 u_5)
Learning.Algorithm.{u_4, u_5}
  (𝓐 : Type u_4) (𝓨 : Type u_5)
  [MeasurableSpace 𝓐]
  [MeasurableSpace 𝓨] : Type (max u_4 u_5)

Code

structure Algorithm (𝓐 𝓨 : Type*) [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] where
  /-- Policy or sampling rule: distribution of the next action. -/
  policy : (n : ℕ) → Kernel (Iic n → 𝓐 × 𝓨) 𝓐
  /-- The policy is a Markov kernel. -/
  [h_policy : ∀ n, IsMarkovKernel (policy n)]
  /-- Distribution of the first action. -/
  p0 : Measure 𝓐
  /-- The first action distribution is a probability measure. -/
  [hp0 : IsProbabilityMeasure p0]

Used by (216)

Actions: Source · Open Issue

`history`🔗

DefinitionLearning.history

Details

History of the algorithm-environment sequence up to time n.

def

Learning.history.{u_1, u_2, u_3} {𝓐 : Type u_1} {𝓨 : Type u_2}
  {Ω : Type u_3} (A : ℕ → Ω → 𝓐) (Y : ℕ → Ω → 𝓨) (n : ℕ) (ω : Ω) :
  ↥(Finset.Iic n) → 𝓐 × 𝓨
Learning.history.{u_1, u_2, u_3}
  {𝓐 : Type u_1} {𝓨 : Type u_2}
  {Ω : Type u_3} (A : ℕ → Ω → 𝓐)
  (Y : ℕ → Ω → 𝓨) (n : ℕ) (ω : Ω) :
  ↥(Finset.Iic n) → 𝓐 × 𝓨

Code

def history (A : ℕ → Ω → 𝓐) (Y : ℕ → Ω → 𝓨) (n : ℕ) (ω : Ω) : Iic n → 𝓐 × 𝓨 :=
  fun i ↦ (A i ω, Y i ω)

Used by (72)

Actions: Source · Open Issue

`action`🔗

DefinitionLearning.IT.action

Details

action n is the action pulled at time n. This is a random variable on the measurable space ℕ → 𝓐 × 𝓨.

def

Learning.IT.action.{u_1, u_2} {𝓐 : Type u_1} {𝓨 : Type u_2} (n : ℕ)
  (h : ℕ → 𝓐 × 𝓨) : 𝓐
Learning.IT.action.{u_1, u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2} (n : ℕ)
  (h : ℕ → 𝓐 × 𝓨) : 𝓐

Code

def action (n : ℕ) (h : ℕ → 𝓐 × 𝓨) : 𝓐 := (h n).1

Used by (31)

Actions: Source · Open Issue

`Environment`🔗

StructureLearning.Environment

Details

A stochastic environment.

structure

Learning.Environment.{u_4, u_5} (𝓐 : Type u_4) (𝓨 : Type u_5)
  [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] : Type (max u_4 u_5)
Learning.Environment.{u_4, u_5}
  (𝓐 : Type u_4) (𝓨 : Type u_5)
  [MeasurableSpace 𝓐]
  [MeasurableSpace 𝓨] : Type (max u_4 u_5)

Code

structure Environment (𝓐 𝓨 : Type*) [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] where
  /-- Distribution of the next observation as function of the past history. -/
  feedback : (n : ℕ) → Kernel ((Iic n → 𝓐 × 𝓨) × 𝓐) 𝓨
  /-- The feedback kernels are Markov kernels. -/
  [h_feedback : ∀ n, IsMarkovKernel (feedback n)]
  /-- Distribution of the first observation given the first action. -/
  ν0 : Kernel 𝓐 𝓨
  /-- The initial observation kernel is a Markov kernel. -/
  [hp0 : IsMarkovKernel ν0]

Used by (128)

Actions: Source · Open Issue

`stepKernel`🔗

DefinitionLearning.stepKernel

Details

Kernel describing the distribution of the next action-feedback pair given the history up to n.

def

Learning.stepKernel.{u_1, u_2} {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐} {m𝓨 : MeasurableSpace 𝓨}
  (alg : Algorithm 𝓐 𝓨) (env : Environment 𝓐 𝓨) (n : ℕ) :
  ProbabilityTheory.Kernel (↥(Finset.Iic n) → 𝓐 × 𝓨) (𝓐 × 𝓨)
Learning.stepKernel.{u_1, u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨}
  (alg : Algorithm 𝓐 𝓨)
  (env : Environment 𝓐 𝓨) (n : ℕ) :
  ProbabilityTheory.Kernel
    (↥(Finset.Iic n) → 𝓐 × 𝓨) (𝓐 × 𝓨)

Code

noncomputable
def stepKernel (alg : Algorithm 𝓐 𝓨) (env : Environment 𝓐 𝓨) (n : ℕ) :
    Kernel (Iic n → 𝓐 × 𝓨) (𝓐 × 𝓨) :=
  alg.policy n ⊗ₖ env.feedback n
deriving IsMarkovKernel

Type uses (2)

Used by (17)

Actions: Source · Open Issue

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdPolicy`🔗

InstanceLearning.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdPolicy

Details

No docstring.

theorem

Learning.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdPolicy.{u_1,
    u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2} {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨} (alg : Algorithm 𝓐 𝓨) (n : ℕ) :
  ProbabilityTheory.IsMarkovKernel (Algorithm.policy alg n)
Learning.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdPolicy.{u_1,
    u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨}
  (alg : Algorithm 𝓐 𝓨) (n : ℕ) :
  ProbabilityTheory.IsMarkovKernel
    (Algorithm.policy alg n)

Code

instance (alg : Algorithm 𝓐 𝓨) (n : ℕ) : IsMarkovKernel (alg.policy n)

Type uses (1)

Algorithm

Used by (14)

Actions: Source · Open Issue

Proof

alg.h_policy n

`instIsMarkovKernelProdForallSubtypeNatMemFinsetIicFeedback`🔗

InstanceLearning.instIsMarkovKernelProdForallSubtypeNatMemFinsetIicFeedback

Details

No docstring.

theorem

Learning.instIsMarkovKernelProdForallSubtypeNatMemFinsetIicFeedback.{u_1,
    u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2} {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨} (env : Environment 𝓐 𝓨) (n : ℕ) :
  ProbabilityTheory.IsMarkovKernel (Environment.feedback env n)
Learning.instIsMarkovKernelProdForallSubtypeNatMemFinsetIicFeedback.{u_1,
    u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨}
  (env : Environment 𝓐 𝓨) (n : ℕ) :
  ProbabilityTheory.IsMarkovKernel
    (Environment.feedback env n)

Code

instance (env : Environment 𝓐 𝓨) (n : ℕ) : IsMarkovKernel (env.feedback n)

Type uses (1)

Environment

Used by (5)

Actions: Source · Open Issue

Proof

env.h_feedback n

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdStepKernel`🔗

InstanceLearning.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdStepKernel

Details

No docstring.

theorem

Learning.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdStepKernel.{u_1,
    u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2} {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨} (alg : Algorithm 𝓐 𝓨) (env : Environment 𝓐 𝓨)
  (n : ℕ) : ProbabilityTheory.IsMarkovKernel (stepKernel alg env n)
Learning.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdStepKernel.{u_1,
    u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨}
  (alg : Algorithm 𝓐 𝓨)
  (env : Environment 𝓐 𝓨) (n : ℕ) :
  ProbabilityTheory.IsMarkovKernel
    (stepKernel alg env n)

Code

deriving IsMarkovKernel

Type uses (3)

Body uses (2)

Used by (10)

Actions: Source · Open Issue

Proof

deriving IsMarkovKernel

`trajMeasure`🔗

DefinitionLearning.trajMeasure

Details

Measure on the sequence of actions and observations generated by the algorithm/environment.

def

Learning.trajMeasure.{u_1, u_2} {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐} {m𝓨 : MeasurableSpace 𝓨}
  (alg : Algorithm 𝓐 𝓨) (env : Environment 𝓐 𝓨) :
  MeasureTheory.Measure (ℕ → 𝓐 × 𝓨)
Learning.trajMeasure.{u_1, u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨}
  (alg : Algorithm 𝓐 𝓨)
  (env : Environment 𝓐 𝓨) :
  MeasureTheory.Measure (ℕ → 𝓐 × 𝓨)

Code

noncomputable
def trajMeasure (alg : Algorithm 𝓐 𝓨) (env : Environment 𝓐 𝓨) :
    Measure (ℕ → 𝓐 × 𝓨) :=
  Kernel.trajMeasure (alg.p0 ⊗ₘ env.ν0) (stepKernel alg env)
deriving IsProbabilityMeasure

Type uses (2)

Body uses (2)

Used by (19)

Actions: Source · Open Issue

`instIsProbabilityMeasureP0`🔗

InstanceLearning.instIsProbabilityMeasureP0

Details

No docstring.

theorem

Learning.instIsProbabilityMeasureP0.{u_1, u_2} {𝓐 : Type u_1}
  {𝓨 : Type u_2} {m𝓐 : MeasurableSpace 𝓐} {m𝓨 : MeasurableSpace 𝓨}
  (alg : Algorithm 𝓐 𝓨) :
  MeasureTheory.IsProbabilityMeasure (Algorithm.p0 alg)
Learning.instIsProbabilityMeasureP0.{u_1,
    u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨}
  (alg : Algorithm 𝓐 𝓨) :
  MeasureTheory.IsProbabilityMeasure
    (Algorithm.p0 alg)

Code

instance (alg : Algorithm 𝓐 𝓨) : IsProbabilityMeasure alg.p0

Type uses (1)

Algorithm

Used by (13)

Actions: Source · Open Issue

Proof

alg.hp0

`prodLeft`🔗

DefinitionLearning.Algorithm.prodLeft

Details

An algorithm with observations in 𝓧 × 𝓨 obtained from an algorithm with observations in 𝓨 by ignoring the 𝓧 component of each observation.

def

Learning.Algorithm.prodLeft.{u_1, u_2, u_4} {𝓐 : Type u_1}
  {𝓨 : Type u_2} {m𝓐 : MeasurableSpace 𝓐} {m𝓨 : MeasurableSpace 𝓨}
  (𝓧 : Type u_4) [MeasurableSpace 𝓧] (alg : Algorithm 𝓐 𝓨) :
  Algorithm 𝓐 (𝓧 × 𝓨)
Learning.Algorithm.prodLeft.{u_1, u_2,
    u_4}
  {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨} (𝓧 : Type u_4)
  [MeasurableSpace 𝓧]
  (alg : Algorithm 𝓐 𝓨) :
  Algorithm 𝓐 (𝓧 × 𝓨)

Code

def Algorithm.prodLeft (𝓧 : Type*) [MeasurableSpace 𝓧] (alg : Algorithm 𝓐 𝓨) :
    Algorithm 𝓐 (𝓧 × 𝓨) where
  policy n := (alg.policy n).comap (fun h i ↦ ((h i).1, (h i).2.2)) (by fun_prop)
  p0 := alg.p0

Type uses (1)

Algorithm

Body uses (2)

Used by (6)

Actions: Source · Open Issue

`bayesStationaryEnv`🔗

DefinitionLearning.bayesStationaryEnv

Details

An environment with observations in 𝓔 × 𝓨. The first element e of an observation is sampled from Q once and remains constant. The second element of an observation is sampled from κ (e, a), where a is the corresponding action.

def

Learning.bayesStationaryEnv.{u_1, u_2, u_3} {𝓔 : Type u_1}
  {𝓐 : Type u_2} {𝓨 : Type u_3} [MeasurableSpace 𝓔] [MeasurableSpace 𝓐]
  [MeasurableSpace 𝓨] (Q : MeasureTheory.Measure 𝓔)
  [MeasureTheory.IsProbabilityMeasure Q]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) 𝓨)
  [ProbabilityTheory.IsMarkovKernel κ] : Environment 𝓐 (𝓔 × 𝓨)
Learning.bayesStationaryEnv.{u_1, u_2,
    u_3}
  {𝓔 : Type u_1} {𝓐 : Type u_2}
  {𝓨 : Type u_3} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐] [MeasurableSpace 𝓨]
  (Q : MeasureTheory.Measure 𝓔)
  [MeasureTheory.IsProbabilityMeasure Q]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) 𝓨)
  [ProbabilityTheory.IsMarkovKernel κ] :
  Environment 𝓐 (𝓔 × 𝓨)

Code

noncomputable
def bayesStationaryEnv (Q : Measure 𝓔) [IsProbabilityMeasure Q] (κ : Kernel (𝓔 × 𝓐) 𝓨)
    [IsMarkovKernel κ] : Environment 𝓐 (𝓔 × 𝓨) where
  feedback n :=
    let g : (Iic n → 𝓐 × 𝓔 × 𝓨) × 𝓐 → 𝓔 × 𝓐 := fun (h, a) => ((h ⟨0, by simp⟩).2.1, a)
    (Kernel.deterministic (Prod.fst ∘ g) (by fun_prop)) ×ₖ (κ.comap g (by fun_prop))
  ν0 := (Kernel.const _ Q) ⊗ₖ κ.swapLeft

Type uses (1)

Environment

Used by (4)

Actions: Source · Open Issue

`bayesTrajMeasure`🔗

DefinitionLearning.IT.bayesTrajMeasure

Details

A measure P on a measurable space that carries random variables E, A, and Y such that IsBayesAlgEnvSeq Q κ alg E A Y P.

def

Learning.IT.bayesTrajMeasure.{u_1, u_2, u_3} {𝓔 : Type u_1}
  {𝓐 : Type u_2} {𝓨 : Type u_3} [MeasurableSpace 𝓔] [MeasurableSpace 𝓐]
  [MeasurableSpace 𝓨] (Q : MeasureTheory.Measure 𝓔)
  [MeasureTheory.IsProbabilityMeasure Q]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) 𝓨)
  [ProbabilityTheory.IsMarkovKernel κ] (alg : Algorithm 𝓐 𝓨) :
  MeasureTheory.Measure (ℕ → 𝓐 × 𝓔 × 𝓨)
Learning.IT.bayesTrajMeasure.{u_1, u_2,
    u_3}
  {𝓔 : Type u_1} {𝓐 : Type u_2}
  {𝓨 : Type u_3} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐] [MeasurableSpace 𝓨]
  (Q : MeasureTheory.Measure 𝓔)
  [MeasureTheory.IsProbabilityMeasure Q]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) 𝓨)
  [ProbabilityTheory.IsMarkovKernel κ]
  (alg : Algorithm 𝓐 𝓨) :
  MeasureTheory.Measure (ℕ → 𝓐 × 𝓔 × 𝓨)

Code

noncomputable
def bayesTrajMeasure (Q : Measure 𝓔) [IsProbabilityMeasure Q] (κ : Kernel (𝓔 × 𝓐) 𝓨)
    [IsMarkovKernel κ] (alg : Algorithm 𝓐 𝓨) : Measure (ℕ → 𝓐 × 𝓔 × 𝓨) :=
  trajMeasure (alg.prodLeft 𝓔) (bayesStationaryEnv Q κ)
deriving IsProbabilityMeasure

Type uses (1)

Algorithm

Body uses (3)

Used by (5)

Actions: Source · Open Issue

`instIsMarkovKernelν0`🔗

InstanceLearning.instIsMarkovKernelν0

Details

No docstring.

theorem

Learning.instIsMarkovKernelν0.{u_1, u_2} {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐} {m𝓨 : MeasurableSpace 𝓨}
  (env : Environment 𝓐 𝓨) :
  ProbabilityTheory.IsMarkovKernel (Environment.ν0 env)
Learning.instIsMarkovKernelν0.{u_1, u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨}
  (env : Environment 𝓐 𝓨) :
  ProbabilityTheory.IsMarkovKernel
    (Environment.ν0 env)

Code

instance (env : Environment 𝓐 𝓨) : IsMarkovKernel env.ν0

Type uses (1)

Environment

Used by (8)

Actions: Source · Open Issue

Proof

env.hp0

`instIsProbabilityMeasureForallNatProdTrajMeasure`🔗

InstanceLearning.instIsProbabilityMeasureForallNatProdTrajMeasure

Details

No docstring.

theorem

Learning.instIsProbabilityMeasureForallNatProdTrajMeasure.{u_1, u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2} {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨} (alg : Algorithm 𝓐 𝓨)
  (env : Environment 𝓐 𝓨) :
  MeasureTheory.IsProbabilityMeasure (trajMeasure alg env)
Learning.instIsProbabilityMeasureForallNatProdTrajMeasure.{u_1,
    u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨}
  (alg : Algorithm 𝓐 𝓨)
  (env : Environment 𝓐 𝓨) :
  MeasureTheory.IsProbabilityMeasure
    (trajMeasure alg env)

Code

deriving IsProbabilityMeasure

Type uses (3)

Body uses (4)

Used by (8)

Actions: Source · Open Issue

Proof

deriving IsProbabilityMeasure

`instIsProbabilityMeasureForallNatProdBayesTrajMeasure`🔗

InstanceLearning.IT.instIsProbabilityMeasureForallNatProdBayesTrajMeasure

Details

No docstring.

theorem

Learning.IT.instIsProbabilityMeasureForallNatProdBayesTrajMeasure.{u_1,
    u_2, u_3}
  {𝓔 : Type u_1} {𝓐 : Type u_2} {𝓨 : Type u_3} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] (Q : MeasureTheory.Measure 𝓔)
  [MeasureTheory.IsProbabilityMeasure Q]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) 𝓨)
  [ProbabilityTheory.IsMarkovKernel κ] (alg : Algorithm 𝓐 𝓨) :
  MeasureTheory.IsProbabilityMeasure (bayesTrajMeasure Q κ alg)
Learning.IT.instIsProbabilityMeasureForallNatProdBayesTrajMeasure.{u_1,
    u_2, u_3}
  {𝓔 : Type u_1} {𝓐 : Type u_2}
  {𝓨 : Type u_3} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐] [MeasurableSpace 𝓨]
  (Q : MeasureTheory.Measure 𝓔)
  [MeasureTheory.IsProbabilityMeasure Q]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) 𝓨)
  [ProbabilityTheory.IsMarkovKernel κ]
  (alg : Algorithm 𝓐 𝓨) :
  MeasureTheory.IsProbabilityMeasure
    (bayesTrajMeasure Q κ alg)

Code

deriving IsProbabilityMeasure

Type uses (2)

Body uses (3)

Used by (4)

Actions: Source · Open Issue

Proof

deriving IsProbabilityMeasure

`bayesTrajMeasurePosterior`🔗

DefinitionLearning.IT.bayesTrajMeasurePosterior

Details

A kernel that represents the posterior over E given the history up to time n.

def

Learning.IT.bayesTrajMeasurePosterior.{u_1, u_2, u_3} {𝓔 : Type u_1}
  {𝓐 : Type u_2} {𝓨 : Type u_3} [MeasurableSpace 𝓔] [MeasurableSpace 𝓐]
  [MeasurableSpace 𝓨] [StandardBorelSpace 𝓔] [Nonempty 𝓔]
  (Q : MeasureTheory.Measure 𝓔) [MeasureTheory.IsProbabilityMeasure Q]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) 𝓨)
  [ProbabilityTheory.IsMarkovKernel κ] (alg : Algorithm 𝓐 𝓨) (n : ℕ) :
  ProbabilityTheory.Kernel (↥(Finset.Iic n) → 𝓐 × 𝓨) 𝓔
Learning.IT.bayesTrajMeasurePosterior.{u_1,
    u_2, u_3}
  {𝓔 : Type u_1} {𝓐 : Type u_2}
  {𝓨 : Type u_3} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐] [MeasurableSpace 𝓨]
  [StandardBorelSpace 𝓔] [Nonempty 𝓔]
  (Q : MeasureTheory.Measure 𝓔)
  [MeasureTheory.IsProbabilityMeasure Q]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) 𝓨)
  [ProbabilityTheory.IsMarkovKernel κ]
  (alg : Algorithm 𝓐 𝓨) (n : ℕ) :
  ProbabilityTheory.Kernel
    (↥(Finset.Iic n) → 𝓐 × 𝓨) 𝓔

Code

noncomputable
def bayesTrajMeasurePosterior [StandardBorelSpace 𝓔] [Nonempty 𝓔]
    (Q : Measure 𝓔) [IsProbabilityMeasure Q] (κ : Kernel (𝓔 × 𝓐) 𝓨) [IsMarkovKernel κ]
    (alg : Algorithm 𝓐 𝓨) (n : ℕ) : Kernel (Iic n → 𝓐 × 𝓨) 𝓔 :=
  condDistrib (fun ω ↦ (ω 0).2.1) (history action (fun n ω ↦ (ω n).2.2) n)
    (bayesTrajMeasure Q κ alg)
deriving IsMarkovKernel

Type uses (1)

Algorithm

Body uses (4)

Used by (4)

Actions: Source · Open Issue

`randomSampling`🔗

DefinitionLearning.randomSampling

Details

The Random Sampling algorithm, which samples from a fixed probability measure at each iteration.

def

Learning.randomSampling.{u_1, u_2} {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐} {m𝓨 : MeasurableSpace 𝓨}
  (μ : MeasureTheory.Measure 𝓐) [MeasureTheory.IsProbabilityMeasure μ] :
  Algorithm 𝓐 𝓨
Learning.randomSampling.{u_1, u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨}
  (μ : MeasureTheory.Measure 𝓐)
  [MeasureTheory.IsProbabilityMeasure μ] :
  Algorithm 𝓐 𝓨

Code

noncomputable def randomSampling (μ : Measure 𝓐) [IsProbabilityMeasure μ] : Algorithm 𝓐 𝓨 where
  policy _ := Kernel.const _ μ
  p0 := μ

Type uses (1)

Algorithm

Used by (5)

Actions: Source · Open Issue

`uniformAlgorithm`🔗

DefinitionLearning.uniformAlgorithm

Details

The Uniform algorithm: actions are chosen uniformly at random.

def

Learning.uniformAlgorithm.{u_1, u_2} {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐} {m𝓨 : MeasurableSpace 𝓨} [Finite 𝓐]
  [Nonempty 𝓐] : Algorithm 𝓐 𝓨
Learning.uniformAlgorithm.{u_1, u_2}
  {𝓐 : Type u_1} {𝓨 : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {m𝓨 : MeasurableSpace 𝓨} [Finite 𝓐]
  [Nonempty 𝓐] : Algorithm 𝓐 𝓨

Code

noncomputable
def uniformAlgorithm [Finite 𝓐] [Nonempty 𝓐] : Algorithm 𝓐 𝓨 := randomSampling (uniformOn Set.univ)

Type uses (1)

Algorithm

Body uses (1)

randomSampling

Used by (4)

Actions: Source · Open Issue

`max`🔗

DefinitionFunction.max

Details

The maximum value of a tuple.

def

Function.max.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : α
Function.max.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : α

Code

abbrev max : α := univ.sup' univ_nonempty f

Used by (8)

Actions: Source · Open Issue

`exists_argmax`🔗

Lemmaexists_argmax

Details

No docstring.

theorem

exists_argmax.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : ∃ i, f i = Function.max f
exists_argmax.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) :
  ∃ i, f i = Function.max f

Code

lemma exists_argmax : ∃ i, f i = f.max

Type uses (1)

max

Used by (3)

Actions: Source · Open Issue

Proof

by
  obtain ⟨i, -, hi⟩ := Finset.exists_mem_eq_sup' (by simp : Finset.univ.Nonempty) f
  exact ⟨i, hi.symm⟩

`argmax`🔗

Definitionargmax

Details

The index of the maximum value of a tuple.

def

argmax.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : ι
argmax.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : ι

Code

noncomputable def argmax := (exists_argmax f).choose

Body uses (2)

Used by (17)

Actions: Source · Open Issue

`actionMean`🔗

DefinitionLearning.IsBayesAlgEnvSeq.actionMean

Details

A random variable that gives the mean feedback of action a.

def

Learning.IsBayesAlgEnvSeq.actionMean.{u_1, u_2, u_4} {𝓔 : Type u_1}
  {𝓐 : Type u_2} {Ω : Type u_4} [MeasurableSpace 𝓔] [MeasurableSpace 𝓐]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) ℝ) (E : Ω → 𝓔) (a : 𝓐) (ω : Ω) :
  ℝ
Learning.IsBayesAlgEnvSeq.actionMean.{u_1,
    u_2, u_4}
  {𝓔 : Type u_1} {𝓐 : Type u_2}
  {Ω : Type u_4} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) ℝ)
  (E : Ω → 𝓔) (a : 𝓐) (ω : Ω) : ℝ

Code

noncomputable
def actionMean (κ : Kernel (𝓔 × 𝓐) ℝ) (E : Ω → 𝓔) (a : 𝓐) (ω : Ω) : ℝ := (κ (E ω, a))[id]

Used by (12)

Actions: Source · Open Issue

`bestAction`🔗

DefinitionLearning.IsBayesAlgEnvSeq.bestAction

Details

A random variable that gives the action with the highest mean feedback.

def

Learning.IsBayesAlgEnvSeq.bestAction.{u_1, u_2, u_4} {𝓔 : Type u_1}
  {𝓐 : Type u_2} {Ω : Type u_4} [MeasurableSpace 𝓔] [MeasurableSpace 𝓐]
  [Nonempty 𝓐] [Fintype 𝓐] (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) ℝ)
  (E : Ω → 𝓔) (ω : Ω) : 𝓐
Learning.IsBayesAlgEnvSeq.bestAction.{u_1,
    u_2, u_4}
  {𝓔 : Type u_1} {𝓐 : Type u_2}
  {Ω : Type u_4} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐] [Nonempty 𝓐]
  [Fintype 𝓐]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) ℝ)
  (E : Ω → 𝓔) (ω : Ω) : 𝓐

Code

noncomputable
def bestAction [Nonempty 𝓐] [Fintype 𝓐] (κ : Kernel (𝓔 × 𝓐) ℝ) (E : Ω → 𝓔) (ω : Ω) : 𝓐 :=
  argmax (fun a ↦ actionMean κ E a ω)

Body uses (2)

Used by (12)

Actions: Source · Open Issue

`policy`🔗

DefinitionBandits.TS.policy

Details

The Thompson sampling policy samples an action according to its probability of being optimal under the posterior over environments given the history so far. The posterior under a uniform algorithm is used to avoid a circular definition.

def

Bandits.TS.policy.{u_1} {K : ℕ} {𝓔 : Type u_1} [MeasurableSpace 𝓔]
  [StandardBorelSpace 𝓔] [Nonempty 𝓔] (hK : 0 < K)
  (Q : MeasureTheory.Measure 𝓔) [MeasureTheory.IsProbabilityMeasure Q]
  (κ : ProbabilityTheory.Kernel (𝓔 × Fin K) ℝ)
  [ProbabilityTheory.IsMarkovKernel κ] (n : ℕ) :
  ProbabilityTheory.Kernel (↥(Finset.Iic n) → Fin K × ℝ) (Fin K)
Bandits.TS.policy.{u_1} {K : ℕ}
  {𝓔 : Type u_1} [MeasurableSpace 𝓔]
  [StandardBorelSpace 𝓔] [Nonempty 𝓔]
  (hK : 0 < K)
  (Q : MeasureTheory.Measure 𝓔)
  [MeasureTheory.IsProbabilityMeasure Q]
  (κ :
    ProbabilityTheory.Kernel (𝓔 × Fin K)
      ℝ)
  [ProbabilityTheory.IsMarkovKernel κ]
  (n : ℕ) :
  ProbabilityTheory.Kernel
    (↥(Finset.Iic n) → Fin K × ℝ) (Fin K)

Code

noncomputable
def TS.policy (hK : 0 < K) (Q : Measure 𝓔) [IsProbabilityMeasure Q] (κ : Kernel (𝓔 × Fin K) ℝ)
    [IsMarkovKernel κ] (n : ℕ) : Kernel (Iic n → (Fin K) × ℝ) (Fin K) :=
  have : Nonempty (Fin K) := Fin.pos_iff_nonempty.mp hK
  (IT.bayesTrajMeasurePosterior Q κ uniformAlgorithm n).map (bestAction κ id)

Body uses (3)

Used by (2)

Actions: Source · Open Issue

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdBayesTrajMeasurePosterior`🔗

InstanceLearning.IT.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdBayesTrajMeasurePosterior

Details

No docstring.

theorem

Learning.IT.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdBayesTrajMeasurePosterior.{u_1,
    u_2, u_3}
  {𝓔 : Type u_3} {𝓐 : Type u_1} {𝓨 : Type u_2} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐] [MeasurableSpace 𝓨] [StandardBorelSpace 𝓔]
  [Nonempty 𝓔] (Q : MeasureTheory.Measure 𝓔)
  [MeasureTheory.IsProbabilityMeasure Q]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) 𝓨)
  [ProbabilityTheory.IsMarkovKernel κ] (alg : Algorithm 𝓐 𝓨) (n : ℕ) :
  ProbabilityTheory.IsMarkovKernel (bayesTrajMeasurePosterior Q κ alg n)
Learning.IT.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdBayesTrajMeasurePosterior.{u_1,
    u_2, u_3}
  {𝓔 : Type u_3} {𝓐 : Type u_1}
  {𝓨 : Type u_2} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐] [MeasurableSpace 𝓨]
  [StandardBorelSpace 𝓔] [Nonempty 𝓔]
  (Q : MeasureTheory.Measure 𝓔)
  [MeasureTheory.IsProbabilityMeasure Q]
  (κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) 𝓨)
  [ProbabilityTheory.IsMarkovKernel κ]
  (alg : Algorithm 𝓐 𝓨) (n : ℕ) :
  ProbabilityTheory.IsMarkovKernel
    (bayesTrajMeasurePosterior Q κ alg n)

Code

deriving IsMarkovKernel

Type uses (2)

Body uses (4)

Used by (1)

instIsMarkovKernelForallSubtypeNatMemFinsetIicProdFinRealPolicy

Actions: Source · Open Issue

Proof

deriving IsMarkovKernel

`measurable_bestAction`🔗

LemmaLearning.IsBayesAlgEnvSeq.measurable_bestAction

Details

No docstring.

theorem

Learning.IsBayesAlgEnvSeq.measurable_bestAction.{u_1, u_2, u_4}
  {𝓔 : Type u_1} {𝓐 : Type u_2} {Ω : Type u_4} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐] [MeasurableSpace Ω] [Nonempty 𝓐] [Fintype 𝓐]
  {κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) ℝ} {E : Ω → 𝓔}
  (hE : Measurable E) : Measurable (bestAction κ E)
Learning.IsBayesAlgEnvSeq.measurable_bestAction.{u_1,
    u_2, u_4}
  {𝓔 : Type u_1} {𝓐 : Type u_2}
  {Ω : Type u_4} [MeasurableSpace 𝓔]
  [MeasurableSpace 𝓐] [MeasurableSpace Ω]
  [Nonempty 𝓐] [Fintype 𝓐]
  {κ : ProbabilityTheory.Kernel (𝓔 × 𝓐) ℝ}
  {E : Ω → 𝓔} (hE : Measurable E) :
  Measurable (bestAction κ E)

Code

lemma measurable_bestAction [Nonempty 𝓐] [Fintype 𝓐] {κ : Kernel (𝓔 × 𝓐) ℝ} {E : Ω → 𝓔}
    (hE : Measurable E) : Measurable (bestAction κ E)

Type uses (1)

bestAction

Body uses (4)

Used by (7)

Actions: Source · Open Issue

Proof

by
  unfold bestAction
  fun_prop

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdFinRealPolicy`🔗

InstanceBandits.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdFinRealPolicy

Details

No docstring.

theorem

Bandits.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdFinRealPolicy.{u_1}
  {K : ℕ} {𝓔 : Type u_1} [MeasurableSpace 𝓔] [StandardBorelSpace 𝓔]
  [Nonempty 𝓔] {hK : 0 < K} {Q : MeasureTheory.Measure 𝓔}
  [MeasureTheory.IsProbabilityMeasure Q]
  {κ : ProbabilityTheory.Kernel (𝓔 × Fin K) ℝ}
  [ProbabilityTheory.IsMarkovKernel κ] {n : ℕ} :
  ProbabilityTheory.IsMarkovKernel (TS.policy hK Q κ n)
Bandits.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdFinRealPolicy.{u_1}
  {K : ℕ} {𝓔 : Type u_1}
  [MeasurableSpace 𝓔]
  [StandardBorelSpace 𝓔] [Nonempty 𝓔]
  {hK : 0 < K}
  {Q : MeasureTheory.Measure 𝓔}
  [MeasureTheory.IsProbabilityMeasure Q]
  {κ :
    ProbabilityTheory.Kernel (𝓔 × Fin K)
      ℝ}
  [ProbabilityTheory.IsMarkovKernel κ]
  {n : ℕ} :
  ProbabilityTheory.IsMarkovKernel
    (TS.policy hK Q κ n)

Code

instance {hK : 0 < K} {Q : Measure 𝓔} [IsProbabilityMeasure Q] {κ : Kernel (𝓔 × Fin K) ℝ}
    [IsMarkovKernel κ] {n : ℕ} : IsMarkovKernel (TS.policy hK Q κ n)

Type uses (1)

policy

Body uses (5)

Used by (1)

tsAlgorithm

Actions: Source · Open Issue

Proof

Kernel.IsMarkovKernel.map _ (by fun_prop)

`initialPolicy`🔗

DefinitionBandits.TS.initialPolicy

Details

The initial action is sampled according to its probability of being optimal under the prior over environments.

def

Bandits.TS.initialPolicy.{u_1} {K : ℕ} {𝓔 : Type u_1}
  [MeasurableSpace 𝓔] (hK : 0 < K) (Q : MeasureTheory.Measure 𝓔)
  (κ : ProbabilityTheory.Kernel (𝓔 × Fin K) ℝ) :
  MeasureTheory.Measure (Fin K)
Bandits.TS.initialPolicy.{u_1} {K : ℕ}
  {𝓔 : Type u_1} [MeasurableSpace 𝓔]
  (hK : 0 < K)
  (Q : MeasureTheory.Measure 𝓔)
  (κ :
    ProbabilityTheory.Kernel (𝓔 × Fin K)
      ℝ) :
  MeasureTheory.Measure (Fin K)

Code

noncomputable
def TS.initialPolicy (hK : 0 < K) (Q : Measure 𝓔) (κ : Kernel (𝓔 × Fin K) ℝ) : Measure (Fin K) :=
  have : Nonempty (Fin K) := Fin.pos_iff_nonempty.mp hK
  Q.map (bestAction κ id)

Body uses (1)

bestAction

Used by (2)

Actions: Source · Open Issue

`instIsProbabilityMeasureFinInitialPolicy`🔗

InstanceBandits.instIsProbabilityMeasureFinInitialPolicy

Details

No docstring.

theorem

Bandits.instIsProbabilityMeasureFinInitialPolicy.{u_1} {K : ℕ}
  {𝓔 : Type u_1} [MeasurableSpace 𝓔] {hK : 0 < K}
  {Q : MeasureTheory.Measure 𝓔} [MeasureTheory.IsProbabilityMeasure Q]
  {κ : ProbabilityTheory.Kernel (𝓔 × Fin K) ℝ} :
  MeasureTheory.IsProbabilityMeasure (TS.initialPolicy hK Q κ)
Bandits.instIsProbabilityMeasureFinInitialPolicy.{u_1}
  {K : ℕ} {𝓔 : Type u_1}
  [MeasurableSpace 𝓔] {hK : 0 < K}
  {Q : MeasureTheory.Measure 𝓔}
  [MeasureTheory.IsProbabilityMeasure Q]
  {κ :
    ProbabilityTheory.Kernel (𝓔 × Fin K)
      ℝ} :
  MeasureTheory.IsProbabilityMeasure
    (TS.initialPolicy hK Q κ)

Code

instance {hK : 0 < K} {Q : Measure 𝓔} [IsProbabilityMeasure Q] {κ : Kernel (𝓔 × Fin K) ℝ} :
    IsProbabilityMeasure (TS.initialPolicy hK Q κ)

Type uses (1)

initialPolicy

Body uses (2)

Used by (1)

tsAlgorithm

Actions: Source · Open Issue

Proof

Measure.isProbabilityMeasure_map (by fun_prop)

`regret`🔗

DefinitionBandits.regret

Details

Regret of a sequence of pulls k : ℕ → 𝓐 at time t for the reward kernel ν ; Kernel 𝓐 ℝ.

def

Bandits.regret.{u_1, u_2} {𝓐 : Type u_1} {Ω : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐} (ν : ProbabilityTheory.Kernel 𝓐 ℝ)
  (A : ℕ → Ω → 𝓐) (t : ℕ) (ω : Ω) : ℝ
Bandits.regret.{u_1, u_2} {𝓐 : Type u_1}
  {Ω : Type u_2} {m𝓐 : MeasurableSpace 𝓐}
  (ν : ProbabilityTheory.Kernel 𝓐 ℝ)
  (A : ℕ → Ω → 𝓐) (t : ℕ) (ω : Ω) : ℝ

Code

noncomputable
def regret (ν : Kernel 𝓐 ℝ) (A : ℕ → Ω → 𝓐) (t : ℕ) (ω : Ω) : ℝ :=
  t * (⨆ a, (ν a)[id]) - ∑ s ∈ range t, (ν (A s ω))[id]

Used by (11)

Actions: Source · Open Issue

LeanMachineLearning exposition

`Bandits.TS.integral_regret_le`🔗

`integral_regret_le`🔗

`IsBayesAlgEnvSeq`🔗

`tsAlgorithm`🔗

`regret`🔗

`Algorithm`🔗

`history`🔗

`action`🔗

`Environment`🔗

`stepKernel`🔗

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdPolicy`🔗

`instIsMarkovKernelProdForallSubtypeNatMemFinsetIicFeedback`🔗

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdStepKernel`🔗

`trajMeasure`🔗

`instIsProbabilityMeasureP0`🔗

`prodLeft`🔗

`bayesStationaryEnv`🔗

`bayesTrajMeasure`🔗

`instIsMarkovKernelν0`🔗

`instIsProbabilityMeasureForallNatProdTrajMeasure`🔗

`instIsProbabilityMeasureForallNatProdBayesTrajMeasure`🔗

`bayesTrajMeasurePosterior`🔗

`randomSampling`🔗

`uniformAlgorithm`🔗

`max`🔗

`exists_argmax`🔗

`argmax`🔗

`actionMean`🔗

`bestAction`🔗

`policy`🔗

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdBayesTrajMeasurePosterior`🔗

`measurable_bestAction`🔗

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdFinRealPolicy`🔗

`initialPolicy`🔗

`instIsProbabilityMeasureFinInitialPolicy`🔗

`regret`🔗

Bandits.TS.integral_regret_le🔗

integral_regret_le🔗

IsBayesAlgEnvSeq🔗

tsAlgorithm🔗

regret🔗

Algorithm🔗

history🔗

action🔗

Environment🔗

stepKernel🔗

instIsMarkovKernelForallSubtypeNatMemFinsetIicProdPolicy🔗

instIsMarkovKernelProdForallSubtypeNatMemFinsetIicFeedback🔗

instIsMarkovKernelForallSubtypeNatMemFinsetIicProdStepKernel🔗

trajMeasure🔗

instIsProbabilityMeasureP0🔗

prodLeft🔗

bayesStationaryEnv🔗

bayesTrajMeasure🔗

instIsMarkovKernelν0🔗

instIsProbabilityMeasureForallNatProdTrajMeasure🔗

instIsProbabilityMeasureForallNatProdBayesTrajMeasure🔗

bayesTrajMeasurePosterior🔗

randomSampling🔗

uniformAlgorithm🔗

max🔗

exists_argmax🔗

argmax🔗

actionMean🔗

bestAction🔗

policy🔗

instIsMarkovKernelForallSubtypeNatMemFinsetIicProdBayesTrajMeasurePosterior🔗

measurable_bestAction🔗

instIsMarkovKernelForallSubtypeNatMemFinsetIicProdFinRealPolicy🔗

initialPolicy🔗

instIsProbabilityMeasureFinInitialPolicy🔗

regret🔗

`Bandits.TS.integral_regret_le`🔗

`integral_regret_le`🔗

`IsBayesAlgEnvSeq`🔗

`tsAlgorithm`🔗

`regret`🔗

`Algorithm`🔗

`history`🔗

`action`🔗

`Environment`🔗

`stepKernel`🔗

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdPolicy`🔗

`instIsMarkovKernelProdForallSubtypeNatMemFinsetIicFeedback`🔗

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdStepKernel`🔗

`trajMeasure`🔗

`instIsProbabilityMeasureP0`🔗

`prodLeft`🔗

`bayesStationaryEnv`🔗

`bayesTrajMeasure`🔗

`instIsMarkovKernelν0`🔗

`instIsProbabilityMeasureForallNatProdTrajMeasure`🔗

`instIsProbabilityMeasureForallNatProdBayesTrajMeasure`🔗

`bayesTrajMeasurePosterior`🔗

`randomSampling`🔗

`uniformAlgorithm`🔗

`max`🔗

`exists_argmax`🔗

`argmax`🔗

`actionMean`🔗

`bestAction`🔗

`policy`🔗

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdBayesTrajMeasurePosterior`🔗

`measurable_bestAction`🔗

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdFinRealPolicy`🔗

`initialPolicy`🔗

`instIsProbabilityMeasureFinInitialPolicy`🔗

`regret`🔗