Theorem 1 — Thompson Sampling has O(ln T/Δ + 1/Δ³) regret on two arms
ProvedAgrawalGoyalTS.TwoArmed.thompson_sampling_two_armed_regretConsider the two-armed stochastic bandit problem: arm has a fixed reward distribution supported in with mean , and arm 1 is the unique optimal arm, . Let , and let be the expected regret in time of Thompson Sampling for general stochastic bandits (Algorithm 2). There is an absolute constant such that for every such instance and every ,
This is the first logarithmic finite-time regret bound for Thompson Sampling; its dependence on matches the Lai–Robbins lower bound up to constants.
Formalization Note The paper writes in the sense of its footnote 1; we state it with one universal constant , quantified before the reward distributions, the means and , and for every . The paper's explicit display on p. 8 () is not the formal claim, because its derivation contains an arithmetic slip. Arm 1 of the paper is Lean arm 0; no condition or is assumed.
import Mathlib import Definitions.Def_StochasticBandit import Definitions.Def_AgrawalGoyalTS_TwoArmed_ThompsonSampling open MeasureTheory BanditAlgorithm
namespace AgrawalGoyalTS.TwoArmed
/-- Theorem 1 (p. 3): there is an absolute constant `C > 0` such that for every two-armed
stochastic bandit with rewards supported in `[0,1]` and `μ₁ > μ₂` (arm `0` is the paper's arm 1),
and every horizon `T ≥ 2`, Thompson Sampling (Algorithm 2) has expected regret
`E[R(T)] ≤ C (ln T / Δ + 1 / Δ³)`, `Δ = μ₁ - μ₂`. -/
theorem thompson_sampling_two_armed_regret :
∃ C : ℝ, 0 < C ∧ ∀ ν : StochasticBandit 2, (∀ i, ν.P i (Set.Icc 0 1) = 1) →
banditArmMean ν 1 < banditArmMean ν 0 → ∀ T : ℕ, 2 ≤ T →
tsRegret ν T ≤
ENNReal.ofReal (C * (Real.log T / (banditArmMean ν 0 - banditArmMean ν 1) +
1 / (banditArmMean ν 0 - banditArmMean ν 1) ^ 3)) := by sorry
end AgrawalGoyalTS.TwoArmed
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.