(8.4), p. 72 — Thompson sampling and the optimum have equal expected history-based scores
ProvedTSTutorial.UCBDecomp.eq_8_4bayesian-regretp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability-matchingthompson-sampling
Let be Thompson sampling, using the same measurable optimal-action selector as the Bayesian model. At period , let be any real-valued function determined by the preceding history and the action . Then
Both expectations use the same joint law of the parameter and the actions and outcomes generated by Thompson sampling. The identity lets a history-based score evaluated at the played action be replaced in expectation by the same score evaluated at the optimal action.
Formalization Note The score has type and cannot inspect . Lean period is the paper's . The two expectations are both represented over histories through period .
Preamble
import Mathlib import Definitions.Def_TSTutorial_UCBDecomp_Setting open MeasureTheory open scoped BigOperators
Formal statement
namespace TSTutorial.UCBDecomp
variable {X Y Θ : Type*} [Fintype X] [DecidableEq X] [Nonempty X]
[Fintype Y] [DecidableEq Y] [MeasurableSpace Θ]
/-- Equation (8.4): history-determined scores have equal expectations at TS's action and x*. -/
theorem eq_8_4 (m : Model X Y Θ) (xStar : Θ → X)
(hx : IsOptimalSelector m xStar) (π : Policy X Y)
(hπ : IsThompsonSampling m xStar π) (s : ℕ)
(U : Hist X Y s → X → ℝ) :
(∫ θ, ∑ h : Hist X Y (s + 1), lik m π (s + 1) θ h *
U (init h) (h (Fin.last s)).1 ∂m.prior) =
(∫ θ, ∑ h : Hist X Y (s + 1), lik m π (s + 1) θ h *
U (init h) (xStar θ) ∂m.prior) := by sorry
end TSTutorial.UCBDecomp
Source
Russo, Van Roy, Kazerouni, Osband, Wen, A Tutorial on Thompson Sampling, Found. Trends Mach. Learn. 11(1) (2018), §8.1.2 p. 72, (8.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.