Global diagonal representation of one-round Thompson information
OpenBanditAlgorithm.bayesian_ts_round_global_diagonal_representationbanditsinformation-theorythompson-sampling
Fix a round of Bayesian Thompson sampling with rewards in . There exist weights and, for every arm , probability laws and on pairs consisting of the pre-round history and a bounded reward, such that the expected one-round regret has the representation
all divergences are finite, and the diagonal information is bounded by the increase in mutual information about the optimal arm:
This packages the Bayes-law identity in the final line of Lemma 36.7 into probability measures suitable for the Pinsker step. It isolates the measure-theoretic conditional-law accounting from the finite-dimensional inequality.
Preamble
import Definitions.Def_BayesianHistoryMutualInformation open MeasureTheory ProbabilityTheory InformationTheory open scoped ENNReal BigOperators
Formal statement
namespace BanditAlgorithm
/-- Global conditional-law representation of the one-round regret and the diagonal
part of the conditional mutual information in Lemma 36.7. -/
theorem bayesian_ts_round_global_diagonal_representation
{k n : ℕ} [NeZero k]
(Q : Measure (Fin n → Fin k → ℝ)) [IsProbabilityMeasure Q]
(hQ : ∀ᵐ X ∂Q, ∀ (s : Fin n) (a : Fin k), X s a ∈ Set.Icc (0 : ℝ) 1)
{pi : BanditPolicy k} (hpi : IsBayesianTSPolicy Q pi) (t : Fin n) :
∃ (q : Fin k → ℝ)
(P M : Fin k → Measure (BanditHistory k t.1 × Set.Icc (0 : ℝ) 1)),
(∀ a, IsProbabilityMeasure (P a)) ∧
(∀ a, IsProbabilityMeasure (M a)) ∧
(∀ a, klDiv (P a) (M a) ≠ ∞) ∧
(∫ p, (p.1 t (bayesianOptimalAction p.1) - p.1 t ((p.2 t).1))
∂bayesianAdversarialMeasure Q pi n le_rfl) =
∑ a, q a *
((∫ z, z.2.1 ∂(P a)) - ∫ z, z.2.1 ∂(M a)) ∧
(∑ a, q a ^ 2 * (klDiv (P a) (M a)).toReal) ≤
bayesianHistoryMutualInformation Q pi (t.1 + 1) (Nat.succ_le_iff.mpr t.2) -
bayesianHistoryMutualInformation Q pi t.1 (Nat.le_of_lt t.2) := by
sorry
end BanditAlgorithmSource
Lattimore and Szepesvári, Bandit Algorithms (2020), Lemma 36.7 and its Bayes-law final equality, printed p. 470 (free PDF p. 479), https://tor-lattimore.com/downloads/book/book.pdf; global conditional-law formalization of the diagonal terms.