BanditAlgorithm.bandit_ucb_regret_bound
Provedbanditsregretucb
(UCB regret bound, GOAL) Consider UCB (L&S Algorithm 3) on a stochastic -armed 1-subgaussian bandit: play each arm once, then play
For any horizon , if then
Preamble
import Definitions.Def_banditRegret import Definitions.Def_ucbPolicy open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.bandit_ucb_regret_bound {k : ℕ} (hk : 0 < k) {ν : StochasticBandit k}
(hν : IsSubgaussianBandit 1 ν) {n : ℕ} (hn : 0 < n)
{π : BanditPolicy k} (hπ : IsUCBPolicy (1 / (n : ℝ) ^ 2) π) :
banditRegret ν π n ≤
3 * ∑ i, banditGap ν i +
∑ i ∈ Finset.univ.filter (fun i ↦ 0 < banditGap ν i),
16 * Real.log n / banditGap ν i := by
sorry
Source
L&S Theorem 7.1, p.105