Adaptive stopped exponential-score supermartingale bound
ProvedBanditAlgorithm.bandit_adaptive_stopped_exp_score_lintegral_le_onebanditsmartingalesprobabilitysubgaussian
Consider any adaptive policy interacting with a stochastic bandit whose centered arm rewards are -subgaussian. Fix an arm , a truncation rank , and a real parameter . Let be the centered sum of rewards from the first pulls of arm , stopped at horizon , and let be its pull count. Then
This is the exact exponential-supermartingale estimate for adaptively selected rewards. It is reusable in Chernoff bounds and Laplace-mixture arguments without losing polynomial factors.
Preamble
import Definitions.Def_ucbStoppedCenteredSum open MeasureTheory ProbabilityTheory
Formal statement
namespace BanditAlgorithm
/-- The stopped exponential score has expectation at most one. -/
theorem bandit_adaptive_stopped_exp_score_lintegral_le_one
{k n : ℕ} (ν : StochasticBandit k)
(hν : IsSubgaussianBandit 1 ν) {π : BanditPolicy k}
(i : Fin k) (u : ℕ) (t : ℝ) :
(∫⁻ h : BanditHistory k n,
ENNReal.ofReal
(Real.exp
(t * armStoppedCenteredSum ν i u n h -
t ^ 2 / 2 *
((min (armPullCount i h) u : ℕ) : ℝ)))
∂banditMeasure ν π n) ≤ 1 := by
sorry
end BanditAlgorithmSource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), canonical reward-stack model in Section 4.6, printed p. 65 / PDF p. 74, and bounded optional stopping in Exercise 4.4, printed p. 69 / PDF p. 78; the same stopped exponential process underlies Eqs. (7.6)–(7.10), printed pp. 106–108 / PDF pp. 115–117.