One-step exponential (martingale) identity for the bandit trajectory
ProvedBanditAlgorithm.bandit_one_step_exp_tilt_identitybanditsconcentrationgaussianmartingale
The one-step exponential tilt identity for the canonical bandit model: for a unit-variance Gaussian bandit, any policy, any round , any arm , any tilt and any -measurable ,
In words: tilting the reward of round costs nothing, whether or not arm is the one played. This is the inductive step of every exponential-martingale argument in the chapter, and the only place where the structure of the canonical model is used -- that the law of the trajectory factors as history step kernel (Ionescu--Tulcea), and that conditionally on the history the reward is , whose moment generating function supplies the factor . Everything downstream is bookkeeping on top of this identity.
Preamble
import Definitions.Def_BanditTrajectory import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory NNReal ENNReal
Formal statement
theorem BanditAlgorithm.bandit_one_step_exp_tilt_identity {k : ℕ} (μvec : Fin k → ℝ)
(pol : BanditAlgorithm.BanditPolicy k) (n : ℕ) (a : Fin k) (lam : ℝ)
(F : BanditAlgorithm.BanditHistory k n → ENNReal) (hF : Measurable F) :
∫⁻ ω, F (BanditAlgorithm.banditTrajPrefix k n ω) *
(if (ω n).1 = a then
ENNReal.ofReal (Real.exp (lam * ((ω n).2 - μvec a) - lam ^ 2 / 2)) else 1)
∂(BanditAlgorithm.banditTrajMeasure (BanditAlgorithm.gaussianBandit μvec) pol)
= ∫⁻ ω, F (BanditAlgorithm.banditTrajPrefix k n ω)
∂(BanditAlgorithm.banditTrajMeasure (BanditAlgorithm.gaussianBandit μvec) pol) := by
sorrySource
Standard exponential-martingale construction for the canonical bandit model (Lattimore & Szepesvari, Bandit Algorithms, Section 4.6 for the model; Garivier & Kaufmann, COLT 2016, Section 4 for this use).