One-rank Gaussian reciprocal posterior-tail estimate
ProvedBanditAlgorithm.gaussian_exact_rank_reciprocal_tail_expectation_boundbanditsgaussianprobabilitythompson-sampling
Consider an arbitrary adaptive policy on a unit-variance Gaussian bandit. Fix an arm , a realized reward rank , and . Let be the posterior Gaussian probability of exceeding after the first rewards of arm . There is a universal constant such that, at every horizon ,
The event ensures that the posterior mean uses exactly realized rewards. Summing this rankwise estimate gives the finite-horizon optimal-arm reciprocal-tail bound used in Gaussian Thompson sampling.
Formalization Note The nonnegative expectation is encoded as a lintegral.
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory ENNReal
Formal statement
namespace BanditAlgorithm
/-- One-rank Gaussian reciprocal-posterior-tail estimate. -/
theorem gaussian_exact_rank_reciprocal_tail_expectation_bound :
∃ C : ℝ, 0 < C ∧
∀ (k : ℕ) [NeZero k] (μvec : Fin k → ℝ) (π : BanditPolicy k),
∀ (i : Fin k) (s : ℕ), 0 < s →
∀ ε : ℝ, 0 < ε →
∀ n : ℕ,
(∫⁻ h,
if s < armPullCount i h then
ENNReal.ofReal
(1 / gaussianTSTailProb i s
(banditArmMean (gaussianBandit μvec) i - ε) h - 1)
else 0
∂banditMeasure (gaussianBandit μvec) π n) ≤
ENNReal.ofReal (C / ((s : ℝ) * ε ^ 2)) := by
sorry
end BanditAlgorithmSource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Exercise 36.6(a) and the Gaussian lower-tail hint, printed p. 475 / PDF p. 484; reward-stack convention in Section 4.6 and Theorem 36.2, printed pp. 463–465 / PDF pp. 472–474. This is the fixed-rank estimate whose harmonic summation yields the finite-horizon form of Exercise 36.6(a).