§8.1.2, p. 73 — Thompson sampling's per-period regret equals pessimism plus width
ProvedTSTutorial.UCBDecomp.pessimism_width_decompositionIn the Bayesian decision model, let be a measurable optimal action and let follow Thompson sampling with the same selector. For any period and any history-determined real function on the actions, expected period regret satisfies both equalities
The identity is the bridge from upper-confidence-bound analyses to expected-regret bounds for Thompson sampling. The function is an analysis choice; Thompson sampling does not use it to choose actions.
Formalization Note The conclusion records both displayed equalities. Every expectation uses the actual joint law of the same Thompson-sampling policy. The finite action and outcome specialization, measurable kernel and selector, common tie-break, and zero-based Lean periods follow the setting definition.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_TSTutorial_UCBDecomp_Setting open MeasureTheory open scoped BigOperators
namespace TSTutorial.UCBDecomp
variable {X Y Θ : Type*} [Fintype X] [DecidableEq X] [Nonempty X]
[Fintype Y] [DecidableEq Y] [MeasurableSpace Θ]
/-- The two equalities of the pessimism/width decomposition on p. 73. -/
theorem pessimism_width_decomposition (m : Model X Y Θ) (xStar : Θ → X)
(hx : IsOptimalSelector m xStar) (π : Policy X Y)
(hπ : IsThompsonSampling m xStar π) (s : ℕ)
(U : Hist X Y s → X → ℝ) :
periodRegret m xStar π s =
unshiftedPessimism m xStar π s U + width m π s U ∧
unshiftedPessimism m xStar π s U + width m π s U =
pessimism m xStar π s U + width m π s U := by sorry
end TSTutorial.UCBDecomp
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.