BanditAlgorithm.thompson_sampling_bayesian_regret
Proved(Bayesian regret, information-theoretic; L&S Theorem 36.5) For the Bayesian -armed adversarial bandit of §36.4 — reward matrix drawn from an arbitrary prior — Thompson sampling (the policy playing each action according to the conditional probability that it is optimal given the history) satisfies
(Proved in the book via the generic information-ratio Theorem 36.6 with the negentropy potential and Lemma 36.7's bound .)
import Definitions.Def_ThompsonSampling open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.thompson_sampling_bayesian_regret {k n : ℕ} [NeZero k]
(Q : Measure (Fin n → Fin k → ℝ)) [IsProbabilityMeasure Q]
(hQ : ∀ᵐ X ∂Q, ∀ (t : Fin n) (a : Fin k), X t a ∈ Set.Icc (0 : ℝ) 1)
{π : BanditPolicy k} (hπ : IsBayesianTSPolicy Q π) :
bayesianAdversarialRegret Q π ≤ Real.sqrt (k * n * Real.log k / 2) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup. Fix arms (typeclass) and a horizon ; is a probability measure ("prior") on reward tables . In the interaction law, ; at each round the policy draws arm from its kernel applied to the past (arm, reward) pairs only (never the table), and the observed reward is deterministically . With the least-index maximizer of , the Bayesian regret is under the joint (table, history) law at horizon . " is a Bayesian TS policy for " means: for every , the joint law of (first observed rounds, ) equals the law of the first rounds composed with 's round- kernel — the round- action is distributed as the posterior law of the optimal action given the first observations.
Assertion.
Hypotheses.
- ; arbitrary (including ); a probability measure.
- -almost every table has all entries in .
- satisfies the Bayesian TS distributional identity above for this and this .
Edge cases.
- : , so the claim reads .
- : the regret is the expectation of an empty sum and the bound is .
- carries the Bochner convention (value if the integrand is not integrable).
- The constraint is only -almost-everywhere; the square root and logarithm are the real functions.
Confirmed by the mission captain (proposal self-audit).