`Bandits.ArrayModel.hist_add_one_eq_IicSuccProd'`🔗

This page has the declaration's own card below, then its dependency graph, then a card for each dependency (type dependencies first, then the rest of the transitive closure). For a theorem, the graph and the dependency cards only follow its statement's dependencies (its proof is replaced by sorry, so what it proves doesn't depend on how); for everything else, both the type and the body/value are followed, since their content is part of what later declarations build on.

Minimal Lean file

`hist_add_one_eq_IicSuccProd'`🔗

LemmaBandits.ArrayModel.hist_add_one_eq_IicSuccProd'

Details

No docstring.

theorem

Bandits.ArrayModel.hist_add_one_eq_IicSuccProd'.{u_1, u_2}
  {𝓐 : Type u_1} {R : Type u_2} {m𝓐 : MeasurableSpace 𝓐}
  {mR : MeasurableSpace R} [Nonempty 𝓐] [StandardBorelSpace 𝓐]
  [DecidableEq 𝓐] (alg : Learning.Algorithm 𝓐 R) (ω : probSpace 𝓐 R)
  (n : ℕ) :
  have a := algFunction alg n (hist alg ω n) (Prod.fst ω (n + 1));
  hist alg ω (n + 1) =
    (MeasurableEquiv.symm
        (MeasurableEquiv.IicSuccProd (fun x => 𝓐 × R) n))
      (hist alg ω n, a,
        Prod.snd ω (Learning.pullCount' n (hist alg ω n) a) a)
Bandits.ArrayModel.hist_add_one_eq_IicSuccProd'.{u_1,
    u_2}
  {𝓐 : Type u_1} {R : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {mR : MeasurableSpace R} [Nonempty 𝓐]
  [StandardBorelSpace 𝓐] [DecidableEq 𝓐]
  (alg : Learning.Algorithm 𝓐 R)
  (ω : probSpace 𝓐 R) (n : ℕ) :
  have a :=
    algFunction alg n (hist alg ω n)
      (Prod.fst ω (n + 1));
  hist alg ω (n + 1) =
    (MeasurableEquiv.symm
        (MeasurableEquiv.IicSuccProd
          (fun x => 𝓐 × R) n))
      (hist alg ω n, a,
        Prod.snd ω
          (Learning.pullCount' n
            (hist alg ω n) a)
          a)

Code

lemma hist_add_one_eq_IicSuccProd' [DecidableEq 𝓐] (alg : Algorithm 𝓐 R) (ω : probSpace 𝓐 R)
    (n : ℕ) :
    let a : 𝓐

Type uses (6)

Body uses (1)

hist_add_one

Used by (1)

hist_add_one_eq_IicSuccProd

Actions: Source · Open Issue

Proof

algFunction alg n (hist alg ω n) (ω.1 (n + 1))
    hist alg ω (n + 1) =
      (MeasurableEquiv.IicSuccProd (fun _ ↦ 𝓐 × R) n).symm
        (hist alg ω n, (a, ω.2 (pullCount' n (hist alg ω n) a) a)) := by
  intro a
  rw [hist_add_one]
  ext i : 1
  simp only [Kernel.symm_IicSuccProd, MeasurableEquiv.prodCongr, MeasurableEquiv.refl_toEquiv,
    MeasurableEquiv.piSingleton, eq_rec_constant, MeasurableEquiv.IicProdIoc,
    MeasurableEquiv.trans_apply, MeasurableEquiv.coe_mk, Equiv.prodCongr_apply, Equiv.coe_refl,
    Equiv.coe_fn_mk, Prod.map_apply, id_eq]
  rfl

Dependency graph

Type dependencies (6)

`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

`probSpace`🔗

DefinitionBandits.ArrayModel.probSpace

Details

Probability space for the array model of stochastic bandits.

def

Bandits.ArrayModel.probSpace.{u_1, u_2} (𝓐 : Type u_1) (R : Type u_2) :
  Type (max u_1 u_2)
Bandits.ArrayModel.probSpace.{u_1, u_2}
  (𝓐 : Type u_1) (R : Type u_2) :
  Type (max u_1 u_2)

Code

def probSpace : Type _ := (ℕ → I) × (ℕ → 𝓐 → R)

Used by (64)

Actions: Source · Open Issue

`algFunction`🔗

DefinitionBandits.ArrayModel.algFunction

Details

The next action is the image of the history and a uniform random variable by this function.

def

Bandits.ArrayModel.algFunction.{u_1, u_2} {𝓐 : Type u_1} {R : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐} {mR : MeasurableSpace R} [Nonempty 𝓐]
  [StandardBorelSpace 𝓐] (alg : Learning.Algorithm 𝓐 R) (n : ℕ) :
  (↥(Finset.Iic n) → 𝓐 × R) → ↑unitInterval → 𝓐
Bandits.ArrayModel.algFunction.{u_1, u_2}
  {𝓐 : Type u_1} {R : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {mR : MeasurableSpace R} [Nonempty 𝓐]
  [StandardBorelSpace 𝓐]
  (alg : Learning.Algorithm 𝓐 R) (n : ℕ) :
  (↥(Finset.Iic n) → 𝓐 × R) →
    ↑unitInterval → 𝓐

Code

noncomputable
def algFunction (alg : Algorithm 𝓐 R) (n : ℕ) :
    (Iic n → 𝓐 × R) → I → 𝓐 :=
  (Kernel.exists_measurable_map_eq_unitInterval (alg.policy n)).choose

Type uses (1)

Algorithm

Body uses (1)

instIsMarkovKernelForallSubtypeNatMemFinsetIicProdPolicy

Used by (17)

Actions: Source · Open Issue

`hist`🔗

DefinitionBandits.ArrayModel.hist

Details

History of actions and rewards up to time n in the array model.

def

Bandits.ArrayModel.hist.{u_1, u_2} {𝓐 : Type u_1} {R : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐} {mR : MeasurableSpace R} [Nonempty 𝓐]
  [StandardBorelSpace 𝓐] [DecidableEq 𝓐] (alg : Learning.Algorithm 𝓐 R)
  (ω : probSpace 𝓐 R) (n : ℕ) : ↥(Finset.Iic n) → 𝓐 × R
Bandits.ArrayModel.hist.{u_1, u_2}
  {𝓐 : Type u_1} {R : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {mR : MeasurableSpace R} [Nonempty 𝓐]
  [StandardBorelSpace 𝓐] [DecidableEq 𝓐]
  (alg : Learning.Algorithm 𝓐 R)
  (ω : probSpace 𝓐 R) (n : ℕ) :
  ↥(Finset.Iic n) → 𝓐 × R

Code

noncomputable
def hist [DecidableEq 𝓐] (alg : Algorithm 𝓐 R) (ω : probSpace 𝓐 R) : (n : ℕ) → Iic n → 𝓐 × R
| 0 => fun _ ↦ (initAlgFunction alg (ω.1 0), ω.2 0 (initAlgFunction alg (ω.1 0)))
| n + 1 =>
  let hn : Iic n → 𝓐 × R := hist alg ω n
  let a : 𝓐 := algFunction alg n hn (ω.1 (n + 1))
  fun i ↦ if hin : i ≤ n then hn ⟨i, by simp [hin]⟩ else (a, ω.2 (pullCount' n hn a) a)

Type uses (2)

Body uses (3)

Used by (30)

Actions: Source · Open Issue

`IicSuccProd`🔗

DefinitionMeasurableEquiv.IicSuccProd

Details

Measurable equivalence between a product up to n + 1 and the pair of the product up to n and the space at n + 1.

def

MeasurableEquiv.IicSuccProd.{u_3} (X : ℕ → Type u_3)
  [(n : ℕ) → MeasurableSpace (X n)] (n : ℕ) :
  ((i : ↥(Finset.Iic (n + 1))) → X ↑i) ≃ᵐ
    ((i : ↥(Finset.Iic n)) → X ↑i) × X (n + 1)
MeasurableEquiv.IicSuccProd.{u_3}
  (X : ℕ → Type u_3)
  [(n : ℕ) → MeasurableSpace (X n)]
  (n : ℕ) :
  ((i : ↥(Finset.Iic (n + 1))) → X ↑i) ≃ᵐ
    ((i : ↥(Finset.Iic n)) → X ↑i) ×
      X (n + 1)

Code

def _root_.MeasurableEquiv.IicSuccProd (X : ℕ → Type*) [∀ n, MeasurableSpace (X n)] (n : ℕ) :
    MeasurableEquiv (Π i : Iic (n + 1), X i) ((Π i : Iic n, X i) × X (n + 1)) :=
  (MeasurableEquiv.IicProdIoc (Nat.le_succ n)).symm.trans
    (MeasurableEquiv.prodCongr (MeasurableEquiv.refl _) (MeasurableEquiv.piSingleton n).symm)

Used by (11)

Actions: Source · Open Issue

`pullCount'`🔗

DefinitionLearning.pullCount'

Details

Number of pulls of arm a up to (and including) time n. This is the number of entries in h in which the arm is a.

def

Learning.pullCount'.{u_1, u_2} {𝓐 : Type u_1} {R : Type u_2}
  [DecidableEq 𝓐] (n : ℕ) (h : ↥(Finset.Iic n) → 𝓐 × R) (a : 𝓐) : ℕ
Learning.pullCount'.{u_1, u_2}
  {𝓐 : Type u_1} {R : Type u_2}
  [DecidableEq 𝓐] (n : ℕ)
  (h : ↥(Finset.Iic n) → 𝓐 × R) (a : 𝓐) :
  ℕ

Code

noncomputable
def pullCount' (n : ℕ) (h : Iic n → 𝓐 × R) (a : 𝓐) := #{s | (h s).1 = a}

Used by (29)

Actions: Source · Open Issue

All dependencies, transitively (3)

`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

`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

`initAlgFunction`🔗

DefinitionBandits.ArrayModel.initAlgFunction

Details

The initial action is the image of a uniform random variable by this function.

def

Bandits.ArrayModel.initAlgFunction.{u_1, u_2} {𝓐 : Type u_1}
  {R : Type u_2} {m𝓐 : MeasurableSpace 𝓐} {mR : MeasurableSpace R}
  [Nonempty 𝓐] [StandardBorelSpace 𝓐] (alg : Learning.Algorithm 𝓐 R) :
  ↑unitInterval → 𝓐
Bandits.ArrayModel.initAlgFunction.{u_1,
    u_2}
  {𝓐 : Type u_1} {R : Type u_2}
  {m𝓐 : MeasurableSpace 𝓐}
  {mR : MeasurableSpace R} [Nonempty 𝓐]
  [StandardBorelSpace 𝓐]
  (alg : Learning.Algorithm 𝓐 R) :
  ↑unitInterval → 𝓐

Code

noncomputable
def initAlgFunction (alg : Algorithm 𝓐 R) : I → 𝓐 :=
  (Measure.exists_measurable_map_eq alg.p0).choose

Type uses (1)

Algorithm

Body uses (1)

instIsProbabilityMeasureP0

Used by (12)

Actions: Source · Open Issue

Bandits.ArrayModel.hist_add_one_eq_IicSuccProd'🔗

hist_add_one_eq_IicSuccProd'🔗

Algorithm🔗

probSpace🔗

algFunction🔗

hist🔗

IicSuccProd🔗

pullCount'🔗

instIsMarkovKernelForallSubtypeNatMemFinsetIicProdPolicy🔗

instIsProbabilityMeasureP0🔗

initAlgFunction🔗

`Bandits.ArrayModel.hist_add_one_eq_IicSuccProd'`🔗

`hist_add_one_eq_IicSuccProd'`🔗

`Algorithm`🔗

`probSpace`🔗

`algFunction`🔗

`hist`🔗

`IicSuccProd`🔗

`pullCount'`🔗

`instIsMarkovKernelForallSubtypeNatMemFinsetIicProdPolicy`🔗

`instIsProbabilityMeasureP0`🔗

`initAlgFunction`🔗