Bayesian regret decomposes into one-round expectations
ProvedBanditAlgorithm.bayesianAdversarialRegret_eq_sum_round_integralbanditsbayesian-regretthompson-sampling
Let be the action with largest total reward and let be the actions in the Bayesian adversarial-bandit trajectory. For a prior supported on reward matrices in , Bayesian regret decomposes round by round:
The expectation is taken under the terminal joint law of the reward matrix and observed trajectory.
Preamble
import Definitions.Def_ThompsonSampling open MeasureTheory ProbabilityTheory open scoped BigOperators
Formal statement
theorem BanditAlgorithm.bayesianAdversarialRegret_eq_sum_round_integral {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)
(pi : BanditPolicy k) :
bayesianAdversarialRegret Q pi =
∑ t, ∫ p, (p.1 t (bayesianOptimalAction p.1) - p.1 t ((p.2 t).1))
∂bayesianAdversarialMeasure Q pi n le_rfl := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), https://tor-lattimore.com/downloads/book/book.pdf, printed p. 469 (PDF p. 478), definition of BR_n immediately before Theorem 36.5, followed by linearity of expectation.