Reciprocal summability of the asymptotic-UCB schedule
ProvedBanditAlgorithm.asymptotic_ucb_schedule_reciprocal_sum_boundanalysisbanditsprobabilityucb
Let be the exploration schedule used by asymptotically optimal UCB. For every horizon , its reciprocal weights satisfy
This is the summability estimate requested in Exercise 8.1.
Preamble
import Definitions.Def_asymptoticUcbPolicy
Formal statement
theorem BanditAlgorithm.asymptotic_ucb_schedule_reciprocal_sum_bound (n : ℕ) :
Finset.sum (Finset.Icc 1 n) (fun t ↦ 1 / BanditAlgorithm.asymptoticUcbSchedule t) ≤ 5 / 2 := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge University Press, 2020), Chapter 8, Exercise 8.1, printed p. 117 / PDF p. 126, https://tor-lattimore.com/downloads/book/book.pdf