BanditAlgorithm.bandit_ucb_minimax_regret_bound
Provedbanditsregretucb
(UCB distribution-free bound) If , the regret of UCB (Algorithm 3) on any environment is bounded by
Preamble
import Definitions.Def_banditRegret import Definitions.Def_ucbPolicy open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.bandit_ucb_minimax_regret_bound {k : ℕ} (hk : 0 < k)
{ν : StochasticBandit k} (hν : IsSubgaussianBandit 1 ν) {n : ℕ} (hn : 0 < n)
{π : BanditPolicy k} (hπ : IsUCBPolicy (1 / (n : ℝ) ^ 2) π) :
banditRegret ν π n ≤
8 * Real.sqrt (n * k * Real.log n) + 3 * ∑ i, banditGap ν i := by
sorry
Source
L&S Theorem 7.2, p.108