2.7. Online.Bandit.Algorithms.TS🔗

Thompson Sampling

This file defines the Thompson sampling algorithm. This algorithm samples an action according to its probability of being optimal under the posterior over environments given the history so far.

Main definitions

• tsAlgorithm hK Q κ: a Thompson sampling algorithm with actions in Fin K given hK : 0 < K, a prior distribution over parameters Q : Measure 𝓔, and a Markov kernel κ : Kernel (𝓔 × Fin K) ℝ. This kernel defines how a parameter e : 𝓔 gives rise to a stationary environment: stationaryEnv (κ.sectR e) : Environment (Fin K) ℝ.

Main results

• hasCondDistrib_action : if Thompson sampling has the correct prior over environments, then the conditional distribution of the next action given the history so far is equal to the conditional distribution of the best action given the history so far.

Module LeanMachineLearning.Online.Bandit.Algorithms.TS contains 6 exposed declarations.

• Bandits.TS.policyDefinition · 17 deps
• Bandits.instIsMarkovKernelForallSubtypeNatMemFinsetIicProdFinRealPolicyInstance · 27 deps
• Bandits.TS.initialPolicyDefinition · 5 deps
• Bandits.instIsProbabilityMeasureFinInitialPolicyInstance · 7 deps
• Bandits.tsAlgorithmDefinition · 19 deps
• Bandits.TS.hasCondDistrib_actionLemma · 21 deps