Sharp adaptive stopped-sum Hoeffding bound
ProvedBanditAlgorithm.bandit_adaptive_stopped_centered_sum_tail_halfLet a stochastic bandit be -subgaussian, let a possibly randomized adaptive policy interact with it for rounds, and fix an arm . Stop the centered reward sum for that arm after its first observations. For every , both tails obey the sharp Hoeffding estimate
The result remains valid even when fewer than observations of the arm have occurred by the horizon; the stopped sum then uses all observations that are available.
This is the adaptive reward-stack concentration bridge needed to apply ordinary Bernoulli Hoeffding estimates at a random arm-pull count.
Formalization Note: armStoppedCenteredSum is constructed directly from the finite interaction history. The Lean proof builds the exponential supermartingale with compensator at every selected reward, integrates it through the policy and reward kernels, and applies Chernoff's method with .
import Definitions.Def_ucbStoppedCenteredSum import Mathlib.Data.Fintype.Order import Mathlib.Probability.Kernel.Composition.IntegralCompProd open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.bandit_adaptive_stopped_centered_sum_tail_half
{k n : ℕ} (ν : BanditAlgorithm.StochasticBandit k)
(hν : BanditAlgorithm.IsSubgaussianBandit (1 / 2) ν)
{π : BanditAlgorithm.BanditPolicy k}
(i : Fin k) (u : ℕ) {t : ℝ} (ht : 0 ≤ t) :
(BanditAlgorithm.banditMeasure ν π n).real
{h : BanditAlgorithm.BanditHistory k n |
(u : ℝ) * t ≤
BanditAlgorithm.armStoppedCenteredSum ν i u n h} ≤
Real.exp (-2 * (u : ℝ) * t ^ 2) ∧
(BanditAlgorithm.banditMeasure ν π n).real
{h : BanditAlgorithm.BanditHistory k n |
BanditAlgorithm.armStoppedCenteredSum ν i u n h ≤
-(u : ℝ) * t} ≤
Real.exp (-2 * (u : ℝ) * t ^ 2) := by
sorry