Inequality (6), p. 6 — the fundamental inequality: Σₐ 𝔼_ν[N_{ψ,a}(T)] KL(νₐ, ν′ₐ) ≥ kl(𝔼_ν[Z], 𝔼_ν′[Z])
ProvedExploreFirst.FundIneq.fundamental_inequalityConsider stochastic bandit problems with arms: a bandit problem assigns a probability distribution on with a finite expectation to each arm. A strategy chooses at each round an arm as a measurable function of , where the are independent uniforms on . It receives a reward drawn from and a fresh independent uniform . For a horizon , write and for the law of and its expectation when interacts with , and for the number of rounds with . Let denote the Kullback–Leibler divergence and the Kullback–Leibler divergence between Bernoulli distributions of parameters , given for by
Fundamental inequality. For every strategy , every pair of bandit problems and , every horizon , and every measurable function of with values in ,
Both sides are in , with the convention : an arm with infinite divergence and zero expected number of draws contributes nothing, and no finiteness or moment condition is imposed on the arm distributions.
The paper derives every one of its lower bounds from this single inequality, by choosing an alternative problem and a statistic such as ; this is how it re-derives the Lai–Robbins and Burnetas–Katehakis asymptotic bounds and obtains its non-asymptotic bounds for small horizons.
Formalization Note. The local FullStrategy is the paper's measurable strategy on ; the local fullHistoryMeasure retains all auxiliary uniforms. The same strategy is run under both problems. Integrable id for every arm of both problems expresses §1.1's standing assumption that each arm has a finite expectation; the published StochasticBandit type alone requires only probability laws. Arms are indexed by . The binary divergence is the -valued klBer, which equals where the paper's convention does.
import Mathlib import Definitions.Def_ExploreFirst_FundIneq_FullHistory open MeasureTheory ProbabilityTheory InformationTheory open scoped ENNReal
namespace ExploreFirst.FundIneq
/-- Garivier, Ménard, Stoltz, arXiv:1602.07182v3, §2, p. 6, inequality (6). The information
`I_T` contains every auxiliary uniform and reward through round `T`. Each arm law has a finite
expectation, as required for a bandit problem in §1.1. The same strategy runs under both problems. -/
theorem fundamental_inequality {K : ℕ} (ν ν' : BanditAlgorithm.StochasticBandit K)
(hν : ∀ a, Integrable id (ν.P a)) (hν' : ∀ a, Integrable id (ν'.P a))
(ψ : FullStrategy K) (T : ℕ)
(Z : FullHistory T → ℝ) (hZ : Measurable Z)
(hZ01 : ∀ h, Z h ∈ Set.Icc (0 : ℝ) 1) :
klBer (∫ h, Z h ∂(fullHistoryMeasure ν ψ T))
(∫ h, Z h ∂(fullHistoryMeasure ν' ψ T))
≤ ∑ a, ENNReal.ofReal (fullExpPulls ν ψ T a) * klDiv (ν.P a) (ν'.P a) := by sorry
end ExploreFirst.FundIneq
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.