BanditAlgorithm.bandit_kl_ucb_regret_bound
Proved(KL-UCB regret bound, GOAL, L&S Theorem 10.6) If the reward in round is — i.e. the environment is bernoulliBandit for a mean vector — then the regret of Algorithm 8 (KL-UCB with ) satisfies, for every ,
for EVERY family with and at each suboptimal arm (-family encoding of the book's infimum), and furthermore
stated in (a zero/junk divergence contributes ), mirroring the liminf style of bandit_instance_dependent_lower_bound.
import Definitions.Def_bernoulliRelativeEntropy import Definitions.Def_banditRegret open MeasureTheory ProbabilityTheory Filter
theorem BanditAlgorithm.bandit_kl_ucb_regret_bound {k : ℕ} (μvec : Fin k → ℝ)
(hμ : ∀ i, μvec i ∈ Set.Icc (0 : ℝ) 1)
(ν : StochasticBandit k) (hν : ν = bernoulliBandit μvec hμ)
(π : BanditPolicy k) (hπ : IsKLUCBPolicy π) :
(∀ n : ℕ, ∀ ε₁ ε₂ : Fin k → ℝ,
(∀ i, 0 < banditGap ν i →
0 < ε₁ i ∧ 0 < ε₂ i ∧ ε₁ i + ε₂ i < banditGap ν i) →
banditRegret ν π n ≤
∑ i ∈ Finset.univ.filter (fun i ↦ 0 < banditGap ν i),
banditGap ν i *
(Real.log (klucbExploration n) /
bernoulliRelativeEntropy (banditArmMean ν i + ε₁ i)
(banditOptimalMean ν - ε₂ i) +
1 / (2 * ε₁ i ^ 2) + 2 / ε₂ i ^ 2)) ∧
atTop.limsup
(fun n : ℕ ↦ ENNReal.ofReal (banditRegret ν π n / Real.log n)) ≤
∑ i ∈ Finset.univ.filter (fun i ↦ 0 < banditGap ν i),
ENNReal.ofReal (banditGap ν i) /
ENNReal.ofReal
(bernoulliRelativeEntropy (banditArmMean ν i)
(banditOptimalMean ν)) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup and notation. Let
with the real conventions (division by gives ; of a nonpositive number is ; so is finite everywhere). Fix with each , and let be a -armed bandit hypothesized to equal the Bernoulli bandit of this vector: arm 's distribution is on . Write for the (Bochner-integral) mean of arm 's distribution, , . is the canonical history measure of and a policy (built from the empty history by repeatedly drawing an arm from the policy kernel and a reward from that arm), and is the expected regret (integral by convention if not integrable). The schedule is (, ). The index of arm at a length- history is
(; , = pull count and empirical mean with ), and the policy property assumed of is: at every history of every length there is an arm selected with probability one, unpulled if any arm is unpulled, and non-strictly maximizing over all arms if every arm has been pulled. Write viewed in .
Assertion (a conjunction). (1) Finite-horizon bound: for every horizon and all real families , satisfying the hypothesis below,
(2) Asymptotic bound:
where the division on the right is the extended one: for , , and .
Hypotheses.
- Each , and equals the Bernoulli bandit of .
- satisfies the index-policy property above.
- In part (1) only: for every arm with , , , and (strict). At arms with both families are unconstrained.
Edge cases.
- In (1) the denominator is a real number; if it equals , the real convention makes that fraction and the term degenerates to .
- In (2), for an arm with but , the truncated denominator is and the term is , so the right side is and the inequality is trivially satisfied.
- For : so in (1); in (2), so those terms are the truncation of .
- Negative values of truncate to before the limsup.
- For the policy property is unsatisfiable, so both parts hold vacuously; carries the usual conventions (supremum , defaulting integral).
Confirmed by the mission captain (proposal self-audit).