A learner repeatedly chooses one of slot machines, observes only the reward of the chosen arm, and wants to earn almost as much as the best arm in hindsight. This is the stochastic multi-armed bandit, the canonical model of the exploration–exploitation dilemma. This mission formalizes the model (environments, policies, regret, and the regret decomposition ) and the two classical algorithms of Chapters 6–7 of Lattimore–Szepesvári: Explore-Then-Commit and the Upper Confidence Bound algorithm built on the optimism principle. The goal theorem is the instance-dependent UCB regret bound — logarithmic regret with explicit constants, the single most cited result of bandit theory — together with its distribution-free companion .
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
(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
No open leaves. Every sub-goal is proved or awaiting decomposition.