Stopped centered sum equals the realized first-rank sample mean
ProvedBanditAlgorithm.armStoppedCenteredSum_eq_firstRewardsMeanbanditsprobabilityreward-stackthompson-sampling
Fix an arm and a positive rank . For any finite bandit history in which arm has been pulled at least times, let be the mean of its first realized rewards and let be the arm mean. Then the centered reward sum stopped after the first pulls satisfies
This identity connects the canonical stopped-sum process used for adaptive concentration with the exact realized-rank empirical mean used in Thompson-sampling posterior calculations.
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_ucbStoppedCenteredSum open MeasureTheory ProbabilityTheory
Formal statement
namespace BanditAlgorithm
/-- Once rank s has been realized, the stopped centered sum is s times the centered first-s reward mean. -/
theorem armStoppedCenteredSum_eq_firstRewardsMean
{k m : ℕ} (ν : StochasticBandit k) (i : Fin k) (s : ℕ)
(h : BanditHistory k m) (hs : 0 < s)
(hcount : s ≤ armPullCount i h) :
armStoppedCenteredSum ν i s m h =
(s : ℝ) *
(armFirstRewardsMean i s h - banditArmMean ν i) := by
sorry
end BanditAlgorithmSource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), reward-stack convention in Section 4.6, printed p. 65 / PDF p. 74, and the first-sample empirical means in Section 36.2, printed pp. 463–465 / PDF pp. 472–474. This is a purely formal bridge between those two source-backed representations.