The information budget of a k-valued optimal action is at most
ProvedBanditAlgorithm.bayesian_history_mutualInformation_endpoint_boundbanditsentropymutual-informationthompson-sampling
Let , where is the observed length- bandit history and takes values among actions. The empty history carries no information, while the complete history cannot reveal more than the entropy of . Therefore
This is the entropy-budget endpoint used when the per-round information gains telescope.
Preamble
import Definitions.Def_BayesianHistoryMutualInformation open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.bayesian_history_mutualInformation_endpoint_bound
{k n : ℕ} [NeZero k]
(Q : Measure (Fin n → Fin k → ℝ)) [IsProbabilityMeasure Q]
(pi : BanditPolicy k) :
bayesianHistoryMutualInformation Q pi n le_rfl -
bayesianHistoryMutualInformation Q pi 0 (Nat.zero_le n) ≤ Real.log k := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), https://tor-lattimore.com/downloads/book/book.pdf, printed p. 471 (PDF p. 480), proof of Theorem 36.5: the cumulative information gain telescopes and the negentropy diameter on the k-simplex is log k.